5.4 Konvergenzverhalten



next up previous contents
Next: 6 Vektor- und Parallelrechner-Implementationen Up: 5 Lineare Gleichungssysteme in Previous: 5.3.3 Polynomiale Vorkonditionierung

5.4 Konvergenzverhalten

 

In diesem Abschnitt soll das Konvergenzverhalten der verschiedenen vorkonditionierten Iterations-Verfahren anhand von Beispielen verglichen werden.
Es wurden zwei MOSFETs mit MINIMOS (Version 5.0) dreidimensional simuliert und die Koeffizientenmatrizen der Elektronen und Löcher abgespeichert. Da das finite Differenzengitter dieser Beispiele klein ist, wurden die Gleichungssysteme mit einem direkten Lösungs-Verfahren gelöst, und die Lösung wurde ebenfalls abgespeichert. Als Fehlernorm wurde bei allen Untersuchungen und Grafiken die -Norm des relativen Lösungsfehlers

benützt. Als Abbruch der Iteration wurde eine Schranke von gewählt. Diese heuristische Zahl ist auch der Defaultwert im Simulator MINIMOS.
Der verwendete Computer war eine VAX 8800. Die Iterationen mit CG und SCG wurden in vierfacher Genauigkeit (Maschinengenauigkeit ), die verbleibenden in doppelter Genauigkeit (Maschinengenauigkeit ) durchgeführt.
Beim ersten Beispiel (MOSFET-1) handelt es sich um einen MOS-Transistor mit nichtplanarer Geometrie (Bird's Beak, Recessed-Channel). Die Kanallänge ist , die Kanalweite . Der berechnete Arbeitspunkt liegt im Unterschwellspannungsbereich (=, =). Das finite Differenzengitter wird selbst-adaptiv erzeugt und hat für die Kontinuitätsgleichungen die Dimensionen [Die erste Achse ist in Kanalrichtung, die zweite weist in das Substrat, die dritte in Kanalweitenrichtung]. Aufgrund der kleinen Kontaktspannungen ist der Stromfluß gering (=, =) und das System in der Nähe des thermischen Gleichgewichts. Der Gummel-Algorithmus konvergiert in Iterationen. Keine Abweichung der Ladungsträgertemperaturen von der Umgebungstemperatur wird berücksichtigt. Die nichtsymmetrischen Koeffizientenmatrizen können symmetrisiert und mit dem klassischen CG-Verfahren gelöst werden. Die Iterationszahlen des klassischen CG-Algorithmus werden mit der symmetrisierten CG-Variante (SCG) sowie mit CGS verglichen. Ein weiterer Parameter des Konvergenztestes ist der Füllgrad der unvollständigen Faktorisierung. Hier wurde nur die Stufe (keine zusätzliche Füllung außerhalb des Matrix-Spärlichkeitsmusters) und Stufe (je eine Diagonale neben den existierenden Matrix-Diagonalen) gewählt. Faktorisierungen höherer Füllstufe wurden ebenfalls getestet, sie bringen jedoch keinen Rechenzeitgewinn. Der CG-Algorithmus liefert gleichzeitig Schätzwerte für die extremalen Eigenwerte [,] der vorkonditionierten Koeffizientenmatrix [75]. Daraus läßt sich die spektrale Konditionszahl =/, abschätzen, die wiederum mit Hilfe von Gleichung (5.27) einen groben Richtwert für die erforderliche Iterationszahl gibt. Diese Schätzwerte liegen zu hoch, die Abhängigkeit der Iterationszahl von der Wurzel der spektralen Konditionszahl gemäß Formel (5.27) ist aber ausgeprägt.
Die Tabellen 5.6 und 5.7 enthalten Iterationszahlen aller Gummel-Iterationen für die Kontinuitätsgleichungen der Elektronen- und Löcherströme.

  
Tabelle 5.6: Löcherstrom-Kontinuitätsgleichungen von MOSFET-1.

  
Tabelle 5.7: Elektronenstrom-Kontinuitätsgleichungen von MOSFET-1.

Für die Löcherstrom-Kontinuitätsgleichung und ILU() konvergiert CGS ab N=2 ca. doppelt so schnell wie CG, wobei nicht vergessen werden darf, daß CGS ungefähr den doppelten arithmetischen Aufwand dafür benötigt.
In der Abbildung 5.1 sind Konvergenzkurven der ersten Gummel-Iteration für beide Kontinuitätsgleichungen gezeichnet. Dabei ist zu bemerken, daß die Iterationszahlen, die aus diesen Kurven abzulesen sind, nicht exakt mit den Zahlen aus Tabelle 5.6 und 5.7 übereinstimmen. Die Begründung liegt an den unterschiedlichen Abbruchkriterien. Während in Abbildung 5.1 die 2-Normen des wirklichen relativen Fehlers eingetragen sind, wird im Simulator MINIMOS eine Norm verwendet, welche die 2-Norm und den ,,Winkel`` zwischen zwei aufeinanderfolgenden Approximationen des Lösungsvektors vergleicht [85].

  
Abbildung: CG(), SCG() und CGS() für den Parameter =, im Vergleich; Löcherstrom-Kontinuitätsgleichung (oberes Bild) und Elektronenstrom-Kontinuitätsgleichung (unteres Bild). Erste Gummel-Iteration von MOSFET-1.


Als zweites Beispiel werden Ergebnisse einer MOSFET-Simulation gezeigt, in der lokale Ladungsträgertemperaturen eine Rolle spielengif. Es handelt sich um einen nichtplanaren -Kanal-MOSFET (==) mit den Spannungen =, = und den resultierenden Strömen = und =. Die linearen Systeme der diskreten Kontinuitätsgleichungen sind nun nicht mehr symmetrisierbar. Für diese Simulation wurde das wiedergestartete GMRES-Verfahren (=) und wiederum CGS verwendet. Dieselben Vorkonditionierungstypen wie im vorhergehenden Beispiel wurden angewendet.

  
Tabelle 5.8: Iterationszahlen beider Kontinuitätsgleichungen von MOSFET-2 im Ladungsträgertemperatur-Relaxationszyklus.

Tabelle 5.8 enthält die Iterationszahlen für den Ladungsträgertemperatur-Relaxationszyklus, der in Gummel-Iterationen konvergiert. Zu bemerken ist, daß Gummel-Iterationen im sogenannten Avalanche-Modus nötig waren, um eine geeignete Anfangslösung für den Ladungsträgertemperatur-Relaxationszyklus zu schaffen. In der Abbildung 5.2 sind Konvergenzkurven für die linearen Systeme während der ersten Ladungsträgertemperatur-Iteration geplottet. CGS konvergiert wesentlich schneller als GMRES, die Konvergenzkurven von CGS tragen jedoch insbesondere für die Löcher stellenweise einen chaotischen Charakter, während GMRES monoton konvergiert.

  
Abbildung 5.2: Vergleich von CGS() und GMRES(,) mit dem Parameter =,; MOSFET-2, erste Gummel-Iteration. Löcherstrom-Kontinuitätsgleichung (oberes Bild) und Elektronenstrom-Kontinuitätsgleichung (unteres Bild).


In Abbildung 5.3 ist ein Vergleich von CGS und BiCGSTAB in Zusammenwirkung mit massiv-parallelisierbaren Vorkonditionierungs-Verfahren zu sehen (Reduziertes System - RS, Diagonale Skalierung - JA, Least-Squares-Jacobi-Polynome - LS() mit =,). Die wesentliche Verbesserung von BiCGSTAB gegenüber CGS hinsichtlich Glattheit der Konvergenz wird besonders deutlich. Die mittlere Konvergenzgeschwindigkeit beider Algorithmen ist gleich (Löcherstrom-Kontinuitätsgleichung von MOSFET-1, erste Gummel-Iteration). Um die Konvergenzgeschwindigkeit der mit ILU() vorkonditionierten Algorithmen zu erreichen, ist - für dieses Beispiel - ein Jacobi-Polynom etwa zehnten Grades vonnöten. Die Evaluierung eines solchen benötigt zehn mal so viel Zeit verglichen mit dem nicht vorkonditionierten Algorithmus. Die Vorteilhaftigkeit von LS-Vorkonditionierung ist in diesem Lichte fraglich. Die Stärke der LS-Vorkonditionierer liegt nur darin, daß keine inneren Produkte, deren Auswertung auf einem parallelen System globale Kommunikation erfordert, benötigt werden. Wie im Abschnitt 6.2 noch erläutert werden wird, kann die Berechnung innerer Produkte auf einem massiv-parallelen System (wie z.B. der ,,Connection Machine``) mit hoher Geschwindigkeit erfolgen. Ein Einsatzbereich der polynomialen Vorkonditionierung ist nur dann gegeben, wenn globale Kommunikation wesentlich teurer ist als lokale.

  
Abbildung 5.3: CGS (oberes Bild) im Unterschied zu BiCGSTAB (unteres Bild) mit verschiedener Vorkonditionierung. Die Konvergenz ist für BiCGSTAB wesentlich glatter (Löcherstrom-Kontinuitätsgleichung, 1.Gummel-Iteration, MOSFET-1).

  
Tabelle: CGS mit massiv-parallelisierbarer Vorkonditionierung. Kontinuitätsgleichung des Löcherstroms, MOSFET-2. Bindestriche kennzeichnen Fälle, in denen das vorgeschriebene Abbruchkriterium in Iterationen nicht erreicht wurde.

  
Tabelle 5.10: CGS mit massiv-parallelisierbarer Vorkonditionierung. Kontinuitätsgleichung des Elektronenstroms, MOSFET-2. Bindestriche kennzeichnen Fälle, in denen das vorgeschriebene Abbruchkriterium in Iterationen nicht erreicht wurde.

In den Tabellen 5.9 und 5.10 werden Iterationszahlen von CGS in Zusammenwirkung mit massiv-parallelisierbaren Vorkonditionierungs-Verfahren gezeigt: Neumann Polynome vom Grad und NEU1, NEU2, das reduzierte System RS und eine Vierfarben-ILU-Faktorisierung MC(). Diese Untersuchung wurde mit dem Gleichungslöser-Simulationspaket NSPCG [75] durchgeführt. Die Vierfarbenumordnung entsteht durch eine zyklische, symmetrische Permutation der vier Farben in einem -Würfel. Ein Querstrich in den Tabellen signalisiert einen CGS-Zusammenbruch. In diesen Fällen wird ein iterativer Parameter (inneres Produkt) kleiner als eine vorgebbare Schwelle (hier Maschinengenauigkeit). Allerdings kommt es zu diesen Zusammenbrüchen erst, wenn die Iteration bereits ein hohes Maß an Genauigkeit erreicht hat. Die iterativ gefundene Lösung ist zumeist noch brauchbar zur Fortsetzung des nichtlinearen Gleichungslösers.
Alle parallelisierbaren Vorkonditionierungs-Verfahren konvergieren wesentlich langsamer als ILU(). Die beste Konvergenzrate zeigt das Multicolor-Ordnungs-Verfahren mit 4 Farben. Allerdings ist die Vektorlänge dieses Verfahrens halb so groß wie bei RS und vier mal so kurz als bei den polynomialen Vorkonditionierern. Hinzu kommt noch der Aufwand für die Faktorisierung, der bei den polynomialen Verfahren wegfällt, und der Aufwand bei den Rücksubstitutionen, der doppelt so viele sequentielle Schritte erfordert wie beim reduzierten System. Aus diesem Grund ist dieses Vierfarben-Verfahren für Computer mit einer Anzahl von Prozessoren, die in der Größenordnung der Gitterpunkte liegt, nicht vorteilhaft. Das reduzierte System ist dagegen eine brauchbare Lösung, die sich daneben auch durch besondere Einfachheit auszeichnet.



next up previous contents
Next: 6 Vektor- und Parallelrechner-Implementationen Up: 5 Lineare Gleichungssysteme in Previous: 5.3.3 Polynomiale Vorkonditionierung



Martin Stiftinger
Fri Oct 14 21:33:54 MET 1994