A task duplication based scalable scheduling algorithm for distributed memory systems

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 of O(\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. (C) 1997 Academic Press.