《《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案(課7).ppt》由會員分享，可在線閱讀，更多相關(guān)《《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案(課7).ppt（28頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),1,第6章 指令級并行軟件方法（指令級，多發(fā)射或亂序執(zhí)行，靜態(tài)調(diào)度）,本章學(xué)習(xí)由軟件（即編譯程序）實(shí)現(xiàn)的指令級并行方法，主要內(nèi)容是如何修改、優(yōu)化已編譯完的目標(biāo)程序，以減少指令間沖突造成的停頓，縮短程序執(zhí)行時(shí)間。 6.1 基本指令調(diào)度及循環(huán)展開 6.5 開發(fā)更多的指令級并行,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),2,教材P154第一段說可以采用圖3.17的5段整數(shù)流水線（下圖a）來討論本節(jié)（本章）的整數(shù)、浮點(diǎn)數(shù)混合運(yùn)算程序，實(shí)際上解釋不通，我們改用下圖b的整數(shù)、浮點(diǎn)分離的流水線結(jié)構(gòu)來討論。,第6章采用的流水線模型,整數(shù)ALU 浮點(diǎn)ALU (b) 實(shí)際可用的流水線
2、結(jié)構(gòu),整數(shù)、浮點(diǎn)共用ALU (a) 圖3.17流水線結(jié)構(gòu)（P71 ）,WB,MEM,IF,ID,F0,F1,F2,F3,WB,MEM,EX,,,,,,,,,,,IF,ID,WB,MEM,EX,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),3,(3) (4),(1) (2),(1) 采用P90圖3.33的優(yōu)化流水線方案： 相關(guān)指令之間采用定向技術(shù)（包括前、后半周期定向），以減少停頓； 在ID段處理分支指令，分支停頓為1個(gè)時(shí)鐘周期； 采用延遲分支技術(shù)，設(shè)1個(gè)延遲槽。 (2) 相關(guān)浮點(diǎn)指令之間的停頓：浮點(diǎn)數(shù)在“執(zhí)行”段需4拍，其它段為1拍。兩條相關(guān)的浮點(diǎn)指令之間的最少停頓周期數(shù)如下表（
3、即教材P153表6.1）,第6章采用的流水線模型,IF,ID,F0,Mem,WB,IF,ID,EX,Mem,WB,F1,F2,F3,IF,ID,F0,Mem,WB,F1,F2,F3,IF,ID,F0,Mem,WB,F1,F2,F3,IF,ID,EX,Mem,WB,IF,ID,F0,Mem,WB,F1,F2,F3,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),4,6.1.1 指令調(diào)度方法 基本原理是按兩條相關(guān)指令之間所需的最小啟動距離將它們隔開，在二者之間安排其它的無關(guān)指令，減少直至消除流水線停頓。 例6.1（P154）：將如下C語言源程序編
4、譯成MIPS目標(biāo)代碼，然后使用指令調(diào)度技術(shù)、延遲分支技術(shù)優(yōu)化其代碼性能（指縮短運(yùn)行時(shí)間）。 for(i=1000;i0;i- -) xi=xi+s; 解： (1)初步編譯結(jié)果如下 Loop： L.D F0, 0(R1) //F01個(gè)向量元素 ADD.D F4, F0, F2 //F4F0+F2（即標(biāo)量s） S.D F4, 0(R1) //F4存回向量元素 DADDIU R1, R1, #-8 //R1R1-8（指向前1個(gè)元素，長浮點(diǎn)） BNE R1, R2, Loop //若R1R2，轉(zhuǎn)Loop,6.1 基本指令調(diào)度及循環(huán)展開,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)
5、,5,調(diào)度前的相關(guān)鏈分析 ： 代碼性能：每輪循環(huán)完成1個(gè)浮點(diǎn)元素運(yùn)算，需10拍，其中5拍是空轉(zhuǎn)。,6.1 基本指令調(diào)度及循環(huán)展開,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),6,模擬軟件Cycles圖： 模擬結(jié)果比分析結(jié)果多1拍的原因在于模擬器的流水線存在“結(jié)構(gòu)沖突”。,6.1 基本指令調(diào)度及循環(huán)展開,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),7,(2) 調(diào)度、延遲分支后的相關(guān)鏈分析 (注意S.D指令需要修改offset值)： 代碼性能：每輪循環(huán)完成1個(gè)浮點(diǎn)元素運(yùn)算，需6拍，其中1拍是空轉(zhuǎn)。 模擬軟件Cycles圖：,6.1 基本指令調(diào)度及循環(huán)展開,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)
6、構(gòu),8,從有效操作比例看，剛才的例子中每個(gè)浮點(diǎn)元素運(yùn)算中使用3條有效指令，附加2條循環(huán)控制指令，輔助操作占了太高的比例。 循環(huán)展開的目的一是降低輔助操作的比例，二是通過合并來增加每個(gè)循環(huán)體中的指令條數(shù)，使指令調(diào)度有更大的調(diào)整范圍，優(yōu)化效果更好。 例6.2（P155）：將例6.1未優(yōu)化程序展開3次得到4個(gè)循環(huán)體，然后使用指令調(diào)度技術(shù)、延遲分支技術(shù)優(yōu)化其代碼性能。假設(shè)原循環(huán)次數(shù)是4的整倍數(shù)。 解：先討論幾個(gè)注意事項(xiàng)。 如果各輪循環(huán)之間不存在相關(guān)，展開后可以簡單并行，否則需處理； 如果原循環(huán)次數(shù)N=展開倍數(shù)MK（K是整數(shù)），則新的循環(huán)次數(shù)K=N/M，否則要在循環(huán)結(jié)束之后增加補(bǔ)償代碼來完成剩余的操作；
7、 原來多輪循環(huán)重復(fù)使用的寄存器，合并之后必須通過重命名來區(qū)分，否則發(fā)生名相關(guān)，限制并行性； 原來各輪循環(huán)中的循環(huán)控制指令，合并后可以減少。,6.1.2 循環(huán)展開方法,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),9,(1)展開后沒有調(diào)度的程序如下 Loop: L.D F0, 0(R1) ;F0 xi（取數(shù)） ADD.D F4, F0, F2 ;F4 F0 + F2 S.D F4, 0(R1) ;xi F4（存結(jié)果） L.D F6, -8(R1) ;F6 xi-1（取數(shù)） ADD.D F8, F6, F2 ;F8 F6 + F2 S.D F8, -8(R1) ;xi-1 F8
8、（存結(jié)果） L.D F10,-16(R1) ;F10 xi-2（取數(shù)） ADD.D F12, F10, F2 ;F12 F10 + F2 S.D F12, -16(R1) ;xi-2 F12（存結(jié)果） L.D F14, -24(R1) ;F14 xi-3（取數(shù)） ADD.D F16, F14, F2 ;F16 F14 + F2 S.D F16, -24(R1) ;xi-3 F16（存結(jié)果） DADDIU R1, R1, #-32 ;R1 R1 - 48（指針前移4個(gè)數(shù)） BNE R1, R2, Loop ;若 R1R2，循環(huán),例6.2（P155）,2014.2.17,
9、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),10,調(diào)度前的相關(guān)鏈分析 （未完，接下頁）：,例6.2（續(xù)1）,,,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),11,代碼性能：每輪循環(huán)完成4個(gè)浮點(diǎn)元素運(yùn)算，共28拍，其中14拍是空轉(zhuǎn)。折算每個(gè)浮點(diǎn)元素運(yùn)算使用28/4=7拍（展開前10拍），其中3.5拍是空轉(zhuǎn)。,例6.2（續(xù)2）,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),12,(2)展開后經(jīng)過調(diào)度優(yōu)化的程序如下 loop: L.D F0, 0(R1) ;F0 xi（取數(shù)） L.D F6, -8(R1) ;F6 xi-1（取數(shù)） L.D F10,-16(R1) ;F10 xi-2（取數(shù)） L.D F14,-2
10、4(R1) ;F14 xi-3（取數(shù)） ADD.D F4, F0, F2 ;F4 F0 + F2 ADD.D F8, F6, F2 ;F8 F6 + F2） ADD.D F12, F10, F2 ;F12 F10 + F2） ADD.D F16, F14, F2 ;F16 F14 + F2 S.D F4, 0(R1) ;xi F4（存結(jié)果） S.D F8, -8(R1) ;xi-1 F8（存結(jié)果） DADDUI R1, R1, -32 ;R1 R1 - 48（指針前移4個(gè)數(shù)） S.D F12, 16(R1) ;xi-2+4 F12（存結(jié)果，指針+32） BNE
11、 R1, R2, loop ;若 R1R2，循環(huán) S.D F16, 8(R1) ;xi-3+4 F16（存結(jié)果，指針+32）,例6.2（續(xù)3）,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),13,調(diào)度后的相關(guān)鏈分析 ：,例6.2（續(xù)4）,代碼性能：每個(gè)浮點(diǎn)元素運(yùn)算使用14/4=3.5拍，無空轉(zhuǎn)。,,,,,,,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),14,習(xí)題改寫（原題意思不清） 以下向量點(diǎn)積循環(huán)段在教材圖3.33所示改進(jìn)流水線上運(yùn)行，浮點(diǎn)運(yùn)算延遲符合教材表6.1規(guī)定，F(xiàn)2的初值為0。 loop: L.D F0, 0(R1) L.D F4, 0(R2) MUL.D F0, F0, F4
12、 ADD.D F2, F0, F2 DADDUI R1, R1, #-8 DADDUI R2, R2, #-8（原題錯(cuò)寫為R1） BNE R1, R3, loop (1)使用循環(huán)展開和指令調(diào)度改造程序（結(jié)果含3個(gè)循環(huán)體），使“空轉(zhuǎn)”周期數(shù)不超過1個(gè)，寫出新程序； (2)手工計(jì)算原程序處理每對元素所需的時(shí)鐘周期數(shù)、其中的空轉(zhuǎn)數(shù)； (3)手工計(jì)算新程序處理每對元素所需的時(shí)鐘周期數(shù)、其中的空轉(zhuǎn)數(shù)；,習(xí)題6.8,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),15,(4)用WinMIPS64模擬器依次運(yùn)行原程序、新程序，測試(2)、(3)步的對應(yīng)結(jié)果（最好打印Cycles圖）； (5)分析模擬過程，你能找
13、出哪些造成測試結(jié)果與手工計(jì)算結(jié)果不一致的原因？,習(xí)題6.8（續(xù)）,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),16,前幾大節(jié)基本解決了分支程序的控制相關(guān)問題，本大節(jié)重點(diǎn)討論循環(huán)程序中的數(shù)據(jù)相關(guān)問題。對編譯之前的源代碼進(jìn)行識別、優(yōu)化更容易。 6.5.1 挖掘更多的循環(huán)級并行 本小節(jié)重點(diǎn)討論不同次循環(huán)迭代之間的相關(guān)。 1. 循環(huán)攜帶相關(guān) 定義：不同次循環(huán)迭代之間的相關(guān)。 影響：如果原始程序內(nèi)存在循環(huán)攜帶相關(guān)，則在循環(huán)展開后，指令不能在各輪循環(huán)之間任意調(diào)動，這就大大限制了優(yōu)化操作的效果發(fā)揮。,6.5 開發(fā)更多的指令級并行,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),17,for(i=1;i<=100;i=i+1)
14、 Ai+1=Ai+Ci; /*S1*/ Bi+1=Bi+Ai+1; /*S2*/ 假設(shè)數(shù)組A、B和C中所有元素的存儲地址都互不相同，請問語句S1與S2之間存在哪些數(shù)據(jù)相關(guān)？ 解： (1) 循環(huán)迭代內(nèi)相關(guān)：藍(lán)色箭頭； (2) 循環(huán)攜帶相關(guān)：紅色箭頭。,例6.7（P173）,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),18,進(jìn)一步討論循環(huán)展開的結(jié)果（以展開1次為例）： for(i=1;i<=100;i=i+2) Ai+1=Ai+Ci; /*S1，來自第1個(gè)迭代*/ Bi+1=Bi+Ai+1; /*S2，來自第1個(gè)迭代*/ Ai+2=Ai+1+Ci+1; /*S3，來自第2個(gè)迭代*/
15、 Bi+2=Bi+1+Ai+2; /*S4，來自第2個(gè)迭代*/ 這時(shí)如果因?yàn)镾1、S2相關(guān)造成停頓，需要在它們之間插入一條語句的話，插入S3仍有同樣的相關(guān)，S4則不能調(diào)至S3之前。實(shí)際上無語句可調(diào)。 由此例可以看出： 循環(huán)迭代內(nèi)相關(guān)是局部性限制，不影響指令在大范圍內(nèi)移動； 循環(huán)攜帶相關(guān)是全局性限制，影響了指令在大范圍內(nèi)移動。 所以需要尋找消除循環(huán)攜帶相關(guān)的方法。,例6.7解（續(xù)）,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),19,有一類循環(huán)攜帶相關(guān)可以修改為循環(huán)內(nèi)相關(guān)，例如 for(i=1;i<=100;i=i+1) Ai=Ai+Bi; /*S1*/ Bi+1=Ci+Di; /*S2*/
16、 解： 其特征是本輪循環(huán)的一條語句與下輪循環(huán)的另一條語句相關(guān)，這種情況不構(gòu)成連續(xù)的相關(guān)鏈，可以把相關(guān)的兩條語句重新組合到同一輪循環(huán)中 A1=A1+B1; for(i=1;i<=99;i=i+1) Bi+1=Ci+Di; /*原來的S2*/ Ai+1=Ai+1+Bi+1; /*原來的S1*/ B101=C100+D100; 以后就可以順利地進(jìn)行循環(huán)展開。相關(guān)鏈分析見下頁。,例6.8（P173）,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),20,例6.8（續(xù)）,,,,,,,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),21,顯式相關(guān)與隱式相關(guān) 同一變量名出現(xiàn)在多條語句中是顯式相關(guān)，可通過字符匹配來
17、識別 同一數(shù)組元素以不同的存儲別名出現(xiàn)在多條語句中是隱式相關(guān)，不能通過簡單的字符匹配來識別 什么是存儲別名 一個(gè)元素被不同的地址表達(dá)式訪問，如 Ai+5、Aj2-6、Ak 由于編譯時(shí)難以預(yù)測索引變量i、j、k將來的運(yùn)行值，故疑似存儲別名一律作相關(guān)看待，所在語句之間必須保持足夠距離，避免并行執(zhí)行 存儲別名判則適用條件數(shù)組是仿射的（affine） 仿射數(shù)組：訪問地址表達(dá)式均為一次函數(shù)，形如Aai+bj+c 非仿射數(shù)組：例如ABi,2. 存儲別名導(dǎo)致的隱式相關(guān)（GCD判則）,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),22,GCD判則（最大公因數(shù)，Greatest Common Divisor） 問題 給定
18、一維數(shù)組Am:n和任意整數(shù)j、k（mj，kn），地址表達(dá)式 Aaj+b 與 Ack+d 有沒有可能是同一個(gè)元素，即什么條件下滿足aj+b = ck+d 判則 如果GCD(c,a)可以整除(d-b)，可能存在存儲別名（疑似相關(guān)） 如果GCD測試的結(jié)果為假（不能整除），一定不存在存儲別名 判則之所以說“可能存在”，是因?yàn)槟繕?biāo)程序在運(yùn)行中，j、k的實(shí)際取值范圍也可能到不了滿足aj+b = ck+d的點(diǎn)。,2. 存儲別名導(dǎo)致的隱式相關(guān)（GCD判則）,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),23,例：6j+13與9k+1是否滿足GCD判則？ 解： GCD(c,a) = 3 ，(d-b) = -12，能夠整除
19、，可能存在存儲別名 驗(yàn)證： 對取值j = 0，1，2，和k = 0，1，2， ，有 6j+13 = 13，19，25，31，37，43，49，55，61， 9k+1 = 1，10，19，28，37，46，55，64，73， 顯然存在存儲別名。將b和d互換后也一樣（這時(shí)(d-b) = +12） 6j+1 = 1，7，13，19，25，31，37，43，49， 9k+13 = 13，22，31，40，49，58，67，76，85，,GCD判則成功的例子,,,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),24,例：4j+1與2k+4是否滿足GCD判則？ 解： GCD(c,a) = 2 ，(d-b) =
20、 3，不能整除，不存在存儲別名 驗(yàn)證： 對取值j = 0，1，2，和k = 0，1，2， ，有 4j+1 = 1，5，9，13，17，21，25，29，33， 2k+4 = 4，6，8，10，12，14，16，18，20， 未發(fā)現(xiàn)存儲別名。將b和d互換后也一樣（驗(yàn)證略）,GCD判則失敗的例子,,,,,,,,,,,,,,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),25,例6.9（P175）使用GCD測試方法判斷下面的循環(huán)中是否存在存儲別名。 for（i=1；i<=100；i=i+1） x2*i+3 = x2*i * 5.0； 解：在這個(gè)循環(huán)中，a = 2，b = 3，c = 2，d = 0， 那么G
21、CD(a,c) = 2，而d-b = -3。 由于2不能整除-3，因此沒有存儲別名，即無論i取何值，x2*i+3與x2*i都將表示數(shù)組x的不同元素。,GCD判則失敗的例子,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),26,在使用GCD測試之前，必須先對這段代碼進(jìn)行“規(guī)范化”修改下標(biāo)從1開始（不必要？），而且每次循環(huán)后增加1（ Hennessy教材3版第4章）。 例如學(xué)習(xí)指導(dǎo)書題6.15原循環(huán)代碼為 for (i=2; i<=100; i+=2) ai = a50*i + 1; 進(jìn)行規(guī)范化后的修改循環(huán)代碼為 for (i=1; i<=50; i++) a2*i = a100*i + 1; 再用GCD測試法，a=2，b=0，c=100，d=1，GCD(c,a)=2，(d-b)=1，(d-b) mod GCD(c,a)0，不能整除，所以該循環(huán)不存在循環(huán)攜帶的真數(shù)據(jù)相關(guān)。此題如果不先作規(guī)范化，則結(jié)論是“存在循環(huán)攜帶相關(guān)”。 習(xí)題6.7（注意學(xué)習(xí)指導(dǎo)書中對應(yīng)的題6.6答案是錯(cuò)的）,GCD測試之前要求循環(huán)代碼“規(guī)范化”,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),27,???,3. 數(shù)據(jù)相關(guān)處理???,2014.2.17,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),28,各次作業(yè)應(yīng)交的內(nèi)容,作業(yè)7（第8次課）,6.8(改)，6.7,
《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》電子教案(課7).ppt
