|
Laboration 1 består av ett antal obligatoriska
teoriuppgifter som görs tillgängliga på denna sida under kursens gång.
Uppgifterna ska redovisas muntligt vid två tillfällen
då även skriftliga lösningar ska lämnas in.
Uppgifterna skall (om möjligt) lösas två-och-två. Huvudsyftet med
uppgifterna är att ge kontinuitet i teoristudierna, att på ett tidigt
stadium identifiera svårigheter, samt naturligtvis att ge ökad teoretisk
kunskap om algoritmer för parallella datorer. Uppgifterna skall redovisas
skriftligt och muntligt. Genomgång av lösningar görs på
föreläsningstid (se schemat) då studenterna förutsätts presentera sina
lösningar. Du ska alltså vara beredd att presentera dina lösningar på
dessa timmar. Om du vid något tillfälle ej kan deltaga vid
dessa redovisningar bör du ta kontakt med handledaren.
Efter samtliga inlämningstillfällen kommer en helhetsbedömning att göras
av varje students samtliga uppgifter, och eventuella
kompletteringsuppgifter kommer att delas ut för uppgifter som ej har lösts.
Det viktiga är dock inte att man lämnat in fullständigt korrekta lösningar
utan att det syns att man gjort ett allvarligt försök att lösa uppgifterna.
Del 2 (Inlämnas och presenteras - tisdag 26/5 kl 09.15)
Obligatoriska uppgifter: 10.2, 10.3, 11.4, 12.1,
samt följande uppgift:
- En parallell
algoritm har
W = n2 och
Tp
= n2/p + 2 p1/2 ts + n tw.
Beräkna dess uppsnabbning, S, effektivitet, E, samt dess
asymptotiska isoeffektivitetsfunktion (med avseende på kommunikation).
Avgör om algoritmen är kostnadsoptimal för de två fallen p = n2
och p = n.
OBS! En liten "hint" ang. Breath-first
ranking som avses i uppgift 10.3: den innebär inte att varje
"lager" av noder kring startnoden (de noder som ligger på avstånd
l) får samma värde.
|
