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

式中：AST (vi,pn)-任务vi在处理器pn上的实际开始时间;AFT (vi,pk)-任务vi在处理器pk上的实际完成时间;vpar-最后一个与任务vi通信的任务;Avail(pn)-处理器pn执行完分配到其上的所有任务的时间。

通过对DAG图的深入研究发现，某层冗余任务的处理在其下一层任务到处理器的映射之后执行效果最好，如对level=1层任务调度完成后对level=0层任务进行冗余判断，将任务分配到处理器和冗余任务处理两个过程交替执行，直到冗余任务列表为空。

(2)任务到处理器映射流程任务到处理器映射流程如图3所示。

(3)任务到处理器映射阶段具体步骤

步骤1 初始化level=0,判断任务调度列表TL在level层的任务是否调度完毕，如果是则跳转到步骤5;否则向下执行步骤2.

步骤2 取任务调度列表TL的首任务记为vi,遍历所有处理器，如果处理器存在空闲时间段且满足vi插入条件，则将vi分配到空闲时间段，并计算其最小最早完成时间，记为EFT1;否则向下执行步骤3.

步骤3 计算将vi分配到所有处理器上的最小最早完成时间，记为EFT2.如果处理器上存在空闲时间段且能使用任务复制技术，则计算在处理器上复制vi的前驱获得最小最早完成时间，记为EFT3,继续执行步骤4.

步骤4 选择EFT1、EFT2、EFT3的最小值，并将任务分配到具有最早完成时间的处理器上，从调度列表中删除vi,建立冗余任务列表RTL,将被复制的任务加入到RTL中，格式为vi,0~vi,k,vi为被复制的任务节点，k为任务所在处理器的编号。

步骤5 判断RTL中是否有(level-1)层任务，如果是则跳转到步骤6;否则跳转到步骤8.

步骤6 取RTL首任务节点，记为vi,k,判断删除任务vi,k后vi,k直接后继节点的最早开始时间是否延迟，如果延迟，判定任务vi,k非冗余任务，从RTL中删除vi,k,跳转到步骤5;否则判定任务vi,k为冗余节点，从RTL中删除vi,k,从任务映射图中删除vi,k,跳转到步骤7继续执行。

步骤7 判断任务vi,k的后继任务能否提前执行，如果能则将其前移执行，修改任务映射图，跳转到步骤5;否则，直接跳转到步骤5.

步骤8 如果level

2 WPTS算法时间复杂度分析

任务合并过程是对DAG图进行一次深度优先遍历，因此其时间复杂度为O (v+e)，v为DAG图中任务的数量，e为有向边的数目。任务分层是从上到下计算每个节点的level值，时间复杂度为O (n+e)，n为任务合并后DAG图中任务的数量。任务权值计算对DAG图进行广度优先遍图3 任务到处理器映射阶段流程历，计算任务节点的weight值和寻找关键路径节点，时间复杂度为O (n2)，因此任务优先级计算阶段的时间复杂度为O (v+e)+O (n+e)+O (n2);任务到处理器的映射阶段考虑了处理器空闲时间段插入和任务复制技术，因此每层任务被映射到处理器上的时间复杂度为O (kp)，k为每层的任务数量，p为处理器的数量，冗余任务处理的时间复杂度为O (k2)，将所有任务映射到处理器上并完成调度结果优化所需的时间复杂度为O (kpm+k2 m)，m 为任务DAG图的层数，其在最坏情况下等于任务数量v.

图3　任务到处理器映射阶段流程

综上所述，WPTS算法的时间复杂度为O (v+e)+O(n+e)+O (n2)+O (kpm+k2 m)，即O (v3)，算法没有提高时间复杂度，且能有效处理使用任务复制技术带来的冗余任务，减少任务的调度长度，避免处理器资源的浪费。