Performance Evaluation of Scheduling Precedence-Constained Computations on Message-Passing Systems
Performance Evaluation of Scheduling Precedence-Constained Computations on Message-Passing Systems
复制标题
消息传递系统上调度优先级约束计算的性能评估
DOI：
10.1109/71.334905
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Adel Al
中科院分区：
文献类型：
--
作者：
M. Al;Adel Al
利用计算、通信和多处理器拓扑的知识，提出了一类基于全局优先级的调度启发式算法——广义链表调度。任务优先级定义为使用最佳局部启发式算法在多处理器上反向调度计算后的任务完成时间。GLS调度包括在正向、图驱动调度中使用任务优先级。局部（ETF）和GLS启发式的评估通过改变通信、并行性和系统拓扑来实现。分析表明，局部启发式算法依赖于局部最大化效率，只有当并行度大到足以覆盖通信时才给出可接受的解（有界加速）。与并行性、通信和网络拓扑变化相比，GLS调度优于本地方法。GLS启发式算法的时间复杂度为O(pn/sup 2/)，其中p为处理器数，n为任务数。>
Using knowledge on computation, communication, and multiprocessor topology, a class of global priority-based scheduling heuristics, called generalized list scheduling (GLS) is proposed. Task-priority is defined as the completion time of the task following backward scheduling the computation over the multiprocessor by using the best local heuristic. GLS scheduling consists of using the task-priority in forward, graph-driven scheduling. Evaluation of local (ETF) and GLS heuristics is carried out by altering over the communication, parallelism, and system topology. Analysis shows that local heuristics rely on locally maximizing the efficiency and gives acceptable solutions only when the parallelism is large enough to cover the communication (bounded speedup). GLS scheduling outperforms the local approaches versus change in parallelism, communication, and network topology. The time complexity of GLS heuristics is O(pn/sup 2/), where p and n are the number of processors and that of the tasks, respectively. >