托馬蘇洛算法

托馬蘇洛算法（英語：Tomasulo algorithm）是IBM羅伯特·托馬蘇洛1967年所研發用來改善處理器亂序執行指令級並行性的硬件算法。

概述

在處理器中，先後執行的指令之間經常具有相關性（例如後一條指令用到前一條指令向寄存器寫入的結果），因此早期簡單的處理器使後續指令停頓，直到其所需的資源已經由前序指令準備就緒。托馬蘇洛算法則通過動態調度的方式，在不影響結果正確性的前提下，重新排列指令實際執行的順序（亂序執行），提高時間利用效率。IBM System/360 Model 91處理器的浮點運算器中率先使用了這種算法。

該算法與之前同樣用於實現指令流水線動態調度的計分板不同在於它使用了寄存器重命名機制。指令之間具有數據相關性（例如後條指令的源寄存器恰好是前條指令要寫入的目標寄存器），進行動態調度時必須避免三類冒險：寫後讀（Read-after-Write, RAW）、寫後寫（Write-after-Write, WAW）、讀後寫（Write-after-Read, WAR）。第一種冒險也被稱為真數據相關（true data dependence），而後兩種冒險則並沒有那麼致命，它們可以由寄存器重命名來予以解決。托馬蘇洛算法使用了一個共享數據總線（common data bus, CDB）將已計算出的值廣播給所有需要這個值作為指令源操作數的保留站。該算法儘可能降低了使用計分板技術導致的流水線停頓，從而改善了並行計算的效率。

具體流程

在指令的發射（issue）階段，如果操作數和保留站都準備就緒，那麼指令就可以直接發射並執行。如果操作數未就緒，則進入保留站的指令會跟蹤即將產生這個所需操作數的那個功能單元。如果連可用的保留站功能單元都已經不夠用，那麼該指令必須被停頓。為了化解讀後寫（WAR）和寫後寫（WAW）衝突，需要在該階段進行指令的寄存器重命名。從指令隊列中取出下一條指令，如果其所用到的操作數目前位於寄存器中，那麼如果與指令匹配的功能單元（這類處理器通常具有多個功能單元以發揮指令級並行的優勢）當前可用，則發射該指令；否則，由於沒有可用的功能單元，指令被停頓，直到保留站或緩存可用。儘管執行時可能並未按照指令代碼的先後順序，但是它們在發射過程還是按照原先的順序。這是為了確保指令順序執行時的一些現象，例如處理器異常，能夠以順序執行時的同樣順序出現。下一個階段為執行階段。在該階段，指令對應的操作被執行。執行前需要保證所有操作數可用，同時寫後讀（RAW）衝突已經被化解。系統通過計算有效地址來避免存儲區的衝突，從而保證程序的正確性。最後的階段為寫結果階段，算術邏輯單元（ALU）的計算結果被寫回到寄存器，以及任何正在等待該結果的保留站中，如果是存儲（store）指令，則寫回到存儲器中。

相關條目

• 指令級並行
• 亂序執行
• 寄存器重命名
• 計分板 (處理器)
• 重排序緩衝區

外部連結

• Dynamic Scheduling - Tomasulo's Algorithm（頁面存檔備份，存於網際網路檔案館）
• Web based Java demo of Tomasulo's algorithm

學術文獻

• An Efficient Algorithm for Exploiting Multiple Arithmetic Units（頁面存檔備份，存於網際網路檔案館）, IBM Journal of Research and Development, 11(1):25-33, January 1967.
• WebHASE: Tomasulo's Algorithm: HASE Java applet simulation of the Tomasulo's Algorithm（頁面存檔備份，存於網際網路檔案館）, Institute for Computing Systems Architecture, Edinburgh University.
• TOMASULO'S ALGORITHM FOR DYNAMIC SCHEDULING（頁面存檔備份，存於網際網路檔案館）
• Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson