License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09061.19
URN: urn:nbn:de:0030-drops-20934
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2093/
|
Go to the corresponding Portal |
Gebremedhin, Assefaw H.
The Enabling Power of Graph Coloring Algorithms in Automatic Differentiation and Parallel Processing
Abstract
Combinatorial scientific computing (CSC) is founded
on the recognition of the enabling power of combinatorial algorithms
in scientific and engineering computation and in high-performance computing.
The domain of CSC extends beyond traditional scientific computing---the
three major branches of which are numerical linear algebra,
numerical solution of differential equations, and
numerical optimization---to include a range of emerging and
rapidly evolving computational and information science disciplines.
Orthogonally, CSC problems could also emanate from
infrastructural technologies for supporting high-performance computing.
Despite the apparent disparity in their origins,
CSC problems and scenarios are unified by the following common features:
(A) The overarching goal is often to make computation
efficient---by minimizing overall execution time, memory usage,
and/or storage space---or to facilitate knowledge discovery or analysis.
(B) Identifying the most accurate combinatorial abstractions that
help achieve this goal is usually a part of the challenge.
(C) The abstractions are often expressed, with advantage, as graph
or hypergraph problems.
(D) The identified combinatorial problems are typically NP-hard to
solve optimally. Thus, fast, often linear-time, approximation (or
heuristic) algorithms are the methods of choice.
(E) The combinatorial algorithms themselves often need to be
parallelized, to avoid their being bottlenecks within a larger
parallel computation.
(F) Implementing the algorithms and deploying them via software
toolkits is critical.
This talk attempts to illustrate the aforementioned features of CSC
through an example: we consider the enabling role graph coloring
models and their algorithms play in efficient computation of
sparse derivative matrices via automatic differentiation (AD).
The talk focuses on efforts being made on this topic within
the SciDAC Institute for Combinatorial Scientific Computing
and Petascale Simulations (CSCAPES).
Aiming at providing overview than details, we discuss
the various coloring models used in sparse Jacobian and Hessian computation,
the serial and parallel algorithms developed in CSCAPES
for solving the coloring problems, and a
case study that demonstrate the efficacy of the coloring techniques
in the context of an optimization problem in a Simulated Moving Bed process.
Implementations of our serial algorithms for the coloring
and related problems in derivative computation are assembled
and made publicly available in a package called ColPack.
Implementations of our parallel coloring algorithms are
incorporated into and deployed via the load-balancing toolkit Zoltan.
ColPack has been interfaced with ADOL-C, an operator overloading-based
AD tool that has recently acquired improved capabilities for
automatic detection of sparsity patterns of Jacobians and Hessians
(sparsity pattern detection is the first step in derivative matrix
computation via coloring-based compression).
Further information on ColPack and Zoltan is available
at their respective websites, which can be accessed via
http://www.cscapes.org
BibTeX - Entry
@InProceedings{gebremedhin:DagSemProc.09061.19,
author = {Gebremedhin, Assefaw H.},
title = {{The Enabling Power of Graph Coloring Algorithms in Automatic Differentiation and Parallel Processing}},
booktitle = {Combinatorial Scientific Computing},
pages = {1--3},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2009},
volume = {9061},
editor = {Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2009/2093},
URN = {urn:nbn:de:0030-drops-20934},
doi = {10.4230/DagSemProc.09061.19},
annote = {Keywords: Graph coloring, sparse derivative computation, automatic differentiation, parallel computing}
}
|
Keywords: |
|
Graph coloring, sparse derivative computation, automatic differentiation, parallel computing |
|
Collection: |
|
09061 - Combinatorial Scientific Computing |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
24.07.2009 |
