We study partitioning to parallelize multiplication of one or more dense vectors by a sparse matrix (SpMV or SpMM). We consider contiguous partitions, where the rows (or columns) of the matrix are split into K parts without reordering. We present exact and approximate contiguous partitioning algorithms that minimize the runtime of the longest-running processor under cost models that combine work factors and hypergraph communication factors . This differs from traditional graph or hypergraph partitioning models which minimize total communication under a work balance constraint. We address regimes where partitions of the row space and column space are expected to match (the symmetric case) or are allowed to differ (the nonsymmetric case) . Our algorithms use linear space. Our exact algorithm runs in linear time when K^2 is sublinear. Our (1 + \epsilon)-approximate algorithm runs in linear time when K\log( /(c_{low}\epsilon)) is O(N^C) for C < } 1  and c_{low} are upper and lower bounds on the optimal cost. We also propose a simpler version of our (1 + \epsilon)-approximate algorithm which runs in a factor of \log(c_{high}} / \epsilon) is sublinear. We\epsilon)) from linear time, but is faster in practice. We empirically demonstrate that all of our algorithms efficiently produce high-quality contiguous partitions. We } combine concepts from high-performance computing and computational geometry. Existing load balancing algorithms optimize a linear model of per-processor work. We make minor adaptations to optimize arbitrary nonuniform monotonic increasing or decreasing cost functions which may be expensive to evaluate. We then show that evaluating our model of communication is equivalent to planar dominance counting. We specialize Chazelle's dominance counting algorithm to points in the bounded integer plane and generalize it to trade reduced construction time for increased query time, since our partitioners make very few queries. Our algorithms split the original row (or column) ordering into parts to optimize diverse cost models. Combined with reordering or embedding techniques, our algorithms might be used to build more general heuristic partitioners, as they can optimally round one-dimensional embeddings of direct K-way noncontiguous partitioning problems .
We study partitioning to parallelize multiplication of one or more dense vectors by a sparse matrix (SpMV or SpMM). We consider contiguous partitions, where the rows (or columns) of a sparse matrix with N nonzeros are split into K parts without reordering. We propose exact and approximate algorithms to produce contiguous partitions minimizing the maximum runtime of any processor under a diverse family of cost models that combine work and hypergraph communication terms in symmetric or asymmetric settings . This differs from traditional partitioning models which minimize total communication , or from traditional load balancing models which only balance work. One can view our algorithms as optimally rounding one-dimensional embeddings of direct K-way noncontiguous partitioning problems . Our algorithms use linear space. Our exact algorithm runs in linear time when K^2 is O(N^C) for C < 1. Our (1 + \epsilon)-approximate algorithm runs in linear time when K\log( c_{high/(c_{low}\epsilon)) is O(N^C) for C < } 1 , where c_{high and c_{low} are upper and lower bounds on the optimal cost. We also propose a simpler version of our (1 + \epsilon)-approximate algorithm which runs in a factor of \log(c_{high}} / (c_{low\epsilon)) from linear time, but is faster in practice. We empirically demonstrate that all of our algorithms efficiently produce high-quality contiguous partitions. We } combine concepts from high-performance computing and computational geometry. We extend existing load balancing algorithms to optimize arbitrary nonuniform monotonic increasing or decreasing cost functions . We reduce evaluation of our communication model to planar dominance counting. We specialize Chazelle's dominance counting algorithm to points in the bounded integer plane and generalize it to trade reduced construction time for increased query time, resulting in an overall linear runtime .
R
the matrix
a sparse matrix with N nonzeros
R
present
propose
R
contiguous partitioning algorithms that minimize the runtime of the longest-running processor under
algorithms to produce contiguous partitions minimizing the maximum runtime of any processor under a diverse family of
D
factors
R
factors
terms in symmetric or asymmetric settings
D
graph or hypergraph
R
under a work balance constraint. We address regimes where partitions of the row space and column space are expected to match (the symmetric case) or are allowed to differ (the nonsymmetric case)
, or from traditional load balancing models which only balance work. One can view our algorithms as optimally rounding one-dimensional embeddings of direct K-way noncontiguous partitioning problems
R
sublinear.
O(N^C) for C < 1.
A
c_{high
A
, where c_{high
R
\epsilon) is sublinear. We
(c_{low
R
Existing
We extend existing
D
optimize a linear model of per-processor work. We make minor adaptations
R
which may be expensive to evaluate. We then show that evaluating our model of communication is equivalent
. We reduce evaluation of our communication model
R
since our partitioners make very few queries. Our algorithms split the original row (or column) ordering into parts to optimize diverse cost models. Combined with reordering or embedding techniques, our algorithms might be used to build more general heuristic partitioners, as they can optimally round one-dimensional embeddings of direct K-way noncontiguous partitioning problems
resulting in an overall linear runtime