针对多处理器系统的迭代式静态任务列表调度算法

技术领域

本发明涉及任务调度领域，具体地说是一种基于多处理器系统上的迭代式静态任务列表 调度算法。

背景技术

现有技术中，多处理器系统能够更大程度上满足应用程序对多任务并发执行的需求，而 如何更有效地实现多处理器系统上的任务调度仍然有待进一步探究。目前，主流的静态任务 调度算法多采用基于任务图模型的列表调度技术。在任务图模型中，用有向无环图 G＝(V,E,W,C)表示应用程序，一个点表示一个任务，点与点之间的有向边E_a,b表示前驱任务 a和后继任务b之间的前驱后继约束关系，点权重W_a表示执行任务a所需的时间，有向边E_a,b的权重C_a,b表示任务a和b进行通信所需的时间。关于任务图模型的详细介绍见于参考文献 《DynamicCriticalPathScheduling:AnEffectiveTechniqueforAllocatingTaskGraphsto Multiprocessors》的研究背景说明部分。由于任务调度问题一般以任务图为模型，因此，任务 调度亦可称为任务图调度。

传统的静态任务静态列表调度算法的实现过程较为简单：根据任务优先级列表，依次把 各个任务被调度在使其获得最早开始时间的处理单元上。任务优先级列表通过特定算法得到， 在优先级列表中，任务所在的位置越靠前，这个任务被调度的优先级越高。关于所述静态任 务静态列表调度算法的详细说明参见文献《TaskSchedulingforParallelSystems》对Algorithm 9和Algorithm10的阐述。静态列表调度算法只考虑任务优先级列表这一种任务优先级序列， 然而，任务优先级列表未必就是最优任务优先级序列。在这里，任务优先级序列表示任务被 调度的先后次序。因此，只考虑一种任务优先级序列的静态列表调度算法容易得到较差调度 结果，即较大的调度长度，从而导致应用程序执行效率较低。所述的调度长度表示执行完成 所有任务所需的时间。

发明内容

本发明是为避免上述现有技术的不足，提出了一种针对多处理器系统的迭代式静态任务 列表调度算法，以期在传统的静态列表调度算法的基础上，进一步减小调度长度，从而提高 应用程序执行效率。

本发明为解决技术问题采用如下技术方案：

本发明一种针对多处理器系统的迭代式静态任务列表调度算法，所述多处理器系统在P 个处理器上执行N个任务的特点是按照如下步骤进行：

步骤1、定义外循环次数为s；设定外循环次数的阈值为S；定义内循环次数为k；设定 内循环次数的阈值为K；

步骤2、初始化所述外循环次数s＝1；

步骤3、在第s次外循环下随机设置所述任务图的任务优先级序列，从而获得所述N个任 务在第s次外循环下的最优任务优先级序列，记为表示所述 第s次外循环下的最优任务优先级序列中第m个被调度任务；1≤m≤N；

步骤4、以所述第s次外循环下的最优任务优先级序列为任务优先级列表，利用静态 任务静态列表调度算法对任务图进行调度，获得所述第s次外循环下的最优调度长度，记 为

步骤5、初始化所述内循环次数k＝1；

步骤6、从随机数产生器获得两个随机数i和j，并对换所述第s次外循环下的最优任务 优先级序列中第i个被调度任务和第j个被调度任务从而获得第s次外循环下的 第k个任务优先级序列，记为表示所述第s外次循 环下的第k个任务优先级序列T^(s)(k)中第l个被调度任务；1≤i≤N，1≤j≤N，1≤l≤N；

步骤7、以所述第s次外循环下的第k个任务优先级序列T^(s)(k)为任务优先级列表，利用静 态任务静态列表调度算法对任务图进行调度，得到第s次外循环下的第k个调度长度，记为 SL^(s)(k)；

步骤8、对所述第s次外循环下的第k个调度长度SL^(s)(k)和第s次外循环下的最优调度长 度进行比较；若则所述第s次外循环下的最优调度长度和最优任务 优先级序列分别赋值为SL^(s)(k)和T^(s)(k)；若所述第s次外循环下的最优调 度长度和最优任务优先级序列都保持不变；

步骤9、将k+1赋值给k，判断k≤K是否成立；若成立，表示对所述第s次外循环下的 最优调度长度尚未完成迭代，返回步骤6执行；否则，执行步骤10；

步骤10、将s+1赋值给s，判断s≤S是否成立；若成立则返回步骤3执行；否则，表示 S个最优调度长度都已经完成迭代，并执行步骤11；

步骤11、从所述的S个最优调度长度中选出最小值作为所 述迭代式静态任务列表调度算法的调度结果，记为SL_best，即 从而完成所述迭代式静态任务列表调度算法，并 以SL_best衡量所述迭代式静态任务列表调度算法的性能高低。

与现有技术相比，本发明的有益效果体现在：

1、本发明在传统静态任务静态列表调度算法的基础上进一步考虑多种任务优先级序列， 从而得到更小的调度长度，有效提高应用程序执行效率。

2、本发明采用对换中两个随机任务的优先级来生成T^(s)(k)，这种任务优先级生成策 略是最容易实现的。

3、本发明在第s次外循环第k次内循环中以T^(s)(k)为任务优先级列表，采用静态列表调度 算法对任务图进行调度，通过比较SL^(s)(k)和来决定是否更新和这一方法使得 在迭代过程中单调递减，从而保证迭代式静态任务列表调度算法得到的调度长度必不大 于静态任务静态列表调度算法。

4、本发明借鉴粒子群算法的基本思想，以S为粒子群规模，为粒子所处状态， S个粒子各自经过K次迭代完成状态更新，再从粒子群的最终状态中选取最优解，这样就能 通过采用多种任务优先级序列避免单一任务优先级序列容易陷入局部最优解的缺陷；

5、本发明可以根据算法实际运行时间的限制来调整S和K的大小；因而具有较高灵活性。

6、本发明的算法实现相对于采用任务聚簇、任务复制和动态优先级列表技术的静态任务 调度算法更为简单。

附图说明

图1是本发明实例中所用的任务图；

图2是本发明的算法执行流程图。

具体实施方式

本实施例中，在一个具有四个处理器的多处理器系统上，迭代式静态任务列表调度算法 的执行过程大致如下：

1、设定当前最优任务优先级序列的初始值，对应的静态列表调度长度作为当前最优调度 长度的初始值；

2从当前最优任务优先级序列生成新的任务优先级序列，如果对应的静态列表调度长度 小于当前最优调度长度，则更新当前最优调度长度和当前最优任务优先级序列；

3重复执行步骤2，直至执行次数达到指定上限；

4对于每个最优任务优先级序列执行步骤1到3；

5从所有最优调度长度中选出最小值，作为最终的调度结果。

具体的说，如图2所示，对图1所示的任务图进行调度，是按如下步骤进行：

步骤1、定义外循环次数为s；设定外循环阈值为S；对照粒子群算法，可以把一种任务 优先级序列及其对应的调度长度看做粒子群中一个粒子的状态，那么S即为这个粒子群的规 模；经过S次外循环之后，粒子群中所有粒子的状态都更新完毕，从所有粒子的最终状态中 选出最小调度长度，这个调度长度为最终的任务调度结果；本实施例中，S取值为4；

定义内循环次数为k；设定内循环阈值为K；K表示每个粒子状态迭代次数的上限；本 实施例中，K取值为256；一般来说，S和K越大，所述迭代式静态任务调度算法的调度效 果越好，但是出于算法运行时间的限制，S和K的取值不能太大；

步骤2、初始化所述的外循环次数s＝1；

步骤3、在第s次外循环下随机设置所述任务图的任务优先级序列，从而获得所述任务图 中N个任务的第s次外循环下的最优任务优先级序列，记为表示所述第s次循环下的最优任务优先级序列中第m个被调度任务；1≤m≤N；

对于图1所示的任务图，一个节点对应于一个任务，如节点V₀对应于任务0；每个节点 的权值即为任务执行完成所需的时间，如所述任务0执行完成所需的时间是99；一条有向边 表示其上两个任务之间的前驱后继约束关系，如有向边E_0,8上的任务0是任务8的前驱，任 务8则是任务0的后继，即任务8的调度优先级不能高于任务0；有向边上的权值与其上两 个任务之间所需的通信时间有关，举例来说，若任务0和8分别被调度在两个不同处理单元 上，则从任务0到任务8的通信所需的时间是55，若任务0和8都被调度在相同处理单元上， 则从任务0到任务8的通信所需的时间是0；

这里的任务优先级序列表示任务图中各个任务被调度的先后顺序，一个任务优先级序列 不符合前驱后继约束条件是指任务图中至少存在一条有向边使得其上的后继比前驱获得更高 优先级；举例来说，对于图1所示的任务图，任务优先级序列 {8,1,2,3,4,5,6,7,0,9,10,11,12,13,14}不符合前驱后继约束条件，因为E_0,8上的后继任务8的 优先级高于前驱任务0；

这里得到的只是第s个最优任务优先级序列的初始值，这个值在后续步骤中不断地 单调递减；对于不满足前驱后继约束的任务优先级序列，由于后继并不能优先于前驱被调度， 因而可以认为相应的静态列表调度长度是正无穷大；所以，不满足前驱后继约束的任务优先 级序列并不适合作为第s个最优任务优先级序列的初始值；

本实施例中，为了得到四种符合前驱后继约束的任务优先级序列，四次外循环分别采用 以下四种任务优先级序列计算方案：TL-Scheme、BL-Scheme、BL_TL-Scheme和 Random-Scheme；四者得到任务优先级序列的方式有所不同：TL-Scheme按照TL权值升序排 列各个任务，BL-Scheme按照BL权值降序排列各个任务，BL_TL-Scheme按照主位关键字BL 权值降序及次位关键字TL权值升序排列各个任务，Random-Scheme随机生成一个符合前驱约 束的任务优先级序列。任务TL和BL权值的计算方法如下式(1)和(2)所示：

本实施例中，根据所述的四种任务优先级序列的计算方法，四次外循环各自对应的最优 任务优先级序列的初始值如表1所示；对照图1所示的任务图，这四种任务优先级序列的确 符合前驱后继约束条件。

表1：四种静态任务优先级计算方法各自对应的任务优先级序列

本发明可以采用论文《并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方 法》和《Listscheduling:extensionforcontentionawarenessandevaluationofnodeprioritiesfor heterogeneousclusterarchitectures》中的任务优先级序列计算方法，以保证最优任务优先级序 列初始值符合前驱后继约束条件；

步骤4、以所述的第s次循环下的最优任务优先级序列为任务优先级列表，利用静态 列表调度算法对任务图进行调度，获得第s次循环下的最优调度长度，记为

以某种任务优先级序列为任务优先级列表，利用静态任务静态列表调度算法对任务图进 行调度而得的调度长度也可被称为这种任务优先级序列对应的静态列表调度长度；在这里， 对应的静态列表调度长度只是第s个最优调度长度的初始值，在迭代过程中将 不断地被更新；在本实施例中，和对应的静态列表调度长度和分别为824、731、731和829；

步骤5、初始化所述的内循环次数k＝1；k表示迭代次数；

步骤6、从随机数产生器获得两个随机数i和j，再对换所述第s次循环下的任务优先级 序列中第i个被调度任务和第j个被调度任务从而获得第s次循环下的第k个试探 性任务优先级序列；记为表示所述第s次循环下 的第k个任务优先级序列T^(s)(k)中第l个被调度任务；1≤i≤N，1≤j≤N，1≤l≤N；

在本实施例中，当s＝1且k＝1时，从随机数对产生器得到两个随机数：1和4，对换 中的任务1和4的优先级，得到第一次外循环下 的第一个任务优先级序列T⁽¹⁾⁽¹⁾＝{0,4,2,3,1,5,6,7,8,10,9,11,13,12,14}；

步骤7、以所述第s次循环下的第k个任务优先级序列T^(s)(k)为任务优先级列表，利用静态 列表调度算法对任务图进行调度，获得第s次循环下的第k个调度长度，记为SL^(s)(k)；

在本实施例中，T⁽¹⁾⁽¹⁾满足前驱约束条件，以T⁽¹⁾⁽¹⁾为任务优先级列表，根据静态列表调度 算法得到相对应的调度长度SL⁽¹⁾⁽¹⁾＝819，也可以说，T⁽¹⁾⁽¹⁾对应的静态列表调度长度 SL⁽¹⁾⁽¹⁾＝819；在步骤3中已经说明，如果T^(s)(k)不满足前驱约束条件，则SL^(s)(k)＝+∞；

步骤8、对所述第s次循环下的第k个调度长度SL^(s)(k)和第s次循环下的最优调度长度 进行比较；若所述第s次循环下的最优调度长度和最优任务优先级 序列分别赋值为SL^(s)(k)和T^(s)(k)；若所述第s次循环下的最优调度长度和最优任务优先级序列都保持不变；

这一步骤使得在迭代的过程中单调递减，进而保证迭代式静态任务列表调度算法得 到的调度长度必不大于静态任务静态列表调度算法；在本实施例中， ${\mathrm{SL}}^{\left(1\right)\left(1\right)}=819<{\mathrm{SL}}_{best}^{\left(1\right)}=824,$因而作出更新：${\mathrm{SL}}_{best}^{\left(1\right)}={\mathrm{SL}}^{\left(1\right)\left(1\right)}$且$T_{best}^{\left(1\right)}=T^{\left(1\right)\left(1\right)};$

步骤9、将k+1赋值给k，判断k≤K是否成立。若成立，表示对所述第s次外循环下的 最优调度长度的迭代还未完成，返回步骤6执行；否则，执行步骤10；

步骤10、将s+1赋值给s，判断s≤S是否成立；若成立，则返回步骤3执行；否则表示 S个最优调度长度都已经迭代完成，继续执行步骤11；

步骤11、从所述S个最优调度长度中选出最小值作为所述 迭代式列表调度算法的最优调度长度，记为SL_best；即 从而完成所述迭代式列表调度算法；并以所述迭 代式列表调度算法的最优调度长度SL_best衡量所述迭代式列表调度算法的性能优劣；调度长度 即为所有任务执行完成所需的时间消耗，因而调度长度的大小是衡量任务调度算法性能的最 重要的一个性能指标；

在本实施例中，所述迭代式静态任务列表调度算法得到的四个最优调度长度和分别是690、690、595和622，进而得到迭代式静态任务列表调度算法调度结果 ${\mathrm{SL}}_{best}=min\{{\mathrm{SL}}_{best}^{\left(1\right)},{\mathrm{SL}}_{best}^{\left(2\right)},{\mathrm{SL}}_{best}^{\left(3\right)},{\mathrm{SL}}_{best}^{\left(4\right)}\}=595.$