Project Description

• Overview
• Design Considerations
  • Design of Toolkits and Libraries
  • Zoltan's Design
  • Zoltan Examples
• Dynamic Load-Balancing and Data Migration Tools
  • Typical Approach to Dynamic Load Balancing
  • Why Dynamic Load Balancing is Harder than Static Partitioning
  • Zoltan's Load-Balancing Suite
  • Data Migration Tools
• Communication Tools
  • Unstructured Communication Library
  • Distributed Data Directories
• Memory Management Tools

• A suite of parallel partitioning algorithms and data migration tools dynamically redistribute data to reflect, say, changing processor workloads.
• Distributed data directories and unstructured communication services let applications perform complication communication using only a few simple primitives.
• Dynamic memory management tools enhance common memory allocation functions to simplify debugging of dynamic memory usage.

For more detailed information, see [Hendrickson and Devine].

Support for data migration (the movement of data to establish a new decomposition) is also provided through a similar callback function interface. An application provides callback functions that pack object data into and unpack data from communication buffers provided by Zoltan. Zoltan calls the packing function to load communication buffers, performs the communication necessary to move the data, and calls the unpacking function to unload the communication buffers.

Several examples of Zoltan's use can be found in the Zoltan User's Guide.

• General examples of library usage.
• Specific examples for each phase of balancing (initialization, load balancing, and data migration).
• Examples of callback function implementations.

Many high-quality static partitioning tools exist; examples include Chaco, METIS, and SCOTCH. General-purpose dynamic load-balancing tools are less common, however, since they are more difficult to implement. The difficulty arises from fundamental algorithmic and software-engineering differences between static and dynamic partitioning. These differences are summarized in the following table.

Static Partitioning...	Dynamic Load Balancing...
Generally used as a pre-processor to an application.	Runs side-by-side with an application.
Can be (and usually is) implemented serially.	Must be implemented in parallel.
Has only modest concern for execution time.	Must run quickly (time to load balance should not exceed time to run in an unbalanced state).
Has only modest concern for memory usage.	Must use little memory (should not affect scalability of application).
Can use file-based interfaces (read geometry from a file; write partition info to a file).	Must use function-call interfaces.
Has no dependence on an application's data structures.	Needs information stored in an application's data structures.
Accounts for part sizes and communication costs.	Accounts for part sizes, communication costs, and data movement costs.

In our experience, no single partitioning strategy is effective for all parallel computations. Some application require partitions based only on the problem's workloads and geometry; others benefit from explicit consideration of dependencies between data. Some applications require the highest quality partitions possible, regardless of the cost to generate them; others can sacrifice some quality so long as new partitions can be generated quickly. For some applications, the cost to relocate data is prohibitively high, so incremental partitioning algorithms are needed; other applications can tolerate greater remapping costs. Most important, application developers might not know in advance which strategies work best in their applications, so the need a convenient means of comparing algorithms.

We provide two classes of parallel partitioning algorithms in the Zoltan library:

• Geometric methods

  Recursive Coordinate Bisection
  Recursive Inertial Bisection
  Hilbert Space-Filling Curve Partitioning
  Refinement Tree Partitioning

• Topology-based methods

  Hypergraph partitioning
  Graph partitioning
  Graph partitioning (through interfaces to ParMETIS (U. Minn.) and Jostle (U. Greenwich))
  

A complicated part of dynamic repartitioning is the need to move data from old processors to new ones. This data migration requires deletions and insertions from the application data structures as well as communication between the processors.

To help an application with data migration, Zoltan requires an application to supply callback functions that pack data into communication buffers and unpack data from communication buffers. Zoltan calls the packing function to load communication buffers with objects to be exported, performs all communication needed to move the data, and calls the unpacking function to load the objects in the data structures on the new processors. This mechanism eliminates the need for the application developer to implement complicated communication for data migration.

Unlike static applications, where communication patterns remain fixed throughout the computation, dynamic applications can have complicated, changing communication patterns. For example:

• After adaptive mesh refinement, new communication patterns must reflect dependencies between newly created elements.
• Multiphysics simulations, such as crash simulations, might require complicated communication to transfer data between decompositions for different simulation phases.

Dynamic applications often need to locate off-processor information. After repartitioning, for example, a processor might need to rebuild ghost cells and lists of data to be communicated. It might know which data it needs, but not where the data are located.

To help locate off-processor data, Zoltan includes a distributed data directory tool that is scalable with respect to both memory usage and computation time. Processors register their owned objects with the directory. Then, through a rendezvous algorithm, other processors can look up the location of data they need.

Dynamic applications rely heavily on the ability to allocate and free memory as needed. Memory leaks and invalid memory accesses are common to developing software. Although many software development tools let users track memory bugs, these tools are often not available on state-of-the-art parallel computers.

Zoltan's memory management package provides simple in-application debugging tools that are beneficial on state-of-the-art computing platforms. The package includes wrappers around malloc and free that record the location of all memory allocation operations. Thus, tracking memory leaks is simplified, as source-code locations of unfreed-memory allocations can be printed. Statistics about memory allocations and frees are also available.