# Presentation: 770634

- Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company,for the United States Department of Energy under contract DE-AC04-94AL85000.

**ASC HPEMS Xyce Circuit Simulator:**
**Linear Solver Technology**
**June 23, 2004**
**R. Hoekstra**
**D. Day, M. Heroux,**** ****E. Keiter, S. Hutchinson,**
**T. Russo, E. Rankin, R. Pawlowski**

**Notes:**
This is the template to use for the 2000 ASCI PI meeting at LLNL.  All text enclosed in [] should be either removed or updated to the appropriate value (with the [] removed after updating).

## Overview

**What’s Hard about Circuit Problems?**
**Trilinos Solver Library**
**Linear Solution for Circuits**
**Direct **
**Iterative**
**Singleton Filtering**
**Ordering/Partitioning**
**Block Triangular Factorization**
**Conclusions**

## What’s HARD?

- Preconditioning

- Partitioning/
- Ordering

**Stiff coupled DAE’s**
**Highly Nonlinear Devices**
**Discontinuities, Hysteresis**
**Sparse Linear Systems**
**Ill-Conditioned/Scaled**
**Non-Symmetric**
**Network Topology (Not A Mesh!)**
**Dense Rows**

## Eigenvalues

*Newton’s Method*
*Spectrum of Jacobian  each iteration*
*Semi-Log Plot*
*Numerically Singular until Convergence*
*Non-Uniqueness*

## Trilinos is a collection of Packages.

*****

*****

*****

*****

*****

*****

*****

*****

*****

*****

*****

*****

**Trilinos is a collection of *****Packages*****.**
**Focused Package Development**
**State-of-the-art algorithms in a given problem regime.**
**Small development team of domain experts.**
**Self-contained**
**Individual Configure/Build/Documentation**
**Benefits**
**Common Infrastructure**
**Common Tools**
**Interoperability**
**http://software.sandia.gov/trilinos**

## Xyce(Trilinos/Zoltan)

**Open source libraries under rapid development**
**Benefits**
**State-of-the-Art Algorithms**
**Rapid Support**
**Gnu Autotool Configure/Build Environment**
**NOX/LOCA:**** Globalized Newton Type Methods, Homotopy/Continuation**
**AztecOO:**** Preconditioned GMRES**
**Ifpack:**** Enhanced Block-ILUK**
**Epetra(Ext):**** Distributed Memory Linear Algebra and Transformations**
**Zoltan:**** Parallel Partition/Load Balance**

**Xyce TopLevel: I/O, Setup **

**Xyce TimeInt**
**(Future Trilinos::TOX)**

**Trilinos::NOX/LOCA**
**Nonlinear Solver/Continuation**

**Xyce Device Models, Loads**

**Trilinos::AztecOO**
**Iterative Linear Solver**

**Trilinos::Ifpack**
**ILU Preconditioner**

**Trilinos::Epetra+Ext**
**Linear Algebra/Parallel Data**

**Trilinos::Amesos**
**Direct Linear Solvers**

**Zoltan Load Balance**
**(ParMETIS, Hypergraph)**

## Amesos:Sparse Direct Linear Solvers

| Library Name | Lang. | Comm. | # procs
for solution1 |
| --- | --- | --- | --- |
| KLU | C | Serial | 1 |
| UMFPACK | C | Serial | 1 |
| Mod. KundertSparse | C | Serial | 1 |
| SuperLU_DIST 2.0 | C | MPI | any |
| MUMPS 4.3.1 | F90 | MPI | any |
| ScaLAPACK | F77 | MPI | any |

## Iterative Linear Solve

**Trilinos: Epetra, IfPack, AztecOO ****(Belos, TSF)**
**Strategy : GMRES**
**Domain Decomposition**
**Singleton Filtering ******** ****DENSE ROWS**
**Zoltan/ParMETIS Partitioning**
**Overlapping Additive Schwarz**
**AMD/RCM Block Reordering**
**Row/Col Scaling**
**Stabilized ILUT(B)**
***B :=*****  dual threshold *****a priori *****diagonal perturbation (A)**

## Adaptive ILU Preconditioning

**Idea: Compute ILU factor of a matrix *****B***** that is “nearby” original matrix *****A*****, but better conditioned.  (Generalization of Manteuffel shift)**
**Sets up a continuum of preconditioners between accurate but poorly conditioned ILU factor and Jacobi scaling.**
***B***** differs from *****A *****only on diagonal**
**Adaptive Algorithm to test threshold values**

| Max Condest | Iters (Res) | Result | Action | Time |
| --- | --- | --- | --- | --- |
| inf | None | Condest not < Condest thresh  | Set  = 10-12 |  |
| 1012 | 1 (100) | Hessenberg Ill-conditioned | Set  = 10-2 |  |
| 102 | 10 (10-7) | Converged |  | 0.35 |

## Singleton Filtering

**Row Singleton**
**Pre-Process**
**Col Singleton**
**Post-Process**

**Dist. Memory Algorithm in Trilinos::EpetraExt**

## Singleton Filtering

| Number of... | Original Problem | After Filtering |
| --- | --- | --- |
| Successful Steps Taken | 925 | 892 |
| Failed Steps Attempted | 67 | 53 |
| Jacobians Evaluated | 2488 | 2399 |
| Linear Solves | 2488 | 2399 |
| Failed Linear Solves | 32 | 13 |
| Linear Solver Iterations | 33595 | 12152 |

## Putting It Together

**Digital Adder on 8 processors**
**Improved both Scalability & Robustness**
**Maybe Iterative Solvers are viable for Circuits!**

- Partition
- Circuit

- Scale

- RCM

- Singleton
- Filter

- Partition
- LinSys

| N | Total Cuts | CondEst | GMRES Iters | LinSolve Time | Newton Steps |
| --- | --- | --- | --- | --- | --- |
| 1220 | ~1000 | 3.00E+05 | 500 | 4.7 | 72 |
| 1220 | 188 | 2.00E+05 | 200 | 1.1 | 45 |
| 1054 | 68 | 1.00E+04 | 127 | 0.43 | 53 |

- PC

- PC+SF+PL+RCM+SCALE

## Parallel Scaling

**Parallel Scaling**

**Nonlinear transmission line **
**14 million devices**
**6 million Unk’s**
**Over factor of 500 speedup using 1024 processors of  ASC White **
**14,000 electrical devices per processor**

## Sandia ASIC Design

**Sandia ASIC Design**
**Digital circuit. ~250K Transistors.**
**Problem Setup**
**Distributed memory scalability**
**Init. Cond. : ****ROBUSTNESS!**
**Homotopy (NOX/LOCA)**
**Singleton Filtering (EpetraExt) **
**AMD Ordering (EpetraExt)**
**Mod. BILUK Precond. (Ifpack)**
**Transient : ****PERFORMANCE!**
**Dominates Run Time!**
**Communication Enhancements (Epetra)**
**Zoltan Partitioning (EpetraExt)**

## XyceTM Parallel ScalingFixed Size ASIC Problem

**Linear solver convergence dominates scalability for DCOP.**
**Transient simulation dominates overall runtime; scalable to 32 processors.**
**Scaling rolloff corresponds to ~8k devices and ~3k unknowns per processor.**

## Partitioning Issues

**Scalable communication volume (cuts)**
**Not so scalable communication count (adj procs)**
**Hierarchical nature of circuits?**
**Will comm. count plateau for bigger problems?**

**Notes:**
Large relative error values are due to small-signal noise (which shows up in the denominator for relative error).

## Load Balance/Partitioning

**Good but not great success so far...**
**New Ideas**
**Weighted Graph Partitioning**
**Improve BILU Preconditioning but keeping fill in block**
**Reduce max values of off block diagonals by several orders of magnitude for some problems**
**Multi-Constraint Partitioning**
**Balance Load(Circuit) and Solve(LinSys) Partitions**
**Hypergraph Partitioning**
**Better representation of non-symmetric systems**
**Better representation of MatVec communication**
**Demonstrated as much as 50% communication volume reduction for sample Xyce problems**

## Block Triangular Factorization

**Steady State Analog Circuit Problems are Block “REDUCIBLE”!**
**Largest Blocks found: <150**
**Novel Algorithm: O(n****b****.****s****b****3****+n****b****2.****s****b****2****)**
**Current implementation beats our fastest sparse direct solver for n>10,000**
**Ill-conditioned (>10****16****) diagonal blocks can be better managed.**

## Block Triangular Solve

- A

- 0

- Block Triangular Factorization
- (Alex Pothien’s Algorithm)

- Invert Diagonals (e.g. SVD, LU)

- Block Backsolve

## Singular Value Thresholding

| N | Num Blocks | Largest Block | Cond Est | KSparse Newton Steps | BTS
Newton Steps | KSparse
Solve time | BTS
Solve Time | KSparse
Max Norm | BTS
Max Norm |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 16 | 13 | 2 | 2.00E+10 | 20 | 12 | 3.00E-05 | 4.00E-04 | 5.00E+00 | 5.00E+00 |
| 1220 | 188 | 101 | 5.00E+15 | 50 | 45 | 7.00E-04 | 2.00E-01 | 1.00E+28 | 1.00E+04 |
| 1815 | 471 | 109 | 4.00E+12 | 61 | 55 | 2.00E-03 | 1.00E-01 | 2.00E+04 | 2.00E+04 |
| 25187 | 7401 | 79 | 1.00E+23 | FAILED | 255 | 11.5 | 3.5 | 1.00E+48 | 2.00E+12 |

**Managing Ill-Conditioned Diagonal Blocks**
**Abs/Rel Thresholding**
**Relative to Nonlinear Norm**

## BTS: What Else?

**Parallel Algorithm**
**BTF Reordering**
**Invert**
**Backsolve**
**Diagonal Block Inversion**
**Performance**
**Ill-Conditioning Management**
**Iterative Solver Preconditioning**
**Nonlinear Algorithm: Step through the diagonal block nonlinear problems**

## Future Directions

**Preconditioned Iterative Solvers**
**Multi-Level Preconditioners: pARMs, etc.**
**BTF based Preconditioner**
**Intelligent Partitioning for Preconditioning**
**Block Triangular Form**
**Parallel**
**Managing Ill-Conditioning**
**Direct Solvers (KLU, T. Davis)**
**Partitioning/Load Balance**
**HyperGraph**
**Multi-Constraint**

## Time-Parallel Multi-time PDEs

**Beta Capability in Xyce**
**Primary Infrastructure**
**To be refactored as Trilinos Pkg**
**Block Linear Algebra Manipulation**
**Fast Time Scale Discretization**
**Arbitrary Order BD and CD (FD unstable)**
**Freq. Domain to be added**

## MPDE Discretization

**Fast Time Discretization       Low Order & Coarse:**
**high error**
**oscillation in slow time scale**
**Mesh refinement study shows expected convergence**
**Win in convergence and speed by using higher order and/or greater refinement**

| N2 | Disc. | RelErr | Time(sec) |
| --- | --- | --- | --- |
| 10 | BD1 | 1.8e-1 | 46 |
|  | CD2 | 6.6e-2 | 28 |
|  | BD4 | 2.2e-2 | 27 |
|  | CD4 | 4.6e-3 | 11 |
| 40 | BD1 | 4.6e-2 | 126 |
|  | CD2 | 3.8e-3 | 29 |
|  | BD4 | 1.2e-4 | 10 |
|  | CD4 | 5.7e-5 | 7 |

**Myce Results, Todd Coffey**

## Epetra Communication

**Import/Export**
**Variable Block Communication ****[Efficient Memory Usage]**
**Efficient Buffering ****[No Dynamic Memory]**
**Direct Data Access ****[No Search]**
**Impact**
**Huge reductions in buffer memory usage for key simulations**
**Critical Impact on Xyce Milestone Problem (Permafrost)**
**Class of highly constrained problems now tractable for Salinas (C. Dohrmann)**

| Epetra Imports | Memory (kB) | Time (s) | Solve Time (s) |
| --- | --- | --- | --- |
| Original | >3,000 | ~10 | 1.1 |
| New | 220 | 0.2 | 1.1 |

## EpetraExt(ensions)

**Public Release: 3.0 & 4.0**
**Capabilities**
**Transforms:**** Singleton Filter, AMD, Remapping, Permutations**
**Matrix Matrix:**** Multiply, Add (Transpose)**
**A. Williams**
**Block Manipulation:**** Triangular Factorization, MPDE Support**
**Distributed Boundary Resolution:**** Generic Directories/Migrators**
**Zoltan Interface:**** Graph/Hypergraph Partitioning**
**Graph Coloring:**** Greedy, Lubi, DOF Ordering, Parallel**
**B. Spotz, R. Hooper**
**Epetra Parallel I/0**** **
**M. Heroux**
**Impact**
**Xyce : Critical performance/robustness for ASC Level 1 Milestone**
**Premo, Charon: finite difference coloring**
**Zoltan: partitioning linear systems**

## Graph Coloring

|  |  | # colors | # dofs | Time (s) |
| --- | --- | --- | --- | --- |
| B61
No-fins
(Unstructured
Tets) | Greedy, Largest First | 155 | 33280 | 30.2 |
|  | Greedy, Smallest First | 245 | 33280 | 26.5 |
|  | Greedy, 
Random | 150 | 33280 | 25.2 |
|  | Lubi, 
Largest First | 160 | 33280 | 24.9 |
|  | Lubi, 
Smallest First | 153 | 33280 | 28.5 |
|  | Lubi, 
Random | 156 | 33280 | 26.3 |
| Sphere-Cone
(Structured
Hexes) | Greedy, Largest First | 90 | 306820 | 69.3 |
|  | Greedy, Smallest First | 105 | 306820 | 83.8 |
|  | Greedy, 
Random | 84 | 306820 | 70.4 |
|  | Lubi, 
Largest First | 84 | 306820 | 81.8 |
|  | Lubi, 
Smallest First | 82 | 306820 | 85.0 |
|  | Lubi, 
Random | 86 | 306820 | 86.8 |

**Premo(Sierra) – Generated by Russel Hooper**

## New Capability Highlights

**Tim Davis’s KLU in AMESOS (The “****Clark Kent****” of Direct Solvers)**
**Gilbert/Peierel’s Left-Looking Sparse LU**
**Fastest direct solver for Xyce circuits**
**Block Triangular Factorization**
**Based on our research ****(D. Day)**
**Available in next Xyce release**
**Prototyping Dist. Mem. Impl.**
**Zoltan Partitioning**
**Weighted Graph Partitioning**
**edgwt(i,j) = F( |val[i][j]| )**
**Improved quality of block ILU**
**Hypergraph Partitioning**
**Improved model of communication cost**
**Direct mapping to non-symmetric matrices**
**Zoltan parallel algorithm in progress**

| Method | 1st Fac | Next Fac | LU nnz (103) | MFlops |
| --- | --- | --- | --- | --- |
| UmfPack | .440 | .257 | 372 | 2.56 |
| KSparse | 84 | 14 | 294 | 0.90 |
| KLU     w/ BTF | .545 | .02 | 201 | 0.16 |