| 主权项 |
一种基于任务复制的多复本容错并行任务调度方法，包括如下步骤：(1)确定任务优先级；采用以关键路径构建优先级队列的方法来确定任务的属性优先级，关键路径指从开始任务到结束任务间具有最大计算开销与通信开销的路径；将任务节点分为三类：关键路径上的节点称为CPN节点；有路径到达CPN节点的节点称为IBN节点；不能到达CPN节点的节点称为OBN节点，所述三类节点的优先级顺序是CPN〉IBN〉OBN；(2)预调度：首先根据关键路径构造任务优先级队列，假定处理器数量无限，每轮调度加入f+1个空处理器，首先利用多复本任务复制函数MST_AR()计算任务t<sub>i</sub>在当前所有处理器上的最早开始时间优化值EST(t<sub>i</sub>,p<sub>j</sub>)，p<sub>j</sub>为处理器编号，通过计算选择空处理器和不选择空处理器两种情况下的最早开始时间的差值来获得最早开始时间优化值OPT(t<sub>i</sub>)，然后选择EST(t<sub>i</sub>,p<sub>j</sub>)值最小的f+1个处理器预放置t<sub>i</sub>的f+1个复本，以<t<sub>i</sub>,OPT(t<sub>i</sub>)>的格式记录最早开始时间优化值；其中，1≤j≤m；1≤i≤n，m为DAG图的任务数目；n为系统中实际的处理器数目；(3)重调度：首先按照最早开始时间优化值排序，然后统计任务t<sub>i</sub>在最早开始时间优化值集合中出现的次数z(t<sub>i</sub>)，然后每轮调度加入z(t<sub>i</sub>)个空处理器，调用MST_AR()函数计算任务t<sub>i</sub>在当前所有处理器上的最早开始时间EST(t<sub>i</sub>,p<sub>j</sub>)，选择开始时间最早的f+1个处理器来放置任务t<sub>i</sub>的所有复本，从而完成任务调度。 |
