Post on 06-Apr-2015
transcript
C. Boehme, O. Haan, U. Schwardmann
GWDG
Übungen II
Programmierung von Parallelrechnern
Programmierung von Parallelrechnern: Übungen II 2
Beispiele • Berechnung von durch numerische
Integration
• Raleigh - Ritz - Methode– Spaltenblock -Verteilung– Reihenblock - Verteilung
• 2-dim Wärmeleitungsgleichung
Programmierung von Parallelrechnern: Übungen II 3
Berechnung von
Inhalt des Kreissegmentes = / 4
dxx 1
0
214
Programmierung von Parallelrechnern: Übungen II 4
Numerische Integration
)(1
n
iixfI
Das Programm numint in pi.f berechnet diese Summe
Programmierung von Parallelrechnern: Übungen II 5
Aufgabe 1
Verteile die Berechnung der Summe auf nproc Tasks
p0 p1 p2 p3
Programmierung von Parallelrechnern: Übungen II 6
Numerische Integration mit vorgegebener Genauigkeit
)(1
n
iin xfI
Das Programm numintprec in pi_p.f berechnet die Summemit vorgegebener Genauigkeit
nnn IIII 22
Programmierung von Parallelrechnern: Übungen II 7
Numerische Integration mit vorgegebener Genauigkeit
Unterteilung des Integrationsgebietesin nin Intervalle, jedes Intervall mit eigenem zur Erzielung der vorgegebenen Genauigkeit
a b
nin
abab
nin
abiaa
dxxfdxxf
iii
b
a
b
a
nin
i
i
i
,
)()(1
0
Programmierung von Parallelrechnern: Übungen II 8
Aufgabe 2
Verteile die Berechnung der nin Integrale auf nproc Tasks,mit Berücksichtigung der Lastverteilung (nin >> nproc).
Hinweis: Benutze das Verarbeitungsmodell Farmer-Worker.p0 ist der Farmer, der die Aufgaben zuteilt,
p1,…pnproc-1 sind die Worker, die nach Arbeit rufen, sobald
sie frei sind.
Programmierung von Parallelrechnern: Übungen II 9
Aufgabe 2
Farmer: me = 0tres = 0Schleife über nintv Intervalle i
Empfange res von anytasktres = tres + resiw = status(mpi_source)Sende i nach iw
Schleife über np-1 Worker iwSende -1 nach iw
Worker: me > 0res = 0Sende res nach 0Schleife über nintv Intervalle iEmpfange i von 0Wenn i <0 fertigres = work(i)sende res nach 0
Programmierung von Parallelrechnern: Übungen II 10
Raleigh - Ritz - Methode
Eigenwertproblem :
Sei
210, iii vvA
0mit 0 rr ii
i vx
0
01
0000 //
v
vvvxA
nn
in
ii
in
ini
ii
n rrrr
111
0 )/)(lim xAxA nn
n
Programmierung von Parallelrechnern: Übungen II 11
Algorithmus Raleigh - Ritz
Sequentielles Fortran Programm
xx
Axx
x
A
1
1
1
Schleife
1mitWähle
Matrix ereInitialisi
x
xR
Rn
nn
Programmierung von Parallelrechnern: Übungen II 12
Parallele Matrix-Vektor Multiplikation Verteilung in Spaltenblöcken
))1(:1():1(
))1(:1():1(
))1(:1,:1():1,:1(
:Daten dieliegen Prozessor auf
und von El. , n Spalten vo / :lokal
1,,0,n Prozessore
nlipnlipynlyl
nlipnlipxnlxl
nlipnlipnAnlnAl
ip
nlnpnnl
npipnp
yxA
Programmierung von Parallelrechnern: Übungen II 13
Parallele Matrix-Vektor Multiplikation Spaltenblock-Verteilung
LokaleTeilergebnisse
GlobaleSummierung
Programmierung von Parallelrechnern: Übungen II 14
Programm ritz_dist_col Paralleler Raley-Ritz Algorithmus
mit Spaltenblock-Verteilung
Ser Eingabe: Matrixdimension n
Ser Initialisierung von A
Par Verteilung von A nach Al
Par Startwert von xl
Schleife
Par yt = Al * xl
Par globale Summe yl
Ser = yl(1)
Par verteile
Par xl = 1/* yl
ritz_dist_col
dist_index dist_matrix_colblock
DGEMVcollect_vector
MPI_BCAST
Programmierung von Parallelrechnern: Übungen II 15
Globale Summierung I : Sammeln
do end
do end
i)1-yt(ial yl(i) yl(i)
nl , 1 i do
ipfr)nl,...,t(ial),MPI_RECV(y call
ipto,..nto,...,t(iato),MPI_SEND(y call
np) (mod ip- myid ipfr
np) (mod ip myid ipto
1-np , 0 ip do
)/(
:dZeitaufwan1 npnctnpt latred
Programm in collect_vector.f
Programmierung von Parallelrechnern: Übungen II 16
Send-Receive
Bei blockierendem Senden Deadlockgefahr!
ierr)status,comm,ource,tag,datatype,cbuf,count, MPI_RECV(call
ierr)mm,est,tag,codatatype,dbuf,count, MPI_SEND(call
ierr)status,g,comm,source,rtae,t,rdatatyprbuf,rcoun
stagdest,sdatatype,scount,ECV(sbuf, MPI_SENDRcall
SENDRECV vermeidet Deadlock
Programmierung von Parallelrechnern: Übungen II 17
Globale Summierung II : MPI_REDUCE
doend
nl,...) yl, yt(ia),(MPI_REDUCE call
p)firstind(i ia
p)firstind(i- 1)pfirstind(i nl
1- nproc , 0 ip do
)/(ln
:dZeitaufwan1
2 npnctnpnpt latred
Programm in reduce_vector.f
Programmierung von Parallelrechnern: Übungen II 18
Aufgabe 1: MPI_REDUCE • Modifikation von collect-vector mit
MPI_REDUCE• Syntax : MPI_Reduce(sendbuf, recvbuf, count, datatype, operation, root, comm)
• (Dateien in Uebungen/Ritz )
Programmierung von Parallelrechnern: Übungen II 19
Aufgabe 1a: MPI_REDUCE_SCATTER • Modifikation von collect-vector mit MPI_REDUCE_SCATTER• Syntax :
MPI_Reduce_scatter(sendbuf, recvbuf, recvcounts, datatype, operation, comm)
do end
p)firstind(i- 1)pfirstind(i (ip)recvcounts
1- nproc , 0 ip do
Programmierung von Parallelrechnern: Übungen II 20
Parallele Matrix-Vektor Multiplikation Verteilung in Zeilenblöcken
))1(:1():1(
))1(:1():1(
):1,)1(:1():1,:1(
:Daten dieliegen Prozessor auf
und von El. , n Zeilen vo/ :lokal
1,,0,n Prozessore
nlipnlipynlyl
nlipnlipxnlxl
nnlipnlipAnnlAl
ip
nlnpnnl
npipnp
yxA
Programmierung von Parallelrechnern: Übungen II 21
Parallele Matrix-Vektor Multiplikation Zeilenblock-Verteilung
Bereitstellung desglobalen Vektors
LokaleErgebnisse
Programmierung von Parallelrechnern: Übungen II 22
Programm ritz_dist_rowParalleler Raley-Ritz Algorithmus
mit Zeilenblock-Verteilung
Ser Eingabe: Matrixdimension n
Ser Initialisierung von A
Par Verteilung von A nach Al
Par Startwert von xl
Schleife
Par globaler Vektor xt
Par yl = Al * xt
Ser = yl(1)
Par verteile Par xl = 1/ * yl
ritz_dist_row
dist_indexdist_matrix_rowblock
global_vector
DGEMV
MPI_BCAST
Programmierung von Parallelrechnern: Übungen II 23
Abgeleitete Datentypen für die Verteilung der globalen Matrix a
MPI_Type_vector(int count,int blocklen,int stride, MPI_Datatype oldtype,MPI_Datatype *newtype)
z.B. ml x n Zeilenblock einer m x n Matrix:
m
n
mlcount = nblocklen = mlstride = m
Programmierung von Parallelrechnern: Übungen II 24
Aufgabe: Benutze Type_vector zur Verteilung von a
Modifiziere dist_matrix_rowblock 1. Definition eines neuen Typs rowblock mit
MPI_TYPE_VECTOR
2. Aktivieren des Typs mit MPI_TYPE_COMMIT(rowblock,ierrr)
3. Senden mit MPI_SEND(a[ia],1,rowblock,ip,0, MPI_COMM_WORLD,ierr)
4. Deaktivieren des Typs mit MPI_TYPE_FREE(rowblock,ierr)
Programmierung von Parallelrechnern: Übungen II 25
Aufgabe 2: global_vector• Modifikation von global_vector mit
MPI_ALLGATHERSyntax:MPI_ALLGATHERV(sendbuf, sendcount, sendtype, recvbuf, recvcounts, displs, recvtype, comm, ierr)
do ip = 0 , nproc -1
recvcounts(ip) = firstind(ip+1) – firstind(ip)
displs(ip) = firstind(ip) – 1
end do
• (Dateien in Uebungen/Ritz )
Programmierung von Parallelrechnern: Übungen II 26
Aufgabe 2a: global_vector
• Modifikation von global_vector mit MPI_SENDRECV
Programmierung von Parallelrechnern: Übungen II 27
Wärmeleitungsgleichung
),1(,),0(,)1,(,)0,(
),(0
)1,()1,(),1(),1(
),(),(
)1:0()(1,0 :erungDiskretisi
),,(,),0(
1,01,0),,(),(),(
2211
21
21212121
2121
2,12,1
:Randwerte
: teAnfangswer
: PunkteInnere
: Randwerteu. -Anfangs
inuiuniuiu
iiu
iiuiiuiiuiiur
iiusiiun
nix
tuu
tftuktuc t
xxx
xxxx
Programmierung von Parallelrechnern: Übungen II 28
Finite-Differenzen Gitter
Programmierung von Parallelrechnern: Übungen II 29
Algorithmus Wärmeleitung
unu
epsdiff
uundiff
utzeitschritun
randnu
anfnnu
epsrnnnt
Kopieren
stop wenn
:Beendigung aufTest
Änderung
)(: eitschritt Z
Schleife
,...)11:0,0(
,)2:1,1:1( Startwerte
,,2,1, :Eingabe
zeitschritt
initialisierung
norm
kopie
waermeleitung
Programmierung von Parallelrechnern: Übungen II 30
Partitionierung mit Randaustausch
Programmierung von Parallelrechnern: Übungen II 31
Algorithmus Wärmeleitung - parallel
unu
epsdiff
uundiff
utzeitschritun
randnu
anfnnu
epsrnnnt
Kopieren
stop wenn
:Beendigung aufTest
Änderung
)(: eitschritt Z
schRandaustau
Schleife
,...)11:0,0(
,)2:1,1:1( Startwerte
,,2,1, :Eingabe
zeitschritt
Initialisierung_mpi
norm
kopie
Waermeleitung_mpi
randaustausch
Programmierung von Parallelrechnern: Übungen II 32
Randaustausch
Mit MPI_SENDRECV:Jeder Prozessor sendet 1. Spalte nach links, empfängt Werte für 0. Spalte von links,Jeder Prozessor sendet n2l. Spalte nach rechts, empfängt Werte für n2l+1. Spalte von rechts.
Randspalten werden mit Prozessor MPI_PROC_NULL ausgetauscht!
Subroutine randaustausch
Programmierung von Parallelrechnern: Übungen II 33
Skalierungsanalyse
npnprr
npn
crnnp
trnnp
nprr
cntrnpnttt
n
npn
np
lat
np
latkore
/const
Prozessor proPunkten von Zahlkonstante :Skalierung
/1
1
)(2/6
Werte2 : dionsaufwanKommunikat
nOperatione /6 : andRechenaufw
2
231
112
2
Programmierung von Parallelrechnern: Übungen II 34
2-dimensionale Verteilung
nprr
npn
crnnq
trnnp
nprr
cnqntrnpnttt
npnnqn
npn
nnqnp
np
lat
np
latkore
const
Prozessor proPunkten von Zahlkonstante :Skalierung
/1
1
)/(4/6
Werte/4/4 : dionsaufwanKommunikat
nOperatione /6 : andRechenaufw
: eGittergröß , ahlProzessorz
2
232
112
2
2
22
Programmierung von Parallelrechnern: Übungen II 35
Aufgabe 3: Wärmeleitungsgleichung mit 2-dim. Verteilung
Modifikation gegenüber 1-dim Verteilung:
Eingabe von nq1,nq2 Überprüfen, ob nq1*nq2 gleich nprocGenerieren der Blockgrößen n1l,n2lAbbildung myid->(myid1,myid2)Initialisierung der lokalen Blöcke Randaustausch bei 2-dim Verteilung
(Dateien in Uebungen/Waermeleitung )