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

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

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

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

0 引 言

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

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

1 智能掃描分析

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