Algorithms for Parallel Computing

Effective use of large parallel computers depends upon the availability of scalable parallel algorithms and implementations. Sandia has a long history of research and development activity in this area, with a focus on algorithms to enable parallel science and engineering simulations. While the research activities have been spread across a number of application areas, many of the fruits of these efforts can be found in the Zoltan tool for parallel data management.

The Zoltan toolkit is used for dynamic load balancing and data migration in the Sandia code CHISELS, a feature-scale modeler for semiconductor surface growth. The computational grid is refined around the deposition surface (shown as a red line). Zoltan's Recursive Coordinate Bisection algorithm generates partitions (indicated by the colored regions) that equally distribute grid cells to processors while maintaining geometric locality of objects in processors. (Image courtesy of Steve Plimpton and Larry Musson.)

Graph-based decomposition		Geometric decomposition
Data transfer between two differing decompositions or meshes is a key component of many applications, including multiphase and multiphysics simulations. We have developed efficient algorithms and easy-to-use utilities for data transfer and unstructured communication. Here data is transferred between a graph-based decomposition (used for finite element computation) and a geometric decomposition (used for contact detection) in a parallel crash simulation code. (Images courtesy of Steve Attaway, et al.)

Areas of Research:

• Chaco: Graph Partitioning and Static Load Balancing
  (Contact: Bruce A. Hendrickson)
• The NEOS-SRN Optimization Server
  (Contact: Willliam E. Hart)
• Zoltan: Dynamic Load Balancing and Support for Parallel Applications
  (Contact: Karen D. Devine)

Program Contact: Suzanne L. K. Rountree

 
Return to Top of the Page

Newsnotes | Info and Events (internal - SNL only) | Open-Source Software Downloads | Privacy and Security
Sandia National Laboratories Home Page - External or Internal (SNL only)

Maintained by: Bernadette M. Watts
Modified on: May 6, 2008