面向并行化的指針分析技術研究.pdf

1、人類對計算能力的需求永無止境，高性能計算水平逐漸成為世界強國競相追逐的焦點。并行化編譯作為高性能計算中不可或缺的一部分，能夠識別程序中不同層次、不同粒度的并行性，并自動生成高效的并行代碼。近年來，并行化技術在并行識別能力、并行編程模型、發(fā)掘方法和并行代碼生成等方面均取得了豐碩的成果，但仍然存在許多亟待解決的問題。在大量基準測試集和科學計算程序并行化實踐中的一個難點是：C、C++等程序的熱點循環(huán)中包含指針變量時，實施并行化變換無法取得理想

2、的加速效果。指針分析以程序分析為基礎，是一項關鍵的數據流分析技術，其分析結果影響并行優(yōu)化后程序的執(zhí)行效率。本文以并行識別與自動并行化系統SW-VEC的研發(fā)為背景，系統深入的研究了支撐并行化變換的指針分析相關關鍵技術，以此來改進編譯系統的并行化能力。
　　本研究主要內容包括：⑴在基于包含的指針分析技術中展開研究，對Narse優(yōu)先權約束評估算法中存在的局限性進行分析，提出了一種基于指向更新的優(yōu)先權指針分析技術。以指針的指向集更新信息確

3、定約束評估的候選集，避免了冗余的約束評估。通過構建約束依賴圖并以依賴關系確定約束評估的優(yōu)先權，簡化了優(yōu)先權評估模型。在基準測試集SPEC2000/SPEC2006上的實驗結果表明，該算法相比Narse優(yōu)先權算法在時間開銷和存儲開銷上具有明顯的性能提升。⑵在需求驅動的指針分析技術研究的基礎上，闡述了基于上下文無關語言可達的別名分析的主要思想，研究了一級流需求驅動的指針分析算法的不精確性。結合并行化的程序特征，提出了一種面向并行化的指針別名

4、分析算法。利用基準測試集SPEC2006中的C語言測試程序用例進行實驗評估，實驗結果表明該算法具有較高的計算精度和良好的可伸縮性，其分析的別名信息能夠顯著提升OpenMP自動并行化程序的加速比。⑶基于需求驅動的數據流分析和引用點對界技術，分析了需求驅動的指針對界分析的有效性。為提高分析的精度和效率，首先進行一種指針對界預分析。在需求驅動的指針對界分析框架內，先后研究了過程內分析、處理控制流、過程間分析以及算法優(yōu)化。在基準測試集和典型應用

5、上進行了實驗評估，驗證了所提出的指針對界分析技術的有效性。⑷在指針范圍分析相關研究的基礎上，提出了一種面向數據傳輸優(yōu)化的指針范圍分析技術。首先給出了需求驅動的指針范圍分析框架，定義了兩種指針范圍的表示形式：范圍描述符域和程序范圍描述符域。而后給出了計算指針范圍的算法流程，分別研究了計算數據范圍的轉移函數以及計算控制范圍的交函數和并函數，并通過擴大轉換和縮小轉換兩種操作進行優(yōu)化。最后在測試集上進行實驗評估，驗證了本文所提出的指針范圍分析技