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

有效

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

1.一種減少異步迭代處理中冗余開銷的方法，其應用在一種調度器中，該調度器分別與任務執行器和消息接收器通訊連接，其特征在于，該方法包括以下步驟：

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

（2）接收來自于消息接收器的數據D；

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

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

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

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

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

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

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

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

2.根據權利要求1所述的方法，其特征在于，步驟（4）包括以下子步驟：

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

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

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

（4-4）創建一個鍵值為D_key的數據G(D)，并將數據D插入數據組G(D)中，然后轉向步驟(4-6)；

（4-5）采用以下公式更新哈希表中鍵值為D_key的數據組的權值，Pri(G(D))＝PriGG(D))+Pri(D)，然后轉向步驟（5）；

（4-6）將數據組G(D)的權值設置為Pri(D)，然后轉向步驟（5）。