LINPACK und LAPACK

Entwicklung

Die Entwicklung der LINPACK-Bibliothek [LinUser] wurde 1974 gestartet. An der Entwicklung beteiligt waren Mitglieder der Research Section of the Applied Mathematics Division of Argonne National Laboratory und andere. Neben der Entwicklung der Bibliothek waren auch das Kennenlernen der Entwicklungsmethoden, das Vorgeben eines Massstabes für mathematische Software sowie die Brauchbarkeit für Ausbildungszwecke das Ziel. LINPACK ist somit sehr gut dokumentiert, verwendet einheitliche Prozeduraufrufe und ist sehr flexibel. Die Leitung der Entwicklergruppe übernahm J.J. Dongarra. Als Entwicklungssprache wurde Fortran verwendet.
Nach dem Start im September 1987 [LaPro] erschienen im April 1989 die ersten Routinen der LAPACK-Bibliothek [Lapack]. Diese Bibliothek bietet eine Reihe von effizienten Routinen für lineare Algebra auf High-Performance Computern. Sie baut auf der LINPACK-Bibliothek auf. Die Hauptmethode, die Algorithmen schneller zu machen, ist, sie so zu strukturieren, dass sie mit Block-Matrix-Operationen in ihren innersten Schleifen arbeiten. Diese Block-Matrix-Operationen lassen sich auf verschiedene Speicher-Architekturen optimieren. Aus [Lapack] entnehmen wir Tabelle 3.1. Sie zeigt die Geschwindigkeit in MFlops auf einem Prozessor eines Cray X-MPs für:

• die LINPACK Routine SGEFA
• die LAPACK Routine SGETRF mit Assembler BLAS
• ein hochoptimierter Assembler-Algorithmus von Cray.

 
Tabelle 3.1: Speed in Megaflops auf einem Prozessor Cray X-MP.  

BLAS

Sowohl die LINPACK- wie auch die LAPACK-Bibliothek bauen auf den sogenannten BLAS-Routinen [Blas1, Blas2, Blas3] auf. BLAS steht für Basic Linear Algebra Subprograms. Auch sie sind komplett in FORTRAN geschrieben. Die BLAS-Routinen sind in drei Pakete aufgeteilt: BLAS 1 [Blas1] für elementare Vektoroperationen, BLAS 2 [Blas2] für Matrix-Vektoroperationen und schliesslich BLAS 3 [Blas3] für Matrix-Matrix-Operationen. Für viele Computer stehen hochoptimierte Assemblerversionen der BLAS-Routinen zu Verfügung.

Benennung

Sowohl für die BLAS-Routinen wie auch für LINPACK und LAPACK finden wir eine einheitliche Benennung der Prozeduren. Der erste Buchstabe bestimmt den Datentyp [LinUser]:

S

REAL einfache Genauigkeit Fliesskomma

D

DOUBLE PRECISION doppelte Genauigkeit Fliesskomma

C

COMPLEX komplexe Zahlen mit einfacher Genauigkeit Fliesskomma

Z

COMLEX*16 komplexe Zahlen mit doppelter Genauigkeit Fliesskomma

Für einfache Genauigkeit wird meist IEEE 32-bit Fliesskomma und für doppelte Genauigkeit IEEE 64-bit Fliesskkomma verwendet.

Form der Daten

Die nächsten beiden Buchstaben bestimmen nun bei LINPACK und LAPACK die Form der Daten [LinUser]:

GE

General

GB

General band

PO

Positive definite

PP

Positive definite packed

PB

Positive definite band

SI

Symmetric indefinite

SP

Symmetric indefinite packed

HI

Hermitian indefinite

HP

Hermitian indefinite packed

TR

Triangular

GT

General tridiagonal

PT

Positive definite tridiagonal

CH

Cholesky decomposition

QR

Orthogonal-triangular decomposition

SV

Singular value decomposition

BLAS

Die letzten Buchstaben bestimmen bei den Basic Linear Algebra Subprograms die Aufgabe der Routine. Die folgende Tabelle zeigt einen Auszug, für eine vollständige Aufzählung siehe [LinUser] (BLAS Level 1), [Blas2] (BLAS Level 2) und [Blas3] (BLAS Level 3).

Blas Level 1

AXPY

Constant times a vector plus a vector

COPY

Copy x into y

SCAL

Constant times a vector

AMAX

Index of element having max absolute value

SWAP

Swap x and y

Blas Level 2

MV

Matrix-vector product

R

Rank-one update

SV

Solve a system of linear equations

Blas Level 3

MM

Matrix-matrix product

SM

Solve a system of linear equations for a matrix of right-hand sides

LINPACK

Bei LINPACK bestimmen die letzten drei Buchstaben die Aufgabe der Routine [LinUser]:

FA

Factor

CO

Factor and estimate condition

SL

Solve

DI

Determinate and/or inverse and/or inertia

DC

Decompose

UD

Update

DD

Downdate

EX

Exchange

LAPACK

Bei LAPACK bestimmen die letzten drei Buchstaben die Aufgabe der Routine (Auszug, für vollständige Liste siehe [LaImpl], Appendix A)

TRF

triangular factorization (LU, Cholesky etc.)

TF2

unblocked triangular factorization

TRS

solve system of linear equatations

TRI

compute inverse

CON

estimate condition number

QRF

perform QR factorization

Benchmark

Das Lösen linearer Gleichungsysteme wird als Benchmark verwendet, um verschiedene Computersysteme miteinander vergleichen zu können. J.J Dongarra veröffentlicht laufend eine Liste [Perf] in der alle Benchmarkresultate zusammengestellt sind.
Für den klassischen LINPACK-Benchmark wird dabei ein 100x100 System gelöst. Die Bedingungen für den Benchmark sind:

• Am Fortran Source Code dürfen keine Änderungen vorgenommen werden.
• Compiler und Operation System müssen allgemein erhältlich sein. Resultate von Betaversionen sind erlaubt, wenn auch die Resultate des Standartcompilers geliefert werden.

Der Fortran Source Code ist unter anonymous ftp in netlib/benchmark als linpacks für einfache Genauigkeit und als linpackd für doppelte Genauigkeit erhältlich.
In einer zweiten Tabelle werden die Resultate ``Toward Peak Performance'' aufgelistet. Hier herrschen folgende Regeln:

• Änderungen sind in der Routine LU erlaubt
• Beliebige Lösungsmethoden können verwendet werden
• Die Mflops-Rate wird aufgrund der Anzahl Operationen für eine LU-Faktorisierung berechnet:
• Die Hauptdriver-Routine mit ihrem Testmatrixgenerator und Residual Check muss verwendet werden.

Der Fortran Source Code ist unter anonymous ftp in netlib/benchmark als 1000s für einfache Genauigkeit und als 1000d für doppelte Genauigkeit erhältlich.
Tabelle 3 (Highly Parallel Computing) in [Perf] zeigt einen Vergleich zwischen mehreren Parallelrechnern. Hier wird die maximal erreichbare Performance für beliebig grosse Systeme verglichen.
Das beste Resultat für den klassischen LINPACK-Benchmark erreicht zurzeit ([Perf] vom 31. Mai 1993) ein CRAY Y-MP mit 16 Prozessoren: 479 Mflop/s. Unter ``Toward Peak Performance'' führt im Moment die NEC SX-3/44R mit 15120 Mflop/s. Die Tabelle 3 (Highly Parallel Computing) wird vom CM-5 (Thinking Machines) mit 1024 Prozessoren mit 59.7 Gflop/s für ein 52224-System angeführt.