Empirical study of dynamic scheduling on rings of processors

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, 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, 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* outperforms policy 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.