一种改进的异构多处理器实时任务调度算法研究

《一种改进的异构多处理器实时任务调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一种改进的异构多处理器实时任务调度算法研究节点都执行完毕之后才能开始执行；对DAG任务的调度就是使整个DAG图的调度长度最短，使DAG图在尽可能短的时间内执行完毕。本论文研究一种改进的异构多处理器实时任务调度算法，任务采用异构多处理器DAG模型来表示。多处理器的异构性导致同一任务在不同的处理器上的执行时间的互异性，具体体现到DAG图上而言，就是各个节点都有一个与处理器个数相关的执行时间数组。同样，要使得这种DAG任务的调度长度最短，应考虑两个重要指标：最大化任务的并行度以及最小化任务间通信，也就是MAX--MIN最优化问

2、题，但这又是相互制约相互限制的两个方面。任务的并行执行，就意味着任务将放置至不同的处理器上执行，任务在不同的处理器上执行，就必然会引起任务间的通信延迟。因此，任务调度问题一直是一个NP问题。近年来，大量的学者尝试并采用了大量的算法对这个问题进行研究f1。161。如：遗传算法，整数规划，局部搜索，分支定界方法等[31，但大多数算法都存在时间复杂度过高的问题。1．2多处理器任务调度的国内外研究现状根据研究的侧重点不同，目前对多处理器任务调度的研究从不同的角度进行划分，具体的分类如下：1、静态调度与动态调度根据调度的方式可分为

3、静态算法和动态算法。静态算法【9‘12】主要是指任务图在调度前已知任务的所有特征，包括任务的到达时间，任务的执行时间，结束时间等等。利用已知的信息，采用某种算法算出每一个任务的调度优先级，再根据优先级对任务进行调度。动态调度【l叫是指在调度前对任务的特征还未进行详细的计算，先将任务初始化调度到不同的处理器，再根据优化算法调整其任务的分布。如图1．1所示，若采用静态调度则是先计算结点的属性，根据一定的优先级进行分簇。若采用level分簇的思想【9d2】，则首先计算各节点的层次Vl为第一层，V2，V3，V4，V5为第二层；V

4、6，V7，V8为第三层，V9为第四层；再根据算法中节点的分簇策略，将节点分簇并放置至各处理器上执行。若采用动态调度的思想【8】，则首先将初始节点Vl首先放于某个处理器上，然后再根据Vl的放置情况分别计算其后继节点的最早开始时间和最晚结束时间等相关属性，再按一定的策略将其后继节点放置到不同的处理器上执行，依此类推直到所有的任务都调度到处理器上。2、单处理器与多处理器根据处理器的个数可分为：单处理器调度、多处理器调度。顾名思义前者只使用一个处理器，后者使用多个处理器进行调度。前者DAG模型往往省略了通信时间，或者通信时间用定

5、值来表示；目前大部分研究主要针对多处理器系统，并且大多数任务模型都考虑通信延迟的任务图，而根据通信延迟的特点和处理器结构类型的特点可以将DAG图分成不同的类型，详细的分析见2．1节。2硕士学位论文图1．1DAG示例图3、可抢占式与非可抢占式根据任务是否允许抢占，可以将任务分成可抢占式和非可抢占式。目前研究的绝大多数任务都是不允许抢占式的，即非可抢占式。如图1．2所示：图中T1表示任务1，T2表示任务2，T1．1表示Tl中的子任务，若砣在时间单位5到达，且他的优先级比Tl高。(a)表示不可抢占的任务，虽然T2的优先级比T1

6、高，但T2在到达时T1．1已经在执行，则T2．1不可以在到达时立刻执行，因为此时处理器正在处理T1，T2只能等T1．1执行完毕后才能执行；(b)表示任务可以抢占，T2到达时，虽然处理器正在处理T1．1，但由于T2．1的优先级别高，且任务是可抢占式的，所以T2．1将处理器抢占并立即执行。本文研究的实时任务都是非可抢占式的任务。厂—1百]厂_两]—1订．(a)圃叵[叵工正◆(b)图1．2可抢占式任务调度和不可抢占式任务调度4、同构多处理器与异构多处理器根据处理器结构，可以分为同构处理器调度【1捌和异构处理器调度‘8·161。

7、异构处理器一调度可以根据处理器是否满足调度需要分为处理器足够的情况和处理器个数不够的情’。况。前者尽可能只考虑任务的并行度，而后者充分考虑任务在不同处理器下执行效率。目前已有很多的算法是关于异构多处理器的，文献[131提出的HEFT(HeterogeneousEarliestFinish-Time)与CPOP(Critical．Path-onaProcessor)是异构多处理器任务调度十分经典的调度算法，HEFT与CPOP算法经过证实其调度结果优于之前所提出的很多异3一种改进的异构多处理器实时任务调度算法研究构多处理器实

8、时任务调度算法，但HEFT与CPOP在调度完之后没有对任务进行优化处理。文献[14】中提出针对异构处理器的一种启发式的调度算法HNPD(HeterogeneousN—ProcessorDuplication)，HNPD算法利用复制策略弥补HEFT任务调度中存在的未优化各节点的执行问题，通过复制策略，HNPD算法有效地