An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems
An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems
复制标题
DOI：
10.1109/tpds.2003.1206502
复制
发表时间：
2003-06-01
影响因子：
5.3
通讯作者：
Singh, K
中科院分区：
文献类型：
--
作者：
Bansal, S;Kumar, P;Singh, K
在并行和分布式计算系统中，优先约束任务图的调度问题是最具挑战性的NP完全问题之一。一般来说，对于细粒度任务图和具有高通信延迟的网络，复制算法更有效。然而，现有的复制算法大多是在全连接处理器无限可用性的假设下设计的，且复杂度较高。低复杂度的最佳复制算法在任务图的成本和/或形状参数受限的情况下工作。此外，所需的处理器数量与任务图的大小成比例地显著增长。提出了一种改进的复制策略，适用于任意任务图，与有限数量的互连约束的处理器。与大多数其他算法，复制一个给定的任务的所有可能的父母/祖先，所提出的算法往往会避免冗余的重复和重复的节点选择性，只有当它有助于提高性能。这导致较低的重复以及较低的时间和空间复杂性。模拟结果团和互连约束的网络拓扑结构与随机和定期基准任务图套件，代表了各种并行数值应用。性能，在规范化的时间表长度和效率方面，与一些著名的和最近提出的算法进行比较。建议的算法是最有效的，因为它产生更好的或可比的时间表，显着更少的处理器消耗。
Scheduling precedence constrained task graphs, with or without duplication, is one of the most challenging NP-complete problems in parallel and distributed computing systems. Duplication heuristics are more effective, in general, for fine grain tasks graphs and for networks with high communication latencies. However, most of the available duplication algorithms are designed under the assumption of unbounded availability of fully connected processors, and lie in high complexity range. Low complexity optimal duplication algorithms work under restricted cost and/or shape parameters for the task graphs. Further, the required number of processors grows in proportion to the task-graph size significantly. An improved duplication strategy is proposed that works for arbitrary task graphs, with a limited number of interconnection-constrained processors. Unlike most other algorithms that replicate all possible parents/ancestors of a given task, the proposed algorithm tends to avoid redundant duplications and duplicates the nodes selectively, only if it helps in improving the performance. This results in lower duplications and also lower time and space complexity. Simulation results are presented for clique and an interconnection-constrained network topology with random and regular benchmark task graph suites, representing a variety of parallel numerical applications. Performance, in terms of normalized schedule length and efficiency, is compared with some of the well-known and recently proposed algorithms. The suggested algorithm turns out to be most efficient, as it generates better or comparable schedules with remarkably less processor consumption.