[發明專利]一種支持動態伸縮的并行計算的方法

在審

• 申請號: 201410049723.0
• 申請日: 2014-02-13
• 公開（公告）號: CN103810041A
• 公開（公告）日: 2014-05-21
• 發明（設計）人: 曹東剛;詹杭龍
• 申請（專利權）人: 北京大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F17/30
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 馮藝東

技術領域

本發明涉及計算機網絡技術領域，具體涉及一種在開放、易變的動態網絡環境下支持動態伸縮的并行計算方法。

背景技術

并行計算是指同時使用多種計算資源來解決問題的模式，它是提高計算機系統的運算速度和處理能力的一種高效手段。隨著并行計算領域的發展，一系列支持并行計算的編程接口和處理系統不斷出現。從POSIXThreads、MPI到OpenMP、PVM，再到現在非常流行的用于特定領域的MapReduce、Dryad、Pregel等編程框架，用戶可以方便地編寫和運行并行程序。

然而，互聯網的快速發展對并行計算技術提出新的挑戰。一方面，互聯網信息量的飛速增長使得并行計算的應用場景越來越廣泛，從早期的科學計算，到現在的網頁搜索、海量數據分析等，其應用類型逐漸多樣化。另一方面，并行計算的載體由封閉的、面向專門應用的系統逐漸轉變成開放的，由眾多計算資源通過網絡構成的運算平臺。這種運算平臺的特點在于參與計算的資源規模可能在運行時發生改變，可能有計算資源在運行中宕機或離線，或者有新資源隨時加入。這就要求平臺上的并行計算具有伸縮性，以更好地利用計算資源，并在計算過程中保證作業成功運行或實現加速。然而，上述提到的編程接口或框架均無法滿足這種需求。此外，諸如MapReduce、Drayd、Pregel等編程框架均面向領域特定的并行程序，不具有通用性。

發明內容

本發明的目的是提供一種在開放、易變的動態網絡環境下支持動態伸縮的并行計算方法，使得程序員能夠簡單、高效地開發多種類型及特定領域的并行計算程序。

本發明主要包括以下內容：（1）將并行作業轉化成由若干任務構成的集合，并將任務集管理與處理器組群的管理進行解耦，以支持可伸縮的計算；（2）通過任務緩沖池實現對并行作業的任務集的管理和調度。

為了實現上述目的，本發明采用以下技術方案：

一種支持動態伸縮的并行計算的方法，首先提出將任務集的管理與處理器進行解耦。任務集的管理只負責維護作業的邏輯流，決定在某一時刻哪些任務可以被調度執行、哪些任務因尚未滿足執行條件而待命。在對任務集進行管理時，不需要考慮處理器的情況。

具體包括以下步驟：

1）將并行作業分解成若干任務構成的任務集；

2）利用任務緩沖池維護上述任務集，并創建動態任務表，用于跟蹤記錄已被調度到處理器集群中的處理器上執行的任務；

3）處理器集群中的處理器只要空閑，便向任務緩沖池請求任務，獲得任務緩沖池調度的待執行的任務進行處理，而后將執行結果提交到任務緩沖池；

4）當任務緩沖池接收到處理器提交的任務的執行結果時，更新任務集及動態任務表；

5）當任務集和動態任務表中沒有待執行的任務時，任務緩沖池結束對任務的調度，并行作業完成。

進一步地，步驟2）中，所述任務緩沖池中任務的狀態包括：尚未調度狀態、已被調度尚未提交狀態和執行結果已提交狀態。

進一步地，步驟2）中，所述任務集中的任務在第一次被調度后，該任務從任務集中移除，添加到動態任務表中。

進一步地，步驟3）中，所述處理器集群中的處理器相互獨立，新加入的處理器可以直接向任務緩沖池請求任務。

進一步地，步驟3）中，所述處理器集群中的每個處理器均包含兩種狀態，空閑及忙碌，并在兩種狀態間循環轉換。若處理器空閑，則向任務緩沖池請求任務并執行，轉換成忙碌狀態。等任務執行完提交后，處理器恢復成空閑狀態。

進一步地，步驟3）中，所述處理器向任務緩沖池請求任務時，任務緩沖池可能返回三種結果，處理器根據任務緩沖池返回的不同結果進行相應操作。若結果為一個待執行的任務，則處理該任務；若結果為stop標記，說明任務緩沖池已確認該并行作業的完成，處理器可以停止運行；若結果為standby標記，說明任務緩沖池目前暫時無法提供任務，但該并行作業尚未完成（可能會有新的待執行任務添加到任務緩沖池中），此時處理器應稍后再請求任務。

進一步地，步驟3）中，如果處理器在執行任務的過程中生成新的子任務，則需要在提交執行結果的同時將新的子任務添加到任務緩沖池中。

進一步地，步驟4）中，如果處理器所提交的任務記錄在任務動態表中，任務緩沖池會將該任務項刪除；如果該任務未記錄在任務動態表中，表示之前已經有其它處理器成功提交過該任務，則忽略此次提交。