沈小龙,马金全,胡泽明,李宇东

(信息工程大学 信息系统工程学院,郑州 450001)

0 引 言

信号处理应用通过有向无环图(Directed Acyclic Graph,DAG)建模为有依赖关系的任务集合。随着科技飞速发展,信号处理应用规模越来越大,功能日趋复杂,信号处理应用通过DAG抽象建模后的任务规模急剧上升,各任务功能不同,对处理器需求有差别,传统同构处理平台已经不能满足此需求,而异构信号处理平台包含丰富处理器资源,成为首要选择。任务在不同处理器上执行时间不同,调度算法决定任务分配情况,直接影响信号处理应用完成时间和平台处理器效率,因此调度算法研究尤为重要。

目前,根据搜索过程把任务调度算法分为启发式和元启发式调度算法。启发式调度算法分为3种:基于列表的调度算法[1-5]运算复杂度低,易于实现,适用于任务和处理器数量较少的情形;基于聚类的调度算法[6-8]可扩展性和鲁棒性较强,但要求聚类后的类别数量小于处理器数量;基于任务复制的调度算法[9-10]可对其他算法进行优化,扩展性较强,但会提高额外计算开销,增加算法复杂度。元启发式调度算法分为蚁群优化算法[11-12]、遗传算法[13-14]、粒子群算法[15-16]等,该类算法通过不断迭代从广泛解空间中找到符合目标性能的最优解,适用于任务较多情形。其中蚁群算法凭借着灵活性高、自适应性强且能够得到较优解的特点得到了广泛应用,在旅行商问题(Traveling Salesman Problem,TSP)、二次分配问题(Quadratic Assignment Problem,QAP)和作业车间调度(Job Shop Scheduling Problem,JSP)问题中取得了较好实验结果。但蚁群算法存在初始信息素不足、收敛速度慢、易陷入局部最优解等问题,且以上调度算法主要优化任务调度长度,属于单目标调度,在最终调度方案中,处理器负载不均衡,造成资源浪费。

基于以上背景,本文提出了一种基于蚁群优化算法的负载均衡调度算法(Ant Colony Optimization Load Balancing,ACOLB)。该算法针对蚁群算法初始信息素不足、搜索空间广泛、搜索时间较长等不足,采用优化初始信息素矩阵,指定蚂蚁遍历任务顺序,运用轮盘赌选择方式寻求最优解,并结合优化目标对启发因子和状态转移公式进行改进,在调度长度和负载均衡方面的性能均有明显改善。

1 系统模型

异构信号处理平台总体分为4层,如图1所示:底层为硬件层包含平台所有处理器资源,如中央处理器(Central Processing Unit,CPU)、图形处理器(Graphics Processing Unit,GPU)、数字信号处理器(Digital Signal Processor,DSP)、现场可编程门阵列(Field Programmable Gate Array,FPGA)等;底层之上为中间层,由操作系统层、板级支持包、平台抽象层等组成,通过对操作系统、驱动等建模,实现不同处理器间数据传输;中间层之上为组件层,包含项目组研发的所有组件,并根据组件特点分类管理;顶层为应用层,包含当前平台部署的信号处理应用程序。异构信号处理平台增加新信号处理应用时,首先进行功能分析从组件库中挑选组件搭建应用程序,然后利用调度算法为应用程序中组件分配处理器,最后通过中间层将组件部署到相应处理器,完成新应用程序在异构信号处理平台上的开发运行。

图1 异构信号处理平台架构

信号处理应用在异构信号处理平台运行时,调度算法决定了其执行时间和各处理器的负载情况,对系统整体实时性和各处理器工作效率影响较大,因此调度算法尤为重要。调度问题研究中,将应用程序抽象成DAG图,定义为G=(V,C,P,W)。经典DAG如图2所示。其中,V={vi}为任务集合与图中节点对应;C={Cij}为任务间平均通信开销与图中有向边对应,有向边表示任务间依赖关系和数据传递方向;P={Pi}为处理器集合;W={Wij}为任务在处理器上的计算开销,与表1相对应。针对某通信信号处理应用,假设所有处理器是连接通畅的,每个任务不可再拆分必须分配到处理器执行,且任务执行期间其所在处理器不可以再执行其他任务,若两个任务分配到同一处理器,则任务间通信开销为零。

表1 典型任务图计算成本表

图2 典型DAG任务图

2 ACOLB算法

2.1 算法思想

蚁群算法灵感来自于真实世界中蚂蚁的觅食过程。蚁群会根据环境变换表现出不同行为特性。蚂蚁从A到B有3条路径可供选择,其长度关系是 2<1<3。蚂蚁在行走过程中释放信息素标记路径,信息素随着时间推移而蒸发,假设每条路径信息素蒸发系数和行进速度相同。对于最初蚂蚁,3条路径初始信息素相同,随机选择路线,选择路线2耗时较短,残留信息素浓度较大;对于后面的蚂蚁,3条线路信息素浓度有差异,选择2的概率明显提高,在动态正反馈机制作用下引导整个蚁群选择最佳路线,找到问题最优解。

在蚁群算法思想上构建异构信号处理平台中信号处理应用的调度模型,应用通过有向无环图抽象成n个任务、m个处理器,蚂蚁需从任务列表中选择一个任务,通过处理器选择规则确定该任务运行的处理器,直到遍历完列表中所有任务。针对经典蚁群算法存在的不足,从任务优先级排序、信息素设置和更新、处理器选择三方面进行改进。

2.2 优先级排序

任务调度顺序对于最终调度结果十分关键,若有n个任务则调度顺序有n!种,造成搜索空间广泛,收敛速度慢。本文采用异构最早完成时间(Heterogeneous Earliest Finish Time,HEFT)算法任务优先级排序规则,计算公式如下:

(1)

2.3 信息素设置和更新

本文研究的通信密集型任务,任务间通信开销大于计算开销,降低通信开销有助于提升调度结果,而关键路径(Critical Path on a Processor,CPOP)算法采用关键路径任务分配到关键处理器思想,能极大减少通信开销,降低调度长度。因此,本文将CPOP调度结果作为初始信息素矩阵,解决初始信息素不足问题。以图2为例,CPOP得到的任务分配情况如表2所示。根据该表对信息素矩阵phe(pheromone)初始化设置,结果如公式(2)所示。

表2 经典DAG图任务分配情况

(2)

式中:phe(j,i)为任务j分配到处理器i的信息素浓度。受初始信息素矩阵引导,蚁群将向着降低通信开销方向不断迭代优化。每次迭代中蚂蚁为所有任务分配处理器,每只蚂蚁完成调度后的信息素增量Δphe计算公式如下:

(3)

式中:Δphe(j,i)为蚂蚁i为任务j分配处理器后引起信息素增量;Q为信息素增加系数;L(i)为蚂蚁在本次迭代中取得的调度长度。为获得更加全面的信息素矩阵,充分利用蚁群群体行为优势,将每只蚂蚁的Δphe累加后对信息素phe进行更新,更新公式如下:

phe=(1-ρ)×phe+Δphe(j,i)。

(4)

式中:ρ为信息素蒸发系数;phe按照蚁群迭代频次进行更新。

2.4 处理器选择

ACOLB算法通过对传统蚁群算法状态转移公式和启发因子改进,在调度长度基础上增加负载均衡优化目标。启发因子由eta和etb两部分组成。eta计算公式如下:

(5)

式中:EFT为蚂蚁完成时间矩阵。etb计算公式如下:

(6)

式中:num_process为处理器实时负载矩阵。ACOLB状态转移公式如下:

(7)

式中:p(i,k),phe(i,k)和eta(i,k)分别为任务i分配到处理器k上的概率、信息素浓度和完成时间倒数;etb(k)为处理器k累计任务量倒数;α,β,χ分别是phe,eta和etb的重要程度因子。

得到任务选择处理器概率后,运用轮盘赌方法确定任务运行处理器。首先计算任务i分配到处理器1～k的概率之和p(i,k)′,公式如下:

(8)

之后,从(0,1)内生成一个随机数rand,确定处理器集合find_process,公式如下:

find_process=p(i,k)′≥rand 。

(9)

选取find_process中编号最小处理器,作为任务i最终分配处理器。

2.5 算法步骤

ACOLB算法流程如图3所示,具体步骤如下:

图3 ACOLB算法流程

输入:DAG

输出:最优解

1 计算优先级列表和CPOP调度结果;

2 设置蚁群规模,迭代次数,phe,α,β,χ,ρ和Q;

3 迭代次数加1;

4 将上一次迭代中:EST,EFT,num_process,eta和etb进行重置;

5 任务数加1;

6 蚂蚁数加1;

7 分配处理器;

8 更新eta和etb;

9 如果有蚂蚁未对该任务进行调度,转到步骤6;

10 如果有任务未分配处理器,转到步骤5;

11 记录此次迭代中最佳调度结果;

12 更新信息素矩阵;

13 如果迭代次数不大于最大迭代值,转到步骤3。

3 仿真实验及性能分析

实验平台是CPU 为Intel(R) Core(TM) i5-1135G7 @ 2.40 GHz 、内存为16 GB的64位操作系统。随机DAG生成程序参数设置为任务数V={10,20,40,60,80},处理器数P={3,4,5,6},通信计算比CCR={0.1,0.25,0.5,0.75,1,2.5,5,7.5,10};并行因子Parallel={0.1,0.5,1,5,10}。CPOP算法对于通信密集型任务调度效果较好,因此将其作为对比算法,通过图1所示的典型DAG和随机DAG,验证ACOLB的有效性和可靠性。

3.1 优化目标

本文所提算法优化目标有两个,即调度长度makespan和负载均衡系数pld。makespan表示算法整体执行时间,越小越好,计算公式如下:

makespan=EFT(vexit)。

(10)

式中:vexit为出口任务。

pld表示系统内所有处理器负载均衡程度,越小越好,其计算公式如下:

(11)

3.2 参数设置

设置50只蚂蚁,进行1 000次迭代,信息素增加系数为1,信息素蒸发系数为0.25,phe重要程度因子α为1,eta重要程度因子β取值范围为0～2,etb重要程度χ为0～1,其中α,β,χ取值范围是通过大量实验确定的。

3.3 ACOLB有效性分析

为验证算法有效性,采用经典DAG和随机DAG进行实验,从调度长度和负载均衡两方面进行对比。

实验1：经典DAG如图1所示,其计算成本如表1所示。ACOLB调度长度如图4所示,CPOP负载情况如图5所示,ACOLB如图6所示。

图4 ACOLB的调度长度

图5 CPOP处理器负载情况

图6 ACOLB处理器负载情况

仿真得到CPOP调度长度为86,负载均衡系数为1.247 2;ACOLB调度长度为76,负载均衡系数为0.471 4,ACOLB调度长度和负载均衡均优于CPOP。ACOLB前期调度结果下降到某个值时,陷入局部最优出现振荡,后通过轮盘赌策略跳出,继续寻找全局最优解。ACOLB负载情况遵循CPOP调度结果引导,2号处理器仍是关键处理器,但较CPOP处理器负载分配情况,能更加均衡最大发挥各处理器性能,提高效率。

实验2：随机生成一个任务数为20,处理器数为5的DAG,应用两种算法得到的调度结果如表3所示。

表3 调度结果

从随机DAG结果可以看出,ACOLB调度长度和负载均衡系数均优于CPOP。对处理器负载均衡之后,关键处理器同CPOP保持一致,能够极大减少任务间通信开销。

从以上两个实验可以得出,ACOLB不仅对于经典DAG有改进效果,对于随机DAG同样可以起到优化调度长度和负载均衡的作用,证明了ACOLB算法的有效性。

3.4 ACOLB可靠性分析

为验证算法可靠性,对处理器和任务数量采用控制变量原则,从调度长度和负载均衡两方面进行对比。

实验3：随机生成一组任务数为20,处理器数分别为3,4,5,6的DAG。两种算法调度长度结果对比如图7所示,处理器负载均衡系数对比如图8所示,对结果进行计算得到调度长度优化率和负载均衡优化率。

图7 任务调度长度对比(实验3)

图8 处理器负载均衡系数对比(实验3)

从实验结果可看出,任务数目相同处理器数目不同时ACOLB算法依然可靠,相比于CPOP算法,其在调度长度和负载均衡方面均有改进,本组实验中调度长度优化率最小值是15.3%,负载均衡优化率最小值是44.5%。

实验4：随机生成一组处理器数为6,任务数分别为20,40,60随机任务图。两种算法调度长度结果对比如图9所示,处理器负载均衡系数对比如图10所示,对结果进行计算得到调度长度优化率和负载均衡优化率。

图9 任务调度长度对比(实验4)

图10 处理器负载均衡系数对比(实验4)

从实验结果看出,处理器数相同任务数不同时,ACOLB算法依然可靠,本组实验中调度长度优化率最小值是13%,负载均衡优化率最小值25%。

从实验3和实验4调度结果可看出,对于随机DAG,ACOLB算法仍然可以达到优化效果,其中调度长度优化率在13%以上;负载均衡改善效果明显,优化率在25%以上,实现了处理器负载均衡,提高了系统整体效能。

4 结束语

本文针对当前异构信号处理平台信号处理应用的调度算法中处理器负载不均衡造成系统资源利用不合理的问题,提出了ACOLB算法。该算法在蚁群优化算法基础上,利用CPOP调度结果解决初始信息素不足问题;利用HEFT调度列表缩小搜索空间,提升搜索速度;利用轮盘赌策略跳出局部最优解;增加负载均衡启发因子均衡调度结果。通过仿真得出,ACOLB算法在任务调度长度和负载均衡方面均有改进,证明了算法的有效性和可靠性。其中调度长度优化率为13%,优化效果一般,是下一步研究方向;负载均衡优化率为25%,优化效果明显。运用该算法可解决处理器负载不均衡问题,使异构信号处理平台负载更加均衡,发挥最大效能。