[發明專利]一種基于謂詞的自動并行優化方法

無效

• 申請號: 201010281799.8
• 申請日: 2010-09-15
• 公開（公告）號: CN101944040A
• 公開（公告）日: 2011-01-12
• 發明（設計）人: 楊克嶠;李弋;臧斌宇
• 申請（專利權）人: 復旦大學
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

技術領域

本發明屬于程序編譯技術領域，具體涉及一種自動并行優化方法。

背景技術

循環是程序中蘊含并行性最豐富的一種結構，也往往是程序執行最耗時的部分。對串行程序并行優化的實質是針對循環體的并行性分析。并行性分析的目的是找出串行程序中適合并行優化的循環體，并且保證修改后的并行程序與原串行程序保持相同的語義。并行性分析根據數據依賴分析的結果，盡可能多的發掘程序中的并行性，以便并行優化工作可以從中權衡取舍，獲得一個全局較優的并行優化方案。

數據依賴分析是一個整數線性規劃問題，因此它不可能有精確且有效的解決方案。實際程序中的循環結構一般也比較復雜，其中含有若干影響并行優化的依賴關系。當含有無法確定的依賴信息時，無法通過循環變換技術來消除依賴。例如程序中存在一些編譯時無法確定的信息出現在嵌套內層循環的上下界或數組訪問的函數中時，分析器就無法精確計算嵌套循環體內數組依賴信息，如數組的定義-使用信息、定義是否覆蓋可能使用，這就限制了對外層嵌套循環的并行識別。只有當一個串行循環內嵌套的所有并行循環包含的數組定義和引用之間都不存在數據依賴，那么并行結構可以直接擴展到該串行循環的最外層。循環信息的不精確使得依賴分析保守認為循環存在簡單依賴，因而無法并行優化。

本發明提出基于謂詞的自動并行優化方法，依據已知程序信息推導可并行條件，提升對簡單依賴循環的并行優化效果。一般情況下，用戶程序的循環攜帶依賴關系比較簡單，復雜的情況并不常見，因而謂詞并行優化技術具備一般性，假設的并行條件在程序的實際執行中的命中率比較高。

發明內容

本發明的目的在于提出一種基于謂詞的自動并行優化方法，以消除循環體的數據依賴，實現對循環結構的自動并行優化。

本發明提出的基于謂詞的自動并行優化方法，主要包括：(1)謂詞的構建；(2)基于謂詞構建并行循環版本。

謂詞的構建，是依據傳統的數組數據流分析和循環依賴性分析，通過程序的已知信息推導出并行謂詞，消除循環的簡單依賴，發掘循環結構的并行潛力；

基于謂詞構建并行循環版本，是在謂詞的約束條件下，判斷嵌套循環能否最外層完全并行，如果能夠最外層完全并行，則將謂詞作為運行時的并行條件，創建循環結構的并行版本；否則，放棄假設的謂詞。

本發明提出的基于謂詞的自動并行優化方法，依據程序的多種特征，通過假設并行條件謂詞，構造一個可并行的循環版本；運行時，程序依據構造的謂詞條件，決定是否運行的并行循環版本。在精確數組數據流分析過程中，當遇到不精確信息導致循環簡單依賴時，則依據已知循環信息推導循環的可并行條件，在可并行條件的約束下，構建并行的循環結構。?

本發明在自動并行優化過程中主要面向由不精確信息導致的簡單依賴循環。通過構建謂詞信息，進一步展開自動并行優化分析；在謂詞約束條件下，如果能夠展開嵌套循環最外層的完全并行，則采納假設的謂詞，構建并行循環版本。對于嵌套循環的最外層并行，一般都有較大的性能收益，從而避免并行開銷評估模型的不精確。

并行謂詞條件的構建依賴數據流依賴分析，在傳統的數組數據流分析方法和依賴相關性測試中獲取循環的已知信息。當依賴相關性測試因為依賴關系不明確而采用保守估計時，觸發對并行謂詞的構建和采用基于謂詞的自動并行優化化技術。通過假設并行謂詞條件，消除不精確數據依賴關系，使得自動并行優化繼續展開后續分析。

附圖說明

圖1是包含簡單依賴的循環示例。由于內層循環邊界N和外層循環邊界間的關系不明確，使得數組數據流分析認為循環內對數組a的讀寫操作存在數據依賴，因而無法自動并行優化。

具體實施方式

下面進一步介紹本發明方法的具體操作步驟：

第一，將源程序轉化為編譯器中間表示

并行化過程中首先將源程序轉變成中間表示形式。程序的中間表示以結構化形式描述程序的抽象語法樹結構，并記錄在程序分析和優化過程中收集和產生的各種信息，它為程序分析、變換和優化的各個階段提供所需的程序信息支持。

第二，數組數據流的依賴性測試

采用傳統的數組數據流分析方法，對兩層嵌套循環中可能存在的數據依賴的分析過程：

a.?構建循環邊界與數組下標的等式

首先找出兩層嵌套循環的代碼中可能存在數據依賴的定義，設兩層嵌套循環的下標分別為i和j，存在數組引用對：對a數組的寫引用a[A1i+B1j+C1]和對a數組的讀引用a[A2i+B2j+C2]。由數組a的定義和引用關系，可建立如下等式：