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

来源:本站
导读:目前正在解读《基于异构多核处理器的静态任务调度研究(二)》的相关信息,《基于异构多核处理器的静态任务调度研究(二)》是由用户自行发布的知识型内容!下面请观看由(电工技术网 - www.9ddd.net)用户发布《基于异构多核处理器的静态任务调度研究(二)》的详细说明。
简介:针对现存任务调度算法优先级选取过于单一、冗余任务处理较晚的问题,提出一种基于加权优先级的任务调度算法-WPTS算法。该算法综合考虑任务3个属性的加权值以决定任务被处理的先后次序,从而克服了任务选取时的单一性问题。在将任务分配到处理器的过程中,保证任务优先调度到完成时间最早的处理器上。同时,引入冗余任务处理过程,及时消除冗余任务,达到对处理器空闲时间段进行有效回收、减少处理器调度长度的效果。

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

提醒:《基于异构多核处理器的静态任务调度研究(二)》最后刷新时间 2024-03-14 01:21:13,本站为公益型个人网站,仅供个人学习和记录信息,不进行任何商业性质的盈利。如果内容、图片资源失效或内容涉及侵权,请反馈至,我们会及时处理。本站只保证内容的可读性,无法保证真实性,《基于异构多核处理器的静态任务调度研究(二)》该内容的真实性请自行鉴别。