一種基於Kahn進程網絡的程序並行框架提取技術的製作方法
2023-04-29 05:09:11 2
一種基於Kahn進程網絡的程序並行框架提取技術的製作方法
【專利摘要】本發明公開了一種基於Kahn進程網絡的程序並行框架提取技術，其特徵在於：基於局部化控制和分散內存的思想，從3個步驟應用程式轉化成為進程網絡完成程序並行框架提取：步驟1、預處理；步驟2、消費者進程重構；步驟3、生產者進程重構。本發明針對嵌入式系統中一類典型的計算密集程序——靜態仿射嵌套循環程序，提出一種並行性發現技術，並且將其表示為Kahn進程網絡。
【專利說明】-種基於Kahn進程網絡的程序並行框架提取技術
【技術領域】
[0001] 本發明屬於一種基於K址n進程網絡的程序並行框架提取技術。
【背景技術】
[0002] 多核或者多處理架構已經成為當前各類信息系統的主要技術。從高性能計算到嵌 入式系統，多核（包括異構多核）處理器可W有效地滿足計算性能要求，降低能耗。但是， 多核計算機系統的內在的並行性利用通常需要並行的程序設計。現有的並行程序設計基於 特定的並行庫，編程人員手工分析程序的可並行性，給出並行化策略和方法。現有的並行庫 包括MPI、化enMP、化da等，該些並行庫通常支持高性能的計算環境，自身的開銷也較大，無 法滿足嵌入式環境多核並行編程的需求。
【發明內容】
[0003] 本發明要解決的技術問題是克服上述缺陷，提供一種基於K址n進程網絡的程序 並行框架提取技術，針對嵌入式系統中一類典型的計算密集程序一一靜態仿射嵌套循環程 序，提出一種並行性發現技術，並且將其表示為K址n進程網絡。
[0004] 為解決上述問題，本發明所採用的技術方案是：
[0005] 一種基於K址n進程網絡的程序並行框架提取技術，其特徵在於：基於局部化控制 和分散內存的思想，從3個步驟應用程式轉化成為進程網絡完成程序並行框架提取：
[0006] 步驟1、預處理：預處理過程首先將每條賦值語句的所有執行壓縮成為一個進程， 從而形成一個初始的進程網絡；
[0007] 步驟2、消費者進程重構：消費者進程重構是根據K址n進程網絡之間的通信是 FIFO的基本要求，將生產者進程共同具有寫操作的內存數組分解為獨立的內存區域，然後 調整、或者新增新的消費者進程的一個過程；
[000引步驟3、生產者進程重構；生產者進程重構是指將多個消費者進程訪問的內存數 組替換為獨立的內存數組，然後調整生產者進程結構的過程。
[0009] 作為一種優化的技術方案，所述步驟2中，消費者進程重構過程將考慮每個進程 的數據消耗，並且給出獨立的內存數組，使得生產者進程可W存儲數據；對於每個數組，確 保只有一個生產者進程；
[0010] 具體的實現過程如下：
[0011] 1)、識別對相同內存數據具有寫操作的生產者進程組；設Sf是對內存數組r寫入 數據的所有生產者進程的集合，町是所有從內存數組r讀數據的消費者進程集合；
[0012] 2)、拆分內存數組；對於每個進程IVG S t，利用獨立的內存數組替代r來支持 其寫操作；
[0013] 3)、建立起消費進程和生產進程的有效連結；為了確保程序的邏輯正確性，消費進 程q G C,.也必須從新的內存r,中讀取數據；將r i與每個r的消費者連接；但是該樣的連結 中，存在許多無效連結；為了消除無效連結，執行IV與消費進程間的數據依賴分析，對於沒 有數據依賴的連結，則刪除之，留下確實有數據依賴的連結；
[0014] 4)、確定r,的範圍；根據數據依賴分析，建立起一個仿射依賴函數，該函數在輸入 埠域上有效；一般地說，假如每個輸入埠域可W利用一個k維的綜合參數化多面體表 示，即/PD = C(N )〇. %對於每個生產者對P/C，它可W由一個唯一的多面體C(N)和一個 仿射依賴函數f表示；一個仿射依賴函數f表示為一個積分矩陣M和一個偏移向量0: f (X) =Mx+0 ;通過該依賴函數，可W確定對於每個生產者/消費者對在內存上的輸入範圍；
[0015] 5)、重構消費者進程；根據每個r;及其輸入埠域的範圍，為消費者進程巧eQ 聲稱一個新進程('，，其循環上下界根據輸入埠的範圍確定。
[0016] 作為一種優化的技術方案，所述步驟3中，步驟如下：
[0017] 1)、對於每一內存數組，識別出相應的消費者進程集合，設町是讀取內存數組r的 所有消費者進程的集合；
[0018] 2)、為每個消費者進程G設立獨立的內存數組ri來替代隊r的訪問；
[0019] 3)、確定每個的輸入域；由於消費者進程重構過程已經完成，對於每個內存數組 r僅有一個進程F輸入數據；那麼就僅需確定P t在每個r i上的輸出；其輸出為
[0020] OPD = /( Q N ) n '') = {p\p= fix), X e (C( N ) n *) j .
[002U 4)、確定生產者c滿足r,的輸入域y ;該需要根據生產者和消費者之間的逆向數 據流分析，求解數據流函數獲得；
[0022] 5)、根據每個獨立的內存數組的輸入範圍重構生產者代碼。
[0023] 由於採用了上述技術方案，與現有技術相比，本發明設計了 一種技術從串行程序 中提取並行性的技術，支持自動化的程序並行化。由於不同類型的串行程序特徵不同，並行 化的效果也不盡相同。本發明針對嵌入式系統中一類典型的計算密集程序一一靜態仿射嵌 套循環程序，提出一種並行性發現技術，並且將其表示為Kahn進程網絡。
【具體實施方式】 [0024] 實施例；
[0025] 一種基於K址n進程網絡的程序並行框架提取技術，基於局部化控制和分散內存 的思想，從3個步驟應用程式轉化成為進程網絡完成程序並行框架提取：
[0026] 步驟1、預處理：預處理過程首先將每條賦值語句的所有執行壓縮成為一個進程， 從而形成一個初始的進程網絡。
[0027] 步驟2、消費者進程重構：消費者進程重構是根據K址n進程網絡之間的通信是 FIFO的基本要求，將生產者進程共同具有寫操作的內存數組分解為獨立的內存區域，然後 調整、或者新增新的消費者進程的一個過程。
[002引步驟3、生產者進程重構；生產者進程重構是指將多個消費者進程訪問的內存數 組替換為獨立的內存數組，然後調整生產者進程結構的過程。
[0029] 所述步驟2中，消費者進程重構過程將考慮每個進程的數據消耗，並且給出獨立 的內存數組，使得生產者進程可W存儲數據；對於每個數組，確保只有一個生產者進程；
[0030] 具體的實現過程如下：
[0031] 1)、識別對相同內存數據具有寫操作的生產者進程組；設Sf是對內存數組r寫入 數據的所有生產者進程的集合，町是所有從內存數組r讀數據的消費者進程集合。
[0032] 2)、拆分內存數組；對於每個進程IVG Sf，利用獨立的內存數組替代r來支持 其寫操作。
[0033] 3)、建立起消費進程和生產進程的有效連結；為了確保程序的邏輯正確性，消費進 程q e C,.也必須從新的內存中讀取數據；將r i與每個r的消費者連接；但是該樣的連結 中，存在許多無效連結；為了消除無效連結，執行IV與消費進程間的數據依賴分析，對於沒 有數據依賴的連結，則刪除之，留下確實有數據依賴的連結。
[0034] 4)、確定的範圍；根據數據依賴分析，建立起一個仿射依賴函數，該函數在輸入 埠域上有效；一般地說，假如每個輸入埠域可W利用一個k維的綜合參數化多面體表 示，即//>D = C(N )〇□%對於每個生產者對P/C，它可W由一個唯一的多面體C(N)和一個 仿射依賴函數f表示；一個仿射依賴函數f表示為一個積分矩陣M和一個偏移向量0: f (X) =Mx+0 ;通過該依賴函數，可W確定對於每個生產者/消費者對在內存上的輸入範圍。
[0035] 5)、重構消費者進程；根據每個r,及其輸入埠域的範圍，為消費者進程巧eCr 聲稱一個新進程.巧，其循環上下界根據輸入埠的範圍確定。
[0036] 所述步驟3中，步驟如下：
[0037] 1)、對於每一內存數組，識別出相應的消費者進程集合，設D,是讀取內存數組r的 所有消費者進程的集合。
[003引 2)、為每個消費者進程G設立獨立的內存數組來替代隊r的訪問。
[0039] 3)、確定每個的輸入域；由於消費者進程重構過程已經完成，對於每個內存數組 r僅有一個進程F輸入數據；那麼就僅需確定P t在每個r i上的輸出；其輸出為
[0040]
【權利要求】
1. 一種基於Kahn進程網絡的程序並行框架提取技術，其特徵在於：基於局部化控制和 分散內存的思想，從3個步驟應用程式轉化成為進程網絡完成程序並行框架提取： 步驟1、預處理：預處理過程首先將每條賦值語句的所有執行壓縮成為一個進程，從而 形成一個初始的進程網絡； 步驟2、消費者進程重構：消費者進程重構是根據Kahn進程網絡之間的通信是FIFO的 基本要求，將生產者進程共同具有寫操作的內存數組分解為獨立的內存區域，然後調整、或 者新增新的消費者進程的一個過程； 步驟3、生產者進程重構：生產者進程重構是指將多個消費者進程訪問的內存數組替 換為獨立的內存數組，然後調整生產者進程結構的過程。
2. 根據權利要求1所述的基於Kahn進程網絡的程序並行框架提取技術，其特徵在於： 所述步驟2中，消費者進程重構過程將考慮每個進程的數據消耗，並且給出獨立的內存數 組，使得生產者進程可以存儲數據；對於每個數組，確保只有一個生產者進程； 具體的實現過程如下： 1) 、識別對相同內存數據具有寫操作的生產者進程組；設&是對內存數組r寫入數據 的所有生產者進程的集合，W是所有從內存數組r讀數據的消費者進程集合； 2) 、拆分內存數組；對於每個進程/fe^，利用獨立的內存數組ri替代r來支持其寫 操作； 3) 、建立起消費進程和生產進程的有效連結；為了確保程序的邏輯正確性，消費進程 C)eC,也必須從新的內存A中讀取數據；將ri與每個r的消費者連接；但是這樣的連結 中，存在許多無效連結；為了消除無效連結，執行與消費進程間的數據依賴分析，對於沒 有數據依賴的連結，則刪除之，留下確實有數據依賴的連結； 4) 、確定1^的範圍；根據數據依賴分析，建立起一個仿射依賴函數，該函數在輸入埠 域上有效；一般地說，假如每個輸入埠域可以利用一個k維的綜合參數化多面體表示，即 //>D=C(N)n'對於每個生產者對p/C，它可以由一個唯一的多面體C(N)和一個仿射 依賴函數f表不；一個仿射依賴函數f表不為一個積分矩陣M和一個偏移向量0:f(X)=Mx+0 ;通過該依賴函數，可以確定對於每個生產者/消費者對在內存巧上的輸入範圍； 5) 、重構消費者進程；根據每個ri及其輸入埠域的範圍，為消費者進程C；eC,.聲稱 一個新進程（',，其循環上下界根據輸入埠的範圍確定。
3. 根據權利要求2所述的基於Kahn進程網絡的程序並行框架提取技術，其特徵在於： 所述步驟3中，步驟如下： 1) 、對於每一內存數組，識別出相應的消費者進程集合，設1\是讀取內存數組r的所有 消費者進程的集合； 2) 、為每個消費者進程CT設立獨立的內存數組&來替代隊r的訪問； 3) 、確定每個&的輸入域；由於消費者進程重構過程已經完成，對於每個內存數組r僅 有一個進程F輸入數據；那麼就僅需確定P在每個ri上的輸出；其輸出為 OPD =/(QN ) nk)^\p\p = ,f\x\xe (QN )nDfr)}. 9 4)、確定生產者G滿足巧的輸入域y;這需要根據生產者和消費者之間的逆向數據流 分析，求解數據流函數獲得； 5)、根據每個獨立的內存數組的輸入範圍重構生產者代碼。
【文檔編號】G06F9/38GK104503734SQ201410855804
【公開日】2015年4月8日 申請日期:2014年12月31日 優先權日:2014年12月31日
【發明者】李尚傑, 程勝, 周志軍, 魏明, 卓保特 申請人:北京神舟航天軟體技術有限公司