# Presentation: 280173

## Technologies for Computational Science

- Boyana Norris
- Argonne National Laboratory
- http://www.mcs.anl.gov/~norris

## Outline

- Automatic differentiation
- Applications in optimization
- How AD works
- Components for scientific computing
- Performance evaluation and modeling
- Bringing it all together

- March 15, 2005

## What is automatic differentiation?

**	**Automatic Differentiation (AD): a technology for automatically augmenting computer programs, including arbitrarily complex simulations, with statements for the computation of derivatives, also known as sensitivities.

**The Computational Differentiation Project **
**at Argonne National Laboratory**

- March 15, 2005

## What is it good for?

- The need to accurately and efficiently compute derivatives of complicated simulation codes arises regularly in
- Optimization (finding a minimum)
- Solving nonlinear differential equations
- Sensitivity and uncertainty analysis
- Inverse Problems, including:
- Data assimilation
- Parameter identification
- AD tools automate the generation of derivative code without precluding the exploitation of high-level knowledge.

- March 15, 2005

## Sensitivity Analysis

- MM5 (a mesoscale weather model, NCAR and Penn State)

- Impact of perturbations of initial temperature on temperature in the system; low-amplitude supersonic waves clearly visible with AD (left), but not visible with divided difference approximations of derivatives (right).

- March 15, 2005

**Notes:**
The MM5 code is a mesoscale weather model developed by NCAR and Penn State. An ADIFOR-generated sensitivity-enhanced version of the code was used to explore the impact of perturbations of initial temperature on temperature in the system. The accuracy of automatic differentiation clearly shows low-amplitude supersonic waves in the system (left), which are not visible with divided difference approximations of derivatives (right).

## Parameter Tuning

- Sea Ice Model (Todd Arbetter, University of Colorado)

- Ice thickness for the standard (left) and tuned (right) parameter values, with actual observations at two locations indicated.

- March 15, 2005

**Notes:**
Although several of the parameters in sea ice models are known with very little precision, tuning of these parameters is often done in an ad hoc manner, proceeding until "acceptable" agreement with observations has been achieved.  We are examining whether the tuning process can be made more effective and automatic through the use of AD and optimization.  We applied AD to a sea ice model provided by Todd Arbetter of the University of Colorado and tuned it using the L-BFGS-B optimization software, minimizing the difference from observed ice velocities.  In addition to improving the agreement with observed ice velocities, the tuned parameters also provide excellent agreement
with observed ice thicknesses.  The figure shows ice thicknesses for the standard (left) and tuned (right) parameter values, with actual observations at two locations indicated.

## Often we look for extreme, or optimum, values that a function has on a given domain.  More formally:

Unconstrained minimization problems are ones in which 

Note: Since a maximum of f is a minimum of -f, we need only to look for the minimum. 

- Often we look for extreme, or optimum, values that a function has on a given domain.  More formally:
- Unconstrained minimization problems are ones in which
- Note: Since a maximum of *f *is a minimum of -*f*, we need only to look for the minimum.

- Optimization Problems

- March 15, 2005

## Newton’s Method

-  For optimization, we want f(x*) = 0, so iterate:

** **

- March 15, 2005

## Example: Minimum Surface

- Objective:
- Find a surface with the minimal area that satisfies Dirichlet boundary conditions and is constrained to lie above a solid plate.

**Solution**

**Error**

- March 15, 2005

**Notes:**
We are researching the integration of AD with the Toolkit for Advanced Optimization (TAO).  Currently, ADIC is being used to compute gradients and Hessians for several example problems.  The image, generated using the ALICE Differencing Engine, shows a sequence of solutions and their deviation from the optimal solution for a bound constrained minimization problem.  The objective is the surface with the minimal area that satisfies Dirichlet boundary conditions and is constrained to lie above a solid plate.

## Example: Minimum Surface (Cont.)

- March 15, 2005

**Notes:**
We are researching the integration of AD with the Toolkit for Advanced Optimization (TAO).  Currently, ADIC is being used to compute gradients and Hessians for several example problems.  The image, generated using the ALICE Differencing Engine, shows a sequence of solutions and their deviation from the optimal solution for a bound constrained minimization problem.  The objective is the surface with the minimal area that satisfies Dirichlet boundary conditions and is constrained to lie above a solid plate.

## We can compute derivatives via:

- Analytic code
- By hand
- Automatic differentiation
- Numerical approximation: finite differencing (FD). For finite differences, recall:

- March 15, 2005

## Why use AD?

- Compared with other methods (numerical differentiation via finite differences, hand coding, etc.), AD offers a number of advantages:
- Accuracy
- Performance
- Reduced effort
- Algorithm-awareness

- March 15, 2005

## More accurate derivatives = faster convergence

- Application: modeling transonic flow over an ONERA M6 airplane wing.

- March 15, 2005

**Notes:**
Application: modeling transonic flow over an ONERA M6 airplane wing.
Using AD and PETSc to solve the steady-state, three-dimensional compressible Euler equations on mapped, structured meshes using a second-order, Roes-type, finite-volume discretization. 

## Who uses it?

- AD has been successfully employed in applications in:
- Atmospheric chemistry
- Breast cancer modeling
- Computational fluid dynamics
- Mesoscale climate modeling
- Network Enabled Optimization System
- Semiconductor device modeling
- And also: groundwater remediation, multidisciplinary design optimization, reactor engineering, super-conductor simulation, multibody simulations, molecular dynamics simulations, power system analysis, water reservoir simulation, and storm modeling.

- March 15, 2005

## How AD Works

- Every programming language provides a limited number of elementary mathematical functions, e.g., +, -, *, /, sin, cos,...
- Thus, every function computed by a program may be viewed as the composition of these so-called intrinsic functions
- Derivatives for the intrinsic functions are known and can be combined using the chain rule of differential calculus

- March 15, 2005

## A Simple Example (Fortran)

- x = 3.14159265/4.0
- a = sin(x)
- b = cos(x)
- t = a/b

_**Differentiated program**_
- x = 3.14159265/4.0
- dxdx = 1.0 ! Initialize “seed matrix”
- a = sin(x)
- dadx = cos(x)*dxdx ! TL/CR
- b = cos(x)
- dbdx = -sin(x)*dxdx ! TL/CR
- t = a/b
- dtda = 1.0/b ! TL
- dtdb = -a/(b*b) ! TL
- dtdx = dtda*dadx + dtdb*dbdx ! CR

**Original program**

- March 15, 2005

## Modes of AD

- Forward mode
- Mode used in simple example
- Propagates derivative vectors, often denoted u or g_u
- Derivative vector u contains derivatives of u with respect to independent variables
- Time and storage proportional to vector length (# indeps)
- Reverse (or adjoint) mode
- Propagates adjoints, denoted ū or u_bar
- Adjoint ū contains derivatives of dependent variables with respect to u
- Propagation starts with dependent variables—must reverse flow of computation
- Time proportional to adjoint vector length (# dependents)
- Storage proportional to number of operations
- Because of this limitation, often applied to subprograms

- March 15, 2005

## Another Simple Example (C code) 

**DERIV_val(y):**  value of program
- 	                variable y
**DERIV_grad(y):**derivative  object
-                               associated with y

- Original code:** ****y = x1*x2*x3*x4;**

- March 15, 2005

**Notes:**
The forward mode:
Associate a gradient with every program variable (of type double) and apply the rules of differential calculus. 
The computation of p directional derivatives requires gradients of length p, therefore, many vector linear combinations of length p, e.g., grad(x) = (0,0,...,1,...0) leads to grad(t) = dt/dx(1:p).

The reverse (adjoint) mode:

Associate an “adjoint” alpha with every program variable and apply the following rule to the inverted program:
s = f(v,w) _v += ds/dv* _s; 
	_w += ds/dw* _s; 

1st step: Reversible program: single assignment form
2nd step: Adjoint computation

## The AD Process

**Application**
**Code**

**AD**
**Tool**

**Code with **
**Derivatives**

**Control**
**Files**

**Derivative**
**Program**

**Compile**
**& Link**

**User’s**
**Derivative**
**Driver**

**AD**
**Support**
**Libraries**

- March 15, 2005

## Ways of Implementing AD

- Operator Overloading
- Use language features to generate trace (“tape”) of computation -> implicit computational graph
- Easy to implement; hard to optimize
- Examples: ADOL-C
- Source Transformation (ST)
- Relies on compiler technology
- Hard to implement; more powerful
- Examples: ADIFOR, ADIC, ODYSSEE, TAMC

- March 15, 2005

## Example AD Tool Architecture (ST)

- AD engine isolated front- and backends via XAIF (XML AD Interface Format)
- XML representation of the computational graph
- Unifies “relevant” Fortran and C constructs
- Implements abstractions, e.g. “derivative object”
- Shared “plug-in” differentiation modules

- March 15, 2005

## XAIF Representation

- XAIF Representation

- March 15, 2005

## XAIF - Abstraction of the Program at  “AD-Level”: Expression Example

- Only the core structure of the program is reflected in XAIF:
- Control flow
- Variable information for *active *variables
- Basic blocks
-  Expression DAGs

- +

- *

- var_2

- var_3

- const

- var_1

- =

- March 15, 2005

## Estimates of Incremental Computational Costs

- March 15, 2005

## Hessian Module

- The Hessian module can compute H, H*V, V^T*H*V, W^T*H*V, as well as arbitrary elements of the Hessian (e.g., diagonal,  *n* predetermined entries).
- Tradeoffs in code generation between source expansion and speed. Hessian/Function Ratio:

- March 15, 2005

## Techniques for Improving Performance of AD Code

- Exploit sparsity (SparsLinC and/or coloring)
- Exploit parallelism
- data: stripmine derivative computation
- task: multithread independent loops
- time: break computation into phases; pipeline derivative computations
- Exploit interface contractions
- For computations of the form
- Compute dg/dx, df/dg, multiply to form df/dx
- Exploit mathematics (e.g., differentiating through linear/nonlinear equation solvers)

- March 15, 2005

## ANL Tools for AD

- ADIFOR was developed in collaboration with Rice University
- full support for Fortran 77
- support for parallelism via MPI and PVM
- support for sparse Jacobians
- ADIC is the first & only compiler-based AD tool for ANSI C
- support for the complete ANSI standard
- will soon support a large subset of C++
- _[www.mcs.anl.gov/adic](http://www.mcs.anl.gov/adic)_, _[www.mcs.anl.gov/adicserver](http://www.mcs.anl.gov/adicserver)_
- XAIF specification and differentiation modules (OpenAD project)
- _[http://www-unix.mcs.anl.gov/~utke/OpenAD](http://www-unix.mcs.anl.gov/~utke/OpenAD)_

- March 15, 2005

## AD in Numerical Toolkits

- NEOS Network-Enabled Optimization Server
- _[http://neos.mcs.anl.gov](http://neos.mcs.anl.gov/)_
- Efficient computation of gradients for large problems, where the objective function has the form
- PETSc (Portable Extensible Toolkit for Scientific Computation) solvers (work in progress)
- User only needs to provide the sequential “subdomain update” function in F77 or ANSI-C.
- _[Differentiated version of toolkit](file:///D:/Home/powerpoint/llnl99.ppt#XAIF  Representation)_ enables optimization/sensitivity analysis of models based on PETSc
- _[www.mcs.anl.gov/petsc](http://www.mcs.anl.gov/petsc)_

- March 15, 2005

## Optimization Solution (PETSc & TAO)

- Main Routine

- Nonlinear Solvers (SNES)

- Gradient
- Evaluation

- March 15, 2005

## Using AD with the Toolkit for Advanced Optimization (TAO)

**Parallel Hessian**
** ****assembly**

**G****lobal-to-local **
**scatter of ghost  values**

**Parallel function**
**assembly**

**Local Function **
**computation**

**G****lobal-to-local **
**scatter of ghost  values**

**Local Hessian**
**computation**

**Local Min.Function**
**computation**

**ADIFOR or ADIC**

**Local Hessian**
**computation**

**Script file**

**Coded manually; can be automated**

**Seed matrix **
**initialization**

- March 15, 2005

## Outline

- Automatic differentiation
**Components for scientific computing**
- Introduction
- Example applications
- Performance evaluation and modeling
- Summary

**CCA**

**Common Component Architecture**

- March 15, 2005

## Software development approaches

- Libraries: collections of subroutines

- Object-oriented libraries: collections of classes

- Components

- Architectures

- Unstructured code (everything in main)

- March 15, 2005

## Components

- Working definition: a component is a piece of software that can be *composed* with other components within a framework; composition can be either static (at link time) or dynamic (at run time)
- “plug-and-play” model for building applications
- For more info: C. Szyperski, *Component Software: Beyond Object-Oriented Programming*, ACM Press, New York, 1998
- Components enable
- Software and tool interoperability
- Automation of performance instrumentation/monitoring
- Application adaptivity (automated or user-guided)
- _[Pictorial intro](file:///../cca/tutorial/talks/pictorial-intro.ppt)_

- March 15, 2005

## Object-oriented vs component-oriented development

- Component-oriented development can be viewed as augmenting OOD with certain policies, e.g., require that certain abstract interfaces be implemented
- Components, once compiled, require a special execution environment
- OO techniques are useful for building individual components by relatively small teams; component technologies facilitate sharing of code developed by different groups by addressing issues in
- Language interoperability
- Via interface definition language (IDL)
- Well-defined abstract interfaces
- Enable “plug-and-play”
- Dynamic composability
- Components can discover information about their environment (e.g., interface discovery) from framework and connected components
- Can convert from an object orientation to a component orientation
- Automatic tools can help with conversion (ongoing work by C. Rasmussen and M. Sottile, LANL)

- March 15, 2005

## Motivating scientific applications

- Discretization

- Parallel I/O

- Meshes

- Data Redistribution

- Physics

- Optimization

- Derivative Computation

- Adaptive Solution

- Astrophysics

- Molecular
- structures

- Aerodynamics

- Fusion

- March 15, 2005

## Motivation: For Application Developers and Users

- You have difficulty managing multiple third-party libraries in your code
- You (want to) use more than two languages in your application
- Your code is long-lived and different pieces evolve at different rates
- You want to be able to swap competing implementations of the same idea and test without modifying any of your code
- You want to compose your application with some other(s) that weren’t originally designed to be combined

- March 15, 2005

## The model for scientific component programming

**CCA**

- March 15, 2005

**Notes:**
So here’s where research begins.

We know how computing started

We know how science went to SPMD programming

And we know how industry went to component programming.

What happens when you merge the two???

## CCA Delivers Performance

**Local**
- No CCA overhead within components
- Small overhead between components
- Small overhead for language interoperability
- Be aware of costs & design with them in mind
- Small costs, easily amortized
**Parallel**
- No CCA overhead on parallel computing
- Use your favorite parallel programming model
- Supports SPMD and MPMD approaches
**Distributed (remote)**
- No CCA overhead – performance depends on networks, protocols
- CCA frameworks support OGSA/Grid Services/Web Services and other approaches

- March 15, 2005

## Overhead from Component Invocation

- Invoke a component with different arguments
- Array
- Complex
- Double Complex
- Compare with f77 method invocation
- Environment
- 500 MHz Pentium III
- Linux 2.4.18
- GCC 2.95.4-15
- Components took 3X longer
- Ensure granularity is appropriate!
- Paper by Bernholdt, Elwasif, Kohl and Epperly

| Function arg type | f77 | Component |
| --- | --- | --- |
| Array | 80 ns | 224ns |
| Complex | 75ns | 209ns |
| Double complex | 86ns | 241ns |

- March 15, 2005

**Notes:**
To examine the component instantiation costs in more detail we compared the time needed to invoke a function in f77 versus the time needed to invoke a component with an array, a complex and a double complex as arguments. 
The components took 3x longer for the function invocation, not function execution so one has to ensure that the granularity is such that the 240 ns overhead is negligible compared to the body of the component.

## Language interoperability: what is so hard?

**Native**
**cfortran.h**
**SWIG**
**JNI**
**Siloon**
**Chasm**
**Platform ****Dependent**

**C**

**C++**

**f77**

**f90**

**Python**

**Java**

- March 15, 2005

**Notes:**
Outline: 3.1.1 Language Interoperability: other technologies

One reason why mixing languages is hard is because many are never designed to be mixed.

Another is that the technologies to overcome this hurdle are all point to point solutions.

At first glance, you might say at least the graph is connected... but the graph is also directed
so while SWIG can automatically wrap C code so its callable in Python, it doesn’t work the
other way around.

## SIDL/Babel makes all supported languages peers

**C**

**C++**

**f77**

**f90**

**Python**

**Java**

**This is not a **
**Lowest Common**
**Denominator**
**Solution!**

- March 15, 2005

**Notes:**
Outline: 3.1.2 Language Interoperability: Babel

Babel solution to the language interoperability problem is to 
reduce the complexity from O(n^2) to O(n).

Babel serves as a central hub from which language bindings
are hung off from.

This is not a “Lowest Common Denominator” solution!
Babel supports an Object-Oriented Programming model
complete with virtual methods and throwing exceptions.
Babel provides extra support to non-OOP languages like 
C, F77 to provide a consistent programming model across
all supported languages.

## CCA Concepts: Components and Ports

- Components *provide* or *use* one or more ports
- Components include some code which interacts with a CCA framework
- Frameworks provide services, such as component instantiation and port connection

- Objective Function

**FunctionPort**

**FunctionPort**

- Optimization Algorithm

**OptimizerPort**

**GradientPort**

**HessianPort**

**GradientPort**

- Function Gradient

**HessianPort**

- Function Hessian

**Implementation details:**
- CCA components...
- Inherit from gov.cca.Component
- Implement setServices method to register ports this component will provide and use
- Implement the ports they provide
- Use ports on other components
- Call getPort/releasePort methods of framework Services object
- Ports (interfaces) extend the gov.cca.Port interface

- March 15, 2005

## Given a rectangular 2-dimensional domain and boundary values along the edges of the domain
Find the surface with minimal area that satisfies the boundary conditions, i.e., compute
        min f(x), where f: R   R
Solve using optimization                            components based on                                            TAO (ANL)

- Given a rectangular 2-dimensional domain and boundary values along the edges of the domain
- Find the surface with minimal area that satisfies the boundary conditions, i.e., compute
-         min f(x), where f: R   R
- Solve using optimization                            components based on                                            TAO (ANL)

- Example:Unconstrained Minimization Problem

- March 15, 2005

**Notes:**
Our final application is an unconstrained minimization problem.  Given a rectangular 2-D domain and boundary values on the edge of the domain, our goal is to find the surface with the minimum area that satisfies the boundary conditions.  That is, we need to compute the minimum of a function f(x) using optimization algorithms.  In this case, we’ll use the solvers provided by the Toolkit for Advanced Optimization (TAO) developed at ANL.

## Unconstrained Minimization Using a Structured Mesh

-                 Reused
-                 TAO Solver
-                 Driver/Physics

- March 15, 2005

**Notes:**
The solution to this optimization problem (although it is very different than the solution of PDEs) still uses many of the same components as before.  In particular, solver, distributed arrays, mxn redistribution, and visualization components are all reused (press the space bar to highlight the yellow circles)
The structure is also similar to what we’ve seen earlier.  There are two application-specific components– the driver and the min surf model that would need to be altered to run a new application.  (press the space bar to highlight the dark blue circles)
The new component in this case is the Tao solver component which is based on the TAO (Toolkit for Advanced Optimization) out of Argonne.  (press the space bar to highlight the purple circle)

## Computational Chemistry:  Molecular Optimization

**Problem Domain:**** **Optimization of molecular structures using quantum chemical methods

**Investigators:**** **Yuri Alexeev (PNNL), Steve Benson (ANL), Curtis Janssen (SNL), Joe Kenny (SNL), Manoj Krishnan (PNNL), Lois McInnes (ANL), Jarek Nieplocha (PNNL), Jason Sarich (ANL), Theresa Windus (PNNL)
**Goals:**** **Demonstrate interoperability among software packages, develop experience with large existing code bases, seed interest in chemistry domain

- March 15, 2005

## Molecular Optimization Overview 

- Decouple geometry optimization from electronic structure
- Demonstrate interoperability of electronic structure components
- Build towards more challenging optimization problems, e.g., protein/ligand binding studies

- Components in gray can be swapped in to create new applications with different capabilities.

- March 15, 2005

## Wiring Diagram for Molecular Optimization

- Electronic structures components:
- MPQC (SNL)
- 	_[http://aros.ca.sandia.gov/~cljanss/mpqc](http://aros.ca.sandia.gov/~cljanss/mpqc)_
- NWChem (PNNL)
- 	_[http://www.emsl.pnl.gov/pub/docs/nwchem](http://www.emsl.pnl.gov/pub/docs/nwchem)_

- Optimization components: TAO (ANL) _[http://www.mcs.anl.gov/tao](http://www.mcs.anl.gov/tao)_
- Linear algebra components:
- Global Arrays (PNNL) _[http://www.emsl.pnl.gov:2080/docs/global/ga.html](http://www.emsl.pnl.gov:2080/docs/global/ga.html)_
- PETSc (ANL)
- 	_[http://www.mcs.anl.gov/petsc](http://www.mcs.anl.gov/petsc)_

- March 15, 2005

## Outline

- Automatic differentiation
- Components for scientific computing
**Performance evaluation and modeling**
- Performance evaluation challenges
- Component-based approach
- Motivating example: adaptive linear system solution
- A component infrastructure for performance monitoring and adaptation of applications
- Summary

- March 15, 2005

## Why Performance Model?

- Performance models enable *understanding *of the factors that affect performance
- Inform the tuning process (of application and machine)
- Identify bottlenecks
- Identify underperforming components
- Guide applications to the best machine
- Enable applications-driven architecture design
- Extrapolate the performance of future systems

- March 15, 2005

## Challenges in performance evaluation

- Many tools for performance data gathering and analysis
- PAPI, TAU, SvPablo, Kojak, ...
- Various interfaces, levels of automation, and approaches to information presentation
- User’s  point of view
- What do the different tools do? Which is most appropriate for a given application?
- (How) can multiple tools be used in concert?
- I have tons of performance data, now what?
- What automatic tuning tools are available, what exactly do they do?
- How hard is it to install/learn/use tool X?
- Is instrumented code portable? What’s the overhead of instrumentation? How does code evolution affect the performance analysis process?

- March 15, 2005

## Incomplete list of tools

- Source instrumentation: _[TAU](http://www.cs.uoregon.edu/research/paracomp/tau/tautools/)_/_[PDT](http://www.cs.uoregon.edu/research/paracomp/proj/pdtoolkit/)_, _[KOJAK](http://icl.cs.utk.edu/kojak/overview/index.html)_ (MPI/OpenMP), _[SvPablo](http://www.renci.unc.edu/Project/SVPablo/SvPabloOverview.htm)_, Performance Assertions, ...
- Binary instrumentation: _[HPCToolkit](http://www.hipersoft.rice.edu/hpctoolkit/)_, _[Paradyn](http://www.paradyn.org/)_, _[DyninstAPI](http://www.dyninst.org/)_, ...
- Performance monitoring: _[MetaSim](http://www.sdsc.edu/PMaC/MetaSim/metasim.html)_ Tracer (memory), _[PAPI](http://icl.cs.utk.edu/papi/)_, _[HPCToolkit](http://www.hipersoft.rice.edu/hpctoolkit/)_, Sigma++ (memory), DPOMP (OpenMP), mpiP, gprof, psrun, ...
- Modeling/analysis/prediction: _[MetaSim](http://www.sdsc.edu/PMaC/MetaSim/metasim.html)_ Convolver (memory), _[DIMEMAS](http://www.cepba.upc.es/dimemas/)_(network), _[SvPablo](http://www.renci.unc.edu/Project/SVPablo/SvPabloOverview.htm)_ (scalability), _[Paradyn](http://www.paradyn.org/)_, Sigma++, ...
- Source/binary optimization: Automated Empirical Optimization of Software (_[ATLAS](http://math-atlas.sourceforge.net/)_), _[OSKI](http://bebop.cs.berkeley.edu/oski)_, ROSE
- Runtime adaptation: _[ActiveHarmony](http://www.dyninst.org/harmony/)_, _[SALSA](http://icl.cs.utk.edu/salsa/)_

- March 15, 2005

## Incomplete list of tools

- Source instrumentation: _[TAU](http://www.cs.uoregon.edu/research/paracomp/tau/tautools/)_/_[PDT](http://www.cs.uoregon.edu/research/paracomp/proj/pdtoolkit/)_, _[KOJAK](http://icl.cs.utk.edu/kojak/overview/index.html)_ (MPI/OpenMP), _[SvPablo](http://www.renci.unc.edu/Project/SVPablo/SvPabloOverview.htm)_, Performance Assertions, ...
- Binary instrumentation: _[HPCToolkit](http://www.hipersoft.rice.edu/hpctoolkit/)_, _[Paradyn](http://www.paradyn.org/)_, _[DyninstAPI](http://www.dyninst.org/)_, ...
- Performance monitoring: _[MetaSim](http://www.sdsc.edu/PMaC/MetaSim/metasim.html)_ Tracer (memory), _[PAPI](http://icl.cs.utk.edu/papi/)_, _[HPCToolkit](http://www.hipersoft.rice.edu/hpctoolkit/)_, Sigma++ (memory), DPOMP (OpenMP), mpiP, gprof, psrun, ...
- Modeling/analysis/prediction: _[MetaSim](http://www.sdsc.edu/PMaC/MetaSim/metasim.html)_ Convolver (memory), _[DIMEMAS](http://www.cepba.upc.es/dimemas/)_(network), _[SvPablo](http://www.renci.unc.edu/Project/SVPablo/SvPabloOverview.htm)_ (scalability), _[Paradyn](http://www.paradyn.org/)_, Sigma++, ...
- Source/binary optimization: Automated Empirical Optimization of Software (_[ATLAS](http://math-atlas.sourceforge.net/)_), _[OSKI](http://bebop.cs.berkeley.edu/oski)_, ROSE
- Runtime adaptation: _[ActiveHarmony](http://www.dyninst.org/harmony/)_, _[SALSA](http://icl.cs.utk.edu/salsa/)_

- March 15, 2005

## Incomplete list of tools

- Source instrumentation: TAU/PDT, KOJAK (MPI/OpenMP), SvPablo, Performance Assertions, ...
- Binary instrumentation: HPCToolkit, Paradyn, DyninstAPI, ...
- Performance monitoring: MetaSim Tracer (memory), PAPI, HPCToolkit, Sigma++ (memory), DPOMP (OpenMP), mpiP, gprof, psrun, ...
- Modeling/analysis/prediction: MetaSim Convolver (memory), DIMEMAS(network), SvPablo (scalability), Paradyn, Sigma++, ...
- Source/binary optimization: Automated Empirical Optimization of Software (ATLAS), OSKI, ROSE
- Runtime adaptation: ActiveHarmony, SALSA

- March 15, 2005

## Challenges (where is the complexity?)

- More effective use  integration
- Tool developer’s perspective
- Overhead of initially implementing one-to-one interoperabilty
- Ongoing management of dependencies on other tools
- Individual Scientist Perspective
- Learning curve for performance tools  less time to focus on own research (modeling, physics, mathematics, optimization)
- Potentially significant time investment needed to find out whether/how using someone else’s tool would improve performance  tend to do own hand-coded optimizations (time-consuming, non-reusable)
- Lack of tools that automate (at least partially) algorithm discovery, assembly, configuration, and enable runtime adaptivity

- March 15, 2005

## What can be done

- How to manage complexity? Provide
- Performance tools that are truly interoperable
- Uniform *easy *access to tools
- Component implementations of software, esp. supporting numerical codes, such as linear algebra algorithms
- New algorithms (e.g., interactive/dynamic techniques, algorithm composition)
- Implementation approach: components, both for tools and the application software

- March 15, 2005

## Performance Evaluation Research Center (http://perc.nersc.gov)

- March 15, 2005

## What is being done

- No “integrated” environment for performance monitoring, analysis, and optimization (yet)
- Most past efforts
- One-to-one tool interoperability
- More recently
- OSPAT (initial meeting at SC’04), focus on common data representation and interfaces
- Tool-independent performance databases: PerfDMF
- Eclipse parallel tools project (LANL)
- ...

- March 15, 2005

## OSPAT

- The following areas were recommended for OSPAT to investigate:
- A common instrumentation API for source level, compiler level, library level, binary instrumentation
- A common probe interface for routine entry and exit events
- A common profile database schema
- An API to walk the callstack and examine the heap memory
- A common API for thread creation and fork interface
- Visualization components for drawing histograms and hierarchical displays typically used by performance tools

- March 15, 2005

## Example: component infrastructure for multimethod linear solvers

- Goal: provide a framework for
- Performance monitoring of numerical components
- Dynamic adaptativity, based on:
- Off-line analyses of past performance information
- Online analysis of current execution performance information
- Motivating application examples:
- Driven cavity flow [Coffey et al, 2003], nonlinear PDE solution
- FUN3D – incompressible and compressible Euler equations
- Prior work in multimethod linear solvers
- McInnes et al, ’03, Bhowmick et al,’03 and ’05, Norris at al. ’05.

- March 15, 2005

## Adaptive Linear System Solution

- Motivation:
- Approximately 80% of total solution time devoted to linear system solution
- Multi-phase nonlinear solution method, requiring the solution of linear systems with varying levels of ill-conditioning [Kelley and Keyes, 1998]
- New approach aiming to reduce overall time to solution
- Combine more robust (but more costly) methods when needed in some phases with faster (but less powerful) methods in other phases
- Dynamically select a new preconditioner in each phase based on CFL number

- March 15, 2005

**Notes:**
Pseudo-transient schemes are composed of three phases (Kelleys and Keyes convergence analysis):
Time step  l remains relatively small – the Jacobians associated with equation (1) are well-conditioned
  l advances to moderate values
  l approaches infinity so that the iterate u l approaches the steady state solution

## Example: driven cavity flow

- Linear solver: GMRES(30), vary only fill level of ILU preconditioner
- Adaptive heuristic based on:
- Previous linear solution convergence rate, nonlinear solution convergence rate, rate of increase of linear solution iterations
- 96x96 mesh, Grashof = 105, lid velocity = 100
- Intel P4 Xeon, dual 2.2 GHz, 4GB RAM

- March 15, 2005

## Bringing it all together

- Integration of ongoing efforts in
- Performance tools: common interfaces and data represenation (leverage OSPAT, PerfDMF, TAU performance interfaces, and similar efforts)
- Numerical components: emerging common interfaces (e.g., TOPS solver interfaces) increase choice of solution method  automated composition and adaptation strategies
- Code generation, e.g., AD
- Long term
- Is a more organized (but not too restrictive) environment for scientific software lifecycle development possible/desirable?

- March 15, 2005

## Multimethod linear solver components

- Adaptive
- Heuristic

- Linear
- Solver B

- Linear
- Solver C

- March 15, 2005

## AD as Component Factory

- Both NEOS and PETSc rely on a well-defined *function interface *in order to provide derivatives via AD
- Extend this idea to components

- Function

**AD Tool**

- Jacobian

- March 15, 2005

## Summary

- Automation at all levels of the application development process can simplify and speed up application development and result in better software quality and performance
- AD addresses the wide-spread need for accurate and efficient derivative computations
- CCA defines a high-performance component model, enabling large-scale software development
- A growing array of performance tools and methodologies aid in understanding and fine-tuning application performance
- Current and future work: bringing these technologies together in a coherent way, making large-scale scientific application development as easy as possible

- March 15, 2005

## Acknowledgments

- Paul Hovland, Jean Utke, Lois Curfman McInnes (ANL)
- Sanjukta Bhowmick (ANL/Columbia)
- Ivana Veljkovic, Padma Raghavan (Penn State)
- Sameer Shende, Al Malony (U. Oregon)
- CCA and PERC members
- Funding: DOE and NSF

- March 15, 2005

## For More Information

- Automatic differentiation
- Andreas Griewank. *Evaluating Derivatives: Principles and Techniques of Alogrithmic Differentiation*, SIAM, 2000.
- _[www.autodiff.org](http://www.autodiff.org/)_ : publications, tools, etc.
- www.mcs.anl.gov/adicserver : ADIC server
- neos.mcs.anl.gov : NEOS server
- Common component architecture
- _[www.cca-forum.org](http://www.cca-forum.org/)_
- Performance tools
- _[perc.nersc.gov](http://perc.nersc.gov/)_
- Student opportunities at MCS/ANL
- www-fp.mcs.anl.gov/division/information/educational_programs/studentopps.html
- Boyana Norris
- Email: norris@mcs.anl.gov, Web: _[www.mcs.anl.gov/~norris](http://www.mcs.anl.gov/~norris)_

- March 15, 2005