Fast Dynamic Load Balancing Tools for Extreme Scale Systems Parallel unstructured applications running on the latest petascale systems require partitions optimizing specific balance metrics. Methods combining the most powerful graph based and geometric methods with ParMA diffusive methods directly operating on an unstructured mesh are discussed. The SSE is focused on extending ParMA to support applications with relational structures that can be expressed with a graph structure. More Information: http://www.scorec.rpi.edu/parma Contact: Cameron Smith smithc11@rpi.edu and Mark Shephard shephard@rpi.edu Cameron W. Smith, Gerrett Diamond, and Mark S. Shephard Rensselaer Polytechnic Institute, USA ParMA: Partitioning using Mesh Adjacencies Guide partitioning decisions with mesh adjacency information • Mesh and partition model adjacencies represent application data more completely then standard (hyper)graph-partitioning models. • All mesh entities can be considered; (hyper)graph uses a subset of the adjacency information. • Complete mesh - O(1) time adjacency queries. Advantages • Avoid graph construction and directly account for multiple entity types important for the solve process • Easy to use with diffusive procedures – compliments other partition methods via incremental refinements Diffusive Approach • Iteratively migrate small sets of elements to (1) reduce the peak imbalance and (2) reduce the number of entities on the part boundaries. Diffusive Iteration Stages • Weight computation – compute weights and exchange with peers • Targeting – determined how much weight each peer can accept • Element selection – select elements for migration • Migration – move elements to peers Complete mesh adjacency structure. . Dynamic Partitioning of Unstructured Meshes Tools for re-partitioning an unstructured mesh due to changing work loads or communication patterns are required to: • Balance work, reduce communications, output distribution, execute in parallel quickly, use little memory, and provide API Common Methods • Graph, hypergraph, geometric diffusive, and local Examples will demonstrate that specific combinations are needed to reach really large part counts (> 500K). 1 - “Controlling Unstructured Mesh Partitions for Massively Parallel Simulations”, Min Zhou, et al., 2010 Geometric recursive inertial bisection Dual graph partition Mesh Example of partitioning methods. Global partitioning [1]. Local partitioning [1]. *** • *** *** • **** Partitioning to One Million Parts Multiple tools needed to maintain partition quality at scale [2] • Local and global topological and geometric methods via Zoltan and Zoltan2 integration ParMA quickly reduces large imbalances and improves part shape • 1.6B element mesh from 128K to 1M parts then running ParMA. 128K partition has less than 7% imbalance for all entity orders. • Global RIB – 103 seconds ParMA – 20 seconds 209% vtx imb reduced to 6%, perfect elm imb increased to 4%, and 5.5% reduction in avg vtx per part suspension upright Mira parameters: a = 10% b = 70% g = 64k *If memory is limited additional methods are available. • 12.9B element mesh from 128K (< 7% imb) to 1M parts then ParMA. • Local ParMETIS – 60 seconds. ParMA – 36 seconds 35% vtx imb reduced to 5%, 11% elm imb reduced to 5%, and 0.6% reduction in avg vtx Extending Application Support Goal • Support applications operating on graph-like structures. Three demonstrations: • Finite element unstructured mesh-based analysis • Hierarchic multi-scale for soft tissue modeling • Scale-free graphs for discrete event simulations Approach • Define N-graph abstraction to directly represent both graph and mesh relational structures: • defined as 𝐺" 𝑉, 𝐸&, 𝐸', … , 𝐸")' where: 𝑉: atomic units 𝑢+ of the domain Ω which uniquely exist on one part s.t. Ω = ∪∀+ 𝑢+, and 𝐸+: relations 𝑒+(𝑢, 𝑣) of type 𝑖between vertices 𝑢 and 𝑣where 𝑢, 𝑣 ∈𝑉and 𝑢 ≠𝑣. • Optionally, vertices and edges may be assigned associated weights 𝑤. • Implement EnGPar - N-Graph based v