Executive Summary
The R&D component of the mission of CSCAPES is to help contribute to the
overarching SciDAC mission by
developing infrastructural algorithmic and software
technologies to support high-performance computing.
The scope of CSCAPES encompasses four areas:
load-balancing--the task of distributing data and work
in a large-scale computation among the processors of a machine to
minimize total execution time--and related parallelization toolkits;
automatic differentiation (AD), a technology for
transforming computer source code for computing a function into code
for computing its derivatives;
basic ingredients in sparse linear solver technology; and
runtime data and iteration reordering to improve
performance in irregular computation.
The focus in CSCAPES in each of these areas is on the formulation
(modeling) and solution (algorithms) of the underlying fundamental
combinatorial problems. These problems are often expressed using graphs or
hypergraphs:
-
Load-balancing in parallel computation can be phrased as a partitioning
problem on a graph, or with more accuracy, on a hypergraph.
-
When computational dependency among subtasks is modeled using a graph, a
distance-1 vertex coloring of the graph can be used to determine a
scheduling of the tasks for concurrent computation. Distance-2 vertex coloring and
several other specialized coloring variants are used to model matrix
partitioning problems that arise in the efficient computation of
sparse Jacobians and Hessians using AD. Data migration tasks in parallel processing
can be modeled using various kinds of edge colorings in graphs.
-
In AD, exploitation of
associativity and commutativity in the chain rule of differential
calculus leads to a variety of vertex or edge elimination
problems in
the directed acyclic graph used to represent the computation of a
function and its derivative.
-
Various types of matchings in graphs are
used in the solution of sparse linear systems (numerical preprocessing
and block triangular decomposition) and in the coarsening phase of
multilevel methods for graph partitioning.
-
Work and storage reduction in
direct solvers for large sparse systems calls for vertex ordering
problems in graphs.
Graph and hypergraph based models are used to
capture the needs in reordering the nodes and elements within an
unstructured mesh to improve runtime performance.
Figure 1 (The Philosophy behind CSCAPES):
This diagram shows the relationship between a typical computational science
and engineering (CSE) application and the key combinatorial problems
for which CSCAPES is developing algorithms and
software. An arrow from A to B indicates that A in some sense uses B;
some horizontal relationships are not shown.
The second row of the figure shows a subset of the scientific computing (SC) tools
needed in the solution of a typical CSE application.
When the solution is carried out on a parallel computer,
the application as well as the SC tools themselves,
involve a variety of high-performance computing tasks (shown in the third third row).
The fundamental combinatorial problems that underlie these tools and tasks are shown
in the fourth row.
Click here for a larger picture .
The diagram in Figure 1 shows how these combinatorial problems,
for which CSCAPES researchers are developing algorithms and software,
are related to
a typical computational science and engineering (CSE) application.
A typical CSE application may require a sequence of numerical optimization problems to be solved,
eigenvalues and eigenvectors to be computed, nonlinear and linear systems of equations to be solved,
and/or derivatives of multivariate functions to be evaluated. Scientific computing (SC) tools for many of
these problems often invoke each other: for example, an optimization tool may need to use an AD tool
or a linear solver, and an eigensolver may call a linear solver or an AD tool.
When the CSE application is solved on a parallel computer with several thousands of processors,
both the application and the SC tools it relies on critically depend on the availability of
high-performance computing (HPC) capabilities such as those for load-balancing, scheduling computational
tasks, and data migration as well as on techniques for improving single processor performance.
As discussed earlier, these HPC tasks in turn rely on the existence of efficient and scalable
algorithms for a variety of combinatorial problems.
CSCAPES is engaged in researching, developing, implementing, and deploying such algorithms.
The load-balancing and parallelization capabilities in CSCAPES are
being deployed through the Sandia-housed Zoltan software toolkit.
Similarly, the AD capabilities are being deployed via the tools
being developed at Argonne within the OpenAD framework. In addition,
serial as well as parallel codes (for coloring, matching, and
re-ordering) are being separately developed at the academic
institutions within CSCAPES, with the ultimate goal of being
integrated with the major software outlets, Zoltan and OpenAD. Both
Zoltan and the tools in OpenAD pre-date CSCAPES and have been under
continuous development for several years with sustained support from
DOE; similarly, the coloring work in CSCAPES was previously supported
by NSF.
For more information on each constituent project within
CSCAPES, click on Projects in the left menu at the top of this page.
Additional overview documents
Here are a select few additional documents that provide more detailed overviews (in various degrees)
of the research activities in the CSCAPES Institute.
For further reading,
click on the menu items Publications and Presentations.