CSE Seminar

SPEAKER: Rebecca Hartman-Baker, Oak Ridge National Laboratory

TITLE: Load Distribution in MADNESS

DATE: Monday, August 6, 2007
TIME: 12:00 Noon
PLACE: 2240 DCL
1304 W. Springfield Ave., Urbana, IL

ABSTRACT

MADNESS (Multiresolution Adaptive Numerical Environment for Scientific Simulation) is an environment for prototyping and developing scientific applications using multiresolution analysis and low separation rank methods. MADNESS is being developed to perform well on leadership computing resources, with the goal of solving problems on a larger scale than ever before. In order to use these resources effectively, computational work must be optimally distributed across thousands or even tens of thousands of processes, making the implementation of effective load balancing techniques a crucial piece of the development effort.

In this talk, I discuss my work on load balancing in MADNESS. Computational work in MADNESS takes the form of an octree with multiwavelet coefficients at each node, so many traditional load balancing techniques, designed for finite element domain decomposition or particle simulations, do not work well. We instead propose the melding algorithm, a recursive process in which leaf children are assimilated into their parent and then a depth-first partitioning of the tree is performed, resulting in an array of choices for distributing the octree across the machine. I discuss the motivation for developing the melding algorithm, describe the method and how it works, including ways to determine which configuration is best based on the target machine, and discuss its theoretical advantages over alternative load balancing techniques. Finally, I present preliminary results of using the melding algorithm on ORNL's Jaguar Cray XT4 machine.