Zoltan Home Page

Zoltan User's Guide

Frequently Asked Questions

Zoltan Project Description

Papers and Presentations

How to Cite Zoltan

Download Zoltan

Report a Zoltan Bug

Contact Zoltan Developers

Sandia Privacy and Security Notice

Zoltan:
Parallel Partitioning, Load Balancing and Data-Management Services

### The Zoltan Team

Sandia National Laboratories Erik Boman Karen Devine Vitus Leung Sivasankaran Rajamanickam Michael Wolf | Georgia Tech Umit Catalyurek

### Past Zoltan Contributors

Sandia National Laboratories: Cédric Chevalier (currently at CEA, DAM) Robert Heaphy Bruce Hendrickson Matthew St. John Lee Ann Riesen Courtenay Vaughan | Siena College James Teresco

National Institute of Standards and Technology William F. Mitchell | Rensselaer Polytechnic Institute Jamal Faik Luis Gervasio
Google (formerly Ohio State University) Doruk Bozdag

Tutorials:

- "Getting Started with Zoltan: A Short Tutorial."
  A ten-page introduction to using Zoltan is now available. Download it here:
  PDF Citation (BIBTEX) Viewgraphs from the tutorial (PDF)
- The Zoltan Tutorial presented at the 2010 ACTS Workshop is available here.
  - Zoltan Tutorial Slides from ACTS 2010 (PDF)

- The Zoltan Tutorial presented at SciDAC2007 is now on-line. Download it here:
  - Zoltan Tutorial Slides (14 Mbytes; PDF)
  - Zoltan Tutorial Handouts (Four slides per page; 8.8 Mbytes; PDF)

- User's Guide (HTML)

Zoltan News:

- Zoltan v3.83 was released in January 2016 as part of Trilinos v12.6. This release includes only minor software changes. See more details below.
- Zoltan v3.82 was released in May 2015 as part of Trilinos v12. This release includes only minor software changes. See more details below.
- Zoltan v3.81 was released in November 2014 as part of Trilinos v11.12. This release upgrades Zoltan's interface to ParMETIS v4 and Scotch v6. See more details below.
- Zoltan v3.8 was released in October 2013 as part of Trilinos v10.11. This release uses Trilinos' BSD license! See more details below.
- Zoltan v3.6 was released in September 2011 as part of Trilinos v10.8. This release includes new recoloring capability in Zoltan's coloring algorithms. Zoltan's hierarchical partitioning algorithm was also updated for greater efficiency. We have updated our third-party library support to include PT-Scotch versions up to 5.1.12 and ParMETIS v3.1 and v4.0.
- Zoltan v3.5 was released in March 2011. This release differs from the Trilinos 10.6 release by including the following features:
  - Fix in Fortran90 interface that causes compilation and run-time problems with gcc 4.5 and later when compiler optimization is enabled.
  - Support for 64-bit builds of Zoltan, enabling operation on more than 2B objects. See details for building in the Zoltan User's Guide.
  - Faster graph builds for very specific input types. See parameter GRAPH_BUILD_TYPE.
- The Zoltan team received the "Best Algorithms Paper Award" at the 2007 International Parallel and Distributed Processing Symposium (IPDPS07) for their paper "Hypergraph-based Dynamic Load Balancing for Adaptive Scientific Computations."
  Abstract (HTML) Paper (PDF) Citation (BIBTEX)

- Zoltan was part of several funded DOE SciDAC projects:
  - SciDAC2 CSCAPES: Combinatorial Scientific Computing and Petascale Simulations
    Contact: Erik Boman
  - SciDAC2 ITAPS: Interoperable Technologies for Advanced Petascale Simulations
    Contact: Karen Devine
  - SciDAC3 to SciDAC5: FASTMath: Frameworks, algorithms and scalable technologies for mathematics
    Contact: Karen Devine

Now available: Zoltan 3.83

New Features in Zoltan v3.83, released January 2016. Release Notes | Backward Compatibility

- Autotools files updated to avoid deprecated perl features
- Added Zoltan_Get_Fn interface to return pointers to registered callback functions.
- Several bug fixes in Fortran90 interface
- Subtle rounding error fixed in PHG hypergraph partitioner
- Minor changes to distributed data directory to track number of nodes per processor; include file DD.h is now named zoltan_dd_const.h

New Features in Zoltan v3.82, released May 2015. Release Notes | Backward Compatibility

- Minor code changes to remove compiler warnings and handle error conditions
- Enable "make -j" in autotools build of Zoltan's F90 interface.

New Features in Zoltan v3.81, released November 2014: Release Notes | Backward Compatibility

- Better integration of ParMETIS v4, METIS v5, and Scotch v6.
- Better handling of interface differences between MPI versions 1 and 2.
- Bug fix in siMPI for non-MPI builds.
- Minor bugfixes.

New Features in Zoltan v3.8, released October 2013: Release Notes | Backward Compatibility

- Zoltan is now released under Trilinos' BSD license.
- Added an improved hash function that speeds lookups, particularly for apps using partitioning parameter RETURN_LISTS=PARTS.
- Added fixes for integer overflows that occur when A and B are valid integers, but A*B overflows an integer.
- Removed support for OCT partitioning; use HSFC partitioning for similar decompositions.
- Removed support for third-party library DRUM.
- Removed support for the Zoltan v1.x interface.

New Features in Zoltan v3.6, released September 2011: Release Notes | Backward Compatibility

- Recoloring capability in Zoltan's coloring algorithms, obtaining colorings with fewer colors.
- Support for graph partitioning and ordering with PT-Scotch up to version 5.1.12.
- Support for graph partitioning and ordering with ParMETIS v3.1 and v4.0.
- Improved hierarchical partitioning performance.
- Deprecation of OCT methods and interface defined in lbi_const.h. See the backward compatibility notes for more info.

New Features in Zoltan v3.5, released March 2011: Release Notes | Backward Compatibility

- Fix in Fortran90 interface that causes compilation and run-time problems with gcc 4.5 and later when compiler optimization is enabled.
- Support for 64-bit builds of Zoltan, enabling operation on more than 2B objects. See details for building in the Zoltan User's Guide.
- Faster graph builds for very specific input types. See parameter GRAPH_BUILD_TYPE.

New Features in Zoltan v3.3, released July 2010: Release Notes | Backward Compatibility

- New local ordering method based on space-filling curves to improve memory and cache locality within a processor.
- Ability to call graph partitioning algorithms using hypergraph callback functions; this capability is useful applications with, say, block-structured matrix distributions (e.g., SuperLU), where all information about a matrix row or column is not available on a single processor.
- Improved execution time of parallel hypergraph partitioning.

New Features in Zoltan v3.2, released September 2009: Release Notes | Backward Compatibility

- New interface to Scotch and PT-Scotch parallel graph partitioning algorithms.
- Simplified interface to graph ordering and coloring algorithms
- Automated symmetrization of graphs for graph partitioning, coloring and ordering. (See parameters GRAPH_SYMMETRIZE and GRAPH_SYM_WEIGHT in the Scotch and ParMETIS graph packages.)
- Improved function Zoltan_LB_Eval returns more information about a decomposition to users.
- Improved examples showing Zoltan usage in C and C++ are included in zoltan/example.
- Improved support for builds under autotools, including builds of Zoltan's F90 interface.
- New support for CMake builds and testing through Trilinos; builds of Zoltan's F90 interface are included.
- Improved integration into Isorropia partitioners for Trilinos' Epetra classes.

New Features in Zoltan v3.1, released September 2008:

- Graph/Matrix ordering interface to PT-Scotch, a high-quality graph ordering and partitioning library from LaBRI/INRIA-Bordeaux.
- New matrix ordering interface that returns ordering information such as permutations and separators to the application.
- New hypergraph partitioning options for inexpensively refining partitions.
- Robustness improvements to Zoltan's parallel hypergraph partitioner and repartitioner.
- New Autotools build environment.
- Tight integration with the Trilinos project, including Trilinos package Isorropia, a matrix-based interface to Zoltan.
- Serial, non-MPI builds are now available.

New Features in Zoltan 3.0, released May 2007:

- Parallel Hypergraph Repartitioning and Dynamic Load Balancing to partition data while accounting for current processor assignments, thus reducing the amount of data migration needed; see the Zoltan User's Guide for details.
- Hypergraph refinement to quickly improve the quality of an existing partition.
- Hypergraph Partitioning and Repartitioning with Fixed Vertices allows users to specify the partition assignment of objects.
- Native graph partitioning using Zoltan's hypergraph partitioner.
- Hierarchical partitioning for hybrid partitions on heterogeneous computers.
- Improved part remapping to reduce data migration costs.
- Simple block and random partitioners for demonstration and testing.

New Features in Zoltan 2:

- Parallel Hypergraph Partitioning
- Distance-1 and Distance-2 graph coloring
- Multicriteria Geometric Partitioning
- C++ Interface

See the release notes for descriptions of new functionality and more.

- Release Notes
- Backward Compatibility
- Download Now!

The Zoltan Library provides critical data-management services to a wide range of parallel applications. Zoltan includes many utilities needed by unstructured and/or adaptive parallel applications. These utilities include

- a suite of dynamic load-balancing and parallel partitioning tools that distribute data over sets of processors,
- data migration tools that simplify movement of data to new parts,
- parallel graph/matrix ordering algorithms for fill-reducing matrix ordering, including interfaces to PT-Scotch (LaBRI/INRIA-Bordeaux) and ParMETIS (U. Minnesota),
- parallel graph coloring including distance-1 and distance-2 coloring,
- distributed data directories that efficiently locate off-processor data,
- an unstructured communication package that greatly simplifies interprocessor communication, and
- a dynamic memory debugging package for memory-debugging on state-of-the-art parallel computers.

Zoltan's object-oriented interface is easy-to-use and enables Zoltan to be used by a number of different applications. Zoltan is designed to be flexible and extensible, so different algorithms can be used, compared and added easily.

Why Zoltan is needed:

- In some applications, work loads and/or geometric locality change as computations proceed;
  Zoltan provides dynamic redistribution of data to maintain high performance.

- Adaptive finite element methods
- Particle methods
- Contact detection algorithms
- Multiphysics simulations
- Adaptive physics models

- Processors need to track off-processor data's locations in dynamic environments; Zoltan's distributed data directories allow applications to efficiently query and update off-processor data locations.
- Unstructured and adaptive applications require complicated interprocessor communication; Zoltan's unstructured communication package manages sends and receives for application developers.
- State-of-the-art parallel computers often do not have sophisticated debugging tools available; Zoltan's dynamic memory management package simplifies location of memory leaks and other memory errors.

Advantages of using Zoltan in applications:

- Zoltan's object-oriented interface is clean and easy to use in applications.
- A suite of load-balancing algorithms is included in Zoltan;
  try them all to see what works best in your application.
- Interfaces to the popular ParMETIS and Jostle packages are included.
- Application development time can be reduced by using Zoltan's parallel utilities for unstructured communication, dynamic memory management, data migration, and distributed data directories.

Advantages of using Zoltan for developing new algorithms:

- New algorithms can be added to Zoltan in a straightforward manner.
- Zoltan's object-based interface provides a simple, general way to get needed application data to the algorithms.
- New algorithms can be compared to high-quality implementations of existing algorithms.
- Zoltan's data-structure neutral design allows new algorithms to be used easily in many different applications.

Zoltan philosophy and project description:

- Overview
- Design Considerations
- Dynamic Load-Balancing and Data Migration Tools
- Communication Tools
- Memory Management Tools

Related links:

- Publications

- Papers and Presentations

- Serial hypergraph partitioners

- PaToH (Georgia Tech)
- Mondriaan (Utrecht University)
- hMetis (University of Minnesota)

- Parallel hypergraph partitioners

- Parkway (Imperial College, London)

- Parallel and dynamic partitioners

- ParMETIS (University of Minnesota)
- Jostle (University of Greenwich)
- DRAMA (ESPRIT IV)

- Serial graph partitioners

- Chaco (Sandia National Laboratories)
- METIS (University of Minnesota)
- Party (University of Paderborn)
- SCOTCH (Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux I)

- Sandia National Laboratories

- Sandia's Computation, Computers and Math Center
- Sandia's Computer Science Research Institute

Copyright (c) 2000-2013, Sandia National Laboratories.
See the README file in the main Zoltan directory for information on Zoltan licensing.