Zoltan-Tutorial-Paper

?Getting Started with Zoltan: a Short Tutorial1 1 1 2Karen D. Devine , Erik G. Boman , Lee Ann Riesen , Umit V. Catalyurek1Cedric Chevalier1 +Sandia National Laboratories , Scalable Algorithms DepartmentAlbuquerque, NM 87185-1318, USA{kddevin,egboman,lafisk,ccheval}@sandia.gov2Ohio State University, Biomedical Informatics DepartmentColumbus, OH 43210, USAumit@bmi.osu.eduAbstract. The Zoltan library is a toolkit of parallel combinatorial al-gorithms for unstructured and/or adaptive computations. In this paper,we describe the most signi cant tools in Zoltan: dynamic partitioning,graph coloring and ordering. We also describe how to obtain, build, anduse Zoltan in parallel applications.Keywords. Parallel Computing, Partitioning, Load Balancing, Color-ing, Ordering.1 IntroductionThe Zoltan library [1] is a toolkit of combinatorial algorithms for parallel, un-structured,and/oradaptivescienti capplications.Itsdata-structureneutralde-sign allows Zoltan to be used by a wide range of applications, including adaptive nite element methods, particle simulations, linear solvers and preconditioners,crash and contact detection, and electrical circuit simulations. Zoltan’s largestcomponent is a suite of dynamic load-balancing and partitioning algorithmsthat increase applications’ parallel performance by reducing processor idle time.Zoltan also has graph coloring and graph ordering algorithms useful in, e.g.,task schedulers, parallel preconditioners and linear ...