Optimally bipartitioning sparsematrices with reordering and parallelization

摘要

A good task-to-processor assignment is crucial for parallel efficiency since the communicationbetween the tasks is usually themain bottleneck for scalability. A fundamental approach to solvethis problem is modeling the tasks as a hypergraph where the pins correspond to the tasks andthe nets represent the communication among them. The vertices in this hypergraph is partitionedinto a number of parts, which correspond to processors, in a way that the total number of verticesfor each part is balanced and the amount of edges having endpoints in different parts isminimized. Sparse matrix-vectormultiplication is an extensively used kernel inmany applications.Recently, a novel, purely combinatorial branch-and-bound–based approach has been proposedfor sparse-matrix bipartitioning which can handle hypergraphs that cannot be optimally partitionedby using existing methods due to the problem's complexity.Our work extends the previousstudywith three ideas.We use 1) matrix ordering techniques to usemore information in the earlierbranchesofthetree, 2) amachine learning approach to choose anorderingbasedonthematrixfeatures,and3) a parallelization technique tosearch anoptimal bipartitioning.Asour experimentsshow, these techniques make the bipartitioning process significantly faster.