From 2003 to 2009, I was a graduate student at the University of Illinois
at Urbana-Champaign Department of Computer Science under the direction of
Michael Heath.
From 2003 to 2007, I was a
Department of Energy Computational Science Graduate Fellow.
My thesis was entitled "Hypergraph Based Combinatorial Optimization of Matrix-Vector Multiplication"
and dealt primarily with two Combinatorial Scientific Computing problems.
The unifying theme in the work was that for both problems I used graph and hypergraph
models to improve the performance of important numerical kernels.
Two-Dimensional Sparse Matrix Partitioning
2D Partition of
cage5
Matrix
 |
In work collaborating with Erik Boman at Sandia National Laboratories, we researched 2D
partitioning of sparse matrices in order to improve the parallel performance of sparse matrix
kernels such as matrix-vector multiplication.
Typically people use 1D methods for partitioning sparse matrices.
However, for certain problems these 1D partitions can result in high communication volumes in the
parallel computation.
In these cases, more general 2D methods are needed in order to obtain good parallel efficiency.
We developed two such 2D partitioning methods for sparse matrices.
One of our methods, the nested dissection partitioning method, has been shown to be one of the best
partitioning methods for sparse matrices from several application areas.
This new method is competitive with the traditional best 2D algorithm (fine-grain hypergraph method) in terms of communication volume,
but requires fewer messages and less time to obtain the partition.
The nested dissection method is particularly effective on structurally symmetric matrices,
where it is about as fast to compute as 1D methods and the communication volume is significantly reduced (up to 97%) compared to 1D layout.
The plan is for these new methods (as well as previously developed methods) to be integrated into
Isorropia,
so they will be readily available for
Trilinos users.
Optimization of Matrix-Vector Multiplication in Finite Element Assembly
Graph Model Example for Optimizing Matrix-Vector Multiplication
 |
In previous work, Kirby et al. showed that combinatorial optimization of matrix-vector multiplication
could lead to faster evaluation of finite element stiffness matrices.
Based on a graph model characterizing relationships between rows, an efficient set of operations
can be generated to perform matrix-vector multiplication for this problem.
In our work, we improved the graph model by extending the set of binary row
relationships and solved this combinatorial optimization problem optimally for the binary row relationships implemented, yielding significantly improved results over previous published graph
models.
We also extended the representation by using hypergraphs to model more complicated row relationships,
expressing a three-row relationship with a three-vertex hyperedge, for example.
Our initial greedy algorithm for this hypergraph model yielded significantly
better results than the graph model for many matrices.
Papers
Michael M. Wolf,
"Hypergraph-Based Combinatorial Optimization of Matrix-Vector Multiplication."
PhD thesis, University of Illinois at Urbana-Champaign, July 2009.
M.M. Wolf, E.G. Boman, and C. Chevalier,
"Improved Parallel Data Partitioning by Nested Dissection with Applications to Information Retrieval."
(In preparation.)
Michael M. Wolf and Michael T. Heath,
"Combinatorial Optimization of Matrix-Vector Multiplication in Finite Element Assembly,"
SIAM Journal on Scientific Computing, Volume 31, Issue 4, 2009, pp. 2960-2980.
(preprint)
Erik G. Boman and Michael M. Wolf,
"A Nested Dissection Approach to Sparse Matrix Partitioning."
(submitted paper.)
M. M. Wolf, E.G. Boman, and B. Hendrickson,
"Optimizing Parallel Sparse Matrix-Vector Multiplication by Corner Partitioning,"
PARA08, Trondheim, Norway, May 2008.
(preprint)
Michael M. Wolf and Erik G. Boman,
"Partitioning for Parallel Sparse Matrix-Vector Multiplication,"
SANDIA Technical Report SAND2007-7977, Sandia National Laboratories, 2007, pp. 75-86.
J. Ray, B. M. Adams, K. D. Devine, Y. M. Marzouk, M. M. Wolf, and H. N. Najm,
"Distributed Micro-Releases of Bioterror Pathogens: Threat Characterizations and Epidemiology
from Uncertain Patient Observables,"
SANDIA Technical Report SAND2008-6044, Sandia National Laboratories.
|
Michael M. Wolf — Postdoc
Contact
mmwolf@sandia.gov
(505) 284-9963
Mailing Address
Sandia National Labs
CSRI/155
P.O. Box 5800
Albuquerque, NM 87185-1320
|
