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å
gruppövningstimmarna (se schemat) då studenterna förutsätts presentera sina
lösningar. Du ska alltså vara beredd att presentera dina lösningar på
gruppövningstimmarna. 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 1 (Inlämnas och presenteras torsdag 19/4)
Obligatoriska uppgifter: 4.6, 5.10, 5.13, 8.5 samt
följande uppgifter:
- Beskriv en
algoritm för att hitta maximum bland n tal på en sqrt(n) x
sqrt(n) mesh. Är algoritmen kostnadsoptimal?
- Matrismultiplikationen
C = C + A * B, där A, B och C är n x n-matriser
kan göras parallellt på en ring av p processorer avbildad på en
p-processorers hyperkub. Antag att matriserna A och C
i utgångsläget är partitionerade radvis med block-striped
partitioning så att processor Pi håller radblock
i och att B är partionerad kolumnvis med block-striped
partitioning så att processor Pi håller
kolumnblock i.
- Konstruera en
parallell algoritm för att utföra matrismultiplikationen på
hyperkuben betraktad som en ring av processorer. Rita gärna figurer
som visar att du förstått matrispartitioneringen.
- Antag att en
addition och en multiplikation tillsammans tar en tidsenhet. Beräkna
arbetet W (= T1), tiden på p processorer Tp,
uppsnabbningen S och effektiviteten E. Antag att ts
är uppstartningstiden och tw är tiden per element
(tal i matriserna) vid meddelandeöverföring.
- Avgör om
algoritmen är kostnadsoptimal (och bestäm i så fall för vilket
förhållande mellan n och p det gäller) och beräkna dess
asymptotiska isoeffektivitetsfunktion med avseende på kommunikation
och parallellitet samt dess totala (overall)
isoeffektivitetsfunktion.
- I kursboken
beskrivs Cannons algoritm för att utföra matrismultiplikationen på
ett 2-dimensionellt nät av processorer. Med det 2-dimensionella nätet
avbildat på en hyperkub med p processorer blir
Tp = n3/p
+ 2 p1/2 ts + 2 tw n2 /p1/2
och algoritmens asymptotiska isoeffektivitetsfunktion q(p3/2). Försök förklara vilka
skillnader i algoritmerna för ringen (i uppgift 1 ovan) och hyperkuben som
ger upphov till skillnaderna i isoeffektivitetsfunktionerna för de två
algoritmerna.
http://www.cs.umu.se/kurser/TDBD08/VT07/lab1.1.html
Ansvarig för sidan: Lars
Karlsson
Senast ändrad 2006-03-14
Copyright © 2006. All rights reserved.
|
|