1 Numerische Bibliotheken Lineare Algebra Fourier-Transformationen Bibliotheken auf dem Linux-Cluster Programmierung von Parallelrechnern C. Boehme, O

1

Numerische BibliothekenLineare Algebra

Fourier-TransformationenBibliotheken auf dem Linux-Cluster

Programmierung von ParallelrechnernC. Boehme, O. Haan, U. Schwardmann

GWDG

Programmierung von Parallelerechnern: Analyse 2

Nutzungsvorteile

• Einsatz numerischer Methoden ohne eigenen Entwicklungs-aufwand

• Expertenwissen über Algorithmen, Numerik und Programmierung sind in Programmbibliotheken gesammelt

Plattformübergreifende Bibliotheken: NAG, IMSL

Plattformspezifische Bibliotheken: MKL (Intel), ESSL (IBM)


Zielkonflikt: Portabilität oder Performanz• Plattformübergreifende Bibliotheken: werden in Standard

Sprache (FORTRAN, C, C++) programmiert und können auf allen Plattformen installiert werden. Optimierung für unterschiedliche Hardware nur über Compiler-Optionen.

• Plattformspezifische Bibliotheken: Werden vom Hardware-Hersteller entwickelt für optimale Leistung auf den eigenen Systemen.Schnittstellen zu den Verfahren sind nicht einheitlich, Programme sind deshalb nicht portabel.


Standardisierte Schnittstellen• Definition und Standardisierung von Schnittstellen zu Basis-

Operationen für eine Klasse von Algorithmen• Hardwarespezifische Implementierung der Basis-Operationen• Portable Implementierung der Algorithmen unter Nutzung der

standardisierten Schnittstellen • Kleiner Satz von Hardware-optimierten Basis-Operationen

führt zu portablen und performanten Programmen• Beispiele: MPI Message Passing Interface

BLACS Basic Linear Algebra Communication Subprograms

BLAS Basic Linear Algebra SubprogramsFFTW Fastest Fouriertransformation in the West


BLAS• Basic Linear Algebra Subprograms• Basis Operationen für Algorithmen der linearen Algebra:

GleichungslöserLeast Square FitEigenwert- und EigenvektorberechnungSingulärwert-Zerlegung

• Level 1 : Vektor-Vektor-Operationen• Level 2 : Matrix-Vektor-Operationen (Optimierung für Pipeline-

Nutzung) • Level 3 : Matrix-Matrix-Operationen (Optimierung für Cache-

Nutzung)


BLAS Level 2 Operationen

ijj

iji yxAy

ijjiij AyxA

jj

iji xAb

MV : Matrix-Vektor-Produkt

R, R2 : Rang 1, Rang 2 Modifikation

SV : Lösung eines Dreiecksgleichungssystem


BLAS Datentypen und Matrixformen• Datentypen:

S realD double precisionC complexZ complex*16

• Matrixformen: GE allgemeine Matrix (GEneral)GB allgemeine Bandmatrix (General Banded)HE HErmite‘sche MatrixSY Symmetrische MatrixHP Hermite‘sche Matrix gePackt gespeichertSP Symmetrische Matrix gePackt gespeichertHB Hermite‘sche Bandmatrix SB Symmetrische BandmatrixTR Dreiecksmatrix (TRiangular) TP Dreiecksmatrix gepackt gespeichert (Triangular Packed)TB Dreiecksbandmatrix (Triangular Banded)


BLAS Level 2 Routinen• Namenskonvention:

Name = Datentyp-Matrixform-Operation• Erlaubte Kombinationen:

reell komplex MV R R2 SVS[D]GE C[Z]GE * *S[D]GB C[Z]GB *S[D]SY C[Z]HE * * *S[D]SP C[Z]HP * * *S[D]SB C[Z]HB *S[D]TR C[Z]TR * *S[D]TP C[Z]TP * *S[D]TB C[Z]TB * *


BLAS Level 3 Operationen

ijljl

ilij CBAC

ljl

ilij CAB

MM : Matrix-Matrix-ProduktRK, R2K : Rang k, Rang 2k Modifikation

SM : Lösung eines Dreiecksgleichungssystem mit mehreren rechten Seiten


BLAS Level 3 Routinen

• Erlaubte Kombinationen:

reell komplex MM RK R2K SMS[D]GE C[Z]GE * *S[D]SY C[Z]SY *

C[Z]HE * * *S[D]TR C[Z]TR * *


BLAS Aufrufe• Beispiel MV, MM

“ y = alpha*a*x + beta*y“ call dgemv(trans,m,n,alpha,a,lda,x,incx,beta,y,incy)

“ c = alpha*a*b + beta*c“ call dgemm(transa,transb,m,n,l,alpha,a,lda,b,ldb,beta,c,ldc)

• Parameter

trans, transa, transb Zugriff auf Matrix(= Ń´,´T´ oder Ć´)a(lda,*), b(ldb,*), c(ldc,*) Matrizenm,n,l Matrix-Dimensionenlda,ldb,ldc,incx,incy Speicherform der Datenalpha, beta Skalare


BLAS Aufrufe – C-Interface• Beispiel MV, MM

“ y = alpha*a*x + beta*y“ cblas_dgemv(CblasRowMajor,CblasNoTrans,m,n,alpha,a,lda,x,incx,beta,y,incy)

“ c = alpha*a*b + beta*c“

cblas_dgemm(CblasRowMajor,CblasNoTrans,CblasNoTrans,m,n,l,alpha,a,lda,b,ldb,beta,c,ldc)

• Parameter

CblasRowMajor, CblasColMajor Speicherung der MatrixCblasNoTrans, CblasTrans, Zugriff auf MatrixCblasConjTrans a, b, c Matrizenm,n,l Matrix-Dimensionenlda,ldb,ldc,incx,incy Speicherform der Datenalpha, beta Skalare


BLAS Aufrufe – C-Interface(2)• Deklaration der Matrizen:

• Include File: cblas.h• Dokumentation: http://www.netlib.org/blas/blast-forum/cinterface.pdfcblas.h


BLACS

• Basic Linear Algebra Communication Subprograms

• Strukturierte Message Passing Bibliothek

• Kommunikationsschnittstelle für ScaLAPACK

• Unterstützt 2-dim. Prozessortopologie

• Unterstützt Matrix-Datenstrukturen

• Implementierungen für verschiedene Message Passing Umgebungen: MPI, PVM, …


2-dim. Prozessortopologie• np Prozessoren ip = 0 , … , np – 1 als 2-dim. Feld anordnen:

np = np1 * np2, ip1 = 0 , … , np1 - 1ip2 = 0 , … , np2 - 1

• Abbildung zwischen linearer und 2-dim. Anordnung Spalten-Anordnung

ip = ip1 + np1*ip2ip2 = Ganzzahliger Teil von ip/np1, ip1 = ip –np1 * ip2

Zeilen-Anordnungip = ip2 + np2*ip1ip1 = Ganzzahliger Teil von ip/np2, ip2 = ip –np2 * ip1


ip 0 1 2 3 4 5

(ip1,ip2)(0,0)

(1,0)

(2,0)

(0,1)

(1,1)

(2,2)

np = 6, np1 = 3, np2 = 2Spalten-Anordnung


BLACS HilfsroutinenBLACS_PINFO(myip,np)

np: Gesamtzahl verfügbarer Prozessorenmyip: Prozessornummer des ausführenden Prozessors

BLACS_GRIDINIT(icntxt,´r´,nprow,npcol)erzeugt Kommunikationskontext icntxt mit nprow*npcol

ProzessorenBLACS_GRIDINFO(icntxt,nprow,npcol,myiprow,myipcol) nprow, npcol: verfügbare Prozessor-Topologie

myiprow,myipcol: Koordinaten des ausführenden Prozessors

BLACS_GRIDEXIT(icntxt)gibt den Kommunikationskontext icntxt frei


BLACS KommunikationsroutinenBLACS kommuniziert 2 Datenstrukturen:GE (Rechteck): M Reihen, N Spalten, eines 2-dim Feldes mit führender Dimension LDA

TR (Trapez): durch M,N,LDA und UPLOW charakterisiert

NM

N-M+1

NMN-M+1

N N

M M

N-M+1

N-M+1

UPLO = Ú´

UPLO = ´L´

N >= M N < M


BLACS Kommunikationsroutinen• BLACS kommuniziert 5 Datentypen:

I integerS realD double precisionC complexZ complex*16

• 4 Formen der Kommunikation:SD Punkt zu Punkt SendenRV Punkt zu Punkt EmpfangenBS Broadcast SendenBR Broadcast Empfangen


Syntax der BLACS Kommunikationcall DGESD2D(icntxt,m,n,a,lda,rdest,cdest)call DTRSD2D(icntxt,uplo,diag,m,n,a,lda,rdest,cdest)call DGERV2D(icntxt,m,n,a,lda,rsrc,csrc)call DTRRV2D(icntxt,uplo,diag,m,n,a,lda,rsrc,csrc) uplow = ú´ oder ´l´ , diag = ú´ (Diagonalelemente werden nicht

kommuniziert) oder ń´ (Diagonalelemente werden kommuniziert)

call DGEBS2D(icntxt,scope,top,m,n,a,lda)call DGEBR2D(icntxt,scope,top,m,n,a,lda,rsrc,csrc) scope = á´ (alle), ´r´ (Reihe), ć´ (Spalte) top berücksichtigt physikalische Vernetzung. top = ´ ´ ist immer richtig


Beispiel Broadcast• Sende Matrix a an alle Prozessoren der gleichen Reihe:

call BLACS_GRIDINIT(icntxt,´r´,npr,npc)call BLACS_GRIDINFO(icntxt,npr,npc,myipr,myipc)if (myipr.eq.1) then if (myipc.eq.0) then call DGEBS2D(icntxt,´r´,´ ´,m,n,a,lda) else call DGEBR2D(icntxt,´r´,´ ´,m,n,a,lda,1,0) end ifend if


BLACS Synchronisationcall BLACS_BARRIER(icntxt,scope) Beispiel:

call BLACS_GRIDINIT(icntxt,´r´,npr,npc)call BLACS_GRIDINFO(icntxt,npr,npc,myipr,myipc)call BLACS_BARRIER(icntxt,á´)

oder:if (myipr.eq.1) then call BLACS_BARRIER(icntxt,´r´)end if

Oder: if (myipc.eq.0) then call BLACS_BARRIER(icntxt,ć´)end if


LAPACK• LAPACK (Linear Algebra PACKage) enthält Verfahren der

linearen Algebra zur Lösung von Gleichungen, für Least Square Fits, zur Bestimmung von Eigenwerten und Eigenvektoren und zur Singulärwertbestimmung.

• LAPACK setzt vollständig auf BLAS Level 2 Level3 Operationen auf.

• LAPACK ist portabel und performant (hängt von der Güte der BLAS-Implementierung ab)


LAPACK Datentypen und Matrixformen• Datentypen S D C Z (wie BLAS)• Matrixformen (u.a.):

GE allgemeine Matrix (GEneral)GB allgemeine Bandmatrix (General Banded)HE HErmite‘sche MatrixSY Symmetrische MatrixHP Hermite‘sche Matrix gePackt gespeichertSP Symmetrische Matrix gePackt gespeichertHB Hermite‘sche Bandmatrix SB Symmetrische BandmatrixTR Dreiecksmatrix (TRiangular) TP Dreiecksmatrix gepackt gespeichert (Triangular Packed)TB Dreiecksbandmatrix (Triangular Banded)OR ORthogonale MatrixOP Orthogonale Matrix gePackt gespeichert PO POsitiv definite Matrix PB Positiv definite Band-MatrixPP Positiv definite Matrix gePackt gespeichertUN UNitäre MatrixUP Unitäre Matrix gePackt gespeichert


LAPACK Routinen

• Hilfsroutinen, die für die Verfahren der Linearen Algebra benötigt werden

• Verfahren der Linearen Algebra wie LU-Zerlegung, QR-Zerlegung, Hessenberg-Reduktion, Reduktion auf Tridiagonalform, Eigenwertberechnung durch Bisektion und viele mehr

• Driver Routinen zur Gleichungslösung etc., setzen auf obigen Verfahren auf


Einige LAPACK DriverroutinenSV Faktorisierung der Matrix und Lösung der Gleichung

SVX zusätzlich mit Fehlerabschätzung und iterativer Verbesserung GLM Löst generalisierte lineare RegressionLS löst über- und unterdeterminierte Systeme mit Hilfe orthogonaler FaktorisierungLSE Löst lineare Least Square Probleme mit NebenbedingungenLSX erzeugt Lösung minimaler Norm mit Hilfe orthogonaler Faktorisierung LSS Löst Least Square Problem mit Hilfe der Singulärwertzerlegung

EV Berechnet alle Eigenwerte und -vektorenEVX Berechnet ausgewählte Eigenwerte und –vektorenES Berechnet alle Eigenwerte und Schur-VektorenGV Berechnet generalisierte Eigenwerte- und vektorenSVD Berechnet Singulärwerte und -vektoren


Beispiel : DGESV• DGESV computes the solution to a real system of linear

equations A * X = B, where A is an N-by-N matrix and X and B are N-by-NRHS matrices.

• The LU decomposition with partial pivoting and row interchanges is used to factor A as A = P * L * U, where P is a permutation matrix, L is unit lower triangular, and U is upper triangular. The factored form of A is then used to solve the system of equations A * X = B.

• Aufruf:

call DGESV( N, NRHS, A, LDA, IPIV, B, LDB, INFO )


ScaLAPACK• Im Message Passing Programmiermodell parallelisierte Form der

LAPACK Bibliothek• Setzt auf BLAS und BLACS auf

ScaLAPACK

LAPACK PBLAS

BLAS BLACS

portierbar

maschinen-spezifisch


Verteilte Datenstrukturen• Zyklische Blockverteilung: Aufeinanderfolgende Blöcke

konstanter Größe werden zyklisch auf Prozessoren verteilt• Parameter der Verteilung:

m Länge des globalen Feldesmb Länge der Blöcke np Anzahl der Prozessorennsrc Prozessor für ersten Block

• Beispiel m = 9, mb = 2, np = 2, nsrc = 1

v1 v2 v3 v4 v5 v6 v7 v8 v9

ip = 0 ip = 1 v1 v2v3 v4 v5 v6v7 v8 v9


Zyklische Blockverteilung von Matrizen• Parameter der Verteilung:

m1,m2 Dimensionen der globalen Matrix mb1, mb2 Dimensionen der Blöckenp1, np2 Dimensionen des Prozessor-Gitters (np=np1*np2)nsrc1, nsrc2 Koordinaten des Prozessors für ersten Block

• Beispiel: m1=5, m2=7, mb1=mb2=2, np1=np2=2, nsrc1=0, nsrc2=0

a11 a12

a21 a22

a13 a14

a23 a24

a15 a16

a25 a26

a17

a27

a31 a32

a41 a42

a33 a34

a43 a44

a35 a36

a45 a46

a37

a47

a51 a52 a53 a54 a55 a56 a57

a11 a12

a21 a22

a15 a16

a25 a26

a51 a52 a55 a56

a13 a14

a23 a24

a17

a27

a53 a54 a57

a31 a32

a41 a42

a35 a36

a45 a46

a33 a34

a43 a44

a37

a47


L-U-Zerlegung einer Matrix: A = L * U

0

1

2

0

1

2

0

1

0 1 2 0 1 2 0 1

Operationen auf Teilmatrizen: kleine Blöcke: gute Last-Verteilunggroße Blöcke: gute EinzelprozessorLeistung


Deskriptoren für verteilte MatrizenJede Verteilte Matrix a wird durch einen Deskriptor mit 9 Elementen charakterisiert:

desca(1) = 1desca(2) = icntxtdesca(3) = m1 desca(4) = m2desca(5) = mb1 desca(6) = mb2desca(7) = nsrc1 desca(8) = nsrc2desca(9) = llda

Die lokalen Daten der verteilten Matrixwerden in einem Feld a(llda,ld2) gespeichert,mit llda >= Anzahl lokal gespeicherter Zeilenld2 >= Anzahl lokal gespeicherter Spalten

Der Deskriptor wird mit initialisiert mit dem Aufruf

call DESCINIT(desca,m1,m2,mb1,mb2,nscr1,nsrc2, icntxt,llda,info)


Beispiel Gleichungslösercall PDGESV(n,nrhs,a,ia,ja,desca,ipiv,b,ib,jb,descb,info)

Gegeben ist eine globale Matrix A, deren Verteilung durch desca definiert ist, und eine globale Matrix B mit der Verteilung descb.Die Dimension der globalen Matrix A ist desca(3)*desca(4)Die Dimension der globalen Matrix B ist descb(3)*descb(4)

PDGES löst das Gleichungssystem, das durch die n*n Submatrix von A mit den Elementen (ia:ia+n-1,ja:ja+n-1) definiert wird, wobei die n*nrhs Submatrix von B mit den Elementen (ib:ib+n-1,jb:jb+nrhs-1) die nrhs rechten Seiten definiert.Die nrhs Lösungen überschreiben die rechten Seiten.ipiv enthält die Information über die Umordnung der Reihen von A bei der Pivotisierung.


Beispiel Gleichungslöserschlechte Verteilung

call BLACS_INIT(icntxt,´r´,np,1) nb = (n + np – 1) / npcall DESCINIT(desca,n,n,nb,n,0,0,icntxt,nb,info)call DESCINIT(descb,n,1,nb,1,0,0,icntxt,nb,infocall PDGESV(n,1,a,1,1,desca,ipiv,b,1,1,descb,info)

a b


Beispiel Gleichungslösergute Verteilung

np = nq*nqcall BLACS_INIT(icntxt,´r´,nq,nq) call DESCINIT(desca,n,n,nb,nb,0,0,icntxt,nb,info)call DESCINIT(descb,n,1,nb,1,0,0,icntxt,nb,infocall PDGESV(n,1,a,1,1,desca,ipiv,b,1,1,descb,info)

a b


Dokumentation• BLAS :

http://www.netlib.org/blas/• BLACS :

http://www.netlib.org/blacs/• PBLAS :

http://www.netlib.org/scalapack/html/pblas_qref.html• LAPACK :

http://www.netlib.org/lapack/http://www.netlib.org/lapack/lug/index.html

• ScaLAPACK :http://www.netlib.org/scalapackhttp://www.netlib.org/scalapack/slug/index.html

http://www.netlib.org/blas/

http://www.netlib.org/blacs/

http://www.netlib.org/scalapack/html/pblas_qref.html


Bibliotheken auf dem Woodcrest-ClusterIntel Math Library mkl :-L/usr/product/parallel/intel/mkl81/lib/em64t NAG Library :-L/usr/product/nag/

IMSL Library :/usr/product/imsl/CTT6.0/lib/lib.linux/


Bibliotheken: Intels MKLMKL = Mathematical Kernel Library Enthält:

BLASSparse BLAS (Level 1)LAPACK Routinen zum GleichungslösenLAPACK-Routinen für EigenwertproblemeFourier Transformationen (FFT)

FFTW-Interface zu MKL-FFTVML (Vector Mathematical Function Library)

Berechnet mathematische Funktionen für Vektorargumente


Intels MKL - Nutzung -lmkl

Bindet BLAS, FFT-lmkl_lapack64

Bindet 64bit LAPACK-Routinen-lvml Bindet die Vektor-Funktionen

zur Berechnung von sin, cos etc.Dokumentation zu mkl unterServices -> Rechenanlagen -> Parallelrechner ->

Woodcrest-Cluster -> Dokumentation


Link zum Messprogramm time_dgemv.f


MPI-Profiling 1• MPI-Standard definiert Profiling-Interface

– Externe Profiling-Bibliotheken können dieses Interface nutzen• Profiling-Bibliothek MPE wird bei MPICH / MVAPICH

mitgeliefert– Einbinden durch Compiler-Switch -mpilog:mpicc -mpilog ...mpif77 -mpilog ...


MPI-Profiling 2• Mit MPE verlinkte Programme erzeugen Log-Datei zur

Laufzeit• Log-Visualisierer Jumpshot-4Download auf gwdu102:wget ftp://ftp.mcs.anl.gov/pub/mpi/slog2/slog2rte.tar.gz

Installieren:tar -xvzf slog2rte.tar.gz

Starten der Visualisierung:java -jar slog2rte-1.2.6/lib/jumpshot_launcher.jar


MPI-Profiling 3• <progname>.clog

öffnen• Anweisungen zum

Konvertieren in .slog2 folgen

Dokumentation:ftp://ftp.mcs.anl.gov/pub/mpi/slog2/js4-usersguide.pdfhttp://www-unix.mcs.anl.gov/perfvis/software/viewers/jumpshot-4/usersguide.html

Documents

1 Numerische Bibliotheken Lineare Algebra Fourier-Transformationen Bibliotheken auf dem Linux-Cluster Programmierung von Parallelrechnern C. Boehme, O