# Presentation: 342958

- Solver Technology from the  SciDAC
- Integrated Software Infrastructure Center for
-  Terascale Optimal PDE Simulations
- Participating Institutions:
**ANL, LBNL, LLNL, **
**UC Berkeley, CU Boulder, CMU, **
**NYU, ODU, U Tennessee**

**Notes:**
15 minute presentation for first DOE NGI PI meeting

## TOPS

**Not just algorithms, but vertically integrated software suites**
**Portable, scalable, extensible, tunable implementations**
**Motivated by representative apps, intended for many others**
**Starring ****hypre**** and ****PETSc****, among other existing packages**

**Coordinated with four other ISIC SciDAC groups:**
**Algorithmic and Software Framework for Applied PDEs**
**Terascale Simulations Tools and Technologies**
**Component Technology for Terascale Simulation Software**
**Performance Science & Engineering**

**Driven by three applications SciDAC groups**
**LBNL-led “21st Century Accelerator” designs**
**ORNL-led core collapse supernovae simulations**
**PPPL-led magnetic fusion energy simulations**

## Scope for TOPS

**Design of “solvers”**
**Time integrators**
**Nonlinear solvers**
**Optimizers**
**Linear solvers**
**Eigensolvers**

**With collaborators: geometry, discretization, adaptivity, data management, visualization issues**

## Participating Institutions

**Office of Science laboratories**
**Argonne (**_**Smith**_**, **_**Moré**_**, Benson, Knepley, Minkoff, Munson, Zhang)**
**Lawrence Berkeley (**_**Ng**_**, Husbands, Li, Marques, Yang)**
**Defense Program laboratory**
**Lawrence Livermore (**_**Falgout**_**, Chow, Dumett, Serban, Vassilevski, Woodward)**
**Universities**
**UC Berkeley (**_**Demmel**_**)**
**CU Boulder (**_**McCormick**_**, Cai, Manteuffel, Ruge)**
**Carnegie Mellon (**_**Ghattas**_**)**
**NYU-Courant (**_**Widlund**_**, Biros, Hientzsch)**
**ODU (**_**Keyes**_**, Dobrian, Pothen)**
**U Tennessee (**_**Dongarra,**_** Eijkhout)**

## Salient Application Properties

**Multirate, requiring fully or semi-implicit in time solvers**
**Multiscale, requiring finest mesh spacing much smaller than domain diameter**
**Multicomponent, requiring physics-informed preconditioners, transfer operators, and smoothers**

**Not linear**
**Not selfadjoint**
**Not structured**

## Keyword: “Optimal”

**Convergence rate nearly independent of discretization parameters**
**Multilevel schemes for linear and nonlinear problems**
**Newton-like schemes for quadratic convergence of nonlinear problems**

**Convergence rate as independent as possible of physical parameters**
**Continuation schemes**
**Asymptotics-induced, operator-split preconditioning**

**Yet different sense: performance-optimized**

## Presentation Plan

**Introduction**
**TOPS philosophy**
**Brief outline of TOPS project scope**
**Project plan**
**Conclusions**

## TOPS Philosophy on PDEs

**Solution of a system of PDEs is rarely a goal in itself **
**PDEs are solved to derive various outputs from specified inputs**
**Actual goal is characterization of a response surface or a design or control strategy**
**Together with analysis, sensitivities and stability are often desired**

**Tools for PDE solution should also support related desires**

## TOPS Philosophy on Resolution

**Demand for resolution is virtually insatiable**
**Relieving resolution requirements with modeling (e.g., turbulence closures, homogenization) only defers the demand for resolution to the next level**
**Validating such models requires high resolution**

**Processor scalability and algorithmic scalability (optimality) are critical **

## TOPS Philosophy on Hardware

**Hardware changes many times over the life of a code**
**Processors, memory, and networks evolve annually**
**Machines are replaced every 3-5 years at major DOE centers**
**Message-passing programming model appears stable, at least as a baseline**
**Codes persist for decades **

**Portability is critical (ease, performance-robustness)**

## TOPS Philosophy on Types of Use

**Solvers are employed in many ways over the life-cycle of an applications code**
**During development and upgrading, robustness (of the solver) and verbose diagnostics are important**
**During production, solvers are streamlined for performance  **

**Tunability is important**

## TOPS Philosophy on Context of Use

**Solvers are employed as a part of a larger code**
**Solver library is not only library to be linked**
**Solvers may be called in multiple nested places**
**Solvers typically make call-backs**
**Solvers should be swappable****	**

**Solver threads must be isolable from other component threads, including other instances of themselves**

## TOPS Philosophy on Users

**Solvers are used by people of varying numerical backgrounds**
**Some expect MATLAB-like defaults**
**Others want to control everything, e.g., even varying the type of smoother and number of smoothings on different levels of a multigrid algorithm**

**Multilayered software design is important**

## TOPS Philosophy on Completeness

**No general purpose PDE solver can anticipate all needs or compete as a general purpose tool with the ingenuity of an expert application domain user**
**We have *****national laboratories*****, not *****numerical libraries***
**A PDE solver improves with user interaction**
**Pace of algorithmic development is very rapid**

**Extensibility is important**

## TOPS Philosophy on Operators

**A continuous operator may appear in a discrete code in many different instances**
**Optimal algorithms tend to be hierarchical and nested iterative**
**Processor-scalable algorithms tend to be domain-decomposed and concurrent iterative**
**Majority of progress towards desired highly resolved, high fidelity result occurs through cost-effective low resolution, low fidelity parallel efficient stages**

**Solver should offer operator abstractions and recurrence**

## TOPS Philosophy on Communities

**Successful codes create scientific subcommunities of self-teaching users**
**Codes that achieve a critical mass of users generate free contributions from those users (e.g., MATLAB)**
**In this way, a code becomes a vehicle for scientific discourse among experts and an educational resource for graduate students and cross-disciplinary newcomers (e.g., the physicist who needs to come “up to speed” in mathematical optimization)**

**TOPS codes must inspire confidence for long-term support to grow such communities**

## Presentation Plan

**Introduction**
**TOPS philosophy**
**Brief outline of TOPS project scope**
**Project plan**
**Conclusions**

## Brief Outline of TOPS Scope

**Five capabilities**
**Adaptive time integrators for stiff systems**
**Nonlinear implicit solvers**
**Optimizers**
**Linear solvers**
**Eigensolvers**
**Two cross-cutting topics**
**Software integration and deployment**
**High performance implementation**

**What exists?  What’s next?**
**NB: Not all of what exists is yet optimal!**

## Component Inter-relationships 

- Optimizer

- Linear solver

- Eigensolver

- Time integrator

- Nonlinear solver

**Indicates dependence**

## What Exists Already?

**Adaptive time integrators for stiff systems: variable-step BDF methods**
**Nonlinear implicit solvers: Newton-like methods, FAS multilevel methods**
**Optimizers (with constraints): quasi-Newton RSQP methods**
**Linear solvers: subspace projection methods (multigrid, Schwarz, classical smoothers), Krylov methods (CG, GMRES), sparse direct methods**
**Eigensolvers: matrix reduction techniques followed by tridiagonal eigensolvers, Arnoldi methods**

## Why is TOPS needed?

**Today’s components do not “talk to” each other very well**
**Mixing and matching procedures too often requires mapping data between different storage structures (taxes memory and memory bandwidth)**
**Logically innermost (solver) kernels are often the most computationally complex — should be designed from the inside out by experts and present the right “handles” to users**
**Many widely used libraries are quite behind the times, algorithmically**

## Time Integrators: What’s ready?

**PVODE**** and ****IDA**** (LLNL)**
**Essentially ****CVODE/VODE**** logic with MPI-based objects**
**Variable-order backward differentiation formulae**
**Predecessors have 300,000 ****netlib**** downloads**
**Interfaced with ****PETSc**
**Employed on thousands of procs of ASCI White and Red, on PDEs of billions of zones with method-of-lines**
**Especially valued for time-adaptive and step control logic**

## Nonlinear Solvers: What’s ready?

**KINSOL**** (LLNL) and ****PETSc ****(ANL)**
**Preconditioned Newton-Krylov methods with MPI-based objects**
**Asymptotically nearly quadratically convergent and mesh independent**
**Matrix-free implementations (FD and AD access to Jacobian elements)**
**Thousands of direct downloads (****PETSc****) and active worldwide “friendly user” base**
**Interfaced with ****hypre**** preconditioners (****KINSOL****)**
**1999 Bell Prize for unstructured CFD computation at 0.227 Tflop/s on a legacy F77 NASA code**

## Nonlinear Solvers: What’s next?

**Semi-automated continuation schemes (e.g., pseudo-transience)**
**Additive-Schwarz Preconditioned Inexact Newton (ASPIN)**
**Full Approximation Scheme (FAS) multigrid**
**Polyalgorithmic combinations of ASPIN, FAS, and NK-MG, together with new linear solvers/preconditioners**
**Automated Jacobian calculations with parallel colorings**
**New grid transfer and nonlinear coarse grid operators**
**Guidance of trade-offs for cheap/expensive function calls**
**Guidance on cycling strategies (V, W, F)**

## Optimizers: What’s ready?

**TAO**** (ANL) and ****VELTISTO**** (CMU)**
**Bound-constrained and equality-constrained optimization**
**Achieve optimum in number of PDE solves independent of number of control variables**
**TAO**** released 2000, ****VELTISTO**** to be released any day now**
**Both built on top of ****PETSc**
**Applied to problems with thousands of controls and millions of constraints on hundreds of processors**
**Used for design, control, parameter identification**
**Used in nonlinear elasticity, Navier-Stokes, acoustics**
**State-of-art Lagrange-Newton-Krylov-Schur algorithmics**

## Optimizers: What’s next?

**Extensions to inequality constraints (beyond simple bound constraints)**
**Extensions to time-dependent PDEs, especially for inverse problems**
**Multilevel globalization strategies**
**Toleration strategies for approximate Jacobians and Hessians**
**“****Hardening” of promising control strategies to deal with negative curvature of Hessian**
**Pipelining of PDE solutions into sensitivity analysis**

## Linear Solvers: What’s ready?

**PETSc**** (ANL), ****hypre**** (LLNL), ****SuperLU ****(UCB), ****Oblio**** (ODU)**
**Krylov, multilevel, sparse direct**
**Numerous preconditioners, incl. BNN, SPAI, PILU/PICC**
**Mesh-independent convergence for ever expanding set of problems**
**hypre**** used in several ASCI codes and milestones to date**
**SuperLU**** in ScaLAPACK**
**State-of-art algebraic multigrid (****hypre****) and multifrontal (****SuperLU****) efforts**
**Algorithmic replacements *****alone***** yield up to two orders of magnitude in DOE apps, before parallelization**

## Linear Solvers: What’s next?

**Hooks for physics-based operator-split preconditionings**
**AMGe, focusing on incorporation of neighbor information and strong cross-variable coupling**
**Spectral AMGe for problems with geometrically oscillatory but algebraically smooth components**
**FOSLS-AMGe for saddle-point problems**
**Hierarchical basis ILU**
**Incomplete factorization adaptations of ****SuperLU**** **
**Convergence-enhancing orders for ILU**
**Stability-enhancing orderings for sparse direct methods for indefinite problems**

## Eigensolvers: What’s ready?

**LAPACK and ScaLAPACK symmetric eigensolvers (UCB, UTenn, LBNL)**
**PARPACK extensions to ScaLAPACK to sparse and nonsymmetric problems**
**Reductions to symmetric tridiagonal or Hessenberg form, followed by new “Holy Grail” algorithm**
**Holy Grail optimal (!): *****O(kn)***** work for *****k n*****-dimensional eigenvectors**

## Eigensolvers: What’s next?

**Iterative linear solution methods for shift-invert Lanczos for selected eigenpairs in large symmetric and complex symmetric generalized eigenproblems**
**Jacobi-Davidson projection methods for selected eigenpairs**
**Multilevel methods for eigenproblems arising from PDE applications**
**Hybrid multilevel/Jacobi-Davidson methods**

## Integration: What’s ready?

**Extensive experience with open source software support**
**LINPACK, LAPACK, ScaLAPACK (incl. ****SuperLU****)**
**MINPACK, MINPACK-2**
**PETSc**
**hypre**
**Many “hand-made” interoperability combinations**
**PETSc**** uses LINPACK, LAPACK, BlockSolve95, SPARSPACK, MINPACK, ParMeTiS, SPAI**
**hypre**** supports ****PETSc**** matrix/vector distributed objects**
**OVERTURE**** and ****SAMRAI**** can use ****PETSc**
**TAO ****and**** VELTISTO ****use**** PETSc**

## Integration: What’s next?

**Interoperable lab-based suites**
**Conformation to CCA, ESI, and FEI standards**
**Interfaces generated by BABEL**
**Automated test suites of development versions run nightly**
**Released versions maintained at NERSC and elsewhere**
**Sample applications distributed with software libraries**
**Integrated tutorials at major professional meetings and via the Access Grid, centered around scientific tasks, not just packages**

## High Performance: What’s ready?

**PhiPAC**** (UCB) and ****ATLAS**** (UTenn)**
**These two self-tuning research efforts now merged**
**Efficient machine-specific search of cache blocking parameters tunes BLAS3 DGEMM better than vendors in many cases, in just a few hours**
**Automatic performance “ports” to new hardware, with code ports**
**Adopted by MathWorks for MATLAB**
**New ****SPARSITY**** package (UCB) now optimizes data structure for sparse matrix-vector multiplications (up to factor of five in serial performance, so far)**

## High Performance: What’s next?

**Automated Empirical Optimization of Software (AEOS)**
**Combination of automatic code generation and experimental profiling to estimate key parameters for target hardware**
**Parameters used to tune selected kernels**
**Generalized beyond linear algebra kernels, especially to multilevel kernels (restriction, prolongation, coarse problem generation)**
**Run-time extensions to algorithmic parameters, such as ILU fill-levels or Schwarz overlap levels**

## Presentation Plan

**Introduction**
**TOPS philosophy**
**Brief outline of TOPS project scope**
**Project plan**
**Conclusions**

##  Ideal Chronology

**Years 1 & 2**
**Hook users with existing technology (need first-year “homerun”)**
**Learn application characteristics**
**Concentrate on functionality over performance, with apps partners**
**Deliver to CCA and Performance ISICs reference optimal solver implementations on scalable model problems**
**Lay foundations for smoother interoperability and higher performance in key kernels through extensive CCA and Performance ISIC interations**
**Years 2 & 3**
**Migrate high performance implementations into user codes**
**Research more optimal, robust algorithmic successors**
**Years 3, 4 & 5**
**Steadily migrate better algorithms into solver codes**
**Continually improve and “harden” codes**
**Educate users in “holistic PDE simulation”, with additional TOPS tools**

## Logistics

**TOPS matrix management**
**People managed within institutions, under nine institutional leads**
**Topics managed across institutions, under seven topical leads**
**Oversight of TOPS**
**Technical advisory committee (reporting to Director) made up of leaders of other ETCs and client APPs groups and lead PIs of TOPS (Falgout, Keyes, More, Ng, Smith)**
**DOE project liaison in Washington, DC**
**Lab division directors (CASC, MCS, NERSC) **
**Communication**
**Regular joint meetings and *****Access Grid***** conferencing**

## Software Policies

**Usability from ****PETSc**** or ****hypre**** for all software**
**Maximal internal reuse**
**Timely response to bug reports, usage questions, functionality requests**
**Parallel ports through MPI**
**Portable to common Unix implementations and Windows**
**Open source**
**Well defined revision control systems within each software suite**

## Intellectual Property Policies

**Each co-PI and post-doc accountable to policies of own employing organization and to DOE**
**Each graduate student accountable to own department and advisor**
**Standard decentralized academic practices for publication showing SciDAC sponsorship**
**TOPS-centralized website with internally refereed tech reports and links as interface to outside**

## Resource Sharing Policies

**Each institutional lead seeks to provide relevant local resources to consortium, consistent with local “appropriate use” guidelines**
**Each project participant may ask to share resources at collaborative site**
**DOE provides time on NERSC systems for high-end prototyping and production**
**Within reason, travel burdens and travel expenses for group meetings are rotated**

## Presentation Plan

**Introduction**
**TOPS philosophy**
**Brief outline of TOPS project scope**
**Project plan**
**Conclusions**

## Challenges for TOPS

**Internal coordination of a nine-institution project**
**Asymmetry in external coordination with other ETCs and APPs groups (“plumber” mentality)**
**Evolving software standards**
**Evolving parallel programming models**
**Decisions about how far to go to meet other SciDAC collaborators “partway” on issues of interfaces and data structures**

## Invitation to Users

**Applications groups identify first-year priorities from TOPS**
**Create corresponding graded set of development/“acceptance test” problems**
**Help identify/recruit visionary and competent “go-betweens” for the software ports**

## Expectations TOPS has of Users

**Willingness to experiment with novel algorithmic choices – optimality is *****rarely***** achieved beyond model problems without interplay between physics and algorithmics!**
**Adoption of flexible, extensible programming styles in which algorithmic and data structures are not hardwired**
**Willingness to make concrete requests, to understand that requests must be prioritized, and to work with us in addressing the high priority requests**