Design och analys av algoritmer för parallelldatorsystem, VT07

Kursinnehåll

Nedan ges en kortfattad beskrivning av olika kursavsnitts syfte och innehåll tillsammans med läsanvisningar och eventuellt elektroniskt tillgängligt material. Se även utdelat material. (Sidan uppdateras med ytterligare information och material under kursens gång.)

Kursintroduktion och modeller för parallella beräkningar, Kapitel 1,2, appendix A  
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 (kap. 1-2) 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 4, sid 147-184
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 5, sid 195 - 231
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 I, Sek. 3.4.1, sid 117 - 129, Sek. 4.5, sid 171, Kapitel 8, sid 337 - 351
Kopior av föreläsningsmaterial delas ut i samband med lektionen.
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.

Principer för design av parallella algoritmer, kapitel 3, sid 85 - 146
Syfte: Att ge kunskap om olika principer för design av effektiva och robusta parallella algoritmer för lösning av olika typer av beräkningsproblem.
Innehåll: Uppdelning av ett problem i oberoende uppgifter (tasks) som kan lösas parallellt. Olika sätt till uppdelning sk. dekompositionsprinciper: rekursiv, data, undersökande, spekulativ, hybridvarianter. Statisk respektive dynamisk uppdelning i uppgifter. Interaktion mellan uppgifter. Mappning av uppgifter för lastbalansering: datapartitionering, uppgiftspartitionering, hierarkiska mappningar. Modeller för parallella algoritmer: dataparallell, uppgiftsgraf, arbetspool, master-slave, pipeline.

Algoritmer för täta matriser II, Kapitel 8, sid 352 - 377
Kopior av föreläsningsmaterial delas ut i samband med lektionen.
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.  

Portabel och effektiv programvara för MIMD-arkitekturer I + II, Artiklar och utdelat material
Kopior av föreläsningsmaterial delas ut i samband med lektionen. SIAM Review artikel för Del II - rekursivt blockade algoritmer och hybrida datastrukturer. (Del II, Old material, men ändå av intresse! ).
Syfte: Att ge kunskap om algoritmutveckling med beaktande av hög prestanda och portabilitet för olika typer av skalbara parallella miljöer med hierarkiska minnestrukturer.
Innehåll: Byggblock och programbibliotek för vektor- och matrisberäkningar.
Del I - Bibliotek för högpresterande beräkningar: Level-1-2-3 BLAS, LAPACK, BLACS, PBLAS, ScaLAPACK. Parallella blockalgoritmer för distribuerat resp. gemensamt minne. Portabilitetsaspekter över och mellan olika parallella plattformer.
Del II - Design av portabel och högpresterande Level 3 BLAS: Minneshierarkier - koncept och karakteristika. GEMM-based Level 3 BLAS - koncept och designprinciper, benchmark, utvidgad optimering för superskalära processorer. Hantering av komplexa djupa minneshierarkier via hierarkisk blockning. Rekursivt blockade algoritmer och dataformat. Trådparallellisering av rekursiva träd.

Design & benchmarking av ett TOP100 Super Cluster System, Artikel
Syfte: Att ge kunskap om design, konstruktion och benchmarking av ett modernt superklustersystem med prestanda motsvarande en plats på TOP100-listan.

Parallella grafalgoritmer, Kapitel 10, sid 429 - 462
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.

Parallella sökalgoritmer för diskreta optimeringsproblem, Kapitel 11, sid 469 - 488, 490 - 492, 495 - 500
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.

Lösning av glesa system av linjära ekvationer på parallelldatorsystem, Kapitel 11 (1st edition), sid 407 - 454
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.

Parallella algoritmer för FFT, Kapitel 13, sid 537 - 548, 553 - 556
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.