2D—Torus 眾核任務綁定與調度的近似算法

丁軍　覃志東

摘 要：任務綁定與調度是眾核軟件綜合過程中要研究的關鍵問題，由于眾核平臺的多樣性與特殊性，任務綁定與調度算法在設計時需要充分考慮任務集與物理平臺的特性。本文針對2D-Torus同構眾核處理器平臺，提出一種基于BAMSE近似算法的任務綁定與調度方案，實現了具有通信開銷的非獨立任務集到物理內核的綁定，并通過實驗探究了改進后的BAMSE算法在2D-Torus眾核平臺上實現任務綁定與調度的性能。

關鍵詞：眾核處理器； 軟件綜合技術； 任務綁定與調度

中圖文分類號：TP311.52 文獻標識碼：A 文章編號：2095-2163（2016）01-

Abstract： Task binding and scheduling is the key problem of many-core software synthesize， as the diversity and particularity of many-core processor platform， the algorithm of task binding and scheduling need to consider the characteristics of the task set and the physical platform. This paper proposes a new algorithm based on BAMSE for 2D-Torus homogeneous many-core processor， and the algorithm realizes the binding of task set with communication on the physical cores. After that， the paper verifies the feasibility of this improved BAMSE algorithm under the 2D-Torus many-core platform.

Key words： many-core processor； software synthesis technique； task binding and scheduling

0引 言

時下，半導體集成技術的飛速發展仍在持續，而與之關聯的處理器也在經歷了單核、多核時代后，正在基礎穩健地向眾核領域邁進，并且，單個芯片上集成內核數目的日益增多已然成為眾核處理器發展的現實可見趨勢[1-2]。眾核處理器上內核數目的增多使其具備了強大的并行計算能力，但卻由于眾核軟件綜合技術的滯后這一不足，而使得諸多眾核處理器平臺因缺乏相應的基礎軟件支持，將無法充分發揮其理想的并行性能，如此即不僅造成了硬件資源的浪費，更在實際效果上限制了眾核處理器性能的進一步提升，故研究優秀的眾核軟件綜合技術已然形成學界共鳴，從而將勢在必行[3]。

眾核軟件綜合流程中，其核心環節即是任務分配與調度，且屬于是典型的NP-hard問題[4]，業內通常用近似算法或元啟發式搜索算法來解決這類問題。根據任務集到處理器內核分配方式的不同，可以把任務分配與調度算法分為兩種類型：一種是不考慮物理平臺的約束，實現任務集合到邏輯處理器的映射。如：基于任務復制技術的CPFD算法[5]、TDS算法[6]、OSA算法[7]、PPA算法[8]，以及近些年來逐漸興起的SA算法[9]、ACO算法[10]、GA算法[11]等元啟發式算法；另一種類型是在考慮實際處理器結構、內核之間的通信帶寬以及數據交換方式的情況下，實現任務集合到物理處理器的綁定。如Mohammad[12]針對ASAP2平臺研發的一種具有通信開銷的任務集合到物理處理器內核綁定與調度的BAMSE算法。但在國內ASAP2的眾核處理器架構在使用上并未可見強勢覆蓋，而基于片上網絡拓撲結構的2D-Torus眾核處理器架構則憑借其較低的通信延遲和優異的拓展性正逐漸成為業界研究的熱點[13-14]。針對這一現狀，本文根據2D-Torus同構眾核平臺的特點，對BAMSE算法提出了處理改進，實現了具有通信開銷的任務集到物理內核的綁定。并通過實驗探究了改進后的BAMSE算法的性能。下文將按照問題描述、任務選擇、內核選擇、解的構建的順序，詳細地敘述2D-Torus平臺下的BAMSE算法。

1 問題描述

應用軟件在眾核平臺上運行時可以通過任務劃分將其分解為一個具有依賴關系和通信開銷的任務集合[15]。業界常用任務模型對此任務集合進行抽象，常用的并行軟件任務模型有：DAG（Directed Acyclic Graph）、SDF（Synchronous DataFlow Graph）、KPN（Kahn Process Networks）、以及HTG（Hierarchical Task Graph）等。本文采用DAG作為軟件任務模型，如圖1所示。

圖1中，每個頂點代表一個任務節點，頂點中的數字代表此任務的任務量，連接頂點的弧代表任務的執行順序，弧上的權重代表任務之間的通信開銷。DAG圖經過抽象可用四元組G = {V， E， W， C}表示，其中：

（1） 任務集合 ； 表示任務圖中第 個任務，N為任務圖中的任務總數。

（2） 任務集合中任務之間的依賴關系集合 ，集合中 表示任務 在 后執行； 為 前驅， 為 的后繼。

（3） 任務量集合 ； 為任務 的任務量。

（4） 任務集合中任務之間的通信開銷集合 ； 為任務 和任務 之間的通信開銷，若 和 被綁定到同一內核，則認為 。

由于眾核平臺的復雜性，目前的任務綁定與調度算法都是針對某一特定平臺，本文針對2D-Torus架構的眾核處理器平臺進行研究。在該結構中，每一個處理器內核均與單獨的路由器相連，而各路由節點均通過物理鏈路與東、南、西、北四個相鄰的路由節點互連；此外，每行的首尾路由節點以及每列首尾節點也通過物理鏈路互相連接，如圖2所示。

經過抽象，2D-Torus眾核平臺可用三元組H = {P， L， T}表示。其中：處理器內核的集合 ，M為平臺上物理內核數目； 實現各個內核互聯的物理鏈路 ；內核執行時間集合

進而，眾核軟件任務綁定與調度問題可描述為：在滿足任務間依賴關系集E和處理器內核間數據鏈路帶寬限制的前提下，從綁定和調度方法空間S中，找到一種將任務集中各任務綁定到2D-Torus各處理器內核上并按照一定的順序調度執行的方法 ，使任務集的總體執行跨度 最小，為此可構建公式如下：

其中， 為按照方法 進行調度時，任務集合 的執行跨度。

3 算法介紹

3.1 任務選擇

任務選擇過程就是在滿足任務圖約束的情況下，確定每個任務的調度優先級，生成合法調度序列的過程。本文在此采用Cuthill-McKee BFS[12]算法來確定任務調度序列。此算法首先按照寬度優先搜索算法遍歷的順序生成基本的調度序列，然后對具有多個后繼的任務節點進行優先級調整，得到最終的任務調度序列。如果把任務調度序列形象地看作一個隊列，那么處在隊首位置的任務優先級最高，隊尾位置的任務優先級最低。優先級調整的具體做法是：按照各子節點的度來確定調度的優先級，度越大優先級越低。如果把圖1表示任務集合分別按照普通BFS（Binary First Search）算法和Cuthill-McKee BFS算法進行調度，可得到如圖3所示的任務調度序列。

然后通過構建一個候選任務隊列來實現調度時的任務選擇。具體方法如下：

（1）建立一個空隊列。

（2）把當前任務圖中所有入度為零的任務節點按照Cuthill-McKee BFS算法確定的優先級依次入隊，優先級高的任務節點先入隊。

（3）從隊首到隊尾依次檢測，把第一個入度為零的任務節點出隊列，并且，把此任務節點的所有后繼節點的入度分別都要減一，這個出隊的任務節點就是本次迭代選擇的任務。

（4）循環步驟（2）～（3），直到所有的任務出隊列。

3.2 處理器內核選擇

在確定了任務的選擇方法后，需要按照各個任務的選擇順序依次把任務綁定到處理器內核上，按照何種策略進行綁定將是任務綁定與調度算法的核心關鍵問題。

在第一次迭代時，由于ASAP2眾核平臺的限制，開始任務必須要分配在最左邊一列的處理器內核上，而在本文研究的2D-Torus眾核平臺下，由于每個內核都可以通過路由節點接受和發送數據，且每個內核的自由度均為4，計算能力也都完全相同，故不需考慮這個限制。本文采取的任務綁定方案為：把開始任務綁定到任意一個內核，以后按照任務選擇的先后順序，每次迭代選取一個任務，并給這個任務確定m個候選內核，直至任務集合中的任務全部被綁定。每次迭代時選擇候選內核的方法如下：

首先假設通過物理鏈路直接相連的處理器內核間的距離為1。如果當前任務無前驅，則隨機選取m個內核作為候選內核；如果當前任務只有一個前驅，前驅任務綁定到內核 上，則認為距離內核 小于等于R（R=1）的處理器核心就是可能的候選內核。如果這個范圍內的內核數目大于等于m個，則隨機選取m個作為候選內核，否則，逐漸增加R，每次增加1，直到能夠取得規定數目的候選內核為止；如果當前任務存在多個前驅，則需要對每一個前驅執行單個前驅的操作，獲得此操作的候選內核的集合，并取交集來確定當前任務的候選內核。如圖4所示。假定R=1，m=1，當前任務為 ，其前驅任務為 和 ，分別被綁定在內核 和 上，則任務 的候選內核集合可以為{ }，但不能是{ }，由于 到 和 的距離均為不超過1（R=1），而 到 的距離為3，則大于此時的R。

此后，再分別把當前任務綁定在這m個候選內核上執行，確定當前任務子集（已經分配內核的任務集合）的執行跨度，同時把符合條件的狀態添加入下次迭代。

3.3解的構建

本文通過維持一個大小為ws的狀態列表來進行解的構建，狀態列表中的每一條記錄代表一種任務綁定的狀態，記錄中保存的信息包括：這種綁定狀態的最長物理鏈路長度（LC）、全部物理鏈路長度的總和（TC），以及這種狀態的執行跨度。狀態列表按照記錄中的執行跨度升序排列。在每次迭代開始之前，假定當前的狀態列表為List1，需要通過這次迭代構建的新的狀態列表為List2，那么List2的構建過程如下：

首先通過內核選擇過程可以得到當前任務候選內核的集合，把當前任務分別綁定到這些候選內核上執行，可以得到m條新的狀態，這些新的狀態對于狀態列表而言也就是m條新的記錄，由于List1中的每條記錄均可產生m條新的記錄，而這m條記錄就是綁定當前任務時產生的m個新的狀態，故可以把這m條新的記錄調存在List2中；然后按照List1中記錄的順序，循環地添加對應的m條新記錄到List2中，并對這些記錄按照執行跨度進行升序排列，直到List1中的記錄全部完成了遍歷。如果狀態列表List2的大小超過了ws，則把新產生的記錄的執行跨度與List2中最后一條記錄的執行跨度進行比較，如果前者比后者小，則用新產生的記錄替換List2中最后一條記錄，并對List2中各條記錄重新進行升序排列，否則，舍棄這條新的記錄，這樣就完成了狀態列表List2的構建。狀態列表List2的構建過程對應著每次迭代中的狀態的篩選，這樣當迭代結束后，狀態列表各記錄中執行跨度的最小值，就是BAMSE算法得到的最優解。如果存在兩條及兩條以上的記錄執行跨度相同，則優先選擇LC較小的作為最優解，如果LC也相同即選擇TC較小的作為最優解。

通過解的構建過程可以發現，ws的大小決定著進入下次迭代的狀態數目，故ws不能太大，也不能太小。ws 太大容易使進入下次迭代的狀態數目過多，造成解空間的指數性增大，求得最優解的效率也將隨即降低。ws太小又會讓BAMSE算法具有貪婪性，導致求得的最優解精度降低。

4 實驗仿真

為了分析改進后的BAMSE算法在2D-Torus眾核平臺下的性能，本文采用早稻田大學的標準任務圖集作為任務圖的數據源。實驗隨機選取了任務圖集中任務數目為50、100、300的任務圖文件，每個文件包含軟件任務模型以及各個任務的編號、任務量、任務前驅和后繼等信息。本文算法采用C語言實現，程序運行環境為Microsoft Visual Studio 2010，試驗主機配置如下：Windows 7 系統，CPU 為 Intel（R） Core（TM）2 Duo CPU T6600 @2.2GHZ，內存為 4GB。

本文通過對不同任務數目和處理器內核數目的情況進行實驗仿真，得到改進后的BAMSE算法在2D-Torus眾核平臺的執行情況。另外，通過分別對不同的ws和m進行實驗，得到了ws和m相應不同時BAMSE算法的影響，具體的實驗如下。

首先，對任務數目分別為50、100、300，處理器內核數目為4、9、16，m = 2，ws = 5的情況進行實驗，得到的結果如圖5所示。

其次，對任務數目分別為50、100、300，處理器內核數目為4、9、16，m為一定值（m=2），對ws不同的情況進行實驗，得到結果如圖6所示。

最后，對任務數目分別為50、100、300，處理器內核數目為4、9、16，ws 為一定值時（ws= 10），對m不同的情況下進行實驗，得到的結果如圖7所示。

由圖5、圖6和圖7結果可知：當任務數目一定時，隨著處理器內核數目的增多，BAMSE算法所得到的執行跨度逐漸變小；當內核數目一定時，隨著任務數目的增多，BAMSE算法所得到的執行跨度逐漸變大。并且，由圖6和圖7還可看出，m和ws在一定程度上會對BAMSE算法的求解精度產生影響。具體表現為：當m一定時，隨著ws的增大，任務集的執行跨度逐漸變小；當ws一定時，隨著m的增大，任務集的執行跨度也逐漸變小；

綜上所述，改進后的BAMSE算法在2D-Torus同構眾核平臺上可以實現任務集到物理內核的綁定，且求解精度會受到最少候選內核數目m和綁定列表大小ws的影響。

5結束語

眾核處理器已成為處理器發展的主流趨勢。近些年來，針對2D-Torus眾核平臺上任務綁定與調度問題的研究正逐漸成為學術界的熱點。本文針對2D-Torus同構眾核平臺，提出一種基于BAMSE算法的任務綁定與調度方案，并通過實驗探究了該算法的性能。目前，元啟發式搜索算法在NP-hard問題的求解中應用漸趨廣泛，本文下一步的研究工作重點即為從元啟發式算法的角度出發，設計適合于2D-Torus眾核平臺的任務綁定與調度方案。

6 參考文獻

[1] GEER D. Chip makers turn to multicore processors[J]. Computer， 2005， 38（5）：11-13.

[2] BORKAR S. Thousand core chips： A technology perspective[C]// Proceedings of the 44th Design Automation Conference， DAC 2007. San Diego， CA， USA ：IEEE， 2007：746-749.

[3] Hashemi M. Automated Software Synthesis for Streaming Applications on Embedded Manycore Processors[D]. California： University of California， 2011.

[4] BEUME N， NAUJOKS B， EMMERICH M. SMS-EMOA： Multi-objective selection based on dominated hypervolume[J]. European Journal of Operational Research， 2007， 181（3）：1653-1669.

[5] AHMAD I， KWOK Y K. On exploiting task duplication in parallel program scheduling[J]. Parallel & Distributed Systems IEEE Transactions on， 1998， 9（9）：872-892.

[6] DARBHA S， AGRAWAL D P. Optimal scheduling algorithm for distributed-memory machines[J]. Parallel & Distributed Systems IEEE Transactions on， 1998， 9（1）：87-95.

[7] PARK C I， CHOE T Y. An optimal scheduling algorithm based on task duplication[C]// 2013 International Conference on Parallel and Distributed Systems IEEE Computer Society. Washington：IEEE， 2001：0009-0009.

[8] ZHOU Shuang E， YUAN You guang， XIONG Bing Zhou， et al. An algorithm of processor pre-allocation based on task duplication[J]. Chinese Journal of Computers， 2004 （2）：216-223.

[9] ATTIYA G， HAMAM Y. Two phase algorithm for load balancing in heterogeneous distributed systems[C]// 16th Euromicro Conference on Parallel， Distributed and Network-Based Processing （PDP 2008）IEEE Computer Society. Toulouse， France：IEEE， 2008：434-439.

[10] FERRANDI F， LANZI P L， PILATO C， et al. Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems[J]. Computer-Aided Design of Integrated Circuits and Systems， IEEE Transactions on， 2010， 29（6）：911 - 924.

[11] GOLUB， KASAPOVIC M， SUAD. scheduling multiprocessor tasks with genetic algorithms[C]// Proceedings of the IASTED International Conference Applied Informatics. Innsbruck ： ACTA， 2002： 273-278.

[12] FOROOZANNEJAD M H， HASHEMI M， MAHINI A， et al. Time-scalable mapping for circuit-switched GALS chip multiprocessor platforms[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2014， 33（5）：752-762.

[13] 郭彬. 片上網絡拓撲結構的研究[D]. 西安：西安電子科技大學， 2010.

[14] 劉有耀. 片上網絡拓撲結構與通信方法研究[D]. 西安：西安電子科技大學， 2009.

[15] 閆喬， 覃志東， 王紹宇，等. 同構多核/眾核處理器任務分配自適應模擬退火算法[J]. 計算機科學， 2014，41（6）：18-21.