Umeå Universitet
Institutionen för datavetenskap Elmroth, Kågström |
Design och analys av algoritmer
11 Januari 2001för parallelldatorsystem - vt2001 Läsanvisningar |
Kursintroduktion och modeller för parallella beräkningar,
Kapitel 2.7, appendix A (kapitel 1 och 2)
Kopior av utdelat material i postscript
Syfte: Att placera in kursen i sitt sammanhang, att ge en repetition
av grundläggande modeller, att introducera nödvändiga begrepp
och beteckningar, samt att klara av en del praktiska problem.
Innehåll: Kommunikationskostnader (uppstartningstid, per-hopp-tid,
tid per ord), lagra-vidarebefordra (store-and-forward), direkt-igenom (cut-through).
Komplexitetsfunktioner. Därtill självstudier för att repetera
följande: Klassificering av parallella arkitekturer: kontrollmekanism,
minnesorganisation (gemensamt, distribuerat), nätverk, kornighet,
PRAM, dynamiska nätverk, crossbar, buss, flerstegsnätverk (multistage
networks), statiska nätverk, linjär lista, ring, 2-dimensionella
nät, träd, hyperkub, utvärdering av nätverk, diameter,
connectivity, bandbredd, inbäddning av andra nätverk i en hyperkub,
routing.
Grundläggande kommunikationsoperationer, Kapitel 3, sid 65 -
101
Kopior av utdelat material i postscript
Syfte: Att ge kunskap om algoritmer för grundläggande
kommunikationsoperationer och deras komplexitet.
Innehåll: Detaljerad beskrivning och analys av kommunikationsoperationer
som används boken igenom. Vanliga kommunikationsmönster: 1-till-1
kommunikation, utsändning (broadcast), alla-till-alla utsändning,
reduktion, prefix summering, "personlig" kommunikation (1-till-alla, alla-till-alla),
cirkulär skiftning. Analys av samtliga kommunikationsoperationer
för en eller flera av topologierna ring, 2-dimensionellt nät,
hyperkub eller balanserat träd. Analys för nätverk med principerna
lagra-vidarebefordra (store-and-forward) och direkt-igenom (cut-through).
Prestanda och skalbarhet för parallella system, Kapitel 4, sid
117 - 138
Kopior av utdelat material i postscript
Syfte: Att ge kunskap om hur ett parallellsystems prestanda
och skalbarhet kan utvärderas.
Innehåll: Prestandamått: exekveringstid, uppsnabbning,
effektivitet och kostnad. Kornighet och datafördelningens inverkan
på prestanda. Skalbarhet, isoeffektivitet, isoeffektivitetsfunktionen,
grad av parallellitet, kostnadsoptimalt, lastbalansering samt undre gränser
för exekveringstid.
Algoritmer för täta matriser 1, Kapitel 5, sid 151 - 178
Syfte: Att ge kunskap om vanliga mönster för att avbilda
matriser på processorer, samt parallella algoritmer för grundläggande
matrisoperationer.
Innehåll: Mönster för att avbilda matriser på
parallelldatorer: blockpartitionering och schackbrädespartitionering.
Matristransponering för olika datadistributioner på 2-dimensionellt
nät och hyperkub. Matris-vektor-multiplikation för olika
datadistributioner med utförlig prestanda- och skalbarhetsanalys.
Algoritmer för matrismultiplikation: enkel algoritm, Cannons
algoritm, Foxs algoritm och DNS-algoritmen (3-dimensionellt nät av
processorer), med utförlig prestanda och skalbarhetsanalys för
samtliga algoritmer på olika topologier.
Algoritmer för täta matriser 2, Kapitel 5, sid 178 - 196
Syfte: Att ge kunskap om parallella algoritmer för lösning
av linjära ekvationssystem.
Innehåll: Lösning av linjära system med
gausselimination för olika datadistributioner, överlappning av
kommunikation och beräkningar, pivotering, lösning av triangulära
system samt numeriska hänsyn.
Grafalgoritmer, Kapitel 7, sid 257 - 281
Kopior av utdelat material i postscript
Syfte: Att ge kunskap om hur viktiga och grundläggande
grafalgoritmer för att finna minsta uppspännande träd, och
för att beräkna sammanhängande komponenter kortaste vägen
kan formuleras parallellt.
Innehåll: Definitioner och representation. Parallell version
av Prims algoritm för att finna minsta uppspännade träd.
Kortaste vägen: Dijkstras algoritm, Floyds algoritm och matrismultiplikationsbaserad
algoritm. Djupet-först-algoritm för att finna sammanhängade
komponenter med analys för block-bandpartitionering av data.
Portabel och effektiv programvara för MIMD-arkitekturer, Utdelat
material
Kopior av utdelat material
Innehåll: Byggblock för vektor- och matrisberäkningar
Syfte: Att ge kunskap om algoritmutveckling med beaktande av
hög prestanda och portabilitet för olika typer av skalbara parallella
miljöer.
(Level-1-2-3 BLAS). Design av ett högpresterande Level-3 BLAS. GEMM-Based
Level-3 BLAS. LAPACK, ScaLAPACK: Bibliotek för högpresterande
beräkningar. Parallella blockalgoritmer för distribuerat respektive
gemensamt minne. Portabilitetsaspekter över och mellan olika parallella
plattformar.
Sökningsalgoritmer för diskreta optimeringsproblem 1, Kapitel
8, sid 299 - 315, 321 - 324, 328 - 329, 332 - 336
Syfte: Att ge kunskap om parallella djupet-först-algoritmer
för sökning med tillämpningar i diskret optimering och i
sammanhanget användbara lastbalanseringsalgoritmer, samt att ge förståelse
för effektiviteten hos olika lastbalanseringsalgoritmer för parallella
djupet-först-algoritmer, samt att ge kunskap om några varianter
av parallella djupet-först- och bäst-först-algoritmer.
Innehåll: Definitioner och exempel (0/1 heltalsproblemet
i linjär programmering, 8-pusslet). Sekventiella djupet-först-algoritmer
(exempelvis iterativ fördjupning A*). Sekventiella bäst-först-algoritmer
(A*). Overheadfaktor i sökning. Arbetsfördelning, lastbalanseringsscheman
(asynkron round-robin, global round-robin, slumpmässigt
val (random polling)). Analys av lastbalanseringsalgoritmer för parallella
djupet-först-algoritmer för olika typer av parallellsystem, algoritmer
för att upptäcka terminering, parallella versioner av djupet-först
branch-and-bound och iterativ fördjupning A*. Parallell formulering
av bäst-först-algoritmer med olika kommunikationsstrategier.
FFT, Kapitel 10, sid 377 - 388, 393 - 396
Syfte: Att ge kunskap om parallella algoritmer för beräkning
av FFT (fast Fourier transform), som har tillämpningar i t ex lösning
av partiella differentialekvationer, analys av vågrörelser,
signalbehandling och filtrering av bilder.
Innehåll: En seriell algoritm. Parallella algoritmer:
binary
exchange-algoritmen för olika topologier och transponeringsalgoritmen.
Grid-computing (material delas ut under kursens gång)
Syfte: Att ge en introduktion till Grid-computing, som idag
är en av de starkaste trenderna inom parallella och högpresterande
beräkningar.
Innehåll: Grundläggande beskrivning av konceptet
grid-computing som i en yttersta förlängning kan få hela
världens beräkningsresurser att smälta samman till ett värdsomspännande
beräkningsnät. (Namnet grid ska ses som analogt med begreppet
powergrid för elnät). Tillämpningsexempel, motivering, arkitektur,
samt programvaror och verktyg som t.ex. globus och NetSolve.
Lösning av glesa system av linjära ekvationer 1, Kapitel
11, sid 407 - 426
Syfte: Att ge kunskaper om representation av glesa matriser,
att ge insikt i tillämpningar där glesa matriser förekommer,
ge kunskap om grundläggande sekventiella och parallella algoritmer
för operationer på glesa matriser, samt att ge kunskap om parallella
iterativa och direkta metoder för lösning av glesa linjära
ekvationssystem
Innehåll: Exempel på tillämpningar som ger
upphov till glesa matriser. Grundläggande operationer och matrislagringsformat:
komprimerad radlagring, (koordinatformat, diagonallagringsformat, Ellpack-Itpack-format,
Jagged-diagonal) beräkning av skalärprodukt och matris-vektormultiplikation
och block-tridiagonala matriser. Algoritmer för strukturerade och
ostrukturerade matriser. Iterativa metoder: Jacobi, Gauss-Seidel,
SOR och konjugerade gradientmetoden. Direkta metoder för glesa
system: algoritmer för omordning av element för att minimera
ifyllnad, symboliska faktoriseringar, numeriska faktoriseringar, eliminationsträd,
lösning av triangulära system.
Tillämpningsexempel: Parallell grundvattensimulering, paper
1, paper
2
Syfte: Att med ett sammanhållet exempel illustrera hur
en applikationsprogramvara för ett skalbart parallelldatorsystem kan
utvecklas från ett seriellt program till ett välfungerande tillämpningsprogram
för ett stort skalbart parallelldatorsystem .
Innehåll: Problemformulering och introduktion till en
etablerad programvara för grundvattensimulering. Genomgång av
huvudstegen för utveckling av en parallell version av programvaran:
I/O, partitionering av en diskretiserad domän, programvaruinfrastruktur
för datadistribution och -omordning, matrisrepresentation, distribuerad
representation av glesa block-matriser, parallella lösare för
glesa system, prekonditonerare, etc. Något om olika
partitioneringsalgoritmer
och intressanta egenskaper hos domänbaserade prekonditionerare.
Prestandajämförelser
mellan olika partitioneringsalgoritmer. Analyser och prestandaresultat
för hela tillämpningsproblemet på 512-processorers
Cray T3E. Aktuella testproblem är ett 2D- och ett 3D-problem från
en studie av lämpligheten att slutförvara avfall från kärnkraftverk
i Yucca Mountains i Nevada, USA.