A COMPARISON OF LIST SCHEDULING HEURISTICS FOR COMMUNICATION INTENSIVE TASK GRAPHS
BENJAMIN S. MACEY AND ALBERT Y. ZOM · Cybernetics & Systems · 1997
List-based priority schedulers have long been the dominant class of static scheduling algorithms. Such heuristics have been predominantly based on the ''critical path, most immediate successors first'' CP MISF priority. The ability of this type of scheduler to handle increased levels of communication overhead is examined in this paper. Three of the more popular list scheduling heuristics, Hu's LSH and Kruatrachue's ISH and DSH, are subjected to a performance-based comparison, with results demonstrating their inadequacies in communication-intensive cases. WINSCHED, a Microsoft Windows tool developed by the Parallel Computing Research Laboratory, is also briefly presented. WINSCHED uses a number of list-based heuristics to schedule a parallel program represented as an enhanced directed acyclic graph EDAG on an arbitrary number of homogeneous parallel processors. It supports six distinct heuristics with or without consideration of communication costs and has six interconnection topologies built in.