An empirical study of dynamic scheduling on rings of processors

✍ Scribed by Miranda E. Barrows; Dawn E. Gregory; Lixin Gao; Arnold L. Rosenberg; Paul R. Cohen

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 479 KB
• Volume: 25
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(99)00039-3

✦ Synopsis

We empirically analyze and compare two low-overhead, deterministic policies for scheduling dynamically evolving tree-structured computations on rings of identical processing elements (PEs). Our computations have each task either halt or spawn two independent children and then halt; they abstract, for instance, computations generated by multigrid methods. Our simpler policy, KOSO KOSO, has each PE keep one child of a spawning task and pass the other to its clockwise neighbor in the ring; our more sophisticated policy, KO SO KOSO Ã , operates similarly, but allows child-passing only from a more heavily loaded PE to a more lightly loaded one. Both policies execute waiting tasks in increasing order of their depths in the evolving task-tree. Our study focuses on two conjectures: (a) Both policies yield good parallel speedup on large classes of the computations we study. (b) Policy KOSO KOSO Ã outperforms policy KOSO KOSO in many important situations. We verify these conjectures via a suite of experiments, supplemented by supporting mathematical analyses. We view our methodology of experimental design and analysis as a major component of our studyÕs contribution, which will prove useful in other such studies.