2D—Torus 眾核任務綁定與調(diào)度的近似算法

丁軍　覃志東

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

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

中圖文分類號：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引 言

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

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

1 問題描述

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

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

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

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

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

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

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

經(jīng)過抽象，2D-Torus眾核平臺可用三元組H = {P， L， T}表示。其中：處理器內(nèi)核的集合 ，M為平臺上物理內(nèi)核數(shù)目； 實現(xiàn)各個內(nèi)核互聯(lián)的物理鏈路 ；內(nèi)核執(zhí)行時間集合

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

其中， 為按照方法 進行調(diào)度時，任務集合 的執(zhí)行跨度。

3 算法介紹

3.1 任務選擇

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

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

（1）建立一個空隊列。

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

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

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

3.2 處理器內(nèi)核選擇

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

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

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

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

3.3解的構建

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

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

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

4 實驗仿真

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

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

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

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

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

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

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

5結束語

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

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] 郭彬. 片上網(wǎng)絡拓撲結構的研究[D]. 西安：西安電子科技大學， 2010.

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

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