這里在循環(huán)維度 k 上有個(gè)隱式的依賴，當(dāng)前迭代(i', j', k') 的 C[i'][j'] 計(jì)算依賴于上一次迭代 (i', j', k'-1) 計(jì)算得到的 C[i'][j']，所以距離向量為 [0, 0, k-(k'-1)=1]，所以在k 維度上無(wú)法并行。

對(duì)循環(huán)做變換

多面體模型中對(duì)循環(huán)優(yōu)化是通過(guò)對(duì)循環(huán)迭代空間做仿射變換實(shí)現(xiàn)的，下面我們介紹三種簡(jiǎn)單的變換，交換和傾斜。

以二層循環(huán)為例:

for(inti=1;i<=?2;++i)
for(intj=1;j<=?3;++j)
S[i][j]=...

對(duì)應(yīng)的每一次迭代的執(zhí)行順序如下圖，圖中的圓型就對(duì)應(yīng)每一次的迭代，序號(hào)就是原始執(zhí)行順序：

假設(shè)變換后的循環(huán)維度分別是 i' 和 j'。

循環(huán)交換

對(duì)應(yīng)的變換矩陣如下：

變換過(guò)程如下：

對(duì)應(yīng)的循環(huán)就變?yōu)椋?/p>

for(intj=1;j<=?3;++j)
for(inti=1;i<=?2;++i)
S[i][j]=...

對(duì)應(yīng)的迭代執(zhí)行順序如下：

圖中圓型的序號(hào)為變換前的原始執(zhí)行順序。

第一個(gè)執(zhí)行的坐標(biāo)是 (i'=1, j'=1)，對(duì)應(yīng)原始坐標(biāo)是 (i=1, j=1)，對(duì)應(yīng)圓型 1。

第二個(gè)執(zhí)行的坐標(biāo)是 (i'=1, j'=2)，對(duì)應(yīng)原始坐標(biāo)是 (i=2, j=1)，對(duì)應(yīng)圓型 4。

第三個(gè)執(zhí)行的坐標(biāo)是 (i'=2, j'=1)，對(duì)應(yīng)原始坐標(biāo)是 (i=1, j=2)，對(duì)應(yīng)圓型 2。

其他以此類推

循環(huán)反轉(zhuǎn)

對(duì)應(yīng)的變換矩陣如下，假設(shè)就對(duì)循環(huán) i 做反轉(zhuǎn)：

變換過(guò)程如下：

對(duì)應(yīng)的循環(huán)就變?yōu)椋?/p>

for(inti=-1;i>=-2;--i)
for(intj=1;j<=?3;++j)
S[i+3][j]=...

對(duì)應(yīng)的迭代執(zhí)行順序如下：

圖中圓型的序號(hào)為變換前的原始執(zhí)行順序。

第1個(gè)迭代 (i'=-1, j'=1) 對(duì)應(yīng)原始坐標(biāo) (i=2, j=1) ，對(duì)應(yīng)原始循環(huán)的圓型 4 。

第4個(gè)迭代 (i'=-2, j'=1) 對(duì)應(yīng)原始坐標(biāo) (i=1, j=1) ，對(duì)應(yīng)原始循環(huán)圓型 1 。

循環(huán)傾斜

對(duì)應(yīng)的變換矩陣如下：

變換過(guò)程如下：

對(duì)應(yīng)的循環(huán)就變?yōu)椋?/p>

for(intd=2;d<=?5;++d)
for(intj=max(1,d-2);j<=?min(3,d-1);++j)
inti=d-j;
S[i][j]=...

對(duì)應(yīng)的迭代執(zhí)行順序如下：

圖中圓型的序號(hào)為變換前的原始執(zhí)行順序。

第1個(gè)迭代 (d=2, j=1) 對(duì)應(yīng)原始坐標(biāo) (i=1, j=1) ，對(duì)應(yīng)原始循環(huán)的圓型 1 。

第2個(gè)迭代 (d=3, j=1) 對(duì)應(yīng)原始坐標(biāo) (i=2, j=1) ，對(duì)應(yīng)原始循環(huán)圓型 4 。

第3個(gè)迭代 (d=3, j=2) 對(duì)應(yīng)原始坐標(biāo) (i=1, j=2) ，對(duì)應(yīng)原始循環(huán)圓型 2 。

第4個(gè)迭代 (d=4, j=2) 對(duì)應(yīng)原始坐標(biāo) (i=2, j=2) ，對(duì)應(yīng)原始循環(huán)圓型 5 。

第5個(gè)迭代 (d=4, j=3) 對(duì)應(yīng)原始坐標(biāo) (i=1, j=3) ，對(duì)應(yīng)原始循環(huán)圓型 3 。

第6個(gè)迭代 (d=5, j=3) 對(duì)應(yīng)原始坐標(biāo) (i=2, j=3) ，對(duì)應(yīng)原始循環(huán)圓型 6 。

如何將串行執(zhí)行的循環(huán)轉(zhuǎn)換為可并行執(zhí)行

以下面的循環(huán)為例：

for(inti=1;i<=?N;?i++)?{
????for(intj=1;j<=?N;?j++)?{
????????A[i][j]?=?A[i-1][j]+A[i][j-1];
}
}

分析上其數(shù)據(jù)依賴分析可得其距離向量：

可知該循環(huán)在 i 和 j 維度上都無(wú)法并行執(zhí)行。

接下來(lái)嘗試對(duì)循環(huán)空間 i 和 j 做仿射變換，我們采用傾斜變換，其實(shí)這個(gè)是很經(jīng)典的一個(gè)并行方法了，稱之為對(duì)角線變換。

具體到多面體編譯技術(shù)的代碼的實(shí)現(xiàn)，是怎么自動(dòng)找到這個(gè)變換的過(guò)程我還沒(méi)完全弄懂，所以假設(shè)我們現(xiàn)在知道了是直接應(yīng)用傾斜變換：

代碼變?yōu)椋?/p>

for(intd=2;d<=?2*N;++d){
for(intj=max(1,d-N);j<=?min(N,?d?-?1);++j){
inti=d-j;
A[i][j]=A[i-1][j]+A[i][j-1];
}
}

接著分析數(shù)據(jù)依賴矩陣，這時(shí)候 A[i][j]= A[d-j][j] 的計(jì)算都只依賴于循環(huán) d 前一次迭代的計(jì)算而循環(huán) j 維度上沒(méi)有數(shù)據(jù)依賴，所以依賴矩陣為：

從依賴矩陣可知，變換后的循環(huán)可以在 j 循環(huán)維度上做循環(huán)。

上面的文字解釋可能有些抽象我們畫圖來(lái)輔助解釋，假設(shè)循環(huán)上界 N=5，則原始的循環(huán)迭代空間如下圖所示：

黑色實(shí)線箭頭表示每個(gè)計(jì)算 A[i][j] 的計(jì)算順序。

數(shù)據(jù)依賴關(guān)系如下：

紅色箭頭表示數(shù)據(jù)依賴。

則經(jīng)過(guò)傾斜變換后的循環(huán)迭代空間如下：

for(intd=2;d<=?2*5;++d){
for(intj=max(1,d-5);j<=?min(5,d-1);++j){
inti=d-j;
A[i][j]=A[i-1][j]+A[i][j-1];
}
}

其實(shí)就是對(duì)應(yīng)于原始空間上，按照對(duì)角線的順序去遍歷。

數(shù)據(jù)依賴如下：

從數(shù)據(jù)依賴上看，可以看到變換后在 j 維度上沒(méi)有數(shù)據(jù)依賴所以可以并行執(zhí)行。

最后在 j 維度上加上 omp 并行：

for(intd=2;d<=?2*5;++d){
#pragmaompfor
for(intj=max(1,d-5);j<=?min(5,d-1);++j){
inti=d-j;
A[i][j]=A[i-1][j]+A[i][j-1];
}
}

后記

這篇文章中對(duì)于多面體模型有并不少是個(gè)人理解，不一定準(zhǔn)確。多面體編譯技術(shù)個(gè)人感覺(jué)很復(fù)雜，在閱讀相關(guān)文獻(xiàn)和書籍的時(shí)候，還需要去搜過(guò)相關(guān)前置知識(shí)才能看懂大概。

而這篇學(xué)習(xí)筆記也僅僅是介紹了一些基本的入門概念，多面體編譯技術(shù)能做的事情并不僅僅局限于本文所介紹的循環(huán)變換發(fā)掘可并行部分，感興趣的讀者可以閱讀參考資料。

審核編輯 ：李倩