On the complexity of list scheduling algorithms for distributed-memory systems

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.