Umeå Universitet 
Institutionen för datavetenskap 
Elmroth, Kågström
Design och analys av algoritmer 
för parallelldatorsystem - vt2001 
Läsanvisningar
11 Januari 2001

Design och analys av algoritmer 
för parallelldatorsystem, D-nivå, 5p

Mål och syfte

Kursen har som mål att ge fördjupade kunskaper om algoritmutveckling för olika typer av skalbara parallella datorarkitekturer med distribuerat eller gemensamt minne, vilket även kan innefatta heterogena plattformer. Med detta avses bland annat metoder och miljöer för design av parallella algoritmer och implementationer av portabel och effektiv programvara. Viktigt är också att kunna förstå en parallell algoritms uppförande. För detta ändamål studeras dels teoretiska modeller för att analysera och prediktera en algoritms prestanda, dels olika verktyg för att mer noggrannt kunna mäta den verkliga prestandan av en implementation. I detta sammanhang studeras olika prestanda- och skalbarhetsmått. Tillämpningsområden är såväl vektor- och matrisberäkningar som datalogiska tillämpningar.
 

Allmän information

Kursansvarig: Erik Elmroth (email: elmroth, tel: 786 69 86).
Övriga lärare:  Bo Kågström (email: bokg, tel: 786 54 19)
Handledning: ges av Erik Elmroth.
Kursbok: Introduction to Parallel Computing: Design and Analysis of Algorithms av Vipin Kumar, Ananth Grama, Anshul Gupta och George Karypis, Benjamin/Cummings, ISBN 0-8053-3170-0, 1994, samt artiklar som delas ut under kursens gång.
Examination: Skriftlig tentamen och laborationer med skriftlig och muntlig redovisning, obligoriska inlämningsuppgifter.
Övrig information: Information kommer att spridas via email och World Wide Web: http://www.cs.umu.se/~elmroth/TDBD08/01/.
 

Utdelat material

Det mesta av det material som delas ut under kursen finns också samlat här nedan. Om du har problem att läsa postscriptfilerna (t.ex. du får inte upp sidan överhuvud taget, hela sidan visas inte i din postscript-viewer etc), så kan du proval att spara ner filen och sedan skriva ut den istället.

Kursinnehåll

Nedan ges en kortfattad beskrivning av varje föreläsnings syfte och innehåll tillsammans med 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.