計算機系統結構的流水線動態調度研究

［摘 要］流水線只有連續流動，不出現斷流，才會獲得高效率。流水處理機在遇到轉移指令，尤其是條件轉移指令時，效率會顯著下降。為了克服由轉移指令造成的相關和其他相關對流水線吞吐率和效率的影響，就要對流水線的相關進行處理。動態調度就是對流水線進行相關處理的一種方法。它通過硬件對流水線的任務進行調度，雖然它本身沒有消除相關，并且可能引入一些其他相關，但是它使得流水線在發生相關的時候盡可能地減少損失。動態調度是以增加部件，即增加硬件成本為代價獲得高效率的。動態調度有兩種算法：記分牌算法和Tomasulo算法。

［關鍵詞］流水線 動態調度 記分牌 Tomasulo算法

［中圖分類號］TP ［文獻標識碼］A ［文章編號］1009－5489(2008)05－0159－02

一、流水線相關性處理及動態調度

流水處理機處理局部相關的方法有兩種。一種是退后后續指令對相關單元的讀，直至在先的指令寫入完成。另一種是設置相關直接通路，將運算結果經相關直接通路直接送入所需部件。不必把結果寫入相關單元，再從此相關單元取出來用，從而可省去“寫入”和“讀出”兩個訪問周期，減少流水線的停頓。

問題是流水線有多個子過程，多條指令同時處在不同子過程中解釋，如何判定流入流水線的多個子過程是否相關，如何控制退后對相關單元的讀，如何設置相關直接通路并控制相關直接通路的連通和斷開。為此，就需要安排和控制任務在流水線中的流動方式。

任務在流水線中的流動方式有兩種。一種是讓任務(指令)流出流水線的順序保持與流水線流入的順序一致，這種方式稱為順序流動方式，或稱同步流動方式。另一種是讓流出流水線的任務可以和流入流水線的順序不同，成為異步流動方式。后一種方式就是流水線的動態調度。

二、記分牌算法

在動態調度流水線中，所有的指令在IS段順序流出，但是在第二階段RO中，由于采用了相關專用通路機制，所以只要指令運行所需的資源滿足并且沒有數據相關，就應該允許亂序執行，同時記錄下這些指令的運行狀態。

記分牌技術的目標是盡可能早地執行無關指令，在沒有數據相關的情況下，達到每個時鐘周期執行一條指令。如果某條指令被暫停，而后面的指令與流水線中正在執行的后被暫停的指令不相關，那么后面的指令就可以流出，記分牌電路全盤負責指令的流出、執行以及相關檢測。每條指令均經過記分牌，并記錄下有關數據相關的信息。然后記分牌需要判斷什么時候指令可以讀操作數并開始執行，如果記分牌判斷某指令不能立即執行，就檢測硬件的變化錯而決定何時能夠執行。記分牌還控制著指令寫目標寄存器的時機，因而所有相關造成的阻塞及其解除的監測全部都集中在記分牌上。

在記分牌中，每條指令的執行可分為四步，通過這四步記分牌保存必要的信息，從而決定下一步進行的時間，這四步代替了DLX的指令譯碼、執行和寫結果。在指令流出段如果指令所需的功能部件空閑，并且其他正在執行的指令使用的目的寄存器與該指令的不同，記分牌就像相應的功能部件流出該指令，并改變記分牌內部的數據結構。這一步替代DLX流水線中指令譯碼階段的一部分，通過確保正在流水線中執行的指令中沒有與所要流出的指令有相同的目的寄存器，從而避免出現寫后寫數據相關，因為如果前一條指令要寫回結果，而要進入的這條指令也要把結果寫回到同一個寄存器或內存地址，那么這條指令不能進入流出段，因為很有可能其他的指令會用到之前的那個結果，這樣可以防止結果被覆蓋。如果存在結構相關或寫后寫相關者條指令就會被停止流出，并且后面的指令的流出也將停止，直到阻塞消失。

讀操作數階段，如果前面已流出的正在運行的指令不對本指令的源操作數其存器進行寫操作，或者一個正在工作的功能部件已經完成了對這個寄存器的寫操作，那么此操作有效這個檢測工作由記分牌完成，當操作數有效后，記分牌告訴功能部件讀操作數并開始執行。這個過程解決了寫后讀相關。指令流出與讀操作數加在一起相當于簡單的DLX流水線的指令譯碼。

執行階段緊跟在讀操作數之后，取到操作數后就開始執行，它與基本流水線的結構及工作過程相同。

在寫回階段，記分牌知道指令執行完畢后，如果目標寄存器空閑，就將結果寫入到目標寄存器中，然后釋放本指令使用的所有資源。這里還要檢查是否有先讀后寫相關，如果有的話，就停頓直到相關消失。一般遇到：前面的某條指令還沒有讀操作數或者其中末各操作數寄存器與結束的指令的目的寄存器相同的時候，不允許指令寫結果。

三、Tomasulo算法

Tomasulo算法的基本思想是只要操作數有效，就將其取到保留站，避免指令直接從寄存器中取數。即將執行的指令從相應的保留站中取得操作數，并將執行結果直接送到等待數據的其他保留站。通過寄存器重命名解決“寫——寫”相關和“先血后讀”相關。在Tomasulo算法中，寄存器重名是通過保留站來實現的，它保存等待流出和正在流出指令所需要的操作數。對于連續的寄存器寫，只有最后一個才真正更新寄存器中的內容，一條指令流出時，存放操作數的寄存器被重命名為對應與該寄存器的保留站的名稱，這就是寄存器的重命名。指令流出邏輯和保留站相結合實現寄存器重命名，從而消除數據寫后寫和先讀后寫相關。

在Tomasulo算法中除了保留站，還有存緩沖和取緩沖，他們用來保存讀寫存儲器的數據和地址。功能部件的結果和從存儲器讀取的數據都送到公共數據總線上。除了取緩沖的輸入和存緩沖的輸出，所有部分均與公共數據總線相連。因為操作數的傳輸過程與記分牌不同，使用Tomasulo算法的指令流水線分為三站：

1.流出Issue：從浮點操作隊列中取一指令。如果是浮點操作并且有空的保留站就流出。如果操作數在寄存器中就將其送入保留站。如果是訪存指令，只要有空的緩沖，指令就流出。如果沒有空的保留站或空緩沖，這就發生了結構沖突，指令就停止流出，直至需要的保留站或緩沖為空。這一步還進行寄存器重命名處理。

2.執行Execute：如果有操作數沒就緒，監視公共數據總線等待所需寄存器的計算結果。某個操作數計算完畢后就被放入等待該結果的保留站。當兩個操作數都就緒后開始執行指令。這一步檢查先寫后讀相關。

3.寫結果Write Result：結果計算完畢后，將其寫入公共數據總線，從而傳輸只等待此結果的功能部件和寄存器。

盡管這些步驟和記分牌基本上類似，但有三處顯著的不同之處：第一，沒有檢查數據寫后寫和先讀后寫相關的過程，在指令流出過程中操作數寄存器重命名已將其消除。第二，通過公共數據總線來廣播結果，將結果送到所有等待此結果的保留站，目標寄存器也相當于一個保留站。第三，存儲器存和取都作為基本的功能部件。另外，由于保留站技術有效的解決先寫后讀，而無需特殊處理，因此，記分牌中判斷先寫后讀的取操作數這一步也被消除。

用于檢測和消除阻塞的數據結構附加在保留站、寄存器文件和存/取緩沖上。不同的部件附加的信息不同。除了取緩沖之外，各部件的每一項均有一個標志域用來保存寄存器重命名所使用的虛擬寄存器的名稱。我們希望通過寄存器重命名來獲得更大的虛擬寄存器空間。標志域之處哪個保留站中指令運行的結果是本部件的操作數。一旦某條指令流出后再等待操作數，它將用產生這個操作數的保留站號來標示操作數，而不是等待寄存器中的結果。特殊編號0表示寄存器中的操作數有效。

保留站的數目多于實際的寄存器，通過使用保留站將寄存器重命名，就消除了數據的寫后寫和先讀后寫相關。在Tomasulo算法中，保留站就是擴展的虛擬寄存器。

Tomasulo算法與記分牌有兩個顯著的不同之處。第一，操作數一旦有效，它的值就被存入保留站的一個V域中，而不是從寄存器文件或計算結果的保留站中取，實際上保留站根本不保存計算結果。第二，指令ADDD在記分牌中由于存在先讀后寫數據相關，在寫結果階段阻塞，而在Tomasulo算法中由于消除了先讀后寫，它能夠在DIVD指令執行前執行完畢。

四、結論

動態調度通過硬件對流水線的任務進行調度，使得流水線在發生相關的時候盡可能地減少損失。動態調度以增加硬件成本為代價獲得高效率。

［參考文獻］

［1］鄭緯民、湯志忠：《計算機系統結構》(第2版)，清華大學出版社出版。

［2］李學干：《計算機系統結構》，電子科技大學出版社出版。

［3］Kai Hwang：《高等計算機系統結構》，清華大學出版社、廣西科學技術出版社出版。

［4］John L.Hennessy；David A.Patterson：《計算機系統結構——量化研究方法》(第4版)，電子工業出版社出版。