王 磊
(陜西廣播電視大學 計算機與信息管理教學部,陜西 西安 710119)
摘 要:為消除數據競爭,可通過旁路控制機構或其它技術手段來解決,但仍然不能從根本上消除數據競爭。針對數據相關的不可避免性,采用流水線的動態調度算法來解決數據競爭問題,常用的動態調度算法是Tomasulo算法和記分牌調度算法,分析了Tomasulo算法和記分牌調度算法的基本思想和算法實現,對他們的異同進行了分析說明,實驗證明,動態調度算法具有很好的消除數據競爭效果。
關鍵詞:數據競爭;動態調度;Tomasulo算法;記分牌調度算法
中圖分類號:TP368.1 文獻標識碼:A 文章編號:1003-7241(2013)06-0023-04
1 引言
為滿足處理器性能增長的要求,提高處理器性能,要求處理器具有每個周期能發射執行多條指令的能力,超標量微處理器可以同時發射執行多條指令,但也同時增加了相關性機率。可以通過旁路控制機構,編譯技術調度指令序列等手段分開具有相關性的指令,來使競爭數目和性能損失減小到最低程度,但不可避免的數據相關使得數據競爭不可能完全消除。文獻[1][2]分析了數據、結構、控制相關性等問題,提出了解決方法,并提到了動態轉移預測和重排序緩沖機制。針對超標量體系中遇到的數據相關和結構相關的問題,討論了流水線的靜態調度思想和動態調度思想,常用的數據流調度方法是Tomasulo算法,介紹了Tomasulo 算法和記分牌方法的動態調度的基本思想,對算法進行了比較分析。
2 數據相關和控制相關
程序中的相關(Correlation)是指在相近指令之間存在有某種關系,且會影響到指令流水線的執行,分為數據相關和控制相關。數據相關指導在執行本條指令的過程中,如果用到的指令、操作數、變址偏移量等是前面指令的執行結果,則必須等待前面的指令執行完成,并把結果寫到主存或通用寄存器中之后,本條指令才能開始執行。控制相關是指由條件分支指令、轉子程序指令、中斷等引起的相關。
數據相關分為三類:RAW相關、WAR相關、WAW相關。RAW 相關(真相關)指若兩條指令之間存在真相關, 則兩條指令不能同時或完全重疊執行。WAR 相關(反相關)與WAW相關(輸出相關)兩種相關的產生都是由于指令的亂序執行所引起的。在數據相關中,真相關是在一條指令的源操作數依賴于前一條指令的結果的條件下發生的,真相關的解決必須有操作數的流動,出現相關的兩條指令不能同時或完全重疊執行。而對于反相關和輸出相關,相當于是由于資源問題所引發的相關,其實質是由于使用了共同的寄存器資源保存了不同的變量值所引發的,若采用更名的方法用兩個不同的寄存器來保存這兩個變量,則出現相關的兩條指令就可并發執行, 不會引起性能損失,因此反相關和輸出相關又稱為偽相關(false dependence),可通過更名解決。
在超標量體系結構中,數據相關的解決可通過靜態調度方法和動態調度方法。靜態調度由編譯器將相關的指令調度開來以減少相關的發生和相關所造成的性能損失,而動態調度由硬件重新安排指令的執行順序, 允許指令亂序執行, 以減少相關所引起的性能損失。常用的數據流調度方法是Tomasulo算法。
3 靜態調度和動態調度基本思想
5段流水線有一個很大的局限性是按序流出和按序執行。如果相近的指令存在相關,就很可能會導致沖突,引起停頓,后面所有的指令也都停止了前進。為解決此問題,將5段流水線的譯碼(ID)段細分為兩個段:
(1) 流出:指令譯碼并檢查是否存在結構沖突。若不存在結構沖突,就將指令流出。
(2) 讀操作數:等待數據沖突消失(若存在),然后讀操作數,并開始執行。
這樣修改后的指令流出仍然是按序流出,但在讀操作數段可能停頓或互相跨越,因而進入執行段時可能亂序執行。動態調度思想是對于一條會產生異常的指令來說,只有當處理機確切地知道該指令將被執行時,才允許它產生異常。
靜態調度可在編譯過程中減少相關的產生,而動態調度可根據處理器的動態信息發掘出更多的ILP(Instruction Level Parallel)。動態調度的優勢是能夠在數據相關時,避免暫停流水線,特點就是流水線的亂序執行,指令的發射是亂序的,指令的完成也有可能是亂序的。由于流水線允許多條指令在同一時刻執行所以流水線結構需要改變,功能單元也需要改變。
4 記分牌動態調度方法思想
記分牌算法把簡單流水線的譯碼段ID分解為:流出和讀操作數。在沒有結構沖突時,盡可能早地執行沒有數據沖突的指令,實現每個時鐘周期執行一條指令。如果某條指令被暫停,而后面的指令與流水線中正在執行或被暫停的指令都不相關,是這些指令可以跨越它,繼續流出和執行下去。
每條指令的執行過程分為4段:流出、讀操作數、執行和寫結果。
(1) 流出:如果當前流出指令所需的功能部件空閑,并且所有其它正在執行的指令的目的寄存器與該指令的不同,記分牌就向功能部件流出該指令,并修改記分牌內部的記錄表。如果存在結構相關和WAW沖突,該條指令就不流出,從而消除了WAW沖突。
(2) 讀操作數:記分牌監測操作數的可用性,一旦數據可用,就告之功能部件從寄存器中讀出源操作數并開始執行。從而消除了RAW沖突,并可能導致指令亂序執行。
(3) 執行:取到操作數后,功能部件開始執行。當結果產生后,就告之記分牌它已經完成執行,該步相當于標準流水線中的執行段(EX)。
(4) 寫結果:記分牌知道執行部件完成了執行,就檢測是否存在WAR沖突。如果不存在,或者已有的WAR沖突已消失,記分牌就告之功能部件把結果寫入目的寄存器,并釋放該指令使用的所有資源。
記分牌中記錄的信息由以下3部分構成。
(1) 指令狀態表:記錄正在執行的各條指令已經進入到了哪一段。
(2) 功能部件狀態表:記錄各個功能部件的狀態。
(3) 結果寄存器狀態表Result:每個寄存器在該表中有一項,用于指出哪個功能部件將把結果寫入該寄存器。
5 Tomasulo算法思想和算法實現
5.1 算法基本思想
寄存器換名是通過保留站和流出邏輯來共同完成,當指令流出時,如果其操作數還沒有計算出來,則該指令中相應的寄存器換名將產生這個操作數的保留站的標識。因此,指令流出到保留站后,其操作數寄存器或者換成了數據本身,或換成了保留站的標識,和寄存器無關。后面指令對該寄存器的寫入操作就不會產生WAR沖突。
指令執行步驟可分為3步:
(1) 流出。從指令隊列的頭部出一條指令。若該指令的操作所需要的保留站有空閑,則把該指令送到保留站(r)。如果其操作數在寄存器中已經就緒,將這些操作數送入保留站r,否則將產生的該操作數的保留站的標識送入保留站r。此后,若被記錄的保留站完成計算,它將直接把數據送給保留站r。此過程實際上是進行了寄存器換名和對操作數進行緩沖,從而消除WAR沖突。
(2) 執行。或某個操作數還沒有被計算出來,本保留站將監視CDB,等待所的計算結果,且被放到CDB上,本保留站將立即獲得數據。當兩個操作數就緒后,本保留站就用相應的功能部件開始執行指令規定的操作。Load和store指令的執行需要兩個步驟:計算有效地址和把有效地址放入load和store緩沖器。Load緩沖器中的load指令的執行條件是存儲器部件就緒。Store緩沖器中的store指令在執行前等到要存入存在器的數據到達。
(3) 寫結果。功能部件計算完畢后,就將計算結果放到CDB上,所有等待該計算結果的寄存器和保留站都同時從CDB上獲得所需要的數據。Store指令在這一步完成對存儲器的寫入:當寫入地址和數據備齊時,將它們送給存儲器部件,store指令完成。
5.2 算法實現
給出Tomasulo算法中指令進入各階段的條件以及在各階段進行的操作數和狀態表內容修改。各符號的意義如下:
r:分配給當前指令的保留站或者緩沖器單元。
rd:目的寄存器編號。
imm:按符號位擴展后的立即數。
Result:浮點部件或load緩沖器返回的結果。
Regs[]:寄存器組。
rs、rt:操作數寄存器編號。
RS:保留站。
Qi:寄存器狀態表。
Op:當前指令的操作碼。
對于load指令來說,rt是保存所取數據的寄存器號;對于store指令來說,rt是保存所要存儲的數據的寄存器號。與rs對應的保留站字段是Vj、Qj;與rt對應的保留站字段是Vk、Qk。
(1) 指令流出
①浮點運算指令
進入條件:有空閑保留站(r)
操作和狀態表內容修改:
if(Qi[rs]≠0){RS[r].QjQi[rs]}
Else {RS[r].VjRegs[rs];RS[r].Qj0};
if(Qi[rt]≠0){RS[r].QkQi[rt]}
else{RS[r].VkRegs[rt];RS[r].Qk0};
RS[r].Busyyes;
RS[r].OpOp;
Qi[rd] r;
②load和store指令
進入條件:緩沖器有空元單元(r)
操作和狀態表內容修改:
if(Qi[rs]≠0){RS[r].QjQi[rs]}
else{RS[r].VjRegs[rs];RS[r].Qj0};
RS[r].Busyyes;
RS[r].AImm;
對于load指令:
Qi[rt]r;
對于store指令:
If(Qi[rt]≠0){RS[r].QkRegs[rt];RS[r].Qk0};
(2) 執行:
① 浮點運算指令
進入條件:(RS[r].Qj=0)且(RS[r].Qk=0);
操作和狀態表內容修改:進入計算,產生結果。
② load和store指令
進入條件:(RS[r].Qj=0)且r成為load/store緩沖隊列的頭部。
操作和狀態表內容修改:
RS[r].ARS[r].Vj+RS[r].A;
對于load指令,在完成有效地址計算后,還要進行:
從Mem[RS[r].A]讀取數據;
(3) 寫結果:
① 浮點運算指令和load指令
進入條件:保留站r執行結束,且CDB就緒。
操作和狀態表內容修改:
② store指令。
進入條件:保留站r執行結束,且RS[r].Qk=0
操作和狀態表內容修改:
如果能夠準確地預測分支,采用Tomasulo算法將獲得很高的性能。
6 Tomasulo算法和記分牌算法的異同
(1) 相同之處:
兩個算法消除RAW競爭的思想相同,Tomasulo算法采用了記分牌方法的動態調度的基本思想,多條指令處于發射狀態,等待條件滿足,可以不按順序執行。
(2) 不同之處:
Tomasulo方法通過寄存器換名過程可消除WAR和WAW競爭。記分牌方法可檢測WAR和WAW競爭,一旦檢測到存在WAR和WAW競爭,通過插入停頓周期來解決此競爭。因此,記分牌方法不能消除WAR和WAW競爭。
7 結束語
在超標量體系結構中, 存在著數據相關和控制相關問題,數據相關的解決可通過靜態調度方法和動態調度方法。靜態調度由編譯器將相關的指令調度開來以減少相關的發生和相關所造成的性能損失,而動態調度由硬件重新安排指令的執行順序, 允許指令亂序執行, 以減少相關所引起的性能損失。常用的數據流調度方法是Tomasulo 算法。講解了Tomasulo 算法和記分牌方法的動態調度的基本思想,對算法進行了比較分析。
參考文獻:
[1] 莫壯堅,李振.超標量微處理器研究[J].海南師范學院學報(自然科學版).2004,17(4):347-351.
[2] 鄧正宏,康慕寧,羅旻.超標量微處理器研究與應用[J].微電子學與計算機.2004,21(9):59-63.
[3] 張晨曦.計算機系統結構教程[M].北京:清華大學出版社.2009.
[4] 宋輝.量子計算機體系結構及模擬技術的研究與實現[D].中國人民解放軍國防科學技術大學.2003.
[5] 沈立.動態VLIW體系結構關鍵技術研究與實現[D].國防科學技術大學.2003.
[6] 王蓉暉.指[9] 令級并行性開發關鍵技術的研究與實現[D].國防科學技術大學.2002.
[7] WilliamStallings.Computer Organization and Architecture:Design for Performance (FourthEdition).北京:清華大學出版社,2002.
[8] 周敏,付慧生,李雪峰.基于流水線的RISC微處理器設計[J].大眾科技;2006,10(5):55-57.