Umeå Universitet
Institutionen för datavetenskap Elmroth, Kågström |
Design och analys av algoritmer
4 Februari 2000för parallelldatorsystem - vt2000 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, tvärslå (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, förbindelse (connectivity), bandbredd, inbäddning av
andra nätverk i en hyperkub, routing.
Grundläggande kommunikationsoperationer, Kapitel 3, sid 65 -
101
Kopior
av utdelat material
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
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
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 en
del utdelat material
Syfte: Att ge kunskap om algoritmutveckling med beaktande av
hög prestanda och portabilitet för olika typer av skalbara parallella
miljöer.
Innehåll: Byggblock för vektor- och matrisberäkningar
(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 fr distribuerat respektive
gemensamt minne. Portabilitetsaspekter ver och mellan olika parallella
plattformar.
Sökningsalgoritmer för diskreta optimeringsproblem 1, Kapitel
8, sid 299 - 315
Kopior
av utdelat material
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.
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)).
Sökningsalgoritmer för diskreta optimeringsproblem 2, Kapitel
8, sid 321 - 324, 328 - 329, 332 - 336
Utdelat material: se föregående föreläsning.
Syfte: 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: 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.
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,
samt ge kunskap om grundläggande sekventiella och parallella algoritmer
för operationer på glesa matriser.
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.
Lösning av glesa system av linjära ekvationer 2, Kapitel
11, sid 426 - 438, 454 - 468
Syfte: Att ge kunskap om parallella iterativa och direkta metoder
för lösning av glesa linjära ekvationssystem.
Innehåll: 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
Syfte: Att med ett sammahå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 paralelldatorsystem .
Innehåll: Problemformulering och introduktion till en
etablerad programvara för grundvattensimulering. Genomgång av
huvudstegen för utveckling av en parallel 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 patritoineringsalgoritmer
och intressanta egenskaper hos domänbaserade prekonditionerare. Prestandarjämförelser
mellan olika partitionberingsalgoritmer. Analyser och prestrandaresultat
för hela tillämpningsproblemet på 512-processorers
Cray T3E. Aktuella testproblem ett 2D- och 3D-problem från en studie
av lämpligheten att slutförvara avfall från kärnkraftverk
i Yucca Mountains i Nevada, USA.