【摘要】：在分布存儲(chǔ)結(jié)構(gòu)的計(jì)算機(jī)系統(tǒng)中,盡可能地降低處理器間的通信開銷、提高并行程序的執(zhí)行效率是并行化編譯必須要考慮的問題。目前的并行化技術(shù)主要針對(duì)循環(huán)級(jí)并行,循環(huán)中的數(shù)組是進(jìn)行通信優(yōu)化的主要對(duì)象。傳統(tǒng)的依賴關(guān)系分析只能確定并行程序中需要通信的位置,不能確定所需通信的數(shù)組區(qū)域,以此為依據(jù)生成的通信代碼中包含大量冗余通信。精確的數(shù)組數(shù)據(jù)流分析所得的信息能夠作為精確數(shù)據(jù)通信代碼生成的依據(jù),但分析的范圍局限在單個(gè)循環(huán)內(nèi)部,無法消除跨循環(huán)邊界的數(shù)據(jù)依賴關(guān)系引起的冗余通信。基于傳統(tǒng)數(shù)據(jù)流分析進(jìn)行通信優(yōu)化可以獲得范圍更廣的數(shù)據(jù)流信息,但優(yōu)化對(duì)象只能精確到標(biāo)量,無法對(duì)數(shù)組中的單個(gè)元素做進(jìn)一步的分析。 本文針對(duì)分布存儲(chǔ)系統(tǒng)并行化編譯中的通信優(yōu)化問題,設(shè)計(jì)并實(shí)現(xiàn)了全局?jǐn)?shù)組數(shù)據(jù)流分析算法。首先,對(duì)比了語法制導(dǎo)求解和迭代求解兩種主要的數(shù)據(jù)流信息求解方法,在自動(dòng)并行識(shí)別工具SW-KAP中間表示的基礎(chǔ)上擴(kuò)展了控制流圖,構(gòu)建了全局?jǐn)?shù)據(jù)流分析的框架；其次,深入研究了數(shù)組區(qū)域的線性不等式表示和循環(huán)中數(shù)組的終寫關(guān)系分析,提出了一種能夠消除冗余通信的暴露集求解算法,并在SW-KAP中增加了對(duì)讀引用的輸入依賴和流依賴關(guān)系的分析,實(shí)現(xiàn)了循環(huán)中數(shù)組暴露集的自動(dòng)求解；第三,結(jié)合全局?jǐn)?shù)據(jù)流分析和循環(huán)內(nèi)的精確數(shù)組數(shù)據(jù)流分析,設(shè)計(jì)并實(shí)現(xiàn)了全局?jǐn)?shù)組數(shù)據(jù)流分析算法,獲得了過程內(nèi)跨越循環(huán)邊界的精確數(shù)組數(shù)據(jù)流信息。 本文所述算法已在自動(dòng)并行識(shí)別工具SW-KAP中實(shí)現(xiàn),全局?jǐn)?shù)組數(shù)據(jù)流分析結(jié)果為編譯器后端實(shí)現(xiàn)精確數(shù)據(jù)通信代碼的生成提供了必要信息,測(cè)試結(jié)果表明算法設(shè)計(jì)正確,能夠提供精確的數(shù)組通信信息,有效降低了自動(dòng)并行識(shí)別生成的并行程序中的通信代價(jià)。
【圖文】：

于寫引用RZ，，使用LWT算法就可獲得R，依賴于R:的范圍。經(jīng)過前面的分析可知，數(shù)組終寫關(guān)系分析需要對(duì)自反輸出依賴關(guān)系和不同寫引用之間的單向輸出依賴關(guān)系進(jìn)行分析。算法流程如圖18所示:首先對(duì)寫引用進(jìn)行自干擾分析，將寫引用自身對(duì)同一數(shù)組元素的多次訪問從非自干擾空間中去除，只留下一次訪問;然后進(jìn)行輸出依賴分析，將該寫引用與其它寫引用之間有依賴關(guān)系的數(shù)組元素從自干擾空間中去除。在最后得到的終寫迭代空間中，所有被訪問的數(shù)組元素都不會(huì)在循環(huán)內(nèi)被再次修改。寫寫引用集合J，外層循環(huán) 環(huán)迭 迭代空間了 了從從寫引用集合刁中取出一 一 個(gè) 個(gè)寫引用」，，4=.4二毛 毛 對(duì)對(duì)毛進(jìn)行自干擾分析得到 到 其其非自干擾迭代空間編 編 林林留x進(jìn)行輸出依賴分析得 得 到 到其終寫迭代空間 Ilwww將將二元組(志，IltJ寫入中間 間 注注釋
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2009
【分類號(hào)】：TP338.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 謝衛(wèi)，劉鍵;多變量數(shù)組下標(biāo)表達(dá)式的分解與相關(guān)性測(cè)試[J];華中理工大學(xué)學(xué)報(bào);1994年06期

2 孫彤,李三立,李曉明;并行化編譯中的一種集成優(yōu)化方法[J];軟件學(xué)報(bào);1996年12期

3 朱根江，謝立，孫鐘秀;一種基于非正規(guī)域的區(qū)域依賴關(guān)系分析法[J];計(jì)算機(jī)學(xué)報(bào);1994年03期

4 臧斌宇,陳彤,張瑜,朱傳琪;有效的數(shù)組私有化方法:相關(guān)-覆蓋方法[J];計(jì)算機(jī)學(xué)報(bào);2000年01期

5 謝幸,陳國良,武繼剛;分布存儲(chǔ)并行機(jī)上的自動(dòng)數(shù)據(jù)布局優(yōu)化模型[J];計(jì)算機(jī)研究與發(fā)展;2000年10期

6 胡世亮,臧斌宇,凌冰,朱傳琪;數(shù)據(jù)流分析中的區(qū)域覆蓋技術(shù)[J];軟件學(xué)報(bào);2000年03期

7 任華;趙榮彩;張平;孟然;;基于精確數(shù)組數(shù)據(jù)流分析框架的通信優(yōu)化[J];計(jì)算機(jī)工程與應(yīng)用;2006年36期

8 馬國凱,王欣[C,王鵬,臧斌宇,朱傳琪;利用U模變換增加并行粒度與改善數(shù)據(jù)訪問局部性的方法[J];計(jì)算機(jī)學(xué)報(bào);2004年04期

9 陳清萍;李曉峰;鄭世榮;;一種基于分解變換的并行化編譯新技術(shù)[J];計(jì)算機(jī)科學(xué);1998年01期

10 劉曉嫻;趙榮彩;梁玲;;消除冗余通信的暴露集求解算法[J];計(jì)算機(jī)工程;2009年11期

相關(guān)博士學(xué)位論文 前2條

1 王軼然;分布式主存系統(tǒng)上自動(dòng)數(shù)據(jù)和計(jì)算分解和相關(guān)研究[D];中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2006年

2 張平;并行化編譯器中并行程序自動(dòng)生成和性能優(yōu)化技術(shù)研究[D];解放軍信息工程大學(xué);2006年

相關(guān)碩士學(xué)位論文 前3條

1 劉曉嫻;全局?jǐn)?shù)組數(shù)據(jù)流分析技術(shù)的研究與實(shí)現(xiàn)[D];解放軍信息工程大學(xué);2009年

2 任華;數(shù)組數(shù)據(jù)流分析算法的優(yōu)化和數(shù)組私有化技術(shù)的研究與實(shí)現(xiàn)[D];解放軍信息工程大學(xué);2007年

3 丁銳;分布存儲(chǔ)結(jié)構(gòu)的通信代碼自動(dòng)生成與優(yōu)化[D];解放軍信息工程大學(xué);2009年

本文編號(hào)：2588738