基于异构多核处理器的静态任务调度研究(二)
扫描二维码
随时随地手机看文章
接上文:
基于异构多核处理器的静态任务调度研究(一)
3 实验验证
3.1 性能评价参数
在静态任务调度中,任务调度的开销比较小,任务调度的总长度成为评价一个任务调度算法的性能标准,除此之外还有任务调度长度比率、算法的效率等,具体的评定标准和公式如下:
(1)调度长度makespan,为所有处理器上的最大任务调度长度。
(2)调度长度比率SLR,计算公式如式(9)所示,分母为所有关键路径任务执行时间的最小值之和。SLR的值总是大于等于1的,且值越小,任务调度算法性能越好。
(3)算法效率Efficiency,计算公式如式(10)所示,分子为任务调度的加速比,计算公式如式(11)所示,分母为任务调度中处理器的数量,Efficiency值越大表明任务调度算法的性能越好
3.2 实验与结果
实验将任务调度性能测试分成两组,通过仿真实验检验WPTS算法在不同任务中的性能。
实验1:利用随机任务产生器[10-11],根据参数值v(DAG的任务数量,取值为{30,40,50,60,70,80,90,100})、α (DAG 的形状参数,取值为{0.5,1.0,2.0}、β (节点的出度,取值为{1,2,3,4,5})、γ (节点的入度,取值为{1,2,3,4,5})、CCR (通信计算时间比,取值为{0.1,0.5,1.0,5.0,10.0})产生3000组DAG类型,每组类型中随机产生20个具有不同节点权值的DAG,共产生60000个随机任务。
将随机任务以参数形式输入算法中,通过Socket将算法运行结果传递到仿真实验环境中。仿真实验使用Simics模拟多核异构处理器结构,通过C语言实现算法和Socket通信模块,实现虚拟多核环境和算法之间的有效信息交互,通过对任务的完成时间长短判断算法优劣(依次比较两种算法,完成时间差在线性级之内的标记为Equal,其它情况下,算法1较算法2完成时间短时标记为Better,完成时间长时标记为Worse),实验方案结构如4所示。
将WPTS算法与CPFD算法、HCPFD算法、HDEFT算法进行比较,统计WPTS算法较其它3种算法取得Bet- ter、Equal和Worse调度性能的次数和所占的比例,比较结果见表1.
4 验证方案结构
从表1可以看出在随机实验环境下,在将3种算法综合的情况下,WPTS 算法能取得最优调度的比例为71.53%,优于其它3种算法。
实验2:(1)令α= {0.5,1.0,2.0},改变随机任务的其它参数,计算各算法的平均SLR和Efficiency,计算公式如式(9)、式(10),实验结果如5、6所示。
5 形状参数α变化时算法的平均SLR
从对比可以看出,任务形状参数α变化会影响任务调度的结果:α值为0.5时,DAG高度较小,任务之间并行性较高;α值为1.5时,DAG高度较大,任务之间并行性较低。4种算法在任务并行性较高时都能取得很好的性能,其中WPTS算法的性能最优,原因是任务并行性较高时,处理器上的空闲时间较少,处理器的利用率较高,而WPTS算法能及时处理任务调度中存在的冗余任务,提高处理器的执行效率。
6 形状参数α变化时算法的Efficiency
(2)改变处理器数量,使其分别为4、8、12、16、20,其它参数不变,各算法的性能如7、8所示。
从对比可以看出,与其它任务调度算法相比,WPTS算法更具有性能优势,其原因在于新算法充分利用处理器上的空闲时间调度任务,并及时对产生的冗余任务进行处理,提前后继任务的最早开始时间,因此取得了更好的调度性能。
(3)CCR取值分别为0.1,0.5,1.0,5.0,10.0,其它参数值不变,各算法的性能测试结果如9、10所示。
从对比可以看出,CCR不同时,因为WPTS算法对冗余任务有较好的处理,因此较其它3种算法取得了更好的性能。
根据这两组测试结果,可以看出WPTS算法要优于CPFD、HCPFD和HDEFT 算法,随着任务规模的增大,WPTS算法的优势越明显。
结束语
通过深入分析目前异构多核处理器任务调度算法存在的不足,提出了WPTS 算法。WPTS 算法使用加权值weight标记任务的优先级,新优先级计算方法克服了优先级选取单一带来的问题,能更准确地反映任务在DAG中的位置和属性;在任务到处理器的映射阶段及时消除任务调度中产生的冗余任务,提前后续任务的最早开始执行时间。实验结果表明,新算法能取得最优调度的比例为71.53%,且在DAG形状、处理器数量和CCR不同时较已有算法均能取得更好的性能