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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、，不做任何處理。重復這個步驟。對產生的每一個新的沖突向量做同樣處理。在初始沖突向量和所有形成的沖突向量之間，箭頭連接。1010101111111011111010117*157*3537*當右移2、4、6位，時移出位為1，表示用這些啟動距離輸入新任務要發(fā)生沖突，不做任何處理。當右移1、3、5和大于等于7位時，移出位是0，表示用這些啟動距離輸入新任務不會發(fā)生沖突。7*表示大于等于75（3）從狀態(tài)圖中可以找到許多不發(fā)生流水段沖突的啟動循環(huán)。，只要找到簡單循環(huán)，進而確定平均啟動距離最小的啟動循環(huán)。它們是： （1，7）、（3，5，7）、（5，7）等簡單循環(huán)平均啟動距離（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最小啟動循環(huán)是具有最小平均最小啟動距離的啟動循環(huán)。 最小循環(huán)為（1，7）、（3，5） 最小恒定循環(huán)為（5） 時間流水12345678910111213141516s1x1x2x1x3x2x4x3s2x1x2x1x2x3x4x3s3x1x1x2x2x3x3x4s4x1x2x3x4最小啟動循環(huán)為（3，5）的流水線工作狀態(tài) 時間流水段123456789101112131415s1x1x2x1x2x3x4x3s2x1x2x1x2x3x4x3x4s3x1x2x1x2x3x4x3x4s4x1x2x3x4最小啟動循環(huán)為（1，7）的流水線工作狀態(tài)

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

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

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

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

24、結構的cray-1與存儲器-存儲器結構的star-100比較，運算速度高3倍多（時鐘周期為40：12.5），主存儲器流量低2.5倍。1976年，cray公司推出cray-1向量機，開始了向量機的蓬勃發(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)結構1991年多向量處理器時間并行+空間并行256交叉存儲16mb1gb大量使用寄存器64位浮點/定點1983年12月,銀河-i巨型計算機由國

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

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

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

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

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

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

31、2+ v3 multv v4,v1,v5 ;v4v1v5 分析：這兩條指令間對v1向量寄存器存在先寫后讀相關, 通常必須等加法指令做完后才可開始乘法指令, 但如果使向量寄存器(例中的v1)在同一時鐘周期內, 既接收一個功能部件送來的運算結果, 又可把這一結果作為下一個向量指令運算所需的源操作數(shù)送給另一個功能部件, 那就可使這兩個部件鏈接起來進行操作。當鏈接進入充分流水操作狀態(tài)后, 在一個時鐘周期內就可同時獲取兩個操作結果。 以cray-1為例,設有如下向量運算: d = a(b+c) 假設向量長度64, 且b和c已由存儲器取至v0和v1, 則下面3條向量指令就可完成上述運算: 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情況一：若這三條指令全部用串行方法則所需時間為: (1+6+1)+n-1+(1+6+1)+n-1+(1+7+1)+n-1=3n+22情況二：若前兩條指令并行執(zhí)行, 第三條指令串行執(zhí)行, 則所需時間為: (1+6+1)+n-1+(1+7+1)+n-1=2n+15拍情況三：采用并行和鏈接加速技術后, 執(zhí)行所需時間為: (1+6+1)+(1+7+1)+(n-1)=17+n-1=n+1

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

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

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

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

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

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

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

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

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

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

43、regregifetchaludmemregbubbleifetchaludmemregbubbleregifetchaludmembubblereg war： waw： 這兩類相關由寄存器重用引起； 指令順序不能改變； 在單功能流水線中不可能發(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定點指令：1 clock浮點指令：3 clocks 對于多功能流水線： 由每個功能單元的執(zhí)行時間不同（如定點和浮點運算）war和waw相關可能引起執(zhí)行錯誤。 解決war和waw相關的最簡單的方法：停頓（暫停）。 指令的可以按程序順序發(fā)射（in-order-issue），但完成順序則可能與程序順序不同，即亂序完成（out-of-order complete）。 指令調度：指令調度：通過改變指令在程序中的位置，將相關指令之間的距離加大到不小于指令執(zhí)行延遲的時鐘數(shù)，使相關指令成為實際上的無關指令。 指令調度（靜

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

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

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

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

49、操作數(shù)進行操作(ex) 如果兩個操作數(shù)都就緒執(zhí)行 如果未就緒監(jiān)控cdb 寫回完成執(zhí)行 (wb) 通過cdb將結構寫入所有等待的功能單元中 標記保留站可用 公共數(shù)據總線: 數(shù)據 + 源 (“來源”總線) 64位數(shù)據 + 4位功能單元源地址 如果與期望的功能單元匹配則寫入 (產生結果) 廣播模式tomsulo算法的基本思想： 只要操作數(shù)一有效就取至保留棧； 要執(zhí)行的指令將從保留棧中取得操作數(shù)； 一條指令發(fā)射時，取操作數(shù)的寄存器被重新命名為該寄存器保留站的名稱。 通過指令發(fā)射邏輯和保留站的結合實現(xiàn)寄存器重命名。例： 執(zhí)行時間i1 ld f2, 34(r2) 1i2 ld f4, 45(r3) 很長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無關，是否可以在指令3等待指令2完成之前，先執(zhí)行指令4？ 進一步思考，指令是否可以通過亂序發(fā)射亂序發(fā)射（out-of-order issue）或亂序執(zhí)行亂序執(zhí)行（out-of-order execution）提高執(zhí)行效率？ 實現(xiàn)方法？對一組一組指令的數(shù)據相關情況進行分析，找出無raw,war,waw相關沖突指令，

51、送入空閑執(zhí)行單元（即無結構相關）執(zhí)行。例： 執(zhí)行時間i1 ld f2, 34(r2) 1i2 ld f4, 45(r3) 很長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ù)目？結

52、論：寄存器的數(shù)目是限制流水線中可執(zhí)行指令條數(shù)的關鍵因素。僅使用少量寄存器通常不能使流水線工作在滿負荷狀態(tài)。 如何解決？例： 執(zhí)行時間i1 ld f2, 34(r2) 1i2 ld f4, 45(r3) 很長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%）消除轉移引起的性能下降。 需要硬件的支持： 指令預測單元的基本構件：bht（branch history table)，btb(branch target buffer)j zj z向后轉移90%向前轉移50% 統(tǒng)計表明，轉移指令中轉移發(fā)生的概率為6070%。 動態(tài)轉移預測就是通過對程序中分支指令過去的行為考察，預測當前轉移指令的行為。 時間相關性 一條分支指令的歷史行為很可能決定著該指令當前的行為。 空間相關性 一些分支指令的行為可能是相互關聯(lián)的。考慮空間相關性問題，例： if (xi 7) y+=1; if (xi 5) c-=4; 如果第一個語句的條件不成立，則第二

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

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

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

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

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

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

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