一種通過函數編程模型支持大規模分布式並行計算的方法
2023-06-12 23:58:16 1
專利名稱：一種通過函數編程模型支持大規模分布式並行計算的方法
技術領域：
本發明涉及函數編程模型的實現技術，特別提供了一種自動歸納並發現問題分割的 模型，並分布調度執行的算法。
背景技術：
由於功耗、主頻等限制，現在處理器速度提升逐步到達瓶頸。為了進一步提升處理 速度，處理器發展不得不從單純提高計算速度轉移到提供更多的並發計算核的多核模式 下。隨著多核數量的逐步增多，並發數量的增大，以往只有在大型科研院所中存在的大 規模的並行系統，將會逐步出現在消費平臺下。
由於以往的計算機發展基本都基於單處理器模式下，缺乏針對多核、乃至大規模並 行系統的自動化支持。開發人員必須依靠自己的經驗，對問題進行分割並實現分布計算 的基礎支撐，對開發人員的能力要求比較高。
函數式編程模型具有天然的並發性，十分適合於大規模分布式系統中。然而由於函 數式編程的設計思想與基於過程的語言差別很大，難以在開發人員中普及。
由此可見，針對大規模並行系統的兩種開發技術，都對開發人員有較高的要求，隨 著多核硬體系統的平民化，對大規模分布式計算的開發軟體支撐也提出了越來越急迫的 要求。
發明內容
本發明所要解決的技術問題是提供一種通過函數編程模型支持大規模分布式並行計 算的方法。
本發明所述的一種通過函數編程模型支持大規模分布式並行計算的方法，包括以下 步驟
1) 首先，將過程式的程序代碼轉換為函數式代碼，過程是消除變量的存在，對 於每一個變量的引用，用該變量賦值式右邊的函數部分取代；
2) 然後，消除函數的邊際效應，過程是利用python代碼的code對象的global
欄位，得到全局變量的訪問信息，將對全局變量的讀取轉換為傳入的參數，對全局變量 的寫入轉換成返回值；
3) 通過fork和forkout函數，對消除了邊際效用的函數進行兩次執行過程，步驟是複製frame對象，包括其本地變量和堆棧，隨後把被複製的frame交給python虛 擬機模擬執行。並每當遇到函數調用的時候，將代碼替換成偽調用代碼；
4) 構造VOID類，使得任何對這個類的實例的任何操作都會返會這個類本身，通過 此染色機制獲知函數調用的依賴關係；
5) 利用偽調用函數，去執行原本需要執行的函數，傳入的參數是一個任何對該類 實例的操作都會返回這個實例本身的VOID類；
6) 執行到forkout函數時，將執行結果通過forkout函數返回，並將被複製的frame 對象拋棄，將全局環境復原到執行之前的狀態，並正常執行；
7) forkout返回的是在模擬執行過程中產生的一系列可以並行執行的函數執行序 列，根據這個執行序列以及參數進行一次分布式計算，將結果緩衝起來，並對代碼進行 第二次執行，在第二次執行的過程中，遇到函數調用，直接返回已經緩衝的數據。
本發明通過建立基於通用語言的並自動化歸納問題分割的模型，實現函數的分布調 度執行算法，適合應用於大規模分布式系統。通過本發明，自動化的發現串行代碼中的 可以並行執行的部分。並由於最小調度單位為函數，因而充分挖掘了並行度，從而可有 效運用在大規模並行系統中。
圖1 Python代碼自動化並行執行總體框架； 圖2 Code對象結構； 圖3 fork和forkout函數示例； 圖4偽調用函數示意圖； 圖5 V0ID類的特點； 圖6並行執行示例。
具體實施例方式
本發明首先將基於過程的實現代碼轉換成函數式，由於阻礙函數並行執行的關鍵問 題在於全局變量。由於全局變量的存在，使得函數具有了狀態，無法滿足輸入和輸出一
一對應的條件。因此首先需要消除函數的邊際效應。如圖l流程所示，首先載入py代 碼，並編譯成code對象。code對象的結構如圖2所示，他們組織成一顆代碼樹。遍歷 這個代碼樹，將所有訪問全局變量的函數，將全局變量作為參數傳入。將所有寫入全局 變量的函數，將全局變量作為返回結果之一返回。如此經過一次遍歷，將生成一顆新的代碼樹，這個代碼樹中的所有函數都沒有邊際效應。
基於無邊際效應的代碼，通過構造如圖3所示的fork和forkout函數，來實現模 擬執行。其過程為複製frame對象，包括其本地變量和堆棧。隨後讓被複製的frame交 給python虛擬機正常執行，直到執行到forkout函數時，將執行結果通過forkout函 數返回。並將被複製的frame對象拋棄，重新恢復到執行之前的狀態，並正常執行。
隨後，為了利用無邊際效應的等效代碼達到並發執行的目的，需要對這個代碼進行 一次模擬執行，分析出函數之間的相互依賴關係。再一次執行如圖l所示的對代碼樹的 遍歷過程，這次當遇到函數調用的時候，將代碼替換成偽調用代碼。
如圖4所示。利用偽調用函數，去執行原本需要執行的函數，傳入的參數是一個特 別構造的VOID類。如圖5所示，VOID類的特點是任何對VOID類實例的操作都會返回這 個實例本身。
隨後進行一次執行的過程，在這個過程中，當傳入的參數不包含VOID實例時，說 明這個函數是沒有依賴的，可以獨立執行。當傳入的函數包含了 VOID實例時，則說明 這個函數將依賴於返回這個VOID實例的上一個函數，在並行計算中必須串行計算這兩 者。
模擬執行的過程中，由於函數執行所依賴的數據都變成了 VOID,所以不會存在真實 的計算，僅僅分析函數的依賴關係和執行參數序列，因而執行速度非常快。
當模擬執行到達程序的終點時，則產生了一系列的函數執行序列，如圖6所示。由 於這個版本中的函數不存在邊際效應，因此確定的輸入一定會產生確定的輸出。根據這 個執行序列以及參數進行一次分布式計算，將結果緩衝起來，並對代碼進行第二次執行。 在第二次執行的過程中，遇到函數調用，直接返回已經緩衝的數據，從而達到並行計算, 提高執行速度的目的。
權利要求
1、一種通過函數編程模型支持大規模分布式並行計算的方法，其特徵在於包括以下步驟1)首先，將過程式的程序代碼轉換為函數式代碼，過程是消除變量的存在，對於每一個變量的引用，用該變量賦值式右邊的函數部分取代；2)然後，消除函數的邊際效應，過程是利用python代碼的code對象的global欄位，得到全局變量的訪問信息，將對全局變量的讀取轉換為傳入的參數，對全局變量的寫入轉換成返回值；3)通過fork和forkout函數，對消除了邊際效用的函數進行兩次執行過程，步驟是複製frame對象，包括其本地變量和堆棧，隨後把被複製的frame交給python虛擬機模擬執行，並且每當遇到函數調用的時候，將代碼替換成偽調用代碼；4)構造VOID類，使得任何對這個類的實例的任何操作都會返會這個類本身，通過此染色機制獲知函數調用的依賴關係；5)利用偽調用函數，去執行原本需要執行的函數，傳入的參數是一個任何對該類實例的操作都會返回這個實例本身的VOID類；6)執行到forkout函數時，將執行結果通過forkout函數返回，並將被複製的frame對象拋棄，將全局環境復原到執行之前的狀態，並正常執行；7)forkout函數返回的是在模擬執行過程中產生的一系列可以並行執行的函數執行序列，根據這個執行序列以及參數進行一次分布式計算，將結果緩衝起來，並對代碼進行第二次執行，在第二次執行的過程中，遇到函數調用，直接返回已經緩衝的數據。
全文摘要
本發明公開了一種通過函數編程模型支持大規模分布式並行計算的方法，首先將基於過程的實現代碼轉換成函數式，然後消除函數的邊際效應，再構造fork和forkout函數，進行模擬執行過程，當遇到函數調用時，將函數調用轉換為將函數和其參數作為參數，傳入偽調用函數。利用VOID的感染特性來對函數調用進行染色獲取函數的調用關係。當到達程序的終點則產生一系列的函數執行序列，根據執行序列以及參數進行一次分布式計算，將結果緩衝起來，並對代碼進行第二次執行，在此過程，遇到函數調用，直接返回已經緩衝的數據。本發明通過建立基於通用語言的並自動化歸納問題分割的模型，實現函數的分布調度執行算法，適合應用於大規模分布式系統。
文檔編號G06F9/44GK101446898SQ20081023543
公開日2009年6月3日 申請日期2008年12月2日 優先權日2008年12月2日
發明者琦 呂, 李文中, 陸桑璐, 陳道蓄 申請人:南京大學