Parallel Distance-k Coloring Algorithms
for Numerical Optimization
Abstract.
Matrix partitioning problems that arise
in the efficient estimation of
sparse Jacobians and Hessians can be modeled using variants of graph
coloring problems. In a
previous work, we argue that distance-2 and
distance-3/2 graph coloring are robust and
flexible
formulations of the respective matrix estimation problems. The problem
size
in large-scale optimization contexts makes the matrix estimation phase
an
expensive part of the entire
computation both in terms of execution time and memory space. Hence,
there is a need for both
shared- and distributed-memory parallel algorithms for the stated graph
coloring problems. In the
current work, we present the first practical shared address space
parallel
algorithms for these problems. The main idea in our algorithms is to
randomly partition the vertex
set equally among the
available processors, let each processor speculatively color its vertices
using information
about already colored vertices, detect eventual conflicts in parallel,
and
finally re-color conflicting vertices sequentially. Randomization is also used in the
coloring phases to further
reduce conflicts. Our PRAM-analysis shows that the algorithms should
give almost linear speedup for
sparse graphs that are large
relative to the number of processors. Experimental results from our
OpenMP implementations on a
Cray Origin2000 using various large graphs show that the algorithms
indeed yield reasonable
speedup for modest numbers of
processors.
Full paper in PDF
|
|