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

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

關鍵詞：程序并行化； 人工智能搜索； 評估函數； 數據依賴關系

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

0 引 言

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

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

1 智能掃描分析

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

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

2 數據依賴分析

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

3 結 語

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

參考文獻

[1] 王姍姍，趙榮彩，張平.對SUIF中依賴關系分析技術的研究與改進[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] 張平.并行化編譯器中并行程序自動生成和性能優化技術研究[D].鄭州：信息工程大學，2006.

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

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

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