[心得] catchup的機制

看板Emulator (模擬器)作者erspicu (.)時間1天前 (2026/04/09 23:23)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串1/1

這篇比較適合對模擬器開發相關議題有興趣的人閱讀說白話就是...我太小看nes紅白機覺得現代cpu效能輾壓過去40年歷史的老主機除了誇張的audio跟video dsp處理鍊覺得效能綽綽有餘再把一般常理上模擬器都不會使用的精確timing途徑給加入但這段是用tricnes的設計我的專案比較牽涉學術嘗試或是個人好奇各方面驗證我的版權宣告: 本專案採用 WTFPL（Do What The Fuck You Want To Public License）授權。您可以自由地參考、分享、使用、修改或將本專案的程式碼整合到您自己的作品中——用於任何目的——完全沒有任何限制。我認為 AI 輔助開發建立在網路上每位開發者共享的知識之上，將成果回饋分享是理所當然的。本專案不保留任何著作權。它是很瘋狂的概念運算量是相當多倍結果就是效能完全被吃掉後面再搞啥ultra輸出我這台電腦到6x也gg (但其實那個後來應該都會搬遷給gpu去算就是) 能解決的方法就是把這種到達接近電路設計物理層級的timing模型做catchup簡化其實多數模擬器都是基於catchup做簡化版的timing 所以test rom拿分幾乎一定會失敗而我是倒過來用暴力輾壓的timing最後再追求簡化但會不會成功也不知道雖然有ai輔助工具開發但那種感覺很像將軍帶頭打仗還是要有一定策略.相關領域知識的判斷能力才能殺敵而且感覺接下來的挑戰不一等能成功牽涉到數學能力好在有test rom能測試結果不然會被ai幻覺搞死都無從驗證成不成功都無所謂天下武功唯快不破新的cpu出來效能再次暴力輾壓就不是啥問題了下面一些ai回覆可以看看 ====== TRICNES的模擬器雖然精確度很高,用到了極為複雜的有限狀態機,導致計算COST非常龐大, 就我的理解模擬器的TIMING模型其實描述的就是一個硬體有現狀狀態機狀態,不知道我的認知是否正確? 你的理解**完全正確**，而且一針見血！你精準地抓到了硬體模擬（Hardware Emulation）最核心的本質：**一個追求「週期精確（Cycle-Accurate）」的模擬器，其 Timing 模型就是在軟體層面重建真實硬體的有限狀態機（Finite State Machine, FSM）。** 真實的復古遊戲機（如 NES）內部其實就是由多個獨立但互相連動的 FSM 組成的（CPU、 PPU、APU 等）。TriCNES 之所以擁有極高的精確度，正是因為它選擇了最硬派的做法— —在軟體中 1:1 刻畫出這些狀態機的每一個微小狀態。但正如你所見，這也導致了運算成本（Cost）的暴增。為什麼在軟體裡跑硬體的 FSM 會這麼吃效能？這牽涉到軟硬體本質上的差異： ### 1. 「平行」與「循序」的維度打擊 * **真實硬體（平行）：** 當 NES 的石英震盪器發出一個時脈訊號（Clock Tick），硬體內部的邏輯閘、暫存器、計數器是**同時且瞬間**改變狀態的。硬體的 FSM 推進是不需要「運算時間」的，它是物理電路特性的自然結果。 * **模擬器軟體（循序）：** 現代 PC 的 CPU 只能一行一行執行程式碼。為了一次 Clock Tick，軟體必須循序漸進地去檢查：「CPU 現在在什麼狀態？PPU 畫到哪個像素了？APU 的計時器到了沒？中斷線（IRQ）有沒有被拉高？」這種把「平行發生的物理現象」攤平成「循序執行的軟體指令」的過程，就是巨大的效能黑洞。 ### 2. 分支預測的噩夢（Branch Prediction Nightmare）在軟體中實作 FSM，最常見的做法就是巨大的 `switch/case` 或是極深層的嵌套 `if/else`。 * 以 TriCNES 為例，PPU 每畫一個像素（Dot），軟體就得跑進一個巨大的 FSM 去判斷：「現在是可見掃描線嗎？是第幾個週期？要抓背景還是 Sprite？要不要觸發 Sprite 0 Hit？」 * 現代 PC 的 CPU 非常依賴「分支預測（Branch Prediction）」來加速執行。但模擬器中的狀態機跳轉極度頻繁且往往不具規律（取決於遊戲當下的指令與畫面），這會導致 PC 的 CPU 一直猜錯分支，不斷清空指令管線（Pipeline Flush），白白浪費大量效能。 ### 3. 顆粒度越細，開銷越大（Granularity） * **指令級精確（Instruction-Accurate）：** 較早期的模擬器（效能好）是「一口氣跑完一個 CPU 指令」，然後直接把時間加上去（例如 `LDA` 算 4 個 Clock），接著讓 PPU 一口氣追上這 12 個 PPU Clock（NES 中 PPU 速度是 CPU 的 3 倍）。這種做法 FSM 顆粒度大，效能極佳，但在某些極限利用硬體時序的遊戲中會產生破圖或當機。 * **週期級精確（Cycle-Accurate）：** 像 TriCNES 這種極致的模擬器，它不允許「一口氣跑完」。它會把一個 `LDA` 指令拆成 4 個獨立的狀態（Fetch opcode, Fetch address, Read memory 等）。這意味著軟體的 FSM 迴圈每秒鐘要執行數百萬次（NES CPU 約 1.79 MHz），每一次都要做大量的狀態檢查與同步。 ### 總結你的認知非常正確。TriCNES 的高相容性，是用無數個極度繁瑣的狀態檢查換來的。它放棄了用「捷徑（Hack 或 Batching）」來模擬結果，而是選擇老老實實地模擬「產生結果的過程」。這種架構在學術與保存歷史上是非常完美的，但在軟體工程上，如何用現代 CPU 的特性（如 SIMD、JIT 編譯、減少記憶體存取、攤平分支）去榨乾這些 FSM 的效能，就成了模擬器開發者最頭痛也最著迷的挑戰了。 ==== 我的意思是比較針對於有限狀態機的簡化,由於目前運算量太大,目前正在尋找簡化有限狀態機的方式,或是說有限狀態機本身就概念核心,無法再進行等價交換精減?這是一個非常深奧且直指計算機科學核心的問題！你已經碰觸到了硬體模擬效能的天花板邊界。針對你的問題：「**有限狀態機（FSM）本身是否就是概念核心，無法再進行等價交換精簡？**」答案是：**FSM 的「外部可觀測行為（Observable Behavior）」是絕對不可妥協的核心，但 FSM 的「內部數學表達與推進方式」有著極大的等價交換與降維空間！** 在計算機科學理論中，對於 FSM 的簡化有幾個不同層次的「等價交換」策略。針對你目前遇到運算量龐大的問題，我們可以從以下三個維度來拆解： --- ### 維度一：數學理論上的「狀態最小化」（State Minimization）在自動機理論（Automata Theory）中，有一個經典演算法叫做 **Hopcroft 演算法**（或是 DFA 最小化）。它的核心概念是：**「如果兩個狀態在接受任何相同的輸入後，都會產生相同的輸出，並轉移到相同的下一個狀態，那麼這兩個狀態在數學上是等價的，可以合併。」** * **在模擬器的現實是：** 很遺憾地，這招在 NES 這種週期精確（Cycle-Accurate）的模擬器中**幾乎無效**。因為 PPU 畫面上每一個 Clock 輸出的像素（Pixel）位置都不一樣，或者 CPU 每一個 Clock 的記憶體總線狀態都不一樣。這意味著在一個 341 個 Clock 的掃描線中，這 341 個狀態在數學上都是「不可替代且獨立的」。 * **結論：** FSM 的「狀態數量集合 $|S|$」在硬體模擬中，通常已經是物理極限，無法在不破壞精確度的情況下被刪減。 --- ### 維度二：運算層面的「狀態轉移函數」化簡（Function Approximation）既然狀態數量不能少，我們只能針對狀態轉移函數 $\delta(s_t, input_t) = s_{t+1}$ 開刀。你目前程式碼中龐大的 `switch` 或 `if-else` 就是在實作這個 $\delta$ 函數。 1. **純算術取代邏輯跳轉（你正在做的事）：** 就像我們之前用 `((bit << 2) - 2)` 來取代 `if (bit == 1) +2 else -2`。我們把離散的邏輯分支，轉換成了連續的代數方程式。這在數學上是完美的等價交換，且對 CPU 管線極度友善。 2. **狀態編碼的藝術（State Encoding）：** 不要用 `int state = 1, 2, 3...` 這種人類好讀的數字來代表狀態。如果我們精心設計狀態的二進位編碼（例如 **One-Hot Encoding** 或 **Gray Code**），我們可以讓狀態轉移變成純粹的位元平移（Shift）或位元反轉（XOR）。 * *例子：* APU 的 Noise 頻道就是一個 LFSR（線性回饋移位暫存器），它本質上是一個擁有 32767 個狀態的 FSM。但我們不需要寫 32767 個 `if`，我們只用了一行位元運算 `(lfsr >> 1) | (fb << 14)` 就完美表達了整個 FSM 的轉移矩陣！ --- ### 維度三：架構層面的降維打擊 —— 從「步進」到「時間躍遷」（Catch-up / Event-Driven）這才是現代高效能模擬器（如 Mesen, bsnes）能夠在保持 100% 週期精確的同時，運算量比 TriCNES 低上好幾倍的終極數學等價交換！目前你的架構是 **「輪詢式步進（Polling / Tick-based）」**： ```csharp // FSM 數學式： s(t+1) = f( s(t) ) while (true) { CPU_Tick(); // 往前 1 步 PPU_Tick(); // 往前 3 步 APU_Tick(); // 往前 1 步 } ``` 這種做法最保險，但即使 PPU 正在畫連續 256 個毫無變化的背景像素，你的迴圈還是得空轉 256 次狀態機判斷。 **等價交換：時間戳與事件驅動（Timestamping & Catch-up）** 在數學上，如果一個 FSM 在接下來的 $N$ 步之內，都沒有外部輸入（$\Sigma$ 為空或不變），那麼我們可以積分（推導）出一個躍遷函數 $\Delta$： $$s_{t+N} = \Delta(s_t, N)$$ 這意味著：**我們不需要一步一步走，我們可以直接用數學公式「算」出 $N$ 步之後的狀態！** * **實作概念：** 1. CPU 執行了一個耗時 12 步的指令。CPU 內部時間標記為 `cpu_time = 12`。 2. PPU 此時時間標記為 `ppu_time = 0`。 3. 因為 CPU 在這 12 步內沒有去讀寫 PPU 的暫存器（沒有發生互動），所以 PPU 這 36 步（$12 \times 3$）的行為是完全可預測的。 4. 我們直接呼叫 `PPU_CatchUp(36)`。在這個函數裡，我們**不寫迴圈**，而是用除法和餘數（Modulo），直接算出 36 步後 PPU 的 `scanline` 和 `dot` 在哪裡，並一次性把這 36 步的像素批次填入畫面緩衝區！ ### 總結 1. **可以精簡嗎？** FSM 作為概念核心是不可消滅的，但其**運算過程**絕對可以被等價精簡。 2. **微觀的精簡：** 繼續利用 SWAR、Bitmask、代數方程式來消除 $\delta$ 函數中的條件分支（你已經做得非常頂尖了）。 3. **宏觀的精簡（未來方向）：** 如果你覺得目前的運算量還是太大，你最終必須從 `PPU_Tick()` 的「一期一會」，走向 `PPU_CatchUp(cycles)` 的「時間躍遷」。這是將 FSM 從「離散的一階遞迴數列」轉化為「連續時間函數」的最強大數學等價交換！ =========== 相關分析整理文件都在下面 https://github.com/erspicu/AprNes/tree/master/MD/catchup_study 主要可以閱讀 https://tinyurl.com/555k3p75 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 182.233.248.16 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Emulator/M.1775748182.A.623.html