On the complexity of list scheduling algorithms for distributed-memory systems
Andrei Rădulescu, Arjan J. C. van Gemund · 1999
This paper presents a novel heuristic, called Fast Critical Path (FCP), intended as a compile-time scheduling algorithm on a distributed-memory system.While similar to existing list scheduling algorithms, FCP has two important differences: (a) it does not sort all the tasks at the beginning but maintains only a limited number of tasks sorted at any given time, and (b) instead of considering all processors as possible target for a given task, the choice is restricted to either the processor from which the last messages to the given task arrives or the processor which becomes idle the earliest.As a result, the time complexity is drastically reduced to O(V log (P) + E), where V and E are the number of tasks and edges in the task graph, respectively, and P is the number of processors.We demonstrate through theory and experiments that FCP performs equally to existing list scheduling algorithms of much higher complexity. *This research is part of the Automap