Task scheduling algorithms for distributed memory systems
Sekhar Darbha, Dharma Prakash Agrawal · 1995
Distributed memory systems (DMSs) are being widely used because they provide several advantages. The main advantage of a DMS is the scalability which lets extra processors to be added easily onto the existing system. But, a major limitation of the DMSs is the high inter-processor communication cost. This problem can be overcome by having efficient task partitioning and scheduling algorithms. The problem of scheduling tasks onto DMSs for obtaining an optimal schedule is known to be NP-Complete. This work, presents two scheduling algorithms which execute in polynomial time and provide an optimal solution for a class of Directed Acyclic Graphs (DAGs) in case adequate processors are available. The first algorithm is the Search and Duplication Based Scheduling (SDBS) algorithm, which assumes that unbounded number of processors are available. The SDBS algorithm has been modified to take into account the variations in the number of processors. The second algorithm, namely the Scalable Task Duplication based Scheduling (STDS) algorithm is a superset of SDBS algorithm. It is scalable and can generate a schedule for any number of processors in the system. Both these algorithms generate the schedule with a worst case complexity of $O(V\sp2),$ where V is the number of nodes of the DAG. The performance of both the algorithms has been examined for several cases and the application of the algorithms on several practical DAGs has been reported.