Revisiting hypergraph models for sparse matrix partitioning

Bora Uçar

doi:10.1137/060662459

Revisiting hypergraph models for sparse matrix partitioning

2007-01-01

38

OA

AI

DOI：10.1137/060662459

原文链接

查看原文

摘要

En 中文

We provide an exposition of hypergraph models for parallelizing sparse matrix-vector multiplies. Our aim is to emphasize the expressive power of hypergraph models. First, we set forth an elementary hypergraph model for the parallel matrix-vector multiply based on one-dimensional (1D) matrix partitioning. In the elementary model, the vertices represent the data of a matrix-vector multiply, and the nets encode dependencies among the data. We then apply a recently proposed hypergraph transformation operation to devise models for 1D sparse matrix partitioning. The resulting 1D partitioning models are equivalent to the previously proposed computational hypergraph models and are not meant to be replacements for them. Nevertheless, the new models give us insights into the previous ones and help us explain a subtle requirement, known as the consistency condition, of hypergraph partitioning models. Later, we demonstrate the flexibility of the elementary model on a few 1D partitioning problems that are hard to solve using the previously proposed models. We also discuss extensions of the proposed elementary model to two-dimensional matrix partitioning.

Keyword:

parallel computing

sparse matrix-vector multiply

hypergraph models

Revisiting hypergraph models for sparse matrix partitioning

摘要

AI总结

期刊

机构

引用论文