A TASK DUPLICATION BASED SCALABLE SCHEDULING ALGORITHM FOR DISTRIBUTED-MEMORY SYSTEMS

One of the major limitations of distributed memory systems (DMSs) is t he 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 (D AG) to obtain an optimal solution is a strong NP-hard problem, This pa per presents a scalable task duplication based scheduling (STDS) algor ithm which can schedule the tasks of a DAG onto the processors of a DM S with a worst case complexity of O(\V\(2)), where \V\ is the number o f nodes of the DAG, This algorithm generates an optimal schedule for D AGs provided a cost relationship is satisfied and if the required numb er of processors are available, The STDS algorithm generates a schedul e for the number of processors available in the system, The performanc e of the STDS algorithm has been observed by comparing the parallel ex ecution times for practical DAGs with the theoretical lowerbound. (C) 1997 Academic Press.