# Presentation: 394454

## Parallel Flexible Iterative Solvers for Sparse Equation Systems from Circuit Simulation 

_**Dr.-Ing. Achim Basermann**_**, M. Nordhausen*********, Dr. Uwe Jaekel, **
- NEC Europe Ltd.
- C & C Research Laboratories (CCRLE), Sankt Augustin, Germany

- E-mail: {basermann,jaekel}@ccrl-nece.de
-               mn@tf.uni-kiel.de

**Koutaro Hachiya**
- Fundamental Design and Technology Development Group,
- Design Engineering Division, NEC Electronics Corp.
- Tamagawa, Japan

- E-mail: koutaro.hachiya@necel.com

- *Diploma student at CCRLE from Christian-Albrechts University of Kiel, Faculty of Engineering

## Introduction to circuit simulation

***x***** V**

**Resistor R = 1 ******

**Diode D**

**5 V**

**0 V**

***I*****R**

***I*****D**

## Transient analysis

## Problem of dense rows and columns (1)

**Problem of dense rows and columns (1)**

**Solution: *****Global node***** removal**

**Very sparse linear systems but some dense rows and columns**

**Problematic for: reordering, repartitioning, load balance,**
**                             ****condition**

## Problem of dense rows and columns (2)

**Real, small buffer circuit**

## Distributed Schur Complement (DSC) techniques: Definitions

**Distributed Schur Complement (DSC) techniques: Definitions**

**Distributed Matrix, 2 processors**

**Processor 1**

**Processor 2**

** ****(Y.Saad, M. Sosonkina)**

## Distributed Schur Complement

**techniques: Algorithm (1)**

**Schematic view on**
**each processor**

## DSC  inner iteration (interface variables)

**Distributed Schur Complement techniques: Algorithm (2)**

_**Advantage:**_** ****Preconditioner may change in each iteration**

**DSC ******** inner iteration (interface variables)**

_**Bi-CGSTAB:**_** ****Solve the interface system very exact ******** fixed preconditioner**

_**FGMRES:**_** ****Only a few interface iterations may be sufficient**

**Difference between  **_**GMRES**_**                and          **_**FGMRES**_

## Flexible iterative methods 

**Distributed Schur Complement techniques: Algorithm (3)**

_**Disadvantage of FGMRES:**_** ****Storage of two subspaces**

**Not critical if number of iterations is small (<10)!**

**Subspace storage can be avoided by methods with short recurrences:**

**Flexible QMR (FQMR) by D.B. Szyld and J.A. Vogel**

** ****2 matrix-vector operations**
** ****2 preconditioner applications**
** ****No subspace storage**

**1) and 2) may be become a disadvantage compared with FGMRES**
**if the number of iterations is small (<10).**

## Distributed Schur Complement techniques: Preconditioning

## Distributed Schur Complement techniques: Repartitioning

**ParMETIS partitioning for 2 processors, small buffer circuit**

** ****Proc. 1**

** ****Proc. 2**

## Distributed Schur Complement techniques: Reordering

**METIS nested dissection reordering, 2 processors, small buffer circuit**
**Goal: fill-in reduction for ILUT (threshold 10****-4**** below)**

** ****Proc. 1**

** ****Proc. 2**

## Results (1)

**Matrix from a large memory circuit simulation**

## Results (2)

**Matrix from a large memory circuit simulation, zoomed in left above**

## Results (3)

**Parallel results, ****iterative solver for original and reduced matrix****, PC cluster**

## Results (4)

**Parallel results, ****block Jacobi versus DSC preconditioning****, PC cluster**

## Results (5)

**Parallel results, ****effect of reordering and repartitioning****, PC cluster**

## Results (6)

**Parallel results, 8 processors, ****contribution of ordering methods****, fast PC cluster**

## Results (7)

**Results (7)**

**Parallel results, scalability + effect of flexibility, Athlon PC cluster**

**Circuit problem with ****89,378**** unknowns and 603,753 nonzeros**

| Time/s on p processors |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Solver | If. sol. | p = 1 | p = 2 | p = 4 | p = 8 | p = 12 | p = 16 |
| Bi-CGSTAB | Quasi-exact | 0.78 | 0.61 | 0.41 | 0.50 | 0.32 | 0.38 |
| FGMRES | Quasi-exact | 0.81 | 0.64 | 0.42 | 0.48 | 0.33 | 0.39 |
| FGMRES | 30 iter. | 0.88 | 0.67 | 0.39 | 0.27 | 0.19 | 0.18 |

## Results (8)

**Parallel results, comparison of FQMR and FGMRES, Athlon PC cluster**

** ****Circuit problem *****Sim_ys48*****: ****24,585**** unknowns, 127,695 nonzeros**
** ****Circuit problem *****ccp*****: ****89,378**** unknowns, 603,753 nonzeros**

| Time/s on p processors |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Matrix | Solver | p = 1 | p = 2 | p = 4 | p = 8 | p = 16 |
|  |  |  |  |  |  |  |
| Sim_ys48 | FQMR | 0.25 | 0.19 | 0.15 | 0.12 | 0.10 |
| Sim_ys48 | FGMRES | 0.12 | 0.09 | 0.07 | 0.05 | 0.04 |
|  |  |  |  |  |  |  |
| ccp | FQMR | 2.19 | 1.29 | 0.81 | 0.91 | 0.49 |
| ccp | FGMRES | 1.09 | 0.80 | 0.49 | 0.54 | 0.29 |

## Results (9): Execution times of NEC ́s circuit simulator MUSASI

- AMD Athlon MP 1900+ PC Cluster

**Circuit problem with 24,705 unknowns**

## Results (10): Execution times of NEC ́s circuit simulator MUSASI

**Results (10):**** Execution times of NEC ́s circuit simulator MUSASI**
- AMD Athlon MP 1900+ PC Cluster

**Circuit problem with ****89,556**** unknowns**

## Conclusions

** ****Removal of dense rows and columns necessary**
** ****Reordering and repartitioning important for DSC****   - Reordering improves load balance****   - Repartitioning keeps interface system small**
** ****Flexible iterative methods preferable for DSC preconditioning,****  FGMRES superior to FQMR for the circuit problems tested**
** ****Iterative solver distinctly superior to direct solution for complex****   large problems**
** ****DSC solver well suited for circuit simulation**

## Results (11)

|  | Original Matrix |  |  | Reduced Matrix |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Matrix | Order | #nonzeros | max. #nz per row (column) | Order | #nonzeros | max. #nz per
row (column) |
| row2m |   16570 |     127130 |       8432 (8371) |   16502 |      109731 |             632 (632) |
| 256md |   26114 |     160079 |       5321 (5339) |   26076 |      141011 |         3600 (3644) |
| Simys |   24705 |     183713 |   18920 (18920) |   24585 |      127695 |             112 (112) |
| ccp |   89556 |     760630 |   30516 (30516) |   89378 |      603753 |             324 (324) |
| circ2a | 482969 |   3912413 | 482741 (482734) | 482963 |    2750390 |                 35 (35) |

**Results (11)**
**NEC Circuit Simulation Problems**

## Results (12): Effect of Partitioning, 8 Processors

|  | Original Matrix | Reduced Matrix |
| --- | --- | --- |
| Matrix | # interface variables | # interface variables |
| row2m |                9123 |                1792 |
| 256md |              14263 |                8160 |
| Simys |              22950 |                1504 |
| ccp |              35484 |                2102 |
| circ2a |            482874 |                  481 |

**Results (12): Effect of Partitioning, 8 Processors**
**NEC Circuit Simulation Problems**

## Results (13)

**Philips Circuit Simulation Problems**
**(Wim Bomhof, ****http://www.cise.ufl.edu/~davis/sparse/Bomhof****)**

|  | Original Matrix |  |  | Reduced Matrix |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Matrix | Order | #nonzeros | max. #nz per row (column) | Order | #nonzeros | max. #nz per
row (column) |
| circuit_1 |     2624 |       35823 |       2571 (2571) |     2566 |        25360 |            135 (135) |
| circuit_2 |     4510 |       21199 |       1285 (1274) |     1262 |          9702 |            136 (136) |
| circuit_3 |   12127 |       48137 |       5682 (2305) |     7607 |        34024 |                44 (63) |
| circuit_4 |   80209 |     307604 |       8900 (6750) |    52245 |      255794 |        6749 (6750) |
| circuit_4 |              Woodbury, 1  |  |  |    52245 |      242299 |            530 (532) |
| circuit_4 |             Woodbury, 50  |  |  |    52245 |      211689 |            149 (169) |

## Results (14): Effect of Partitioning, 8 Processors

**Philips Circuit Simulation Problems**

|  | Original Matrix | Reduced Matrix |
| --- | --- | --- |
| Matrix | # interface variables | # interface variables |
| circuit_1 |                2594 |                1987 |
| circuit_2 |                1265 |                  629 |
| circuit_3 |                2688 |                  186 |
| circuit_4 |              20763 |              18334 |
| circuit_4 |   Woodbury, 1  |              10845 |
| circuit_4 |  Woodbury, 50  |                1378 |

## Results (15)

|  | Original Matrix |  |  | Reduced Matrix |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Matrix | Order | #nonzeros | max. #nz per row (column) | Order | #nonzeros | max. #nz per
row (column) |
| add20 |     2395 |        17319 |             124 (84) |      2395 |        13151 |              84 (84) |
| add32 |     4960 |        23884 |               32 (15) |      4960 |        19848 |              15 (15) |
| memplus |   17758 |      126150 |           574 (353) |    17736 |        99108 |          353 (353) |
| bcircuit |   68902 |      375558 |               34 (34) |    68902 |      375558 |              34 (34) |
| hcircuit | 105676 |      513072 |       1399 (1399) |  105592 |      506970 |          723 (723) |
| scircuit | 170998 |      958936 |           353 (353) |  170850 |      958370 |          353 (353) |

**Results (15)**
**Motorola Circuit Simulation Problems**
**(Steve Hamm, ****http://www.cise.ufl.edu/~davis/sparse/Hamm****)**

## Results (16): Effect of Partitioning, 8 Processors

**Motorola Circuit Simulation Problems**

|  | Original Matrix | Reduced Matrix |
| --- | --- | --- |
| Matrix | # interface variables | # interface variables |
| add20 |                  449 |                  449 |
| add32 |                    28 |                    28 |
| memplus |                4544 |                4576 |
| bcircuit |                  662 |                  662 |
| hcircuit |                2490 |                  975 |
| scircuit |                1874 |                1700   |

**Zeros not**
**stored**