A Task Duplication Based Scalable Scheduling Algorithm for Distributed Memory Systems
A Task Duplication Based Scalable Scheduling Algorithm for Distributed Memory Systems
复制标题
一种基于任务复制的分布式存储系统可扩展调度算法
DOI：
10.1006/jpdc.1997.1376
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
D. Agrawal
中科院分区：
文献类型：
--
作者：
S. Darbha;D. Agrawal
分布式存储系统（DMS）的主要限制之一是处理器间通信的高成本，这可以通过具有有效的任务划分和调度算法来最小化。众所周知，调度有向无环图（DAG）的任务以获得最优解是一个强NP-难问题。本文提出了一种基于可扩展任务复制的调度算法（STDS），该算法能够将DAG的任务调度到DMS的处理器上，最坏情况下的复杂度为O（|V| 2），其中|V|是DAG的节点数。该算法生成一个最优的时间表DAG提供的成本关系是满意的，如果所需数量的处理器可用。STDS算法为系统中可用的处理器数量生成一个调度表。通过将实际DAG的并行执行时间与理论下限进行比较，观察了STDS算法的性能。
One of the major limitations of distributed memory systems (DMSs) is the high cost for interprocessor communication, which can be minimized by having an efficient task partitioning and scheduling algorithm. It is well known that scheduling the tasks of a directed acyclic graph (DAG) to obtain an optimal solution is a strong NP-hard problem. This paper presents a scalable task duplication based scheduling (STDS) algorithm which can schedule the tasks of a DAG onto the processors of a DMS with a worst case complexity ofO(|V|2), where |V| is the number of nodes of the DAG. This algorithm generates an optimal schedule for DAGs provided a cost relationship is satisfied and if the required number of processors are available. The STDS algorithm generates a schedule for the number of processors available in the system. The performance of the STDS algorithm has been observed by comparing the parallel execution times for practical DAGs with the theoretical lowerbound.