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.