《《計算機系統(tǒng)結(jié)構(gòu)》電子教案(課6).ppt》由會員分享，可在線閱讀，更多相關(guān)《《計算機系統(tǒng)結(jié)構(gòu)》電子教案(課6).ppt（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、2014.2.17,計算機系統(tǒng)結(jié)構(gòu),1,第5章 指令級并行硬件方法（P111）（指令級，多發(fā)射或亂序執(zhí)行，動態(tài)調(diào)度）,本章學(xué)習(xí)由硬件（即流水線控制器）實現(xiàn)的指令級并行方法，主要內(nèi)容是流水線的多指令控制技術(shù)，目的是讓處理機中同時流動更多的指令，減少各種原因造成的停頓，以縮短程序執(zhí)行時間。 5.1 指令級并行的概念（重點） 5.2 相關(guān)與指令級并行 5.3 指令的動態(tài)調(diào)度 5.4 動態(tài)分支預(yù)測技術(shù)（重點） 5.5 多指令流出技術(shù)（重點）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),2,從執(zhí)行程序的角度來看，并行性等級從低到高可分為： 指令內(nèi)部并行：單條指令中各微操作之間的并行。 指令級并行：并行執(zhí)行兩條或
2、兩條以上的指令。 線程級并行：并行執(zhí)行兩個或兩個以上的線程。通常是以一個進程內(nèi)派生的多個線程為調(diào)度單位。 任務(wù)級或過程級并行：并行執(zhí)行兩個或兩個以上的過程或任務(wù)（程序段）。以子程序或進程為調(diào)度單元。 作業(yè)或程序級并行：并行執(zhí)行兩個或兩個以上的作業(yè)或程序。,并行性等級的劃分（P23，1.5.1節(jié)）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),3,指令級并行的英文縮寫是ILP （Instruction-Level Parallelism） 開發(fā)ILP的途徑有兩種： 資源重復(fù)，重復(fù)設(shè)置多個處理部件，讓它們同時執(zhí)行相鄰或相近的多條指令； 采用流水線技術(shù)，使指令重疊并行執(zhí)行。 (1)狹義指令級并行 超標(biāo)量
3、SuperScalar （設(shè)備重復(fù)） 超長指令字Very Long Instruction Word（簡稱VLIW） (2)廣義指令級并行 流水線Pipeline （設(shè)備細(xì)分） 超級流水線Super Pipeline (3)線程級并行 超線程Hyper-Threading（簡稱HT） (4)任務(wù)線程 多核處理機Multicore,5.1 指令級并行的概念,,,,,,,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),4,靜態(tài)調(diào)度（軟件方法）：在程序執(zhí)行前，在編譯過程中對目標(biāo)指令序列進行優(yōu)化，避免將來由于相關(guān)和沖突造成的停頓。主要手段是將沖突指令錯開啟動時間、變
4、量換名等。 動態(tài)調(diào)度（硬件方法）：在程序執(zhí)行中，由專門硬件預(yù)測將要發(fā)生的沖突、控制指令在流水線中的流動，避免停頓。 2. 流水線處理機的實際CPI = 理想流水線的CPI加上各類停頓的時鐘周期數(shù)： CPI流水線 = CPI理想 + 停頓結(jié)構(gòu)沖突 + 停頓數(shù)據(jù)沖突 + 停頓控制沖突 CPI理想是衡量流水線最高性能的一個指標(biāo)。本式表明降低實際CPI有許多途徑。 換一個角度，有時從CPI的倒數(shù)看問題會有新思路，IPC（Instructions Per Cycle）是每個時鐘周期完成的指令條數(shù)。 在不能縮短單條指令周期數(shù)的情況下，在每個時鐘周期里啟動更多的指令（提高IPC），同樣可以提高處理
5、機的性能。這就是ILP的基本思想。,1. 開發(fā)ILP的方法分類,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),5,基本程序塊：一串連續(xù)的代碼除了入口和出口以外，沒有其他的分支指令和轉(zhuǎn)入點 。 程序平均每47條指令就會有一個分支。 4. 循環(huán)級并行：使一個循環(huán)中的不同循環(huán)體并行執(zhí)行。 開發(fā)循環(huán)的不同疊代之間存在的并行性（最常見、最基本思路） 這是指令級并行研究的重點之一 5. 最基本的開發(fā)循環(huán)級并行的技術(shù) 循環(huán)展開（loop unrolling）技術(shù) 采用向量指令和向量數(shù)據(jù)表示,3. 基本程序塊,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),6,多發(fā)射技術(shù)（Multiple Issue）：同時啟動多條指令。 為什么
6、要多發(fā)射？在傳統(tǒng)流水線上，要減少CPU時間，可以減少CPI或者Cycle。CPI的下限是1，減少Cycle碰到了“4G墻”（指Intel公司開發(fā)4GHz P4計劃失敗，因為功耗正比于主頻3次方），工程師們無奈又回頭來打CPI的主意，想使CPI低于1，即在一個時鐘周期內(nèi)流出多條指令。 狹義的多指令流出技術(shù)（同時啟動）包括超標(biāo)量(Superscalar)和超長指令字(VLIW)，廣義的多指令流出技術(shù)（分時啟動）還包括超流水線(Superpipeline)等。 超標(biāo)量采用多條流水線的多發(fā)射技術(shù)，每個時鐘周期流出的指令數(shù)不定，既可以使用編譯器靜態(tài)調(diào)度，也可以使用硬件動態(tài)調(diào)度。 由于管理亂序流動中指令相
7、關(guān)問題的硬件復(fù)雜度非常大，所以目前超標(biāo)量CPU的ILP沒有超過8的。 采用單發(fā)射技術(shù)的傳統(tǒng)處理機又被稱為“標(biāo)量處理機”。,5.5 多指令流出技術(shù)（又稱多發(fā)射技術(shù)，P141）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),7,超長指令字CPU采用長指令單發(fā)射，多個執(zhí)行部件同時執(zhí)行小指令的方法，每個時鐘周期流出的小指令數(shù)是限定的。在編譯過程中，由編譯程序來判斷實際指令之間的相關(guān)關(guān)系，進行靜態(tài)調(diào)度，把抽取ILP的復(fù)雜工作轉(zhuǎn)移給編譯器，而執(zhí)行指令的硬件則大大簡化，也比較規(guī)則，有利于低功耗設(shè)計。 超流水線則是將每個功能部件進一步流水化，使得一個功能部件在一拍中可以分時處理多條指令。,5.5 多指令流出技術(shù)（續(xù)）,
8、2014.2.17,計算機系統(tǒng)結(jié)構(gòu),8,5.5.0 超標(biāo)量技術(shù)：一個時鐘節(jié)拍內(nèi)同時發(fā)射多條指令（P142第1段）。,時空圖,“超標(biāo)量”的前身是“多操作部件技術(shù)”。它是通過“設(shè)備并聯(lián)”技術(shù)擴充的單流水線，被擴充的部件通常是運算部件、訪存部件等“瓶頸”部件。,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),9,5.5.3 超長指令字技術(shù)VLIW（P147，P163）,把多條無相關(guān)關(guān)系的常規(guī)指令打包在一個超長的指令字中，讓它們同時被處理，分別控制多個功能部件并行工作的技術(shù)。 每個操作放在一個槽（slot）內(nèi)。 這種技術(shù)的實質(zhì)，是把超標(biāo)量技術(shù)中的相關(guān)性識別任務(wù)，由CPU硬件轉(zhuǎn)移給程序員或編譯程序去實現(xiàn)。,2014
9、.2.17,計算機系統(tǒng)結(jié)構(gòu),10,5.5.5 超流水技術(shù)：一個時鐘節(jié)拍內(nèi)分時發(fā)射多條指令（P149）,時空圖,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),11,附：超線程技術(shù)HT,通俗的理解就是將一顆具有超線程功能的“實體”處理器虛擬成兩個“邏輯”處理器，讓多個應(yīng)用程序或單一應(yīng)用程序的多個線程，能夠同時在同一顆處理器上執(zhí)行。 超線程運行模式下，CPU中核心資源的利用率可提高3040%，也就是說在同樣時間里可多執(zhí)行3040%的指令，其性能可以與含雙處理器的系統(tǒng)相媲美，但具有低得多的價格。 為了同時執(zhí)行多個線程，使用超線程技術(shù)的新一代P4 HT處理器需要增加一個邏輯處理器單元。因此面積比以往的P4增大了5
10、%。而其余部分如ALU（整數(shù)運算單元）、FPU（浮點運算單元）、L2 Cache（二級緩存）則保持不變，這些部分是被分享的。 雖然采用超線程技術(shù)能同時執(zhí)行兩個線程，但是當(dāng)兩個線程爭奪同一資源時，其中一個要被阻塞，這時性能就不如兩個真正的CPU。 含有超線程技術(shù)的CPU需要主板（包括芯片組和BIOS）、軟件（包括操作系統(tǒng)和應(yīng)用軟件，如XP）支持，才能比較理想地發(fā)揮該項技術(shù)的優(yōu)勢。 超線程是一種過渡技術(shù)，不久就被多核心技術(shù)取代。,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),12,對于多指令流出的處理機，分支等待造成的性能下降比單流出機器更為顯著每停一拍要減少幾條指令，所以需要采取更復(fù)雜的解決辦法。 第
11、3章介紹了避免在分支（包括無條件跳轉(zhuǎn)）指令后面空等待的幾種方法。 其中“在ID周期完成判斷并計算目標(biāo)地址”的方法把分支等待周期由3個減少到1個，但是再要消除這1個等待周期就很難了。有的處理機做這兩件事需要的周期數(shù)還不止1個。 從上文調(diào)換不相關(guān)指令到“延遲槽”執(zhí)行的辦法固然可以避免這段時間的空等待，但是找不到不相關(guān)指令就不能用。 為了利用這種等待周期，還有一個辦法是“猜測”，不等“判跳”完成就開始取下條指令，取完之后“判跳”結(jié)果也出來了，如果證明“猜對”就繼續(xù)執(zhí)行這條指令，“猜錯”就報廢它。 為了容易實現(xiàn)，一個CPU在設(shè)計時就把“猜”的方向設(shè)定了，即總是猜分支失敗（或者總是猜分支成功），這種猜法
12、的“猜對率”沒有保障。,5.4 動態(tài)分支預(yù)測技術(shù)（P133）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),13,現(xiàn)在討論的“動態(tài)分支預(yù)測技術(shù)”就是對每條分支指令完成之后的真實方向進行記錄，下次再回到這條指令時就往上次的同一方向猜，猜對的可能性就增大了。萬一有的指令是一會兒總是分支失敗，一會兒又總是分支成功（動態(tài)變化），那也可以在猜錯后及時修改記錄，以后就按新的方向猜。 “分支開銷”指“猜對”、“猜錯”兩種情況下流水線分別等待的時間（周期數(shù)）。顯然，“猜錯”時的開銷更大，否則“猜”就沒有意義了。,5.4 動態(tài)分支預(yù)測技術(shù)（續(xù)）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),14,分支歷史表的英文縮寫是BHT（Br
13、anch History Table） (1) 1位BHT方法 表中給最近遇到的每條分支指令分配1個bit的記錄單元，0表示上次分支不成功，1表示上次分支成功。 BHT表可以設(shè)在指令Cache中，也可以用一個專門的RAM來實現(xiàn)。查表方法是相聯(lián)比較。表的容量決定了能為多少個“最近用到”的分支指令記錄歷史信息。裝滿之后可以按“先進先出”或“最近最少使用”策略進行替換。,5.4.1 分支歷史表 BHT 方法（P134）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),15,(2) 2位BHT方法 有的分支指令會有“臨時性換向”，比如一段循環(huán)程序末尾的“返回指令”可能在n-1次分支成功后跟1次分支失敗，但是下一次
14、再執(zhí)行這段循環(huán)程序，“返回指令”又應(yīng)該按分支成功猜測。為了避免“1位BHT方法”被這種偶然變化所“欺騙”，可以使用2bit信息記錄，只有連續(xù)2次“猜錯”才會“改口”猜另一方向。具體算法見下圖。,5.4.1 分支歷史表 BHT 方法（續(xù)）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),16,分支目標(biāo)緩沖器的英文縮寫是BTB（Branch-Target Buffer），也稱分支目標(biāo)Cache（ranch-Target Cache）。 上面介紹的BHT表只保存了分支指令地址和成功轉(zhuǎn)移的方向，沒有保存成功轉(zhuǎn)移的目標(biāo)地址，即只猜“是否轉(zhuǎn)移”，不猜“轉(zhuǎn)到哪里”，在轉(zhuǎn)移成功情況下即使“猜對了”也需要另花時間計算目標(biāo)地
15、址，這對于判斷分支方向和計算目標(biāo)地址同時進行的機器來說起不到節(jié)省時間的作用。 分支目標(biāo)緩沖器BTB表里面增加了成功轉(zhuǎn)移的目標(biāo)地址，如果“猜”本次轉(zhuǎn)移成功就可以立即用它取指，不等待目標(biāo)地址的計算結(jié)果，而“猜”本次分支失敗則不需要使用目標(biāo)地址。所以BTB表只保存成功的分支指令地址及其目標(biāo)地址，不保存失敗的分支指令。遇到分支指令要“猜”時，采用并行比較來搜索，搜到匹配項猜“分支成功” ，沒有匹配項猜“分支失敗” ，而后者不需要BTB提供目標(biāo)地址。,5.4.2 分支目標(biāo)緩沖器BTB方法,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),17,BTB表的結(jié)構(gòu)：,分支目標(biāo)緩沖器BTB方法（續(xù)1）,2014.2.17,計
16、算機系統(tǒng)結(jié)構(gòu),18,BTB預(yù)測方法邏輯分支圖：,分支目標(biāo)緩沖器BTB方法（續(xù)2）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),19,BTB預(yù)測機構(gòu)加入到流水線中：,分支目標(biāo)緩沖器BTB方法（續(xù)3）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),20,現(xiàn)在分析采用BTB預(yù)測方法的加速效果，以第3章末尾（P90）的改進后的MIPS流水線為例。 在采用BTB預(yù)測方法之前，該流水線在ID周期進行分支判斷與計算目標(biāo)地址，到EX周期才能取下一條指令，所以每條轉(zhuǎn)移指令之后有1個周期的固定延遲。 采用BTB預(yù)測方法之后，不同情況下的延遲周期數(shù)是不同的，下面分4種情形討論。,分支目標(biāo)緩沖器BTB方法（續(xù)4）,2014.2.17,
17、計算機系統(tǒng)結(jié)構(gòu),21,情形1：BTB命中，指令K轉(zhuǎn)移 延遲=0,分支目標(biāo)緩沖器BTB方法（續(xù)5）,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令K,指令L,1.指令K取指，PC+4； 2.使用指令K的地址，檢索BTB表，命中，表明指令K上次轉(zhuǎn)移成功，猜此次仍轉(zhuǎn)移，PC 指令L的地址,1.指令K譯碼、判斷轉(zhuǎn)移、計算轉(zhuǎn)移目標(biāo)地址； 2.判斷結(jié)果是：轉(zhuǎn)移。所以“試取指令L”有效； 3.不改BTB表，猜指令K下次仍轉(zhuǎn)移到指令L,使用PC值，試取指令L（有效）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),22,情形2：BTB命中，指令K不轉(zhuǎn)移 延遲=2,分支目標(biāo)緩沖器BTB方法（續(xù)6）,I
18、F,ID,EX,Mem,WB,ID,EX,Mem,WB,指令K,指令L,1.指令K取指，PC+4； 2.使用指令K的地址，檢索BTB表，命中，表明指令K上次轉(zhuǎn)移成功，猜此次仍轉(zhuǎn)移，PC 指令L的地址,1.指令K譯碼、判斷轉(zhuǎn)移、計算轉(zhuǎn)移目標(biāo)地址； 2.判斷結(jié)果是：不轉(zhuǎn)移。所以“試取指令L”無效，須報廢； 3.PC指令L的地址+4,使用PC值，試取指令L（無效）,Str,IF,指令K+1,使用新PC值，改取指令K+1,刪除BTB表該項，猜指令K下次不轉(zhuǎn)移,IF,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),23,情形3：BTB不命中，指令K轉(zhuǎn)移 延遲=2,分支目標(biāo)緩沖器BTB方法（續(xù)7）,IF,ID,EX,
19、Mem,WB,ID,EX,Mem,WB,指令K,指令K+1,1.指令K取指，PC+4； 2.使用指令K的地址，檢索BTB表，不命中，表明指令K上次沒有轉(zhuǎn)移，猜此次仍不轉(zhuǎn)移，不改PC,1.指令K譯碼、判斷轉(zhuǎn)移、計算轉(zhuǎn)移目標(biāo)地址； 2.判斷結(jié)果是：轉(zhuǎn)移。所以“試取指令K+1”無效，須報廢； 3.PC指令L的地址,使用PC值，試取指令K+1（無效）,Str,IF,指令L,使用新PC值，改取指令L,BTB表增添一項，猜指令K下次轉(zhuǎn)移到指令L,IF,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),24,情形4：BTB不命中，指令K不轉(zhuǎn)移 延遲=0,分支目標(biāo)緩沖器BTB方法（續(xù)8）,IF,ID,EX,Mem,WB,I
20、F,ID,EX,Mem,WB,指令K,指令K+1,1.指令K取指，PC+4； 2.使用指令K的地址，檢索BTB表，不命中，表明指令K上次沒有轉(zhuǎn)移，猜此次仍不轉(zhuǎn)移，不改PC,1.指令K譯碼、判斷轉(zhuǎn)移、計算轉(zhuǎn)移目標(biāo)地址； 2.判斷結(jié)果是：不轉(zhuǎn)移。所以“試取指令K+1”有效； 3.不改BTB表，猜指令K下次仍不轉(zhuǎn)移,使用PC值，試取指令K+1（有效）,注意：該情形包括當(dāng)前指令是轉(zhuǎn)移指令但不成功、當(dāng)前指令不是轉(zhuǎn)移指令兩種情況。,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),25,小結(jié)： 可見，與不用BTB的時序相比，情形1、4減少了延遲，而情形2、3增加了延遲。 我們可以這樣計算： 平均轉(zhuǎn)移延遲=情形1概率0
21、+情形2概率2+情形3概率2+情形1概率0 如果平均值小于1，則新方法加快了轉(zhuǎn)移指令執(zhí)行速度，反之則減慢了速度。,分支目標(biāo)緩沖器BTB方法（續(xù)9）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),26,采用BTB預(yù)測方法后的CPI計算公式： 平均CPI = 理想CPI + 平均延遲周期數(shù) 由于平均CPI針對所有指令，所以還要把非轉(zhuǎn)移指令也考慮進去，如下圖,分支目標(biāo)緩沖器BTB方法（續(xù)10）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),27,例5.6 設(shè)程序中轉(zhuǎn)移指令占20%，50%可以在BTB命中，命中的指令本次轉(zhuǎn)移概率為90%，未命中的指令本次轉(zhuǎn)移概率為60%，判斷轉(zhuǎn)移并計算地址的開銷是2，修改BTB的開銷是1
22、，非轉(zhuǎn)移指令的CPI=1。求平均CPI。 解：,分支目標(biāo)緩沖器BTB方法（續(xù)11）,平均CPI = 1 + 20% 50%(90%0 + 10%3) + + 50%(60%3 + 40%0) = 1.21,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),28,如果不采用BTB預(yù)測方法，每條轉(zhuǎn)移指令無論是否成功，都有2個周期的固定延遲。 平均CPI = 1 + 20%2 = 1.40 可見，采用BTB預(yù)測方法有可能縮短平均CPI。,分支目標(biāo)緩沖器BTB方法（續(xù)12）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),29,5.8題假設(shè)有一條長流水線，僅僅對條件轉(zhuǎn)移指令使用分支目標(biāo)緩沖。假設(shè)分支預(yù)測錯誤的開銷為4個時鐘周期
23、，緩沖不命中的開銷為3個時鐘周期。假設(shè)：命中率為90%，預(yù)測精度為90%，分支頻率為15%，沒有分支的基本CPI為1。 (1)求程序執(zhí)行的CPI。 (2)相對于采用固定的2個時鐘周期延遲的分支處理，采用哪種方法能使程序執(zhí)行速度更快？ 分析：,分支目標(biāo)緩沖器BTB方法（續(xù)13）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),30,5.9題假設(shè)分支目標(biāo)緩沖的命中率為90%，程序中無條件轉(zhuǎn)移指令的比例為5%，沒有無條件轉(zhuǎn)移指令的程序CPI值為1。假設(shè)分支目標(biāo)緩沖中包含分支目標(biāo)指令，允許無條件轉(zhuǎn)移指令進入分支目標(biāo)緩沖，則程序的CPI值為多少？假設(shè)原來的CPI=1.1。 分析：本題只考慮無條件轉(zhuǎn)移指令，所以取指后
24、100%會轉(zhuǎn)移，BTB命中開銷=0拍，所缺的條件是不命中開銷。再看，“原來的CPI”指使用BTB方法前的平均CPI，是1.1，理想CPI=1，由此可以解出原來的轉(zhuǎn)移開銷。使用BTB方法后的不命中開銷比它多1拍。,分支目標(biāo)緩沖器BTB方法（續(xù)14）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),31,思考題： 5.8題：BTB“命中率為90%”意味著什么？實際上有沒有可能達到？ 參考觀點：BTB表中存放最近一次執(zhí)行中轉(zhuǎn)移成功的轉(zhuǎn)移指令地址，它的命中率指程序中包含的全部轉(zhuǎn)移指令有百分之多少已經(jīng)存入。顯然，“條件轉(zhuǎn)移指令命中率為90%”的情形只能是90%以上條件轉(zhuǎn)移指令被執(zhí)行過后才可能出現(xiàn)，即程序運行的后期。我們要計算程序運行全程的平均CPI，應(yīng)該引用BTB的平均命中率，通常應(yīng)該在50%左右。 一些特殊程序中，BTB平均命中率也可能達到90%，比如高次數(shù)循環(huán)。 該題的設(shè)計者為了證明“BTB方法能使程序執(zhí)行速度更快”，設(shè)定了特殊情況下的已知條件。 5.9題：根據(jù)BTB方法原理，BTB不命中開銷 = 指令本身的轉(zhuǎn)移開銷 + BTB表修改開銷（1拍），但是習(xí)題指導(dǎo)書中的題解沒有加這1拍。 參考觀點：該題解應(yīng)該修正。,分支目標(biāo)緩沖器BTB方法（續(xù)15）,2014.2.17,計算機系統(tǒng)結(jié)構(gòu),32,各次作業(yè)應(yīng)交的內(nèi)容,作業(yè)6（第6次課）,5.11，5.8，5.9,
《計算機系統(tǒng)結(jié)構(gòu)》電子教案(課6).ppt
