[發明專利]一種適用于核外圖處理系統的異步IO執行方法及系統

有效

• 申請號: 201711115579.6
• 申請日: 2017-11-13
• 公開（公告）號: CN107992358B
• 公開（公告）日: 2020-05-19
• 發明（設計）人: 邵志遠;廖小飛;金海;李浪
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 廖盈春;李智

本發明公開了一種適用于核外圖處理系統的異步IO執行方法及系統，屬于大數據領域的圖計算與處理技術領域，也可以用于其他數據存放在磁盤的迭代計算系統。其中，方法的實現包括：在圖計算執行過程中，線程將從任務隊列中獲取的任務發送給異步IO庫，而后異步IO庫依據任務所需數據的存儲情況，異步地發出數據的讀取請求并加入到請求隊列，然后請求隊列對異步產生的讀取請求進行排序合并，在相關數據讀取完畢時，異步IO庫執行對應任務，從而在執行層提高磁盤的訪問效率，加快任務的執行速度。本發明能應用于基于磁盤的迭代計算系統，加快算法的執行速度，實用性強。

技術領域

本發明屬于大數據處理技術的圖計算技術領域，更具體地，涉及一種適用于核外圖處理系統的異步IO執行方法及系統。

背景技術

圖數據模型用來表征不同實體間復雜的依賴關系，在現實生活中隨處可見。在許多實際的應用當中，如社交網絡分析、網頁搜索、商品推薦等，都可以使用圖數據模型來進行問題的建模和分析。然而，在大數據時代，這類問題的規模通常十分龐大并仍然在快速增長，使得圖計算技術領域面臨巨大的挑戰。在此背景下，如何加快基于磁盤的大規模圖數據中相關算法的求解成為了亟待解決的問題。

現有的大規模圖處理方式主要包括：多節點的分布式平臺和單節點的核外系統。多節點的分布式平臺進行圖計算的步驟是：劃分圖數據、給節點機發送圖數據、節點機處理接收的圖數據、處理結果的匯總。單節點的核外系統則是利用單個節點機的外部存儲來存放大規模的圖數據，然后依次載入部分圖數據到內存中進行處理。

分布式圖處理平臺隨著問題規模的擴大有很好的擴展性，但是系統處理效率難以提高。首先，圖的劃分，在提高系統性能的同時保證節點間負載均衡，是一個多項式復雜程度的非確定性NP-hard問題。其次，節點間協同工作和容錯需求，制約了系統的性能。最后，環境搭建和程序編寫比較復雜，而且程序的調優和優化相對困難。

近幾年，單機核外圖處理系統有了許多新的成果——GraphChi、X-Stream、TurboGraph、MMap、VENUS、GridGraph。這些成果極大地降低了大圖計算的開銷，同時能夠達到甚至超過部分分布式圖處理平臺的處理時延。由此證明的單機核外圖處理系統處理大規模圖數據的可行性，使得加快單機核外圖處理系統中相關算法的求解擁有廣泛的需求。

由于不同的算法有不同的訪問存儲特點，現有的單機核外圖處理系統對于不同的算法并不一定都有最優的性能。對于GraphChi、X-Stream和GridGraph的執行模型，PageRank算法能夠最大化利用磁盤帶寬，因為每次迭代都需要遍歷所有的圖數據，而對于BFS算法，則浪費了磁盤帶寬，因為每次迭代中不是所有頂點都需要參與計算，部分讀取的數據無用。然而，對于MMap，PageRank算法帶來的隨機性訪問限制了算法性能，而對于BFS算法，隨機性訪問減少了無用數據的讀取，加速了算法的執行。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種適用于核外圖處理系統的異步IO執行方法及系統，由此解決現有基于磁盤的大規模圖數據中相關算法求解效率較低的技術問題。

為實現上述目的，按照本發明的一個方面，提供了一種適用于核外圖處理系統的異步IO執行方法，包括：

(1)判斷系統的任務隊列是否為空，如果是，則執行步驟(8)，否則執行步驟(2)；

(2)獲取所述系統的任務隊列中的目標任務，并判斷所述目標任務所需數據是否都能直接訪問，如果是，則執行步驟(7)，否則執行步驟(3)；

(3)對所述目標任務所需的不能直接訪問的數據生成讀取請求，將所述讀取請求加入異步IO庫的請求隊列，并將所述目標任務加入所述異步IO庫的任務隊列；

(4)判斷所述異步IO庫的請求隊列中的讀取請求數是否大于預設閾值，如果是，則執行步驟(5)，否則執行步驟(1)；