Parallelizing conjugate gradient for the CRAY X-MP
Die Arbeit gliedert sich in zwei etwa gleich große Teile. Zunächst wird gezeigt, welche Hilfsmittel zur Erzeugung paralleler Programme auf dem System CRAY-XMP dem Benutzer zur Verfügung gestellt werden (zur Prozeßgenerierung, Kommunikation und Synchronisation). Dabei wird deutlich herausgearbeitet, welche zusätzlichen Laufzeiten in Kauf genommen werden müssen. Besonders die Verluste, die sich durch die Konflikte am zentralen Speicher ergeben, erweisen sich bei den untersuchten Algorithmen als gravierend (etwa 30 \% bei 4 Prozessoren). Im zweiten Teil wird auf die Parallelisierung (im Sinne von Nebenläufigkeit) der konjugierten Gradientenmethode mit Vorkonditionierung eingegangen. Dabei wird eine Datenpartitionierungstechnik (Vektoren werden abschnittsweise verschiedenen Prozessoren zugeordnet) angewendet. Gemessene Laufzeiten werden für mehrere Konditionierungstechniken angegeben: -- mittels Diagonalmatrix, -- durch polynominale Approximation der Inversen, -- und durch eine unvollständige Cholesky-Zerlegung, die durch Verwendung zusätzlicher Nullelemente so modifiziert wird, daß das zu invertierende Gleichungssystem in mehrere (pro Prozessor ein) unabhängige Gleichungssysteme zerfällt. Die Arbeit ist lesenswert, aber auf zwei Nachteile muß hingewiesen werden: die Messungen streuen stark und einige Algorithmenteile sind offensichtlich nicht ganz korrekt in eine leserverständliche Form transformiert worden.
preconditioned conjugate gradient algorithm
scientific article; zbMATH DE number 3945252