Tomasulo算法是由Robert Tomasulo 設計的，因而以他的名字命名。IBM360/91機器中的浮點部件首先採用了這種方法。其核心思想是：記錄和檢測指令相關，運算元一旦就緒就立即執行，把發生RAW（寫後讀）衝突的可能性減少到最少。通過暫存器換名來消除WAR（讀後寫）和WAW（寫後寫）衝突。
基本介紹
- 中文名：tomasulo算法
- 發明：Robert Tomasulo
- 屬性：一種算法
- 名字由來：以發明者名字命名
歷史,概述,具體流程,保留站,結構圖,
歷史
在CDC 6600三年之後(1966)，為IBM 360/91設計。
目標：即使在沒有特殊編譯支持的情況下，也能取得高性能。
IBM 360 和CDC 6600指令系統體系結構之間的差異：
IBM的每條指令有兩個暫存器描述符(registerspecifiers),而CDC 6600有三個；IBM有四個浮點暫存器，而CDC 6600有八個。
概述
在處理器中，先後執行的指令之間經常具有相關性（例如後一條指令用到前一條指令向暫存器寫入的結果），因此早期簡單的處理器使後續指令停頓，直到其所需的資源已經由前序指令準備就緒。Tomasulo算法則通過動態調度的方式，在不影響結果正確性的前提下，重新排列指令實際執行的順序（亂序執行），提高時間利用效率。IBM System/360 Model 91處理器的浮點運算器中率先使用了這種算法。
該算法與之前同樣用於實現指令流水線動態調度的計分板不同在於它使用了暫存器重命名機制。指令之間具有數據相關性（例如後條指令的源暫存器恰好是前條指令要寫入的目標暫存器），進行動態調度時必須避免三類冒險：寫後讀（Read-after-Write, RAW）、寫後寫（Write-after-Write, WAW）、讀後寫（Write-after-Read, WAR）。第一種冒險也被稱為真數據相關（true data dependence），而後兩種冒險則並沒有那么致命，它們可以由暫存器重命名來予以解決。Tomasulo算法使用了一個共享數據匯流排（common data bus, CDB）將已計算出的值廣播給所有需要這個值作為指令源運算元的保留站。該算法儘可能降低了使用計分板技術導致的流水線停頓，從而改善了並行計算的效率。
具體流程
在指令的發射（issue）階段，如果運算元和保留站都準備就緒，那么指令就可以直接發射並執行。如果運算元未就緒，則進入保留站的指令會跟蹤即將產生這個所需運算元的那個功能單元。如果連可用的保留站功能單元都已經不夠用，那么該指令必須被停頓。為了化解讀後寫（WAR）和寫後寫（WAW）衝突，需要在該階段進行指令的暫存器重命名。從指令佇列中取出下一條指令，如果其所用到的運算元目前位於暫存器中，那么如果與指令匹配的功能單元（這類處理器通常具有多個功能單元以發揮指令級並行的優勢）當前可用，則發射該指令；否則，由於沒有可用的功能單元，指令被停頓，直到保留站或快取可用。儘管執行時可能並未按照指令代碼的先後順序，但是它們在發射過程還是按照原先的順序。這是為了確保指令順序執行時的一些現象，例如處理器異常，能夠以順序執行時的同樣順序出現。下一個階段為執行階段。在該階段，指令對應的操作被執行。執行前需要保證所有運算元可用，同時寫後讀（RAW）衝突已經被化解。系統通過計算有效地址來避免存儲區的衝突，從而保證程式的正確性。最後的階段為寫結果階段，算術邏輯單元（ALU）的計算結果被寫回到暫存器，以及任何正在等待該結果的保留站中，如果是存儲（store）指令，則寫回到存儲器中。
保留站
控制及緩衝器分布於運算單元(FU) 與Scoreboard；功能部件緩衝器稱為"保留站(reservationstations)"; 存放未決的運算元。指令中的暫存器被數值或者指向保留站的指針代替；這一過程稱為暫存器換名(register renaming)；消除WAR,WAW冒險保留站比實際暫存器多，因而可以完成最佳化編譯器所不能完成的一些工作。
結構圖
Tomasulo算法的三段
1.Issue―從FP Op Queue中取出指令
如果保留站空閒(無結構冒險),
2.Execution―對運算元執行操作(EX)
如果兩個運算元都已就緒,就執行;
如果沒有就緒,就觀測公共數據匯流排等待所需結果
3.Write result―完成執行(WB)
通過公共數據匯流排將結果寫入到所有等待的部件;
