• Algorithmic Load Balancing (Tuesday 3:30-5:00PM)
    Room A108/110/112
    Chair: Hugh Caffey, SUN

    • Title: Large Scale Parallel Structured AMR Calculations Using the SAMRAI Framework
    • Authors:
      Andrew M. Wissink (Lawrence Livermore National Lab)
      Richard D. Hornung (Lawrence Livermore National Lab)
      Scott R. Kohn (Lawrence Livermore National Lab)
      Steve S. Smith (Lawrence Livermore National Lab)
      Noah Elliott (Lawrence Livermore National Lab)
    • Abstract:
      This paper discusses the design and performance of the parallel data communication infrastructure in SAMRAI, a software framework for structured adaptive mesh refinement (SAMR) multi-physics applications. We describe requirements of such applications and how SAMRAI abstractions manage complex data communication operations found in them. Parallel performance is characterized for two adaptive problems solving hyperbolic conservation laws on up to 512 processors of the IBM ASCI Blue Pacific system. Results reveal good scaling for numerical and data communication operations but poorer scaling in adaptive meshing and communication schedule construction phases of the calculations. We analyze the costs of these different operations, addressing key concerns for scaling SAMR computations to large numbers of processors, and discuss potential changes to improve our current implementation.

    • Title: Parallel Interval-Newton Using Message Passing: Dynamic Load Balancing Strategies
    • Authors:
      Chao-Yang Gau (University of Notre Dame)
      Mark A. Stadtherr (University of Notre Dame)
    • Abstract:
      Branch-and-prune and branch-and-bound techniques are commonly used for intelligent search in finding all solutions, or the optimal solution, within a space of interest. The corresponding binary tree structure provides a natural parallelism allowing concurrent evaluation of subproblems using parallel computing technology. Of special interest here are techniques derived from interval analysis, in particular an interval-Newton/generalized-bisection procedure. In this context, we discuss issues of load balancing and work scheduling that arise in the implementation of parallel interval-Newton on a cluster of workstations using message passing, and describe and analyze techniques for this purpose. Results using an asynchronous diffusive load balancing strategy show that a consistently high efficiency can be achieved in solving nonlinear equations, providing excellent scalability, especially with the use of a two-dimensional torus virtual network. The effectiveness of the approach used, especially in connection with a novel stack management scheme, is also demonstrated in the consistent superlinear speedups observed in performing global optimization.   

    • Title: Dynamic Load Balancing of SAMR Applications on Distributed Systems
    • Authors:
      Zhiling Lan (Northwestern University)
      Valerie E. Taylor (Northwestern University)
      Greg Bryan (Massachusetts Institute of Technology)
      Best Student Paper Finalist
    • Abstract:
      Dynamic load balancing(DLB) for parallel systems has been studied extensively; however, DLB for distributed systems is relatively new. To efficiently utilize computing resources provided by distributed systems, an underlying DLB scheme must address both heterogeneous and dynamic features of distributed systems. In this paper, we propose a DLB scheme for Structured Adaptive Mesh Refinement(SAMR) applications on distributed system s. While the proposed scheme can take into consideration (1) the heterogeneity of processors and (2) the heterogeneity and dynamic load of the networks, the focus of this paper is on the latter. The load-balancing processes are divided into two phases: global load balancing and local load balancing. We also provide a heuristic method to evaluate the computational gain and redistribution cost for global redistribution. Experiments show that by using our distributed DLB scheme, the execution time can be reduced by 9%-46% as compared to using parallel DLB scheme which does not consider the heterogeneous and dynamic features of distributed systems.