基于动态关键任务的多处理器任务分配算法
第３０卷第３期计算
机
学报
ｖ０１．３０Ｎｏ．３
２００７年３月
ＣＨＩＮＥＳＥＪＯＵＲＮＡＬ０ＦＣＯＭＰＵＴＥＲＳ
Ｍａｒ．２００７
基于动态关键任务的多处理器任务分配算法
兰
舟孙世新
（电子科技大学计算机科学与工程学院成都６１００５４）
摘要多处理器调度问题是影响系统性能的关键问题，基于任务复制的调度算法是解决多处理器调度问题较为
有效的方法．文中分析了几个典型的基于任务复制算法，提出了基于动态关键任务（ＤＣＴ）的多处理器任务分配算法．ＤＣＴ算法以克服贪心算法不足为要点，调度过程中动态计算任务时间参数，准确确定处理器的关键任务，以关键任务为核心优化调度，逐步改善调度结果，最终取得最优的调度结果．分析和实验证明，ＤＣＴ算法优于现有其它同类算法．
关键词调度长度；任务复制；多处理器系统；任务分配；并行计算；同构系统中图法分类号ＴＰ３１１
Ａｎ
Ａｌｇｏｒｉｔｈｍ
ｏｆＡ¨ｏｃａｔｉｎｇＴａｓｋｓｔｏ
Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ
Ｂａｓｅｄ
ｏｎ
ＤｙｎａｍｉｃＣｒｉｔｉｃａｌＴａｓｋ
ＬＡＮＺｈｏｕ
ＳＵＮＳｈｉ—Ｘｉｎ
（Ｃｏ比ｇＰｏ，ｃｏｍ户“￡ＰｒＳｃ｛Ｐ九ｃＰ口咒ｄ眈ｇｉ舛ｅｅｒｉ雄ｇ，协ｆ御州￡ｙｏ，ＥＺ８甜ｒｏｎ把ＳｃｉＰ竹ｃ曰口ｎｄｎｃ＾加ＺｏｇｙＤ，劬ｉ撇，Ｃ＾删ｇｄＭ６１００５４）
Ａｂｓｔ腿ｃｔ
Ｏｎｅｏｆｍａｉｎｏｂｓｔａｃｌｅｓｉｎａｃｈｉｅｖｉｎｇｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｉｓｔｈｅｓｃｈｅｄｕｌｉｎｇｆｏｒｍｕｌｔｉｐｒｏｃｅｓ—
ｓｏｒｓ．
Ｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎ
ｔａｓｋｄｌ：ｌｐｌｉｃａｔｉｏｎｉｓ
ａ
ｂｅｔｔｅｒｗａｙ
ｔｏ
ｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍ．
Ｔｈｅ
ａｕｔｈｏｒｓｄｉｓｃｕｓｓｓｅｖｅｒａｌｒｅｃｅｎｔｌｙｒｅｐｏｒｔｅｄｄｕｐｌｉｃａｔｉｏｎ—ｂａｓｅｄｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓａｎｄｐｒｏｐｏｓｅ
ａ
ｎｏｖｅｌａＩｇｏｒｉｔｈｍ．
Ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍ，
ｗｈｉｃｈｉｓｃａｌＩｅｄｔｈｅ
ａｌｇｏｒｉｔｈｍ
ｏｆａｎｏｃａｔｉｎｇｔａｓｋｓｔｏ
ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｂａｓｅｄ
ｏｎ
ＤｙｎａｍｉｃＣｒｉｔｉｃａｌＴａｓｋ（ＤＣＴ），ｉｓｄｉｆｆｅｒｅｎｔｆｒｏｍｔｈｅｐｒｅｖｉｏｕｓｌｙｐｒｏｐｏｓｅｄ
ａｌｇｏｒｉｔｈｍｓｉｎ
ａ
ｎｕｍｂｅｒｏｆｗａｙｓ．Ｂｅｓｉｄｅｓ
ａ
ｄｉｒｅｃｔｅｄａｃｙｃｌｉｃｇｒａｐｈ（【）ＡＧ），ｔｈｅｇａｎｔｔｇｒａｐｈａｌｓｏｉｓ
ｉｎｔｒｏｄｕｃｅｄｉｎｔｏｔｈｅｓｃｈｅｄｕＩｉｎｇｐｒｏｃｅｓｓ．Ｂａｓｅｄ
ｏｎ
ｔｈｅｇａｎｔｔｇｒａｐｈ七）ＣＴａＩｇｏｒｉｔｈｍ
ａｓｅｔ
ｏｆｔｉｍｅｐａ—
ｒａｍｅｔｅｒｓｉｓ
ｐｕｔ
ｆｏｒｗａｒｄｔｏａｃｃｕｒａｔｅｌｙｄｅｓｃｒｉｂｅｔｈｅ
ｔａｓｋｐｏｓｉｔｉｏｎｓ
ａｎｄｓｔａｔｅｓ．
Ａｆｔｅｒｄｙｎａｍｉｃａｌｌｙ
ｃｏｍｐｕｔｉｎｇｔｈｅｔａｓｋｔｉｍｅｐａｒａｍｅｔｅｒｓ，ＤＣＴａｌｇｏｒｉｔｈｍｄｅｔｅｒｍｉｎｅｓｔｈｅｃｒｉｔｉｃａｌｔａｓｋｓｏｆ
ａ
ｐｒｏｃｅｓｓｏｒ
ａｎｄｔｈｅｎｏｐｔｉｍｉｚｅｓｔｈｉｓｐｒｏｃｅｓｓｏｒｓｃｈｅｄｕｌｅｌｅｎｇｔｈｔｈｒｏｕｇｈｄｕｐＩｉｃａｔｉｎｇｔｈｅｃｒｉｔｉｃａｌｆａｔｈｅｒｔａｓｋｓｏｆｔｈｅｃｒｉｔｉｃａｌｔａｓｋｓ
ｔｏ
ｔｈｉｓｐｒｏｃｅｓｓｏｒ．
Ｏｎｃｅｔｈｅｓｃｈｅｄｕｌｅｌｅｎｇｔｈｉｓ
ｓｈｏｒｔｅｒ，亡）ＣＴａｌｇｏｒｉｔｈｍｄｅｔｅｒ—ｍｉｎｅｓｔｈｅｃｒｉｔｉｃａｌｔａｓｋｓａｇａｉｎｆｏｒｔｈｅｎｅｘｔ
ｓｃｈｅｄｕｌｉｎｇｓｕｃｈｔｈａｔ
ＤＣＴａｌｇｏｒｉｔｈｍ
ｃａｎ
ｔａｃｋｌｅｔｈｅ
ｄｒａｗｂａｃｋｓｏｆｔｈｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍｓ（ｅ．ｇ．０ＳＡ，ＰＰＡａｎｄＣＰＦＤａｌｇｏｒｉｔｈｍ）．ＤＣＴａｌｇｏｒｉｔｈｍａｌｓｏ
ｅｍｐｌｏｙｓｓｅｖｅｒａｌｓｔｒａｔｅｇｉｅｓ
ｔｏ
ｒｅｄｕｃｅｔｈｅｎｕｍｂｅｒｏｆｐｒｏｃｅｓｓｏｒｓ．
Ｔｈｅａｎａｌｙｔｉｃａｌａｎｄｅｘｐｅｒｉｍｅｎｔａｌ
ｒｅｓｕｌｔｓｓｈｏｗＤＣＴａｌｇｏｒｉｔｈｍｈａｓａｄｖａｎｔａｇｅｓ
ｏｖｅｒ
ｔｈｅｐｒｅＶｉｏｕｓｌｙｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓｉｎｔｅｒｍｓｏｆ
ｔｈｅｓｃｈｅｄｕｌｅｌｅｎｇｔｈａｎｄｔｈｅｎｕｍｂｅｒｏｆｐｒｏｃｅｓｓｏｒｓ．
Ｋｅｙｗｏｒｄｓ
ｓｃｈｅｄｎｌｅｌｅｎｇｔｈ；ｔａｓｋｄｕｐｌｉｃａｔｉｏｎ；ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｙｓｔｅｍ；ｔａｓｋａｌｌｏｃａｔｉｏｎ；
ｐａｒａｌｌｅｌ
ｃｏｍｐｕｔｉｎｇ；ｈｏｍｏｇｅｎｅｏｕｓｓｙｓｔｅｍ
收稿日期：２００５一０４—３０；修改稿收到日期：２００６一０３—２０．兰
舟，男。１９６９年生，博士研究生，主要研究方向为网络计算技术与高性能并行计
算．ｐｍａｉｌ：ｉｚＩａｎｚｈｏｕ＠１６３．ｃｏｍ．孙世新，男，１９４０年生，教授，博士生导师，主要研究领域为网络计算技术、并行／分布式计算及其应用、信息压缩技术、数值计算与组合算法等．
万方数据
３期
兰
舟等：基于动态关键任务的多处理器任务分配算法
４５５
引言
一个任务系统可以看成由多个具有偏序关系、可以并行或串行执行的子任务组成．多处理器调度的目标就是按照某种策略将子任务合理分配到各个处理器上并行有序地执行，使任务系统执行时间最短．调度算法可分为静态调度和动态调度两种．静态调度和动态调度相比，具有实现简单、开销小等特点．基本的静态调度算法分为基于随机搜索和基于启发法两类［１］．基于随机搜索的算法包括基因算法阻引、退火算法Ⅲ、局部搜索技术嘲等．基于启发法的算法包括表调度法［１“］、聚族法［７＿８］、任务复制法［９ｑ２］等．任务复制法的基本思想是，在多个接受消息的处理器中执行发送消息任务的副本，将任务在处理器之间的通信改变为处理器内部通信．其特点是牺牲处理器本地处理时间（需要复制任务做冗余计算），而换取减少处理器之间的通信时间．当采用合理的复制策略时，任务复制算法能获得比其他算法较好的调度性能［８’１
３｜．
典型的任务复制算法有ＴＤＳ［９｜，ＯＳＡ［１０］，ＰＰＡ［１１］，ＣＰＦＤ［”３等．ＴＤＳ算法的主要思想是将友好父任务和子任务分配到同一处理器，使子任务具有较小的最早开始时间，以此缩短调度长度．在满足一定最优条件下，ＴＤｓ算法能获得最优调度结果．ＯＳＡ算法改进了ＴＤＳ算法，放宽了ＴＤＳ算法的最优条件，将多个父任务和子任务分配到同一处理器，最大可能地使子任务获得最小的最早开始时间，从而缩短调度长度．ＰＰＡ算法改进了ＯＳＡ算法，采用和ＯＳＡ算法一样的调度策略；同时考虑了处理器数目优化，采用父任务合并策略，在不影响调度长度的前提下减少处理器数量．ＰＰＡ算法的调度长度优于ＴＤＳ算法，和ＯＳＡ算法相当；所用处理器数目优于ＴＤＳ和ＯＳＡ算法．ＣＰＦＤ算法采用试探性策略，理器上，并计算相应的最早开始时间，最终将该任务分配到可以获得最小最早开始时间的处理器上．ＣＰＦＤ算法在调度当前任务时，递归地寻找其ＶＩＰ
（ＶｅｒｙＩｍｐｏｒｔａｎｔ
Ｐａｒｅｎｔ）蚴任务，将ＶＩＰ任务复制
到当前处理器上，使当前任务能获得最小的最早开ＴＤＳ算法不允许多个父任务和子任务分配到同一处理器，使子任务难以获得较好的最早开始时
万方数据
间．０ＳＡ，ＰＰＡ，ＣＰＦＤ算法将尽可能多的父任务和
子任务分配到同一处理器，尽管当前任务能获得最小的最早开始时间，却限制了其子孙或祖先任务的
调度，制约了调度长度优化．另外，ＴＤＳ及ＣＰＦＤ算法未考虑处理器数目的优化，较多地占用了资源．０ＳＡ算法在一定限制条件下考虑了处理器数目优化．ＰＰＡ算法采用父任务合并策略优化处理器数目，但只考虑了全部父任务合并，未考虑部分父任务合并的可能性，而且未考虑任务间的非线性合并．本文基于任务复制提出了ＤＣＴ算法，改变了传统以ＤＡＧ图调度为主的不足，将Ｇａｎｔｔ图引入到调度过程中，提出了相应时间参数，合理表示了任务在调度过程中的状态，依此准确确定关键任务，以关键任务为核心进行优化调度，并动态确定关键任务，克服了贪心算法的不足；ＤＣＴ算法既考虑了任务间的线性合并也考虑了非线性合并，．增加了任务合并的可能性．实验结果表明，ＤＣＴ算法在调度长度和处理器数目方面优于同类算法．
２调度算法模型
一个任务系统可以用一个四元组的有向无环图（ＤＡＧ）表示为
Ｇ＝（Ｖ，Ｅ，Ｗ，Ｃ）
其中，Ｖ一｛ｎ；ｈ为有序任务，ｉ＝１，２，…，口，ｕ为任务
数目）；
Ｅ＝ｋ．』旧，』表示行ｉ到咒』的边，，ｚｔ称为咒Ｊ的父任
务，，ｚｉ称为咒；的子任务）；
Ｗ＝｛硼。ｌ训。表示竹；的计算开销）；Ｃ＝｛ｃｌ。』ｋ，Ｊ表示，２；到，ｚ』的通信开销）；ｐ卯ｄ（极）＝｛嘶Ｊｑ．ｆ∈Ｅ）；跚ｃｆ（ｎｔ）＝｛，ｌ川毋。ｆ∈Ｅ）；
如果咒。没有父任务，则绝为开始任务；如果啦没有子任务，则佗；为结束任务．
不失一般性，假定ＤＡＧ图仅有一个开始任务和一个结束任务Ⅲ．本文用咒；表示开始任务，用他表示结束任务．
任务系统的子任务分配到处理器之后，其分配情况可以用一个７元组的Ｇａｎｔｔ图表示为
Ｇ口＝（Ｐ，Ｔ，ＣＬ，ＥＰＳＴ，ＥＰＦＴ，ＬＡＳＴ，ＬＡＦＴ）．
Ｔ一‰，ｋ，表示分配到户；中的第Ｊ个任务）；
将被调度任务分配到父任务所在处理器和一个空处始时间，以此缩短调度长度．
其中，Ｐ一｛户。Ｉ夕；表示第ｉ个处理器，ｉ＝１，２，…，ｍ，优为处理器数目）；
４５６
计算机学
ｅｐｓ￡ｆ，』２ｆＯ，
报
ＣＬ＝｛ｃｚ。ｌｃ厶表示夕；中的有序任务队列）；ＥＰＳＴ＝｛ｇ户ｓｏ州ＩＰ户站州表示‘州的最早可能开始时间ｂ
ＥＰＦＴ＝｛Ｐｐ以州ｌＰ夕＾嘶表示‘叫的最早可能结束时间）；
￡ｉ。』一扎，
｛ｍｘｉ。∈鬈∥则已舨＾㈦∥ｈ瓶一１｝，
【
其它
（７）
ＬＡＳＴ一｛肠对叫Ｉ如ｓ‰表示‰的最迟允许开始
时间｝；
ＬＡＦＴ一｛Ｚｎ，￡¨ｌ纪力嘶表示￡¨的最迟允许结束时间）．
ｃ厶中第一个任务称为夕ｉ的首任务，最后一个任
而可能结束的最早时间，由式（１）确定．
８ｐ以谢是指￡谢具备开始条件后立即开始执行ｐ；的关键任务ｏ¨是指ｐ；中满足Ｐ户丘州一－＜Ｐｐ盯¨（Ｊ≥２）的任务；除关键任务以外的任务称为非关键任务．
ｚ口以州是指￡州不影响子任务和后继任务最迟允许开始时间而最迟允许的结束时间，由式（８）确定．Ｚｎ丘¨一
Ｐｐ／￡ｉ．Ｊ，
￡｛，』。咒。
务称为户；的尾任务，￡州称为。叫＋。的前驱任务，岛一，称为如，ｊ的后继任务．
ＤＡＧ图刻画了任务系统的静态关系，Ｇａｎｔｔ图则刻画了任务系统变化了的动态的关系．对于任务复制算法，ＤＡＧ图中的任务在Ｇａｎｔｔ图中至少出现一次，最多ｍ次，在户。中则至多出现一次．夕；中
ｍｉｎ｛，２ｉ２、｛如ｓ“．；一ｃ“∽ｍｍ｝），、‘＾．ｚ∈Ⅲ（ｉ・Ｊ）
’
＾≠ｉ
￡¨唯一地和ＤＡＧ图中任务ｎ对应，用‘叫一以表示，
反之则不成立．在不引起歧义和便于理解的情况下，本文也用硼¨来表示ｔ奶的计算开销，用ｃｃ州）＇（州，或ｃ州州）（ｚ¨一咒）表示“，，和￡¨之间的通信开销，用夕ｒＰｄ（ｉ，ｊ）和ｓ“ｃｃ（ｉ，．『）表示￡州的父任务集和子任务集，用Ｐ㈦ｍ（圳）∈Ｅ表示￡ｉｊ是￡¨的父任务．任务佗分配到户；用咒∈ｃ厶表示，反之用扎仨ｃ厶表示．
本文采用和文献［２—３，９］相同的算法假设，即假设多处理器系统是同构的，处理单元之间是全连接且通信效率相同，处理单元具有Ｉ／Ｏ单元，处理单元之间通信可以和任务计算同时进行．假定任务执行是非抢占的，则Ｇａｎｔｔ图中的任务均满足以下关系：
Ｐ声以ｉ，』＝８夕盯ｉ，』＋叫ｆ，』
（１）（２）
￡¨为尾任务时
（８）
ｍｉｎ｛．曼ｉ２、｛ｚ口ｓ如，。一ｃ。；．，，，。。ｍ），ｚ口ｓ￡；，，＋。｝，
、￡１．ｆ∈５斯ｆ（ｉ＇Ｊ）
其它
肠ｓ‰是指￡州不影响子任务和后继任务最迟允
许开始时间而最迟允许的开始时间，由式（９）确定．
纪ｓ￡“Ｊ一如＾¨一硼嘶
可能完成时间的最大值，即
ＳＬｆ—ｍａｘ｛Ｐｐ丘州）
￡ｆ．Ｊ∈ｄ‘
（９）
处理器户ｉ的调度长度ＳＬ，是指夕ｉ中任务的最早
（１０）
一个任务系统的调度长度ＳＬ（Ｓｃｈｅｄｕｌｅｋｎｇｔｈ）定义为所有ＳＬ；中的最大者，即
ＳＬ＝ｍａｘ｛ＳＬ。）
１≤ｆ≤ｍ
（１１）
Ｚ口以ｆ．』一纪５“＋硼ｆ，Ｊ
如果忌＞Ｊ，则
８户∥Ⅲ≤Ｐ夕跪，＾肠＾¨≤Ｚ口“矾
如果
Ｐ（ｆ，ｍ㈦＾）∈Ｅ，则志＞歹
ＳＬ。为ｐ。中尾任务的最早可能结束时间，ＳＬ为吼的最早可能结束时间．
当ＳＬ。无法进一步减小时，称ＳＬｉ达到最优．分析式（１０）可以得知，调度长度和任务的最早可能结束时间密切相关，而任务的最早可能结束时间和任务所在的处理器、其父任务位置及前驱任务的完成时间有关，这样调度长度的优化就转化为对Ｇａｎｔｔ图的优化．而关键任务在优化过程中有极其重要的作用，为此给出以下两个定理．
定理１．
证明．
（３）（４）（５）
数据到达时问ｄ口“一ｍ是指父任务竹（咒硭ｆｚ；）的数据到达￡州的最早时间，可由式（６）确定．
ｄｎ￡。，（叫）＝
ｎ∈ｐⅢ‘ｌ＇，）
＂岳“ｌ’‘＾．ｆ一”
ｍｉｎ
｛ｅｐ＾¨＋厶．（ｆ，Ｊ）｝
（６）
￡¨的关键父任务则是指父任务中数据到达时间最大的任务，为使式（６）取得最大值的任务．
Ｐ户ｓ幺．Ｊ是指‘¨具备开始条件（得到所有数据且前驱任务完成）后可能开始执行的最早时间，由式
（７）确定．
关键任务是减小调度长度的核心．可分两个方面来证明．
（１）非关键任务友，，满足Ｐ户盯¨一Ｐ户＾。一－，其Ｐ夕盯州由‘州一ｔ确定，在Ｐ户＾嘶一－没有减小的前提下，Ｐ户ｓ‘研无法减小，由式（１）知，Ｐｐ厂‘叫是无法减小的；
万方数据
３期
兰
舟等：基于动态关键任务的多处理器任务分配算法
４５７
（２）改善关键任务的最早可能完成时间就有可能减小调度长度．当尾任务￡抽是关键任务时，如果Ｐｐ丘咖减小，由式（１０）可知，ＳＬｆ会随之减小；当反，。是关键任务而ｅ户力姗不能减小或￡ｆ＇口不是关键任务时，减小户。中关键任务￡叫的Ｐ户∥嘶将为减小￡ｍ（忌＞歹）的Ｐｐ＾矾创造机会，继而为减小尾任务岛，。的
印以抽提供可能，因而就有可能改善ＳＬ。．
综合（１），（２）可知定理成立．证毕．
定理２．
当夕。中没有关键任务或所有关键任务￡¨的Ｐｐ＾Ⅲ均不能减小时，ＳＬｉ达到最优．
证明．
分两种情况证明．
（１）当户ｉ中没有关键任务时，ｐ；中任务均为非关键任务，由定理１知，户。中的所有任务￡¨的Ｐ户，一￡¨均不能减小，ＳＬ；也就不能减小，ＳＬ。达到最优；
（２）当ｐｉ中有关键任务￡州时，由于所有关键任务岛，ｉ的Ｐ户丘¨均不能减小，而非关键任务￡ｍ的ｅｐ丘ｍ又不能减小，ＳＬｉ也就不能减小，ＳＬｉ达到最优．
综合（１），（２）可知定理成立．
证毕．
定理１说明了减小调度长度的可能途径，定理２说明如何判断调度长度已达到最优．这两个定理构成了ＤＣＴ算法的理论基础．３
ＤＣＴ调度算法
ＤＣＴ调度算法的基本原理是，动态地确定当前
处理器的关键任务，将其关键父任务复制到当前处理器，以减小关键任务‘¨的ｅ夕＾叫，从而减小ＳＬ；。ＤＣＴ算法包括两个主要内容，一是选择策略，即选取未调度任务中哪一个任务予以调度的策略；二是复制策略，即决定什么任务需要复制，在什么时候复制，复制到什么地方．
ＤＣＴ算法的实现过程是，每调度一个新的任务，就构造一个当前处理器，当前处理器开始只包括开始任务和当前任务，然后动态地确定当前处理器中的关键任务，将关键任务的关键父任务复制到当前处理器，直到当前处理器中关键任务的最早可能完成时间不能减小或没有关键父任务时为止．
３．１
选择策略
ＤＣＴ算法选用任务深度为权值，采用小者优先
策略构建调度队列，任务深度由式（１２）确定．
‘ＰｕＰ￡（行｛）一１
，，，、ｆｏ＇
％勒一
ｍａｘ｛ｚＰ剐“（咒，））＋１，
其它
（１２）
万方数据
深度相同时，以序号小者优先．由式（１２）可知，父任务的深度值必然小于子任务的深度值，确保了父任务先调度，子任务后调度，开始任务最先调度，结束任务最后调度，满足了ＤＡＧ图中任务间的优先关系．
３．２
复制策略
３．２．１关键任务确定
由定理１可知，关键任务是减小调度长度的核心，只有某个关键任务￡。的ｅｐ＾¨减小了，ＳＬ；才有可能减小．根据关键任务定义可构造确定ｐ。中关键任务的启发函数为
Ｈ１（ｉ）一‰，ＩＰ户，‰一，＜已户ｓ‰且Ｊ≥２）
（１３）
式（１３）可能确定出多个关键任务瓦川越靠近尾任务的关键任务对尾任务最早可能完成时间影响越大，作用越直接，因而ＤＣＴ算法采用歹值大者优先的策略，依次优化（减小）这些关键任务的最早可能完成时间，一旦有关键任务的最早完成时间得到了优化，就停止优化过程，重新确定关键任务后进入下一轮优化．
３．２．２复制任务确定
由式（１）可知，任务￡¨的８ｐ丘¨由Ｐ夕ｓ￡。和叫。之和确定，硼¨是固定不变的，只有Ｐｐ盯ｉ，减小了，８户＾¨才会减小．由式（７）可知，Ｐ户ｓ￡。由‘叫的关键父任务挖的ｄｎ￡州。）和前驱任务‘嘶一１的Ｐ户以叫一ｌ确
定，为如￡州叫，和８乡以州一。的大者．由关键任务的定
义可知，关键任务￡州的ｄ口￡。’（ｉｍ大于其前驱任务￡Ⅲ一１的Ｐｐ豇埘一１，这样缩小关键任务￡叫的ｅｐｓ￡叫就转化为缩小关键任务的ｄ口￡。一，ｊ）．由式（６）可知，任
务￡州的ｄ口￡州州，由‰的关键父任务咒的最小的
Ｐ户以¨（“，。一咒）及ｃ。．（｛ｍ之和确定，而经过前期调度，关键父任务孢最小的８夕丘¨（“，ｚ一咒）已经为最，优了，只能在“Ⅲ，ｊ，上作文章．当父任务和子任务分配到同一处理器中时，二者的通信为处理器内部通信，通信时间可近似为ｏ，因而可以将关键父任务ｎ复制到当前处理器，将原来咒和￡¨在处理器之间的通信变为处理器内部的通信，忽略通信时间％㈦ｊ，而减小关键任务￡¨的ｄ口￡州。），以减小‘州的Ｐｐｓ‘¨．需要注意的是，对于复制到当前处理器的关键父任务来说，其最早可能开始时间会发生变化，当变化到使关键任务的最早可能开始时间增大时，应将和关键父任务在同一处理器的其父任务一起复制到当前处理器，直到关键任务￡。的Ｐ夕ｓ￡。有减小为止．由式（６）及关键父任务的定义，可以得到确定关键任务￡。的关键父任务￡加的启发函数为
４５８计算
机
学报
Ｈ一
０
咋
鬈
ｐ，如
＋厶
ｍ¨ｍ～
３．２．３复制位置确定
参数Ｐｐｓ￡。，ｅｐ少州，比ｓ￡州，ｚｎ丘¨准确刻画了￡¨在ｐ。中所处的位置，在时间段ｅｐ疏’』＇肠“¨内任意安排￡。的开始时间均不会影响ＳＬｉ，为其它任务复制到≠州之后或之前提供了可能．在满足任务间优先关系的前提下，对于关键任务反＂￡加必须满足以下条件才能复制到￡¨与￡州一，之间：
Ｐｐｓ￡。，』一８ｐ以¨一ｌ＞叫…，ｊ≥２
（１５）
对于其它任务‰，￡姗必须满足以下条件才能
复制到￡¨之前：
ｚ口ｓ‰一Ｐ户＾叫一ｌ≥叫加，歹≥２
（１６）式（１５）或式（１６）确定了￡加可以复制的位置，一般来说，式（１６）可能确定多个可以复制的位置．算法
实现时，将￡加复制到使关键任务或关键父任务取得
最小最早可能开始时间的位置．
每复制一个任务之后，任务时间参数发生改变．如果关键任务的最早可能开始时间有改善则停止复制操作，重新确定关键任务后再复制有关任务，否则应考虑将先前所复制任务的父任务一起复制到当前处理器，直到关键任务的最早可能开始时间有改善或无法改善或没有关键任务为止．３．２．４冗余队列删除
为了保留任务获得最早可能开始时间的调度安排，每调度新任务时，ＤＣＴ算法都重新构造一个当前处理器，最多时有口一１个处理器队列．口一１个处理器队列中有些属于冗余调度，没有这些队列不会对任务系统调度和调度长度产生任何影响．为了节约资源，需要将冗余队列删除．ＤｃＴ算法实现这个功能时，先统计只调度过一次的任务（‰除外），然后依次删除不包含这些任务的处理器队列，删除后ＳＬ无变化则删除成功，否则撤消删除．３．３处理器数目优化
处理器数目优化是指在不增大ＳＬ的前提下，将两个或两个以上处理器中的任务合并到一个处理器上，以减少处理器数量．
ＤＣＴ算法的处理器数目优化分为两个阶段，第一阶段为线性合并，依次对子任务检查，将尽可能多的父任务所在处理器队列合并到子任务所在的处理器队列中．任务从一个处理器合并到另外一个处理器之后，任务时间参数会发生变化．为了确保不影响调度长度，在满足任务间优先关系的前提下，除两个
万方数据
处理器均有的任务外，Ａ中任务￡¨同时满足了以下关系后才能合并于ｐ；中的￡嘶和￡。＋，之间：
缸ｓ‰＋ｌ—Ｐｐ弘州≥姒，ｚ
（１７）Ｚ口＾ｌ，ｆ≤Ｚ口ｓ￡。，ｊ＋１
（１８）比ｓ‰≥Ｐ夕以¨
（１９）
式（１７）保证了可以在ｆ¨及。奶＋－之间合并“，ｆ，式（１８）保证了合并“，。之后不会影响￡州＋－的ｚｎｓ￡训＋１，式（１９）保证了合并“，，之后其ｚ口ｓ￡引可以得到保证，不会影响其子任务的最迟允许开始时间．除Ａ及ｐ。均有的任务外，户ｔ中所有其它任务都满足式（１７）～式（１９）之后才能将ｐｔ中的任务合并于ｐｉ中，合并之后删除ｍ，ＳＬ无变化则合并成功，否则撤消合并．
第二阶段为非线性合并，将不相关处理器中的任务合并到其中的一个处理器中．所谓不相关处理器是指两处理器中除开始任务外，没有相同的任务，也不存在分属于两处理器中的两个任务有共同子任务的情况．一般将调度长度小的合并到调度长度大的处理器中．如有两不相关处理器夕。和户ｔ，将Ａ中的任务￡¨合并于夕ｉ中的任务￡¨和任务￡ｆ＇ｊ＋。之间，则要求￡¨同时满足式（１７）～式（１９）；如果将ｐｔ中的尾任务￡¨合并于夕ｉ中的尾任务￡ｑ之后，则只要求满足式（１９）．除ｍ外，Ａ中所有任务均满足条件时才能将ｐ。中的任务合并于夕ｉ中．合并后删除夕ｔ，ＳＬ无变化则合并成功，否则撤消合并．３．４算法描述
ＤＣＴ算法的总体实现为：
Ａ１９０ｒｉｔｈｍ
ＤＣ：ｒ＿ｓｆ＾ｅ矗群ＺＰ（Ｇ，Ｇ口）
｛
／／ｉｎｐｕｔ：Ｇ一（Ｖ，Ｅ，Ｗ，Ｃ）
／／ｏｕｔｐｕｔ；Ｇａ＝（Ｐ，Ｔ，ＣＬ，ＥＰＳＴ，ＥＰＦＴ，ＬＡＳＴ，
ＬＡＦＴ）
Ｓ娩Ｐｄ“Ｚ已（Ｇ，Ｇｎ）；Ｍ；ｒｇＰ（Ｇ，Ｇｎ）；｝
算法中，默认输入的ＤＡＧ图只有一个７２，和一个行。，任务按深度值从小到大进行了排序，因而省略了构建调度队列的实现．Ｓ砌ｅｄ“如（）函数实现任
务复制功能，并删除冗余队列；地ｒｇｇ（）函数实现任务合并，减少处理器数目．Ｓｃ＾ｅｄ“ｚＰ（），№ｒｇＰ（）的
具体实现如下：
ｖｏｉｄＳｃ＾Ｐｄ“ＺＰ（Ｇ，Ｇ口）
｛
／／ｉｎｐｕｔ：Ｇ一（Ｖ，Ｅ，Ｗ，Ｃ）
／／ｏｕｔｐｕｔ：（１ｎ一（Ｐ，丁，ＣＬ，ＥＰＳ丁，ＥＰＦＴ，ＬＡＳ丁，
３期
兰舟等：基于动态关键任务的多处理器任务分配算法
４５９
ＬＡ｝”Ｉ’）
ｆｏｒ（ｉ一２；ｉＧ口；ｉ＋＋）／／ｕ为ＤＡＧ图的任务个数
（
构造包含开始任务和任务ｉ的处理单元夕ｉ；
ｄｏ
｛
查找夕ｉ的关键任务及其关键父任务；复制关键父任务及其父任务（需要的话）
）ｗｈｉｌｅＳ厶有提高且有关键任务；）／／ｅｎｄｏｆｆｏｒ
统计只调度过一次的任务；／／删除冗余队列ｆｏｒ（ｉ一１；ｉ＜＝户；ｉ＋＋）／／户为处理器数目
（
ｉｆ户ｉ中不包含只调度过一次的任务ｔｈｅｎ
｛
删除∥；
ｉｆ
ＳＬ增加ｔｈｅｎ撤消删除；
ｅｌｓｅ统计只调度过一次的任务；
）
）／／ｅｎｄｏｆ删除冗余队列｝／／ｅｎｄｏｆｓｃ＾ｅｄ“如（）
ｖｏｉｄ
Ｍｅｒ９８（Ｇ，Ｇ口）
ｆ
／／ｉｎｐｕｔ：Ｇ一（ｙ，Ｅ，’矿，Ｃ）
／／ｏｕｔｐｕｔ：Ｇ口一（Ｐ，Ｔ，（ｊＬ，ＥＰＳＴ，ＥＰＦＴ，ＬＡＳ丁，
ＬＡＦｎ
查找ＩｐｒＰｄ（，ｚ。）Ｉ≥２的任务并计数，不妨设为量；ｆｏｒ（ｉ一七；ｉ＞＝１；ｉ＋＋）／／线性合并
（
查找挖［妇所在的处理器并存入加口，并计数，设为ｍ；
ｆｏｒ（ｊ一１０＜．＿ｍ；ｊ＋＋）｛
查找除多［ｊ］以外，挖［妇父任务所在的处理器并存入
如琥ｅｒｐｅ口，对处理器计数，设为砣；
ｆｏｒ（ｑ＝１；ｑ＜≥：咒；ｇ＋＋）｛
ｉｆ．肠ｔ＾ＰｒｐＰ［ｑ］能并入ｐ８［刀ｔｈｅｎ
｛
知髓Ｐ印ｅ［口］并入加［ｊ］；
ｉｆ
ＳＬ增加ｔｈｅｎ撤消并入；
）））
）／／ｅｎｄｏｆ线性合并
按Ｓ厶从小到大将“；排序，设有女个处理器；ｆｏｒ（ｉ一是；ｉ＞一１；ｉ＋＋）／／非线性合并
（
查找与虻妇无关的处理器存入加口，设有优个；
ｆｏｒ（ｊ＝１；Ｊ＜－＿ｍ；ｊ＋＋）｛
ｉｆ加［力能并人加［ｉ］ｔｈｅｎ
万方数据
｛
加［力并入加［ｉ］；
ｉｆ
ＳＬ增加ｔｈｅｎ撤消并人；
）｝
）／／ｅｎｄｏｆ非线性合并
）／／ｅｎｄｏｆｍ８ｒ９８（）
分析ＤＣＴ算法及其实现可得定理３．
定理３．
采用ＤＣＴ算法所得到的调度长度优
于ＰＰＡ及ＣＰＦＤ算法，所用处理器数目少于ＰＰＡ算法．
证明．
ＰＰＡ及ＣＰＦＤ算法采用贪心算法的策
略，试图用局部最优获得全局最优的调度结果．ＤＣＴ算法在调度过程中动态确定关键任务，并保留前期任务的最优调度信息，保证了调度优化对象的正确性．每次调度只要求调度长度有改善即可，克服了贪心算法的不足，使调度过程更加合理，其结果优于ＰＰＡ及ＣＰＦＤ算法．
ＤＣＴ算法既考虑了任务间的线性合并也考虑了非线性合并，并采用逐步合并方式，增加了任务合
并可能性，其合并结果优于ＰＰＡ算法．证毕．
４算法性能分析
ＤＣＴ算法由Ｓｃ＾Ｐｄ“ｚＰ（），胁ｒｇＰ（）两个函数构
成．Ｓ如８ｄ托据（）函数中主循环的循环次数是口一１次，内循环在最坏的情况下为ｒ已次，ｒ为各处理器中任务数的最大值，ｅ为ＤＡＧ图中任务人度的最大
值，故Ｓ旗Ｐ矗“抛（）函数时间复杂度为ｏ（ｒＰ口）．
地ｒｇｅ（）函数中，线性合并的循环次数最多为
Ｏ（口ｐ２），ｐ为处理器数目，非线性合并的循环次数最
多为０（户２），故胁ｒｇｅ（）的算法复杂度为０（印２）＋
０（ｐ２）一０（口２ｐ）．因而ＤＣＴ算法的时间复杂度为
Ｄ（ｒ口刀）＋０（护夕）＝Ｏ（ｕ２ｃ），ｆ为Ｐ和ｐ的大者．和
ＰＰＡ及ＣＰＦＤ算法相比（见表１），当夕＞已时，ＤＣＴ算法的时间复杂度有所增大，但ＤＣＴ算法保证了取得最优的调度结果，而ＰＰＡ和ＣＰＦＤ算法不一定能取得最优的调度结果．
表ｌ算法时间复杂度对照表
算法
时问复杂度
ＰＰＡ０（口２Ｐ）’ＣＰＦＤ
Ｏ（护Ｐ）ＤＣＴ
ｏ（护ｃ）
注，＊原文为Ｏ（护），有误
４６０
计算机学报
５
实验对比
本文算法示例为图１所示任务系统．圆圈表示
任务，圆圈中上方数字为任务编号，下方数字为任务计算开销，箭头线旁数字为两个任务间的通信开销．
图１
不例用的ＤＡＧ图
采用ＰＰＡ，ＣＰＦＤ，ＤＣＴ算法对示例调度，结果分别如图２，图３，图４所示．Ｐ历（ｉ＝１，２，３，４，５，６）为处理器编号，圆角方框表示任务，其上方数字为任务编号，下方数字为任务计算开销，图中阴影部分表
示处理器等待时间区．
为了进一步对比ＤＣＴ，ＰＰＡ，ＣＰＦＤ算法的调
度性能，本文分别采用ＤＣＴ，ＰＰＡ，ＣＰＦＤ算法对随机任务图调度．随机任务图的产生方式见文献［１２］．任务个数ＴＮ（ＴａｓｋＮｕｍｂｅｒ）为２０，４０，６０，８０，１００，通信计算比率ＣＣＲ（Ｃｏｍｍｕｎｉｃａｔｉｏｎ
ｔｏ
Ｃｏｍｐｕｔａ—
ｔｉｏｎ
Ｒａｔｉｏ）［１２３为０．５，２．ｏ，５．０，每种丁Ｎ和ＣｃＲ组
合随机产生２０个ＤＡＧ图，取调度结果的平均值作为算法在此种组合条件下的调度结果．计算结果如图５，图６所示．图５中的横坐标是丁Ｎ，纵坐标是规
Ｏ
５
胁田曰
如
眦圈日臼崮
ｎ
加
孙
阉问淌∞㈦褥嗣囝㈤
～～
峨嚆㈤峨—坻，叫
隅雕醺］；｛ｌ√麟震崮剀｜｛Ｊ
图２
ＣＰＦＤ的调度结果
万方数据
格化调度长度ＮＳＬ（Ｎｏｒｍａｌｉｚｅｄ
ＳｃｈｅｄｕｌｅＬｅｎｇｔｈ），
它是利用变换变量将算法产生的调度长度规格化而得到的，本文采用的变换变量是ＤＡＧ图中关键路径上所有任务的计算开销之和ｍ］．
Ｏ
５
ｍ
隅囝剐富
瞰圄
ｌ｜鳓州Ｈ函口曰
巧
∞
衢
髓阑㈤㈧㈦㈣邕■■魔一～｜｜
图３
ＰＰＡ的调度结果
Ｏ
５
ｍ
临
Ⅺ
眦阑㈤㈥磁㈣域瞧感愀讯懋心；ｌ｜＼瞰蕊邕㈦｜｛；一秭藤雠拶｛ｌ｜ｌ；√
图４
Ｉ）ｃＴ的调度结果
和ＰＰＡ及ＣＰＦＤ算法相比，ＤＣＴ算法是以两任务间后一任务最迟开始时间和前一任务最早完成时间的时间间隔作为任务复制空间，而ＰＰＡ及ＣＰＦＤ算法则是以两任务间后一任务最早开始时间和前一任务最早完成时间的时间间隔作为任务复制空间．一般来说，前者大于后者，ＤＣＴ算法中任务复
制的可能性大于ＰＰＡ及ＣＰＦＤ算法，这是ＤＣＴ算法优于ＰＰＡ及ＣＰＦＤ算法的原因之一．ＣＣＲ值越大，则任务系统中通信开销相对计算开销越大，ＤＣＴ算法的任务复制空间越大于ＰＰＡ及ＣＰＦＤ算法，调度长度提高越大，这一点在图５中得到了验证．当ＣＣＲ为５．０时，ＤＣＴ算法较ＰＰＡ及ＣＰＦＤ
算法ＮＳＬ最大提高ｏ．６２７６（ＴＮ一１００），最小提高０．１２８８（ＴＮ＝２０）；而当ＣＣＲ为Ｏ．０５时，ＮＳＬ最大提高０．００６７（ＴＮ＝１００），最小提高仅Ｏ．ｏ００２
（ＴＮ一８０）．
３期兰舟等：基于动态关键任务的多处理器任务分配算法
４６１
从图２～６可以看出，对同一个（组）ＤＡＧ图，采用ＤＣＴ算法得到的调度长度均小于ＰＰＡ，ＣＰＦＤ
算法，所需处理器比ＰＰＡ，ＣＰＦＤ算法少．
图５ＰＰＡ，ＣＰＦＤ，ＤＣＴ算法对随机ＤＡＧ图调度的调度长度对比图
图６ＰＰＡ，ＣＰＦＤ，ＤＣＴ算法对随机ＤＡＧ图调度所用处理器数目对比图
ｐｒｏｃｅｓｓｏｒｔａｓｋｓ
ｗｉｔｈ
ｇｅｎｅｔｉｃａｌｇｏ“ｔｈｍｓ．
ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ
６
结束语
本文在分析了几个典型的基于任务复制的调度
ｏｎ
ＰａｒａＩｌｅｌａｎｄＤｉｓｔ“ｂｕｔｅｄ
Ｓｙｓｔｅｍｓ，１９９９，１０（８）：８２５—８３７
ｈｙｂｒｉｄ
ｇｅｎｅｔｉｃ
［３］Ｚｈｏｎｇ
ｆｏｒｎａＩ
Ｙｉ—Ｗｅｎ，ＹａｎｇＪｉａｎ—Ｇａｎｇ．Ａ
ｉｎ
ａｌｇｏｒｉｔｈｍ
ｔａｓｋｓｓｃｈｅｄｕｌｉｎｇ
ｏｆ
Ｆｕｄａｎ
ｐａｒａｌＩｅｌｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓｙｓｔｅｍｓ．Ｊｏｕｒ—
２００４，４３（５）：
Ｕｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ），
算法的基础上，提出了ＤＣＴ算法，采用ＤＡＧ图和Ｇａｎｔｔ图共同刻划调度过程，以Ｇａｎｔｔ图为主提出了准确描述任务位置和状态的时间参数．ＤＣＴ算法在调度过程中动态地确定关键任务，克服了贪心算法的不足，使得调度过程准确合理；ＤＣＴ算法既考虑了任务间的线性合并也考虑了非线性合并，增加了处理器队列合并的可能性．分析和实验表明，ＤＣＴ算法在调度长度和处理器数目方面优于其它同类算法．
ＤＣＴ算法在调度过程中保留了任务获得最早可能开始时间和最早可能结束时间的调度安排，最多时有ｕ一１个处理器队列，使得算法的空间复杂度较大，有待进一步优化．
参
考
［７］［６］［５］［４］
９１８—９２２Ａｔｔｉｙａｃｉｎｇｔｈｅ
ｉｎ１２ｔｈ
Ｇ，ＨａｍａｍＹ．Ｔｗｏ
ｐｈａｓｅａｌｇｏ“ｔｈｍｆｏｒ１０ａｄｂａｌａｎ—
ｓｙｓｔｅｍｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ
ｏｆ
ｈｅｔｅｒｏｇｅｎｅｏｕｓ
ｄｉｓｔｒｉｂｕｔｅｄ
ｏｎ
ＥｕｒｏｍｉｃｒｏＣｏｎｆｅｒｅｎｃｅ
Ｐｒｏｃｅｓｓｉｎｇ．
ＰａｒａＵｅｌ，Ｄｉｓｔｒｉｂｕｔｅｄａｎｄ
２００４：
４３４—
Ｎｅｔｗｏｒｋ－Ｂａｓｅｄ
４３９
ＡＣｏｒｕｎａ，Ｓｐａｉｎ，
ＷｕＭｉｎ＿Ｙｏｕ，ＳｈｕＷｅｉ，
ｓｃｈｅｄｕｌｉｎｇ
ａｎｄ
Ｇｕ
Ｊｕｎ．
ＬｏｃａｌｓｅａｒｃｈｆｏｒＤＡＧ
ｔａｓｋａｓｓｉｇｎｍｅｎｔ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩｎｔｅｒｎａ—
ｏｎ
ｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＰａｒａＵｅｌ
Ｐｒｏｃｅｓｓｉｎｇ．Ｂｌｏｏｍｉｎｇｔｏｎ，ＩＬ，
ＵＳＡ，１９９７：１７４—１８０
Ｌｉｕ
ＧＱ，Ｐｏｈ
ＫＬ，ＸｉｅＭ．ＩｔｅｒａｔｉｖｅＪｏｕｒｎａｌｏｆ
ｌｉｓｔ
ｓｃｈｅｄｕｌｉｎｇｆｏｒｈｅｔ—
ａｎｄ
ｅｒｏｇｅｎｅｏｕｓｃｏｍｐｕｔｉｎｇ．
Ｐａｒａｌｌｅｌ
Ｄｉｓｔｒｉｂｕｔｅｄ
Ｃｏｍｐｕｔｉｎｇ，２００５，６５（５）：６５４—６６４
Ｂｏｅｒｅｓｇｙ
Ｃ，ＦｉｌｈｏＪＶ，Ｒｅｂｅｌｌｏ
ｔａｓｋ
ｏｎ
ＶＥＦ．Ａｃｌｕｓｔｅｒ－ｂａｓｅｄ
ｓｔｒａｔｅ—
ｆｏｒｓｃｈｅｄｕｌｉｎｇ
ｏｆ
ｔｈｅ
ｈｅｔｅｒｏｇｅｎｅｏｕｓ
ｏｎ
ｐｒｏｃｅｓｓｏｒｓ／／Ｐｒｏ—
Ａｒｃｈｉｔｅｃｔｕｒｅ
Ｂｒａｚｉｌ，
ｃｅｅｄｉｎｇｓ
ａｎｄ
１６ｔｈ
ＳｙｍｐｏｓｉｕｍＣｏｍｐｕｔｅｒＦｏｚｄｏ
ＨｉｇｈＰｅｒｆｏｒｍａｎｃｅＣｏｍｐｕｔｉｎｇ．
Ｉｇｕａｃｕ，
文献
２００４：２１４—２２１
［８］
ＰａｌｉｓＭｕｌｉｎｇ
Ａ，Ｌｉｏｕ
Ｊ—Ｃ，ＷｅｉＤＳＬ．Ｔａｓｋｃｌｕｓｔｅｒｉｎｇａｎｄｓｃｈｅｄ—
ｐａｒａｌｌｅｌ
ａｒｃｈｉｔｅｃｔｕｒｅｓ．
ＩＥＥＥ
ｆｏｒ
ｄｉｓｔ“ｂｕｔｅｄｍｅｍｏｒｙ
ｏｎ
［１］
ＴｏｐｃｕｏｇｌｕＨ，ＷｕＭｉｎ—Ｙｏｕ．Ｐｅｒｆｏｒｍａｎｃｅ—ｅｆｆｅｃｔｉｖｅｃｏｍｐｌｅｘｉｔｙ
ＩＥＥＥ
ａｎｄｌｏｗ—
ＴｒａｎｓａｃｔｉｏｎｓＰａｒａｌｌｅｌａｎｄＤｉｓｔｒｉｂｕｔｅｄＳｙｓｔｅｍｓ，１９９６，７
ｔａｓｋ
ｓｃｈｅｄｕｌｉｎｇ
ｏｎ
ｆｏｒ
ｈｅｔｅｒｏｇｅｎｅｏｕｓｃｏｍｐｕｔｉｎｇ．ｓｙｓｔｅｍｓ，
（１）：４５—５５
ＴｒａｎｓａｃｔｉｏｎｓＰａｒａｌｌｅｌａｎｄＤｉｓｔ“ｂｕｔｅｄ
［９］ＤａｒｂｈａＳ，Ａｇｒａｗａｌｄｉｓｔ“ｂｕｔｅｄ—ｍｅｍｏｒｖ
ＤＰ．
０ｐｔｉｍａｌｓｃｈｅｄｕｌｉｎｇ
ａｌｇｏｒｉｔｈｍ
ｏｎ
ｆｏｒ
２００２，１３（３）：２６０—２７４
ｍａｃｈｉｎｅｓ．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓＰｄｒａｌｌｅｌ
［２］
ＣｏｒｒｅａＲＣ，ＦｅｒｒｅｉｒａＡ，Ｒｅｂｒｅｙｅｎｄ
Ｐ．
Ｓｃｈｅｄｕｌｉｎｇｍｕｌｔｉ—
ａｎｄＤｉｓｔ“ｂｕｔｅｄ
Ｓｙｓｔｅｍｓ，１９９８，９（１）：８７—９５
万方数据
４６２
计算机学报
２００７年
［１０］ＰａｒｋＣ—Ｉ，Ｃｈｏｅ’ｒ．Ｙ．Ａｎｏｐｔｉｍａｌｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄ
ｏｎ
ｔａｓｋ
ｄｕｐｌｉｃａ“ｏｎ．
ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎ
Ｃｏｍｐｕｔｅｒｓ，
２００２，５１（４）：４４４—４４８［１１］ＺｈｏｕＳｈｕａｎｇ－Ｅ，
Ｙｕａｎ
Ｙｏ旷Ｇｕａｎｇ，ＸｉｏｎｇＢｉｎｇ＿Ｚｈｏｕ，
ｏｕ
Ｚｈｏｎｇ—Ｈｏｎｇ．Ａｎａｌｇｏｒｉｔｈｍｏｆ
ｐｒｏｃｅｓｓｏｒ
ｐｒｅ—ａｌｌｏｃａｔｉｏｎｂａｓｅｄｏｎ
ｔａｓｋ
ｄｕｐｌｉｃａｔｉｏｎ．ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒｓ，２００４，２７（２）：２１６—２２３（ｉｎＣｈｉｎｅｓｅ）
ＬＡＮ
Ｚｈ伽。ｂｏｒｎ
ｉｎ１９６９，Ｐｈ．Ｄ．
ｃａｎｄｉｄａｔｅ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅ
ｎｅｔｗｏｒｋ
ｃｏｍｐｕｔｉｎｇａｎｄ
ｈｉｇｈ
ｐｅｒｆｏｒｍ—
ａｎｃｅ
ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ．
Ｂａｃｋｇｒｏｕｎｄ
Ａｓｍａｉｎ
ｐａｒｔ
ｏｆｔｈｅｈｉｇｈｐｅｒｆｏｒｍａｎｃｅｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍ
ｒｅｓｅａｒｃｈ，ｔｈｅｐｒｏｐｏｓｅｄＤＣＴａｌｇｏｒｉｔｈｍｐｒｏｖｉｄｅｓ
ａｎ
ｅｆｆｅｃｔｉｖｅ
ｓｃｈｅｍｅｆｏｒａｌｌｏｃａｔｉｎｇｔａｓｋｓｔｏ
ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ．Ｔｈｉｓａｌｇｏ—
ｒｉｔｈｍ
ｃａｎ
ｂｅ
ｅｍｐｌｏｙｅｄ
ｉｎ
ｍａｎｙ
ｔｙｐｉｃａｌ
ｐａｒａｌｌｅｌ
ａｌｇｏ“ｔｈｍｓ
万方数据
（周双娥，袁由光，熊兵周，欧中红．基于任务复制的处理器预分配算法．计算机学报，２００４，２７（２）：２１６—２２３）
［１２］
ＡｈｍａｄＩ，ＫｗｏｒｋＹＫ．Ｏｎｅｘｐｌｏｉｔｔａｓｋｄｕｐｌｉｃａｔｉｏｎ
ｉｎ
ｐａｒａｌｌｅｌ
ｐ西ｇｒａｍｓｃｈｅｄｕｌｉｎｇ．ＩＥＥＥ
Ｔｒａｎｓａｃｔｉｏｎｓｏｎ
Ｐａｒａｌｌｅｌａｎｄ
Ｄｉｓ—
ｔｒｉｂｕｔｅｄＳｙｓｔｅｍｓ，１９９８，９（９）：８７２—８９２
［１３］ＫｒｕａｔＭｃｈｃｅＢ，ＬｅｗｉｓＴ．Ｇｒａｉｎｓｉｚｅｄｅｔｅｒｍｉｎａｔｉｏｎｆｏｒｐａｒａ卜
ｌｅｌｐｒｏｃｅｓｓｉｎｇ．ＩＥＥＥＳｏｆｔｗａｒｅ，１９９８，１：２３—３２
ＳＵＮＳｈ卜ｘｊｎ，ｂｏｒｎｉｎ
１９４０，ｐｒｏｆｅｓｓｏｒ，Ｐｈ．Ｄ．ｓｕｐｅｒｖｉ—
ｓｏｒ．
Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｎｅｔｗｏｒｋｃｏｍｐｕｔｉｎｇ，ｐａｒ—
ａｌｌｅｌａｎｄ
ｄｉｓｔｒｉｂｕｔｅｄｃｏｍｐｕｔｉｎｇ，ｉｎｆｏｒｍａｔｉｏｎｃｏｍｐａｃｔｉｎｇｔｅｃｈｎｉｑｕｅ，
ｎｕｍｅｒｉｃａｌ
ｍｅｔｈｏｄｓ，
ｃｏｍｂｉｎａｔｏｒｉａｌ
ａｌｇｏｒｉｔｈｍ，
ｅｔＣ．
ｓｕｃｈ
ａｓ
ＦａｓｔＦｏｕｒｉｅｒ
Ｔｒａｎｓｆｏｒｍ（ＦＦＴ），ｍｅａｎａｎａｌｙｓｉｓＬＵ—
ｄｅｃｏｍｐｏｓｉｔｉｏｎ，Ｌａｐｌａｃｅｅｑｕａｔｉｏｎ．Ａｌｓｏ
ＤＣＴ
ａｌｇｏｒｉｔｈｍ
ｉｓ
ｓｕｉｔａｂｌｅｆｏｒｓｏｍｅｒｅｓｏｕｒｃｅ一１ｉｍｉｔｅｄｅｎｖｉｒｏｎｍｅｎｔ，ｆｏｒｅｘａｍ—ｔｈｅｅｍｂｅｄｄｅｄｒｅａｌ—ｔｉｍｅｄｉｓｔｒｉｂｕｔｅｄ
ｓｙｓｔｅｍ．
ｐｌｅ，ｆｏｒ