Publications

Siefert, Christopher S.; Tuminaro, Raymond S.; Bochev, Pavel B.; Boman, Erik G.; Devine, Karen D.

Abstract not provided.

Boman, Erik G.; Devine, Karen D.

Abstract not provided.

Journal of Physics: Conference Series

Boman, Erik G.; Devine, Karen D.

Abstract not provided.

SciDAC Review

Boman, Erik G.; Devine, Karen D.; Hendrickson, Bruce A.

Abstract not provided.

Devine, Karen D.; Boman, Erik G.; Riesen, Lee A.

Abstract not provided.

Devine, Karen D.

Abstract not provided.

Boman, Erik G.; Devine, Karen D.; Heaphy, Robert T.; Riesen, Lee A.

Abstract not provided.

Adams, Brian M.; Devine, Karen D.; Ray, Jaideep R.

Abstract not provided.

Boman, Erik G.; Devine, Karen D.

Abstract not provided.

Boman, Erik G.; Devine, Karen D.; Riesen, Lee A.; Heaphy, Robert T.; Hendrickson, Bruce A.; Vaughan, Courtenay T.

Abstract not provided.

Devine, Karen D.; Boman, Erik G.; Heaphy, Robert T.

Abstract not provided.

Boman, Erik G.; Devine, Karen D.; Heaphy, Robert T.; Hendrickson, Bruce A.

Graph partitioning is often used for load balancing in parallel computing, but it is known that hypergraph partitioning has several advantages. First, hypergraphs more accurately model communication volume, and second, they are more expressive and can better represent nonsymmetric problems. Hypergraph partitioning is particularly suited to parallel sparse matrix-vector multiplication, a common kernel in scientific computing. We present a parallel software package for hypergraph (and sparse matrix) partitioning developed at Sandia National Labs. The algorithm is a variation on multilevel partitioning. Our parallel implementation is novel in that it uses a two-dimensional data distribution among processors. We present empirical results that show our parallel implementation achieves good speedup on several large problems (up to 33 million nonzeros) with up to 64 processors on a Linux cluster.

Devine, Karen D.

Abstract not provided.

Proposed for publication in the IEEE Transactions on Parallel and Distributed Systems.

Devine, Karen D.

We address the problem of partitioning and dynamic load balancing on clusters with heterogeneous hardware resources. We propose DRUM, a model that encapsulates hardware resources and their interconnection topology. DRUM provides monitoring facilities for dynamic evaluation of communication, memory, and processing capabilities. Heterogeneity is quantified by merging the information from the monitors to produce a scalar number called 'power.' This power allows DRUM to be used easily by existing load-balancing procedures such as those in the Zoltan Toolkit while placing minimal burden on application programmers. We demonstrate the use of DRUM to guide load balancing in the adaptive solution of a Laplace equation on a heterogeneous cluster. We observed a significant reduction in execution time compared to traditional methods.

Boman, Erik G.; Devine, Karen D.; Heaphy, Robert T.

Abstract not provided.

Devine, Karen D.; Boman, Erik G.; Heaphy, Robert T.; Hendrickson, Bruce A.

Abstract not provided.

Proposed for publication in Journal of Computational Physics.

Shadid, John N.; Tuminaro, Raymond S.; Devine, Karen D.; Hennigan, Gary L.; Lin, Paul L.

Abstract not provided.

Devine, Karen D.; Boman, Erik G.; Devine, Karen D.; Heaphy, Robert T.; Hendrickson, Bruce A.; Heroux, Michael A.

We have developed infrastructure, utilities and partitioning methods to improve data partitioning in linear solvers and preconditioners. Our efforts included incorporation of data repartitioning capabilities from the Zoltan toolkit into the Trilinos solver framework, (allowing dynamic repartitioning of Trilinos matrices); implementation of efficient distributed data directories and unstructured communication utilities in Zoltan and Trilinos; development of a new multi-constraint geometric partitioning algorithm (which can generate one decomposition that is good with respect to multiple criteria); and research into hypergraph partitioning algorithms (which provide up to 56% reduction of communication volume compared to graph partitioning for a number of emerging applications). This report includes descriptions of the infrastructure and algorithms developed, along with results demonstrating the effectiveness of our approaches.

Devine, Karen D.; Hendrickson, Bruce A.; Boman, Erik G.; Vaughan, Courtenay T.

The design of general-purpose dynamic load-balancing tools for parallel applications is more challenging than the design of static partitioning tools. Both algorithmic and software engineering issues arise. The authors have addressed many of these issues in the design of the Zoltan dynamic load-balancing library. Zoltan has an object-oriented interface that makes it easy to use and provides separation between the application and the load-balancing algorithms. It contains a suite of dynamic load-balancing algorithms, including both geometric and graph-based algorithms. Its design makes it valuable both as a partitioning tool for a variety of applications and as a research test-bed for new algorithmic development. In this paper, the authors describe Zoltan's design and demonstrate its use in an unstructured-mesh finite element application.