7.并行技術(shù)和高端處理器(1)課件

1、第三章 并行技術(shù)和高端處理器提高計(jì)算機(jī)性能(速度)所經(jīng)歷的主要?dú)v程:微程序設(shè)計(jì)模式RISC設(shè)計(jì)模式并行設(shè)計(jì)模式指令并行、數(shù)據(jù)并行、線程并行、多核并行等已成為提升計(jì)算機(jī)速度的主要手段高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器 同時(shí)性(simultaneity): 是指把兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生的并行性叫同時(shí)性。 概述: 計(jì)算機(jī)中的并行性 并行性(parallelism): 是指在同一時(shí)刻或是同一時(shí)間間隔內(nèi)完成兩件或兩件以上的工作。只要時(shí)間上互相重疊, 就存在并行性。這一概念引入計(jì)算機(jī)系統(tǒng), 成為提高其性能的主要技術(shù)之一。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器以n位并行加法為例:

2、由于存在進(jìn)位信號(hào)的傳播延遲時(shí)間, 全部n位加法結(jié)果并不是在同一時(shí)刻獲得的, 因此并不存在同時(shí)性, 而只存在并發(fā)性的關(guān)系。 如果有m個(gè)存儲(chǔ)器模塊能同時(shí)進(jìn)行讀出信息, 則屬于同時(shí)性。 高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器 從軟件運(yùn)行的角度看, 并行性從低到高可分為: (1) 指令內(nèi)部并行: 指令內(nèi)部的微操作之間的并行; (2) 指令級(jí)并行(Instruction Level Parallel, ILP): 并行執(zhí)行兩條或多條指令; (3) 任務(wù)級(jí)或過程級(jí)并行: 并行執(zhí)行兩個(gè)或多個(gè)過程或任務(wù)(程序段); (4) 作業(yè)或程序級(jí)并行: 多個(gè)作業(yè)或程序間的并行。 高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技

3、術(shù)和高端處理器 從處理數(shù)據(jù)的角度, 并行性從低到高可以分為: (1) 字串位串: 同時(shí)只對(duì)一個(gè)字的一位進(jìn)行處理; (2) 字串位并: 同時(shí)對(duì)一個(gè)字的全部位進(jìn)行處理; (3) 字并位串: 同時(shí)對(duì)多字的同一位進(jìn)行處理; (4) 全并行: 同時(shí)對(duì)多字的全部或部分位進(jìn)行處理。 在一個(gè)計(jì)算機(jī)系統(tǒng)中, 可以采取多種并行性措施?？梢杂袌?zhí)行程序方面的并行性, 又可以有數(shù)據(jù)處理方面的并行性。當(dāng)并行性提高到一定級(jí)別則認(rèn)為進(jìn)入并行處理領(lǐng)域。例如, 執(zhí)行程序的并行性達(dá)到任務(wù)或過程級(jí), 或者處理數(shù)據(jù)的并行性達(dá)到字并位串一級(jí), 即可認(rèn)為進(jìn)入并行處理領(lǐng)域。 高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器提高并行性的三種技術(shù)

4、途徑: (1) 時(shí)間重疊: 即多個(gè)處理過程在時(shí)間上相互錯(cuò)開, 輪流重疊使用同一硬件設(shè)備的不同部分, 以加快硬件周轉(zhuǎn)。原則上不要求重復(fù)的硬件設(shè)備。(2) 資源重復(fù): 根據(jù)“以數(shù)量取勝”的原則, 通過重復(fù)設(shè)置資源(尤其是硬件資源), 大幅度提高計(jì)算機(jī)系統(tǒng)的性能。如多處理器系統(tǒng)是資源重復(fù)的典型情況。 (3) 資源共享: 這是一種軟件方法, 它使多個(gè)任務(wù)按一定時(shí)間順序輪流使用同一套硬件設(shè)備。例如分時(shí)系統(tǒng)就是遵循資源共享這一思想產(chǎn)生的 。 高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器系統(tǒng)設(shè)計(jì)的定量原理:只加速使用頻率高的部件:這是最重要和最廣泛的設(shè)計(jì)準(zhǔn)則。

5、因?yàn)轭l繁使用的部件對(duì)系統(tǒng)性能的影響大, 反之影響則小。阿姆達(dá)爾(Amdahl)定律:阿姆達(dá)爾定律是最基本的定量分析原則, 指系統(tǒng)中對(duì)某一部件采用某種更快的執(zhí)行方式后, 所能獲得的系統(tǒng)性能的改進(jìn)程度, 取決于這種執(zhí)行方式被使用的頻率, 或所占總時(shí)間比例。所以可以認(rèn)為, 阿姆達(dá)爾定律實(shí)際上定義了采取增強(qiáng)(加速)某部分功能處理后, 可獲得的性能改進(jìn)或執(zhí)行時(shí)間的加速比。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器假設(shè): To: 表示不采用任何增強(qiáng)功能措施完成某一任務(wù)時(shí)間; Te: 表示采取某種增強(qiáng)功能措施完成同一任務(wù)所需時(shí)間;fe: 表示可采用增強(qiáng)功能措施部分所占百分比; re: 表示采取增強(qiáng)功能措

6、施比不采取增強(qiáng)功能措施可加快執(zhí)行的倍數(shù);則性能加速比為:Sp =(未采用改進(jìn)措施前執(zhí)行某任務(wù)時(shí)間)(采用改進(jìn)措施后執(zhí)行某任務(wù)的時(shí)間) =Te To=(1 fe) +re fe1高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器Sp=(1 fe) +re fe1例1: 假設(shè)將某系統(tǒng)的某一部件的處理速度加快到10倍, 但該部件的原處理時(shí)間僅為整個(gè)運(yùn)行時(shí)間的40%, 則采用加快措施后能使整個(gè)系統(tǒng)的性能提高多少?解: 由題意可知 fe=0.4, re=10, 根據(jù)阿姆達(dá)爾定律,Sp=(1 fe) +re fe1=(1 0.4) +10 0.41=1.56式中: (1fe)表示不可改進(jìn)部分, 當(dāng)fe為0時(shí)(

7、即沒有可改進(jìn)部分時(shí)), Sp為1(性能沒有提高); 當(dāng)re時(shí), 則Sp=1/(1fe), 即改進(jìn)部分比例越大, 加速比越高。因此性能提高幅度受改進(jìn)部分所占比例的限制。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器例2: 假設(shè)某程序中, 求浮點(diǎn)數(shù)平方根FPSQR操作占整個(gè)程序執(zhí)行時(shí)間的20%, 而所有浮點(diǎn)運(yùn)算指令操作占整個(gè)程序執(zhí)行的50%?，F(xiàn)用兩種措施提高計(jì)算機(jī)系統(tǒng)性能, 一種是采用FPSQR硬件, 可以使FPSQR操作的速度提高10倍; 另一種是使所有浮點(diǎn)指令的速度提高兩倍, 試比較兩種方案。解:在兩種方案下, re分別是10和2, fe分別是20和50, 使用加速比公式:SFPPSQR=(1

8、fe) +(fere)1=(10.2) +(0.210)11.22SFPP=(1fe) +(fere)11.33=(10.5) +(0.52)1采用“提高浮點(diǎn)指令的速度”比“FPSQR硬件”更好。第一節(jié) 流水線技術(shù)流水技術(shù)是指:高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器 將一個(gè)重復(fù)的時(shí)序過程分解成為若干個(gè)子過程, 而每個(gè)子過程都可以在其專用功能段上與其它子過程同時(shí)執(zhí)行。理論上講: 效率為一個(gè)工人的三倍。一、指令流水線(整數(shù)) 假設(shè): 將一條指令的整個(gè)過程分解為四個(gè)階段: 非流水線方式(假設(shè)各階段時(shí)間等長):處理器t存結(jié)果t取指令t指令譯碼t指令執(zhí)行t4t時(shí)間完成整條指令高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)

9、第三章并行技術(shù)和高端處理器完成n條指令需要n4t 時(shí)間。如果將處理器按照指令各階段的功能重新設(shè)計(jì):讓完成不同功能所涉及的硬件部分在邏輯上相互獨(dú)立, 讓不同邏輯功能部件在時(shí)間上并行工作, 從而使多條指令的不同階段的功能并行完成, 以提高指令執(zhí)行速度。如下圖所示:WBiEXi+1FEi+3DEi+2寫數(shù)邏輯取指邏輯譯碼邏輯執(zhí)行邏輯高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器例: 如以下幾條指令的執(zhí)行過程:寫數(shù)邏輯取指邏輯譯碼邏輯執(zhí)行邏輯 FE1指令1WB4EX5DE6WB5EX6WB6DE1 FE2指令2EX1DE2 FE3指令3WB1EX2DE3 FE4指令4WB2EX3DE4 FE5指令5W

10、B3EX4DE5 FE6指令6注: 該圖不反映流水線時(shí)間重疊關(guān)系, 只反映指令在不同階段的功能在什么部件上完成。將該圖按執(zhí)行的時(shí)間順序改寫為(如下圖):高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器 FE指令1DEEXWB FE指令2DEEXWB FE指令3DEEXWB指令4 FEDEEXWB指令5 FEDEEXWB指令6 FEDEEXWB4t時(shí)完成第1條指令tt2t7t5t3t6t4t9t8t19t時(shí)完成第6條指令高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器二、浮點(diǎn)加法流水線 浮點(diǎn)加法的全過程為求階差、對(duì)階、尾數(shù)相加、規(guī)格化四個(gè)子過程, 分別用不同的部件來實(shí)現(xiàn)。 采用流水線以后, 雖然每個(gè)

11、加法操作的總時(shí)間仍然是4t , 但在加法器的輸出端, 卻是每隔一個(gè)t就輸出一個(gè)加法結(jié)果。 高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器求階差對(duì)階尾數(shù)相加規(guī)格化求階差對(duì)階尾數(shù)相加規(guī)格化求階差對(duì)階尾數(shù)相加.求階差對(duì)階.三、流水線性能指標(biāo)(1) 流水線吞吐率TP (也稱流水線排空時(shí)間)是指在單位時(shí)間內(nèi), 流水線所完成的任務(wù)數(shù)量或者輸出結(jié)果的數(shù)量。TP = Tkn其中: n為任務(wù)數(shù)量, Tk是處理完n個(gè)任務(wù)所用的時(shí)間。上述計(jì)算吞吐率的基本公式可根據(jù)流水線的具體設(shè)計(jì)可進(jìn)一步細(xì)分下述兩種情況:高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器針對(duì)指令流水線, 則為指令數(shù)量 各時(shí)間段均等的流水線假設(shè)一個(gè)時(shí)間段

12、均等(t)的流水線, 級(jí)數(shù)為k , 第一條指令輸入后, 經(jīng)過kt的時(shí)間完成, 此后的每一個(gè)t完成一條指令, 這樣, 流水線完成n條指令所需時(shí)間為: Tk = kt + (n1) t代入基本公式:TP = Tkn=kt + (n1) tn最大吞吐率:TPmax = limnkt + (n1) tn=t1高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器(排空時(shí)間) 各段時(shí)間不完全相等的流水線一般情況下, 不同的指令以及指令的不同階段所需時(shí)間可能都會(huì)有差異, 因此可以按實(shí)際所需時(shí)間分配每一級(jí)的時(shí)間長度。比如: 假設(shè)流水線采用5級(jí)流水深度, 每一級(jí)按以下分配時(shí)間長度:15432t2t3ttt 但存在控制

13、很復(fù)雜、時(shí)間瓶頸使部分功能部件利用率較低的缺陷。第2級(jí)部件需等待第3級(jí)部件2t的時(shí)間之后才能將操作交給第3級(jí)部件; 即: t1=t , t2=t , t3=3t , t4=2t , t5=t高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器指令1指令2指令3等待時(shí)間, 稱為 流水線阻塞 流水線執(zhí)行情況:1 2 3 3 3 4 4 51 2 3 3 3 4 4 51 2 3 3 3 4 4 5指令41 2 3 3 3 4 4 5tt8t11t14t17t從第2條指令開始, 每3t完成1條指令, 因此有:TP = Tkn=+ (n1) Max(t1 , t2 , tk) ntiki=1高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)

14、構(gòu) 第三章并行技術(shù)和高端處理器(2) 流水線加速比TP=Max(t1 , t2 , tk)1最大吞吐率:如上例中, 最大吞吐率:TP=3t1流水線加速比定義: 按順序方式執(zhí)行一批指令所用的時(shí)間與按流水線方式執(zhí)行同一批指令所用時(shí)間之比。加速比:S =TkTs順序方式執(zhí)行所用時(shí)間流水線方式執(zhí)行所用時(shí)間高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器假設(shè)流水線各段時(shí)間均等為t , 則一條k段流水線完成n條指令所需時(shí)間為: Tk =(k+n1) t。假設(shè)按順序執(zhí)行n條指令, 則完成n條指令所需時(shí)間為: Ts = nkt 。因此有加速比:S =nk k+n1 最大加速比:Smax =nk k+n1 lim

15、n=k即當(dāng)nk時(shí),流水線加速比等于流水線段數(shù), 因此理論上流水線段數(shù)越多越好, 但在設(shè)計(jì)上會(huì)帶來許多問題。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器(3) 流水線效率流水線效率是指: 流水線中的功能部件的利用率, 其值為流水線功能部件的實(shí)際使用時(shí)間與整個(gè)運(yùn)行時(shí)間之比。假設(shè)流水線級(jí)數(shù)為k , 各級(jí)時(shí)間相等(t), 完成n條指令總時(shí)間為Tk , 則每一級(jí)的效率為(理想情況):E =由于各級(jí)相同, 則整條流水線利用率:ei =ntTk= (k+n1) tnt= (k+n1)n (k+n1)n當(dāng)nk 時(shí), E趨于1。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器例. 一個(gè)四級(jí)流水線(各級(jí)等長),

16、僅執(zhí)行完一條指令時(shí):E = (k+n1)n= (4+11)1=41即: 由于僅執(zhí)行完一條指令, 流水線四段中, 在任何一個(gè)t時(shí)間內(nèi), 都只有一個(gè)段被使用, 其余三個(gè)段為空閑, 因此利用率只有四分之一。再假設(shè)執(zhí)行完三條指令, 且流水線無阻塞:E = (k+n1)n= (4+31)3=21流水線情況:高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器 FE指令1DEEXWB FE指令2DEEXWB FE指令3DEEXWBtt2t5t3t6t4t1在流水線執(zhí)行過程中, 各段空閑情況:取指部件: 空閑t4、 t5、 t6譯碼部件: 空閑t1、 t5、 t6執(zhí)行部件: 空閑t1、 t2、 t6寫數(shù)部件: 空

17、閑t1、 t2、 t3即在整個(gè)6t的時(shí)間, 任何一個(gè)部件都存在3t的空閑, 利用率1/2。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器如果各級(jí)的效率不完全相等, 則流水線效率為:E = ntiki=1K tiki=1+(n1)max(t1 , t2. tk)高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器上述計(jì)算公式都是流水線在理想情況的計(jì)算方法, 在實(shí)際情況, 流水線可能存在阻塞, 不能按理想狀態(tài)實(shí)現(xiàn)流水執(zhí)行。 非理想狀況下流水線效率分析:假設(shè)一段程序由n條指令構(gòu)成的, 分為K級(jí)流水, 用tij表示第i條指令的第j階段所需時(shí)間。(1) 如果采用順序執(zhí)行, 則有:第1條指令完成時(shí)間: t11

18、+ t12 + t13. + t1K第2條指令完成時(shí)間: t21 + t22 + t23. + t3K第3條指令完成時(shí)間: t31 + t32 + t33. + t3K第n條指令完成時(shí)間: tn1 + tn2 + tn3. +tnK順序完成該程序所需時(shí)間為上述所有tij的累加:TS = i=1nj=1ktij高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器第1個(gè)部件使用時(shí)間: t11+t21+t31+ tn1第2個(gè)部件使用時(shí)間: t12+t22+t32+tn2第3個(gè)部件使用時(shí)間: t13+ t23+ t33+tn3第K個(gè)部件使用時(shí)間: t1K+t2K+t3K+tnK所有K個(gè)部件的平均使用時(shí)間為:

19、(t11+t21+tn1) +(t12+t22+tn2) + +(t1K +t2K+tnK)K=TSK(2) 如果按流水線方式執(zhí)行, 則有:假設(shè)完成的總時(shí)間為TK , 所謂效率則是流水線部件被實(shí)際使用的時(shí)間占總時(shí)間的比例。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器所有部件的平均使用時(shí)間除以該程序完成的總時(shí)間(Tk)則為利用率, 即:TS為順序方式執(zhí)行所用時(shí)間;Tk為流水線方式執(zhí)行所用時(shí)間。上式即為一種簡單實(shí)際的流水線效率計(jì)算方法。E =TSTkk Tkk=TS高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器四、流水線的相關(guān)與沖突1、流水線相關(guān)相關(guān)是指兩條指令之間存在某種依賴關(guān)系。一般來說,

20、指令之間的依賴性越少, 流水線各級(jí)的并行性越高, 流水線效率也越高。反之, 依賴性越多, 流水線各級(jí)的并行性越低, 流水線效率也越低。有三種類型的相關(guān):數(shù)據(jù)相關(guān)(真數(shù)據(jù)相關(guān))、名相關(guān)、控制相關(guān)高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器(1) 數(shù)據(jù)相關(guān)假設(shè)兩條指令I(lǐng)nsi和Insj (Insi在Insj之前) , 如果有下列情形之一, 則稱指令I(lǐng)nsi和Insj數(shù)據(jù)相關(guān): Insj使用 Insi產(chǎn)生的結(jié)果 Insj與 Insk數(shù)據(jù)相關(guān), 而Insk又與Insi數(shù)據(jù)相關(guān)后者表明數(shù)據(jù)相關(guān)具有傳遞性。如下程序段存在數(shù)據(jù)相關(guān):MOV Ri , 8MOV Rj , RiADD Rk , Rj由此可知,

21、 數(shù)據(jù)相關(guān)會(huì)引發(fā)流水線阻塞。第二條指令使用第一條指令產(chǎn)生的結(jié)果, 第三條指令使用第二條指令產(chǎn)生的結(jié)果。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器(2) 名相關(guān)名相關(guān)是指: 如果兩條指令使用了相同的寄存器或者存儲(chǔ)單元, 但他們之間沒有數(shù)據(jù)流動(dòng), 則稱這兩條指令名相關(guān)。 由于兩條指令僅僅是使用了相同的名字而沒有數(shù)據(jù)傳輸, 所以只需通過改變指令中操作數(shù)的名稱即可消除名相關(guān)(可通過編譯或硬件實(shí)現(xiàn))。(3) 控制相關(guān)控制相關(guān)是由分支指令引起的, 程序流向需根據(jù)分支指令執(zhí)行的結(jié)果來確定?？刂葡嚓P(guān)可引起流水線阻塞, 是流水線中要解決的重要問題。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器由于相關(guān)的存在

22、, 可能引發(fā)流水線沖突而導(dǎo)致流水線阻塞。2、流水線沖突(1) 數(shù)據(jù)沖突:(2) 控制沖突:(3) 結(jié)構(gòu)沖突:一條指令執(zhí)行過程中, 需要前面的指令的執(zhí)行結(jié)果。分支指令未執(zhí)行完成, 導(dǎo)致流水線不能正常往下執(zhí)行。硬件資源滿足不了指令重疊執(zhí)行的要求, 而可能引發(fā)流水線阻塞。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器五、分支預(yù)測(cè)技術(shù)主要討論硬件動(dòng)態(tài)地進(jìn)行分支處理, 即在程序運(yùn)行過程中, 根據(jù)分支指令過去的表現(xiàn)來預(yù)測(cè)其將來的行為。采用動(dòng)態(tài)分支預(yù)測(cè)應(yīng)實(shí)現(xiàn)兩個(gè)目的: 判斷預(yù)測(cè)是否成功 盡快找到分支目標(biāo)地址, 以避免流水線阻塞如何記錄分支的歷史信息, 要記錄哪些信息?(2) 如何根據(jù)這些信息來預(yù)測(cè)分支的方向

23、, 甚至提前取出分支目標(biāo)指令?為此, 需解決以下兩個(gè)問題:高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器此外, 在分支預(yù)測(cè)錯(cuò)誤時(shí), 要作廢已經(jīng)預(yù)取和分析的指令, 恢復(fù)現(xiàn)場, 并從另一路分支重新取指令。如下圖所示:i1ii+1i+2p+1p+2分支指令預(yù)測(cè)執(zhí)行路徑實(shí)際執(zhí)行路徑顯然, 為了能恢復(fù)現(xiàn)場, 需要在執(zhí)行預(yù)測(cè)目標(biāo)指令之前將現(xiàn)場保存起來。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器1、分支歷史表BHT采用Branch History Table(BHT)來記錄分支指令的歷史, 并按該歷史情況來進(jìn)行預(yù)測(cè)。所謂“歷史”是指最近一次或幾次的執(zhí)行是成功還是失敗。如果只記錄最近一次的歷史, 則BHT

24、 中只需要1個(gè)二進(jìn)制位(最簡單的一種方式)。為提高預(yù)測(cè)精度, 常采用兩位二進(jìn)制來記錄歷史,實(shí)際測(cè)試表明, 采用更多的位與采用兩位的預(yù)測(cè)精度差異不大。 兩位分支預(yù)測(cè)的狀態(tài)轉(zhuǎn)換圖如下:高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器00011011分支不成功分支成功分支不成功分支成功分支不成功分支成功分支不成功分支成功分支預(yù)測(cè)不成功分支預(yù)測(cè)成功在00和01狀態(tài)下, 預(yù)測(cè)不成功, 在10和11狀態(tài)下, 預(yù)測(cè)成功。 線條邊的文字說明是指分支指令的實(shí)際執(zhí)行情況。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器兩位預(yù)測(cè)操作有兩步: 分支預(yù)測(cè); 修改狀態(tài)當(dāng)分支指令到達(dá)譯碼階段時(shí), 根據(jù)從BHT中讀出的信息進(jìn)行預(yù)

25、測(cè):(1) 從BHT中讀出的數(shù)據(jù)為“00”或“01”, 按“分支不成功”處理, 繼續(xù)處理分支指令的下一條指令。當(dāng)分支指令的實(shí)際執(zhí)行結(jié)果出來后, 如果發(fā)現(xiàn)預(yù)測(cè)正確, 繼續(xù)執(zhí)行指令, 否則, 作廢已經(jīng)預(yù)取的和分析的指令, 恢復(fù)現(xiàn)場, 并從分支路徑重新取指令執(zhí)行。 對(duì)狀態(tài)的修改操作是: 在原狀態(tài)為“00”情況下, 如果預(yù)測(cè)不正確, 則將狀態(tài)改為“01”; 否則, 就是預(yù)測(cè)正確, 狀態(tài)不變；若原狀態(tài)為“01”, 如果預(yù)測(cè)不正確, 則將狀態(tài)改為“11”; 否則, 就是預(yù)測(cè)正確, 則將狀態(tài)改為“00” 。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器(2) 從BHT中讀出的數(shù)據(jù)為“10”或“11”, 按“

26、分支成功”處理處理, 即從成功分支路取指令進(jìn)行處理。待分支指令的實(shí)際執(zhí)行結(jié)果出來后, 如果發(fā)現(xiàn)預(yù)測(cè)正確, 繼續(xù)執(zhí)行指令, 否則, 作廢已經(jīng)預(yù)取的和分析的指令, 恢復(fù)現(xiàn)場, 并從分支路徑重新取指令執(zhí)行。 對(duì)狀態(tài)的修改操作是:若原狀態(tài)為“11”, 如果預(yù)測(cè)不正確, 則將狀態(tài)改為“10”; 否則, 就是預(yù)測(cè)正確, 狀態(tài)不變; 若原狀態(tài)為“10”, 如果預(yù)測(cè)不正確, 則將狀態(tài)改為“00”; 否則, 就是預(yù)測(cè)正確, 則將狀態(tài)改為“11” 。BHT可以放在指令高速緩存中, 也可以用專門的硬件來實(shí)現(xiàn)。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器BHT僅僅是預(yù)測(cè)分支是否成功, 而對(duì)分支目標(biāo)地址不提供支持,

27、還需要另外的時(shí)間來計(jì)算目標(biāo)地址, 因此, 如果確定分支目標(biāo)地址的時(shí)間比較長時(shí)(大于或遠(yuǎn)大于預(yù)測(cè)時(shí)間), BHT方法就沒有什么意義。2、采用分支目標(biāo)緩沖器BTBBTB是一個(gè)由硬件實(shí)現(xiàn)的專用表格。表格中每一項(xiàng)至少由兩個(gè)字段構(gòu)成: 已執(zhí)行過的成功分支指令的地址 預(yù)測(cè)的分支目標(biāo)地址高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器在每次取指令的同時(shí), 用該指令的地址與BTB中的所有項(xiàng)目的第一個(gè)字段進(jìn)行比較, 如果有匹配的, 意味著該指令是分支指令并且上一次執(zhí)行分支是成功的, 據(jù)此預(yù)測(cè)本次執(zhí)行也將分支成功, 分支地址由該項(xiàng)的第二個(gè)字段給出;如果沒有匹配的, 就把當(dāng)前指令當(dāng)作普通指令(不是分支指令)來執(zhí)行。如

28、下圖所示:高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器當(dāng)前取指令的地址成功的分支指令地址 分支目標(biāo)地址 A0P0A1P1.Ak-1Pk-1查找有匹配該指令為成功分支指令, 用預(yù)測(cè)的分支目標(biāo)地址作為下一條指令的PC值有無本指令不是分支指令, 按普通指令執(zhí)行高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器由于BTB中存放的是執(zhí)行過的成功分支指令的地址, 所以如果當(dāng)前指令的地址與BTB中的第一個(gè)字段匹配, 那么就將該匹配項(xiàng)中第二個(gè)字段中的地址送往PC, 從分支目標(biāo)處開始取指令。如果預(yù)測(cè)正確, 則不會(huì)產(chǎn)生任何分支延遲; 如果預(yù)測(cè)錯(cuò)誤, 或者在BTB中沒有匹配的項(xiàng), 則至少有兩個(gè)時(shí)鐘周期的延遲開銷 (更

29、新BTB中的項(xiàng), 在更新期間停止取指令)。 采用BTB時(shí)所進(jìn)行的處理步驟:高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器當(dāng)前PC值送存儲(chǔ)器和BTBBTB中有匹配的項(xiàng)成功分支指令正常執(zhí)行指令(無延遲)將其PC值和分支目標(biāo)地址寫入BTB作為一個(gè)新的項(xiàng)(有延遲) 否是以BTB的第二個(gè)字段作為分支目標(biāo)地址送PC當(dāng)前分支成功否是否分支預(yù)測(cè)錯(cuò)誤, 清除已取指令, 從另一分支取指令, 從BTB中刪除相應(yīng)項(xiàng) (有延遲) 是分支預(yù)測(cè)正確, 繼續(xù)執(zhí)行后續(xù)(無延遲) BTB的另一種形式是在分支目標(biāo)緩沖器中增加一個(gè)“分支歷史表”(也稱“轉(zhuǎn)移歷史表”) 字段, 存放過去所有執(zhí)行過的分支指令的轉(zhuǎn)移情況(無論轉(zhuǎn)移成功與否)

30、, 該字段用于轉(zhuǎn)移預(yù)測(cè)(功能類似于簽前述的BHT)。當(dāng)前預(yù)取的指令分支指令地址 分支歷史表 分支目標(biāo)地址 A0 T0 P0 A1 T1 P1 Ak1 Tk1 Pk1.查找該方法實(shí)際上是BTB 與BHT相結(jié)合高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器第二節(jié) 向量處理技術(shù)向量處理機(jī):a1a2aN.A=b1b2bN.B=c1c2cN.C=d1d2dN.D=可以有如下幾種處理方式:具有向量數(shù)據(jù)表示和向量指令的流水線處理機(jī)。 例: 考慮以下向量計(jì)算: D = A(B + C) 其中A、B、C、D是長度為 N 的向量。高級(jí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第三章并行技術(shù)和高端處理器1. 水平(橫向)處理方式水平處理方式即逐個(gè)求di: 先計(jì)算 d1 = a1(b1 + c1); 再計(jì)算 d2 = a2 (b2 + c2); , 最后計(jì)算 dN = aN(bN + cN)。一般的計(jì)算機(jī)采用該方式, 組成循環(huán)程序處理。在每次循環(huán)中, 至少要用到如下幾條機(jī)器指令:a1a2aN.b1b2bN