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

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

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

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

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

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