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.