JOSTLE is a software package designed to partition unstructed meshes (for example, finite element or finite volume meshes) for use on distributed memory parallel computers. It can also be used to repartition and load-balance existing partitions (such as those deriving from adaptive refined meshes). It achieves this by modelling the mesh as an undirected graph and then using state-of-the-art graph partitioning techniques.
The code is extremely fast and provides high quality multilevel partitioning and diffusive load-balancing in both serial & parallel.
Since its first release in 1995, JOSTLE has gained a worldwide user community of around 150 licensed sites. Although some are no longer current, it has been licensed by groups based at Los Alamos, Argonne & Sandia National Labs (all in the USA), NASA, and in Universities across the world (specifically the USA, Canada, Brazil, Austria, Belgium, Czech Republic, Finland, France, Germany, Greece, Holland, Italy, Poland, Russia, Spain, Sweden, Switzerland, Turkey, Israel, Oman, India, Japan, Singapore & Taiwan).
JOSTLE has recently been commercialised and is available under the name of NetWorks.
You can find out more about the underlying algorithms from several papers; probably the best to start with are:
- overview paper
- C. Walshaw and M. Cross. JOSTLE: Parallel Multilevel Graph-Partitioning Software - An Overview. In F. Magoules, editor, Mesh Partitioning Techniques and Domain Decomposition Techniques, pages 27-58. Civil-Comp Ltd., 2007. (Invited chapter).
- dynamic partitioning & load balancing:
- C. Walshaw, M. Cross, and M. Everett. Parallel Dynamic Graph Partitioning for Adaptive Unstructured Meshes. J. Par. Dist. Comput., 47(2):102-108, 1997.
- parallel partitioning:
- C. Walshaw and M. Cross. Parallel Optimisation Algorithms for Multilevel Mesh Partitioning. Parallel Comput., 26(12):1635-1660, 2000.
- multiphase partitioning:
- C. Walshaw, M. Cross, and K. McManus. Multiphase Mesh Partitioning. Appl. Math. Modelling, 25(2):123-140, 2000.
- multilevel balancing:
- C. Walshaw and M. Cross. Mesh Partitioning: a Multilevel Balancing and Refinement Algorithm. SIAM J. Sci. Comput., 22(1):63-80, 2000.
- partitioning for optimising domain shape:
- C. Walshaw, M. Cross, R. Diekmann, and F. Schlimbach. Multilevel Mesh Partitioning for Optimising Domain Shape. Intl. J. High Performance Comput. Appl., 13(4):334-353, 1999.
- mapping to heterogeneous communication networks:
- C. Walshaw and M. Cross. Multilevel Mesh Partitioning for Heterogeneous Communication Networks. Future Generation Comput. Syst., 17(5):601-623, 2001.
- combined with evolutionary search to create extremely high quality partitions:
- A. J. Soper, C. Walshaw, and M. Cross. A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph Partitioning. J. Global Optimization, 29(2):225-241, 2004.
A full list of papers can be found on the publications page.
User guides are available for: