依賴分析與循環(huán)變換課件

1、 依賴分析是指令調(diào)度和數(shù)據(jù)cache優(yōu)化的一個(gè)重要的工具。依賴關(guān)系決定了保證程序正常執(zhí)行時(shí)的指令順序。其中包含對于兩個(gè)給定的寄存器或者內(nèi)存引用是否訪問了統(tǒng)一區(qū)域，和指令之間的資源沖突。依賴分析也用于程序的向量化和并行化等利用調(diào)整語句順序來提高性能的工作中。 依賴分類 控制依賴 數(shù)據(jù)依賴 S1 a = b +cS2if a 10 goto L1S3d = b * c;S4e = d + 1;S5 L1: d = e / 2; 流依賴 ：如果 S1 S2 并且前面的語句定值后面的語句使用那個(gè)值，這種就叫做流依賴，表示為 S1 f S2。 反依賴 ：如果S1 S2 并且S1使用S2設(shè)定的值，我們就說

2、這里存在反依賴，寫作S1 a S2 。 輸出依賴 ：如果S1 S2 并且它們都對同樣的變量賦值，我們就說這里存在輸出依賴，寫作S1 o S2 。 輸入依賴 ：如果S1 S2 并且它們都讀取同樣的值，我們就說這里存在輸入依賴，寫作S1 i S2。有一點(diǎn)要注意的就是輸入依賴對語句并沒有限制語句的執(zhí)行順序，但是它對數(shù)組元素的標(biāo)量替換有用。 一組依賴關(guān)系集合可以用一個(gè)有向圖來表示，我們把這圖叫做依賴圖。在圖中節(jié)點(diǎn)表示語句邊表示依賴關(guān)系。每條邊都被標(biāo)記來表示依賴類型，除了流依賴未被標(biāo)記?？刂埔蕾囃ǔ１缓雎缘舫强刂埔蕾囀莾蓚€(gè)節(jié)點(diǎn)之間的唯一依賴關(guān)系。 S1 a = b +cS2if a 10 goto L

3、1S3d = b * c;S4e = d + 1;S5 L1: d = e / 2;在依賴DAG中節(jié)點(diǎn)表示機(jī)器指令或者低等級(jí)的中間代碼，它的邊表示指令之間的依賴關(guān)系。一條從I1到I2的邊可能有如下幾種依賴關(guān)系：I1對一個(gè)I2用的寄存器或者地址寫值，I1 f I2；I1使用一個(gè)I2改變了值的地址或者寄存器；I1和I2對同一個(gè)地址或者寄存器賦值；我們不能確定I1是否能移動(dòng)到I2前，例如用不同寄存器r11和r1212訪問地址。除非我們可以肯定它們指向不同的地址，否則我們就認(rèn)定它們之間存在依賴關(guān)系。 如果I2必須等到I1執(zhí)行一些時(shí)鐘周期后才能執(zhí)行我們就說在DAG中I1是I2的前驅(qū)。在DAG中我們忽略掉

4、依賴邊的類型。而是用I1和I2之間正確執(zhí)行的最小時(shí)鐘周期間隔來標(biāo)記邊。例如I2必須等到I1執(zhí)行2個(gè)時(shí)鐘周期后才能執(zhí)行，我們就標(biāo)記這條邊為1。在例子中我們假設(shè)一個(gè)load指令要兩個(gè)周期完成 1 r3 = r15 (4)2 r4 = r15+4 (4)3 r2 = r3 r44 r5 = r125 r12 = r12 + 46 r6 = r3 * r57 r15+4 = r38 r5 = r6 + 2在例子中指令1和2是相互獨(dú)立的，因?yàn)樗麄冊L問的是不同的地址。指令3必須在它們后面，因?yàn)樗玫搅酥噶?，2賦值的寄存器。指令4和1，2是獨(dú)立的，它們是給不同的寄存器賦值。指令7必須在指令1 2 4 后面

5、，因?yàn)樗褂昧?的結(jié)果存在2訪問的地址并且有可能和4訪問的地址別名。4到8的邊是多余的因?yàn)橛幸粭l從4到6的邊和一條6到8的邊。但是如果4到8的邊如果是4個(gè)延遲那么這條邊就不算是多余的，因?yàn)?，2，4，5，6，7，8，3和1，2，4，5，6，8，7，3都是可行的，但是第一個(gè)要8個(gè)時(shí)鐘周期但是第二個(gè)需要9個(gè)時(shí)鐘周期。 為了對基本塊建立DAG我們需要兩個(gè)函數(shù) Latency: LIRInst x integer x LIRInst x integer - integer 和 Conflict: LIRInst x LIRInst - Boolean 定義如下 Latency(I1, n1, I2,

6、n2) 執(zhí)行I1的第n1個(gè)周期到開始執(zhí)行I2的第n2個(gè)周期的延遲。 和true I1I2Conflict(I1,I2) =false 如果 必須在 前執(zhí)行其他情況true I1I2Conflict(I1,I2) =false 如果必須在前執(zhí)行其他情況true I1I2Conflict(I1,I2) =false 如果必須在前執(zhí)行其他情況 我們使用資源向量。一個(gè)指令的資源向量就是一個(gè)指令執(zhí)行時(shí)連續(xù)用到的資源的數(shù)組。例如MIPS R4000浮點(diǎn)運(yùn)算有7個(gè)資源：A（mantissa Add）E(Exception test ), M（Multiplier first）N（Multiplier sec

7、ond stage）, R (Adder Round) , S (operand Shift), U (Unpack)。單精度的浮點(diǎn)加法 add (add.s)和乘法指令multiply (mul.s)有如下的資源向量 1234567Add.s US,AA,RR,SMul.s UMMMNN,AR例如計(jì)算Latency（mul.s, 4, add.s, 1）我們有下面的資源向量I1RV1 =MI2RV1 = UI1RV2 =NI2RV2 = S,AI1RV3 =N,AI2RV3 = A,RI1RV4 =RI2RV4 = R,SI1RV5 =I2RV5 = I1RV6 =I2RV6 = 可以計(jì)算得

8、到它們之間得延遲為2 循環(huán)的規(guī)范形式：每個(gè)循環(huán)的索引值從1開始每次遞增1到整數(shù)n.,并且語句只存在于最內(nèi)層循環(huán)里面 迭代空間：k層循環(huán)的k維離散笛卡爾空間稱為迭代空間。 1.n1 X 1.n2 X.X 1.nk for i1=1 to n1 dofor i2 to n2 do.for ik to nk do語句endfor.endforendfor 字典序 (lexicographical order):用來表示，例如： i11,.,ik1 i12,.,ik2當(dāng)且僅當(dāng)：j, 1 = j =k, i11 = i12, ., i(j-1)1 = i(j-1)2并且ij1 ij2 在迭代向量i11,

9、.,ik1是i12,.,ik2的前驅(qū)，當(dāng)且僅當(dāng)i11,.,ik1 i12,.,ik2 for i = 1 to 3 dofor j = 1 to 4 doS1t =x+y;S2ai,j = bi,j +ci,j;S3bi,j = ai,j * di+1,j + t;EndforEndfor在例子中語句的執(zhí)行次序如下：S2i, j-1 S3 i,jS2i,j S3i,j對應(yīng)的依賴關(guān)系如下：S2i, j-1 f S3 i,jS2i,j a S3i,j 距離向量:d = .這里di是整數(shù)，也就表示對于每一個(gè)索引向量i 有依賴距離d那么使用索引向量id的都依賴向量i； 方向向量：用來粗略的表示距離向量

10、和它的整數(shù)范圍，兩種常用的表示如下： 0,01,-,-1-, +=+-+=* 在我們進(jìn)行循環(huán)變化的時(shí)候最重要得一點(diǎn)就是要考慮循環(huán)內(nèi)兩個(gè)迭代之間是否存在依賴關(guān)系，如果有就需要知道那么它是那一種依賴關(guān)系。 依賴測試目的：證明循環(huán)內(nèi)沒有依賴存在，如果不能證明就要盡可能精確的卻定依賴類型for i =1 to 4 dobi = a3*i -5 +2.0a2*i +1 = 1.0/iendfor求同一迭代中是否存在依賴 ：2*i + 1= 3 *i -5且1= i =4 不動(dòng)迭代中是否存在迭代 ：2*i1 +1 = 3 *i2 -5且1=i1=4 1=i2=4 通常測試循環(huán)中是否存在依賴關(guān)系的問題可以看

11、作求解丟番圖方程，也就是滿足整數(shù)系數(shù)的給定不等式的整數(shù)解，這是一個(gè)NP完全問題。幸運(yùn)的是在實(shí)際執(zhí)行程序中下標(biāo)表達(dá)式通常比較簡單。 循環(huán)內(nèi)數(shù)組元素之間的依賴問題可以描述為:S: Xf1(i), , fd(i) S: X f1(i), , fd(i)測試在循環(huán)界限內(nèi)是否存在i, i, 使fk(i) = fk(i), k1:d 通常我們限定f()為線性函數(shù) 循環(huán)存在依賴關(guān)系當(dāng)且僅當(dāng)下面等式： 0,10,211*nnjjjjjjaaibbi和下面不等式：,11jjibi 且 ,21jjibi 對于j1,.,n同時(shí)滿足。依賴的類型是由具體數(shù)組X是被使用或者被定值所決定的。 for i = 2, 100

12、for j = 1, 100 s: ai+3j = s: = a2*ji+1 endforendfor 求解等式：i1+3 = 2*j2且 j1=i2+1；2 x 1001 yi2, j1=j2i1=i2, j1 1X -5 當(dāng)在不同迭代的時(shí)候： gcd(3,2) X (-5 1 + 3 - 2) - 1X -5 for i =1 to 4 dobi = a3*i -5 +2.0a2*i +1 = 1.0/iendfor當(dāng)在同一迭代，也就是方向“=”時(shí)：gcd(4-2) X (-5 1 + 3 - 2) - 2X -5 當(dāng)在不同迭代的時(shí)候： gcd(4,2) X (-5 1 + 3 - 2)

13、- 2X -5 for i =1 to 4 dobi = a4*i +2.0a2*i +1 = 1.0/iendfor 可分性和弱可分性是實(shí)際程序中常遇見的兩種訪問類型。依賴方程只有一個(gè)變量時(shí), 可分性測試是一種精確測試方法 例如:f(i, j) = 2 * j - 2f(i, j) = 5 * j -7可進(jìn)行可分性測試可分性測試條件下的依賴測試：a1*ij1 a2*ij2 = b2-b1l=ij1=u 且 l=ij2=u f(i, j) = i - 2f(i, j) = j -3不能進(jìn)行可分性測試 可分性測試滿足a1 = a2時(shí)，下標(biāo)表達(dá)式必須要滿足下面條件其中一個(gè)： a1=a2=0 并且

14、b1 = b2 (b1- b2)/a = U 符合可分性測試a1 = a2 并且符合第一種情況 a1 = a2 = 0 對于 s1 s2: b1 = b2 存在依賴 對于 s1 s3: b1 b2 不存在依賴 對于 s2 s3: b1 b2 不存在依賴for i = 1, 100 s1: a(2) = s2: = a(2) s3: a(5) = endfor 符合可分性測試a1=a2(-5-1)/3 = -2 4 滿足條件 (b1- b2)/a = U 所以 S1 S2存在依賴。for i =1 to 4 do.S1:bi = a3*i -5 +2.0S2:a3*i +1 = 1.0/i.en

15、dfor 對于弱可分性測試，下標(biāo)變量的線性表達(dá)式都有a1a2。 對于只有一個(gè)下標(biāo)等式的，可以建立有兩個(gè)未知數(shù)的線性等式。那么循環(huán)存在依賴關(guān)系當(dāng)且僅當(dāng) gcd(a1,a2)|(b2-b1),并且解要在循環(huán)界限內(nèi)。 當(dāng)有兩個(gè)等式集合a1,1*y = a2,1*x +(b2,1-b1,1)和a1,2*y = a2,2*x +(b2,2-b1,2） 如果a2,1/a1,1 = a2,2 /a1,2，那么當(dāng)且僅當(dāng)(b2,1-b1,1)/a1,1 = (b2,1 b1,2)/a1,2 時(shí)原等式有解 如果a2,1/a1,1 a2,2/a1,2 那么這里存在一個(gè)解 上面兩種情況解都要滿足循環(huán)邊界的不等式限制

16、有n（n=3）個(gè)等式集合的時(shí)候,那么n-2個(gè)等式是多余的，提供了冗余的決策信息對于數(shù)組g 我們要解兩個(gè)獨(dú)立的等式 2*x = y+1z = 3 *w可以求得當(dāng)n=3時(shí)候有解對數(shù)組h 我們必須同時(shí)滿足兩個(gè)等式x= y+2x=2*y-2求得唯一解 x= 6 y= 4所以當(dāng)且僅當(dāng)n=6時(shí)h有依賴關(guān)系for i= 1, n for j =1 , n fi=g2*i,j+1.0 gi+1,3*j=hi,j 1.5 hi+2,2*i - 2 = 1.0/i endforendfor其他測試方法：擴(kuò)展GCD測試強(qiáng)SIV和 弱SIV測試Delta測試Acyclic測試Power測試簡單循環(huán)剩余測試Fourie

17、r-Motzkin測試Constraint-Matrix測試Omega測試相同點(diǎn)保守不同點(diǎn)復(fù)雜度不同精確度不同 程序依賴圖PDG是由控制依賴圖和數(shù)據(jù)依賴圖構(gòu)成的，PDG中的節(jié)點(diǎn)可以是基本塊也可以是語句或者其他等級(jí)的表示。我們在前面已經(jīng)介紹了數(shù)據(jù)依賴圖，下面我們主要講控制依賴圖。 在控制依賴圖中用帶謂詞的程序作為它的根節(jié)點(diǎn)或者中間節(jié)點(diǎn)，無謂詞的作為它的葉節(jié)點(diǎn)。節(jié)點(diǎn)n控制依賴節(jié)點(diǎn)m當(dāng)且僅當(dāng)： 存在一條控制流路徑從m到n ，路徑上的節(jié)點(diǎn)除了m外都被n 后支配。 n 不后支配m。 構(gòu)建CDG基本步驟： 在程序流圖的入口節(jié)點(diǎn)entry上加入start節(jié)點(diǎn)，它的“Y”邊走向entry，“N”邊到達(dá)exit

18、。我們叫這圖為G+ 建立G+的后支配圖，建立邊集合S 其中m-n 是n沒有后支配m的 找出m和n的在后支配樹上的最早公共前驅(qū)l 那么所有從l到n的路徑上的節(jié)點(diǎn)除了l以外都控制依賴m。后支配圖S集合 ：start- entry, B1-B2, B1-B3, B4-B6startB1R1B3B4B5R3R2YB6B2YNYregion節(jié)點(diǎn)：把有同一種控 制依賴的放在一塊。 循環(huán)變換被用來重新排列程序語句和循環(huán)迭代的順序。變換必須保證程序原來的行為不變，使得循環(huán)有助于做其他優(yōu)化。 循環(huán)變換最重要的兩點(diǎn)就是合法性和變換的效果。 循環(huán)變換的主要目的 ： 程序獲取更多的優(yōu)化機(jī)會(huì) 提高程序的指令局部性和數(shù)據(jù)

19、局部性 改變程序的依賴關(guān)系發(fā)掘更多的并行機(jī)會(huì)使程序向量化 主要是將循環(huán)內(nèi)的條件判斷語句外提。優(yōu)點(diǎn)是減少了條件判斷語句的執(zhí)行頻率。缺點(diǎn)是使得循環(huán)結(jié)構(gòu)變得更加復(fù)雜。使代碼膨脹。DO I = 1 , NIF test THEN statements DO I = 1 , N IF test THEN statements then statements then statements ELSE more statements else statements ENDDO ENDIFELSE more statements DO I = 1 , NENDDO statements else statem

20、ents more statements ENDDOEND IF 將一個(gè)循環(huán)按索引集分成兩部分，移去循環(huán)中對索引值的條件測試。增加程序的并行性 DO I = 1 , N A(I) = A(I) + A(5) ENDDO 將上面循環(huán)分裂為兩個(gè) DO I = 1 , 5A(I) = A(I) + A(5) ENDDO DOALL I = 6 , NA(I) = A(I) + A(5) ENDDO 當(dāng)標(biāo)量在循環(huán)中先被賦值然后又在后面的語句中被使用的時(shí)候就會(huì)形成流依賴，并且從使用到賦值又可以形成反依賴。這種反依賴會(huì)使得其他循環(huán)變換變得困難。標(biāo)量擴(kuò)展就是將循環(huán)中的標(biāo)量擴(kuò)展成為向量，改變程序的依賴性有利于

21、進(jìn)行其他循環(huán)變換。for i = 1 to n dot = ai + bic i= t + 1/tendfor變換后if n1 thenallocate txnfor i = 1 to n dotxi = ai + bic i= txi + 1/txiendfort = txnendif 循環(huán)剝皮：去掉循環(huán)的第一次或者最后一次迭代。 對于某些循環(huán)第一次或者最后一次迭代的計(jì)算過程與其它的迭代不同 可以去掉循環(huán)里面的對索引值的條件語句 有利于實(shí)施循環(huán)合并等其他循環(huán)變化DO I = 1 , NIF (I 1) A(I) = 1 continueA(I) = A(I-1)*2ENDDO 循環(huán)剝皮 A(

22、1) = 1DO I = 2, NA(I) = A(I-1)*2ENDDO 將兩個(gè)循環(huán)合并成為一個(gè)循環(huán)，減小循環(huán)的控制開銷。for j= .dobody1endforfor j= . dobody2endfor 循環(huán)合并后:for j=. dobody1body2endforfor i =1 ,99 doai = bi +1endforfor i = 1 ,98 doci = ai+1 *2endfor進(jìn)行循環(huán)剝皮ai = b i +1for i = 2, 99 doai = bi +1 endforfor i = 1 ,98 doci = ai +1*2endfor循環(huán)合并i =1ai =

23、bi +1for ib =0 , 97i = ib +2ai = bi +1i = ib +1ci = ai +1*2endforid 1 = iu 循環(huán)合并必須要滿足條件： 兩個(gè)循環(huán)是相鄰的 并且兩循環(huán)的控制條件要一致（如不一致可以通過循環(huán)變換實(shí)現(xiàn)一致） 兩個(gè)循環(huán)語句間沒有方向?yàn)?的依賴 把一個(gè)循環(huán)分割成兩個(gè)或者更多的小循環(huán)，這個(gè)是循環(huán)合并的逆過程。通過變成更小的循環(huán)可以減少指令cache的壓力，可以提高內(nèi)存的局部性。循環(huán)分割要保證原有的環(huán)狀依賴關(guān)系不能被破壞。在原循環(huán)的依賴圖中的強(qiáng)連通子圖上的節(jié)點(diǎn)應(yīng)該被分割到同一子循環(huán)中去。 DO I = 1 , NS1: A(I) = B(I + 2)

24、+ 1S2: C(I) = B(I - 1) + F(I)S3: B(I) = A(I - 1) + 2S4: D(I) = D(I + 1) + B(I - 1)ENDDO進(jìn)行循環(huán)分割后：DO I = 1, NS1: A(I) = B(I-2) + 1S3: B(I) = A(I-1) + 2ENDDODO I = 1, NS2: C(I) = B(I-1) + F(I)ENDDODO I = 1, NS4: D(I) = D(I+1) + B(I-1)ENDDO 利用幺模矩陣進(jìn)行循環(huán)變換,進(jìn)行變換的時(shí)候必須保證幺模矩陣T和循環(huán)中的距離向量d 有 Td0。 幺模變換可以進(jìn)行循環(huán)反轉(zhuǎn)，交換，傾

25、斜 將循環(huán)內(nèi)外層交換位置。有助于發(fā)現(xiàn)程序的并行性，將可并行化的循環(huán)交換到外層。還能使程序向量化，將可向量化的循環(huán)交換到內(nèi)層。提高程序的數(shù)據(jù)局部性。有助于實(shí)施其他循環(huán)變換 For i = . doFor j = . doBody1Endfor Endfor 變化矩陣為 For j = . doFor i = . doBody1Endfor Endfor0110 循環(huán)反轉(zhuǎn)是改變循環(huán)的執(zhí)行順序，讓其反轉(zhuǎn)執(zhí)行。循環(huán)反轉(zhuǎn)的合法性：對于forall, dopar, dosingle類型的循環(huán)進(jìn)行反轉(zhuǎn)一直都是合法的，但是對于串行循環(huán)只有在循環(huán)的迭代空間沒有依賴關(guān)系時(shí)才能進(jìn)行循環(huán)反轉(zhuǎn)變換。循環(huán)反轉(zhuǎn)可以增加循環(huán)

26、合并的機(jī)會(huì)。DO I = 1 , N A(I) = B(I) + 1 C(I) = A(I) /2 ENDDO DO I = 1 , N D(I) = 1 / C(I+1)ENDDO變換矩陣DO I = N, 1 A(I) = B(I) + 1 C(I) = A(I) /2 D(I) = 1 / C(I+1)ENDDO 1001 循環(huán)傾斜是為了改變循環(huán)中存在的依賴關(guān)系的方向，發(fā)掘更多的并行性，為其它循環(huán)變換提供便利 幺模矩陣： 或 f 為傾斜因子，考慮到傾斜效果，傾斜因子一般用1或 2 循環(huán)傾斜僅改變循環(huán)迭代空間的形狀，但不改變循環(huán)執(zhí)行的次序101f101f DO I=1，N DO J=1，N

27、S: A（I，J）=A（I-1，J）+A（I，J-1） ENDDO ENDDO使用么模變換矩陣 后循環(huán)迭代空間的形狀被改變 DO I = 1，N DO J = I+1，I+NS: A(I,J-I) = A( I-1,J-I) + A(I,J-I-1) ENDDO ENDDO 1011 循環(huán)分段：將一個(gè)單層循環(huán)分成兩個(gè)嵌套循環(huán) 外層循環(huán)把原迭代空間分成幾個(gè)不同的段，一個(gè)段中含有多個(gè)原循環(huán)的迭代 內(nèi)層循環(huán)則執(zhí)行原循環(huán)的迭代for I = 1 , N for Is = 1 , N , sbody(I) for I = Is , min(N , Is + s 1)endforbody(I) endfo

28、r endfor 循環(huán)分段特性： 循環(huán)分段總是合法的，分段后保持原循環(huán)的可向量化（并行化）特性。 對該循環(huán)的外層循環(huán)或內(nèi)層循環(huán)存在的依賴關(guān)系不產(chǎn)生影響對依賴關(guān)系的影響：設(shè)依賴距離為d，分段的大小為 如果d和s是常數(shù)：變換后的依賴距離為(d div s, d mod s)，如果d mod s 還有一個(gè)依賴距離為(d div s + 1, -(s d) mod s); 如果d和s不是常數(shù)：原依賴方向新依賴方向( , *) (= , ( , *) (= , ) 循環(huán)分段作用： 并行優(yōu)化，將迭代次數(shù)多的可并行循環(huán)分段，在內(nèi)外層分別實(shí)施不同的并行優(yōu)化。 向量優(yōu)化，使分段后內(nèi)層循環(huán)長度恰為向量長度，有助向

29、量代碼的生成 提高數(shù)據(jù)局部性 與循環(huán)分段差異： 循環(huán)分段： 用于單層循環(huán) 每段的起點(diǎn)是由段長和原循環(huán)的索引值下界確定的 循環(huán)分塊： 用于嵌套循環(huán) 每塊的起點(diǎn)獨(dú)立于原循環(huán)的索引值下界 分塊： It塊循環(huán)， I基本循環(huán), ts是分塊大小， to 偏移值for I = l0 , hi for It = floor(l0 to)/ ts) * ts + to , floor(hi to)/ ts) * ts + to for I = max(l0 , It) , min(hi , It + ts- 1)原循環(huán)：for I = 1 , 50 for J = I , 60 A(I , J) = A(I , J) + 1 endforendfor循環(huán)分塊后：塊大小ts = 20,偏移t0 = 5for It = -15