[發明專利]一種面向流計算的動態調度分配方法

無效

• 申請號: 201310345008.7
• 申請日: 2013-08-08
• 公開（公告）號: CN103412794A
• 公開（公告）日: 2013-11-27
• 發明（設計）人: 王堃;于悅;郭篁;陸恒;張玉華
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 葉連生

1.一種面向流計算的動態分配調度方法，其特征在于該方法建立流序列圖SQG，采用動態權重更新機制計算每條邊的權重，選擇權重最小的邊發送元組，同時提出兩種優化方案，

該方法實現過程如下：設k為主機數，首先初始化k臺主機上的模板匹配器，將需要匹配的模板分配給k個邏輯主機，構成k個相同的匹配序列，然后以操作器為頂點，對應操作器的輸入輸出關系為邊，建立流序列圖SQG，對于每個邏輯主機，采用動態權重更新機制計算從某節點出去的邊的權重，在流序列圖SQG中進行最短路徑選擇，即選擇權重最小的邊，設定一個計數器并將其歸0，然后重復下面步驟：

1）處理上一個操作器發來的元組，

2）發送已處理好的元組至下一級操作器并將首部中的操作器序列號operator_Id加1，

3）計數器加1，為了減小上下文切換，設置計數器上限為w，當計數器大于w時跳出循環，最后一級操作器將緩存的元組排序并發送給用戶應用。

2.根據權利要求1所述的一種面向流計算的動態分配調度方法，其特征在于所述的流序列圖SQG是一個加權的有向無環圖，具體描述如下：

每個邏輯處理單元通常包含多個操作器，這些單元是物理單元，即多核系統的各個處理器以及簇計算環境中的節點，抑或是虛擬單元；為了降低處理單元的壓力，采用多個相同的處理單元以并行的方式進行處理，并且各個不同邏輯主機的操作器間按照既定規律傳遞信息；整個處理流程中，操作器A輸出的數據作為操作器B的輸入，那么所有邏輯單元中的操作器A都可以像別的邏輯單元中的操作器B發送數據；

由K個相同邏輯單元構成的操作器序列組成了一個有向圖，操作器為圖的頂點，源點和匯點為圖中兩個特殊節點；第一級的節點通過一條邊與源點相連，最后一級的節點通過一條邊與匯點相連，連接兩個節點的一條邊代表操作器之間的任務隊列，邊的權重代表隊列中等待的任務數；操作器a可以進行選取，即選擇有著某些信息的元組，操作器b可以進行聚合，即接收操作器a傳來的所有特定的元組，計算是否滿足觸發下一步動作的條件；動態分配調度算法運行前需要建立此圖，根據各個操作器的性能變化進行調度；調度進程對SQG進行運算，找到源點到匯點的最短路徑，減少元組的延遲；

定義1：在SQG中，圖的頂點記為V，代表流操作器，圖的邊記為E，代表兩個操作器之間的隊列，代表位于主機j上的第i級操作器，O_{_}ⁱ代表所有主機上的第i級操作器，O_j_代表主機j上的所有操作器，O_{_}^|V|代表所有主機上的最后一級操作器，

定義2：一個可劃分子集的有向圖，從其狀態i頂點出去的邊只與狀態i+1的頂點相連，則此圖為多狀態圖，

定義3：由狀態i到狀態i+1的頂點所發生的轉移稱為步。設一個元組從初始狀態到被處理完畢總共需要經過n級操作器，則總共需要n步，這n步構成了一條操作器路徑，從起點到達操作器所花時間最少的一條路徑稱作最短操作器路徑MIN_PATH(Oⁱ_j)。