Overhead Analysis of a Dynamic Load Balancing Library for Cluster Computing

This paper investigates the overhead of a dynamic load balancing library for large irregular data-parallel scientific applications on general-purpose clusters. The library is based on an integrated approach combining the advantages of novel dynamic loop scheduling strategies as data migration policies with the advances in resource management and task migration capabilities offered by a recently developed parallel runtime system. The paper focuses on the contribution of the runtime system software layer to the total overhead of the library. Experiments to compare the performance of two applications using the library, the Nbody simulations and the profiling of a quadrature routine, with the performance of the same applications using an MPI-only implementation of the dynamic scheduling techniques indicate only a slight decrease in performance due to the overhead of the runtime system software layer. The results validate the suitability of the runtime system as an implementation platform for dynamic load balancing schemes, and underscore the significance of using the integrated approach, as well as the benefits of using the library especially in cluster applications characterized by irregular and unpredictable behavior.