片上多处理器系统的多线程调度策略

摘要：本文提出了一种多线程调度策略，解决片上多处理器系统的线程分配问题。实验证实，本文的线程调度策略有效地实现了系统的负载均衡。

关键词：片上多处理器；多线程调度

中图分类号：TP332 文献标识码：A文章编号：1007-9599 (2011) 12-0000-02

Multi-Threaded Scheduling Policy of Chip Multi-processor System

Wu Lin

(Xi'an Institute of Computing Technology,Xi'an710068,China)

Abstract:This paper presents a multi-threaded scheduling strategy to tackle the multi-processor system-on-chip thread allocation.Experiments confirmed that this thread scheduling policy effectively to achieve the system's load balancing.

Keywords:Chip multi-processor;Multi-threaded scheduling

一、引言

随着SOC技术的发展，片上多处理器（Chip Multiprocessor，CMP）[1]系统处理器核的数量增多；多线程编程技术的发展，每个任务包含线程的个数增多。CMP中的各个处理器核间满足低延迟和高带宽的通讯要求，能够快速的在各处理器核之间传输数据，通讯开销较小。利用多处理器系统这种通讯便捷的优势，将多线程分配给多个处理器，可大大提高线程的并行性。

调度是求得最优分配是一个NP难问题[2]，近年来的研究通过优化求解或启发式求解获得近优方案。文献[3]提出一种立体编码的遗传算法TDC实现CMP任务分配，迭代次数少，能够得到较好的分配结果，但是由于遗传算法实现较为复杂，分配决策过程耗时较长。文献[4]提出启发式调度算法，以任务的执行时间和处理器核的平均负载量作为启发目标进行任务的调度，获得较好的负载平衡，但迭代判优重组过程实现较为复杂，平均迭代次数在10次以上，算法效率不高。这些算法分配任务到一个处理器核上，不适用于CMP结构。本文设计了TAMG算法实现多线程在CMP系统上的均衡分配。

二、CMP系统的线程调度策略的核心思想

将关系密切的线程分配到同一处理器核或临近的处理器核上，从而使得系统的通信代价减小。同时要保证每个处理器核上执行时间的均衡，通过无向带权图来描述线程之间的耦合关系，确保减少核间通信和核间负载均衡，划分关系图，将关系密切的线程分在一组，完成任务内的线程集到处理器核的分配。

三、基于TAGM算法的线程层分配

（一）线程分配模型

假设m个线程，分配给N个处理核，目标是最小化通信开销与负载均衡。共有Nm种子图划分方案，使用穷举法寻找最优解是不可行的，只能在尽量满足条件的前提下获得近优解。

用无向带权图G=表示任务内线程之间的耦合关系（Thread Affinity Graph，TAG），V、E、W分别表示节点、边和边上的权值，节点对应线程，节点间的边表示线程之间有共享数据关系，边上的权值描述线程之间共享数据的程度，权值越大，耦合关系越强。

线程分配的过程看成线程关系图节点融合的过程。融合节点可以是一个或多个原始节点，两个融合节点可以合并得到一个新的融合节点。TAG图的节点融合描述为如下的过程：对于一个图G，得到融合后的节点集合V’={V1’，…，Vk’}，每个融合节点对应一个线程集合：Vi'Ti’（i=1…k）。

（二）线程关系图节点融合算法TAGM的思想

输入线程集T的线程关系图信息，以及对应处理器核数目N。算法的基本思想就是从初始的线程关系图开始，每次选择节点融合，保证融合后的所有边的权值之和在所有融合方案中最小，并且融合后得到的融合节点其总执行时间不超过阈值，重复此选择-融合过程，经过若干次迭代后可以得到N个融合节点，这些融合节点对应的就是最终分到处理器核上的线程集。阈值可按如下公式：

其中ε是一个调节量，用来均衡和减少通信开销之间的平衡，具体计算时，可以将ε设定为平均计算时间 的一个百分比。

迭代的过程就是TAG图中节点融合的过程，融合节点有两种思路，单边融合，每次选择权值最大的边，判断阈值情况后选择合并节点，迭代次数为m-N；多边融合，每次选择没有公共节点的若干条边，构成最大匹配边集合，判断阈值情况后一次性融合多对节点，迭代次数为2N（1-N/m）。单边融合在图中节点个数较少的时候效率较高，随着节点个数的增加，迭代次数也增加，效率降低。多边融合计算最大匹配边集合比较耗时，在节点个数较少的时候效率不高，随着节点个数的增加，一次能够融合多对节点，效率有明显的提高。综合两种算法的优劣性，在节点个数较多的时候选用多边融合，在节点个数较少的时候选用单边融合。

在大量样本测试的基础上，得到效率分界点时的线程个数X与处理器核数目N的离散函数关系X=f（N），作为选择算法分界点的经验值。

（三）TAGM算法的实现

本文提出了TAGM（Thread Affinity Graph Merging）算法，主要包括两个过程，单边融合和多边融合。

1.单边融合的方法，每次选择权值最大边，按照公式（3）计算阈值，在阈值判断后，将不满足要求的边加入exception vector，融合满足条件的节点：合并融合节点Va和Vb，形成新的融合节点Vc，重复此过程直到节点个数不满足条件。

2.多边融合的方法，找到互相没有公共节点的最大匹配边集合，对于这些边分别进行阈值判断，将不满足要求的边加入到exception vector中，融合满足条件的节点，重复此过程直到结点个数不满足条件。

本文通过改进匈牙利算法计算最大匹配边集合，能够快速找到近优解。方法如下：

（1）找一条边，两节点时间之和最大，此边作为初始match，将此match加入match vector中，标记其中一节点为first，另一节点为last，将两节点加入match nodes中；

（2）取出match vector中最新加入的match，任意选择match中与first有边的节点A，并且A没有在match nodes中，任意选择match中与last有边的节点B，并且B不在match nodes中；

（3）如果A存在，将此边加入到match的head，将A加入match nodes中，如果B存在，将边加入match的tail，将B加入match nodes中，更改后的match添加match vector中，转到（2）；

（4）如果A、B都不存在，计算match vector中每个match边权值的和，返回权值和最大match。

（5）结束

四、评价与分析

（一）TAGM算法的评价

随机生成了50000个线程关系图，首先使用单边融合算法和多边融合算法分别对关系图进行划分，得到效率分界点的线程个数X与处理器核数目N的离散函数关系X=f（N）作为选择算法分界点的经验值，实验结果如图1所示。图中纵坐标表示算法对节点个数相同、连接方式不同的50000个关系图进行融合计算时间的均值，横坐标表示线程个数。

图1:4核、16核情况下单边融合多边融合算法效率比较

图1（a）为处理器核数为4时分配算法的效率随着线程个数增加的变化。从图中可知线程个数大于18时，多边融合的效率明显高于单边融合；图1（b）是线程个数在8-17区间时两种算法的效率比较，可以明显看出线程数等于13时多边融合算法的时间开销低于单边融合，则X4=f（N=4）=13；同理，由图1（c）（d）可知，当处理器核个数等于16，线程个数等于23时，多边融合算法的效率明显高于单边融合，则X16=f（N=16）=23。TAGM算法中作分界点判断的经验值为X4=13。

TAGM算法与单边和多边融合的效率比较结果如图2所示。

图2:三种算法效率比较

从图2（a）中可以看出，在线程个数大于23时，TAGM算法的效率明显高于单边融合算法。图2（b）中，当线程个数超过13时，TAGM算法效率明显高于单边融合和多边融合算法效率。实验结果证明，TAGM算法综合了多边融合和单边融合两种算法的优势，节省了分配过程中的额外时间开销。

（二）线程调度系统负载平衡情况

将TAGM算法与文献[4]中的启发算法进行比较，取文献[4]中获得的任务集信息作为实例，如表1。完成80个任务在多核系统上的分配。为了便于比较，不失一般性的对问题进行以下假设：

1.将线程作为计算量的最小单位，每个线程执行的时间相同，那么可用线程数量来表征任务的计算量。

2.认为线程间通信量一致，即线程层分配将实现所有线程在处理核集内的平均分配。

在满足以上假设之后，可将本文算法与[4]中的启发算法进行负载平衡性能的比较。

表1：任务集信息

任务集输入信息

84 40 16 58 6 17 97 51 46 24

77 59 33 32 11 91 61 15 66 41

86 8 40 12 89 40 88 92 24 6

38 39 89 94 12 52 40 39 52 93

94 8 65 27 14 88 55 21 46 3

96 18 6 97 8 95 55 42 52 19

91 76 63 26 96 62 97 17 30 63

12 35 55 94 83 63 68 98 54 42

80个任务共包含4092个线程，分给16个处理核，每个处理核的理想平均负载为255.75。图3为四种分配策略的负载均衡性比较：

图3：系统负载平衡情况比较

文献[4]中的实验证明该启发算法具有较好的负载平衡性。从图中可以看出，本文的策略能够与文献[4]中的启发算法达到较为相近均衡程度，但是由于文献[4]的启发算法得到最优结果要进行3次优化迭代，最好情况下，该算法执行时间是任务层次分配算法执行时间的5倍。

五、结论

本文针对片上多处理器系统中的线程调度问题进行了分析，并通过以上运算结果及其分析可以看出，根据线程集间的耦合关系进行线程到处理器的分配，在较短时间内得到近优解，有效地实现了系统的负载均衡。

参考文献：

[1]Spracklen L,Abraham SG.Chip multithreading:Opportunities and challenges[J].11th International Symposium on High-Performance Computer Architecture,Proceedings,，2005,248-252

[2]吴佳骏.多核多线程处理器上任务调度技术研究[D].中国科学院研究生院,2006

[3]A Abraham RB,B Nath.Nature’s Heuristics for Scheduling Job on Computational Grids[C].ADCOM,2000,45-52

[4]张金泉,倪丽娜,蒋昌俊等.独立任务调度的启发式算法[J].计算机工程与应用,2005,22-25

[作者简介]吴琳，辽宁人，计算机科学与技术硕士，现任中航工业计算技术研究所助理工程师，从事处理器硬件研究与设计。