# Presentation: 304414

## David Keyes, project lead

**David Keyes, project lead**

**http://www.tops-scidac.org**

## Plan

**What TOPS aims to provide**
**Some uses of TOPS solver software**
**TOPS posters: *****what to find***** Tues. aft.**
**TOPS attendees: *****who to meet***** Tues. aft.**
**Preview of TOPS’ linear solver interface**
**How to work with TOPS**

** ****Get you to lunch on time!**

## Shameless advertisement

**16****th**** Domain Decomposition meeting **
**USA hosts for first time since 1997 **
**January 12-16, 2005**
**Courant Institute, NYU**
**Co-organized by O. Widlund & D. K.**
**Invited speakers**
**Participant-initiated minisymposia**
**Contributed talks**
**Pre-conference short course on software for prototyping domain decomposition methods**

## Shameless advertisement

**16****th**** Domain Decomposition meeting **
**USA hosts for first time since 1997 **
**January 12-16, 2005**
**Courant Institute, NYU**
**Co-organized by O. Widlund & D. K.**
**Invited speakers**
**Participant-initiated minisymposia**
**Contributed talks**
**Pre-conference short course on software for prototyping domain decomposition methods**

- March

## Who we are...

**Who we are...**

**... ****the ****PETSc ****and**** TAO**** people**

**... ****the ****hypre**** and ****Sundials**** people**

**... ****the ****SuperLU ****and ****PARPACK**** people**

## Plus some university collaborators ...

**Plus some university collaborators ...**

**... ****with a history of lab collaborations in high performance computing**

## Beyond the on-line “Templates” guides

**www.netlib.org/****e****templates**

**www.netlib.org/templates**

**124 pp.**

**410 pp.**

**... ****these are good starts, but not adequate for SciDAC scales!**

## Themes affirmed in our May’03 review

**Central concept: software “toolchain” **
**solutions ******** sensitivity, stability, optimization**
**modules are nested**
**the greatest coding work is in the distributed data structures and should be leveraged**
**users deal with mathematical objects throughout; software hides the MPI and ugly details for performance**
**Ordered goals: usability, robustness, algorithmic efficiency, and performance efficiency**
**Growth industry: multirate problems are forcing applications codes into implicitness**

## Scope for TOPS

**Design and implementation of “solvers”**
**Time integrators**
**Nonlinear solvers**
**Optimizers**
**Linear solvers**
**Eigensolvers**
**Software integration**
**Performance optimization**

**(w/ sens. anal.)**

**(w/ sens. anal.)**

## The power of optimal algorithms

**Advances in algorithmic efficiency rival advances in hardware architecture**
**Consider Poisson’s equation on a cube of size *****N=n******3***
**If  *****n=*****64, this implies an overall reduction in flops of ****~****16 million**

| Year | Method | Reference | Storage  | Flops |
| --- | --- | --- | --- | --- |
| 1947 | GE (banded) | Von Neumann & Goldstine | n5 | n7 |
| 1950 | Optimal SOR | Young | n3 | n4 log n |
| 1971 | CG | Reid | n3 | n3.5 log n |
| 1984 | Full MG | Brandt | n3 | n3 |

## Algorithms and Moore’s Law

**Algorithms and Moore’s Law**

**This advance took place over a span of about 36 years, or 24 doubling times for Moore’s Law**
**2****24********16 million ******** the same as the factor from algorithms alone!**

## Where to go past O(N) ?

**Since *****O(N)***** is already optimal, there is nowhere further “upward” to go in efficiency, but one must extend optimality “outward”, to more general problems**
**Hence, for instance, algebraic multigrid (AMG), obtaining *****O(N)***** in  *****indefinite,***** *****anisotropic, *****or***** inhomogeneous***** problems**

***algebraically smooth error***

## TOPS software in SciDAC collabs

| APDEC | Hypre |  |
| --- | --- | --- |
| ASCTKD | PETSc |  |
| AST | PARPACK/SuperLU |  |
| CCTTSS | TAO*, SUNDIALS** |  |
| CEMM | PETSc/Hypre, SUNDIALS |  |
| CMRS | PETSc/Hypre |  |
| CLGT |  |  |
| PERC | PETSc |  |
| SSC |  |  |
| TSI | custom |  |
| TSTT | TAO |  |

- current

- planned

- *supporting NWChem, MPQC    **supporting CFRFS

## TOPS software in SciDAC collabs

| APDEC | Hypre |  |
| --- | --- | --- |
| ASCTKD | PETSc |  |
| AST | PARPACK/SuperLU | Veltisto/PETSc |
| CCTTSS | TAO*, SUNDIALS** | PETSc/Hypre |
| CEMM | PETSc/Hypre, SUNDIALS |  |
| CMRS | PETSc/Hypre |  |
| CLGT |  | Hypre, PARPACK |
| PERC | PETSc |  |
| SSC |  | PETSc/Hypre |
| TSI | custom | PETSc/Hypre, SUNDIALS |
| TSTT | TAO |  |

- current

- planned

- *supporting NWChem, MPQC    **supporting CFRFS

## TOPS citations outside of SciDAC

**Astronomy**
**Biomechanics**
**Chemistry**
**Cognitive Sciences**
**Combustion**
**Electrical Engineering**
**Geosciences**
**Hydrodynamics**
**Materials Science**
**Mechanics**
**Micromechanics/Nanotechnology**
**Numerical Analysis**
**Optics**
**Porous Media**
**Shape Optimization**

**Dspice**
**EMSolve**
**FEMLAB****®**
**FIDAP****®**
**GlobalArrays**
**HP Mathematical Library****®**
**libMesh**
**Magpar**
**Mathematica****®**
**NIKE**
**Prometheus**
**SCIRun**
**SLEPc**
**Snark**
**Trilinos**

**25 jour., proc., theses (2002-04):**

**Widely distributed software:**

## Bell prize news

**TOPS’ PETSc software has been employed in two Bell Prizes (“special category”) in 1999 & 2003**
**2003 prize: geological parameter estimation problem**
**Forward PDE: 17 million unknowns**
**Inverse problem: 70 billion unknowns (over time history)**
**2048 procs of HPAlphaServer for 24 hours**

**reconstruction**

**target**

## Poster iconography, 2004

- Overview

- Iterative
- Solvers

- Eigensolvers

**Poster iconography, 2004**

- Integrators

- Optimizers

- Direct
- Solvers

- Implementation
- Performance

- Convergence
- Performance

## Who to talk with at this meeting ...

**Linear solvers                                  *****(******Esmond Ng******)***
**Eigensolvers                                *****(******Esmond Ng******, Osni Marques)***
**Nonlinear solvers                          *****(David Keyes)***
**ODE/DAEs/sensitivity                          *****(David Keyes)***
**Optimizers                                     *****(Omar Ghattas, Jorge Mor******é******)***
**Software integration                        *****(David Keyes)***
**Performance optimization            *****(Victor Eijkhout, Rich Vuduc)***

**Ng, LBNL**

## Who to talk with at this meeting ...

**Marques, LBNL**

**Linear solvers                                  *****(Esmond Ng)***
**Eigensolvers                                *****(Esmond Ng, ******Osni Marques******)***
**Nonlinear solvers                          *****(David Keyes)***
**ODE/DAEs/sensitivity                          *****(David Keyes)***
**Optimizers                                     *****(Omar Ghattas, Jorge Mor******é******)***
**Software integration                        *****(David Keyes)***
**Performance optimization            *****(Victor Eijkhout, Rich Vuduc)***

## Who to talk with at this meeting ...

**Linear solvers                                  *****(Esmond Ng)***
**Eigensolvers                                *****(Esmond Ng, Osni Marques)***
**Nonlinear solvers                          *****(******David Keyes******)***
**ODE/DAEs/sensitivity                          *****(******David Keyes******)***
**Optimizers                                     *****(Omar Ghattas, Jorge Mor******é******)***
**Software integration                        *****(******David Keyes******)***
**Performance optimization            *****(Victor Eijkhout, Rich Vuduc)***

**Keyes, Columbia**

## Who to talk with at this meeting ...

**Linear solvers                                  *****(Esmond Ng)***
**Eigensolvers                                *****(Esmond Ng, Osni Marques)***
**Nonlinear solvers                          *****(David Keyes)***
**ODE/DAEs/sensitivity                          *****(David Keyes)***
**Optimizers                                     *****(******Omar Ghattas******, Jorge Mor******é******)***
**Software integration                        *****(David Keyes)***
**Performance optimization            *****(Victor Eijkhout, Rich Vuduc)***

**Ghattas, CMU**

## Who to talk with at this meeting ...

**Mor****é****, ANL**

**Linear solvers                                  *****(Esmond Ng)***
**Eigensolvers                                *****(Esmond Ng, Osni Marques)***
**Nonlinear solvers                          *****(David Keyes)***
**ODE/DAEs/sensitivity                          *****(David Keyes)***
**Optimizers                                     *****(Omar Ghattas, ******Jorge Mor******é******)***
**Software integration                        *****(David Keyes)***
**Performance optimization            *****(Victor Eijkhout, Rich Vuduc)***

## Who to talk with at this meeting ...

**Linear solvers                                  *****(Esmond Ng)***
**Eigensolvers                                *****(Esmond Ng, Osni Marques)***
**Nonlinear solvers                          *****(David Keyes)***
**ODE/DAEs/sensitivity                          *****(David Keyes)***
**Optimizers                                     *****(Omar Ghattas, Jorge Mor******é******)***
**Software integration                        *****(David Keyes)***
**Performance optimization            *****(******Victor Eijkhout******, Rich Vuduc)***

**Eijkhout, UT**

## Who to talk with at this meeting ...

**Linear solvers                                  *****(Esmond Ng)***
**Eigensolvers                                *****(Esmond Ng, Osni Marques)***
**Nonlinear solvers                          *****(David Keyes)***
**ODE/DAEs/sensitivity                          *****(David Keyes)***
**Optimizers                                     *****(Omar Ghattas, Jorge Mor******é******)***
**Software integration                        *****(David Keyes)***
**Performance optimization            *****(Victor Eijkhout, ******Rich Vuduc******)***

**Vuduc, UC Berkeley**

## TOPS Solver Interface

## Desiderata

**Simplicity**
**as few required concepts as possible**
**Generality**
**richness of instances of each concept**
**Language independence**
**callable from anything you want, but easy for us  to maintain**
**High performance**
**no forced provision or recopying of data beyond what best method needs**
**Extensibility**
**something we can live with as new algorithms come along and have to be integrated underneath**

## Some progenitors

**FEI - **finite element interface**/C++ **
**developed at SNL**
**ESI - **equation solver interface**/C++ **
**multi-lab effort**
**hypre **conceptual interfaces**/C **
**developed at LLNL**
**PETSc/C **
**developed at ANL**

## TOPS solver interfaces today

**PETSc is an API that calls**
**Hypre, SuperLU, PVODE (SUNDIALS), many other solvers outside of TOPS’ responsibility to maintain**
**TAO, Veltisto call PETSc**
**Other interoperability combinations**
**e.g., PARPACK calls SuperLU, Hypre calls SuperLU and PETSc, ...**
**For linear solvers, want common interface to PETSc, Hypre, SuperLU, etc.**
**Purpose is *****not***** to avoid subroutine call-through overhead, but to offer full functionality of each**

## Language independence

**Implemented using LLNL’s SIDL (Scientific Interface Definition Language), a winning card of CCTTSS**
**Will not require additional packages**
**Does not require learning a new programming language**
**F77/F90, C/C++, Python**

## Abstract interface concepts

**Solver**** is a labeled object that contains visible ****operator**** and ****vector(s)****, and invisible associated storage**
**A given application code may have *****dozens of persistent solver objects*****, each with reusable factorizations, preconditioners, coarse grid hierarchies, etc.**
**Vector**** represents field data**
**Operators**** and ****vectors**** can be accessed with a ****viewer**
**Operators**** and ****vectors ****have distributed, blocked ****layouts**

## “View”

- Allows user to access vector and matrix values in the language of the application, e.g, ‘conceptual interfaces’ of Hypre
- Handles any communication of the data transparently

## Accessing values in vectors/matrices

- interface View {
-     // Begin getting or setting values
-     void startAccessible();
-     // Send values to correct (distributed) locations
-     void endAccessibleStartCommunication();
-     // Receive values to correct locations
-     void endAccessibleEndCommunication();
-     // Set all entries to zero
-     void zero();

- Sub-interface specific methods

## Classical linear algebra view

- interface View_Vector_Rn extends TOPS.View {
-    <double>  getValues(<int> indices);
-     void          setValues(<int> indices, <double> values);
-     void          addValues(<int> indices, <double> values);
-     <double> accessArrayRead();
-     <double> accessArrayWrite();
-     void          restoreArray(<double> values);

- Indices represent locations in Rn

## Structured-grid view

- interface View_Vector_S extends TOPS.View {
-    <double,3>  getValues(<int,3> indices);
-     void             setValues(<int,3> indices, <double,3> values);
-     void             addValues(<int,3> indices, <double,3> values);
-     <double,3> accessArrayRead();
-     <double,3> accessArrayWrite();
-     void            restoreArray(<double,3> values);

- Indices represent locations in Rm x Rn  x Rp

## Views/Layouts

**Rn - ‘classical linear algebra’ access**
**S - single structured grid**
**Fe - finite element interface**
**Ss - semi-structured grids; block-structured grid with additional arbitrary node-to-node connections**
**...**

## For further discussion

** **Open source interface to PETSc and Hypre, to begin with
-  Will not require installing Babel (?)
-  Working code available soon
-  Comments welcome!

- bk://tops.bkbits.net/tops-solver-interface

## Working with TOPS

**Hundreds of groups around the world use TOPS software without directly collaborating with TOPS co-PIs**
**You can, too, but SciDAC *****does***** provide limited opportunity for direct collaboration**

## Benefits of working with TOPS

**Apps groups tend to under-employ complicated iterative libraries on their own**
**underexploitation of available structure**
**underexploitation of algorithmic options**
**underexploitation of profiling tools**
**TOPS thinks of its work as *****adding options*****, *****not***** making changes**
**TOPS can often help a lot *****before *****adding solver options**

## May’03 review recommendations

**“****Down-select to a smaller set of applications and a subset of the algorithms to be implemented in the solver software tools.”**
**“****On a high priority basis, allocate resources in the later years to algorithm and software consultation and deep collaboration with selected applications.”**

## Requirements for future collaborations

**Version control systems are *****essential***** to having any lasting impact or “insertion path” for solver improvements**
**Automated build system for user code *****required***
**Portability to Linux desktop/laptop *****required *****for development purposes**
**Access to user’s production machine *****required *****for performance tuning purposes**

## Expectations TOPS has of users

**Be willing to experiment with novel algorithmic choices – optimality is *****rarely***** achieved (beyond model problems) without interplay between physics and algorithmics!**
**Adopt flexible, extensible programming styles in which solver algorithms and data structures are not hardwired**
**Be willing to let us play with the real code you care about, but be willing, if appropriate, to abstract out relevant compact tests**

## TOPS success metrics

**Understand range of algorithmic options and their tradeoffs (*****e.g.,***** memory *****vs.***** time, inner iteration work *****vs.***** outer)**
**Can try all reasonable options easily without recoding or extensive recompilation**
**Know how their solvers are performing**
**Spend more time in their physics than in their solvers**
**Are intelligently driving solver research, and publishing joint papers with TOPS researchers**
**Can simulate *****truly new physics*****, as solver limits are steadily pushed back (finer meshes, complex coupling, etc.)**

**TOPS users ****—**

## For more information ...

**For more information**** ...**