多核处理器将两个或多个计算核心集成在一块集成电路芯片中，能够以并行化的方式将软件程序的多个任务分配到处理器中的不同处理核上同时执行，以提高处理速度．然而，当前程序的串行化设计方式，很容易出现一个或少数几个承担大多数任务的重载核与多个处于空闲或只承担极少数任务的轻载核并存的负载不均衡状态，无法充分发挥多核并行的计算优势．为了解决这一问题，须要对多核运行环境进行均衡模型构建，并利用任务分配和任务迁移技术对软件程序进行有效的并行化处理．多核环境均衡模型的构建，须要综合考虑处理核数量、任务数量、任务执行开销和任务间通信代价等诸如因素．文献[1]构建了基于单片多核处理器的动态负载均衡模型，给出影响多核处理器负载均衡诸多因素的正式描述．文献[2]针对未考虑主调度核的利用率和任务队列存在伪共享缓存缺失的问题提出了一种改进的任务调度模型，取消了核的分类并加入了多模式工作机制，不过缺乏在工作模式转换频率和转换时间方面的探索．文献[3]考虑集群处理器、内存、网络带宽及磁盘外设资源之间的负载均衡，建立物理节点间的合作博弈模型，有效提升各节点的平均负载均衡度．任务分配是利用处理核资源配置和初始任务特征等静态信息，当进行编译时将任务派发给各个处理核，达到初始的负载均衡，但是这种均衡状态并不稳定，会因为任务执行带来的任务状态变化而被打破，因此须要根据整体的任务和处理核的实时状态进行任务的重新安排，以实现多核任务负载的动态均衡．文献[4]研究了多种任务分配和迁移算法，提到一种象限分治的任务迁移思想，通过迭代式的象限划分重分配某个重载核的任务，但是该算法以任务数量作为迁移选择的依据，最终的结果不能体现真正的负载均衡．文献[5]针对汽车软件的多核任务执行提出一种任务分配和调度的负载均衡方法，对高安全性任务进行了优先排序．文献[6-7]针对嵌入式视觉应用程序的任务调度，提出一种独占最早完成时间算法，并在大量的基准测试集合计算机视觉与深度学习应用程序的组合上进行了实验分析．文献[8]提出一种适用于微内核操作系统的集中式全局动态多核负载均衡方法，不过仍存在着最佳阈值参数选取和根核心节点是否参与调度等问题未能解决．文献[9]提出一种多核并行子图匹配算法以实现负载均衡，只是其中在主核上构建基于路径的子图结构需要较大的开销．文献[10]利用独立队列替代共享队列，同时结合紧急任务优先调度的方式考虑负载均衡的实现．文献[11]研究了在处理核与任务划分预先绑定架构下的多核任务负载均衡分析与评估算法，能够支持分区任务的合理均衡分配．文献[12]面向虚拟机任务迁移开展了节能调度算法的研究．文献[13-14]针对专门的处理架构和应用问题开展了动态负载均衡方法的研究，只是相应的方法依赖于特定平台架构和应用特征，通用性和移植性较差．本研究基于构建的三元任务模型和方阵化同构多核阵列架构，提出一种采用多核象限分治思想实现任务迁移的动态负载均衡机制(DLBQ)．该机制通过对方阵化处理核阵列的迭代象限划分进行重载核任务的动态迁移，实现运行时的动态负载均衡．1 负载均衡系统模型1.1　多核任务负载均衡问题描述一个处理核c上的计算资源是有限的，其数量用r表示．而运行在处理核上的一个任务d可以使用一个三元组进行描述，即d=t,s,p，其中；t为任务执行时间，通过统计尚未执行的任务指令的时间获得，这里任务中每种指令的执行时间通过对测试程序添加计时代码后在实际硬件上运行获得；s为任务计算量，通过统计尚未执行的指令操作所需计算资源数得到，而每种指令的计算资源数通过估算完成该指令功能所须计算部件包含的晶体管数量获得；p为任务优先级，根据任务执行时所处执行阶段动态标记．任务执行过程划分为初始阶段、等待阶段、准备阶段、活动阶段和完成阶段，优先级依次降低．对多核任务的负载均衡问题，作如下相关定义：a．处理核集合C={c1，c2，…，cn} (n ∈ N*)；b．正在执行的任务集合D={d1，d2，…，dm} (m ∈N*)；c．D的n划分Π(D)={D1，D2，…，Dn}，该划分应同时满足条件：Di⋂Dj=∅ (1≤i,j≤n,i≠j);D1⋃D2⋃⋯⋃Dn=D;∑di∈Djdi.s≤cj.r (j=1,2,⋯,n).D的一个n划分对应了m个任务到n个处理核的一个映射，其中每个子集Di表示第i个处理核所承担的任务集．定义如下所示的均方差值σ表示多核任务负载均衡度(LBF)，即σ2=1n∑∑di∈Dj1≤j≤ndi. t -∑l=1mdl.  t/n2，式中：d为某个任务；D为任务集；n为处理核数量；m为任务集中的任务数量；i，j，l为序号．在D的所有n划分中，必然存在一个使得σ最小的n划分，对应的多核任务负载最为均衡．1.2　方阵化的处理核阵列架构为提高任务迁移的效率，降低迁移带来的额外开销，设计一种多核处理器中处理核的方阵化排列架构，如图1所示，图中：每一个正方形框代表一个处理核位置，用ca,b中的下标值a和b来分别表示处理核在方阵中的行位置和列位置；深灰色框表示该位置放置有处理核；白色框表示该位置不放置处理核；核与核之间利用纵横交错的互连资源(用正方形框四周的浅灰色条表示)连接，以缩小和规整核间距．10.13245/j.hust.239331.F001图1同构处理核的方阵化排列架构示意图假定处理器中核的数量n=2k，k为非负整数，有：a．当k=0时，n=1，为单核处理器；b．当k=1时，n=2，两个处理核并排排列；c．当k1时，在k不同取值的情况下对处理核的排列作如下设计：若k为偶数，n=2k/2×2k/2，则按图1(a)所示的2k/2阶方阵进行排列；若k为奇数，则n个处理核不能构成方阵，但可证明必然存在两个自然数i和j，满足2k=i2-j2 (i=3×2k-32,j=2k-32)．即n个处理核可以排列成一个在中部去除j阶方阵后的i阶方阵，如图1(b)所示．为了能够进一步均衡核与核的间距，可以将位于中部j阶方阵中的j2个空位分散到i阶方阵中所有满足如下公式的位置ca,b，从而形成如图1(c)所示的方阵结构，即：a=3w1-1 (1≤w1≤j);b=3w2-1 (1≤w2≤j),式中w1和w2为[1，j]内的某个自然数值．2 象限分治动态负载均衡机制2.1　多核任务的象限分治迁移过程系统的多核负载均衡度σ会随着各处理核上任务的执行而动态变化．当σ超过一定阈值时，系统将被视为处于负载不均衡状态，而此时必然存在任务负载相对过重的重载核，这就须要对重载核的任务进行迁移，以使系统重新处于负载均衡状态．为了使完成迁移后的各处理核负载尽量均衡及迁移过程的开销也能够尽量均衡，当进行任务迁移时，对处理核方阵进行象限划分，将处于某一象限中的某个重载核上的任务迁移到其他三个象限中与其曼哈顿距离最短的处理核上；若还存在重载核，则在每个象限内再进行象限划分作进一步的任务迁移，依此重复，直至不再存在重载核或每个象限只有1个(当k为偶数时)或8个(当k为奇数时)处理核，如图2所示，图中：条纹黑色方框表示重载核；条纹深灰色方框表示轻载核．10.13245/j.hust.239331.F002图2多核任务的象限分治迁移过程假定某次划分象限时的方阵大小为i×i，由于四个象限具有空间对称性，以重载核ca,b处于第一象限为例，因此其迁移的目标核位置应满足如下约束：ca,  i/2 (第二象限);ci/2+1,  i/2 (第三象限);ci/2+1,  b (第四象限).对于k为奇数情况下，当多次划分到每个象限为8个处理核时，若还存在重载核，则将根据曼哈顿距离将任务从该重载核向同一象限中的其他处理核进行扩散迁移．2.2　基于象限分治的任务动态迁移算法任务迁移将在检测到系统负载处于不均衡状态下进行．当进行迁移时将首先根据重载核上任务的优先级，结合任务剩余执行时间和计算量需求选择迁移的任务，DLBQ动态迁移算法的输入为处理核集合C和当前任务集的n划分Π(D)，输出结果为新的任务集的n划分Π(D)*．算法的象限迭代分治过程具体步骤如下．步骤1 检测获得重载核c．步骤2 对c上的任务按优先级p降序排列，得到有序任务队列T(不包含处于完成阶段的任务，该类任务不在迁移考虑范围)．步骤3 获取当前处理核阵列范围，划分象限并建立对应的四个任务子队列，按序将T中的任务逐个放入当前所含任务总执行时间最小的子队列．若出现多个子队列的任务总执行时间相等，则随机选择除c所在象限对应子队列外的一个．步骤4 计算每个任务子队列的总计算量，若超过对应象限中各处理核的总计算资源数，则选择其中优先级较低的任务调整到c所在象限对应子队列．步骤5 将非c所在象限的子队列中的任务迁移到目标象限中相应位置的处理核上．步骤6 返回步骤1进行迭代．3 实验与结果分析为了验证DLBQ中动态迁移算法的相关性能，将其与文献[8]中仅考虑任务数量的象限分治负载均衡算法(实验中命名为Base)进行对比实验．3.1　实验条件设定实验中实际采用的计算机硬件配置为Intel i5-3210M 2.5 GHz处理器、64 GiB内存，实验过程通过软件模拟产生不同数量处理核和任务完成．多核任务在执行时间和计算量上具有随机性，而当研究多核负载均衡时更关注核与核之间的相对情况．为便于分析比较，利用文献[15]提出的任务划分方法和测试数据集划分任务，每次按数量梯度为100划分得到总数不超过1 000的任务集合，且任务数须超过处理核数的两倍以上；同时采用相对量处理，将任务执行时间映射到[0，100]区间，任务计算量映射到[0，30]区间，并设定单个处理核的计算资源数为所有任务总计算量与处理核数比值的两倍．任务执行的五个阶段采用数值表示：0为初始阶段；1为等待阶段；2为准备阶段；3为活动阶段；4为完成阶段．数值越大，优先级越低．任务优先级将随任务执行而动态变化．设定当出现某个处理核所承担任务的计算量总和超过该处理核计算资源数的两倍时，将触发迁移算法．迁移算法可以在多个重载核上并行执行，在实验中设定初始状态为1个重载核，处理核数目分别使用24，25，26，27．3.2　迁移效果实验与结果分析进行任务动态迁移后的效果可以从负载均衡度和系统效率两个方面进行衡量．3.2.1　负载均衡度多核的任务负载均衡度σ由各个处理核上任务总执行时间的均方差表示，其值越小表明系统均衡度越好．不同实验条件下得到的σ结果如图3所示，图例采用“算法名称-处理核数量”来表示不同的实验情况(后续实验结果图的图例含义均同此)．为便于表示和比较，对实验得到的σ值进行取对数处理．10.13245/j.hust.239331.F003图3迁移后系统负载均衡度的实验结果由图3可以看出：DLBQ算法和Base算法得到的结果明显分离，DLBQ算法的结果要比Base算法的小得多．通过对实验结果进一步分析计算可知：DLBQ算法得到负载均衡度要比Base算法低1~2个数量级，平均约为1.48个数量级，并且处理核越少任务越多，改善幅度越大．在相同处理核数的情况下，Base算法的负载均衡度随着任务的增加基本持续一个上升的趋势，而DLBQ算法则呈现一个平稳的状态；在任务数目相同的情况下，Base算法的结果随处理核数的增加而降低，而DLBQ算法的结果则相反．综合分析上述结果可知：Base算法由于只考虑任务数量进行迁移，虽然能够有效降低重载核的负载，但是较大可能存在将大量执行时间较长的任务迁移到少数几个处理核的情况，因此导致系统整体仍处于或更易于进入负载不均衡状态；而DLBQ算法兼顾考虑了任务执行时间、计算量和执行阶段的特征，并基于专门设计的方阵架构进行选择性迁移，能够将迁移后各个处理核的执行时间方差维持在一个较低的值，以获得更好的负载均衡效果．3.2.2　系统效率在多核处理系统中，完成所有任务的执行时间(包含运行迁移算法所需时间)取决于完成所承担任务用时最长的处理核，因此定义系统效率e为完成所承担任务用时最长的处理核执行时间的倒数，即e=max∑d∈Did.  t-1    (1≤i≤n)，式中max函数为在n个子任务集中选择任务总执行时间最大的时间和．实验得到的系统效率结果如图4所示，可以看出：在相同实验条件下，DLBQ算法的迁移效率都优于Base算法．对实验结果进一步分析计算可得：平均效率提高幅度约33.6%；当处理核数相同时，随着任务数量的增加，DLBQ算法的效率优势逐渐减小；而当任务数量相同时，处理核越多，DLBQ算法的效率优势就越明显．10.13245/j.hust.239331.F004图4迁移后系统效率的实验结果3.3　迁移开销实验与结果分析任务的迁移过程会给系统带来额外的负载开销，从迁移频率和迁移距离两个方面设计相关的实验进行分析．3.3.1　迁移频率迁移频率指任务集在多核上执行的过程中，因负载均衡调整而发生的任务从一个核迁移到另一个核的总次数，用f表示．不同实验条件下得到的任务迁移频率结果如图5所示．10.13245/j.hust.239331.F005图5迁移频率分析从图5可以看出：对于两种算法，迁移频率都随着任务数量和处理核数量的增加而增加．分析可得：当处理核数固定而任务数量增加时，由于平均分配到各个处理核上的任务负载也随着增加，某些轻载核在接收迁移过来的任务后很可能成为重载核，引发新的迁移过程而使迁移频率上升；当任务数固定而处理核数量增加时，平均分配到各个处理核上的任务负载将减少，系统负载均衡的阈值会随之下调，这会使得部分处理核的负载情况相对变重而成为重载核，从而引发新的迁移过程使迁移频率上升．从图5中还发现：在相同实验条件下，DLBQ算法中迁移发生的频率要比Base算法的小一些，根据实验数据计算可得平均降幅约为9.0%．不过DLBQ算法的这种降幅优势与任务数和处理核数的变化并未体现较明显的特征关系．3.3.2　迁移距离实验中设定相邻两个处理核之间的距离为1，迁移距离指被迁移任务的起止处理核之间的曼哈顿距离，用l表示．不同实验条件下得到的任务迁移距离结果如图6所示．10.13245/j.hust.239331.F006图6迁移距离分析从图6可以看出：迁移距离随任务数和处理核数的增加而增加，且基本呈现正比的增长关系．从迁移算法的机理分析可知，迁移算法目的是要将重载核上的任务经过选择均匀调整到其余的轻载核．当须要迁移的目标越远(即处理核越多)、须要迁移的任务越多时，产生的迁移距离之和就越大．同时，从图中可以观察得到：两种算法的迁移距离曲线基本重合，说明DLBQ算法的改进设计不会带来额外的迁移开销．4 结论随着多核系统的普及应用，多核任务的负载均衡问题受到广泛关注．本研究在定义了任务三元模型表示基础上，对多核负载均衡问题进行了形式化描述，确定了以各处理核上任务执行时间的均方差值作为负载均衡度的衡量标准；为规整和均衡处理核间距，设计了一种方阵化的多核阵列架构，并据此研究实现了一个基于象限分治思想的任务动态迁移算法，通过象限并行和多重迭代消除系统中的重载核，从而达到多核任务执行时的动态负载均衡．实验结果表明：所研究的负载均衡机制能够在不增加或稍有减小迁移开销的前提下，显著改善各个处理核的负载均衡度，有效减小多核系统完成所有任务的执行时间．未来的工作一方面可以扩展任务的三元模型表示，在负载均衡机制中增加考虑任务之间的相关性；另一方面可以扩展迁移初始状态从一个重载核变为多个重载核同时迁移，并且对触发迁移过程的负载均衡度阈值选取进行进一步研究．