基于异构多核处理器的静态任务调度研究（二）

接上文：

基于异构多核处理器的静态任务调度研究(一)

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不同时较已有算法均能取得更好的性能