Argonne National Laboratory

Evaluation of Hierarchical Mesh Reorderings

TitleEvaluation of Hierarchical Mesh Reorderings
Publication TypeConference Paper
Year of Publication2009
AuthorsStrout, MM, Osheim, N, Rostron, D, Hovland, PD, Pothen, A
Conference NameComputational Science, ICCS 2009
Date Published02/2009
PublisherSpringer Berlin/Heidelberg
Other NumbersANL/MCS-P1578-0209

Irregular and sparse scientific computing programs frequently experience performance losses because of inefficient use of the memory
system in most machines. Previous work has shown that, for a graph
model, performing a partitioning and then reordering within each partition (hierarchical reordering) improves performance. More recent work has shown that reordering heuristics based on a hypergraph model result in better reorderings than those based on a graph model. This paper studies the effects of hierarchical reordering strategies within the hypergraph model. In our experiments, the reorderings are applied to the nodes and elements of tetrahedral meshes, which are used as input to a mesh optimization application. This application includes computations such as loops over the elements in the mesh and sparse matrix multiplication based on the structure of the mesh. We show that cache performance degrades over time with consecutive packing, but not with breadth-first ordering, and that hierarchical reorderings involving hypergraph partitioning followed by consecutive packing or breadth-first orderings in each partition improve overall execution time.