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