浙江工商大學(xué)計(jì)算機(jī)體系結(jié)構(gòu)第2章指令級(jí)并行及其開(kāi)發(fā)ppt課件

1、第2章 指令級(jí)并行及其開(kāi)發(fā)o 指令級(jí)并行概念o 支持指令級(jí)并行的根本編譯技術(shù) o 預(yù)測(cè)技術(shù)o 動(dòng)態(tài)調(diào)度o 基于硬件的推測(cè)o 多發(fā)射技術(shù)o 指令傳送和推測(cè)高級(jí)技術(shù)o 2.1 指令級(jí)并行概念o 指令級(jí)并行ILP，instruction-level parallelismo 產(chǎn)生于80年代中期，處置器采用流水線方式使指令的執(zhí)行可以重疊進(jìn)展，可以將指令間的關(guān)系看做是并行的，指令間潛在的重疊稱為o 指令級(jí)并行方法分為兩類：一種依賴于硬件，動(dòng)態(tài)地發(fā)現(xiàn)和開(kāi)發(fā)指令級(jí)并行；另一種依賴于軟件技術(shù)，在編譯階段靜態(tài)地發(fā)現(xiàn)并行。前一種占主導(dǎo)位置，后一種局限于科學(xué)或特定領(lǐng)域。2.1 指令級(jí)并行概念o 循環(huán)級(jí)并行o 為了提

2、高指令級(jí)并行，最常用的方法是將一個(gè)循環(huán)中的各次迭代并行執(zhí)行，通常將這類并行稱為循環(huán)級(jí)并行。o o 在循環(huán)中，每個(gè)迭代可以與其他任何一次迭代重疊執(zhí)行，在每次迭代內(nèi)部沒(méi)有重疊。2.1 指令級(jí)并行概念o 數(shù)據(jù)相關(guān)和冒險(xiǎn)o 要判別一段程序蘊(yùn)含多少并行度，判別指令的相關(guān)性是一個(gè)關(guān)鍵問(wèn)題，特別是在開(kāi)發(fā)指令級(jí)并行時(shí)必需明確哪些指令是可以并行執(zhí)行的。o 兩條指令是并行的是指流水線有充足資源的情況下，這兩條指令可以在恣意深度的流水線上并行執(zhí)行而不會(huì)產(chǎn)生停頓。o 兩條指令是相關(guān)的，是指它們只能以順序的方式執(zhí)行，雖然它們之間只存在部分重疊。2.1 指令級(jí)并行概念o 數(shù)據(jù)相關(guān)o 相關(guān)有三種不同的類型：數(shù)據(jù)相關(guān)、名字相

3、關(guān)和控制相關(guān)o o 數(shù)據(jù)相關(guān)，也稱為真數(shù)據(jù)相關(guān)，比如有兩條指令j和i，指令j能夠會(huì)援用指令i的結(jié)果或指令j數(shù)據(jù)相關(guān)于指令K，而指令k數(shù)據(jù)相關(guān)于指令i，那么稱指令j數(shù)據(jù)相關(guān)于指令i2.1 指令級(jí)并行概念o 數(shù)據(jù)相關(guān)o 數(shù)據(jù)相關(guān)的兩條指令是不能同時(shí)執(zhí)行或完全重疊的，相關(guān)意味著在兩條指令之間能夠能夠存在一條由一個(gè)或多個(gè)數(shù)據(jù)冒險(xiǎn)組成的相關(guān)鏈見(jiàn)附錄A；同時(shí)執(zhí)行數(shù)據(jù)相關(guān)的指令會(huì)使內(nèi)部互鎖流水線的處置器檢測(cè)到冒險(xiǎn)，呵斥停頓，從而減小甚至消除指令間的重疊度o 數(shù)據(jù)相關(guān)傳送三方面的信息：1數(shù)據(jù)相關(guān)闡明存在冒險(xiǎn)的能夠，2數(shù)據(jù)相關(guān)決議了必需遵照的執(zhí)行順序，3數(shù)據(jù)相關(guān)決議了可以到達(dá)并行度的上限2.1 指令級(jí)并行概念o

4、 名字相關(guān)o 名字相關(guān)發(fā)生在運(yùn)用一樣存儲(chǔ)器或存儲(chǔ)單元稱為名字的兩條指令之間，但名字相關(guān)的指令間不存在數(shù)據(jù)流，名字相關(guān)有兩種類型假設(shè)指令i位于指令j之前：o 1、反相關(guān)o 指令 i 讀一個(gè)存放器或存儲(chǔ)單元，而指令j寫(xiě)該存放器或存儲(chǔ)單元，必需維護(hù)原始的指令執(zhí)行順序。o 2、輸出相關(guān)o 指令i和指令j寫(xiě)一樣的存放器時(shí)，為了保證該存放器的值最后是由指令j寫(xiě)入的，必需維護(hù)指令的執(zhí)行順序。2.1 指令級(jí)并行概念o 控制相關(guān)o 控制相關(guān)決議了于轉(zhuǎn)移指令有關(guān)的指令的執(zhí)行順序，從而使與轉(zhuǎn)移有關(guān)的指令只在該當(dāng)被執(zhí)行時(shí)按程序順序執(zhí)行，最簡(jiǎn)單的控制相關(guān)例子：o if p1 o S1;o o if p2 o S2;o

5、o 2.1 指令級(jí)并行概念o 控制相關(guān)o 控制相關(guān)會(huì)帶來(lái)兩類限制：o 1、與某一轉(zhuǎn)移相關(guān)的指令不能被挪動(dòng)到該轉(zhuǎn)移之前，這樣的挪動(dòng)會(huì)使指令的執(zhí)行不再受控于該轉(zhuǎn)移，比如不能將if語(yǔ)句的then 部分中的指令挪動(dòng)到if語(yǔ)句之前o o 2、與某一轉(zhuǎn)移相關(guān)的指令不能被挪動(dòng)到該轉(zhuǎn)移之后，這樣的挪動(dòng)會(huì)使指令的執(zhí)行遭到該轉(zhuǎn)移的控制，不能將if語(yǔ)句之前的指令挪動(dòng)到受控于該if語(yǔ)句的then 部分中o 2.1 指令級(jí)并行概念o 數(shù)據(jù)冒險(xiǎn)o 根據(jù)指令讀寫(xiě)順序，數(shù)據(jù)冒險(xiǎn)可以分為三類，寫(xiě)后讀、寫(xiě)后寫(xiě)、讀后寫(xiě)。o 寫(xiě)后讀o J試圖在i寫(xiě)一個(gè)數(shù)據(jù)之前讀取它，這時(shí)j將錯(cuò)誤地讀出舊值，是最常見(jiàn)的冒險(xiǎn)類型，它對(duì)應(yīng)于真實(shí)的數(shù)據(jù)相關(guān)

6、o 寫(xiě)后寫(xiě)WAWo J試圖在i寫(xiě)一個(gè)數(shù)據(jù)之前寫(xiě)該數(shù)據(jù)，這時(shí)，假設(shè)執(zhí)行順序錯(cuò)誤，那么當(dāng)寫(xiě)操作終了時(shí)，留下的值將是i寫(xiě)的結(jié)果，而程序的本意是留下j寫(xiě)的值2.1 指令級(jí)并行概念o 數(shù)據(jù)冒險(xiǎn)o 讀后寫(xiě)WA Ro J試圖在i讀一個(gè)數(shù)據(jù)之前寫(xiě)該數(shù)據(jù)，這時(shí)，i將錯(cuò)誤地讀出新值，這類冒險(xiǎn)是由反相關(guān)引起的。 WA R不會(huì)發(fā)生在靜態(tài)流水線中，由于在靜態(tài)流水線中，所以的讀操作發(fā)生的早，寫(xiě)操作發(fā)生的晚見(jiàn)附錄A。只需在指令流水過(guò)程中一些指令的寫(xiě)操作提早完成、或者其他指令的讀操作滯后完成、或者指令順序被改動(dòng)的情況下，才會(huì)發(fā)生WA R冒險(xiǎn)o 讀后讀RAR不產(chǎn)生冒險(xiǎn)2.2 支持指令級(jí)并行的根本編譯技術(shù)o 根本流水線調(diào)度o 為

7、了防止流水線停頓，要去發(fā)現(xiàn)可以流水重疊的不相關(guān)的指令序列，將指令代碼中相關(guān)的指令加以分別，使其相隔的時(shí)鐘周期能正好等于原來(lái)指令在流水執(zhí)行時(shí)的時(shí)延。編譯器進(jìn)展這類調(diào)度的才干既依賴于程序的指令級(jí)并行度，也依賴于流水線中功能單元的時(shí)延。2.2 支持指令級(jí)并行的根本編譯技術(shù)o 循環(huán)展開(kāi)o 循環(huán)展開(kāi)可以添加有效操作對(duì)轉(zhuǎn)移和開(kāi)銷指令的比重，展開(kāi)可以經(jīng)過(guò)多次復(fù)制循環(huán)體和調(diào)整循環(huán)中止代碼來(lái)實(shí)現(xiàn)。o 循環(huán)展開(kāi)也可以用來(lái)改良調(diào)度的效果，由于它消除了轉(zhuǎn)移，因此來(lái)自不同迭代的指令可以被一同調(diào)度，可以在迭代內(nèi)參與不相關(guān)的指令來(lái)消除數(shù)據(jù)相關(guān)引起的停頓。2.2 支持指令級(jí)并行的根本編譯技術(shù)o 循環(huán)展開(kāi)和調(diào)度小結(jié)o 1、假設(shè)

8、迭代之間是互不相關(guān)的，那么可以斷定循環(huán)展開(kāi)是有意義的；o 2、為不同的計(jì)算運(yùn)用一樣的存放器會(huì)引起額外的限制，需求運(yùn)用不同的存放器來(lái)防止這類限制；o 3、消除額外的測(cè)試和轉(zhuǎn)移指令，調(diào)整循環(huán)終止和迭代代碼；o 4、假設(shè)來(lái)自不同循環(huán)體的load和store是互不相關(guān)的，那么可以在循環(huán)展開(kāi)中將兩者交換o 5、調(diào)度代碼，堅(jiān)持相關(guān)性，確保與原始代碼結(jié)果一樣o 2.2 支持指令級(jí)并行的根本編譯技術(shù)o 循環(huán)展開(kāi)和調(diào)度小結(jié)o 循環(huán)展開(kāi)的效果受制于三要素：展開(kāi)使額外開(kāi)銷降低、代碼量的大小和編譯器的限制。o 循環(huán)展開(kāi)次數(shù)越多，那么額外開(kāi)銷的時(shí)鐘周期越小；代碼量的增長(zhǎng)，特別是在規(guī)模較大的循環(huán)中，當(dāng)代碼量的增長(zhǎng)使指令C

9、ache的缺失率添加時(shí)，這類問(wèn)題就更加明顯；假設(shè)將展開(kāi)和大規(guī)模調(diào)度相結(jié)合，存放器缺乏是一個(gè)亟待處理的問(wèn)題，特別是在多發(fā)射處置器中，由于要重疊執(zhí)行更多的獨(dú)立指令序列，存放器缺乏帶來(lái)的挑戰(zhàn)更為嚴(yán)峻o 循環(huán)展開(kāi)對(duì)簡(jiǎn)單流水線、超標(biāo)量多發(fā)射構(gòu)造、VLIW均適用2.3 采用預(yù)測(cè)技術(shù)減小轉(zhuǎn)移開(kāi)銷o 可以經(jīng)過(guò)轉(zhuǎn)移預(yù)測(cè)技術(shù)來(lái)減小轉(zhuǎn)移引起的性能損耗，轉(zhuǎn)移預(yù)測(cè)既可以在編譯階段靜態(tài)完成，也可以由硬件在執(zhí)行階段動(dòng)態(tài)完成，有些處置器，轉(zhuǎn)移行為在編譯階段是高度可預(yù)測(cè)的，靜態(tài)轉(zhuǎn)移預(yù)測(cè)既可以運(yùn)用于此類處置器，也可以用來(lái)輔助動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)2.3 采用預(yù)測(cè)技術(shù)減小轉(zhuǎn)移開(kāi)銷o 靜態(tài)轉(zhuǎn)移預(yù)測(cè)o 為了重組轉(zhuǎn)移周?chē)拇a以獲得更高的性能，需

10、求在程序編譯階段靜態(tài)預(yù)測(cè)轉(zhuǎn)移行為，最簡(jiǎn)單的方法是預(yù)測(cè)轉(zhuǎn)移總是被選中，這種方法的錯(cuò)誤率等于轉(zhuǎn)移不被選中的比率；另一種技術(shù)是經(jīng)過(guò)分析轉(zhuǎn)移的歷史表現(xiàn)來(lái)進(jìn)展轉(zhuǎn)移預(yù)測(cè)，這種技術(shù)擁有更高的準(zhǔn)確率，它的根據(jù)在于轉(zhuǎn)移的表現(xiàn)通常遵照雙峰分布，圖2.3闡明經(jīng)過(guò)這種戰(zhàn)略進(jìn)展轉(zhuǎn)移預(yù)測(cè)是勝利的。2.3 采用預(yù)測(cè)技術(shù)減小轉(zhuǎn)移開(kāi)銷o 動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)o 動(dòng)態(tài)預(yù)測(cè)最簡(jiǎn)單的方法是轉(zhuǎn)移預(yù)測(cè)緩存，它是一小塊由轉(zhuǎn)移指令低位地址索引的存儲(chǔ)單元，用來(lái)記錄轉(zhuǎn)移指令在最近的一次執(zhí)行中能否被選中，這種方法是緩存中最簡(jiǎn)單的一種，沒(méi)有標(biāo)志位，而且只需當(dāng)轉(zhuǎn)移延遲高于計(jì)算目的所花的時(shí)間時(shí)才起作用。2.3 采用預(yù)測(cè)技術(shù)減小轉(zhuǎn)移開(kāi)銷o 動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)o 1bi

11、t預(yù)測(cè)在性能上有缺乏之處，假設(shè)一個(gè)轉(zhuǎn)移幾乎總是被選中，而當(dāng)他偶爾未被選中時(shí)，錯(cuò)誤預(yù)測(cè)會(huì)使預(yù)測(cè)位空翻，從而使預(yù)測(cè)錯(cuò)誤兩次而不是一次。o 通常運(yùn)用2bit預(yù)測(cè)法來(lái)彌補(bǔ)這個(gè)缺陷，在這種預(yù)測(cè)法中，僅當(dāng)錯(cuò)誤兩次時(shí)才改動(dòng)預(yù)測(cè)方向，圖2.4為2bit預(yù)測(cè)法的有限形狀機(jī)。2.3 采用預(yù)測(cè)技術(shù)減小轉(zhuǎn)移開(kāi)銷o 動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)o 轉(zhuǎn)移預(yù)測(cè)緩存可以作為一個(gè)在IF流水階段經(jīng)過(guò)指令地址訪問(wèn)的公用Cache來(lái)實(shí)現(xiàn)，也可以附屬于指令Cache中的每一塊隨指令一同讀取。假設(shè)經(jīng)過(guò)譯碼后發(fā)現(xiàn)指令為轉(zhuǎn)移指令，并且預(yù)測(cè)轉(zhuǎn)移將被選中，那么應(yīng)立刻從預(yù)測(cè)方向上開(kāi)場(chǎng)取指令，否那么繼續(xù)按順序取指令和執(zhí)行，如圖2.4所示，預(yù)測(cè)錯(cuò)誤時(shí)改動(dòng)預(yù)測(cè)位。n

12、bit 計(jì)數(shù)器當(dāng)計(jì)數(shù)器值大于或等于2n-1的一半時(shí)，預(yù)測(cè)轉(zhuǎn)移被選中，反之不被選中。2.3 采用預(yù)測(cè)技術(shù)減小轉(zhuǎn)移開(kāi)銷o Tournament預(yù)測(cè)器o 又稱整體部分自順應(yīng)預(yù)測(cè)器，為理處理規(guī)范2bit預(yù)測(cè)只思索部分信息而引起的在一些重要轉(zhuǎn)移上預(yù)測(cè)失敗的問(wèn)題而產(chǎn)生的，該預(yù)測(cè)器運(yùn)用多個(gè)預(yù)測(cè)器，一個(gè)基于全局信息，另一個(gè)基于部分信息，經(jīng)過(guò)一個(gè)選擇器將二者結(jié)合。o Tournament預(yù)測(cè)器以中等大小8K-32K的預(yù)測(cè)位獲得更高的準(zhǔn)確率，同時(shí)可以有效地利用大量預(yù)測(cè)位。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 動(dòng)態(tài)調(diào)度o 動(dòng)態(tài)調(diào)度是經(jīng)過(guò)硬件對(duì)指令執(zhí)行順序進(jìn)展重組，在堅(jiān)持?jǐn)?shù)據(jù)流和異常行為的同時(shí)減少停頓。o 動(dòng)態(tài)調(diào)度優(yōu)勢(shì)

13、：o 可以處置一些在編譯階段無(wú)法預(yù)見(jiàn)的相關(guān)情況，如存儲(chǔ)器援用等，同時(shí)它簡(jiǎn)化了編譯器的設(shè)計(jì)。更重要的是，它可以在等待時(shí)執(zhí)行一些其他的代碼，允許在別的流水線機(jī)器上編譯的指令在不同的流水線上有效地運(yùn)轉(zhuǎn)，但動(dòng)態(tài)調(diào)度會(huì)使硬件復(fù)雜度顯著添加。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 動(dòng)態(tài)調(diào)度o 動(dòng)態(tài)調(diào)度雖然不能改動(dòng)數(shù)據(jù)流，但它會(huì)在相關(guān)性出現(xiàn)時(shí)盡力防止停頓，而由編譯器執(zhí)行的靜態(tài)流水線調(diào)度那么是將相關(guān)指令分別，使它們不再引起冒險(xiǎn)，從而將停頓減至最小。o 簡(jiǎn)單流水線技術(shù)的主要限制是按序發(fā)射和執(zhí)行指令，指令以程序順序發(fā)射，一旦指令在流水線中停頓，后續(xù)指令就無(wú)法再執(zhí)行，比如當(dāng)指令i的執(zhí)行時(shí)間很長(zhǎng)，那么在指令i完成、指令j

14、可以執(zhí)行之前，指令j之后的指令都必需暫停。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 動(dòng)態(tài)調(diào)度o 亂序執(zhí)行：指令的發(fā)射仍采用按序的方式，但指令在它的操作數(shù)可用時(shí)馬上開(kāi)場(chǎng)執(zhí)行，流水線采用亂序執(zhí)行使得指令的終了也是亂序的，亂序執(zhí)行會(huì)產(chǎn)生WAR和WAW冒險(xiǎn)。o 指令的亂序完成會(huì)使異常處置變得復(fù)雜，異常行為必需維護(hù)，以確保除嚴(yán)厲按照程序順序執(zhí)行時(shí)出現(xiàn)的異常之外，不會(huì)出現(xiàn)新的異常。o 即使異常行為被維護(hù)，動(dòng)態(tài)調(diào)度也會(huì)產(chǎn)生一些不準(zhǔn)確的異常。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 動(dòng)態(tài)調(diào)度o 不準(zhǔn)確異常：是指當(dāng)產(chǎn)生異常時(shí)，處置器的形狀與嚴(yán)厲按照程序順序執(zhí)行時(shí)的處置器形狀不同，不準(zhǔn)確異常的發(fā)生有下面兩種能夠：o 1、異常

15、指令執(zhí)行之前，流水線提早完成了后面的指令o 2、異常指令完成之前，流水線還沒(méi)有完成前面的指令2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 動(dòng)態(tài)調(diào)度o 為了實(shí)現(xiàn)亂序執(zhí)行，需求將五級(jí)流水線的ID流水階段分割為以下兩個(gè)部分：o 1、發(fā)射 譯碼指令，檢測(cè)構(gòu)造冒險(xiǎn)o 2、讀操作數(shù) 等到不存在數(shù)據(jù)冒險(xiǎn)時(shí)讀操作數(shù)o 在動(dòng)態(tài)調(diào)度流水線中，一切的指令在發(fā)射階段都是按序發(fā)射，但在讀操作數(shù)階段，那么能夠產(chǎn)生停頓，即進(jìn)入亂序執(zhí)行。o 重點(diǎn)討論Tomasulo算法2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 用Tomasulo方法進(jìn)展動(dòng)態(tài)調(diào)度o 算法由Robert Tomasulo 提出，經(jīng)過(guò)對(duì)操作數(shù)何時(shí)可用進(jìn)展跟蹤以減少RAW冒險(xiǎn)，經(jīng)過(guò)

16、引入存放器重命名減少WAW和WAR冒險(xiǎn)。該方法的改良版本的共同特點(diǎn)是經(jīng)過(guò)跟蹤指令的相關(guān)性使指令在操作數(shù)可用時(shí)立刻開(kāi)場(chǎng)執(zhí)行，經(jīng)過(guò)存放器重命名減少數(shù)據(jù)冒險(xiǎn)。o 存放器重命名是指經(jīng)過(guò)重命名一切的目的存放器，包括指令序列中位置靠前的指令將要讀和寫(xiě)的存放器。o 2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 保管站：保管站： 在在Tomasulo算法中，存放器重命算法中，存放器重命名是經(jīng)過(guò)保管站實(shí)現(xiàn)的，保管站為等待發(fā)射的名是經(jīng)過(guò)保管站實(shí)現(xiàn)的，保管站為等待發(fā)射的指令保管操作數(shù)。根本思想是：指令保管操作數(shù)。根本思想是：o 1、當(dāng)操作數(shù)可用時(shí)，保管站馬上取操作數(shù)、當(dāng)操作數(shù)可用時(shí)，保管站馬上取操作數(shù)并將其緩存，從而防止從存

17、放器中讀操作數(shù)；并將其緩存，從而防止從存放器中讀操作數(shù)；o 2、即將執(zhí)行的指令指定保管站為其提供數(shù)、即將執(zhí)行的指令指定保管站為其提供數(shù)據(jù)輸入；據(jù)輸入；o 3、當(dāng)對(duì)存放器的后續(xù)寫(xiě)操作在執(zhí)行過(guò)程中、當(dāng)對(duì)存放器的后續(xù)寫(xiě)操作在執(zhí)行過(guò)程中發(fā)生重疊時(shí)，只允許最后一個(gè)實(shí)踐更新存放器發(fā)生重疊時(shí)，只允許最后一個(gè)實(shí)踐更新存放器。o 在指令被發(fā)射后，它所需求的操作數(shù)所對(duì)應(yīng)在指令被發(fā)射后，它所需求的操作數(shù)所對(duì)應(yīng)的存放器被重命名為保管站的名字的存放器被重命名為保管站的名字o 2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 保管站保管站o 保管站與存放器堆相比有兩個(gè)重要特保管站與存放器堆相比有兩個(gè)重要特點(diǎn)，首先，冒險(xiǎn)檢測(cè)和執(zhí)行控制是

18、分布點(diǎn)，首先，冒險(xiǎn)檢測(cè)和執(zhí)行控制是分布的，一個(gè)單元中的指令何時(shí)可以開(kāi)場(chǎng)執(zhí)的，一個(gè)單元中的指令何時(shí)可以開(kāi)場(chǎng)執(zhí)行是由該單元保管站所掌握的信息決議行是由該單元保管站所掌握的信息決議的；其次，結(jié)果將從緩存它們的保管站的；其次，結(jié)果將從緩存它們的保管站中直接傳送給功能單元，而不是經(jīng)過(guò)存中直接傳送給功能單元，而不是經(jīng)過(guò)存放器傳送，這是經(jīng)過(guò)一條公共結(jié)果總線放器傳送，這是經(jīng)過(guò)一條公共結(jié)果總線/公共數(shù)據(jù)總線實(shí)現(xiàn)的，它使得等待操作公共數(shù)據(jù)總線實(shí)現(xiàn)的，它使得等待操作數(shù)的一切單元可以同時(shí)取到操作數(shù)。數(shù)的一切單元可以同時(shí)取到操作數(shù)。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o Tomasulo算法處置器構(gòu)造o 該處置器根本構(gòu)造見(jiàn)

19、圖2.9，包括浮點(diǎn)單元和load-store單元。每個(gè)保管站保管一條曾經(jīng)被發(fā)射并等待執(zhí)行的指令，假設(shè)指令所需求的操作數(shù)曾經(jīng)被計(jì)算出來(lái)，那么保管站需求保管該操作數(shù)，否那么要保管將要提供該操作數(shù)的保管站的名字。o load-store緩存保管從存儲(chǔ)器中讀出或即將要保管到存儲(chǔ)器中去的數(shù)據(jù)或數(shù)據(jù)地址。 o 浮點(diǎn)存放器經(jīng)過(guò)一對(duì)總線和功能單元相連，經(jīng)過(guò)一條單獨(dú)的總線和store緩存相連。從功能單元和存儲(chǔ)器中得到的結(jié)果被送往公共數(shù)據(jù)總線。o 保管站均設(shè)置標(biāo)簽域，用于流水線控制。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 指令運(yùn)轉(zhuǎn)的三個(gè)階段o 1、發(fā)射：從指令隊(duì)列中取到下一條指令，指令隊(duì)列按FIFO順序維護(hù)，以保證正

20、確的數(shù)據(jù)流。假設(shè)有匹配的空閑保管站，并且指令的操作數(shù)的值也保管在存放器中，那么將指令和操作數(shù)的值一同發(fā)射到該保管站中。假設(shè)沒(méi)有空閑的保管站，那么闡明發(fā)生構(gòu)造冒險(xiǎn)，指令會(huì)被停頓，直至出現(xiàn)可用的保管站或緩存。假設(shè)操作數(shù)不在存放器中，那么需求跟蹤將要產(chǎn)生該操作數(shù)的功能單元，存放器重命名在這一步進(jìn)展。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 指令運(yùn)轉(zhuǎn)的三個(gè)階段o 2、執(zhí)行：假設(shè)有一個(gè)或多個(gè)操作數(shù)處于不可用形狀，那么監(jiān)視公共數(shù)據(jù)總線，等待這些操作數(shù)被計(jì)算出來(lái)。當(dāng)一個(gè)操作數(shù)可用時(shí)，該操作數(shù)將被放入等待它的保管站中。當(dāng)指令所需的一切操作數(shù)都已就緒時(shí)，該指令將在相應(yīng)的功能單元中執(zhí)行。經(jīng)過(guò)在操作數(shù)可用之前延遲指令的執(zhí)

21、行，防止了RAW冒險(xiǎn)。假設(shè)多條指令在同一個(gè)時(shí)鐘周期內(nèi)就緒，那么功能單元將被迫在就緒指令間做出選擇。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o 指令運(yùn)轉(zhuǎn)的三個(gè)階段o 2、執(zhí)行：為了維護(hù)異常行為，在程序順序中的一切前序轉(zhuǎn)移完成之前，任何指令都不能開(kāi)場(chǎng)執(zhí)行。這個(gè)約束可以確保在執(zhí)行過(guò)程中引起異常的指令會(huì)被執(zhí)行。o 3、寫(xiě)結(jié)果：當(dāng)結(jié)果就緒時(shí)，將其寫(xiě)到公共數(shù)據(jù)總線上，并由此送往等待它的存放器和保管站。o 當(dāng)指令曾經(jīng)被發(fā)射且正在等待源操作數(shù)時(shí)，標(biāo)簽字段將指向包含將產(chǎn)生源操作數(shù)指令的保管站號(hào)，比如0那么闡明操作數(shù)曾經(jīng)在存放器中就緒。2.4 采用動(dòng)態(tài)調(diào)度抑制數(shù)據(jù)冒險(xiǎn)o Tomasulo算法o Tomasulo方法采用總

22、線廣播結(jié)果的方式，由保管站監(jiān)聽(tīng)，這種方法實(shí)現(xiàn)了靜態(tài)流水線調(diào)度中直接通路和旁路技術(shù)的功能，而在動(dòng)態(tài)調(diào)度方法中，為了到達(dá)同樣的目的，需求在源和結(jié)果之間添加一個(gè)時(shí)鐘周期的時(shí)延，與功能單元產(chǎn)生結(jié)果相比，動(dòng)態(tài)調(diào)度流水線中消費(fèi)指令和消費(fèi)指令之間的有效時(shí)延至少要多花一個(gè)時(shí)鐘周期。o 每個(gè)保管站有七個(gè)字段，見(jiàn)P66.2.6 基于硬件的推測(cè) 當(dāng)我們?cè)噲D進(jìn)一步開(kāi)發(fā)指令級(jí)并行時(shí)，維護(hù)控制相關(guān)性便成為一個(gè)嚴(yán)重的負(fù)擔(dān)。轉(zhuǎn)移預(yù)測(cè)技術(shù)減少了直接由轉(zhuǎn)移引起的停頓，但是要想使處置器在一個(gè)時(shí)鐘周期內(nèi)執(zhí)行多條指令，僅靠轉(zhuǎn)移預(yù)測(cè)恐怕無(wú)法使我們獲得期望的指令級(jí)并行度。為了堅(jiān)持最高性能，一個(gè)寬發(fā)射處置器能夠需求每個(gè)時(shí)鐘周期都執(zhí)行一條轉(zhuǎn)移

23、指令，因此，要想進(jìn)一步開(kāi)發(fā)并行度，就必需抑制控制相關(guān)帶來(lái)的問(wèn)題?？梢越?jīng)過(guò)推測(cè)轉(zhuǎn)移的結(jié)果，并按照推測(cè)正確的情況執(zhí)行指令，以到達(dá)抑制控制相關(guān)的目的。 2.6 基于硬件的推測(cè)o 基于硬件的推測(cè)綜合以下三種思想o 經(jīng)過(guò)動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)選擇要執(zhí)行的指令，經(jīng)過(guò)推測(cè)技術(shù)允許指令在控制相關(guān)消除之前開(kāi)場(chǎng)執(zhí)行可以消除錯(cuò)誤推測(cè)序列的影響，經(jīng)過(guò)動(dòng)態(tài)調(diào)度處置幾個(gè)不同的根本塊之間的調(diào)度作為比較，沒(méi)有推測(cè)的動(dòng)態(tài)調(diào)度只能在根本塊之間實(shí)現(xiàn)部分重疊2.6 基于硬件的推測(cè)o 基于硬件的推測(cè)o 為了擴(kuò)展Tomasulo算法并使其支持推測(cè)技術(shù)，必需將指令結(jié)果的旁路操作推測(cè)執(zhí)行指令需求指令結(jié)果的旁路操作從實(shí)踐的指令完成中分別出來(lái)。經(jīng)過(guò)這種分

24、別，可以允許指令將它的執(zhí)行結(jié)果旁路給其他指令，而在確定而不是推測(cè)指令的執(zhí)行之前，不允許做任何更新。2.6 基于硬件的推測(cè)o 基于硬件的推測(cè)o 實(shí)現(xiàn)推測(cè)技術(shù)的關(guān)鍵思想是允許指令亂序執(zhí)行，但是要求指令必需按序提交，并且在指令提交之前阻止一切不可恢復(fù)的動(dòng)作比如更新形狀或產(chǎn)生異常。當(dāng)運(yùn)用推測(cè)技術(shù)擴(kuò)展動(dòng)態(tài)調(diào)度時(shí)，必需將指令的完成與指令提交區(qū)分開(kāi)來(lái)，由于指令能夠在提交之前曾經(jīng)完成。在指令執(zhí)行過(guò)程中需求一組硬件緩存的支持，運(yùn)用這些緩存保管曾經(jīng)執(zhí)行完但還沒(méi)有提交的指令執(zhí)行結(jié)果，這些硬件緩存稱為重排序緩存。2.6 基于硬件的推測(cè)o 重排序緩存ROBo 重排序緩存提供了附加的存放器，這種方法與Tomasulo算法

25、經(jīng)過(guò)保管站擴(kuò)展存放器集類似。在指令運(yùn)算完成到提交這段時(shí)間內(nèi)，重排序緩存為指令保管結(jié)果。即在這段時(shí)間內(nèi)， ROB是指令的操作數(shù)源，但ROB與保管站的重要區(qū)別是：在Tomasulo算法中，當(dāng)指令完成寫(xiě)結(jié)果的操作后，一切的后繼指令都將從存放器文件中讀取結(jié)果；而在推測(cè)技術(shù)中，只需在指令提交之后存放器文件才會(huì)被更新。2.6 基于硬件的推測(cè)o 重排序緩存ROBo 重排序緩存每一個(gè)入口都包含4個(gè)字段：指令類型、目的字段、值字段和就緒字段。o 指令類型字段闡明指令是轉(zhuǎn)移運(yùn)算、store操作還是存放器運(yùn)算。o 目的字段提供存放器序號(hào)或存儲(chǔ)器地址，指令將把結(jié)果寫(xiě)向目的字段指向的存放器或存儲(chǔ)器o 值字段用來(lái)在指令提

26、交之前，保管指令執(zhí)行結(jié)果的值，就緒字段闡明指令曾經(jīng)完成它的執(zhí)行，其結(jié)果曾經(jīng)可用。2.6 基于硬件的推測(cè)o 處置器硬件構(gòu)造o 見(jiàn)圖2.14。雖然ROB替代了保管站的重命名功能，但是在指令發(fā)射到指令開(kāi)場(chǎng)執(zhí)行這段時(shí)間內(nèi)，依然需求一個(gè)空間來(lái)緩存操作及操作數(shù)。這個(gè)功能依然由保管站來(lái)提供。由于一切指令在提交之前都在ROB中占有一個(gè)位置，因此，用ROB入口的序號(hào)作為結(jié)果的標(biāo)簽，而不是運(yùn)用保管站的序號(hào)。這要求分配給指令的ROB序號(hào)必需可以記錄在保管站中。這里實(shí)現(xiàn)時(shí)為重命名運(yùn)用額外的存放器，而ROB僅用于記錄指令提交的時(shí)間。2.6 基于硬件的推測(cè)o 指令的執(zhí)行過(guò)程o 指令的執(zhí)行包括發(fā)射、執(zhí)行、寫(xiě)結(jié)果和提交4個(gè)步

27、驟，其中前3個(gè)步驟與Tomasulo算法類似，只添加了提交最后一個(gè)階段。o 提交階段是完成指令的最后一個(gè)階段，這之后只需指令的結(jié)果被保管。o 當(dāng)指令提交后，指令在ROB中的入口將被收回，存放器或存儲(chǔ)器將被更新，無(wú)須再占用ROB的入口。假設(shè)ROB已被填滿，那么只需求停頓指令的發(fā)射，直到有可用的入口出現(xiàn)為止。2.7多發(fā)射技術(shù) 采用前面幾節(jié)中引見(jiàn)的技術(shù)可以消除數(shù)據(jù)相關(guān)和控制相關(guān)引起的停頓，從而獲得理想的CPI理想CPI為多少？。為了進(jìn)一步提高性能，需求將CPI減小到1以下，但在每個(gè)時(shí)鐘周期發(fā)射一條指令的前提下，無(wú)法實(shí)現(xiàn)這個(gè)目的。 采用多發(fā)射技術(shù)可以處理此問(wèn)題，多發(fā)射處置器的目的是允許在一個(gè)時(shí)鐘周期內(nèi)

28、發(fā)射多條指令，重點(diǎn)引見(jiàn)VLIW方法。2.7多發(fā)射技術(shù)o VLIW方法o VLIW超長(zhǎng)指令字處置器每時(shí)鐘周期發(fā)射固定數(shù)目的指令，這些指令被組織成一條長(zhǎng)指令或一個(gè)固定的指令包，指令間的并行度由指令顯式地表示出來(lái)。 VLIW處置器采用編譯器靜態(tài)調(diào)度的方式。o VLIW采用多個(gè)獨(dú)立的功能單元， 將多個(gè)運(yùn)算打包成一條長(zhǎng)指令，或者要求發(fā)射包中的指令滿足一樣的約束，兩種方法本質(zhì)上一樣。2.7多發(fā)射技術(shù)o VLIW方法o 對(duì)于寬發(fā)射情況，VLIW的優(yōu)勢(shì)更加明顯。為了使功能單元一直處于任務(wù)形狀，代碼序列必需含有足夠的并行度，以填滿功能單元的可用運(yùn)算槽。代碼序列中的并行度可用經(jīng)過(guò)將循環(huán)展開(kāi)，在每個(gè)單獨(dú)的、更大的循

29、環(huán)體中進(jìn)展代碼調(diào)度而實(shí)現(xiàn)。假設(shè)并行度要求跨轉(zhuǎn)移調(diào)度代碼，那么需求運(yùn)用更復(fù)雜的全局調(diào)度算法，附錄G中，討論了一種專門(mén)為VLIW設(shè)計(jì)的全局調(diào)度技術(shù)，我們重點(diǎn)討論無(wú)轉(zhuǎn)移代碼調(diào)度情況。2.7多發(fā)射技術(shù)o VLIW方法o 為了抑制代碼快速增長(zhǎng)帶來(lái)的影響，可采用智能譯碼方法，比如讓一切的功能單元運(yùn)用一個(gè)立刻數(shù)字段；也可以在主存中緊縮指令，當(dāng)指令被讀入Cache或被譯碼時(shí)再將它們解緊縮。o 早期VLIW是鎖步的，并且沒(méi)有檢測(cè)冒險(xiǎn)的硬件，由于一切的功能單元必需堅(jiān)持同步，因此恣意一個(gè)功能單元的停頓都將引起整個(gè)處置器的停頓。雖然編譯器可以對(duì)確定的功能單元進(jìn)展調(diào)度以阻止停頓，但是要預(yù)測(cè)停頓是困難的。在最近的處置器中

30、，功能單元的操作越來(lái)越獨(dú)立，指令發(fā)射后，由硬件擔(dān)任檢測(cè)指令異步執(zhí)行。2.7多發(fā)射技術(shù)o VLIW方法-開(kāi)發(fā)指令級(jí)并行首選方法o 開(kāi)發(fā)指令級(jí)并行度是一切多發(fā)射處置器所面臨的一個(gè)共同挑戰(zhàn)。某些情況下，向量處置器可以高效地執(zhí)行浮點(diǎn)程序中的一些簡(jiǎn)單循環(huán)，而多發(fā)射處置器需求將循環(huán)展開(kāi)才可以獲得足夠的并行度。對(duì)于這類運(yùn)用，很難確定多發(fā)射處置器能否真的優(yōu)于向量處置器；當(dāng)代價(jià)一樣時(shí)，向量處置器能夠會(huì)更快。然而多發(fā)射處置器的優(yōu)勢(shì)在于他們可以從構(gòu)造化較差的代碼中開(kāi)發(fā)并行度，而且有才干緩存一切格式的數(shù)據(jù)，這些緣由使得多發(fā)射處置器成為開(kāi)發(fā)指令級(jí)并行度的首選方法，而向量處置器只是作為多發(fā)射處置器的擴(kuò)展和補(bǔ)充。2.9指令

31、傳送和推測(cè)的高級(jí)技術(shù)o 提高取指令帶寬o 在高性能流水線特別是多發(fā)射流水線中，僅靠準(zhǔn)確地預(yù)測(cè)轉(zhuǎn)移是不夠的，還需求傳送高帶寬的指令流。比如現(xiàn)代多發(fā)射處置器每時(shí)鐘周期要傳送4-8條指令。o 多發(fā)射處置器要求每時(shí)鐘周期取到的平均指令數(shù)目不低于平均吞吐量，這要求通向指令Cache的途徑足夠?qū)?，帶最困難的還是轉(zhuǎn)移的處置。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 轉(zhuǎn)移目的緩存o 為了減小流水線的轉(zhuǎn)移代價(jià)，必需確定當(dāng)前正在譯碼的指令能否是轉(zhuǎn)移指令，假設(shè)是，那么下一條指令的地址是什么，假設(shè)是轉(zhuǎn)移指令且知道下一條指令的地址，那么就可以將轉(zhuǎn)移代價(jià)降為0。把為轉(zhuǎn)移的后繼指令保管預(yù)測(cè)地址的轉(zhuǎn)移預(yù)測(cè)Cache稱為轉(zhuǎn)移目的緩存或

32、轉(zhuǎn)移目的Cache。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 轉(zhuǎn)移目的緩存o 由于轉(zhuǎn)移目的緩存要預(yù)測(cè)下一條指令的地址，并且在指令譯碼終了前將預(yù)測(cè)地址發(fā)送出去，因此必需確定取到的指令能否是一條被預(yù)測(cè)為將被選中的轉(zhuǎn)移指令。假設(shè)地址匹配，那么相應(yīng)的預(yù)測(cè)指令地址將作為下一條指令的地址。轉(zhuǎn)移預(yù)測(cè)緩存的硬件構(gòu)造本質(zhì)上與Cache的硬件構(gòu)造一致圖2.22。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 轉(zhuǎn)移目的緩存o 假設(shè)在轉(zhuǎn)移目的緩存中發(fā)現(xiàn)了一個(gè)匹配的入口，那么取指令立刻從預(yù)測(cè)指令地址開(kāi)場(chǎng)。由于在確定指令能否轉(zhuǎn)移之前將預(yù)測(cè)地址發(fā)送出去，因此轉(zhuǎn)移目的緩存的預(yù)測(cè)入口必需與指令完全匹配，假設(shè)處置器不對(duì)這種匹配進(jìn)展核實(shí)，那么在當(dāng)前指令

33、不是轉(zhuǎn)移的情況下，發(fā)送出去的預(yù)測(cè)地址就是錯(cuò)誤的，這會(huì)降低處置器的速度。在轉(zhuǎn)移目的緩存中，只保管那些預(yù)測(cè)為被選中的轉(zhuǎn)移。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 轉(zhuǎn)移目的緩存o 運(yùn)用轉(zhuǎn)移目的緩存的詳細(xì)步驟參考圖2.23.o o 在緩存中存在匹配的轉(zhuǎn)移入口且預(yù)測(cè)正確的情況下，是不存在轉(zhuǎn)移延遲的；否那么，將至少付出2個(gè)時(shí)鐘周期的轉(zhuǎn)移代價(jià)。處置緩存缺失和預(yù)測(cè)錯(cuò)誤是一個(gè)艱巨的挑戰(zhàn)，由于必需在重寫(xiě)緩存入口的同時(shí)停頓取指令的操作。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 轉(zhuǎn)移目的緩存o 轉(zhuǎn)移目的緩存的另外一種方式是在緩存中保管一條或多條目的指令，以此作為預(yù)測(cè)目的地址的替代或補(bǔ)充。這種方式有兩個(gè)潛在優(yōu)勢(shì)，首先，這種方法允許轉(zhuǎn)

34、移目的緩存的訪問(wèn)時(shí)間超越兩個(gè)相繼取指令操作的時(shí)間間隔，也能夠允許更大的轉(zhuǎn)移目的緩存；其次，經(jīng)過(guò)緩存實(shí)踐的指令可以實(shí)現(xiàn)優(yōu)化，稱之為轉(zhuǎn)移隱含，運(yùn)用轉(zhuǎn)移隱含，可以將無(wú)條件轉(zhuǎn)移代價(jià)降為0時(shí)鐘周期。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 前往地址預(yù)測(cè)器o 當(dāng)要提高推測(cè)的準(zhǔn)確性時(shí)，將面臨間接轉(zhuǎn)移帶來(lái)的挑戰(zhàn)，間接轉(zhuǎn)移目的地址是在運(yùn)轉(zhuǎn)時(shí)確定的。高級(jí)編程言語(yǔ)會(huì)為間接程序調(diào)用、case選擇語(yǔ)句以及goto語(yǔ)句生成這類轉(zhuǎn)移，但間接轉(zhuǎn)移大部分還是來(lái)自過(guò)程前往，而在面向?qū)ο蟮难哉Z(yǔ)中，比如c+或Java，過(guò)程前往更加頻繁。o 過(guò)程前往可運(yùn)用堆棧作為前往地址緩存，該構(gòu)造用來(lái)緩存最近的幾個(gè)前往地址，當(dāng)調(diào)用發(fā)生時(shí)將前往地址壓入堆棧，

35、調(diào)用前往時(shí)再將其彈出。假設(shè)Cache足夠大的話，它將出色地預(yù)測(cè)前往地址。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 集成的取指令單元o 為了滿足多發(fā)射處置器的要求，可選擇集成取指令單元的方法，將取指令作為一個(gè)獨(dú)立自主的單元來(lái)實(shí)現(xiàn)，由該單元為流水線的其他部分提供指令，當(dāng)然，這會(huì)添加多發(fā)射的復(fù)雜性，不再將取指令視為一個(gè)單獨(dú)的流水段。在最新設(shè)計(jì)中，集成取指令單元包含以下功能：集成的轉(zhuǎn)移預(yù)測(cè)、指令預(yù)取、指令存儲(chǔ)器訪問(wèn)和緩存。2.9指令傳送和推測(cè)的高級(jí)技術(shù)o 集成的取指令單元o 1、集成的轉(zhuǎn)移預(yù)測(cè)o 轉(zhuǎn)移預(yù)測(cè)成為取指令的一部分，并且繼續(xù)對(duì)轉(zhuǎn)移進(jìn) 行預(yù)測(cè)，以驅(qū)動(dòng)流水線的取指令操作。o 2、指令預(yù)取o 為實(shí)現(xiàn)一個(gè)時(shí)鐘周期內(nèi)傳送多條指令，取指令單元自主管理指令的預(yù)取，并將它