[發(fā)明專利]一種基于謂詞的自動并行優(yōu)化方法

無效

• 申請?zhí)枺?/td>: 201010281799.8
• 申請日: 2010-09-15
• 公開（公告）號: CN101944040A
• 公開（公告）日: 2011-01-12
• 發(fā)明（設(shè)計）人: 楊克嶠;李弋;臧斌宇
• 申請（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

1.一種基于謂詞的自動并行優(yōu)化方法，其特征在于基本步驟為：(1)謂詞的構(gòu)建；(2)基于謂詞構(gòu)建并行循環(huán)版本；其中：

謂詞的構(gòu)建，是依據(jù)傳統(tǒng)的數(shù)組數(shù)據(jù)流分析和循環(huán)依賴性分析，通過程序的已知信息推導(dǎo)出并行謂詞，消除循環(huán)的簡單依賴，發(fā)掘循環(huán)結(jié)構(gòu)的并行潛力；

基于謂詞構(gòu)建并行循環(huán)版本，是在謂詞的約束條件下，判斷嵌套循環(huán)能否最外層完全并行；如果能夠最外層完全并行，則將謂詞作為運行時的并行條件，創(chuàng)建循環(huán)結(jié)構(gòu)的并行版本；否則，放棄假設(shè)的謂詞。

2.根據(jù)權(quán)利要求1所述的基于謂詞的自動并行優(yōu)化方法，其特征在于具體操作步驟如下：

第一，將源程序轉(zhuǎn)化為編譯器中間表示

首先將源程序轉(zhuǎn)變成中間表示形式，程序的中間表示是以結(jié)構(gòu)化形式描述程序的抽象語法樹結(jié)構(gòu)，并記錄在程序分析和優(yōu)化過程中收集和產(chǎn)生的各種信息，為程序分析、變換和優(yōu)化的各個階段提供所需的程序信息支持；

第二，數(shù)組數(shù)據(jù)流的依賴性測試

采用已有的數(shù)組數(shù)據(jù)流分析方法，對兩層嵌套循環(huán)中可能存在的數(shù)據(jù)依賴進行分析，其步驟為：

構(gòu)建循環(huán)邊界與數(shù)組下標(biāo)的等式

首先找出兩層嵌套循環(huán)的代碼中可能存在數(shù)據(jù)依賴的定義，設(shè)兩層嵌套循環(huán)的下標(biāo)分別為i和j，存在數(shù)組引用對：對a數(shù)組的寫引用a[A1i+B1j+C1]和對a數(shù)組的讀引用a[A2i+B2j+C2]；由數(shù)組a的定義和引用關(guān)系，建立如下等式：

A1i?+?B1j+?C1?=?A2i?+B2j?+?C2??

和限制條件不等式：

m<=?i?<=n????????????????????????????????????????????????

x<=?j?<=y

將等式寫成如下矩陣的形式：?

（A1?-?A2，B1?–?B2）?=?C2?–?C1

即Av?＝?c，這里v=<i,j>,?c=<C2?–?C1>

依據(jù)等式系統(tǒng)，進行數(shù)組數(shù)據(jù)流的依賴性測試，對上面的等式的測試過程如下：

?A????????????????????I

（A1?-?A2??B1?–?B2）???

把A的第一列*?加到第二列，得到：

（A1?–?A2??0）???

D????????????????????????U

求解等式Dt?=?c，得t?=?<C2?–?C1,?t2>，此時<i,?j>?=?Ut，因此

i=?

j?=?t2

依據(jù)條件不等式

m<=??<=n

x?<=?t2?<=?y

得到最終判定不等式：??????????????

?<=t2?<=?

x?<=?t2?<=?y

若?x,y<=或?<=x,y，則t2無解，a數(shù)組的訪問沒有依賴；?

謂詞構(gòu)造

????將不等式系統(tǒng)中最后判定的不等式轉(zhuǎn)化為使得數(shù)組數(shù)據(jù)流無依賴的并行謂詞，即將最終判定條件轉(zhuǎn)化為條件謂詞x,y<=或?<=x，y；并基于該條件謂詞更新循環(huán)信息，繼續(xù)后續(xù)并行優(yōu)化分析；

第三，判斷能否對嵌套循環(huán)最外層進行完全并行

基于更新后循環(huán)迭代信息，進行相關(guān)性測試，判定能否嵌套循環(huán)最外層的完全并行；如果能夠完全并行，則采納構(gòu)建的并行謂詞，并以該謂詞作為運行時的并行執(zhí)行條件，生成并行循環(huán)結(jié)構(gòu)；

第四，將中間表示翻譯成帶OpenMP標(biāo)注的并行程序

采用源到源的程序轉(zhuǎn)換，將串行程序優(yōu)化成帶OpenMP并行指示的并行程序；具體是把程序翻譯成如下形式：

IF?((?y?.le.)?.or.

?(x?.ge.??.and.?y?.ge.?))?THEN

#pragma?parallel?do

嵌套循環(huán)程序

ELSE

嵌套循環(huán)程序

ENDIF。