[發(fā)明專利]一種調(diào)度器及其減少異步迭代處理中冗余開銷的方法

有效

• 申請?zhí)枺?/td>: 201310173239.4
• 申請日: 2013-05-10
• 公開（公告）號: CN103309942A
• 公開（公告）日: 2013-09-18
• 發(fā)明（設計）人: 廖小飛;金海;張宇
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 朱仁玲

技術領域

本發(fā)明屬于大數(shù)據(jù)處理領域，更具體地，涉及一種調(diào)度器及其減少異步迭代處理中冗余開銷的方法。

背景技術

異步迭代處理普遍存在于萬維網(wǎng)應用，數(shù)據(jù)挖掘和科學計算等領域中，例如：萬維網(wǎng)搜索引擎中的PageRank算法,鏈接分析和推薦系統(tǒng)中的Adsorption算法,以及用于解決線性方程組的Jacobi方法，它允許前面迭代中產(chǎn)生的中間結果立即被用于目前迭代中的計算,加快迭代計算的收斂速度，并且不存在負載均衡問題而使得云計算基礎設施得到更好的應用。

然而，當有很多可用的中間結果可用時，異步迭代處理就會由于下面兩個原因觸發(fā)后續(xù)迭代中大量沒必要的計算開銷和通信開銷：一）盲目的選擇一個中間結果進行處理，而不考慮每個數(shù)據(jù)對收斂速度的影響和首先處理它們將引起的開銷；二）為每一個中間結果都在后續(xù)迭代中級聯(lián)觸發(fā)大量的計算和通信開銷，從而使得異步迭代處理對大多數(shù)迭代應用會引起大量冗余計算和通信開銷，減慢異步迭代處理的收斂速度，浪費大量計算機資源，實際上，這些冗余觸發(fā)可以通過調(diào)度算發(fā)被避免掉，然而目前所有的用于異步迭代處理的調(diào)度算法，例如：優(yōu)先級調(diào)度（Priority?scheduling）、輪詢調(diào)度（Round-robin?scheduling）等，在選擇一個中間結果進行處理時，都不考慮首先處理這些中間結果的開銷。同時，這些調(diào)度算法都不是以組的形式進行調(diào)度的，從而需要為每一個中間結果數(shù)據(jù)級聯(lián)觸發(fā)后續(xù)迭代中的計算和通信，最終使得使用這些調(diào)度算法的異步迭代處理對于很多迭代應用仍然存在大量的級聯(lián)性的計算和通信冗余開銷。然而，這些冗余計算和通信開銷會大量的浪費了計算機資源，并減慢了迭代計算的收斂速度。

發(fā)明內(nèi)容

針對現(xiàn)有技術的以上缺陷或改進需求，本發(fā)明提供了一種減少異步迭代處理中冗余開銷的方法，其目的在于解決現(xiàn)有方法中存在的冗余計算和通信開銷大、計算機資源浪費、迭代計算的收斂速度慢的問題。

為實現(xiàn)上述目的，按照本發(fā)明的一個方面，提供了一種減少異步迭代處理中冗余開銷的方法，其應用在一種調(diào)度器中，該調(diào)度器分別與任務執(zhí)行器和消息接收器通訊連接，該方法包括以下步驟：

（1）建立一個哈希表，每一表項對應一個數(shù)據(jù)組，其中每一表項又包括三個域：第一個域用于存儲數(shù)據(jù)組的鍵值，第二個域用于數(shù)據(jù)組的權值，第三個域用于存儲數(shù)據(jù)組中的數(shù)據(jù)列表，數(shù)據(jù)列表中包括數(shù)據(jù)的值、以及數(shù)據(jù)所在的迭代層次；

（2）接收來自于消息接收器的數(shù)據(jù)D；

（3）根據(jù)該數(shù)據(jù)D的ITC值和IN值計算該數(shù)據(jù)D的權值Pri(D)，具體包括以下子步驟：

（3-1）計算數(shù)據(jù)D的ITC值ITC(D)和IN值IN(D)，其中ITC(D)＝±D，IN(D)是記錄在數(shù)據(jù)D中的信息，其具體為數(shù)據(jù)D的最初原始數(shù)據(jù)變化到數(shù)據(jù)D期間所處理的次數(shù)；

（3-2）根據(jù)ITC（D）和IN(D)并利用以下等式計算數(shù)據(jù)D的權值Pri(D)：Pri(D)＝t₁×ITC(D)+t₂×IN(D)/T，其中t₁和t₂分別為表示ITC（D）和IN(D)重要性的權重值，且其取值為0至1之間的小數(shù)，T為調(diào)整IN(D)取值范圍的值，其取值范圍是大于1的整數(shù)；

（4）判斷在哈希表中是否存在與該數(shù)據(jù)D具有相同鍵值的數(shù)據(jù)組G(D)存在，若存在則更新該數(shù)據(jù)組G(D)的權值和數(shù)據(jù)列表，否則在哈希列表中創(chuàng)建與該數(shù)據(jù)D相同鍵值的數(shù)據(jù)組G(D)，并進行初始化，

（5）判斷任務執(zhí)行器是否空閑，如果是則進入步驟（6），否則返回步驟（2）；

（6）從哈希表中選擇權值最大的一個數(shù)據(jù)組，將該數(shù)據(jù)組對應的數(shù)據(jù)傳送給任務執(zhí)行器處理，然后進入步驟（7）；

（7）判斷任務執(zhí)行器中運行的應用程序是否結束，如果是則過程結束，否則轉入步驟（8）；

（8）判斷哈希表中是否還有未處理的數(shù)據(jù)組，如果有則返回步驟（5），否則返回步驟（2）。

優(yōu)選地，步驟（4）包括以下子步驟：

（4-1）獲得數(shù)據(jù)D的鍵值D_key，對該鍵值進行哈希函數(shù)處理以獲得一個唯一組標識K；

（4-2）根據(jù)該唯一標識K在哈希表中進行查詢，以判斷是否有鍵值為D_key的數(shù)據(jù)組G(D)，若有,則轉入步驟（4-3），否則轉入步驟（4-4）；

（4-3）將數(shù)據(jù)D插入具有鍵值D_key的數(shù)據(jù)組G(D)中，然后轉入步驟（4-5）；