[發明專利]基于關鍵路徑的適應處理器內核緊缺調度方法有效

申請號：	201310305300.6	申請日：	2013-07-21
公開（公告）號：	CN103336723A	公開（公告）日：	2013-10-02
發明（設計）人：	謝志強;韓英杰	申請（專利權）人：	哈爾濱理工大學
主分類號：	G06F9/50	分類號：	G06F9/50;G06F15/163
代理公司：	哈爾濱東方專利事務所 23118	代理人：	陳曉光
地址：	150080 黑龍江省***	國省代碼：	黑龍江;23
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	基于關鍵路徑適應處理器內核緊缺調度方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域：

本發明涉及一種適應處理器內核緊缺的多核調度方法。

背景技術：

多核處理器現已廣泛應用于各個領域，如何在滿足一定約束條件下使處理器上任務充分并行處理，是任務調度研究的主要方向。任務調度需要通過任務調度算法來實現，而多核任務調度算法早已被證明是NP完全問題，即使在允許任務復制的前提下也是NP完全問題，故在以后的研究中大多側重于獲取近似最優解。

目前多核處理器片上通信機制主要有兩種，一種是基于共享L2cache的共享存儲結構，一種是基于片上網絡或交叉開關的片上互連結構。無論處理器采用哪種結構，處理器內核之間的通信開銷都是不可忽略的，這也是影響處理器性能的主要因素之一。現今多核處理器任務調度研究主要有三個方向：任務分配優化，提高L2cache命中率的共享存儲優化和任務負載均衡等。其中，任務分配優化方向的主要著眼點在于將任務通過合理的調度算法分配到處理器各個內核上執行，以減少內核之間通信開銷和提前任務完成總時間。

在多核處理器結構中，一個應用程序可以看成是一個任務的集合，這些任務之間存在著一定的數據依賴關系，這種依賴關系在應用程序開始執行之前就已經存在。如何在滿足這種依賴關系的前提下，將應用程序中的任務合理的分配到處理器內核上執行，達到減少通信時間和任務執行總時間的目的，是多核處理器任務分配優化方向研究的主要內容。

目前，在任務分配優化方向比較著名的調度算法主要有：IREA，PPA，ETDS，TDMSCL，CPFD，PY，等。由于采用任務復制的方式將加權有向無環任務圖(Directed?Acyclic?Graph,?DAG)轉換為產品加工樹后，便于對任務進一步的分析處理；又由于對產品加工樹采用逐層分解調度方式，便于在每一步調度中都能優先調度當前關鍵路徑上的節點，達到減少任務執行時間的目的，而以往算法沒有考慮到這一點，因此在任務完成總時間上會有所延遲，同時由于不能根據處理器當前剩余內核數對調整調度序列進行調整，因此在處理器內核不足時無法進行任務處理，進而使得當前剩余內核空閑，會造成處理器資源浪費。

發明內容：

本發明的目的是提供一種適應處理器內核緊缺的多核調度方法。

上述的目的通過以下的技術方案實現：

一種基于關鍵路徑的適應處理器內核緊缺調度方法，該方法包括如下步驟：任務圖轉換模塊采用復制叉節點的方法將DAG任務圖轉換為產品加工樹；產品加工樹調度模塊按層序遍歷產品加工樹，自上而下將所述的產品加工樹劃分成若干子樹，自最底層的子樹起，依次在子樹中查找并優先調度關鍵路徑上節點，形成調度序列，每調度完成一棵子樹便將該子樹虛擬為一個節點并加入上層的子樹中，直到所有節點調度完畢，形成初始調度序列；序列合并調整模塊采用合并通信最為頻繁且合并后對任務完成總時間影響最小序列的方式，將調度序列合并以適應處理器內核緊缺。

所述的基于關鍵路徑的適應處理器內核緊缺調度方法，所述的調度方法具體實施步驟如下：

步驟1：遍歷DAG任務圖，復制叉節點，將DAG圖轉換為產品加工樹；

步驟2：由葉節點起層序遍歷產品加工樹，依次將入度大于1的節點加入隊列a；

步驟3：判斷隊列a是否為空，如不為空，繼續執行，否則跳至步驟13；

步驟4：取出隊列a當前頭結點T_i，與其緊前節點序列形成以T_i為根節點的產品加工樹；

步驟5：在加工樹中查找關鍵路徑，將關鍵路徑上節點依次加入隊列b；

步驟6：判斷隊列b是否為空，如不空繼續向下執行，否則跳轉至步驟3；

步驟7：取出并刪除隊列b當前頭結點，判斷該節點入度是否大于1，如該任務節點入度不大于1，繼續向下執行，否則跳轉至步驟9；

步驟8：與緊前節點序列形成調度序列，跳轉到步驟6；

步驟9：將不在關鍵路徑上的緊前節點序列形成初始調度序列；

步驟10：擬合并緊前節點序列，如果合并后使得該節點開始時間延遲，繼續向下執行；否則跳轉至步驟12；

步驟11：將關鍵緊前節點序列與非關鍵緊前節點序列分別形成調度序列，并將節點分配到使其最早開始執行的序列上，跳轉至步驟6；