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.
|
|
