Phase-based adaptive dynamic load balancing for parallel tree computation

Dynamic load balancing (DLB) is a technique for the parallel implementation of problems which generate unpredictable workloads by migrating work units to lightly loaded processors based on run-time workload measurement. Adaptive DLB is a refinement where aspects of the load balancing system itself are modified in the light of measured workloads. This thesis investigates phase-based adaptive DLB, a version of adaptive DLB in which a parallel computation moves through different load balancing phases identified on the basis of run-time workloads. The idea is explored through a case study of parallel tree computation, in which three distinct phases with intervening transitions are identified. Two major variants of phase-based adaptivity are distinguished. In parametric adaptivity, parameters of the DLB algorithm are adapted between phases; in algorithmic adaptivity, different DLB algorithms are utilised in each phase. These concepts are investigated quantitatively through a simulator for parametric adaptivity and discussed in detail for algorithmic adaptivity. The simulator permits a range of processor topologies, parameterises the performance of the underlying network, includes two different network performance models, and allows a wide range of simulated tree-structured workloads, parameterised by depth, fan-out, node granularity and imbalance. It was extensively validated in relation to the performance of two DLB algorithms on a 512-processor Cray T3D. The simulator was used to evaluate the benefit of parametric phase-based adaptivity. Preliminary experiments with non-adaptive algorithms revealed performance to be sensitive to the interval between load-balancing invocations, so this parameter was prioritised for subsequent adaptivity experiments. A performance metric called Improvement Through Adaptivity (ITA) was discussed. Two DLB algorithms were used as test cases; the well-established Generalised Dimension Exchange Method and a novel Loadserver algorithm, whose implementation is described in the thesis. Results were obtained for all combination of the transitions, and the relationships between ITA and various parameters (processor sizes, node granularity, tree imbalance and network performance) were established. Similar relationships were observed for both algorithms, though with some differences in detail. Positive values of ITA were obtained with both algorithms, for at least one transition combination, over a range of all the parameters. Thus, the potential benefits of phase-based parametric adaptivity are confirmed, justifying future work in implementing this technique.