HNU計算機結構體系-實驗2：CPU動態指令調度Tomasulo

文章目錄

實驗2 CPU動態指令調度Tomasulo
- 一、實驗目的
- 二、實驗說明
- 三、實驗內容
- - 問題1：
  - 問題2：
  - 問題3：
  - 問題4：
  - 問題5：
- 四、思考題
- - 問題1：
  - 問題2：
- 五、實驗總結

實驗2 CPU動態指令調度Tomasulo

一、實驗目的

熟悉Tomasulo模擬器同時加深對Tomasulo算法的理解，從而理解指令級并行的一種方式-動態指令調度。

掌握Tomasulo算法在指令流出、執行、寫結果各階段對浮點操作指令以及load和store指令進行什么處理；給定被執行代碼片段，對于具體某個時鐘周期，能夠寫出保留站、指令狀態表以及浮點寄存器狀態表內容的變化情況。

二、實驗說明

學習ScoreBoard和Tomasulo算法，并且進行Tomasulo算法的模擬實驗，同時熟悉動態指令調度相關知識

三、實驗內容

Tomasulo算法模擬器

使用模擬器進行以下指令流的執行并對模擬器截圖、回答問題

L.D   F6, 21（R2）
L.D   F2, 0 （R3）
MUL.D  F0, F2, F4
SUB.D  F8, F6, F2
DIV.D  F10,F0, F6
ADD.D  F6, F8, F2

假設浮點功能部件的延遲時間：加減法2個周期，乘法10個周期，load/store2個周期，除法40個周期

問題1：

分別截圖（當前周期2和當前周期3），請簡要說明load部件做了什么改動

答：

周期2：占用Load2部件，Busy置位；R2就緒，將地址 R[R2]+21 保存在Load1部件的地址寄存器

周期3：第一條LD指令執行完畢，地址 M[R[R2]+21] 計算完成，Load1部件將從存儲器讀到的值保存在Load1部件寄存器；R3就緒，將地址 R[R3]+0 保存在Load2部件地址寄存器

寄存器重命名：一個新的指令流出，進入保留站之后，它首先就要檢查操作數，在寄存器中查看對應的操作數有沒有，如果有的話自然萬事大吉直接讀取就可以，如果是基于其他運算指令得到的，并且還沒有完成，寄存器中此時就沒有數值，此時對這個操作數進行標記，標記這個計算指令對應的保留站編號，對于源操作數，也需要改寫成這個指令的保留站編號，這時就完成了寄存器的重命名。

寄存器重命名的好處在于它允許多個指令并行地使用同一個物理寄存器的多個重命名副本，避免了數據相關性的延遲和資源競爭。這可以提高指令級并行性，并允許更多的指令同時執行，從而提高整體性能。

問題2：

請截圖（MUL.D剛開始執行時系統狀態），并說明該周期相比上一周期整個系統發生了哪些改動（指令狀態、保留站、寄存器和Load部件）

答：

MUL.D剛開始執行時是第六個周期：

其上一個周期為第五個周期：

主要變化如下：

指令狀態：發射第六條ADD指令，同時第三條、第四條指令進入執行狀態
保留站：新發射的ADD.D指令占用Add2保留站，進入執行的指令MUL.D和SUB.D開始執行，時間開始倒計時
寄存器：新發射的指令ADD.D指令等待F8寄存器，F6的狀態變成Busy, 原因是新發射的ADD.D指令寫入F6
Load部件：無變化

Tomasulo算法采用了保守的策略，確保結果先寫入寄存器文件或數據存儲器，然后在下一個周期才允許其他指令讀取這個結果。這樣可以確保后續指令讀取到的是正確的、已經更新的值，保持數據的一致性。

問題3：

簡要說明是什么相關導致MUL.D流出后沒有立即執行

答：

因為其所需要的一個操作數F2還沒有寫回，即與L.D F2 0(R3)之間的RAW相關

Tomasulo算法通過動態調度的方式，將指令按照其操作數的可用性進行調度。當一個指令需要等待一個操作數時，它會被放置在調度隊列中，直到所有操作數都可用。這種方式可以有效地隱藏RAW依賴的延遲，因為指令可以在操作數就緒后立即被調度執行。

問題4：

請分別截圖（15周期和16周期的系統狀態），并分析系統發生了哪些變化

答：

第十五周期：

第十六周期：

主要變化如下：

指令狀態：
- 第十五個周期時MULT指令剛執行完畢
- 第十六個周期時將MULT指令的執行結果寫回到F0寄存器中
保留站：
- 第十五個周期時仍在執行MULT指令
- 第十六個周期時釋放保留站，CBD將結果廣播到指令DIV.D對應的保留站
寄存器：
- 第十五個周期時F0結果還未寫回
- 第十六個周期時釋放保留站，CBD將結果廣播到寄存器
Load部件：無變化

問題5：

回答所有指令剛剛執行完畢時是第多少周期，同時請截圖（最后一條指令寫CBD時認為指令流執行結束）

答：

所有指令執行完畢是第57個周期，DIV.D是執行的最后一條指令, 在第56個周期執行完畢，在第57個周期開始寫結果

四、思考題

問題1：

Tomasulo算法相比Score Board算法有什么異同？（簡要回答兩點：1.分別解決了什么相關問題，2.兩者分別是分布式還是集中式）

答：

Tomasulo

特點：分布式；指令狀態、相關控制和操作數緩存分布在各個部件中(保留站)
WAR相關：使用RS的寄存器或指向RS的指針代替指令中的寄存器-寄存器重命名
WAW相關：使用RS中的寄存器值或指向RS的指針代替指令中的寄存器
RAW相關：檢測到寄存器就緒即沒有沖突再讀取操作數，進入執行階段
結構相關：有結構沖突不發射
結果Forward：從FU廣播結果到RS和寄存器

Score Board

特點：集中式；指令狀態和相關控制都在記分牌處理
WAR相關：對操作排隊，僅在讀操作數階段讀寄存器
WAW相關：檢測到相關后，停止發射前一條指令，直到前一條指令完成
RAW相關：檢測到沒有沖突(寄存器就緒)再讀取操作數，進入執行階段
結構相關：有結構相關不發射
結果Forward：寫回寄存器接觸等待

問題2：

Tomasulo算法是如何解決結構冒險、RAW、WAR和WAW相關的數據冒險？

答：

結構相關: 所有功能部件都完全流水化, 功能部件有序訪問存儲器，有結構沖突不發射
RAW相關：Tomasulo通過監測Common Data Bus跟蹤每個源操作數當前是否可用，僅當所有源操作數可用時才允許指令進入執行階段
WAR，WAW相關：Tomasulo使用硬件寄存器重命名技術, 以及在發射階段時, RS空閑才發射指令和操作數

WAW相關：

Tomasulo算法可以避免WAW相關，原理是前一個指令先進功能單元，緊接著對應的目標寄存器的標識就修改為了這個保留站的編號，接下來，第二個指令進入功能單元，目的寄存器的標識再次修改成第二個，這時即便是第二個指令先完成并寫回，前一個指令再算好了也不會改變寄存器了，因為在CDB通知各個功能單元的時候，對應的寄存器只會響應第二個指令完成時傳遞發出的CDB信號。
舉例說明：修改模擬器中的默認指令，將最后的加法指令的目的寄存器調整為F12，此時最后兩條指令之間就產生了WAW相關，因為除法指令的執行時間會更長，如果不進行處理的話，就會出現除法指令執行——加法指令執行——加法指令完成寫回——除法指令完成寫回的情況，那么最后F12的結果就會是除法指令的結果，但是這顯然和程序想表達的意思不一致。

而通過使用tomasulo算法，我們可以看到在第五個周期的時候，除法指令流出，進入保留站，F12寄存器保留了除法指令的保留站編號：

在第六個周期的時候，加法指令流出，此時F12的寄存器更改標識為加法指令對應的保留站編號：

那么此時第一條指令什么時候完成就已經不重要了，F12對應的寄存器只會在加法指令完成之后，響應CDB信號讀取數據，可以看到在加法指令完成的第十一個周期，寄存器F12中就獲取了數據：

而繼續執行程序到最后除法指令完成，可以看到最后的除法運算完成之后，F12的寄存器數據也沒有改變，說明Tomasulo算法可以處理WAW相關。

WAR相關：

前一個讀指令先進保留站，有數據的話是直接從寄存器取，沒有的話就是標記上對應的指令的保留站編號，這樣一來，后續的寫操作的目的寄存器和前一個讀的已經不同名了，自然沒有影響。

舉例說明：添加了兩個加法指令，其中第一個指令要讀F12寄存器，第二個指令要寫F12寄存器，如果沒有處理WAR相關，指令亂序執行，就可能會出現因為加法指令完成更快，寫回到F12的位置，第一個加法指令讀到的是第二個指令的結果，但是實際指令的目的是讓它讀除法指令的結果，導致WAR相關。

而在Tomasulo算法中，我們可以看到在第五個周期的時候，除法指令流出，目的寄存器F12此時標記的就是這個除法指令的保留站編號，在這里實現了寄存器的重命名：

接下來第七個周期的時候，添加的第一個加法指令流出，此時檢查操作數，F4在寄存器中已經有了，所以可以直接讀取，F12此時還沒有，所以讀取的是對應指令的保留站編號并存在保留站中：

在之后是第八個周期，添加的第二個寫F12的指令流出，此時因為剛好第四個指令sub指令完成，所以不會存在結構相關的問題，指令直接存放在保留站的第一個位置，并且此時，F12的對應的保留站指令修改為添加的第二個指令：

此時，繼續執行到添加的F12寫回指令完成：

此時F12也已經有了自己的數據了：

如果沒有使用Tomasulo算法，那么可能這個時候添加的第一條指令就會讀取走這個F12的數據并且開始執行，但是因為Tomasulo算法的寄存器重命名規則，他的保留站里存的用的操作數是保留站編號為Mult2的指令的結果數據，所以此時不執行，繼續等待。

繼續執行到除法指令完成：

此時查看保留站，可以看到對應的保留站編號域變更為具體數值域：

接下來開始執行：

這里后面的寫指令沒有對前面的讀指令造成影響，說明Tomasulo算法可以處理WAR相關。

五、實驗總結

在進行這個實驗的過程中，我深入學習和研究了Tomasulo算法和指令級并行的動態指令調度方法，并通過Tomasulo模擬器進行了實際操作和觀察。以下是我在這個實驗中的心得體會和收獲：

對Tomasulo算法的理解加深：通過實驗，我對Tomasulo算法的原理和實現方式有了更深入的理解。我了解了如何使用寄存器重命名、亂序執行和指令調度等技術來實現指令級并行，提高處理器的性能。這個算法的核心思想和設計對于理解現代處理器的工作原理非常重要。
實踐操作的重要性：通過使用Tomasulo模擬器，我能夠親身操作和觀察指令級并行的過程，這對于加深理論知識的理解非常有幫助。通過在模擬器上進行實驗，我能夠看到指令之間的依賴關系、執行時間和調度策略對性能的影響，從而更好地理解并行執行的原理。
學以致用：這個實驗不僅僅是理論學習，更是將理論知識應用于實際情境的實踐。通過實驗，我能夠更好地將Tomasulo算法應用于指令級并行的場景，并理解其在提高處理器性能方面的作用。這種將理論知識轉化為實際應用的能力對于我今后在計算機體系結構和并行計算領域的學習和研究都具有重要意義。

綜上所述，通過這個實驗，我不僅熟悉了Tomasulo模擬器和動態指令調度的實踐操作，還加深了對Tomasulo算法和指令級并行的理解。這個實驗為我今后在計算機體系結構和并行計算領域的學習和研究打下了堅實的基礎，并培養了我動手實踐和團隊合作的能力。