Abschlussbericht

Abschlussbericht
Projekt 2:
Lösung von großen Gleichungssystemen auf
Computerclustern
TECHNISCHE UNIVERSITÄT GRAZ
Institut für Theoretische Geodäsie
und Satellitengeodäsie
Projekt 2
LV 508.538, SS2011
Andreas Kvas, 0730611
Zusammenfassung
Ziel der vorliegenden Arbeit ist es, eine qualifizierte Aussage über die Eignung der
numerischen Bibliothek ScaLAPACK für die Lösung großer Gleichungssysteme zu treffen.
Der Schwerpunkt liegt dabei auf Systemen mit symmetrischen, positiv definiten Koeffizientenmatrizen, wie sie zum Beispiel im Ausgleich nach kleinsten Quadraten entstehen.
Vor diesem Hintergrund findet ebenfalls eine Untersuchung der Routinen zur expliziten
Invertierung von Matrizen statt. Zusätzlich werden alternative Speicherschemata, die es
durch Ausnutzung spezieller Matrixstrukturen wie Symmetrie oder Dreiecksform erlauben
die Speicherauslastung zu verringern, beschrieben und teilweise implementiert.
Im Zuge des Projekts entstand eine C-Bibliothek, deren Routinen die Grundlage der
Evaluierung darstellen.
Abstract
In this technical report a qualified assessment of the numerical linear algebra library
ScaLAPACK with respect to the ability of solving large linear equation systems is made.
Emphasis lies on systems with symmetric, positive definite coefficient matrices; e.g. normal
equation matrices encountered in least squares adjustment. Due to this fact routines for
explicit computation of the matrix inverse are also examined. Additionally alternative
storage schemes which allow the reduction of storage overhead are described and a basic
set of routines is implemented.
In the course of this project, a C library was designed and implemented whose routines
serve as basis for the evalution.
1
Inhaltsverzeichnis
1 Einleitung
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Zielsetzung der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Scientific Computing
2.1 Parallelrechnerarchitektur . . . . . . . .
2.2 Paralleles Rechnen . . . . . . . . . . . .
2.2.1 Parallel Virtual Machine (PVM)
2.2.2 Message Passing Interface . . . .
2.3 Numerische Lineare Algebra . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 ScaLAPACK Softwarekomponenten
3.1 Message Passing Primitives . . . . . . . . . . . . .
3.2 Basic Linear Algebra Communication Subprograms
3.3 Basic Linear Algebra Subprograms (BLAS) . . . .
3.3.1 BLAS Technical Forum Standard . . . . . .
3.3.2 ATLAS . . . . . . . . . . . . . . . . . . . .
3.3.3 Parallelisierung der BLAS . . . . . . . . . .
3.4 LAPACK . . . . . . . . . . . . . . . . . . . . . . . .
4 Matrix Speicherschemata
4.1 Zweidimensionale block-zyklische Verteilung
4.2 ScaLAPACK Standardspeicherschema . . . .
4.3 Distributed Packed Storage . . . . . . . . .
4.3.1 Definitionen . . . . . . . . . . . . . .
4.3.2 Implementierte Algorithmen . . . . .
4.4 ScaLAPACK Packed Storage Extension . . .
5 Praktische Untersuchungen
5.1 Beschreibung der verwendeten
5.2 Performance-Metriken . . . .
5.3 Ergebnisse . . . . . . . . . . .
5.3.1 Parameteroptimierung
5.3.2 Skalierbarkeit . . . . .
5.3.3 Performance . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . .
(BLACS)
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
4
.
.
.
.
.
6
6
8
8
9
10
.
.
.
.
.
.
.
10
11
11
12
12
12
15
15
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
15
17
17
17
19
20
Hard- und Software
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
21
22
23
23
25
26
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Zusammenfassung und Ausblick
27
Referenzen
28
A Zeitplan
30
B CSL Reference Manual
31
2
Verwendete Notationen und Abkürzungen
Matrixnotation
A ∈ M(M × N, R)
Eine reelle Matrix der Größe M × N
aij
Element in Zeile i und Spalte j der Matrix A

A11
 ..
 .
AM 1

· · · A1N
.. 
..
.
. 
· · · AM N
Aij
Blockdarstellung der Matrix A
Submatrix in Blockzeile i und Blockspalte j
der Matrix A
Algorithmen und Pseudocode
k = 0 : 10
k läuft von 0 bis 10 mit Inkrement 1;
k = {0, 1, 2, · · · , 10}
k = 0 : 2 : 10
k läuft von 0 bis 10 mit Inkrement 2;
k = {0, 2, 4, · · · , 10}
C ← αAT A + βC
Matrixoperation αAT A + βC;
C wird mit dem Ergebnis überschrieben
ScaLAPACK
MB , NB
Blockgröße; B ∈ M(MB × NB , R)
P
Anzahl der aktiven Prozesse
PR × PC
Prozessgittergröße
mlocal
Zeilen der lokalen Submatrix eines Prozesses
nlocal
Spalten der lokalen Submatrix eines Prozesses
3
1
Einleitung
1.1
Motivation
Die Bestimmung der geometrischen Form und zeitlichen Veränderung des Erdschwerefeldes ist
eine wesentliche Grundlage für ein besseres Verständnis der physikalischen Vorgänge in und
auf unserem Planeten.
Einen wichtigen Beitrag dazu liefert die Satellitengeodäsie mit Missionen wie CHAMP
(CHAllenging Minisatellite Payload, Reigber et al. (2001)), GRACE (Gravity Recovery
And Climate Experiment, Tapley et al. (2004)) oder GOCE (Gravity field and steady-state
Ocean Circulation Explorer, Drinkwater et al. (2007)), deren globale Daten es erst ermöglichen entsprechende Schwerefeldmodelle zu berechnen.
Da die Verbesserung von Messverfahren und -systemen genauere Lösungen ermöglichen, werden auf Grund der damit verbundenen steigenden Problemgrößen im Zuge der Auswertung
sehr hohe Anforderungen an Hard- und Software gestellt. Dieser Umstand führt dazu, dass
die entstehenden Gleichungssysteme in der Praxis nur noch auf Netzwerken von Computern
(Computerclustern) und mit hoch optimierten numerischen Bibliotheken in annehmbarer Zeit
gelöst werden können.
Neben proprietären und streng hardwarespezifischen Softwarepaketen (z.B. Intel MKL, IBM
ESSL, AMD Core Math Library) existiert mit ScaLAPACK und den zu Grunde liegenden Komponenten eine portable, freie Zusammenstellung von Routinen mit hohem Abstraktionsgrad
bezüglich Parallelisierung zur Behandlung der oben genannten Problemstellungen.
Diese Eigenschaften rechtfertigen eine nähere Betrachtung und Evaluierung der Bibliothek.
1.2
Zielsetzung der Arbeit
Das Ziel der vorliegenden Arbeit ist es, eine qualifizierte Aussage über die Eignung von ScaLAPACK für Problemstellungen in der Satellitengeodäsie zu treffen.
Der Schwerpunkt liegt dabei auf der Lösung von symmetrischen, positiv definiten Gleichungssystemen wie sie z.B. im Laufe eines Ausgleichs nach kleinsten Quadraten auftreten, sowie auf
der expliziten Berechnung der inversen Koeffizientenmatrix.
Als Grundlage für die Evaluierung der Bibliothek werden folgende Arbeitsschritte systematisch
abgearbeitet.
1. Entwicklung von Benchmark-Tests
Als Fundament für die späteren Untersuchungen von ScaLAPACK dienen Test- und Hilfsroutinen (d.h. Lösung linearer Gleichungssysteme unter Vorgabe bestimmter Parameter,
File-Handling) die auf einem Desktop-PC implementiert, getestet und zu automatisierten Benchmarkings zusammengefasst werden.
2. Allgemeine Laufzeitoptimierung
Auf Basis der implementierten Benchmarkings werden die steuerbaren Parameter der
Bibliothek optimiert, um bestmögliche Performance erzielen zu können.
3. Beispielhafte Implementierung realer Anwendungen
Im abschließenden Abreitsschritt wird das Verhalten von ScaLAPACK bei realitätsnahen
Problemstellungen getestet.
4
Die Arbeit ist wie folgt aufgebaut. Kapitel 2 gibt eine Einführung in die theoretischen Hintergründe wissenschaftlichen Rechnens. Die Schwerpunkte liegen dabei auf Parallelrechnerarchitektur, Parallelisierung von Software und numerischer linearer Algebra.
In Kapitel 3 wird die Softwarehierarchie von ScaLAPACK vorgestellt und eine detaillierte Beschreibung der einzelnen Komponenten gegeben. Zusätzlich wird anhand eines Vergleichs verschiedener numerischer Bibliotheken die Bedeutung von Hardwareoptimierung für effizientes
Rechnen gezeigt.
Die in ScaLAPACK verwendete block-zyklische Verteilung von Matrixelementen auf die einzelnen Prozesse werden in Kapitel 4 erörtert. Darüber hinaus werden Speicherschemata, die
spezielle Strukturen von Matrizen wie Symmetrie oder Dreicksform ausnützen und damit den
Speicherbedarf verringern, vorgestellt.
Die Ergebnisse der Untersuchungen der Eignung von ScaLAPACK für die Lösung großer Gleichungssysteme finden sich in Kapitel 5.
Schließlich wird die Arbeit mit einer Zusammenfassung der Evaluierung, sowie einem Ausblick
auf weiterführende Arbeiten abgeschlossen.
5
2
Scientific Computing
2.1
Parallelrechnerarchitektur
Obwohl die Geschwindigkeit von Computerprozessoren zunimmt, verlangt die komplexer werdende Modellierung von Phänomenen in allen naturwissenschaftlichen Disziplinen nach immer
schnellerer Hardware. Da der Entwicklung von leistungsfähigeren Prozessoren und schnellerem
Speicher jedoch physikalische und ökonomische Grenzen gesetzt sind (Foster (1995)), kann der
Bedarf an mehr Rechenleistung nur mit Hilfe von Rechnerverbünden gedeckt werden.
Grundsätzlich lassen sich Parallelrechner grob in zwei Gruppen aufteilen: Systeme mit gemeinsamen physischen Speicher und Adressraum (shared memory systems) und Systeme in denen
jede CPU ihren eigenen Speicher und Adressraum besitzt; Lesen und Schreiben von entfernten
Speicheradressen ist nur über explizite Kommunikation möglich (distributed memory systems).
0x3A28213A
0x6339392C
0x7363682E
Abbildung 1: Der von Neumann Computer. Ein Prozessor führt Lese- und Schreiboperationen
auf einem angebauten Speichermodul aus (nach Tanenbaum (1999)).
Ausgehend vom Computermodell nach von Neumann (siehe Abbildung 1) sollen nun die am
weit verbreitetsten Parallelrechnerarchitekturen erörtert werden.
• Multicomputer
Kommunikationsnetz
Abbildung 2: Schematische Darstellung eines Multicomputers.
6
Der Multicomputer setzt sich aus mehreren von Neumann Computern (sogennanten
Knoten), welche über ein Netzwerk verbunden sind, zusammen. Jeder Knoten führt eine
eigene Sequenz von Instruktionen, wie Lesen und Schreiben des lokalen Speichers oder
Senden und Empfangen von Nachrichten, aus. Ein Charakteristikum des Multicomputers
ist die Eigenschaft, dass Zugriffe auf entfernten Speicher zeitintensiver sind, als jene auf
den lokalen Speicher des CPUs. Die Eigenschaft wird als locality bezeichnet (Foster
(1995)).
Eine Sonderform dieses Prinzips stellen distributed shared memory systems dar. Dabei
wird den verteilten Speichermodulen eines Multicomputers z.B. auf Betriebssystemlevel
ein virtueller Adressraum übergeordnet. Für den Benutzer stellt sich das verteilte System
dann als einzelne Maschine dar.
• Multiprozessor
In einem Multiprozessor teilen sich alle Prozessoren einen Hauptspeicher mit gemeinsamen virtuellen Adressraum (shared memory system, vgl Abbildung 3).
Hauptspeicher
Abbildung 3: Schematische Darstellung eines Shared-Memory Systems.
Diese Architektur ermöglicht die Kommunikation zwischen einzelnen Prozessoren durch
einfache Schreibe- und Leseinstruktionen im Hauptspeicher. Deshalb ergibt dieser Ansatz
ein einfaches Modell für Softwareentwickler, da im Vergleich zu verteilten Systemen
weniger Koordination zwischen den CPUs notwendig ist.
Den großen Nachteil dieser Maschinen stellt dabei die aufwendige (technisch und wirtschaftlich) Herstellung, sowie die begrenzte Skalierbarkeit dar (Tanenbaum (1999)).
• Network of Workstations
Abschließend seien hier noch die Network of Workstations angeführt. Dieses Prinzip
basiert auf der Verwendung von bereits vorhandener Infrastruktur (z.B. gewöhnliche
Desktop-Rechner) für die Lösung von numerischen Problemen.
Ein Projekt, das sich auf die effiziente Nutzung dieser Systeme auf dem Software-Level
konzentriert, wird im folgenden Kapitel vorgestellt.
7
2.2
Paralleles Rechnen
Um die in Kapitel 2.1 beschriebenen Rechnerarchitekturen optimal nutzen zu können, bedarf es einer entsprechenden Anpassung der auszuführenden Programme. Insbesondere die
Kommunikation zwischen einzelnen Prozessen und deren Synchronisation erfordern spezielle
Ansätze.
Grundsätzlich betrachtet bieten Kommunikationsbibliotheken neben Routinen zur expliziten
Steuerung von Prozessen zwei Message Passing Primitives die Daten und Instruktionsaustausch ermöglichen: send und receive.
Diese liegen meist in unterschiedlicher Semantik vor:
• Synchronisierter Nachrichtenaustausch
Wird von einem Prozess eine Nachricht mittels send übertragen, so wird dieser angehalten (geblockt) bis von einem weiteren Prozess ein entsprechendes receive ausgeführt
wurde. Erst nach der korrekter Ankunft der Nachricht wird der Sender wieder freigegeben.
Obwohl diese Methode vollständig ohne Bufferung auskommt, hat sie den groben Nachteil, dass durch das Stoppen der Senderprozesse u.U. große Performanceeinbußen hinzunehmen sind.
• Buffered Message Passing
Die Zwischenspeicherung von übertragenen Nachrichten erlaubt es einem Prozess nach
einem send sofort weitere Instruktionen auszuführen, und seinen eigenen Nachrichtenbuffer wieder zu verwenden. Dieses Schema verringert den Zeitraum in welchem der
Sender gelockt wird, bietet jedoch keine Möglichkeit zu überprüfen, ob die Nachricht
tatsächlich am Ziel angekommen ist.
• Nonblocking Message Passing
Im Nonblocking Message Passing wird die Verwaltung der einzelnen send Aufrufe dem
Betriebssystem übertragen. Der Nachrichtenbuffer des Senderprozesses wird dabei jedoch
nicht sofort freigegeben, was bedeutet, dass eine Abfrage vor dem Senden einer weiteren
Nachricht nötig wird ob dieser wieder verwendet werden darf. Eine Folge dieses Ansatzes
ist eine erhöhte Komplexität der Kommunikationssoftware.
In den folgenden Abschnitten sollen nun zwei verbreitete Kommunikationsmodelle vorgestellt
werden.
2.2.1
Parallel Virtual Machine (PVM)
Das Parallel Virtual Machine Projekt stellt eine Sammlung von Software-Tools dar, die es dem
Benutzer ermöglichen Netzwerke von heterogenen Computern für parallele Programmierung
zu nützen.
Das System lässt sich in zwei Teile aufspalten; ein Programm das auf jedem Computer der an
den Berechnungen teilnimmt im Hintergrund ausgeführt wird (nach der UNIX-Nomenklatur
als daemon bezeichnet) und eine Bibliothek von Routinen, welche die Steuerung der einzelnen
Prozesse zur Laufzeit ermöglicht.
Das Programmiermodell von PVM basiert auf der Aufteilung eines Problems in einzelne Aufgaben. Diese liegen in der Ausführung unterschiedlicher Funktionen (functional parallelism)
8
oder in der, für wissenschaftliches Rechnen interessanteren, Manipulation von lokalen Daten
(data parallelism).
Die Kommunikation zwischen den Prozessen wird über expliziten, geblockten Austausch von
Nachrichten (Daten oder Instruktionen) durchgeführt.
Neben send und receive stehen dem User daraus abgeleitete Kommunikationsroutinen wie
Broad- und Multicasts zu Verfügung.
Eine ausführliche Beschreibung des Projekts findet sich in Geist et al. (1994).
2.2.2
Message Passing Interface
Die zweite weit verbreitete Kommunikationssoftware für Multicomputer stellen Implementierung des Message Passing Interface Standards (MPI) dar. Diese bieten, im Vergleich zu PVM,
weitaus vielfältigere und komplexere Routinen zum Nachrichtenaustausch bzw. zur Prozessverwaltung dar.
MPI basiert auf vier Konzepten (Tanenbaum (1999)):
• Communicators
Ein sogenannter MPI Communicator setzt sich aus einer Gruppe von Prozessen die
sich in einem gemeinsamen Kontext (eine Kennung die eindeutige Zuordnung ermöglicht) zusammen. Dieses Prinzip erlaubt die Aufspaltung der vorhandenen Prozesse in
Untergruppen, die sich auch gegebenenfalls überlappen können.
• Message Data Types
Die mit MPI übertragenen Nachrichten besitzen einen spezifischen Datentyp. Neben
den elementaren Datentypen wie Ganz- oder Gleitkommazahlen, werden von den im
MPI Standard definierten Routinen ebenfalls daraus abgeleitete bzw. benutzerdefinierte
Typen unterstützt.
• Communication Operations
Anhand eines einfachen send Befehls soll nun die Struktur der MPI Kommunikationsroutinen erörtert werden.
MPI_Send ( b u f f e r , count , MPI_DOUBLE, d e s t i n a t i o n , tag , a c t i v e ) ;
Im obigen Beispiel wird ein Datenpaket buffer, welches aus count Elementen vom Typ
MPI_DOUBLE besteht, an den Prozess mit dem linearen Index destination im Kontext
active gesendet. Zusätzlich besitzen MPI Nachrichten einen sogenannten tag. Dieser
ermöglicht Typisierung und damit eine Selektion auf der Empfängerseite.
Sämtliche im Message Passing Standard definierten Routinen zum Nachrichtenaustausch
unterstützen alle unter Abschnitt 2.2 angeführten Kommunikationsmodi.
• Virtual Topologies
Die virtuellen Topologien erlauben es Prozesse in Baumstrukturen, Ringen, zwei- bzw.
dreidimensionalen Gittern sowie als Torus anzuordnen. Diese Funktionalität bietet die
Möglichkeit häufig genutzte Kommunikationspfade einfacher darzustellen und damit die
Kommunikation zu erleichtern.
9
2.3
Numerische Lineare Algebra
Für die effiziente Lösung von numerischen Problemen auf Computern spielt neben der reinen
Rechenleistung (bzw. die Gleitkommaoperationen pro Cycle) des Prozessors u.a. die Dauer
von einzelnen Speicherzugriffen eine entscheidende Rolle (Tanenbaum (1999)).
Da schneller Speicher jedoch kostenintensiv ist, besitzen moderne Computern in der Regel eine
hierachische Speicherstruktur, in der sich Größe und Geschwindigkeit indirekt proportional
gegenüber stehen (vgl. Abbildung 4).
Cache
Arbeitsspeicher
Geschwindigket
Register
Festplatte
Abbildung 4: Schematische Darstellung der hierachischen Speicherstruktur eines Computers.
Während der Laufzeit befinden sich die zu bearbeitenden Daten in der Regel im Arbeitsspeicher des Rechners, weshalb dem Cache eine Sonderrolle zufällt. Dieser ermöglicht es bei effizienter Nutzung die relativ gesehen geringere Geschwindigkeit des Hauptspeichers zu maskieren.
Die Verwaltung des Caches basiert dabei auf dem sogennanten Lokalitätsprinzip (Tanenbaum
(1999)) welches besagt, dass bereits gelesene bzw. benachbarte Daten mit höherer Wahrscheinlichkeit wiederverwendet werden als jene die weiter entfernt im Speicher liegen. Aus diesem
Grund sind Speicher und Cache in Blöcke mit fixer Größe aufgeteilt, die als cache lines bezeichnet werden. Benötigt der Prozessor nun sich an einer bestimmten Speicheradresse befindliche
Daten, wird zusätzlich die gesamte line in den Cache geladen.
Für die Entwicklung von numerischer Software bedeutet dies, dass die Organisation der Daten
(d.h. die Organisation der Matrixelemente) im Speicher und die Anpassung der Algorithmen
an die ausführende Hardware fundamentale Aufgaben darstellen.
3
ScaLAPACK Softwarekomponenten
In den folgenden Abschnitten sollen die Softwarekomponenten (siehe Abbildung 5) der ScaLAPACK Bibliothek kurz beschrieben werden.
10
ScaLAPACK
PBLAS
LAPACK
BLACS
BLAS
Message Passing Primitives
Abbildung 5: ScaLAPACK Softwarehierachie.
3.1
Message Passing Primitives
Die Kommunikation zwischen den einzelnen Prozessen innerhalb der ScaLAPACK Routinen
kann grundsätzlich über zwei Softwarepakete passieren:
• Parallel Virtual Machine
• Message Passing Interface
Deren Funktionsweise und Eigenschaften werden in Kapitel 2 erörtert. Für das vorliegende
Projekt wurden als Kommunikationsbibliothek mit OpenMPI eine Implementierung des Message Passing Interface Standards verwendet. Diese erlaubte es auf Grund der weitreichenden
Funktionalität von MPI ebenfalls effiziente Routinen zum Lesen und Schreiben von Matrizen
zu implementieren.
3.2
Basic Linear Algebra Communication Subprograms (BLACS)
Die BLACS bieten dem Entwickler einen, auf Anwendungen der linearen Algebra zugeschnittenen, höheren Abstraktionsgrad bezüglich der Kommunikationen zwischen Prozessen. In der
Praxis bedeutet dies, dass der Datenaustausch via Send/Receive, auf dem Array-Level bzw.
Block-Level passiert.
Dieser Ansatz bietet folgende Vorteile (Dongarra und Whaley (1997)):
• Einfachere Implementierung
Kommunikation muss nicht zwangsweise auf dem Byte-Level durchgeführt werden.
• Zugeschnitten auf numerische Lineare Algebra
Durch die höhere Abstraktion der Kommunikation zwischen den Prozessen wird die
Anwendung in numerischen Programmen erleichtert.
11
• Portabilität
Da, wie auch z.B. bei den Basic Linear Algebra Subprograms 3.3, ein einheitliches Interface für die einzelnen Routinen festgelegt ist, ermöglichen die BLACS eine Portierung
auf andere Systeme.
3.3
3.3.1
Basic Linear Algebra Subprograms (BLAS)
BLAS Technical Forum Standard
Um die Modularität und Portierbarkeit numerischer Software zu gewährleisten wurden bereits
sehr früh standardisierte Interfaces für Vektor-Vektor (Lawson et al. (1979)) und MatrixMatrix Operationen (Dongarra et al. (1988)) vorgeschlagen. Das Ergebnis dieser Arbeiten
ist die Spezifikation einer Kollektion von Routinen die im Basic Linear Algebra Subprograms
Technical Forum Standard (Dongarra (2002)) festgeschrieben ist.
Je nach Gestalt der Operanden die Routinen in Klassen, den sogenannten Levels aufgeteilt.
• Level 1: Vektor-Vektor Operationen
• Level 2: Matrix-Vektor Operationen
• Level 3: Matrix-Matrix Operationen
Dabei sind insbesondere die Level 3 - BLAS (für Details siehe Dongarra et al. (1990)) von
Interesse, da diese block-basierende Algorithmen wie sie z.B. im Softwarepaket LAPACK zu
finden sind ermöglichen.
3.3.2
ATLAS
Da, wie bereits in den vorhergehenden Abschnitten erwähnt, die Leistung der Routinen stark
von der zugrundeliegenden Hardware abhängt, werden von Prozessor- und Supercomputerherstellern per Hand optimierte Implementierungen (wie z.B. die Intel MKL oder IBM ESSL)
des BLAS-Standards angeboten.
Einen anderen Ansatz verfolgt die ATLAS (Automatically Tuned Linear Algebra Software;
Whaley und Dongarra (1997)), die in diesem Projekt verwendet wird. Anders als bei handoptimierten BLAS werden Performance steuernde Parameter wie Blockgrößen und Schleifenstrukturen durch systematisches Ausprobieren und anschließende Laufzeitmessung von Routinen, die Referenzoperationen im L1-Cache des Prozessors durchführen, bestimmt. Dieser
Optimierungsprozess ermöglicht es, auf quasi jedem Prozessortyp Berechnungen mit hoher
Performance durchzuführen, was z.B. bezüglich der Zusammenstellung von Computerclustern
entsprechende Flexibilität mit sich bringt.
Um die Notwendigkeit von optimierten BLAS zu veranschaulichen wird im folgenden Abschnitt
ein Performancevergleich anhand verschiedener Implementierungen des Standards und einer
Referenzlösung über einfache Schleifen von Matrix-Matrix Multiplikation (Algorithmus 3.1)
und Cholesky-Faktorisierung (Algorithmus 3.2) angestellt. Als Gradmesser der Leistung wird
die Geschwindigkeit der Algorithmen in Flops (FLoating point OPerations per Second) herangezogen.
12
Algorithmus 3.1 Matrixmultiplikation
for i = 1 : N do
for j = 1 : N do
for k = 1 : N do
cij ← aik bkj + cij
end for
end for
end for
Algorithmus 3.2 Cholesky-Faktorisierung
for i = 1 : N do
√
aii ← aii
for j = i + 1 : N do
a
aji ← aji
ii
end for
for k = i + 1 : N do
for l = k : N do
alk ← alk − ali aki
end for
end for
end for
Abbildung 6 zeigt einen Vergleich der Leistung von hardware-optimierten BLAS (ATLAS),
einer generischen Implementierung (GSL CBLAS) und der Lösung über einfache Schleifen.
BLAS Performancevergleich - Matrixmultiplikation
BLAS Performancevergleich - Cholesky Faktorisierung
4000
8000
6000
Performance [Mflops]
Performance [Mflops]
7000
5000
4000
3000
2000
3000
2000
1000
1000
0
0
0
1000
2000
3000
4000
5000
0
1000
N
ATLAS
Einfache Schleifen
2000
3000
4000
5000
N
GSL CBLAS
(a) Matrixmultiplikation
ATLAS
Einfache Schleifen
GSL CBLAS
(b) Cholesky-Faktorisierung
Abbildung 6: Tatsächliche Rechenleistung von optimierten und nicht-optimierten Algorithmen
auf einem einzelnen Kern eines AMD Opteron mit 2.30 GHz.
Wie in der obigen Abbildung zu erkennen ist, bringt der Einsatz von optimierten Bibliotheken ab einer Problemgröße von N ≥ 1000 eine Leistungssteigerung um das 30- bis 50-fache
gegenüber generischen BLAS Implementierungen und einfachen Schleifen.
Ausgehend vom zuvor durchgeführten Performancevergleich der untersuchten Bibliotheken
bzw. Implementierungen lässt sich eine Abschätzung der Rechenzeit für die Multiplikation
bzw. Faktorisierung großer Matrizen anstellen.
Diese Abschätzung soll ein besseres Gefühl für die Dauer der Operationen vermitteln und die
Angabe von Rechengeschwindigkeit in Gleitkommaoperationen pro Sekunde interpretierbar
machen.
13
Die für die Extrapolation benötigte Leistung in Flops wurde dabei aus den Abbildungen 6a
bzw. 6b abgegriffen und ergibt sich wie folgt:
Tabelle 1: Rechenleistung von optimierten und nicht-optimierten Algorithmen auf einem einzelnen Kern eines AMD Opteron.
Implementierung
Matrixmultiplikation
[Mflops]
7200
230
150
ATLAS
GSL CBLAS
Einfache Schleifen
Cholesky Faktorisierung
[Mflops]
3500
200
470
Rechenzeitabschaetzung - Cholesky Faktorisierung
1000
1750
875
1500
750
Rechenzeit [h]
Rechenzeit [h]
Rechenzeitabschaetzung - Matrixmultiplikation
2000
1250
1000
750
625
500
375
500
250
250
125
0
1⋅104
3⋅104
ATLAS
Einfache Schleifen
5⋅104
N
7⋅104
9⋅104
GSL CBLAS
(a) Matrixmultiplikation
0
1⋅104
3⋅104
ATLAS
Einfache Schleifen
5⋅104
N
7⋅104
9⋅104
GSL CBLAS
(b) Cholesky-Faktorisierung
Abbildung 7: Abschätzung der Rechenzeit von optimierten und nicht-optimierten Routinen
für große Matrizen.
Wie die obigen Abbildungen zeigen, treten bei nicht-optimierten Routinen bereits bei Problemen der Größe N = 3 · 104 Rechenzeiten auf, die im Bereich von Tagen liegen.
Betrachtet man im Speziellen die abgeschätzten Laufzeiten der optimierten ATLAS-Bibliothek
(vgl. Abbildung 8), so ergeben sich für die Faktorisierung nach Cholesky für Matrizen der
Größe 6 · 104 Zeiten von ca. 6 Stunden. Die Dauer der Matrixmultiplikation liegt auf Grund
der höheren Komplexität mit ca. 9 Stunden etwas darüber.
14
ATLAS - Extrapolierte Rechenzeit
Rechenzeit [h]
40
30
20
10
0
1⋅104
3⋅104
Cholesky Faktorisierung
5⋅104
N
7⋅104
9⋅104
Matrixmultiplikation
Abbildung 8: Extrapolierte Rechenzeit der optimierten ATLAS-Bibliothek.
Diese Richtwerte können für die Rechenzeitabschätzung der parallelen Implementierung des
jeweiligen Algorithmus, unter Annahme einer linearen Effizienzsteigerung, über den Zusammenhang
tseq
tparallel =
mit P . . . Prozessanzahl
P
herangezogen werden.
3.3.3
Parallelisierung der BLAS
Mit dem Beginn des ScaLAPACK Projekts wurde ebenfalls die Notwendigkeit eines standardisierten Interfaces für die Grundoperationen der numerischen Linearen Algebra auf verteilten
Systemen erkannt.
Vor diesem Hintergrund wurde eine parallele Version der BLAS Routinen (die sogennanten
PBLAS), welche die selben Ziele wie ihr sequentielles Gegenstück anstrebt, angedacht und
implementiert (Choi et al. (1995)). Diese bilden in Verbindung mit BLACS und den Message Passing Primitives (vgl. Kapitel 3.2 bzw. 3.1) die Grundbausteine für die Routinen der
ScaLAPACK Bibliothek.
3.4
LAPACK
LAPACK stellt bezüglich der angebotenen Funktionalität das sequentielle Pendant und den
Vorläufer von ScaLAPACK dar. Die Verbindung zu ScaLAPACK entsteht durch implizite Aufrufe von LAPACK Routinen bei der Manipulation von lokalen Arrays.
Anzumerken ist, dass LAPACK durch die Verwendung von parallelisierten BLAS Routinen
ebenfalls auf Multiprozessoren eingesetzt werden kann.
Eine sehr detaillierte Beschreibung dieser Bibliothek findet sich im LAPACK User’s Guide
(Anderson et al. (1999)).
4
4.1
Matrix Speicherschemata
Zweidimensionale block-zyklische Verteilung
ScaLAPACK (so wie andere numerische Bibliotheken, z.B. High Performance Fortan) verwendet für die Aufteilung der einzelnen Matrixelemente auf das Prozessgitter die sogenannte
15
zweidimensionale block-zyklische Verteilung. Diese bietet neben einer gleichmäßigen Auslastung der Prozesse während der Laufzeit, die Möglichkeit Level 3-BLAS Routinen auf jedem
Prozess auszuführen und damit optimale Ausnutzung der lokalen Hardware zu gewährleisten
(Dongarra et al. (1992)).
Für die Position (x, y) des Elements aij der Matrix A im lokalen Block (l, m) des Prozesses
(pr , pc ), ergeben sich folgende analytische Zusammenhänge.
j i−1 k j j−1 k
,
)
PR M B
PC NB
ji − 1k
jj − 1k
(pr , pc ) = (
mod PR ,
mod PC )
MB
NB
(x, y) = ((i − 1) mod MB + 1, (j − 1) mod NB + 1)
(l, m) = (
(1)
Das Abbildungsgesetz (1) soll nun anhand des nachfolgenden Beispiels veranschaulicht werden.
Beispiel. Gegeben sei ein Prozessgitter (PR × PC ) der Größe (2 × 3) und A ∈ M(9 × 9, R).
Die einzelnen Blöcke Aij mit MB = NB = 2 werden wie folgt auf die einzelnen Prozesse
aufgeteilt:
(a) Globale Betrachtung der Matrix A
P00
P01
P02
P10
P11
P12
(b) A verteilt auf die Prozesse Pkl
Abbildung 9: Aufspaltung der Matrix A in (2 × 2) Blöcke und deren Verteilung am Prozessgitter.
Die während der Distribution entstehenden zweidimensionalen Arrays werden im (linearen)
Arbeitsspeicher des jeweiligen Prozesses, durch Aneinanderreihung der einzelnen Spalten (ColumnMajor-Order ) verspeichert.
Vom Standpunkt der einzelnen Prozesse ergibt sich schließlich folgendes Bild (Abbildung 10).
16
P00
P01
P02
L00 ∈ M(5 × 4)
L01 ∈ M(5 × 3)
L02 ∈ M(5 × 2)
P10
P11
P12
L10 ∈ M(4 × 4)
L11 ∈ M(4 × 3)
L12 ∈ M(4 × 2)
Abbildung 10: Aufteilung der Matrix A vom Prozess-Standpunkt aus gesehen. Lkl bezeichnet
das jeweilige lokale Array.
Abschließend ist anzumerken, dass sich jede ein- und zweidimensionale Datenverteilung als
Sonderfall der zweidimensionalen block-zyklischen Verteilung realisieren lässt (Details sind in
Blackford et al. (1997) gegeben).
4.2
ScaLAPACK Standardspeicherschema
Im Standardspeicherschema von ScaLAPACK werden vollbesetzte Matrizen vollständig entsprechend der zweidimensionalen block-zyklischen Verteilung auf das Prozessgitter aufgeteilt.
Da dieser Ansatz für symmetrische Matrizen und Dreicksmatrizen erheblichen Speicheroverhead verursacht, werden in den folgenden Abschnitten alternative Speicherschemata vorgestellt.
4.3
4.3.1
Distributed Packed Storage
Definitionen
Obwohl die derzeitigen Parallelplattformen immer mehr Speicherkapazität aufweisen, steigt
auch die Größe der Probleme die auf ihnen gelöst werden. Entwickelt man zum Beispiel das
Erdschwerefeld in einer harmonischen Reihe bis Grad und Ordnung 360 (e.g. EGM96, Lemoine et al. (1998)) so würde bei der Bestimmung der Koeffizienten durch Ausgleich nach
kleinsten Quadraten die Normalgleichungsmatrix eine Größe von ca. 130 GB aufweisen. Eine
Entwicklung bis Grad/Ordnung 2160 (e.g. wie im EGM2008, Pavlis et al. (2008)) würde für
die vollständige Speicherung der Normalgleichungen bereits ca. 20 TB benötigen.
Liegen Matrizen nun, wie in den obigen Beispielen, in symmetrischer Form oder als Dreicksmatrix vor, so ist während der Berechnungen der Speicher zu knapp 50 % mit redundanter
Information gefüllt. Es liegt daher nahe diese Strukturen zur Reduktion des Speicheraufwandes
auszunützen und nur die Hälfte der Matrixelemente zu speichern.
ScaLAPACK unterstützt zu diesem Zeitpunkt, im Gegensatz zum sequentiellen Pendant LAPACK, dieses sogennante packed storage Schema nur sehr begrenzt (vgl. Kapitel 4.4). Aus
diesem Grund wurde in Baboulin et al. (2007) ein Speicherschema vorgeschlagen, das es durch
einen Block basierenden Ansatz ermöglicht unmodifizierte ScaLAPACK Routinen zu verwenden.
17
Im ersten Schritt wird die Matrix A in quadratische Blöcke (im folgenden als distributed blocks
bezeichnet) der Größe
NBD = NB · q · l
mit
q ... kleinstes gemeinsames Vielfaches von PR und PC
l ... beliebiger Faktor (l ∈ N \ {0})
aufgeteilt, die im Falle der Betrachtung des unteren Dreiecks anschließend spaltenweise horizontal aneinander gereiht werden (siehe Abbildung 11).
N11
NT21
NT31
N21
N22
NT32
N31
N32
N33
N11
N21
N31
N22
N32
N33
Abbildung 11: Blockweise Aufteilung und anschließende horizontale Anordnung einer Matrix
im Distributed Packed Storage Format bei Betrachtung der unteren Dreiecksblöcke.
Wird das obere Dreieck der Matrix referenziert, werden die einzelnen Blöcke reihenweise angeordnet (vgl. Abbildung. 12).
N11
NT21
NT31
N21
N22
NT32
N31
N32
N33
N11
NT21
NT31
N22
NT32
N33
Abbildung 12: Blockweise Aufteilung und anschließende horizontale Anordnung einer Matrix
im Distributed Packed Storage Format bei Betrachtung der oberen Dreiecksblöcke.
Der Grund für diese Anordnung liegt in der besseren Cache-Nutzung, da elementare Blöcke
und distributed blocks zusammenhängend im Speicher liegen.
Das entstehende Array wird wie eine gewöhnliche vollbesetzte Matrix betrachtet und entsprechend der zweidimensionalen block-zyklischen Verteilung auf die einzelnen Prozesse aufgeteilt.
18
Es ist anzumerken, dass die jeweiligen Diagonalblöcke vollständig gespeichert werden. Während dadurch ein gewisser Speicheroverhead entsteht, erlaubt diese Vorgehensweise jedoch die
Verwendung der standardmäßig in ScaLAPACK implementierten Routinen.
4.3.2
Implementierte Algorithmen
Wie bereits zuvor angemerkt, basiert das Distributed Packed Format auf der Verwendung von
unmodifizierten ScaLAPACK Routinen, die in block-basierenden Algorithmen auf distributed
blocks angewendet werden. Um dieses Prinzip zu veranschaulichen soll nun der in Baboulin
et al. (2007) präsentierte Algorithmus für die Cholesky Faktorisierung aufgeschlüsselt werden.
Folgende ScaLAPACK Routinen werden verwendet:
• pdpotrf: Cholesky Faktorisierung
• pdtrsm: Lösung von Gleichungssystemen mit Dreieckiger Koeffizientenmatrix
• pdgemm, pdsyrk: Matrixmultiplikation
Beispiel. Gegeben sei eine symmetrische, positiv definite Matrix N, die aufgeteilt in distributed blocks, mit

 D
N11
·
·
D
· 
N = ND
21 N22
D
D
N31 N32 ND
33
als horizontales Array im Distributed Packed Format
N1 N2 N3 N4 N5 N6
vorliegt. Bezeichnet man mit N die Anzahl der distributed block-Spalten ergibt sich der Algorithmus zur Faktorisierung der Matrix nach Cholesky wie folgt:
for i = 1 : N do
j ← indget(i, i)
Nj ← cholesky(Nj ) {Faktorisierung des Diagonalblocks Nj (pdpotrf)}
Nj+1:j+N −i ← Nj+1:j+N −i · N−T
{Update der Blockspalte von Nj (pdtrsm)}
j
for k = i + 1 : N do
l ← indget(k, k)
Nl ← Nl − Nj+k−i NTj+k−i {Update der restlichen Matrixblöcke (pdgemm, pdsyrk)}
Nl+1:l+N −k ← Nl+1:l+N −k − Nj+1+k−i:j+N −i NTj+k−i
end for
end for
(Anm.: Die Funktion indget stellt eine Abbildungsvorschrift für die Indizes der distributed
blocks zwischen Standard-ScaLAPACK Speicherschema und Distributed Packed Speicherschema dar. Die Operationen an den in Schritt 2 bzw. 3 vorliegenden Rechtecksmatrizen werden
über Schleifendurchläufe realisiert.)
Analog zum obigen Beispiel wurden folgende Routinen implementiert:
19
• Matrixinversion
Die Inversionsroutine für Dreiecksmatrizen basiert auf dem in Higham (2002) untersuchten Algorithmus (Methode 1B), welcher z.B. auch in LAPACK implementiert ist.
Zusätzlich wurde eine Routine implementiert, die im Anschluss an die Inversion das
Produkt L−T L−1 berechnet.
• Lösung von Gleichungssystemen
Der Algorithmus für das Lösen von Gleichungssystemen mit dreieckiger Koeffizientenmatrix basiert auf einfachem blockweisen Vorwärts- bzw. Rückwärtseinsetzen.
4.4
ScaLAPACK Packed Storage Extension
Wie auch die bereits beschriebenen Speicherschemata basiert auch das ScaLAPACK packed
storage format auf der zweidimensionalen block-zyklischen Verteilung der Matrixelemente.
Einen wesentlichen Unterschied stellt jedoch die Tatsache dar, dass nur die jeweils unteren
bzw. oberen Dreiecksblöcke der Matrix gespeichert werden.
Anzumerken ist, dass Diagonalblöcke vollständig im Speicher liegen. Diese Vorgehensweise
erhöht zwar den tatsächlichen Speicherbedarf der lokalen Arrays, ermöglicht jedoch eine erheblich leichtere Anpassung der ScaLAPACK Routinen (D’Azevedo und Dongarra (1998)).
Da die Routinen für dieses Speicherschema zu diesem Zeitpunkt nur als prototype-Versionen
und nur mit sehr eingeschränkten Funktionsumfang vorliegen, wurde an dieser Stellen keine
ausführliche Evaluierung durchgeführt.
20
5
Praktische Untersuchungen
Es folgt der technische Bericht über die praktischen Untersuchung zur Evaluierung der ScaLAPACK Routinen.
Grundlage der Benchmarkings stellen die Routinen der im Rahmen des Projekts entstandenen
Bibliothek CSL (C-wrapped ScaLAPACK) dar. Eine detaillerte Beschreibung und Dokumentation findet sich in Anhang B.
5.1
Beschreibung der verwendeten Hard- und Software
Die praktischen Untersuchungen für die Evaluierung von ScaLAPACK wurden am Cluster des
Instituts für Theoretische Geodäsie und Satellitengeodäsie durchgeführt.
Dieser setzt sich aus vier AMD Opteron 6176 Zwölfkern-Prozessoren zusammen, die eine Taktung von 2.3 GHz aufweisen. Der Arbeitsspeicher besteht aus 32 Modulen mit jeweils 8GB
RAM und einer Speichertaktung von 1333 MHz.
Eine detaillierte Auflistung der Hardwarekomponenten findet sich in Tabelle 2.
Tabelle 2: Hardware Spezifikationen des Numbercrunchers.
Komponente
AMD Opteron 6176 2.3 GHz
Anmerkungen
12 Kerne
L1-Chache: 128 KB
L2-Chache: 512 KB
G34 Motherboard H8QGi-F
Kingston DDR3 RAM, 1333MHz
32 × 8GB Module
Softwareseitig präsentiert sich der Number Cruncher als Standard GNU/Linux-System, mit
Squeeze (Debian Distribution) als Betriebssystem. Eine Auflistung der verwendeten Bibliotheken und Compiler findet sich in der unten stehenden Tabelle (3).
Tabelle 3: Verwendete Software und numerische Bibliotheken.
Komponente
Debian Squeeze
Version
6.0.1a
GNU C Compiler
GNU Fortran Compiler
4.4.5
4.4.5
OpenMPI
ATLAS
BLACS
LAPACK
1.4.3
3.8.3
1.1
3.3.0
Anmerkungen
Betriebssystem
Debug Level 0
21
5.2
Performance-Metriken
Es folgen die genauen Definition der wichtigsten Metriken für Performance und Skalierbarkeit
von parallelen numerischen Algebra Routinen (Dongarra und D’Azevedo (1997) bzw. Sun und
Gustafson (1991)).
• Laufzeit t
Wird in dieser Arbeit primär für die Auswertung der Parameteroptimierung herangezogen, da nur Vergleiche zwischen den einzelnen Testläufen angestellt werden.
• Performance G pro Kern
Als Maß für die Leistung der Routinen wird die Performance in FLOPS pro Kern herangezogen. Diese ermöglicht direkte Vergleiche mit anderen Bibliotheken sowie mit der
in Kapitel 3.3.2 angestellten Leistungsfestellung der sequentiellen ATLAS-BLAS.
• Isogranularitätskurven
Als Maß für die Skalierbarkeit der Routinen wird die Form von Isogranularitätskurven
herangezogen. Je stärker diese bei steigender Problemgröße von einer Geraden abweichen, desto weniger skalierbar sind die Routinen.
22
5.3
Ergebnisse
Es folgen die Ergebnisse der praktischen Untersuchungen.
5.3.1
Parameteroptimierung
In der Parameteroptimierung wurden einzelne steuerbare Parameter von ScaLAPACK bzw.
den zu Grunde liegenden Komponenten variiert um eine Konfiguration für optimale Leistung
zu bestimmen.
Die Notation für die folgenden Abschnitte lautet wie folgt:
N
PR
PC
tchol
tinv
...
...
...
...
...
Problemgröße (i.e. Zeilen-/Spaltenanzahl der Normalgleichungsmatrix)
Anzahl der Prozessgitterreihen
Anzahl der Prozessgitterspalten
Laufzeit der Cholesky Faktorisierung
Laufzeit der Matrixinversion
• Steuerbare ScaLAPACK Parameter
In den folgenden Abbildungen werden die Ergebnisse der Variation von Blockgröße und
Prozessgitterform dargestellt. Die Betrachtungen wurden seperat für die drei Operationen pdgemm (Matrix-Matrix Multiplikation), pdpotrf (Cholesky Faktorisierung) und
pdpotri (Matrixinversion) durchgeführt.
Optimierung der Prozessgitterform
50
Optimierung der Prozessgitterform
350
8x2
4x4
2x8
8x2
4x4
2x8
300
40
30
Laufzeit t [s]
Laufzeit t [s]
250
20
200
150
100
10
50
0
pdgemm
pdpotrf
pdpotri
(a) Problemgröße N = 10
4
0
pdgemm
pdpotrf
pdpotri
(b) Problemgröße N = 2 · 104
Abbildung 13: Laufzeit in Abhängigkeit der Prozessgitterform.
Wie in Abbildung 13 zu sehen ist, wirkt sich die Änderung Prozessgitterform nur geringfügig auf die Laufzeit der Routinen aus. Allgemein lässt sich sagen, dass sich ein
vertikales Rechteck positiv auf die Leistung bei Matrix-Matrix Multiplikation auswirkt,
jedoch bei der Inversion am Schlechtesten abschneidet.
23
Optimierung der Blockgröße NB
80
pdgemm
pdpotrf
pdpotri
70
Laufzeit t [s]
60
50
40
30
20
10
0
0
256
512
768
1024
NB
Abbildung 14: Laufzeit in Abhängigkeit der Blockgröße für N = 104 .
Bei der Betrachtung von Abbildung 14 fällt auf, dass bei einer Blockgröße von NB ≈ 250
ein Minimum der Laufzeit auftritt. Bei steigender Blockgröße nimmt die Performance
kontinuierlich ab, da dadurch die einzelnen Blöcke nicht mehr vollständig in die unteren
Cache-Level passen.
• OpenMPI Kommandozeilenparameter
OpenMPI bietet die Möglichkeit vor dem Programmstart unterschiedliche Reihungsbzw. Bindungsmodi der Prozesse auszuwählen. Tabelle 4 zeigt die Laufzeit für Cholesky
Faktorisierung und Matrixinversion für alle verfügbaren Kombinationen.
– Getestete Parameter:
−−bind−to−none (default)
−−bind−to−core
−−bind−to−socket
Prozesse werden nicht gebunden
Prozesse werden auf physische Kerne gebunden
Prozesse werden auf Sockets gebunden
– Getestete Reihungsschemata:
−−bycore (default) Prozesse werden benachbarten Kernen zugewiesen
−−bysocket
Prozesse werden benachbarten Sockets zugewiesen
Tabelle 4: Ergebnisse der MPI Kommandozeilenparameteroptimierung.
N
20000
20000
20000
20000
PR
7
7
7
7
PC
6
6
6
6
tchol [s]
17
58
133
18
tinv [s]
58
397
797
59
(default)
−−bind−to−socket
−−bind−to−socket
−−bind−to−core
(default)
−−bysocket
−−bycore
−−bycore
24
• Threaded/Non-Threaded ATLAS
ATLAS bietet neben den herkömmlichen Bibliotheken und Interfaces zusätzlich die Möglichkeit eine auf POSIX-Threads basierende Implementierung der BLAS einzubinden, die
eine betriebssystemnahe Form der Parallelisierung beinhaltet. Die folgenden Tests wurden durchgeführt um zu untersuchen ob Interferenzen mit der Kommunikation über die
BLACS entstehen.
Tabelle 5: Laufzeitvergleich für Cholesky Faktorisierung und Matrixinversion unter der Verwendung von threaded und non-threaded BLAS.
5.3.2
N
20000
20000
PR
7
7
PC
6
6
NB
256
256
tchol [s]
34
34
tinv [s]
552
548
20000
20000
7
7
6
6
256
256
17
18
59
57
Skalierbarkeit
Leistung in Abhaengikeit der Prozessanzahl P
150
Leistung in Abhaengikeit der Prozessanzahl P
150
pdpotrf
pdpotri
pdpotrf
pdpotri
125
Performance G [Gflops]
125
Performance G [Gflops]
threaded
threaded
100
75
50
25
100
75
50
25
0
0
0
10
20
P
30
40
(a) Standard - ScaLAPACK Speicherschema
0
10
20
P
30
40
(b) Distributed Packed Format
Abbildung 15: Isogranularitätskurven (Leistung in Abhängigkeit der Porzessanzahl bei konstanter Speicherauslastung pro Prozess) für ScaLAPACK - Routinen und Routinen des Distributed Packed Formats.
Wie in Abbildung 15a zu erkennen ist, zeigt die ScaLAPACK Routine zur Cholesky Faktorisierung pdpotrf geringe Leistungsabfälle bei steigender Problemgröße. Die auf der Faktorisierung
basierende Matrixinversion der pdporti ist hingegen höchst skalierbar. Für die Lösung großer
Systeme mit anschließender expliziter Berechnung der inversen Koeffizientenmatrix, bedeutet
25
dies, dass auf Grund der stark unterschiedlichen Anteile der jeweiligen Routine an der tatsächlichen Laufzeit (siehe Abschnitt 5.3.1), von guter Skalierbarkeit bezüglich der Problemgröße
ausgegangen werden kann.
Die Isogranularitätskurven der implementierten Routinen zur Manipulation von Matrizen im
Distributed Packed Speicherschema (vgl. Abbildung 15b) zeigen ab einer Prozessanzahl P
von 36 einen Leistungseinbruch. Dieses Ergebnis deckt sich mit den in Baboulin et al. (2007)
durchgeführten Untersuchungen.
5.3.3
Performance
Leistung in Abhaengikeit der Problemgroesse N
pdpotrf
pdpotri
Performance G pro Kern [Gflops]
8
6
4
2
0
7500
15000
30000
N
60000
120000
Abbildung 16: Performance pro Kern in Abhängigkeit der Problemgröße N .
Die in Abbildung 16 dargestellte Leistung pro Kern für Choleksy Faktorisierung und Matrixinversion bewegt sich zwischen ca. 3.5 und 4.5 Gflops.
Ein Vergleich mit den in Kapitel 2 erhaltenen Leistung für die sequentielle Implementierung
der Routine pdpotrf (d.h. das LAPACK Pendant) lässt auf eine beinahe lineare Leistungssteigerung und damit hohe Effizienz der Routine schließen.
Der Leistungsprung bei N = 6.3·104 lässt sich durch die, auf Grund der maximalen Prozessanzahl von Pmax = 48 erforderliche Anordnung der Prozesse als horizontales bzw. vertikales
Rechteck erklären (vgl. Abschnitt 5.3.1).
26
6
Zusammenfassung und Ausblick
In der vorliegenden Arbeit wurden die theoretischen Grundlagen für effizientes Rechnen in
Parallelumgebungen mit Schwerpunkt auf numerischer linearer Algebra erörtert. Darauf aufbauend wurde ein Überblick über die zu untersuchende Bibliothek und ihrer zu Grunde liegenden Komponenten gegeben.
Es wurde eine Sammlung von Hilfsroutinen und Wrappern entwickelt und implementiert, die
durch Einführung von strukturierten Datentypen die Prozesssteuerung, Speicherverwaltung
und allgemeine Nutzung der Bibliothek erleichtert. Zusätzlich erfolgte die Implementierung
von Routinen die es erlaubten spezielle Strukturen von Matrizen wie Symmetrie oder Dreiecksform auszunutzen um die Speicherauslastung zu verringern.
Basierend auf den entstandenen Routinen wurden Benchmark-Tests implementiert, welche es
ermöglichten nach Optimierung von leistungssteuernden Parametern der Bibliothek, die Performance und Skalierbarkeit von ScaLAPACK zu evaluieren.
Es konnte schließlich gezeigt werden, dass ScaLAPACK eine leistungsstarke Sammlung von
Routinen zur Lösung von großen Gleichungssystemen auf verteilten Systemen darstellt.
27
Referenzen
E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov, und D. Sorensen. LAPACK User’s Guide. Society
for Industrial and Applied Mathematics, Philadelphia, PA, USA, dritte Auflage, 1999.
M. Baboulin, L. Giraud, S. Gratton, und J. Langou. A distributed packed storage for large
dense parallel in-core calculations. Concurrency and Computation: Practice and Experience,
19(4):483–502, 2007.
L. S. Blackford, J. Choi, A. Cleary, E. D’Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, und R. C. Whaley. ScaLAPACK Users’
Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997.
J. Choi, J. J. Dongarra, L. S. Ostrouchov, A. P. Petitet, D. W. Walker, und
R. C. Whaley.
A Proposal for a Set of Parallel Basic Linear Algebra Subprograms.
Technischer Bericht 100, LAPACK Working Note, Mai 1995.
URL
http://www.netlib.org/lapack/lawnspdf/lawn100.pdf.
E. F. D’Azevedo und J. J. Dongarra.
Packed storage extensions for ScaLAPACK.
Technischer Bericht 135, LAPACK Working Note, Apr. 1998.
URL
http://www.netlib.org/lapack/lawnspdf/lawn135.pdf.
Dongarra. Basic Linear Algebra Subprograms Technical Forum Standard. International Journal of High Performance Applications and Supercomputing, 16:1–111, 2002.
J.
J. Dongarra und E. F. D’Azevedo.
The design and implementation of
the parallel out-of-core ScaLAPACK LU, QR, and cholesky factorization routines.
Technischer Bericht 118, LAPACK Working Note, Jan. 1997.
URL
http://www.netlib.org/lapack/lawnspdf/lawn118.pdf.
J.
J. Dongarra und R. C. Whaley.
A User’s Guide to the BLACS
v1.1.
Technischer Bericht 94, LAPACK Working Note, Mai 1997.
URL
http://www.netlib.org/lapack/lawnspdf/lawn94.pdf.
ursprünglich veröffentlicht
März 1995.
J. J. Dongarra, J. Du Croz, S. Hammarling, und R. J. Hanson. An extended set of FORTRAN
Basic Linear Algebra Subprograms. ACM Trans. Math. Softw., 14:1–17, März 1988.
J. J. Dongarra, J. Du Croz, S. Hammarling, und I. S. Duff. A set of Level 3 Basic Linear
Algebra Subprograms. ACM Trans. Math. Softw., 16:1–17, März 1990.
J. J. Dongarra, R. A. van de Geijn, und D. W. Walker. A Look at Scalable Dense Linear
Algebra Libraries. Technischer Bericht 43, LAPACK Working Note, April 1992. URL
http://www.netlib.org/lapack/lawnspdf/lawn43.pdf.
M. R. Drinkwater, R. Haagmans, D. Muzi, A. Popescu, R. Floberghagena, M. Kern, und
M. Fehringer. THE GOCE GRAVITY MISSION: ESA’S FIRST CORE EARTH EXPLORER. In Proceedings of the 3rd International GOCE User Workshop, 6-8 November, 2006,
Frascati, Italy, pages 1–8. ESA Special Publication, 2007.
28
I. Foster. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software
Engineering. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1995.
A. Geist, A. Beguelin, J. J. Dongarra, W. Jiang, R. Manchek, und V. Sunderam. PVM:
Parallel Virtual Machine. A Users’ Guide and Tutorial for Networked Parallel Computing.
MIT Press, Cambridge, MA, USA, 1994.
N. J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and
Applied Mathematics, Philadelphia, PA, zweite Auflage, 2002.
C. L. Lawson, R. J. Hanson, F. T. Krogh, und D. R. Kincaid. Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage [F1]. ACM Trans. Math. Softw., 5:324–325,
September 1979.
F. G. Lemoine, S. C. Kenyon, J. K. Factor, R. G. Trimmer, N. K. Pavlis, D. S. Chinn, C. M.
Cox, S. M. Klosko, S. B. Luthcke, M. H. Torrence, Y. M. Wang, R. G. Williamson, E. C.
Pavlis, R. H. Rapp, und T. R. Olson. The Development of the Joint NASA GSFC and
NIMA Geopotential Model EGM96. NASA Goddard Space Flight Center, Juli 1998.
N. K. Pavlis, S. A. Holmes, S. C. Kenyon, und F. J. K. An Earth Gravitational Model to Degree
2160: EGM2008. presented at the 2008 General Assembly of the European Geosciences
Union, April 13-18 2008.
C. Reigber, H. Lühr, und P. Schwintzer. Announcement of Opportunity for CHAMP.
GeoForschungsZentrum Potsdam Online Available Documents, Mai 2001.
URL
http://op.gfz-potsdam.de/champ/docs_CHAMP/CH-GFZ-AO-001.PDF.
X.-H. Sun und J. L. Gustafson. Toward a Better Parallel Performance Metric. Parallel
Computing, 17:1039–1109, 1991.
A. S. Tanenbaum. Structured Computer Organization. Prentice Hall, Upper Saddle River, NJ
[u.a.], vierte Auflage, 1999.
B. D. Tapley, S. Bettadpur, M. Watkins, und C. Reigber. The gravity recovery and climate
experiment: Mission overview and early results. Geophysical Research Letters, 31:9607–+,
Mai 2004.
R. C. Whaley und J. J. Dongarra.
Automatically Tuned Linear Algebra Software.
Technischer Bericht 131, LAPACK Working Note, Dezember 1997.
URL
http://www.netlib.org/lapack/lawnspdf/lawn131.pdf.
29
Zeitplan
Abbildung 17: Gantt-Diagramm der einzelnen Projektphasen, Arbeitspakete und Meilensteine mit dazugehörigen Start-/Endterminen.
A
C-wrapped ScaLAPACK
Reference Manual
Edition 1.0, for CSL 0.1
31 May 2011
Andreas Kvas
[email protected]
i
Table of Contents
1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1
1.2
1.3
1.4
2
1
1
1
1
Using the Library. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1
2.2
2.3
2.4
2.5
2.6
3
Routines available in CSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Message Passing Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ScaLAPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Program Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
File Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Compiling and Linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Executing MPI-based Programs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ISO C99. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Code Reuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
3
3
4
4
4
Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1 Error Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Error Reporting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Error Reporting Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4
BLACS Context Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1
4.2
4.3
4.4
4.5
5
Full Storage Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1
5.2
5.3
5.4
5.5
6
Context Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Context Destruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Auxiliary BLACS Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Timing Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Example Program for BLACS Contexts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Array Descriptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Linear Equation Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Matrix Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Auxiliary Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Data In- / Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
12
13
13
13
Distributed Packed Storage Routines . . . . . . . . . . . . . . . . . . . . . . . 15
6.1
6.2
6.3
6.4
6.5
Array Descriptor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Linear Equation Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Matrix Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Auxiliary Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Data In- / Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
17
17
17
18
7
Packed Storage Extension Routines . . . . . . . . . . . . . . . . . . . . . . . . 19
8
Function Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Chapter 1: Introduction
1
1 Introduction
The CSL is a collection of high-performance linear algebra routines for distributed-memory
message-passing MIMD computers and networks of workstations supporting MPI. The routines
rely and are based on the C interface to the ScaLAPACK library and its underlying components.
1.1 Routines available in CSL
The library lays emphasis on linear equation systems with positive definite coefficient matrices.
The following table gives a coarse overview of the available computation and auxiliary functions.
Parallel File I/O
BLACS Context Handling
Basic Linear Algebra
Cholesky Factorisation
Triangular Solvers
Matrix Inversion
Auxiliary Matrix Routines
The use of these routines is described in this manual. Each chapter provides detailed definitions of the functions, followed by example programs and references to the articles on which the
algorithms are based.
1.2 Message Passing Interface
The communication routines in CSL depend on an implementation of the Message Passing
Interface standard (such as OpenMPI).
MPI: The Complete Reference (Snir et al., 1996) or Designing and Building Parallel Programs
(Foster, 1995) offer an introduction to the theoretical background as well as practical examples
on the matter.
1.3 BLAS
The Basic Linear Algebra Subprograms (BLAS) define a set of fundamental operations on vectors
and matrices which can be used to create optimized higher-level linear algebra functionality.
For optimal performance, the use of an optimized BLAS library such as ATLAS (available
through math-atlas.sourceforge.net/ under a modified BSD-License) or, if available, a vendor specific implementation is encouraged.
1.4 ScaLAPACK
Because CSL is based on the ScaLAPACK library and (almost exclusively) uses the same naming
scheme for function calls, array descriptors and context handling, the user should be familiar
with the underlying routines.
A comprehensive documentation for ScaLAPACK can be found in the ScaLAPACK Users’
Guide (Blackford et al. 1997).
Chapter 2: Using the Library
2
2 Using the Library
The following sections describe the basic structure of CSL programs, how to compile them and
introduces the naming conventions used throughout the library.
2.1 Program Structure
The following short example program demonstrates the use of the library by computing the
Cholesky factorisation of a 1000 x 1000 matrix on a 3 x 2 process grid using square blocks of
size 256. Note that for shortness’ sake no error handling whatsoever is done.
#include
#include
#include
#include
<stdio.h>
<math.h>
<mpi.h>
<stdlib.h>
#include <blacs_grid.h>
#include <slp_array.h>
#include <slp_errno.h>
int
main(int argc, char *argv[])
{
size_t mlocal, nlocal;
size_t N, nblock;
int descA[DESCRIPTOR_SIZE], descNEQ[DESCRIPTOR_SIZE];
slp_array *designmatrix;
slp_array *neqmatrix;
blacs_grid *procgrid;
size_t mprocs, nprocs;
N=1000;
mprocs=3;
nprocs=2;
nblock=256;
MPI_Init(&argc, &argv);
procgrid=blacs_grid_alloc(mprocs, nprocs, "C");
blacs_grid_init(procgrid, MPI_COMM_WORLD);
mlocal=slp_numroc(N, nblock, procgrid, ROW);
nlocal=slp_numroc(N, nblock, procgrid, COLUMN);
designmatrix=slp_array_alloc(mlocal, nlocal, nblock, nblock);
slp_array_set_rand(designmatrix, procgrid);
neqmatrix=slp_array_alloc(mlocal, nlocal, nblock, nblock);
slp_array_set_zero(neqmatrix);
Chapter 2: Using the Library
3
slp_descinit(descA, designmatrix, N, N, nblock, nblock, procgrid);
slp_descinit(descNEQ, neqmatrix, N, N, nblock, nblock, procgrid);
slp_pdsyrk("L", "T", 1.0, designmatrix, descA,
0.0, neqmatrix, descNEQ);
slp_pdpotrf("L", neqmatrix, descNEQ);
slp_array_free(designmatrix);
slp_array_free(neqmatrix);
blacs_grid_free(procgrid);
MPI_Finalize();
return EXIT_SUCCESS;
}
Basically, four steps are required to call a CSL (or ScaLAPACK) routine:
1. Initialize MPI and the BLACS process grid
This done via a call to MPI Init and blacs grid alloc/blacs grid init respectively.
2. Distribute the matrices on the process grid
slp numroc returns the correct sizes for the local sub arrays on each process. After allocating
sufficient memory, slp array set rand fills designmatrix with pseudorandom numbers in the
range of [0; 1].
3. Call CSL (or ScaLAPACK) routines
In the example slp pdsyrk performs a symmetric rank-k update to make sure neqmatrix
is symmetric and positive definite. slp pdpotrf then computes the Cholesky factorisation,
overwriting the lower triangle of neqmatrix.
4. Release the BLACS process grid
blacs grid free frees all resources associated with the current BLACS handle; MPI Finalize
terminates the MPI execution environment.
2.2 File Formats
The only supported file format as of now are binary files with double precision matrix entries
stored in column-major-order.
Matrices are always stored fully; if a matrix written to file with a distributed packed storage
or a packed storage extension routine, the unreferenced blocks are filled with zeros.
2.3 Compiling and Linking
(Note: The following paths and directories assume an unmodified checkout from the subversion
repository.)
The library header files are located in the ‘include’ directory of the working copy.
A typical compilation command for a source file ‘example.c’ with the respective MPI C
compiler mpicc is
Chapter 2: Using the Library
$ mpicc example.c -lmpi -lcsl -lscalapack -lblacs -lf77blacs -lcblacs
-latlas -lcblas -llapack -lm -lgfortran -lblacs
4
\
assuming all required libraries are in the users search path. Note that if you compiled your
MPI implementation by hand, you may have to use the absolute path to the mpicc binary.
2.4 Executing MPI-based Programs
To run the binary compiled in the preceding example, the user has to run
$ mpiexec -np 4 ./a.out
Note that if you compiled your MPI implementation by hand, you may have to use the
absolute path to the mpiexec binary.
2.5 ISO C99
The library is written in ISO C99 compliant to ISO/IEC:9899:1999; thus it should be portable
to any system with a MPI C compiler supporting C99.
To avoid namespace conflicts all routines either have slp_, pse_ or dps_ as prefix depending
on the underlying storage scheme. Macros use the same convention with uppercase prefixes (i.e.
SLP_, PSE_ and DPS_).
2.6 Code Reuse
Whereever possible, dependencies between files and modules within the library have been
avoided. While producing redundant code, the routines for each storage schemes can be used
independently. Additionally this practice should facilitate the extraction and modification of
single functions.
Chapter 3: Error Handling
5
3 Error Handling
The following chapter gives a short overview of the error handling process within the CSL library.
Note that the library routines are designed in a manner so that the error handlers of the
ScaLAPACK components are called as little as possible and instead rely on returning error
codes. This should allow to achieve a somewhat clean exit on failure.
For details on error handling of the ScaLAPACK components the user is referred
to
http://www.netlib.org/scalapack/slug/node155.html
(BLACS),
http://www.netlib.org/scalapack/slug/node154.html
(PBLAS)
and
http://www.mcs.anl.gov/research/projects/mpi/usingmpi/ (MPI).
3.1 Error Codes
Each computational routine of the library returns a non-zero value to indicate an error and
SLP SUCCESS to indicate successful completion.
slp_errno status = function( ... );
if(status!=SLP_SUCCESS)
{
/* try to recover */
}
In numerical libraries error occurences due to e.g. ill-posed or ill-condinioned problems should
be expected, so the examination of the return values poses a crucial task.
The error code numbers returned by library functions are defined in ‘slp_errno.h’. They
have the common prefix SLP_ and expand to non-zero expressions of type slp_errno (typedef’ed
enum). Many of the error codes use a base name similar to those in the C library and the GNU
Scientific Library.
Following is a list of the most common error codes.
slp_errno SLP_FAILURE
[enum]
Generic failure; usually this means something very bad happened.
slp_errno SLP_EDOM
[enum]
Domain error; used by mathematical functions when an argument value does not fall into the
domain over which the function is defined.
slp_errno SLP_ERANGE
[enum]
Range error; used by mathematical functions when the result value is not representable
because of overflow or underflow.
slp_errno SLP_ENOMEM
[enum]
Out of memory error; the CSL routine is unable to allocate more memory. This error code
is returned when malloc returns a NULL pointer within a library routine.
slp_errno SLP_EINVAL
[enum]
Invalid argument; the argument passed to a libary function is not valid. e.g. if a function
only works on the lower (‘‘L’’) or upper (‘‘U’’) triangle of a matrix, any other character
will result in this error.
slp_errno SLP_ENOTPOSDEF
Matrix not positive definite; Returned by Cholesky factorisation routines.
[enum]
Chapter 3: Error Handling
6
slp_errno SLP_ENOTREG
[enum]
Matrix not regular; If a rank defect is encountered during matrix inversion, the routine aborts
with this error code.
slp_errno SLP_ESIZE
[enum]
Matrix size not compliant; Returned by matrix multiplication or triangular solvers. Indicates
that the routine aborted because the input matrix/vector sizes do not allow the algebraic
operation.
slp_errno SLP_EIO
[enum]
Generic I/O error; File could either not be found, created, opened, closed, read or written to.
slp_errno SLP_ENOTSQR
[enum]
Matrix not square; Returned by routines that require square matrices as input (e.g. Cholesky
factorisation, matrix inversion, ...).
slp_errno SLP_EUNIMPL
[enum]
Called functionality not yet implemented.
slp_errno SLP_ELOSS
[enum]
Indicates total loss of accuracy; returned e.g. if an ill-conditionend matrix is inverted.
3.2 Error Reporting
To report an occured error, the library provides the function
void slp_error (const char *function, const char *file, const int line,
slp errno error )
[Function]
This function prints an error message containing the file, line and function in which the error
occured, as well as a string representation of the error code to stderr.
For convenience ‘slp_errno.h’ also defines the macro
SLP_ERROR (function, error )
[Macro]
which expands to the following code fragment,
do { \
slp_error (function, __FILE__, __LINE__, err); \
return err; \
} while(0);
3.3 Error Reporting Example
Here is an example of some code which checks the return value of a function where an error
might be reported.
/* snip */
status=slp_descinit(descA, submatrix, M, N,
nblock, nblock, procgrid);
if(status!=SLP_SUCCESS)
{
/* snip */
}
/* snip */
Chapter 3: Error Handling
7
status=slp_pdpotrf("L", neqmatrix, descA);
if(status!=SLP_SUCCESS)
{
SLP_ERROR("slp_pdpotrf", status);
slp_array_free(submatrix);
blacs_grid_free(procgrid);
MPI_Finalize();
exit(SLP_FAILURE);
}
/* snip */
The routine slp_pdpotrf computes the Cholesky factorisation of a symmetric, positive definite matrix. As we can see, the array descriptor for the global matrix was created with different
variables for row and column number, M and N. If the value of M is not equal to the value of
N the factorisation will be aborted and slp_pdpotrf returns SLP_ENOTSQR as error code.
The if clause then frees all allocated memmory and terminates the BLACS and MPI execution environments.
Chapter 4: BLACS Context Handling
8
4 BLACS Context Handling
The functions described in this chapter provide a simple interface to the context handling routines of the BLACS. The current BLACS context is represented by a typedef’ed structure known
as blacs_grid, containing both global and local properties such as context handle, grid size and
process rank.
The following functions are defined in ‘blacs_grid.h’.
4.1 Context Initialisation
The blacs_grid structure contains eight components; size1 , size2 n procs specifiy the grid
size, blacs handle is the unique integer handle of the context, current row , current col and
current rank hold the process coordinates either in 2D or 1D representation and finally major order determines the mapping of the processes.
typedef struct {
size_t size1_;
size_t size2_;
size_t n_procs_;
int blacs_handle_;
size_t current_row_;
size_t current_col_;
size_t current_rank_;
const char *major_order_;
} blacs_grid;
Before any calls to CSL (or ScaLAPACK) routines can be made, the user has to define and
initialise a communication environment for the active processes. This usually requires two steps:
(1) Initializing the MPI execution environment and (2) Mapping the processes onto a 2D-grid
specified by a BLACS context.
blacs_grid * blacs_grid_alloc (size t size1, size t size2, const char
*major_order )
[Function]
Constructor for the typedef’ed structure blacs_grid. size1 and size2 determine the shape
of the grid while major_order specifies the mapping of the processes (i.e column-major-order
‘‘C’’ or row-major-order ‘‘R’’).
void blacs_grid_init (blacs grid *procgrid, MPI Comm comm )
[Function]
Initialises the BLACS process grid specified in procgrid by mapping the processes of the MPI
communicator comm accordingly. Note that the number of processes in the MPI communicator
and the BLACS context must be the same.
4.2 Context Destruction
Contexts consume resources, and therefore the user should release them when they are no longer
needed.
Chapter 4: BLACS Context Handling
9
void blacs_grid_free (blacs grid *procgrid )
[Function]
Destructor for the typedef’ed structure blacs_grid. Frees the resources associated with the
BLACS context represented by the passed argument. Note that after calling this function,
the underlying context no longer exists and its handle may be reused.
4.3 Auxiliary BLACS Routines
The following routines provide auxiliary functionality for context handling.
int blacs_grid_fprintf (FILE *stream, blacs grid *procgrid )
[Function]
Prints the value of each blacs_grid member to the output stream stream; Due to the limited
formatting options, the main purpose of this routine lies in the debugging process.
int io_process (size t size1, size t size2 )
[Function]
Generates an pseudo-random process rank in the range [0; size1 * size2].
4.4 Timing Routines
‘blacs_grid.h’ also defines functions for measuring algorithm run times, allowing to the determine performance of individual routines. The time measurements rely on the MPI routines
MPI_Wtime and MPI_Wtick.
The basic datatype for all timing operations is the typedef’ed structure slp_timer.
typedef struct {
double start_;
double elapsed_;
double elapsed_max_;
} slp_timer;
When a timer is invoked start holds the respective time stamp; after stopping the timer, the
elapsed time is stored in member elapsed . Because the run times of routines generally differ on
each active process, the maximum value of elapsed is stored in elapsed max .
slp_timer * slp_timer_alloc (void )
[Function]
Constructor for typedef’ed structure slp timer. Allocates required memory and initialises the
members.
void slp_timer_free (slp timer *timer )
[Function]
Destructor for typedef’ed structure slp timer. Frees all allocated memory associated with
timer.
void slp_timer_start (slp timer *timer )
[Function]
Starts timer with a call of MPI_Wtime.
void slp_timer_stop (slp timer *timer )
[Function]
Stops timer with a call of MPI_Wtime and calculates the elapsed time.
void slp_timer_reduce (MPI Comm comm, int root, slp timer *timer )
[Function]
Determines the largest value of elapsed among all active processes and stores it in member
elapsed max on process with MPI rank root.
Chapter 4: BLACS Context Handling
10
4.5 Example Program for BLACS Contexts
The following code snippet illustrates a more complex BLACS context initialisation and features
calls to MPI communicator modifying routines.
/* snip */
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
is_active=mpi_rank<mprocs*nprocs;
MPI_Comm_split(MPI_COMM_WORLD, is_active,
mpi_rank % (mprocs*nprocs), &active);
if(!is_active)
{
MPI_Get_processor_name(procname, &l_proc_name);
printf("BLACS context size: %zu x %zu |"
" Rank %3d (node %s) idling...\n",
mprocs, nprocs, mpi_rank, procname);
}
else
{
procgrid=blacs_grid_alloc(mprocs, nprocs, "C");
blacs_grid_init(procgrid, active);
/* call CSL routines */
blacs_grid_free(procgrid);
}
MPI_Finalize();
/* snip */
The first two lines of code initialise the MPI execution environment and determine the rank
of the calling process. With this information, MPI_COMM_WORLD (the communicator containing
all processes) is split into two subgroups, so that only mprocs*nprocs processes partake in
the calculation. The code in the if clause writes the node name and process rank of the idling
processes to stdout, while in the else clause the BLACS process grid is created. After some calls
to CSL routines, the BLACS context is freed and the MPI execution environment is terminated.
Chapter 5: Full Storage Routines
11
5 Full Storage Routines
This chapter describes the implemented functions for computation using the standard ScaLAPACK storage scheme (denoted full storage throughout the following chapters).
For convenience sake one assertion has been made:
• The process with coordinates (0, 0) always holds the first block of a distributed matrix.
The functions described in the following sections are defined in the header file ‘slp_array.h’.
5.1 Array Descriptor
For distributed matrices in full storage, the ScaLAPACK array descriptor for in-core dense
matrices is used. The following table shows the entries of the integer array with their definition.
(Note: The prototype header ‘scalapack.h’ defines the macros in column two, which expand
to the respective indices.)
0
DESC_DTYPE
Descriptor type (=1 for full storage matrices)
1
DESC_CTXT
Context handle of the BLACS process grid
over which the matrix is distributed
2
DESC_M
Number of rows in the global array
3
DESC_N
Number of columns in the global array
4
DESC_MB
Blocking factor used to distribute the rows of
the array
5
DESC_NB
Blocking factor used to distribute the columns
of the array
6
DESC_RSRC
Process row over which the first row of the
global matrix is distributed (=0)
7
DESC_CSRC
Process column over which the first column
of the global matrix is distributed (=0)
8
DESC_LLD
Local leading dimension
The local array on each of the processes is described by the following structured data type.
typedef struct {
size_t size1_;
size_t size2_;
size_t mblocks_;
size_t nblocks_;
size_t *blocksize1_;
size_t *blocksize2_;
double *data_;
} slp_array;
Chapter 5: Full Storage Routines
12
The members size1 and size2 denote the number of rows and columns of the local array;
mblocks , nblocks and blocksize1 , blocksize2 store the number of block rows and block
columns and the individual block sizes respectively. The local matrix elements are stored in
column-major order in member data .
slp_array * slp_array_alloc (size t size1, size t size2, size t
max_blocksize1, size t max_blocksize2 )
[Function]
Constructor for typedef’ed structure slp_array. Allocates all required memory and calculates the individual block sizes.
void slp_array_free (slp array *submatrix )
[Function]
Destructor for typedef’ed structure slp_array. Frees all memory associated with submatrix.
size_t slp_numroc (size t N, size t nblock, blacs grid *procgrid,
slp dimension dim )
[Function]
Wrapper for the ScaLAPACK routine NUMROC. Computes the size of the local submatrix.
dim is either ROW or COLUMN.
slp_errno slp_descinit (int *descA, slp array *submatrix, size t M,
size t N, size t mblock, size t nblock, blacs grid *procgrid )
[Function]
Creates and array descriptor for a distributed matrix of size M x N with the blocking factors
mblock and nblock. The return value descA has to be preallocated with at least DESCRIPTOR_
SIZE*sizeof(int) bytes.
5.2 Linear Equation Systems
A symmetric, positive definite matrix has a Cholesky factorisation into a product of a lower
triangular matrix and its transpose (or into a product of the transpose of an upper triangular
matrix and the upper triangular matrix itself). This factorisation can be used to convert the
linear system Ax = b into a pair of triangular systems (Ly = b, LT x = y or U T y = b, U x = y),
which can be solved by forward and backward-substitution
slp_errno slp_pdpotrf (const char *UPLO, slp array *A, int *descA )
[Function]
slp_pdpotrf computes the Cholesky factorisation of the symmetric positive definite distributed matrix represented by A and descA. The lower (UPLO = ‘‘L’’) or upper (UPLO
= ‘‘U’’) triangle of A is overwritten in the process.
slp_errno slp_pdpotrs (const char *UPLO, slp array *A, int *descA,
slp array *RHS, int *descRHS )
[Function]
slp_pdpotrs solves a system of linear equations with a symmetric positive definite distributed
coefficient matrix, using the Cholesky factorisation computed by slp_pdpotrf. The right
hand side vector is represented by RHS and descRHS.
slp_errno slp_pdposv (const char *UPLO, slp array *A, int *descA,
slp array *RHS, int *descRHS )
[Function]
slp_pdposv computes the solution to a real system of linear equations with a symmetric
distributed positive definite coefficient matrix. The right hand side vector is represented by
RHS and descRHS.
Chapter 5: Full Storage Routines
13
5.3 Matrix Inversion
The Cholesky factorisation of a symmetric positive definite matrix can be used to efficiently
calculate the matrix inverse.
slp_errno slp_pdpotri (const char *UPLO, slp array *A, int *descA )
[Function]
slp_pdpotri computes the inverse of a real symmetric positive definite distributed matrix
using the Cholesky factorization computed by slp_pdpotrf.
5.4 Auxiliary Routines
The following auxiliary routines are available in ‘slp_array.h’.
void slp_array_set_rand (slp array *submatrix, blacs grid *procgrid )
[Function]
Fills the local array submatrix with pseudo random numbers in the interval [0; 1]. The offset
of the seed on each process should result in a matrix with full rank.
void slp_array_set_zero (slp array *submatrix )
[Function]
Fills the local array submatrix with zeros.
slp_errno slp_array_set_eye (slp array *A, int *descA )
[Function]
Creates an identity matrix using the memory of the square distributed matrix A, descA.
slp_errno slp_pdsyrk (const char *UPLO, const char *TRANSA, double
[Function]
alpha, slp array *A, int *descA, double beta, slp array *B, int *descB )
Performs one of the symmetric rank-k updates B ← αAAT + βB (TRANSA = ‘‘N’’)
or B ← αAT A + βB (TRANSA = ‘‘T’’ ). A is a general distributed matrix, B is a
symmetric distributed matrix. UPLO determines whether the lower (UPLO=‘‘L’’) or upper
(UPLO=‘‘U’’) triangle of B is overwritten.
slp_errno slp_pdgemm (const char *TRANSA, const char *TRANSB, double
[Function]
alpha, slp array *A, int *descA, slp array *B, int *descB, double beta, slp array
*C, int *descC )
Performs a general matrix-matrix multiplication of the form C ← αAB + βC.
5.5 Data In- / Output
The following routines handle the in- and output of binary data for full storage distributed
matrices.
slp_errno slp_array_fread (MPI Comm comm, char *filename,
slp array *submatrix, int *descriptor, blacs grid *procgrid )
[Function]
Reads binary data from file filename. Each process in the BLACS context specified by
procgrid reads entries independently and maps the numerical data according to the 2Dblock-cyclic distribution.
slp_errno slp_array_fread_at (MPI File fid, slp array *submatrix,
size t M, unsigned int I, blacs grid *procgrid )
[Function]
Reads binary data from file filename. Each process in the BLACS context specified by
procgrid reads entries independently and maps the numerical data according to the 2Dblock-cyclic distribution. I denotes the row offset in the matrix to be read.
Chapter 5: Full Storage Routines
14
slp_errno slp_array_fread_partial (MPI Comm comm, char
[Function]
*filename, size t M, size t N, size t MSUB, size t nblock, slp array *neqmatrix,
int *descN, blacs grid *procgrid )
Wrapper for slp_array_fread_at. Recursively computes a normal equation matrix from a
design matrix that would not fit in the available memory.
slp_errno slp_array_fwrite (MPI Comm comm, char *filename,
slp array *submatrix, int *descriptor, blacs grid *procgrid )
[Function]
Writes data to binary file filename. Each process in the BLACS context specified by procgrid
writes entries independently and maps the numerical data according to the 2D-block-cyclic
distribution. If the file filename does not exist, it is created and preallocated according to
the global size of the matrix to be written.
Chapter 6: Distributed Packed Storage Routines
15
6 Distributed Packed Storage Routines
This chapter describes the implemented functions for computation using the distributed packed
storage scheme defined in Baboulin et al. 2007.
For convenience sake one assertion has been made:
• The process with coordinates (0, 0) always holds the first block of a distributed matrix.
The functions described in the following sections are defined in the header file ‘dps_array.h’.
6.1 Array Descriptor
For matrices in distributed packed storage format an extended array descriptor is used. The
following table shows the entries of the integer array with their definition.
(Note: The macros in column two, which expand to the respective indices are defined in
‘dps_array.h’.)
0
DESC_DTYPE
Descriptor type (=1 for full storage matrices)
1
DESC_CTXT
Context handle of the BLACS process grid
over which the matrix is distributed
2
DESC_M
Number of rows in the global array
3
DESC_N
Number of columns in the global array
4
DESC_MB
Blocking factor used to distribute the rows of
the array
5
DESC_NB
Blocking factor used to distribute the columns
of the array
6
DESC_RSRC
Process row over which the first row of the
global matrix is distributed (=0)
7
DESC_CSRC
Process column over which the first column
of the global matrix is distributed (=0)
8
DESC_LLD
Local leading dimension
9
DESC_N_FULL_STORAGE
Row/column number of the matrix in full
storage
10
DESC_N_BLOCKROWS
Number of distributed block rows
11
DESC_N_DISTBLOCKS
Number of distributed blocks
12
DESC_MAX_DBS
Maximum distributed block size
13
DESC_MIN_DBS
Minimal distributed block size
Chapter 6: Distributed Packed Storage Routines
16
The local array on each of the processes is described by the following structured data type.
typedef struct {
size_t size1_;
size_t size2_;
size_t mblocks_;
size_t nblocks_;
size_t *blocksize1_;
size_t *blocksize2_;
double *data_;
} dps_array;
The members size1 and size2 denote the number of rows and columns of the local array;
mblocks , nblocks and blocksize1 , blocksize2 store the number of block rows and block
columns and the individual block sizes respectively. The local matrix elements are stored in
column-major order in member data .
dps_array * dps_array_alloc (size t size1, size t size2, size t
max_blocksize1, size t max_blocksize2 )
[Function]
Constructor for typedef’ed structure dps_array. Allocates all required memory and calculates the individual block sizes.
void dps_array_free (dps array *submatrix )
[Function]
Destructor for typedef’ed structure dps_array. Frees all memory associated with submatrix.
size_t dps_numrow (blacs grid *procgrid, size t nblock, size t
blockfactor )
size_t dps_numcol (size t N_FS, size t dps_numrows, size t *n_blocks,
size t *block_rows )
[Function]
[Function]
These functions are used to calculate the size of the horizontal array in which the distributed
block of the symmetric matrix are stored.
size_t dps_numroc (size t N, size t nblock, blacs grid *procgrid,
dps dimension dim )
[Function]
Wrapper for the ScaLAPACK routine NUMROC. Computes the size of the local submatrix.
dim is either DPS_ROW or DPS_COLUMN.
slp_errno dps_descinit (int *descA, dps array *submatrix, size t
[Function]
GLOBAL_N, size t nblock, size t blockfactor, blacs grid *procgrid )
Creates an extended array descriptor for a matrix in distributed packed storage with the
blocking factors mblock and nblock. The return value descA has to be preallocated with at
least DPS_DESCRIPTOR_SIZE*sizeof(int) bytes.
Chapter 6: Distributed Packed Storage Routines
17
6.2 Linear Equation Systems
A symmetric, positive definite matrix has a Cholesky factorisation into a product of a lower
triangular matrix and its transpose (or into a product of the transpose of an upper triangular
matrix and the upper triangular matrix itself). This factorisation can be used to convert the
linear system Ax = b into a pair of triangular systems (Ly = b, LT x = y), which can be solved
by forward and backward-substitution
slp_errno dps_pdpotrf (const char *UPLO, dps array *A, int *descA )
[Function]
dps_pdpotrf computes the Cholesky factorisation of the symmetric positive definite distributed matrix represented by A and descA. The lower (UPLO = ‘‘L’’) or upper (UPLO
= ‘‘U’’ or U T y = b, U x = y) triangle of A is overwritten in the process.
slp_errno dps_pdtrsm (const char *SIDE, const char *UPLO, const char
[Function]
*TRANSA, const char *DIAG, dps array *A, int *descA, dps array *RHS, int
*descRHS )
slp_pdpotrs solves a system of linear equations with a triangular coefficient matrix in distributed packed storage format. The right hand side vector is represented by RHS and
descRHS.
slp_errno dps_pdpotrs (char *UPLO, dps array *A, int *descA, dps array
*RHS, int *descRHS )
[Function]
slp_pdpotrs solves a system of linear equations with a symmetric positive definite distributed
coefficient matrix, using the Cholesky factorisation computed by slp_pdpotrf. The right
hand side vector is represented by RHS and descRHS.
6.3 Matrix Inversion
The Cholesky factorisation of a symmetric positive definite matrix can be used to efficiently
calculate the matrix inverse.
slp_errno dps_pdpotri (const char *UPLO, dps array *submatrix, int
*descA );
[Function]
dps_pdpotri computes the inverse of a real symmetric positive definite distributed matrix
using the Cholesky factorization computed by dps_pdpotrf.
6.4 Auxiliary Routines
The following auxiliary routines are available in ‘dps_array.h’.
void dps_array_set_zero (dps array *submatrix )
[Function]
Fills the local array submatrix with zeros.
void dps_array_set_rand (dps array *submatrix, blacs grid *procgrid )
[Function]
Fills the local array submatrix with pseudo random numbers in the interval [0; 1]. The offset
of the seed on each process should result in a matrix with full rank.
slp_errno dps_array_set_eye (dps array *submatrix, int *descA )
[Function]
Creates an identity matrix using the memory of the square distributed matrix A, descA.
Chapter 6: Distributed Packed Storage Routines
slp_errno dps_atbya (const char *UPLO, double *A, int *descA, dps array
*NEQ, int *descNEQ )
18
[Function]
Computes the matrix product AT A and stores the result in NEQ, the local array of a matrix
in distributed packed storage.
6.5 Data In- / Output
The following routines handle the in- and output of binary data for matrices in distributed
packed storage.
slp_errno dps_array_fread (MPI Comm comm, char *filename,
dps array *submatrix, int *descriptor, blacs grid *procgrid )
[Function]
Reads binary data from file filename. Each process in the BLACS context specified by
procgrid reads entries independently and maps the numerical data according to the 2Dblock-cyclic distribution.
slp_errno dps_array_fwrite (MPI Comm comm, char *filename,
dps array *submatrix, int *descriptor, blacs grid *procgrid )
[Function]
Writes data to binary file filename. Each process in the BLACS context specified by procgrid
writes entries independently and maps the numerical data according to the 2D-block-cyclic
distribution. If the file filename does not exist, it is created and preallocated according to
the global size of the matrix to be written.
Chapter 7: Packed Storage Extension Routines
19
7 Packed Storage Extension Routines
Due to the lack of inversion routines in the ScaLAPACK packed storage extension, only very
crude wrappers for Cholesky factorisation exist at this point. These allow some form of performance assesment, but are unsuitable for real world applications.
For this reason, a documentation is omitted in this manual.
Chapter 8: Function Index
20
8 Function Index
S
B
blacs_grid_alloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
blacs_grid_fprintf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
blacs_grid_free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
blacs_grid_init . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
9
9
8
D
dps_array_alloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_array_fread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_array_free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_array_fwrite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_array_set_eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_array_set_rand . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_array_set_zero . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_atbya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_descinit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_numcol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_numroc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_numrow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_pdpotrf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_pdpotri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_pdpotrs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
dps_pdtrsm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
18
16
18
17
17
17
18
16
16
16
16
17
17
17
17
I
io_process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
slp_array_alloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
slp_array_fread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_array_fread_at . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_array_fread_partial . . . . . . . . . . . . . . . . . . . . . . . 14
slp_array_free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
slp_array_fwrite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
slp_array_set_eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_array_set_rand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_array_set_zero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_descinit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
slp_error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
SLP_ERROR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
slp_numroc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
slp_pdgemm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_pdposv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
slp_pdpotrf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
slp_pdpotri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_pdpotrs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
slp_pdsyrk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
slp_timer_alloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
slp_timer_free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
slp_timer_reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
slp_timer_start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
slp_timer_stop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9