複製鏈接
請複製以下鏈接發送給好友

tomasulo算法

鎖定
Tomasulo算法是由Robert Tomasulo 設計的,因而以他的名字命名。IBM360/91機器中的浮點部件首先採用了這種方法。其核心思想是:記錄和檢測指令相關,操作數一旦就緒就立即執行,把發生RAW(寫後讀)衝突的可能性減少到最少。通過寄存器換名來消除WAR(讀後寫)和WAW(寫後寫)衝突。
中文名
tomasulo算法
發    明
Robert Tomasulo
屬    性
一種算法
名字由來
以發明者名字命名

tomasulo算法發展歷史

在CDC 6600三年之後(1966),為IBM 360/91設計。
目標:即使在沒有特殊編譯支持的情況下,也能取得高性能。
IBM 360 和CDC 6600指令系統體系結構之間的差異:
IBM的每條指令有兩個寄存器描述符(registerspecifiers),而CDC 6600有三個;IBM有四個浮點寄存器,而CDC 6600有八個。 [1] 

tomasulo算法產品介紹

在處理器中,先後執行的指令之間經常具有相關性(例如後一條指令用到前一條指令向寄存器寫入的結果),因此早期簡單的處理器使後續指令停頓,直到其所需的資源已經由前序指令準備就緒。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)將已計算出的值廣播給所有需要這個值作為指令源操作數的保留站。該算法儘可能降低了使用計分板技術導致的流水線停頓,從而改善了並行計算的效率。 [2] 

tomasulo算法具體流程

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

tomasulo算法保留站

控制及緩衝器分佈於運算單元(FU) 與Scoreboard;功能部件緩衝器稱為"保留站(reservationstations)"; 存放未決的操作數。指令中的寄存器被數值或者指向保留站的指針代替;這一過程稱為寄存器換名(register renaming);消除WAR,WAW冒險保留站比實際寄存器多,因而可以完成優化編譯器所不能完成的一些工作。 [2] 

tomasulo算法結構圖

Tomasulo算法的三段
1.Issue―從FP Op Queue中取出指令
如果保留站空閒(無結構冒險),
控制機制發射指令&發送操作數(對寄存器進行換名).
2.Execution―對操作數執行操作(EX)
如果兩個操作數都已就緒,就執行;
如果沒有就緒,就觀測公共數據總線等待所需結果
3.Write result―完成執行(WB)
通過公共數據總線將結果寫入到所有等待的部件; [1] 
參考資料
  • 1.    An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM Journal of Research and Development, 11(1):25-33, January 1967.
  • 2.    John L. Hennessy, David A. Patterson. Computer architecture : a Quantitative Approach (Fourth edition). Elsevier. ISBN 978-0-12-370490-0.