-
Sparse matrix-vector multiplication: Hypergraph
partitioning model exactly encodes the total communication volume requirement
into its objective function. Hence, hypergraph partitioning exactly corresponds
to minimizing total volume while maintaining computational load balance.
1D partitioning: Rowwise or columnwise partitioning of sparse
matrices are obtained through partitioning column-net or row-net
hypergraph representations of the matrices. See[1].
2D partitioning: Fine grain (on nonzero basis) and coarse grain
(checkerboard, jagged-like) decompositions of sparse matrices are obtained
using a fine-grain hypergraph model and multi-constraint partitioning
features. These yield substantially lesser communication volume than the
1D model, besides keeping total message count below some upper bounds.
See[2,3,4].
Partitioning for several objectives: Recently, PaToH is used
in a two-phase method to minimize total communication volume, total message
count, maximum volume per processor, and maximum message count per processor
while balancing computational loads of the processors through 1D partitioning
of sparse matrices. In the first phase, PaToH balances computational loads
of the processors and sets a lower bound on total communication volume.
In the second phase, the rest of the objectives are attacked while trying
to attain the lower bound on communication volume. The feature Partitioning
with fixed vertices is used in the second phase. See[5].
-
Sparse matrix ordering: Ordering sparse matrices
is a well studied problem. Although most of the previous solutions built
on graph models, it is possible to use hypergraph models.
Ordering rectangular matrices for parallel solution of LP problems:
PaToH is used to permute rectangular matrices into singly-bordered block
diagonal form with the objective of minimizing the border size and maintaining
balance on diagonal-block sizes. The border size is minimized through the
use of net-cut metric as an objective function while partitioning hypergraph
representation of matrices. See[4,6].
Ordering for matrix factorization: Some powerful fill-reducing
orderings of sparse matrices for factorization are obtained through nested-dissection
based on GPVS(Graph partitioning with vertex separators). Having modeled
GPVS as a hypergraph partitioning problem, high quality orderings are obtained
through using PaToH with net-cut metric. See[4].
-
VLSI design: PaToH has been used to partition
circuits. PaToH generates extremely good results on partitioning circuits
from the well-know ISPD98 benchmark. See PaToH's results on ISPD98 benchmark
compared to other partitioners at Umit
V. Catalyurek's page. A paper on this application of PaToH which also
discusses fine tunings is in progress.
-
Direct Volume Rendering: Parallel direct volume
rendering of unstructured grids requires image-space decomposition or
object-space decomposition. Although these two decompositions lead to
different rendering algorithms which has their own peculiarities,
PaToH has been used in both of the schemes to have efficient
renderings.
Image space decomposition: In this decomposition, having supplied
the necessary portions of the object to the processors, there does not
occur any communication. However, a high volume of communication can occur
in between different visualization instances during data-migration phase.
Two hypergraph models has been proposed. One of them models total communication
volume regardless of the current data-to-processor assignment and requires
an additional step to generate new screen region-to-processor assignment.
This model uses connectivity-1 metric of PaToH. The second
model uses fixed vertices to represent current data-to-processor assignment
and generates screen region-to-processor assignment during partitioning
with fixed vertices. See[7].
Object space decomposition: In this decomposition communication
occurs during ray-segment migration in a visualization instance and during
data migration in between different visualization instances. Two hypergraph
models, which exactly models the total volume of communication in these
two communication steps, is proposed. In the first model, total communication
volume during ray-segment migration phase is minimized using connectivity-1metric
in PaToH. The partitioning is used to guide a matching phase to minimize
total communication volume during data migration phase. The second hypergraph
model uses fixed vertices to minimize total communication volume in the
two communication phases. The connectivity-1 metric and partitioning
with fixed vertices features of PaToH are used. A paper on this subject
is in preparation.
Send yours to be popularized
here.