[精品]流水和現(xiàn)代器技術(shù)

1、第五章 重疊、流水和現(xiàn)代處理器技術(shù)北京航空航天大學(xué)計(jì)算機(jī)學(xué)院2005 年 4 月主要內(nèi)容：基本問題流水線技術(shù)向量流水技術(shù)現(xiàn)代處理器技術(shù) 如何提高cpu執(zhí)行效率？ tcpu =in * cpi * tc in ： 執(zhí)行程序中的指令總數(shù)；cpi ：執(zhí)行每條指令所需的平均時(shí)鐘周期數(shù)；tc ： 時(shí)鐘周期的時(shí)間長(zhǎng)度。程序中指令總數(shù)時(shí)鐘周期執(zhí)行整個(gè)程序所需cpucpi nniiiiicpi1)*( 其中：ii 表示第i種指令在程序中執(zhí)行次數(shù),cpii表示執(zhí)行一條第i類指令所需的平均時(shí)鐘周期數(shù), in 為程序中所有的指令類數(shù). 順序執(zhí)行方式 一條指令的執(zhí)行過程：取指令取指令-分析分析-執(zhí)行執(zhí)行 執(zhí)行n條指令

2、所用的時(shí)間為： 如每段時(shí)間都為t，則執(zhí)行n條指令所用的時(shí)間為：t=3nt 主要優(yōu)點(diǎn)：控制簡(jiǎn)單，節(jié)省設(shè)備。 主要缺點(diǎn)：執(zhí)行指令的速度慢，功能部件的利用率很低。niiiitttt1(）執(zhí)行分析取指令取指令k 分析k 執(zhí)行k 取指令k+1 分析k+1執(zhí)行k+1指令執(zhí)行方式分析指令執(zhí)行方式分析 此時(shí)，執(zhí)行n條指令的時(shí)間為：t=(2+2n)t主要優(yōu)點(diǎn)：指令的執(zhí)行時(shí)間縮短功能部件的利用率明顯提高主要缺點(diǎn)：需要增加一些硬件控制過程稍復(fù)雜取指 分析 執(zhí)行取指 分析 執(zhí)行取指 分析 執(zhí)行一次重疊執(zhí)行方式一次重疊執(zhí)行方式(一種最簡(jiǎn)單的流水線方式一種最簡(jiǎn)單的流水線方式)二次重疊執(zhí)行方式二次重疊執(zhí)行方式把取第把取第k

3、+1條指令提前到分析第條指令提前到分析第k條指令同時(shí)執(zhí)行條指令同時(shí)執(zhí)行 如果三個(gè)過程的時(shí)間相等，執(zhí)行n條指令的時(shí)間為：t=(2+n)t 理想情況下同時(shí)有三條指令在執(zhí)行 處理機(jī)的結(jié)構(gòu)要作比較大的改變（必須采用先行控制方式）取指k+2 分析k+2 執(zhí)行k+2取指k+1 分析k+1 執(zhí)行k+1取指k分析k執(zhí)行k主要內(nèi)容：基本問題流水線技術(shù)向量流水技術(shù)現(xiàn)代處理器技術(shù) 包含以下內(nèi)容：流水線的分類流水線的分類流水線的表示方法流水線的表示方法流水線的特點(diǎn)流水線的特點(diǎn)流水線的性能分析流水線的性能分析非線性流水線技術(shù)非線性流水線技術(shù) 從流水線具有功能多少來看，可以分為單功能流水線和多功能流水線。只能實(shí)現(xiàn)一種功能

4、的流水處理。取指令譯碼執(zhí)行保存結(jié)果t1t2t3t4是指同一流水線的各段之間可以通過不同的連接方式實(shí)現(xiàn)多種不同的運(yùn)算或功能。輸入減階對(duì)階移位相加規(guī)格化相乘累加輸出12345678輸入減階對(duì)階移位相加規(guī)格化輸出123458輸入相乘累加輸出1678流水功能段流水功能段浮點(diǎn)加、減法運(yùn)算浮點(diǎn)加、減法運(yùn)算定點(diǎn)乘法運(yùn)算定點(diǎn)乘法運(yùn)算 按多功能流水線的各段能否允許同時(shí)用多種不同功能連接流水，可把流水線分為靜態(tài)流水線和動(dòng)態(tài)流水線。 靜態(tài)流水線在某一時(shí)間內(nèi)各段只能按一種功能連接流水。 動(dòng)態(tài)流水線的各段在同一時(shí)間內(nèi)可按不同運(yùn)算或功能連接。 可同時(shí)進(jìn)行浮點(diǎn)加、減運(yùn)算和定點(diǎn)乘法運(yùn)算的流水線輸入減階對(duì)階移位相加規(guī)格化相乘累

5、加輸出12345678 從流水線中各功能段之間是否有反饋回路，可以把流水線分為線性流水線和非線性流水線。s1s2s3s4輸出輸入反饋線 流水線的表示法有三種：連接圖、時(shí)空?qǐng)D、預(yù)約表。主要考慮前二種。 流水線的每一個(gè)階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級(jí)、流水節(jié)拍等。 一個(gè)流水階段與另一個(gè)流水階段相連形成流水線。指令從流水線一端進(jìn)入，經(jīng)過流水線的處理，從另一端流出。 有些復(fù)雜指令 在執(zhí)行階段也采用流水線方式工作，稱為操作流水線。取指令譯碼執(zhí)行保存結(jié)果t1t2t3t4 一般4至12個(gè)流水段，等于及大于8個(gè)流水段的稱為超流水線處理機(jī)。取指形成操作數(shù)地址譯碼取操作數(shù)執(zhí)

6、行保存結(jié)果采用“時(shí)空?qǐng)D”表示流水線的工作過程。一條簡(jiǎn)單流水線的時(shí)空?qǐng)D：分析k分析k+1 分析k+2 分析k+3執(zhí)行k執(zhí)行k+1 執(zhí)行k+2 執(zhí)行k+3時(shí)間空間0t1t2t3t4t5 一個(gè)浮點(diǎn)加法器流水線的時(shí)空?qǐng)D(由求階差、對(duì)階、尾數(shù)加和規(guī)格化4個(gè)流水段組成)：ed1時(shí)間空間0t1t2t3t4t5ed2 ed3 ed4 ed5ea1 ea2 ea3 ea4 ea5ma1 ma2 ma3 ma4 ma5nl1 nl2 nl3 nl4 nl5t6t7t8nl：規(guī)格化ma：尾數(shù)加ea：對(duì)階ed：求階差 在流水線的每一個(gè)功能部件的后面都要有一個(gè)緩沖器，稱為鎖存器、閘門寄存器等，它的作用是保存本流水段的執(zhí)

7、行結(jié)果。 各流水段的時(shí)間應(yīng)盡量相等，否則回引起阻塞、斷流等。 只有連續(xù)提供同類任務(wù)才能充分發(fā)揮流水線的效率。 在流水線的每一個(gè)流水線段中都要設(shè)置一個(gè)流水鎖存器。 流水線需要有“裝入時(shí)間”和“排空時(shí)間”。只有只有流水線完全充滿時(shí)，整個(gè)流水線的效率才能得到充流水線完全充滿時(shí)，整個(gè)流水線的效率才能得到充分發(fā)揮。分發(fā)揮。 衡量流水線性能的主要指標(biāo)有：吞吐率、加速比和效率 求流水線吞吐率的最基本公式： n為任務(wù)數(shù), tk為完成n個(gè)任務(wù)所用時(shí)間 各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下完成n個(gè)連續(xù)任務(wù)需要的總時(shí)間為： k為流水線的段數(shù)， t為時(shí)鐘周期1時(shí)間空間s123 n-1 ns2s3s4123 n-1 n

8、123 n-1 n123 n-1 nkt(n-1) tnt(k-1)tt吞吐率：最大吞吐率為： 各段執(zhí)行時(shí)間不相等、輸入連續(xù)任務(wù)情況下：吞吐率為： 最大吞吐率為：tnkntp) 1(ntplimnknttmax() 11),max() 1(211kkiitttntntp ),max(121maxkttttp 流水線各段執(zhí)行時(shí)間不相等的解決辦法s1輸入t1=ts2t2=3ts3t3=ts4t4=t輸出1時(shí)間空間s1s2s3s4sti(n-1)t2tk23n123n123n123n一是將“瓶頸”流水段細(xì)分(如果可分的話)：二是將 “瓶頸”流水段重復(fù)設(shè)置：s1輸入輸出ts2-1ts2-2ts2-3t

9、s3ts4ts2(3t)s1輸入輸出t1=ts2-1s2-1s2-1s3s4t3=tt4=tt2=3t流水段重復(fù)設(shè)置的流水線1時(shí)間空間2 3ns1s2-14 5 614-2 -1n-225n-136n1 2 3n4 5 6-2 -11 2 3n4 5 6-2 -1s2-2s2-3s3s4 計(jì)算流水線加速比的基本公式：s = 順序執(zhí)行時(shí)間t0 / 流水線執(zhí)行時(shí)間tk 各段執(zhí)行時(shí)間相等，輸入連續(xù)任務(wù)情況下加速比為： 最大加速比為： 各段執(zhí)行時(shí)間不等，輸入連續(xù)任務(wù)情況下實(shí)際加速比為：1) 1(nknktnktnksslimk nknknmax1k=6k=10任務(wù)個(gè)數(shù)加速比10246811 248 1

10、6 32 64 128snttntttiikiikk 11121() max(,）計(jì)算流水線效率的一般公式：各流水段執(zhí)行時(shí)間相等，輸入n個(gè)連續(xù)任務(wù)流水線的效率為： 流水線的最高效率為：ktktkne0個(gè)流水段的總的時(shí)空區(qū)個(gè)任務(wù)占用的時(shí)空區(qū)1) 1(nkntnkktnke11maxnknlimen1時(shí)間空間s123 n-1 ns2s3s4123 n-1 n123 n-1 n123 n-1 nkt(n-1) tnt(k-1)tt 各流水段執(zhí)行時(shí)間不等，輸入n個(gè)連續(xù)任務(wù)流水線的效率為：),max() 12111kkiikiitttntktne （s1輸入t1=ts2t2=3ts3t3=ts4t4=t

11、輸出1時(shí)間空間s1s2s3s4sti(n-1)t2tk23n123n123n123n流水線的吞吐率、加速比與效率的關(guān)系： 因?yàn)?因此：e=tp t ，s=ketnkntp) 1(1nknks1nkne 對(duì)于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過上面給出的公式很容易計(jì)算出流水線的吞吐率、加速比和效率。例5.2：用一條4段浮點(diǎn)加法器流水線求8個(gè)浮點(diǎn)數(shù)的和：zabcdefgh解：z = (a+b) + (c+d) + (e+f) + (g+h)1時(shí)間空間2 3求階差45671 2 3 45671 2 3 45671 2 3 4567對(duì)階尾數(shù)加規(guī)格化加數(shù) a c e ga+be+fb d f hc

12、+dg+ha+b+c+de+f+g+h結(jié)果a+bc+de+fg+ha+b+c+de+f+g+hz z 7個(gè)浮點(diǎn)加法共用了15個(gè)時(shí)鐘周期。流水線的吞吐率為：流水線的加速比為：流水線的效率為：tttntpk147015787115740ttttsk470154740tttktek什么是非線性流水線？什么是非線性流水線？ 如果存在反饋回路，當(dāng)一個(gè)任務(wù)在流水線中流過時(shí)，在同一個(gè)流水段中可能要經(jīng)過多次。不能每一個(gè)時(shí)鐘周期向流水線輸入一個(gè)新任務(wù)。這樣的流水線就是非線性流水線。 非線性流水線的調(diào)度問題就是要解決要隔多少個(gè)時(shí)鐘周期向流水線輸入一個(gè)新任務(wù)才能使流水線 的各個(gè)流水段都不發(fā)生沖突。 表示一個(gè)非線性流

13、水線需要用到連接圖和預(yù)約表。s1s2s3s4輸出輸入反饋線 時(shí)間流水段1234567s1xxxs2xs3xxs4x非線性流水線1的連接圖非線性流水線的預(yù)約表s1s2s3s4輸出輸入反饋線 時(shí)間流水段1234567s1xxxs2xxs3xxs4x非線性流水線2的連接圖非線性流水線的預(yù)約表 預(yù)約表橫坐標(biāo)表示流水線的時(shí)鐘周期，縱坐標(biāo)表示流水線的各個(gè)流水段，中間有“x”表示該流水段在這一個(gè)時(shí)鐘周期處于工作狀態(tài)，空白表示該流水段在這一個(gè)時(shí)鐘周期不工作。 一行中可以有多個(gè)“x”，表示一個(gè)任務(wù)在不同時(shí)鐘周期重復(fù)使用了同一流水段；一列中有多個(gè)“x”表示在同一個(gè)時(shí)鐘周期同時(shí)占用了多個(gè)流水段。預(yù)約表的行數(shù)是流水線

14、的段數(shù)，預(yù)約表的列數(shù)是一個(gè)任務(wù)從進(jìn)入流水線到流水線中輸出所經(jīng)過的時(shí)鐘周期數(shù)。 向一條非線性流水線的輸入端連續(xù)輸入兩個(gè)任務(wù)之間的時(shí)間間隔稱為非線性流水線的啟動(dòng)距離，以時(shí)鐘周期數(shù)表示。 當(dāng)使用某些啟動(dòng)距離時(shí)，將在某些流水段發(fā)生沖突，即兩個(gè)或兩個(gè)以上任務(wù)同時(shí)爭(zhēng)用一個(gè)流水段。引起非線性流水線流水段沖突的啟動(dòng)距離稱為禁啟動(dòng)止距離。 不發(fā)生沖突的啟動(dòng)距離是一個(gè)循環(huán)數(shù)列。使非線性流水線的任何一個(gè)流水段在任何一個(gè)時(shí)鐘周期都不發(fā)生沖突的循環(huán)數(shù)列稱為非線性流水線的啟動(dòng)循環(huán)。x3x2x1s4x4x2x3x1x2x1s3x3x4x2x3x1x2x1s2x2x3x4x1x2x3x1x2x1s11110987654321

15、 時(shí)間流水段啟動(dòng)距離為3的流水線沖突情況兩個(gè)任務(wù)爭(zhēng)用一個(gè)流水段s1三個(gè)任務(wù)爭(zhēng)用一個(gè)流水段s1啟動(dòng)距離為5的流水線預(yù)約表x2x1x1s4x2x2x2x1s3x3x1x1s2x2x1x1x1s11110987654321 時(shí)間流水段x2x2啟動(dòng)周期重復(fù)啟動(dòng)周期（5）是一個(gè)循環(huán)，稱為恒定循環(huán)。時(shí)間流水段12345678910111213141516s1x1x2x1x2x1x2x3x4x3x4x3x4s2x1x2x1x2x3x4x3x4s3x1x2x1x2x3x4x3x4s4x1x2x3x4啟動(dòng)距離為（1，7）循環(huán)時(shí)的流水線預(yù)約表要正確地調(diào)度一條非線性流水線，首先要找出流水線的所有禁止啟動(dòng)距離。所有禁

16、止啟動(dòng)啟動(dòng)距離組合在一起成為一個(gè)數(shù)列，稱為禁止向量。 由預(yù)約表得到禁止向量的方法： 將預(yù)約表的每一行中任意兩個(gè)“x”之間的距離都計(jì)算出來，去掉重復(fù)的，這種數(shù)組成的一個(gè)數(shù)列就是這條非線性流水線的禁止向量。 例如：前述的非線性流水線，其禁止向量為（3，4，6）。 把一個(gè)啟動(dòng)循環(huán)內(nèi)的所有啟動(dòng)距離相加，然后再除以這個(gè)循環(huán)內(nèi)的啟動(dòng)距離個(gè)數(shù)，就得到這個(gè)啟動(dòng)循環(huán)的平均啟動(dòng)距離。 非線性流水線無沖突調(diào)度的主要目標(biāo)是要找出具有最小平均啟動(dòng)距離的啟動(dòng)循環(huán)，按照這樣的啟動(dòng)循環(huán)向非線性流水線的輸入端輸入任務(wù)，流水線的工作速度最快，而且所有流水段在任何時(shí)間都沒有沖突。 例子：一條有4個(gè)流水段的非線性流水線，每個(gè)流水段的

17、延遲時(shí)間都相等，它的預(yù)約表如下圖： 時(shí)間流水段1234567s1xxs2xxs3xxs4x（1）寫出流水線的禁止向量和初始沖突向量（2）畫出調(diào)度流水線的狀態(tài)圖（3）求流水線的最小啟動(dòng)循環(huán)和最小啟動(dòng)距離（4）求平均啟動(dòng)距離最小的恒定循環(huán)。解：（1）禁止向量為（2，4，6）沖突向量：用二進(jìn)制表示，長(zhǎng)度是禁止向量的最大距離。沖突向量c=（c6c5c4c3c2c1），由禁止向量，c2=c4=c6=1，其余位為0，沖突向量為 c=（101010）。（2）由沖突向量構(gòu)造一張圖：將c放到一個(gè)6位邏輯右移移位器，當(dāng)從移位器右移出0，用移位器中的值與初始沖突向量做“按位或”，得到一個(gè)新的沖突向量。當(dāng)移位器移出1

18、，不做任何處理。重復(fù)這個(gè)步驟。對(duì)產(chǎn)生的每一個(gè)新的沖突向量做同樣處理。在初始沖突向量和所有形成的沖突向量之間，箭頭連接。1010101111111011111010117*157*3537*當(dāng)右移2、4、6位，時(shí)移出位為1，表示用這些啟動(dòng)距離輸入新任務(wù)要發(fā)生沖突，不做任何處理。當(dāng)右移1、3、5和大于等于7位時(shí)，移出位是0，表示用這些啟動(dòng)距離輸入新任務(wù)不會(huì)發(fā)生沖突。7*表示大于等于75（3）從狀態(tài)圖中可以找到許多不發(fā)生流水段沖突的啟動(dòng)循環(huán)。，只要找到簡(jiǎn)單循環(huán)，進(jìn)而確定平均啟動(dòng)距離最小的啟動(dòng)循環(huán)。它們是： （1，7）、（3，5，7）、（5，7）等簡(jiǎn)單循環(huán)平均啟動(dòng)距離（1，7）4（3，5）4（5，7）

19、6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7最小啟動(dòng)循環(huán)是具有最小平均最小啟動(dòng)距離的啟動(dòng)循環(huán)。 最小循環(huán)為（1，7）、（3，5） 最小恒定循環(huán)為（5） 時(shí)間流水12345678910111213141516s1x1x2x1x3x2x4x3s2x1x2x1x2x3x4x3s3x1x1x2x2x3x3x4s4x1x2x3x4最小啟動(dòng)循環(huán)為（3，5）的流水線工作狀態(tài) 時(shí)間流水段123456789101112131415s1x1x2x1x2x3x4x3s2x1x2x1x2x3x4x3x4s3x1x2x1x2x3x4x3x4s4x1x2x3x4最小啟動(dòng)循環(huán)為（1，7）的流水線工作狀態(tài)

20、時(shí)間流水段123456789101112131415s1x1 x2x1 x3x2 s2x1 x1x2x2x3 s3x1 x1 x2x2 x3 x3s4x1 x2 x3恒定啟動(dòng)循環(huán)（5）的流水線工作狀態(tài)啟動(dòng)周期重復(fù)啟動(dòng)周期主要內(nèi)容：基本問題流水線技術(shù)向量流水技術(shù)現(xiàn)代處理器技術(shù)向量處理的特點(diǎn)向量處理機(jī)的基本結(jié)構(gòu)向量處理的方法向量處理的關(guān)鍵技術(shù)1、向量流水處理的主要特點(diǎn) (1) 各個(gè)元素的操作一般相同且數(shù)據(jù)相互獨(dú)立，不存在相關(guān)。非常適合于流水處理； (2) 一條向量指令相當(dāng)于一個(gè)標(biāo)量循環(huán),可降低對(duì)指令訪問帶寬的要求； (3) 一般采用多體交叉存儲(chǔ)，支持跨步長(zhǎng)度訪問 具有向量數(shù)據(jù)表示和向量指令系統(tǒng)的處

21、理機(jī)稱為向量處具有向量數(shù)據(jù)表示和向量指令系統(tǒng)的處理機(jī)稱為向量處理機(jī)。理機(jī)。q向量處理機(jī)是解決數(shù)值計(jì)算問題的一種高性能計(jì)算機(jī)結(jié)構(gòu)。q向量處理機(jī)一般都采用流水線結(jié)構(gòu)，往往有多條流水線并行 工作。q向量處理機(jī)通常屬大型或巨型機(jī)，也可以用微機(jī)加一臺(tái)向量 協(xié)處理器組成。q一般向量計(jì)算機(jī)中包括有一臺(tái)高性能標(biāo)量處理機(jī)。q必須把要解決的問題轉(zhuǎn)化為向量運(yùn)算，向量處理機(jī)才能充分 發(fā)揮作用。一個(gè)典型向量求解問題: y = a*x + y 其中x和y為向量, 初始值存放在存儲(chǔ)器中, a為標(biāo)量。通常, 根據(jù)這一求解表達(dá)式是單精度還是雙精度操作, 分別稱為saxpy(single-precision ax plus y)

22、或daxpy循環(huán), 表示是單精度或雙精度的a乘x后再加y。若用向量機(jī)來完成同樣操作, 則有: ld f0,a ;標(biāo)量a裝入f0 lv v1,rx ;裝入向量x, lv為向量取指令 multv v2,f0,v1 ;向量x與標(biāo)量a相乘 lv v3,ry ;裝入向量y addv v4,v2,v3 ;向量加ax+y sv ry,v4 ;存結(jié)果向量, sv為向量存指令 向量機(jī)只需執(zhí)行6條指令, 從而可大大降低對(duì)指令帶寬要求 向量處理機(jī)的基本結(jié)構(gòu)形式 按向量操作對(duì)象及結(jié)果主要存放方式分類： 1）存儲(chǔ)器存儲(chǔ)器工作方式向量機(jī) 利用多個(gè)獨(dú)立的存儲(chǔ)器模塊并行工作。 2）寄存器寄存器工作方式向量機(jī) 主要利用向量寄存

23、器。 采用多個(gè)存儲(chǔ)體交叉和并行訪問來提高存儲(chǔ)器速度； 操作數(shù)緩沖棧和寫結(jié)果緩沖棧主要用于解決訪問存儲(chǔ)器沖突 ； 主要優(yōu)缺點(diǎn)：硬件結(jié)構(gòu)簡(jiǎn)單，造價(jià)低。速度相對(duì)比較低。 早期的向量處理多采用這種存儲(chǔ)器-存儲(chǔ)器結(jié)構(gòu)。 主主存存儲(chǔ)儲(chǔ)器器操作數(shù)操作數(shù)緩沖棧緩沖棧流水線流水線運(yùn)算運(yùn)算部件部件寫結(jié)果寫結(jié)果緩沖棧緩沖棧 把存儲(chǔ)器-存儲(chǔ)器結(jié)構(gòu)中的緩沖棧改為向量寄存器，運(yùn)算部件需要的操作數(shù)從向量寄存器中讀取，運(yùn)算的中間結(jié)果也寫到向量寄存器中。 向量寄存器與標(biāo)量寄存器的主要差別是： 一個(gè)向量寄存器能夠保存一個(gè)向量，例如：64個(gè)64位寄存器。 采用寄存器-寄存器結(jié)構(gòu)的主要優(yōu)點(diǎn)：降低主存儲(chǔ)器的流量。 例如：寄存器-寄存器

24、結(jié)構(gòu)的cray-1與存儲(chǔ)器-存儲(chǔ)器結(jié)構(gòu)的star-100比較，運(yùn)算速度高3倍多（時(shí)鐘周期為40：12.5），主存儲(chǔ)器流量低2.5倍。1976年，cray公司推出cray-1向量機(jī)，開始了向量機(jī)的蓬勃發(fā)展，其峰值速度為0.1 gflops。 cray 1 1985年，cray-2，1g flops 1990年, sx-3, 22g flops 1991年，cray-ymp-c90,16gflopscray 2cray xmp/4cray y-mp816系統(tǒng)結(jié)構(gòu)1991年多向量處理器時(shí)間并行+空間并行256交叉存儲(chǔ)16mb1gb大量使用寄存器64位浮點(diǎn)/定點(diǎn)1983年12月,銀河-i巨型計(jì)算機(jī)由國(guó)

25、防科技大學(xué)計(jì)算機(jī)研究所研制成功。 銀河-ii并行巨型計(jì)算機(jī)由國(guó)防科技大學(xué)計(jì)算機(jī)研究所于1992年11月研制成功。銀河銀河1銀河銀河2 向量處理方式有三種類型：1橫向處理方式：橫向處理方式：向量計(jì)算是按行的方式從左至右橫向地進(jìn)行。 也稱水平處理方式，橫向加工方式等。2縱向處理方式：縱向處理方式：向量計(jì)算是按列的方式自上而下縱向地進(jìn)行。 也稱垂直處理方式，縱向加工方式等。3縱橫處理方式：縱橫處理方式：橫向處理和縱向處理相結(jié)合的方式。 也稱分組處理方式，縱橫向加工方式等。 以一個(gè)簡(jiǎn)單的c語言編寫的程序?yàn)槔f明向量的三種處理方式的工作原理。for (i = 1；i = n；i+)yi = ai (

26、bi + ci ); 逐個(gè)分量進(jìn)行處理：假設(shè)中間結(jié)果為t(i)。計(jì)算第1個(gè)分量： t(1) = b(1) + c(1) y(1) = a(1) t(1)計(jì)算第2個(gè)分量： t(2) = b(2) + c(2) y(2) = a(2) t(2) 計(jì)算最后一個(gè)分量：t(n) = b(n) + c(n) y(n) = a(n) t(n) 即逐個(gè)求y中的n個(gè)分量, 先進(jìn)行相加t1b1+c1, 其中t1為暫存單元, 然后相乘y1t1a1。 存在兩個(gè)問題： 在計(jì)算向量的每個(gè)分量時(shí)，都發(fā)生寫讀數(shù)據(jù)相關(guān)。流水線效率低。 如果采用多功能流水線，必須頻繁進(jìn)行流水線切換。 結(jié)論： 這種加工方式不適合于向量流水處理。

27、先縱向加工所有b和c向量中元素對(duì)的相加操作, 中間結(jié)果暫存到t1tn中, 然后再縱向加工所有對(duì)應(yīng)元素的乘法操作。 t(1) = b(1) + c(1)t(2) = b(2) + c(2) t(n) = b(n) + c(n)y(1) = a(1) t(1)y(2) = a(2) t(2) y(n) = a(n) t(n) 用向量指令形式表示時(shí), 變成: t=b+c y=ta 特點(diǎn)：流水線功能的切換只需一次?？色@得較高的吞吐率。 數(shù)據(jù)相關(guān)不影響流水線連續(xù)工作，可采用向量鏈接技術(shù)。 結(jié)論： 這種處理方式適用于向量處理機(jī)。 縱橫向加工(或稱為分組加工) 以寄存器寄存器方式工作的向量機(jī)都采用這種加工方

28、式。因?yàn)橄蛄考拇嫫鞯拈L(zhǎng)度有限(如cray-1的長(zhǎng)度為64)。當(dāng)向量長(zhǎng)度超過向量寄存器可表示的最大限度n時(shí), 就不得不分組加以處理。假設(shè)向量長(zhǎng)度為n, 則有n=kn+r, 其中nn, rn,n、k、r均為正整數(shù), k為組數(shù), r為余數(shù)(余下的部分也作為一組處理)。它的加工方式是: 組內(nèi)縱向加工, 組間為橫向加工。第一組計(jì)算: t1n=b1n+c1n y1n=a1n+t1n再算第二組: tn+12n=bn+12n+cn+12n yn+12n=an+12n+tn+12n 向量與標(biāo)量性能的平衡向量與標(biāo)量性能的平衡 向量鏈接技術(shù)向量鏈接技術(shù) 向量循環(huán)開采技術(shù)向量循環(huán)開采技術(shù) 實(shí)際的應(yīng)用問題中通常既有向量

29、計(jì)算又有標(biāo)量計(jì)算，而且兩類計(jì)算有一定的比例。向量平衡點(diǎn)(vector balance point)： 為了使向量硬件設(shè)備和標(biāo)量硬件設(shè)備的利用率相等，一個(gè)程序中為了使向量硬件設(shè)備和標(biāo)量硬件設(shè)備的利用率相等，一個(gè)程序中向量代碼所占的百分比。向量代碼所占的百分比。 關(guān)鍵問題是：向量硬件和標(biāo)量硬件都能充分利用，都不空閑。 向量處理機(jī)的向量平衡點(diǎn)必須與用戶程序的向量化程度相匹配。機(jī)器型號(hào) 向量性能向量性能(mflops)85.0 151.5 143.3 201.6 737.3 424.2 207.1 標(biāo)量性能標(biāo)量性能(mflops)9.8 11.2 13.1 17.0 17.8 9.5 6.6 向量平衡

30、向量平衡點(diǎn)點(diǎn)幾種超級(jí)計(jì)算機(jī)向量和標(biāo)量的性能向量運(yùn)算中的相關(guān)和沖突向量運(yùn)算中的相關(guān)和沖突 向量運(yùn)算中的數(shù)據(jù)相關(guān)和功能部件沖突主要有： 寫讀數(shù)據(jù)相關(guān)； 讀讀數(shù)據(jù)相關(guān)，或向量寄存器沖突； 運(yùn)算部件沖突。v0v1v2 v0v1v2v3v4 v5 v3v0 v4(a)不相關(guān)的指令 (b)寫讀數(shù)據(jù)相關(guān)v0v1v2 v0v1v2v3v4v5 v3v1 v4(c)功能部件沖突 (d)讀讀數(shù)據(jù)相關(guān) 利用向量指令間存在的先寫后讀的數(shù)據(jù)相關(guān)性來加快向量指令序列執(zhí)行速度的技術(shù)稱為鏈接技術(shù)。具體的說，結(jié)果寄存器可能成為后繼指令的操作數(shù)寄存器，兩條有數(shù)據(jù)相關(guān)的向量指令并行執(zhí)行。 例如：addv v1,v2,v3 ;v1v

31、2+ v3 multv v4,v1,v5 ;v4v1v5 分析：這兩條指令間對(duì)v1向量寄存器存在先寫后讀相關(guān), 通常必須等加法指令做完后才可開始乘法指令, 但如果使向量寄存器(例中的v1)在同一時(shí)鐘周期內(nèi), 既接收一個(gè)功能部件送來的運(yùn)算結(jié)果, 又可把這一結(jié)果作為下一個(gè)向量指令運(yùn)算所需的源操作數(shù)送給另一個(gè)功能部件, 那就可使這兩個(gè)部件鏈接起來進(jìn)行操作。當(dāng)鏈接進(jìn)入充分流水操作狀態(tài)后, 在一個(gè)時(shí)鐘周期內(nèi)就可同時(shí)獲取兩個(gè)操作結(jié)果。 以cray-1為例,設(shè)有如下向量運(yùn)算: d = a(b+c) 假設(shè)向量長(zhǎng)度64, 且b和c已由存儲(chǔ)器取至v0和v1, 則下面3條向量指令就可完成上述運(yùn)算: ld v3,a

32、;v3a addv v2,v0,v1 ;v2v0+v1 multv v4,v2,v3 ;v4v2v3 ld v3,a ;v3a addv v2,v0,v1 ;v2v0+v1 multv v4,v2,v3 ;v4v2xv3情況一：若這三條指令全部用串行方法則所需時(shí)間為: (1+6+1)+n-1+(1+6+1)+n-1+(1+7+1)+n-1=3n+22情況二：若前兩條指令并行執(zhí)行, 第三條指令串行執(zhí)行, 則所需時(shí)間為: (1+6+1)+n-1+(1+7+1)+n-1=2n+15拍情況三：采用并行和鏈接加速技術(shù)后, 執(zhí)行所需時(shí)間為: (1+6+1)+(1+7+1)+(n-1)=17+n-1=n+1

33、6拍設(shè)被加工向量長(zhǎng)度為n鏈接的條件：1鏈接兩條或多條指令存在先寫后讀相關(guān)2只有當(dāng)前一指令的第一個(gè)結(jié)果分量送入結(jié)果向量寄存器的那一個(gè)時(shí)鐘周期方可鏈接3當(dāng)一條向量指令的兩個(gè)源操作數(shù)分別是兩條先行指令的結(jié)果寄存器時(shí), 要求先行的兩條指令產(chǎn)生運(yùn)算結(jié)果的時(shí)間必須相等, 即要求有關(guān)功能部件的延遲時(shí)間相等4鏈接的兩條向量指令的向量長(zhǎng)度必須相等5針對(duì)不同的向量機(jī), 可能對(duì)鏈接還有其他特殊限制。如cray-1中, 允許自存儲(chǔ)器取數(shù)操作參與鏈接, 但不允許向存儲(chǔ)器寫數(shù)操作實(shí)現(xiàn)鏈接, 因?yàn)閏ray-1并不提供這種鏈接功能。 當(dāng)向量的長(zhǎng)度大于向量寄存器的長(zhǎng)度時(shí)，必須把長(zhǎng)向量分成長(zhǎng)度固定的段，采用循環(huán)結(jié)構(gòu)處理這個(gè)長(zhǎng)向量

34、，這種技術(shù)稱為向量循環(huán)開采技術(shù)，也稱為向量分段開采技術(shù)。 例如：a和b為長(zhǎng)度n的向量。 for (i=1; i=n; i+) ai=5*b(i)+c;當(dāng)n為64或更小時(shí)，產(chǎn)生a數(shù)組的7條指令序列是： 1：s15.0在標(biāo)量寄存器內(nèi)設(shè)置常數(shù) 2：s2c 將常數(shù)c裝入標(biāo)量寄存器 3：vln 在vl寄存器內(nèi)設(shè)置向量長(zhǎng)度 4：v0b 將b向量讀入向量寄存器 5：v1s1 v0 b數(shù)組的每個(gè)分量和常數(shù)相乘 6：v2s2v1 c和5b(i)相加 7：av2將結(jié)果向量存入a數(shù)組 第4、5、6、7條指令可以采用向量鏈接執(zhí)行。當(dāng)n超過64時(shí)，就需要采用向量循環(huán)。 向量的分段開采： low=1 vl=(n mod

35、mvl) *找出零頭長(zhǎng)度值 do 20 j=0, (n/mvl) *外循環(huán) do 10 i=low, low+vl-1 *以長(zhǎng)度vl操作 4：v0b 5：v1s1 v0 6：v2s2v1 主要操作 7：av2 10 continue low=low+vl *下一向量的開始 vl=mvl *將長(zhǎng)度值恢復(fù)成mvl 20 contine 經(jīng)分段處理后, 第一段長(zhǎng)度為n mod mvl, 而以后各段的長(zhǎng)度均為mvl（向量寄存器的長(zhǎng)度）。主要內(nèi)容：基本問題流水線技術(shù)向量流水技術(shù)現(xiàn)代處理器技術(shù) so easy ? no! 進(jìn)一步的思考：采用流水線技術(shù)所帶來的問題。取指令譯碼執(zhí)行保存結(jié)果t1t2t3t4i:

36、 add r1,r2,r3j: sub r4,r1,r3 研究相關(guān)性，不但可作為是否可指令調(diào)度的依據(jù)，而且可了解程序固有的并行性以及可以獲得的并行性。 相關(guān)相關(guān) 意味指令的運(yùn)行、結(jié)果產(chǎn)生的順序有要求， 意味指令的并行運(yùn)行和改變順序可能會(huì)產(chǎn)生問題， 是否意味指令的流水線運(yùn)行一定會(huì)產(chǎn)生停頓。 流水線3類相關(guān) 結(jié)構(gòu)相關(guān): 硬件不能支持兩條指令同時(shí)訪問同一個(gè)資源 two dogs fighting for the same bone 數(shù)據(jù)相關(guān): 指令依賴于前面尚在流水線中的指令的執(zhí)行結(jié)果 控制相關(guān): 在判斷轉(zhuǎn)移條件之前，就試圖決策轉(zhuǎn)移方向(分支指令、跳轉(zhuǎn)指令) 解決相關(guān)性問題，提高處理器執(zhí)行效率，是推

37、解決相關(guān)性問題，提高處理器執(zhí)行效率，是推動(dòng)處理器新技術(shù)產(chǎn)生的動(dòng)力源泉。動(dòng)處理器新技術(shù)產(chǎn)生的動(dòng)力源泉。 指令和數(shù)據(jù)共用同一個(gè)存儲(chǔ)器 存儲(chǔ)器為單口存儲(chǔ)器 沖突發(fā)生條件 instr 1 存儲(chǔ)器訪問指令 讀寫存儲(chǔ)器 instr 2 取指令時(shí)間時(shí)間(時(shí)鐘周期時(shí)鐘周期)loadinstr 1instr 2instr 3instr 4regaludmemifetchregregaludmemifetchregregaludmemifetchregcycle 1 cycle 2 cycle 3 cycle 4cycle 6 cycle 7cycle 5存儲(chǔ)器沖突存儲(chǔ)器沖突dmemregaludmemregif

38、etch指指令令執(zhí)執(zhí)行行次次序序時(shí)間時(shí)間(時(shí)鐘周期時(shí)鐘周期)loadinstr 1instr 2instr 3regaludmemifetchregregaludmemifetchregregaludmemifetchregcycle 1 cycle 2 cycle 3 cycle 4cycle 6 cycle 7cycle 5regaludmemifetchreg氣泡氣泡氣泡氣泡氣泡氣泡氣泡氣泡氣泡氣泡 原因：資源爭(zhēng)用 方法1: 等待第一步：檢測(cè)第二步：插入等待(空操作/氣泡) 方法2: 投入更多的硬件資源 雙存儲(chǔ)器(“harvard architecture”) 多端口存儲(chǔ)器（寄存器堆）r

39、ead after write (raw) 先寫后讀(寫未完成，讀即發(fā)出) instrj在instri完成寫之前讀 起因：基于變量的通訊 raw相關(guān)是程序相關(guān)性中最本質(zhì)的相關(guān)性之一。i: add r1,r2,r3j: sub r4,r1,r3 write after read (war) 先讀后寫 instrj在instri完成讀之前進(jìn)行寫操作 反相關(guān) 起因：r1的重用i: sub r4,r1,r3 j: add r1,r2,r3k: mul r6,r1,r7 write after write (waw) 寫后寫 instrj在instri完成寫之前進(jìn)行寫操作 輸出相關(guān) 起因是r1的重用i:

40、 sub r1,r4,r3 j: add r1,r2,r3k: mul r6,r1,r7 無妨假設(shè)處理器執(zhí)行如下形式的操作：rk (ri) op (rj)則：rk (ri) op (rj) rm (rk) op (rn)稱為raw（read after write）相關(guān)； ri(rk) op (rj) rk (rm) op (rn)稱為war（write after read）相關(guān)； rk (ri) op (rj) rk (rm) op (rn)稱為waw（write after write）相關(guān)。 指令的范圍（range)和域(domain)： r(i): 指令i所修改的寄存器（或存儲(chǔ)器單元

41、）的集合。 d(i): 指令i所讀取的寄存器（或存儲(chǔ)器單元）的集合。 假設(shè)指令j在程序的執(zhí)行順序中是指令i的后續(xù)指令。若指令j提前于指令i執(zhí)行，則可能引起： raw相關(guān)沖突，如果 r(i) d(j) ; war相關(guān)沖突，如果 d(i) r(j) ; waw相關(guān)沖突，如果 r(i) r(j) ;時(shí)間時(shí)間 (時(shí)鐘周期時(shí)鐘周期)指指令令執(zhí)執(zhí)行行次次序序add r1,r2,r3sub r4,r1,r3and r6,r1,r7or r8,r1,r9xor r10,r1,r11regaludmemifetchregregaludmemifetchregregaludmemifetchregregaludm

42、emifetchregregaludmemifetchregregaludmemifetchreg時(shí)間時(shí)間 (時(shí)鐘周期時(shí)鐘周期)指指令令執(zhí)執(zhí)行行次次序序ld r1, 4(r2)sub r4,r1,r6and r6,r1,r7or r8,r1,r9regaludmemifetchregregaludmemifetchregregaludmemifetchregregaludmemifetchreg 旁路未能解決所有問題時(shí)間時(shí)間 (時(shí)鐘周期時(shí)鐘周期)or r8,r1,r9指指令令執(zhí)執(zhí)行行次次序序ld r1, 4(r2)sub r4,r1,r6and r6,r1,r7regaludmemifetch

43、regregifetchaludmemregbubbleifetchaludmemregbubbleregifetchaludmembubblereg war： waw： 這兩類相關(guān)由寄存器重用引起； 指令順序不能改變； 在單功能流水線中不可能發(fā)生。i: sub r4,r1,r3 j: add r1,r2,r3k: mul r6,r1,r7i: sub r1,r4,r3 j: add r1,r2,r3k: mul r6,r1,r7ifidissuegprsfprsalufaddfmulfdivwbi: fdiv r4,r1,r3 j: add r1,r2,r3k: mul r6,r1,r7i:

44、 fmul r1,r4,r3 j: add r1,r2,r3k: mul r6,r1,r7定點(diǎn)指令：1 clock浮點(diǎn)指令：3 clocks 對(duì)于多功能流水線： 由每個(gè)功能單元的執(zhí)行時(shí)間不同（如定點(diǎn)和浮點(diǎn)運(yùn)算）war和waw相關(guān)可能引起執(zhí)行錯(cuò)誤。 解決war和waw相關(guān)的最簡(jiǎn)單的方法：停頓（暫停）。 指令的可以按程序順序發(fā)射（in-order-issue），但完成順序則可能與程序順序不同，即亂序完成（out-of-order complete）。 指令調(diào)度：指令調(diào)度：通過改變指令在程序中的位置，將相關(guān)指令之間的距離加大到不小于指令執(zhí)行延遲的時(shí)鐘數(shù)，使相關(guān)指令成為實(shí)際上的無關(guān)指令。 指令調(diào)度（靜

45、態(tài)）通常由編譯完成。 指令調(diào)度（動(dòng)態(tài)）通常采用硬件實(shí)現(xiàn)。 動(dòng)機(jī) 編譯時(shí)某些情況無法判斷，可以利用那些只有運(yùn)行時(shí)才能看到的信息； 簡(jiǎn)化編譯器設(shè)計(jì)； 代碼的可移植性好。 核心思路 允許暫停后的指令執(zhí)行； 寄存器重命名。記分板記分板(scoreboard) 命名起源于cdc 6600，其基本結(jié)構(gòu)：寄寄存存器器文文件件浮點(diǎn)乘浮點(diǎn)乘浮點(diǎn)乘浮點(diǎn)乘浮點(diǎn)除浮點(diǎn)除浮點(diǎn)加浮點(diǎn)加定點(diǎn)部件定點(diǎn)部件記分板記分板其基本控制階段： 發(fā)射(issue) 指令譯碼 檢測(cè)結(jié)構(gòu)相關(guān)、寫寫相關(guān) 當(dāng)前指令被阻塞后續(xù)指令被阻塞 讀操作數(shù)(read operands) 在沒有數(shù)據(jù)相關(guān)的前提下讀取操作數(shù) 執(zhí)行(execution) 功能部件

46、執(zhí)行完后通知記分板控制系統(tǒng) 寫回結(jié)果(write result) 記分板檢測(cè)功能部件的寫回，若發(fā)現(xiàn)有相關(guān)沖突則暫停記分板主要部件：記分板主要部件： 指令狀態(tài)表指令處于哪個(gè)階段 功能部件狀態(tài)表功能部件當(dāng)前狀態(tài)，9個(gè)域busy是否正在使用op運(yùn)算類型(/)fi目標(biāo)寄存器fj, fk源寄存器qj, qk產(chǎn)生fj，fk的功能部件rj, rkfj, fk就緒標(biāo)志 寄存器結(jié)果狀態(tài)表指示哪個(gè)功能部件將寫入該寄存器。如果沒有指令寫該寄存器，則為空。 記分板算法對(duì)cdc6600的加速比： 對(duì)fortran語言，性能提高1.7倍； 對(duì)手寫匯編程序，性能提高2.5倍。 6600記分板局限性： 指令窗口小指令調(diào)度有限

47、； 功能部件少結(jié)構(gòu)冒險(xiǎn)(整數(shù)load/store部件)； 結(jié)構(gòu)冒險(xiǎn)暫停發(fā)射。tomasulo算法算法1. 采用于ibm 360/91浮點(diǎn)部件(1967年)；2. 將記分牌技術(shù)和寄存器重命名技術(shù)結(jié)合起來，更有效地解決寫后寫、讀后寫相關(guān)； 1967年，ibm公司的robert tomasulo 開創(chuàng)性的提出了解決上述問題的方法-寄存器重命名（rrgister renaming)。 寄存器重命名技術(shù)使得在不改變指令系統(tǒng)前提下實(shí)際寄存器數(shù)量得到增加。換句話說，可以使用比isa（industry standard architecture) 更多的寄存器而依然保持與isa的兼容性。fp加法器加法器add

48、1add2add3fp乘法器乘法器mult1mult2叢主存來叢主存來保留站保留站common data bus (cdb)去主存去主存fp操作操作隊(duì)列隊(duì)列讀數(shù)緩沖區(qū)讀數(shù)緩沖區(qū)寫緩沖區(qū)寫緩沖區(qū)保留站的組成：保留站的組成： op:功能單元運(yùn)算類型 (+或) vj, vk: 源操作數(shù)值 qj, qk: 產(chǎn)生源操作數(shù)的保留站 qj,qk=0 數(shù)據(jù)就緒 busy: 保留站或相關(guān)fu忙 寄存器結(jié)果狀態(tài)表 指示哪個(gè)fu要寫哪個(gè)寄存器 如果沒有將寫入寄存器的未決指令，則該域?yàn)榭?發(fā)射叢fp操作隊(duì)列中取指令 如果保留站空閑(沒有結(jié)構(gòu)冒險(xiǎn)) ，則 控制單元發(fā)射指令&發(fā)送操作數(shù)(對(duì)寄存器進(jìn)行換名) 執(zhí)行對(duì)

49、操作數(shù)進(jìn)行操作(ex) 如果兩個(gè)操作數(shù)都就緒執(zhí)行 如果未就緒監(jiān)控cdb 寫回完成執(zhí)行 (wb) 通過cdb將結(jié)構(gòu)寫入所有等待的功能單元中 標(biāo)記保留站可用 公共數(shù)據(jù)總線: 數(shù)據(jù) + 源 (“來源”總線) 64位數(shù)據(jù) + 4位功能單元源地址 如果與期望的功能單元匹配則寫入 (產(chǎn)生結(jié)果) 廣播模式tomsulo算法的基本思想： 只要操作數(shù)一有效就取至保留棧； 要執(zhí)行的指令將從保留棧中取得操作數(shù)； 一條指令發(fā)射時(shí)，取操作數(shù)的寄存器被重新命名為該寄存器保留站的名稱。 通過指令發(fā)射邏輯和保留站的結(jié)合實(shí)現(xiàn)寄存器重命名。例： 執(zhí)行時(shí)間i1 ld f2, 34(r2) 1i2 ld f4, 45(r3) 很長(zhǎng)i

50、3 multd f6, f4, f2 3i4 subd f8, f5, f2 1i5 divd f4, f2, f8 4i6 addd f10, f6, f4 1124356順序發(fā)射：1 (2,1) . . . . . . 2 3 4 4 3 5 . . . 5 6 6 指令4與指令3無關(guān)，是否可以在指令3等待指令2完成之前，先執(zhí)行指令4？ 進(jìn)一步思考，指令是否可以通過亂序發(fā)射亂序發(fā)射（out-of-order issue）或亂序執(zhí)行亂序執(zhí)行（out-of-order execution）提高執(zhí)行效率？ 實(shí)現(xiàn)方法？對(duì)一組一組指令的數(shù)據(jù)相關(guān)情況進(jìn)行分析，找出無raw,war,waw相關(guān)沖突指令，

51、送入空閑執(zhí)行單元（即無結(jié)構(gòu)相關(guān)）執(zhí)行。例： 執(zhí)行時(shí)間i1 ld f2, 34(r2) 1i2 ld f4, 45(r3) 很長(zhǎng)i3 multd f6, f4, f2 3i4 subd f8, f5, f2 1i5 divd f4, f2, f8 4i6 addd f10, f6, f4 1124356順序發(fā)射：1 (2,1) . . . . . . 2 3 4 4 3 5 . . . 5 6 6亂序發(fā)射（執(zhí)行）： 1 (2,1) 4 4 . . . . 2 3 . . 3 5 . . . 5 6 6問題：什么因素限制了流水線中指令執(zhí)行的條數(shù)？程序中的那些特征限制了流水線中的可執(zhí)行指令的數(shù)目？結(jié)

52、論：寄存器的數(shù)目是限制流水線中可執(zhí)行指令條數(shù)的關(guān)鍵因素。僅使用少量寄存器通常不能使流水線工作在滿負(fù)荷狀態(tài)。 如何解決？例： 執(zhí)行時(shí)間i1 ld f2, 34(r2) 1i2 ld f4, 45(r3) 很長(zhǎng)i3 multd f6, f4, f2 3i4 subd f8, f5, f2 1i5 divd f4, f2, f8 4i6 addd f10, f6, f4 1124356順序發(fā)射：1 (2,1) . . . . . . 2 3 4 4 3 5 . . . 5 6 6亂序發(fā)射： 1 (2,1) 4 4 5 . . . 2 3 5 . 3 6 6流水線的效率提高了！tomasulo記分板窗

53、口=14指令 95%）消除轉(zhuǎn)移引起的性能下降。 需要硬件的支持： 指令預(yù)測(cè)單元的基本構(gòu)件：bht（branch history table)，btb(branch target buffer)j zj z向后轉(zhuǎn)移90%向前轉(zhuǎn)移50% 統(tǒng)計(jì)表明，轉(zhuǎn)移指令中轉(zhuǎn)移發(fā)生的概率為6070%。 動(dòng)態(tài)轉(zhuǎn)移預(yù)測(cè)就是通過對(duì)程序中分支指令過去的行為考察，預(yù)測(cè)當(dāng)前轉(zhuǎn)移指令的行為。 時(shí)間相關(guān)性 一條分支指令的歷史行為很可能決定著該指令當(dāng)前的行為。 空間相關(guān)性 一些分支指令的行為可能是相互關(guān)聯(lián)的。考慮空間相關(guān)性問題，例： if (xi 7) y+=1; if (xi 5) c-=4; 如果第一個(gè)語句的條件不成立，則第二

54、條語句的條件亦不成立。 基本思想：基于該分支指令的歷史記錄-根據(jù)該分支指令在最近一次或幾次的運(yùn)行情況(轉(zhuǎn)移成功或失敗)，來預(yù)測(cè)該分支指令的本次運(yùn)行情況(轉(zhuǎn)移成功或失敗)。 實(shí)現(xiàn)方法：建立一片緩沖區(qū)，記錄各運(yùn)行過的分支指令的運(yùn)行情況(轉(zhuǎn)移成功或失敗)。-根據(jù)分支指令地址的低位，究竟多少位取決于緩沖區(qū)大小。 -預(yù)測(cè)位，其長(zhǎng)度(多少位)決定能記錄該指令前多少次運(yùn)行情況。轉(zhuǎn)移指令的執(zhí)行過程：(1)現(xiàn)場(chǎng)保留。(2)按預(yù)測(cè)方向取后繼指令。(3)得到分支結(jié)果后如果預(yù)測(cè)成功，繼續(xù)運(yùn)行；如果預(yù)測(cè)失敗，恢復(fù)保留的現(xiàn)場(chǎng)，從分支處重新執(zhí)行；(4)修改預(yù)測(cè)位。i-1分支指令ii+1i+2p+2p+1得到分支結(jié)果(1)(

55、1)預(yù)測(cè)位長(zhǎng)度為預(yù)測(cè)位長(zhǎng)度為1 1預(yù)測(cè)位內(nèi)容：預(yù)測(cè)位內(nèi)容：記錄該指令最近一次分支是否成功,如 “1”表示分支成功， “0”表示分 支失敗。預(yù)測(cè)方法：預(yù)測(cè)方法：如果該指令最近一次分支成功則預(yù)測(cè)分支成功，反之則預(yù)測(cè)分支失敗。預(yù)測(cè)位修改：預(yù)測(cè)位修改：如果實(shí)際運(yùn)行該指令發(fā)現(xiàn)分支成功，則置預(yù)測(cè)位為“1”，反之為“0”。10分支不成功分支成功分支不成功分支成功(2)(2)預(yù)測(cè)位長(zhǎng)度為預(yù)測(cè)位長(zhǎng)度為n n預(yù)測(cè)位內(nèi)容：預(yù)測(cè)位內(nèi)容：為 0 到 2n-1 計(jì)數(shù)器，每次分支結(jié)果出來后，如分支成功則加 1，分支失則減 1，計(jì)數(shù)器值增加到 2n-1 后不再增加，減小到 0 后不再減小。預(yù)測(cè)方法：預(yù)測(cè)方法：如果計(jì)數(shù)器值大于

56、或等于最大值的一半 2n-1 ，預(yù)測(cè)分支成功，反之預(yù)測(cè)分支失敗。n 為為 2 時(shí)的預(yù)測(cè)位：時(shí)的預(yù)測(cè)位：1110分支不成功分支成功分支不成功分支成功0100分支不成功分支成功分支不成功分支成功分支預(yù)測(cè)成功分支預(yù)測(cè)不成功i-cache opcode offset+0 0target pcbht indexk2k-entry bht,2bits/entryinstructionsbranch?taken / takenfatch pc實(shí)際試驗(yàn)：(1)預(yù)測(cè)位為 2 和預(yù)測(cè)位為 n 的預(yù)測(cè)性能差別不大。(2)預(yù)測(cè)緩沖區(qū)大小增加到 4096 個(gè)記錄項(xiàng)后預(yù)測(cè)性 能不再明顯增加(只用取指令地址的低 12 位)

57、(3)在預(yù)測(cè)位為 2 ，預(yù)測(cè)緩沖區(qū)為 4096 個(gè)記錄項(xiàng)情 況下，預(yù)測(cè)準(zhǔn)確率為8299，即預(yù)測(cè)失敗率為 118。起作用的前提：目標(biāo)地址的計(jì)算要快于分支結(jié)果計(jì)算。進(jìn)一步減少分支延遲：分支目標(biāo)緩沖進(jìn)一步減少分支延遲：分支目標(biāo)緩沖分支指令無延遲的前提：分支指令無延遲的前提： 分支預(yù)測(cè)成功 分支預(yù)測(cè)和目標(biāo)地址計(jì)算都在 if 階段就能完成。基本思想：基本思想：設(shè)立一個(gè)緩沖區(qū)(稱為分支目標(biāo)緩沖區(qū)，或btb )，其中存放最近一次運(yùn)行時(shí)分支成功的分支指令的信息(指令地址、分支目標(biāo) pc )，如果當(dāng)前指令屬于分支目標(biāo)緩沖(與其中某一條指令的地址相同)，則確定該指令是分支指令，并預(yù)測(cè)分支成功，從分支目標(biāo)緩沖直接獲

58、得目標(biāo) pc ；反之，則順序取指令(普通指令或預(yù)測(cè)分支失敗的分支指令)。地址標(biāo)示分支目標(biāo) pc當(dāng)前 pc查找、比較分支目標(biāo)緩沖命中？認(rèn)為本指令是分支指令并且分支成功，以分支目標(biāo) pc 作為下一條指令地址yn認(rèn)為本指令不是分支成功的分支指令，按普通指令處理 當(dāng)前pc值訪問指令存儲(chǔ)器和查詢btb 預(yù)測(cè)錯(cuò)誤， 清除取來的指令并從分支的另外一個(gè)目標(biāo)取指令，刪除btb中對(duì)應(yīng)項(xiàng) y es no btb中存在？ 以分支目標(biāo)pc值送pc 成功分支指令？ 當(dāng)前分支成功？ 預(yù)測(cè)成功， 后繼指令無延遲執(zhí)行 以當(dāng)前指令 pc值和分支目標(biāo)pc送入btb中作為一個(gè)新項(xiàng) 普通指令 no y es no y es 取指令 指

59、令譯碼 指令執(zhí)行 作為下一條指令地址 btb indexkfatch pcmatchpc entrypc entryvalid=validtargeti - cache 超標(biāo)量處理器 超流水線處理器 超標(biāo)量超流水線處理器 三種處理器的比較 vliw處理器 超標(biāo)量處理機(jī)：一個(gè)時(shí)鐘周期內(nèi)能夠同時(shí)發(fā)射多條指令的處理機(jī)稱為超標(biāo)量處理機(jī)，它必須有兩條或兩條以上能夠同時(shí)工作的指令流水線。 超標(biāo)量處理機(jī)典型結(jié)構(gòu)：多條指令流水線、多個(gè)功能部件。先進(jìn)的超標(biāo)量處理機(jī)有：定點(diǎn)處理部件cpu，浮點(diǎn)處理部件fpu，圖形加速部件gpu，大量的通用寄存器，兩個(gè)一級(jí)高速cache，標(biāo)量處理機(jī)的指令級(jí)并行度大于1。 motor

60、ola公司的公司的mc88110： 10個(gè)操作部件： 整數(shù)（2）、位操作、浮點(diǎn)加、浮點(diǎn)乘、浮點(diǎn)除、圖形（2）、load/store和指令分配轉(zhuǎn)移部件。 兩個(gè)寄存器堆： 整數(shù)部件通用寄存器堆，32個(gè)32位寄存器； 浮點(diǎn)部件擴(kuò)展寄存器堆，32個(gè)80位寄存器。每個(gè)寄存器堆有8個(gè)端口，分別與8條內(nèi)部總線相連接，有一個(gè)緩沖深度為4的先行讀數(shù)棧和一個(gè)緩沖深度為3的后行寫數(shù)棧。 兩個(gè)獨(dú)立的高速cache： 一個(gè)數(shù)據(jù)cache和一個(gè)指令cache，容量各為8kb，采用兩路組相聯(lián)方式。一個(gè)轉(zhuǎn)移目標(biāo)指令cache：在有兩路分支時(shí)，存放其中一路分支上的指令。整數(shù)整數(shù)部件部件整數(shù)整數(shù)部件部件位位操作操作浮點(diǎn)浮點(diǎn)加加乘法乘法部