[發明專利]并行程序通信模式的提取方法及系統

有效

• 申請號: 200910093067.3
• 申請日: 2009-09-22
• 公開（公告）號: CN101661409A
• 公開（公告）日: 2010-03-03
• 發明（設計）人: 鄭緯民;陳文光;翟季冬;盛田維;何江舟
• 申請（專利權）人: 清華大學
• 主分類號: G06F9/54
• 分類號: G06F9/54
• 代理公司: 北京路浩知識產權代理有限公司
• 代理人: 胡小永

1.一種并行程序通信模式的提取方法，該方法包括步驟：

S1.解析并行程序源碼，識別所述并行程序中的通信函數調用， 確定所述通信函數中的通信變量，并將所述通信變量放入設定集合；

S2.分析所述并行程序的控制流和數據流，收集所述并行程序的 數據依賴、控制依賴以及通信依賴信息；

S3.收集所述并行程序中的調用信息，構建程序調用圖；

S4.通過基于LIVE變量傳播的切割算法對所述并行程序進行程 序切割，獲得所述并行程序的程序切片；

S5.執行所述程序切片，收集并輸出通信記錄；

S6.根據所述通信記錄，按照設定目標獲取所述并行程序的通信 模式；

其中，一個變量是LIVE變量，當且僅當，它的值改變可以通過 程序的數據依賴、控制依賴和通信依賴的傳播影響到任何通信變量的 值；

步驟S4進一步包括：

S4.1將所述通信變量放入LIVE變量集合；

S4.2自頂向下遍歷所述程序調用圖的每個節點函數，對所述每 個節點函數，若存在所述設定集合中的通信變量通過所述數據依賴、 控制依賴以及通信依賴關聯的變量，則將相應關聯的變量放入所述 LIVE變量集合；

S4.3自底向上遍歷所述程序調用圖的每個節點函數，對所述每 個節點函數，若存在所述設定集合中的通信變量通過所述數據依賴、 控制依賴以及通信依賴關聯的變量，則將相應關聯的變量放入所述 LIVE變量集合；

S4.4若所述LIVE變量集合保持不變，則執行步驟S4.5，否則返 回步驟S4.2；

S4.5標記所述并行程序中所有所述LIVE變量集合中變量定義 的語句；

S4.6對所述并行程序中的所有接收語句，標記接收變量在所述 LIVE變量集合中的通信語句，并根據所述通信依賴信息標記對應的 發送函數；

S4.7刪除所述并行程序中未標記的非通信語句，及未在所述 LIVE變量集合中的變量，得到所述并行程序的程序切片。

2.如權利要求1所述的并行程序通信模式的提取方法，其特征 在于，步驟S1進一步包括：

S1.1按照預定義的函數名識別所述并行程序中所有的通信函 數；

S1.2按照預定義的格式確定所述通信函數中的每個通信變量， 并將其放入所述設定集合。

3.如權利要求1所述的并行程序通信模式的提取方法，其特征 在于，步驟S2進一步包括：

S2.1通過數據流分析，對所述并行程序中每個變量的使用和定 義之間建立鏈接關系，即數據依賴，并將所述數據依賴信息保存于使 用-定義UD數據結構；

S2.2分析所述并行程序的控制分支，將所述并行程序中的控制 依賴轉化為所述數據依賴，并將轉化的數據依賴信息保存于使用-定 義UD數據結構；

S2.3對所述并行程序的所有通信調用進行配對分析，對所有發 送和接收的通信操作建立鏈接關系，即通信依賴，并將所述通信依賴 信息保存于消息依賴MD數據結構。

4.如權利要求1所述的并行程序通信模式的提取方法，其特征 在于，步驟S3進一步包括：

S3.1記錄所述并行程序中每個函數調用點的被調用函數名稱以 及需要傳遞的參數變量；

S3.2根據所述記錄的信息，構建程序調用圖。

5.如權利要求3所述的并行程序通信模式的提取方法，其特征 在于，步驟S5進一步包括：

S5.1記錄所述標記的通信語句在實際傳輸通信語句中的消息內 容，并記錄：消息類型、消息大小、消息的源和目的地址；

S5.2記錄所述未標記的通信語句的消息類型、消息大小、消息 的源和目的地址。

6.一種并行程序通信模式的提取系統，該系統包括：

變量確定單元，用于解析并行程序源碼，識別所述并行程序中的 通信函數調用，確定所述通信函數中的通信變量，并將所述通信變量 放入設定集合；

分析單元，用于分析所述并行程序的控制流和數據流，收集程序 的數據依賴、控制依賴以及通信依賴信息；

調用圖構建單元，用于收集所述并行程序中的調用信息，構建程 序調用圖；

程序切割單元，用于通過基于LIVE變量傳播的切割算法對所述 并行程序進行程序切割，獲得所述并行程序的程序切片；

執行單元，用于執行所述程序切片，收集并輸出通信記錄；

提取單元，用于根據所述通信記錄，按照設定目標獲取所述并行 程序的通信模式；

其中，一個變量是LIVE變量，當且僅當，它的值改變可以通過 程序的數據依賴、控制依賴和通信依賴的傳播影響到任何通信變量的 值；

所述程序切割單元進一步包括：

整理子單元，用于將所述通信變量放入LIVE變量集合；

第一遍歷子單元，用于自頂向下遍歷所述程序調用圖的每個節點 函數，對所述每個節點函數，若存在所述設定集合中的通信變量通過 所述數據依賴、控制依賴以及通信依賴關聯的變量，則將相應關聯的 變量放入所述LIVE變量集合；

第二遍歷子單元，用于自底向上遍歷所述程序調用圖的每個節點 函數，對所述每個節點函數，若存在所述設定集合中的通信變量通過 所述數據依賴、控制依賴以及通信依賴關聯的變量，則將相應關聯的 變量放入所述LIVE變量集合；

第一標記單元，用于在所述第一遍歷子單元及第二遍歷子單元遍 歷所述程序調用圖的每個節點函數后，若所述LIVE變量集合保持不 變，標記所述并行程序中所有所述LIVE變量集合中變量定義的語句； 若所述LIVE變量集合發生變化，則由所述第一遍歷子單元及第二遍 歷子單元再一次遍歷所述程序調用圖的每個節點函數；

第二標記單元，用于對所述并行程序中的所有接收語句，標記接 收變量在所述LIVE變量集合中的通信語句，并根據所述通信依賴信 息標記對應的發送函數；

程序切割子單元，用于刪除所述并行程序中未標記的非通信語 句，及未在所述LIVE變量集合中的變量，得到所述并行程序的程序 切片。