基于人工智能搜索和數(shù)據(jù)依賴分析的程序并行化

摘要： 主要研究了自動并行化中的前端分析技術(shù)，引入了人工智能搜索方法，并且對其進行改進，實現(xiàn)了在評估函數(shù)支持下進行廣度和深度搜索的方法。在前端分析的基礎(chǔ)上探討了傳統(tǒng)的數(shù)據(jù)依賴分析方法，針對其不足之處出現(xiàn)的數(shù)組數(shù)據(jù)流分析技術(shù)，對其流程圖算法進行描述，并且對終寫樹和寫寫樹的思想加以實例說明。這一流程經(jīng)過測試后可以很好地提高程序并行化的效率。

關(guān)鍵詞：程序并行化； 人工智能搜索； 評估函數(shù)； 數(shù)據(jù)依賴關(guān)系

中圖分類號： TN911?34 文獻標(biāo)識碼： A 文章編號： 1004?373X（2013）06?0001?03

0 引 言

并行性分析作為自動并行化系統(tǒng)的重要組成部分，它的基礎(chǔ)是前端分析和數(shù)據(jù)依賴關(guān)系的分析。前端分析就是對讀入的程序進行掃描分析；數(shù)據(jù)依賴分析的是語句及變量的之間的數(shù)據(jù)依賴關(guān)系。程序并行化就是在掃描中對程序進行初步并行性分析，然后根據(jù)數(shù)據(jù)依賴關(guān)系，判斷循環(huán)并行的可能性。

文中探討了人工智能掃描策略，并且對已有策略進行改進。為了實現(xiàn)大型程序中循環(huán)級并行性檢測得到可靠的、精確的數(shù)據(jù)依賴關(guān)系分析，文中針對傳統(tǒng)從數(shù)據(jù)依賴關(guān)系分析的不足研究了精確的數(shù)據(jù)依賴關(guān)系分析技術(shù)——數(shù)組數(shù)據(jù)流分析技術(shù)。

1 智能掃描分析

前端分析就是對讀入的串行程序進行掃描，由于程序有很多分支，掃描時就可以分多次掃描，每次掃描的不同內(nèi)容就是相當(dāng)于搜索路徑不同，可以通過人工智能搜索來實現(xiàn)。本文采用的掃描方法是iterative hill climbing method，算法思想是：

從一般的情況進行考慮，p的值是不會接近的，固應(yīng)該設(shè)置一個臨界值。在程序并行化智能搜索中，制定如下策略：初始階段的搜索，控制p值使其偏大，在程序的搜索過程中向深度方向進行，目的是為盡快接近目標(biāo)；當(dāng)進入到一定階段，搜索到一定程度后，應(yīng)調(diào)整使p值變小，廣度方向應(yīng)成為搜索方向的選擇，目標(biāo)結(jié)點要避免錯過，直至搜索成功完成。

2 數(shù)據(jù)依賴分析

建立LWT樹的方法是可以實現(xiàn)將依賴關(guān)系精確到具體數(shù)值的，這樣就為循環(huán)嵌套數(shù)組分析程序自動并行化提供了更高效的方法，同時也成為代碼生成和通信優(yōu)化的關(guān)鍵依據(jù)。

3 結(jié) 語

本文介紹的人工智能掃描方法中，針對已優(yōu)化的算法進行進一步改進，在其中探討了基于評估函數(shù)的結(jié)合深度和廣度搜索的智能搜索算法，在一定程度上解決了花費時間較多、占用很大存儲空間的問題。并且還探討了優(yōu)于傳統(tǒng)數(shù)據(jù)依賴關(guān)系分析的算法——數(shù)組數(shù)據(jù)流分析算法，根據(jù)其算法流程圖就終寫樹和寫寫樹進行了實例分析。這兩方面技術(shù)的改進能夠很好的提高程序并行化的效率。

參考文獻

[1] 王姍姍，趙榮彩，張平.對SUIF中依賴關(guān)系分析技術(shù)的研究與改進[J].計算機工程，2006，32（7）：89?91.

[2] Stanford Compiler Group. SUIF compiler system [M]. Versionl.0. US： Standford University， 1994.

[3] DONG Chun?li， ZHAO Rong?cai. An improving computation and data decomposition [C]// Proceedings of DCABES. [S.l.]： DCABES， 2006： 111?116.

[4] 張平.并行化編譯器中并行程序自動生成和性能優(yōu)化技術(shù)研究[D].鄭州：信息工程大學(xué)，2006.

[5] 龔雪容，生擁宏，沈亞楠.串行程序并行化中計算代碼與同步通信代碼的自動生成[J].計算機應(yīng)用與軟件，2008（1）：91?92.

[6] 沈志宇.并行編譯方法[M].北京：國防工業(yè)出版社，2000.

[7] 張磊，王廣生.運動模糊圖像重構(gòu)的算法及其并行化處理研究[J].現(xiàn)代電子技術(shù)，2008，31（10）：145?147.