第2章指令級并行及其開發(fā)指令級并行概念支持指令級并行的基本編譯技術

預測技術動態(tài)調(diào)度基于硬件的推測多發(fā)射技術指令傳送和推測高級技術

浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第1頁!2.1指令級并行概念指令級并行（ILP，instruction-levelparallelism）

產(chǎn)生于80年代中期，處理器采用流水線方式使指令的執(zhí)行可以重疊進行，可以將指令間的關系看做是并行的，指令間潛在的重疊稱為~

指令級并行方法分為兩類：一種依賴于硬件，動態(tài)地發(fā)現(xiàn)和開發(fā)指令級并行；另一種依賴于軟件技術，在編譯階段靜態(tài)地發(fā)現(xiàn)并行。前一種占主導地位，后一種局限于科學或特定領域。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第2頁!2.1指令級并行概念循環(huán)級并行

為了提高指令級并行，最常用的方法是將一個循環(huán)中的各次迭代并行執(zhí)行，通常將這類并行稱為循環(huán)級并行。

在循環(huán)中，每個迭代可以與其他任何一次迭代重疊執(zhí)行，在每次迭代內(nèi)部沒有重疊。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第3頁!2.1指令級并行概念數(shù)據(jù)相關

相關有三種不同的類型：數(shù)據(jù)相關、名字相關和控制相關

數(shù)據(jù)相關，也稱為真數(shù)據(jù)相關，比如有兩條指令j和i，指令j可能會引用指令i的結(jié)果或指令j數(shù)據(jù)相關于指令K，而指令k數(shù)據(jù)相關于指令i，則稱指令j數(shù)據(jù)相關于指令i浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第4頁!2.1指令級并行概念名字相關

名字相關發(fā)生在使用相同存儲器或存儲單元（稱為名字）的兩條指令之間，但名字相關的指令間不存在數(shù)據(jù)流，名字相關有兩種類型（假設指令i位于指令j之前）：1、反相關

指令i讀一個寄存器或存儲單元，而指令j寫該寄存器或存儲單元，必須保護原始的指令執(zhí)行順序。2、輸出相關

指令i和指令j寫相同的寄存器時，為了保證該寄存器的值最后是由指令j寫入的，必須保護指令的執(zhí)行順序。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第5頁!2.1指令級并行概念控制相關

控制相關會帶來兩類限制：1、與某一轉(zhuǎn)移相關的指令不能被移動到該轉(zhuǎn)移之前，這樣的移動會使指令的執(zhí)行不再受控于該轉(zhuǎn)移，比如不能將if語句的then部分中的指令移動到if語句之前

2、與某一轉(zhuǎn)移相關的指令不能被移動到該轉(zhuǎn)移之后，這樣的移動會使指令的執(zhí)行受到該轉(zhuǎn)移的控制，不能將if語句之前的指令移動到受控于該if語句的then部分中

浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第6頁!2.1指令級并行概念數(shù)據(jù)冒險讀后寫（WAR）

J試圖在i讀一個數(shù)據(jù)之前寫該數(shù)據(jù)，這時，i將錯誤地讀出新值，這類冒險是由反相關引起的。WAR不會發(fā)生在靜態(tài)流水線中，因為在靜態(tài)流水線中，所以的讀操作發(fā)生的早，寫操作發(fā)生的晚（見附錄A）。只有在指令流水過程中一些指令的寫操作提前完成、或者其他指令的讀操作滯后完成、或者指令順序被改變的情況下，才會發(fā)生WAR冒險

讀后讀（RAR）不產(chǎn)生冒險浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第7頁!2.2支持指令級并行的基本編譯技術循環(huán)展開

循環(huán)展開可以增加有效操作對轉(zhuǎn)移和開銷指令的比重，展開可以通過多次復制循環(huán)體和調(diào)整循環(huán)中止代碼來實現(xiàn)。

循環(huán)展開也可以用來改進調(diào)度的效果，由于它消除了轉(zhuǎn)移，因此來自不同迭代的指令可以被一起調(diào)度，可以在迭代內(nèi)加入不相關的指令來消除數(shù)據(jù)相關引起的停頓。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第8頁!2.2支持指令級并行的基本編譯技術循環(huán)展開和調(diào)度小結(jié)

循環(huán)展開的效果受制于三因素：展開使額外開銷降低、代碼量的大小和編譯器的限制。

循環(huán)展開次數(shù)越多，則額外開銷的時鐘周期越小；代碼量的增長，特別是在規(guī)模較大的循環(huán)中，當代碼量的增長使指令Cache的缺失率增加時，這類問題就更加明顯；如果將展開和大規(guī)模調(diào)度相結(jié)合，寄存器不足是一個亟待解決的問題，特別是在多發(fā)射處理器中，由于要重疊執(zhí)行更多的獨立指令序列，寄存器不足帶來的挑戰(zhàn)更為嚴峻循環(huán)展開對簡單流水線、超標量多發(fā)射結(jié)構、VLIW均適用浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第9頁!2.3采用預測技術減小轉(zhuǎn)移開銷靜態(tài)轉(zhuǎn)移預測

為了重組轉(zhuǎn)移周圍的代碼以獲得更高的性能，需要在程序編譯階段靜態(tài)預測轉(zhuǎn)移行為，最簡單的方法是預測轉(zhuǎn)移總是被選中，這種方法的錯誤率等于轉(zhuǎn)移不被選中的比率；另一種技術是通過分析轉(zhuǎn)移的歷史表現(xiàn)來進行轉(zhuǎn)移預測，這種技術擁有更高的準確率，它的依據(jù)在于轉(zhuǎn)移的表現(xiàn)通常遵循雙峰分布，圖2.3表明通過這種策略進行轉(zhuǎn)移預測是成功的。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第10頁!2.3采用預測技術減小轉(zhuǎn)移開銷動態(tài)轉(zhuǎn)移預測

1bit預測在性能上有不足之處，假設一個轉(zhuǎn)移幾乎總是被選中，而當他偶爾未被選中時，錯誤預測會使預測位空翻，從而使預測錯誤兩次而不是一次。

通常使用2bit預測法來彌補這個缺陷，在這種預測法中，僅當錯誤兩次時才改變預測方向，圖2.4為2bit預測法的有限狀態(tài)機。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第11頁!2.3采用預測技術減小轉(zhuǎn)移開銷Tournament預測器又稱整體局部自適應預測器，為了解決標準2bit預測只考慮局部信息而引起的在一些重要轉(zhuǎn)移上預測失敗的問題而產(chǎn)生的，該預測器使用多個預測器，一個基于全局信息，另一個基于局部信息，通過一個選擇器將二者結(jié)合。Tournament預測器以中等大小（8K-32K）的預測位獲得更高的準確率，同時可以有效地利用大量預測位。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第12頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險動態(tài)調(diào)度

動態(tài)調(diào)度雖然不能改變數(shù)據(jù)流，但它會在相關性出現(xiàn)時盡力避免停頓，而由編譯器執(zhí)行的靜態(tài)流水線調(diào)度則是將相關指令分離，使它們不再引起冒險，從而將停頓減至最小。

簡單流水線技術的主要限制是按序發(fā)射和執(zhí)行指令，指令以程序順序發(fā)射，一旦指令在流水線中停頓，后續(xù)指令就無法再執(zhí)行，比如當指令i的執(zhí)行時間很長，則在指令i完成、指令j可以執(zhí)行之前，指令j之后的指令都必須暫停。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第13頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險動態(tài)調(diào)度不精確異常：是指當產(chǎn)生異常時，處理器的狀態(tài)與嚴格按照程序順序執(zhí)行時的處理器狀態(tài)不同，不精確異常的發(fā)生有下面兩種可能：1、異常指令執(zhí)行之前，流水線提前完成了后面的指令2、異常指令完成之前，流水線還沒有完成前面的指令浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第14頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險用Tomasulo方法進行動態(tài)調(diào)度

算法由RobertTomasulo提出，通過對操作數(shù)何時可用進行跟蹤以減少RAW冒險，通過引入寄存器重命名減少WAW和WAR冒險。該方法的改進版本的共同特點是通過跟蹤指令的相關性使指令在操作數(shù)可用時立即開始執(zhí)行，通過寄存器重命名減少數(shù)據(jù)冒險。

寄存器重命名是指通過重命名所有的目標寄存器，包括指令序列中位置靠前的指令將要讀和寫的寄存器。

浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第15頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險保留站

保留站與寄存器堆相比有兩個重要特點，首先，冒險檢測和執(zhí)行控制是分布的，一個單元中的指令何時可以開始執(zhí)行是由該單元保留站所掌握的信息決定的；其次，結(jié)果將從緩存它們的保留站中直接傳送給功能單元，而不是通過寄存器傳送，這是通過一條公共結(jié)果總線/公共數(shù)據(jù)總線實現(xiàn)的，它使得等待操作數(shù)的所有單元可以同時取到操作數(shù)。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第16頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險指令運行的三個階段

1、發(fā)射：從指令隊列中取到下一條指令，指令隊列按FIFO順序維護，以保證正確的數(shù)據(jù)流。如果有匹配的空閑保留站，并且指令的操作數(shù)的值也保存在寄存器中，則將指令和操作數(shù)的值一起發(fā)射到該保留站中。如果沒有空閑的保留站，則說明發(fā)生結(jié)構冒險，指令會被停頓，直至出現(xiàn)可用的保留站或緩存。如果操作數(shù)不在寄存器中，則需要跟蹤將要產(chǎn)生該操作數(shù)的功能單元，寄存器重命名在這一步進行。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第17頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險指令運行的三個階段

2、執(zhí)行：為了保護異常行為，在程序順序中的所有前序轉(zhuǎn)移完成之前，任何指令都不能開始執(zhí)行。這個約束可以確保在執(zhí)行過程中引起異常的指令會被執(zhí)行。3、寫結(jié)果：當結(jié)果就緒時，將其寫到公共數(shù)據(jù)總線上，并由此送往等待它的寄存器和保留站。

當指令已經(jīng)被發(fā)射且正在等待源操作數(shù)時，標簽字段將指向包含將產(chǎn)生源操作數(shù)指令的保留站號，比如0則表明操作數(shù)已經(jīng)在寄存器中就緒。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第18頁!2.6基于硬件的推測

當我們試圖進一步開發(fā)指令級并行時，維護控制相關性便成為一個嚴重的負擔。轉(zhuǎn)移預測技術減少了直接由轉(zhuǎn)移引起的停頓，但是要想使處理器在一個時鐘周期內(nèi)執(zhí)行多條指令，僅靠轉(zhuǎn)移預測恐怕無法使我們獲得期望的指令級并行度。為了保持最高性能，一個寬發(fā)射處理器可能需要每個時鐘周期都執(zhí)行一條轉(zhuǎn)移指令，因此，要想進一步開發(fā)并行度，就必須克服控制相關帶來的問題。可以通過推測轉(zhuǎn)移的結(jié)果，并按照推測正確的情況執(zhí)行指令，以達到克服控制相關的目的。

浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第19頁!2.6基于硬件的推測基于硬件的推測

為了擴展Tomasulo算法并使其支持推測技術，必須將指令結(jié)果的旁路操作（推測執(zhí)行指令需要指令結(jié)果的旁路操作）從實際的指令完成中分離出來。通過這種分離，可以允許指令將它的執(zhí)行結(jié)果旁路給其他指令，而在確定而不是推測指令的執(zhí)行之前，不允許做任何更新。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第20頁!2.6基于硬件的推測重排序緩存（ROB）

重排序緩存提供了附加的寄存器，這種方法與Tomasulo算法通過保留站擴展寄存器集類似。在指令運算完成到提交這段時間內(nèi)，重排序緩存為指令保存結(jié)果。即在這段時間內(nèi)，ROB是指令的操作數(shù)源，但ROB與保留站的重要區(qū)別是：在Tomasulo算法中，當指令完成寫結(jié)果的操作后，所有的后繼指令都將從寄存器文件中讀取結(jié)果；而在推測技術中，只有在指令提交之后寄存器文件才會被更新。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第21頁!2.6基于硬件的推測處理器硬件結(jié)構

見圖2.14。盡管ROB替代了保留站的重命名功能，但是在指令發(fā)射到指令開始執(zhí)行這段時間內(nèi)，仍然需要一個空間來緩存操作及操作數(shù)。這個功能仍然由保留站來提供。由于所有指令在提交之前都在ROB中占有一個位置，因此，用ROB入口的序號作為結(jié)果的標簽，而不是使用保留站的序號。這要求分配給指令的ROB序號必須能夠記錄在保留站中。這里實現(xiàn)時為重命名使用額外的寄存器，而ROB僅用于記錄指令提交的時間。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第22頁!2.7多發(fā)射技術

采用前面幾節(jié)中介紹的技術可以消除數(shù)據(jù)相關和控制相關引起的停頓，從而獲得理想的CPI（理想CPI為多少？）。為了進一步提高性能，需要將CPI減小到1以下，但在每個時鐘周期發(fā)射一條指令的前提下，無法實現(xiàn)這個目標。

采用多發(fā)射技術可以解決此問題，多發(fā)射處理器的目標是允許在一個時鐘周期內(nèi)發(fā)射多條指令，重點介紹VLIW方法。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第23頁!2.7多發(fā)射技術VLIW方法

對于寬發(fā)射情況，VLIW的優(yōu)勢更加明顯。為了使功能單元始終處于工作狀態(tài)，代碼序列必須含有足夠的并行度，以填滿功能單元的可用運算槽。代碼序列中的并行度可用通過將循環(huán)展開，在每個單獨的、更大的循環(huán)體中進行代碼調(diào)度而實現(xiàn)。若并行度要求跨轉(zhuǎn)移調(diào)度代碼，則需要使用更復雜的全局調(diào)度算法，附錄G中，討論了一種專門為VLIW設計的全局調(diào)度技術，我們重點討論無轉(zhuǎn)移代碼調(diào)度情況。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第24頁!2.7多發(fā)射技術VLIW方法-開發(fā)指令級并行首選方法

開發(fā)指令級并行度是所有多發(fā)射處理器所面臨的一個共同挑戰(zhàn)。某些情況下，向量處理器可以高效地執(zhí)行浮點程序中的一些簡單循環(huán)，而多發(fā)射處理器需要將循環(huán)展開才可以獲得足夠的并行度。對于這類應用，很難確定多發(fā)射處理器是否真的優(yōu)于向量處理器；當代價相同時，向量處理器可能會更快。然而多發(fā)射處理器的優(yōu)勢在于他們能夠從結(jié)構化較差的代碼中開發(fā)并行度，而且有能力緩存所有格式的數(shù)據(jù)，這些原因使得多發(fā)射處理器成為開發(fā)指令級并行度的首選方法，而向量處理器只是作為多發(fā)射處理器的擴展和補充。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第25頁!2.9指令傳送和推測的高級技術轉(zhuǎn)移目標緩存

為了減小流水線的轉(zhuǎn)移代價，必須確定當前正在譯碼的指令是否是轉(zhuǎn)移指令，如果是，那么下一條指令的地址是什么，如果是轉(zhuǎn)移指令且知道下一條指令的地址，那么就可以將轉(zhuǎn)移代價降為0。把為轉(zhuǎn)移的后繼指令保存預測地址的轉(zhuǎn)移預測Cache稱為轉(zhuǎn)移目標緩存或轉(zhuǎn)移目標Cache。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第26頁!2.9指令傳送和推測的高級技術轉(zhuǎn)移目標緩存

如果在轉(zhuǎn)移目標緩存中發(fā)現(xiàn)了一個匹配的入口，則取指令立即從預測指令地址開始。由于在確定指令是否轉(zhuǎn)移之前將預測地址發(fā)送出去，因此轉(zhuǎn)移目標緩存的預測入口必須與指令完全匹配，若處理器不對這種匹配進行核實，那么在當前指令不是轉(zhuǎn)移的情況下，發(fā)送出去的預測地址就是錯誤的，這會降低處理器的速度。在轉(zhuǎn)移目標緩存中，只保存那些預測為被選中的轉(zhuǎn)移。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第27頁!2.9指令傳送和推測的高級技術轉(zhuǎn)移目標緩存

轉(zhuǎn)移目標緩存的另外一種形式是在緩存中保存一條或多條目標指令，以此作為預測目標地址的替代或補充。這種形式有兩個潛在優(yōu)勢，首先，這種方法允許轉(zhuǎn)移目標緩存的訪問時間超過兩個相繼取指令操作的時間間隔，也可能允許更大的轉(zhuǎn)移目標緩存；其次，通過緩存實際的指令可以實現(xiàn)優(yōu)化，稱之為轉(zhuǎn)移隱含，使用轉(zhuǎn)移隱含，可以將無條件轉(zhuǎn)移代價降為0時鐘周期。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第28頁!2.9指令傳送和推測的高級技術集成的取指令單元

為了滿足多發(fā)射處理器的要求，可選擇集成取指令單元的方法，將取指令作為一個獨立自主的單元來實現(xiàn)，由該單元為流水線的其他部分提供指令，當然，這會增加多發(fā)射的復雜性，不再將取指令視為一個單獨的流水段。在最新設計中，集成取指令單元包含以下功能：集成的轉(zhuǎn)移預測、指令預取、指令存儲器訪問和緩存。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第29頁!2.9指令傳送和推測的高級技術推測的實現(xiàn)問題和擴展

探討三個問題：寄存器重命名與重排序緩存、多轉(zhuǎn)移推測和值預測。

支持推測：寄存器重命名與重排序緩存

在寄存器重命名方法中，物理寄存器的擴展集被用來保存結(jié)構可見寄存器和臨時值，擴展寄存器替代了ROB和保留站的功能。重命名方法較ROB方法的一個優(yōu)勢在于指令提交的簡化，但撤銷分配寄存器的工作會更復雜，因為在釋放物理寄存器之前，必須確定它與任何系統(tǒng)結(jié)構寄存器不再對應，且對該寄存器的使用已全部完成。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第30頁!2.9指令傳送和推測的高級技術推測的代價

為了將推測的代價降到最小，大多數(shù)推測處理器只允許低代價的異常事件發(fā)生，如果發(fā)生了代價昂貴的異常事件，處理器在處理該事件之前，必須等待引起該事件的指令推測性質(zhì)消失，盡管這會輕微影響程序的一些性能，但相對于特別是在頻繁發(fā)生此類事件且轉(zhuǎn)移預測率不夠理想的情況，這種方法能夠有效地避免性能損失。

隨著處理器的發(fā)展，推測技術所付出的代價以及寬發(fā)射和推測所受的限制都將變得越來越明顯，此問題后面章節(jié)繼續(xù)討論。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第31頁!2.9指令傳送和推測的高級技術值預測

值預測是一種提高程序中可用指令級并行度的技術。值預測嘗試對指令將要產(chǎn)生結(jié)果的值進行預測。由于大多數(shù)指令在執(zhí)行時產(chǎn)生的結(jié)果并不相同，因此值預測的成功率是有限的。但是，值預測對于某些特定類型的指令來說卻是可行的，如讀取一個常量池，或是一個相對穩(wěn)定變量的load指令。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第32頁!2.1指令級并行概念數(shù)據(jù)相關和冒險

要判斷一段程序蘊含多少并行度，判斷指令的相關性是一個關鍵問題，特別是在開發(fā)指令級并行時必須明確哪些指令是可以并行執(zhí)行的。

兩條指令是并行的是指流水線有充足資源的情況下，這兩條指令可以在任意深度的流水線上并行執(zhí)行而不會產(chǎn)生停頓。

兩條指令是相關的，是指它們只能以順序的方式執(zhí)行，盡管它們之間只存在部分重疊。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第33頁!2.1指令級并行概念數(shù)據(jù)相關

數(shù)據(jù)相關的兩條指令是不能同時執(zhí)行或完全重疊的，相關意味著在兩條指令之間可能可能存在一條由一個或多個數(shù)據(jù)冒險組成的相關鏈（見附錄A）；同時執(zhí)行數(shù)據(jù)相關的指令會使內(nèi)部互鎖流水線的處理器檢測到冒險，造成停頓，從而減小甚至消除指令間的重疊度數(shù)據(jù)相關傳遞三方面的信息：1）數(shù)據(jù)相關表明存在冒險的可能，2）數(shù)據(jù)相關決定了必須遵循的執(zhí)行順序，3）數(shù)據(jù)相關決定了可以達到并行度的上限浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第34頁!2.1指令級并行概念控制相關

控制相關決定了于轉(zhuǎn)移指令有關的指令的執(zhí)行順序，從而使與轉(zhuǎn)移有關的指令只在應當被執(zhí)行時按程序順序執(zhí)行，最簡單的控制相關例子：

ifp1{S1;}ifp2{S2;}

浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第35頁!2.1指令級并行概念數(shù)據(jù)冒險

依據(jù)指令讀寫順序，數(shù)據(jù)冒險可以分為三類，寫后讀、寫后寫、讀后寫。

寫后讀（ＲＡＷ）

J試圖在i寫一個數(shù)據(jù)之前讀取它，這時j將錯誤地讀出舊值，ＲＡＷ是最常見的冒險類型，它對應于真實的數(shù)據(jù)相關

寫后寫（WAW）

J試圖在i寫一個數(shù)據(jù)之前寫該數(shù)據(jù)，這時，如果執(zhí)行順序錯誤，那么當寫操作結(jié)束時，留下的值將是i寫的結(jié)果，而程序的本意是留下j寫的值浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第36頁!2.2支持指令級并行的基本編譯技術基本流水線調(diào)度

為了避免流水線停頓，要去發(fā)現(xiàn)可以流水重疊的不相關的指令序列，將指令代碼中相關的指令加以分離，使其相隔的時鐘周期能正好等于原來指令在流水執(zhí)行時的時延。編譯器進行這類調(diào)度的能力既依賴于程序的指令級并行度，也依賴于流水線中功能單元的時延。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第37頁!2.2支持指令級并行的基本編譯技術循環(huán)展開和調(diào)度小結(jié)

1、如果迭代之間是互不相關的，則可以判定循環(huán)展開是有意義的；2、為不同的計算使用相同的寄存器會引起額外的限制，需要使用不同的寄存器來避免這類限制；3、消除額外的測試和轉(zhuǎn)移指令，調(diào)整循環(huán)終止和迭代代碼；4、如果來自不同循環(huán)體的load和store是互不相關的，則可以在循環(huán)展開中將兩者交換5、調(diào)度代碼，保持相關性，確保與原始代碼結(jié)果相同

浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第38頁!2.3采用預測技術減小轉(zhuǎn)移開銷可以通過轉(zhuǎn)移預測技術來減小轉(zhuǎn)移引起的性能損耗，轉(zhuǎn)移預測既可以在編譯階段靜態(tài)完成，也可以由硬件在執(zhí)行階段動態(tài)完成，有些處理器，轉(zhuǎn)移行為在編譯階段是高度可預測的，靜態(tài)轉(zhuǎn)移預測既可以應用于此類處理器，也可以用來輔助動態(tài)轉(zhuǎn)移預測浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第39頁!2.3采用預測技術減小轉(zhuǎn)移開銷動態(tài)轉(zhuǎn)移預測

動態(tài)預測最簡單的方法是轉(zhuǎn)移預測緩存，它是一小塊由轉(zhuǎn)移指令低位地址索引的存儲單元，用來記錄轉(zhuǎn)移指令在最近的一次執(zhí)行中是否被選中，這種方法是緩存中最簡單的一種，沒有標志位，而且只有當轉(zhuǎn)移延遲高于計算目標所花的時間時才起作用。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第40頁!2.3采用預測技術減小轉(zhuǎn)移開銷動態(tài)轉(zhuǎn)移預測轉(zhuǎn)移預測緩存可以作為一個在IF流水階段通過指令地址訪問的專用Cache來實現(xiàn)，也可以附屬于指令Cache中的每一塊隨指令一起讀取。如果經(jīng)過譯碼后發(fā)現(xiàn)指令為轉(zhuǎn)移指令，并且預測轉(zhuǎn)移將被選中，則應立刻從預測方向上開始取指令，否則繼續(xù)按順序取指令和執(zhí)行，如圖2.4所示，預測錯誤時改變預測位。nbit計數(shù)器當計數(shù)器值大于或等于2^n-1的一半時，預測轉(zhuǎn)移被選中，反之不被選中。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第41頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險動態(tài)調(diào)度

動態(tài)調(diào)度是通過硬件對指令執(zhí)行順序進行重組，在保持數(shù)據(jù)流和異常行為的同時減少停頓。動態(tài)調(diào)度優(yōu)勢：

可以處理一些在編譯階段無法預見的相關情況，如存儲器引用等，同時它簡化了編譯器的設計。更重要的是，它可以在等待時執(zhí)行一些其他的代碼，允許在別的流水線機器上編譯的指令在不同的流水線上有效地運行，但動態(tài)調(diào)度會使硬件復雜度顯著增加。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第42頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險動態(tài)調(diào)度

亂序執(zhí)行：指令的發(fā)射仍采用按序的方式，但指令在它的操作數(shù)可用時馬上開始執(zhí)行，流水線采用亂序執(zhí)行使得指令的結(jié)束也是亂序的，亂序執(zhí)行會產(chǎn)生WAR和WAW冒險。

指令的亂序完成會使異常處理變得復雜，異常行為必須保護，以確保除嚴格按照程序順序執(zhí)行時出現(xiàn)的異常之外，不會出現(xiàn)新的異常。

即使異常行為被保護，動態(tài)調(diào)度也會產(chǎn)生一些不精確的異常。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第43頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險動態(tài)調(diào)度為了實現(xiàn)亂序執(zhí)行，需要將五級流水線的ID流水階段分割為以下兩個部分：

1、發(fā)射譯碼指令，檢測結(jié)構冒險2、讀操作數(shù)等到不存在數(shù)據(jù)冒險時讀操作數(shù)

在動態(tài)調(diào)度流水線中，所有的指令在發(fā)射階段都是按序發(fā)射，但在讀操作數(shù)階段，則可能產(chǎn)生停頓，即進入亂序執(zhí)行。

重點討論Tomasulo算法浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第44頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險保留站：

在Tomasulo算法中，寄存器重命名是通過保留站實現(xiàn)的，保留站為等待發(fā)射的指令保存操作數(shù)。基本思想是：

1、當操作數(shù)可用時，保留站馬上取操作數(shù)并將其緩存，從而避免從寄存器中讀操作數(shù)；

2、即將執(zhí)行的指令指定保留站為其提供數(shù)據(jù)輸入；3、當對寄存器的后續(xù)寫操作在執(zhí)行過程中發(fā)生重疊時，只允許最后一個實際更新寄存器。

在指令被發(fā)射后，它所需要的操作數(shù)所對應的寄存器被重命名為保留站的名字

浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第45頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險Tomasulo算法處理器結(jié)構

該處理器基本結(jié)構見圖2.9，包括浮點單元和load-store單元。每個保留站保存一條已經(jīng)被發(fā)射并等待執(zhí)行的指令，如果指令所需要的操作數(shù)已經(jīng)被計算出來，那么保留站需要保存該操作數(shù)，否則要保存將要提供該操作數(shù)的保留站的名字。

load-store緩存保存從存儲器中讀出或即將要保存到存儲器中去的數(shù)據(jù)或數(shù)據(jù)地址。

浮點寄存器通過一對總線和功能單元相連，通過一條單獨的總線和store緩存相連。從功能單元和存儲器中得到的結(jié)果被送往公共數(shù)據(jù)總線。

保留站均設置標簽域，用于流水線控制。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第46頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險指令運行的三個階段

2、執(zhí)行：如果有一個或多個操作數(shù)處于不可用狀態(tài)，則監(jiān)視公共數(shù)據(jù)總線，等待這些操作數(shù)被計算出來。當一個操作數(shù)可用時，該操作數(shù)將被放入等待它的保留站中。當指令所需的所有操作數(shù)都已就緒時，該指令將在相應的功能單元中執(zhí)行。通過在操作數(shù)可用之前延遲指令的執(zhí)行，避免了RAW冒險。如果多條指令在同一個時鐘周期內(nèi)就緒，則功能單元將被迫在就緒指令間做出選擇。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第47頁!2.4采用動態(tài)調(diào)度克服數(shù)據(jù)冒險Tomasulo算法Tomasulo方法采用總線廣播結(jié)果的方式，由保留站監(jiān)聽，這種方法實現(xiàn)了靜態(tài)流水線調(diào)度中直接通路和旁路技術的功能，而在動態(tài)調(diào)度方法中，為了達到同樣的目標，需要在源和結(jié)果之間增加一個時鐘周期的時延，與功能單元產(chǎn)生結(jié)果相比，動態(tài)調(diào)度流水線中生產(chǎn)指令和消費指令之間的有效時延至少要多花一個時鐘周期。

每個保留站有七個字段，見P66.浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第48頁!2.6基于硬件的推測基于硬件的推測綜合以下三種思想

通過動態(tài)轉(zhuǎn)移預測選擇要執(zhí)行的指令，通過推測技術允許指令在控制相關消除之前開始執(zhí)行（能夠消除錯誤推測序列的影響），通過動態(tài)調(diào)度處理幾個不同的基本塊之間的調(diào)度（作為比較，沒有推測的動態(tài)調(diào)度只能在基本塊之間實現(xiàn)部分重疊）浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第49頁!2.6基于硬件的推測基于硬件的推測

實現(xiàn)推測技術的關鍵思想是允許指令亂序執(zhí)行，但是要求指令必須按序提交，并且在指令提交之前阻止所有不可恢復的動作（比如更新狀態(tài)或產(chǎn)生異常）。當使用推測技術擴展動態(tài)調(diào)度時，必須將指令的完成與指令提交區(qū)分開來，因為指令可能在提交之前已經(jīng)完成。在指令執(zhí)行過程中需要一組硬件緩存的支持，使用這些緩存保存已經(jīng)執(zhí)行完但還沒有提交的指令執(zhí)行結(jié)果，這些硬件緩存稱為重排序緩存。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第50頁!2.6基于硬件的推測重排序緩存（ROB）

重排序緩存每一個入口都包含4個字段：指令類型、目標字段、值字段和就緒字段。

指令類型字段表明指令是轉(zhuǎn)移運算、store操作還是寄存器運算。

目標字段提供寄存器序號或存儲器地址，指令將把結(jié)果寫向目標字段指向的寄存器或存儲器

值字段用來在指令提交之前，保存指令執(zhí)行結(jié)果的值，就緒字段表明指令已經(jīng)完成它的執(zhí)行，其結(jié)果已經(jīng)可用。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第51頁!2.6基于硬件的推測指令的執(zhí)行過程

指令的執(zhí)行包括發(fā)射、執(zhí)行、寫結(jié)果和提交4個步驟，其中前3個步驟與Tomasulo算法類似，只增加了提交最后一個階段。

提交階段是完成指令的最后一個階段，這之后只有指令的結(jié)果被保留。

當指令提交后，指令在ROB中的入口將被收回，寄存器或存儲器將被更新，無須再占用ROB的入口。如果ROB已被填滿，則只需要停止指令的發(fā)射，直到有可用的入口出現(xiàn)為止。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第52頁!2.7多發(fā)射技術VLIW方法

VLIW（超長指令字）處理器每時鐘周期發(fā)射固定數(shù)目的指令，這些指令被組織成一條長指令或一個固定的指令包，指令間的并行度由指令顯式地表示出來。VLIW處理器采用編譯器靜態(tài)調(diào)度的方式。VLIW采用多個獨立的功能單元，

將多個運算打包成一條長指令，或者要求發(fā)射包中的指令滿足相同的約束，兩種方法本質(zhì)上相同。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第53頁!2.7多發(fā)射技術VLIW方法

為了克服代碼快速增長帶來的影響，可采用智能譯碼方法，比如讓所有的功能單元使用一個立即數(shù)字段；也可以在主存中壓縮指令，當指令被讀入Cache或被譯碼時再將它們解壓縮。

早期VLIW是鎖步的，并且沒有檢測冒險的硬件，由于所有的功能單元必須保持同步，因此任意一個功能單元的停頓都將引起整個處理器的停頓。盡管編譯器可以對確定的功能單元進行調(diào)度以阻止停頓，但是要預測停頓是困難的。在最近的處理器中，功能單元的操作越來越獨立，指令發(fā)射后，由硬件負責檢測指令異步執(zhí)行。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第54頁!2.9指令傳送和推測的高級技術提高取指令帶寬

在高性能流水線特別是多發(fā)射流水線中，僅靠準確地預測轉(zhuǎn)移是不夠的，還需要傳送高帶寬的指令流。比如現(xiàn)代多發(fā)射處理器每時鐘周期要傳送4-8條指令。

多發(fā)射處理器要求每時鐘周期取到的平均指令數(shù)目不低于平均吞吐量，這要求通向指令Cache的路徑足夠?qū)挘瑤ё罾щy的還是轉(zhuǎn)移的處理。浙江工商大學計算機體系結(jié)構第2章指令級并行及其開發(fā)共62頁，您現(xiàn)在瀏覽的是第55頁!2.9指令傳送和推測的高級技術轉(zhuǎn)移目標緩存

由于轉(zhuǎn)移目標緩存要預測下一條指令的地址，并且在指令譯碼結(jié)束前將預測地址發(fā)送出去，因此必須確定取到的指令是否是一條被預測為將被選中的轉(zhuǎn)移指令。如果地址匹配，則相應的預測指令地址將作為下一條指令的地址。轉(zhuǎn)移預測緩存的硬件結(jié)構本質(zhì)上與Cache