Umeå Universitet
Institutionen för datavetenskap
Elmroth, Kågström |
|
Design och analys av algoritmer
för parallelldatorsystem - vt2000
Obligatoriska teoriuppgifter
21 Januari 2000 |
Obligatoriska teoriuppgifter
Obligatoriska teoriuppgifter skall lämnas in i samband med
gruppövning 1-3. Uppgifterna får lösas individuellt
eller 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 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 Erik Elmroth.
Till varje tillfälle finns dessutom ett antal extra övningsuppgifter
som också kommer att tas upp på gruppövningarna. Som övning
är det därför att rekommendera att du löser även
dessa uppgifter innan respektive gruppövning. Du behöver dock
inte lämna in lösningar till dessa övningar.
Korrekta lösningar inlämnade i tid ger 1 bonuspoäng att
inkludera till tentamenspoängen (maximalt är det alltså
möjligt att få 3 bonuspoäng från teoriuppgifterna).
Bonuspoäng kan delas ut även om ej alla inlämnade uppgifterna
är korrekta, om det framgår att studenten ordentligt har satt
sig in i de teorier som uppgiften avser och att lösningen kan betraktas
som "ett seriöst försök".
Efter samtliga 3 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.
Gruppövning 1 (Inlämnas och presenteras den 31/1 2000)
Obligatoriska uppgifter: 3.19, 4.2, 4.15 samt följande uppgift:
-
Antag att en algoritm har den asymptotiska isoeffektivitetsfunktionen q(p3/2),
där p är antalet processorer. Antag vidare att ett problem
av storlek W löses på p processorer med effektiviteten
E.
Om antalet processorer ökas till q, hur stort skall då
problemet vara för att effektiviteten skall bli E även
för detta processorantal?
Extra övningsuppgifter: 3.11, 4.19, samt följande:
-
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.
-
Beräkna med tre decimalers noggrannhet den effektivitet som erhålls
för p = 4, n = 100, ts = 30 och tw
= 20. Hur stort skall problemet vara, enligt isoeffektivitetsfunktionen,
för att samma effektivitet skall erhållas för p = 8.
Beräkna den effektivitet som erhålls för p = 8 på
denna problemstorlek och förklara eventuella avvikelser från
den effektivitets som erhölls för p = 4.
Gruppövning 2 (Inlämnas och presenteras den 10/2 2000)
Obligatoriska uppgifter: 5.1, 5.5, samt följande uppgift:
-
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 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 som ger
upphov till skillnaderna i isoeffektivitetsfunktionerna för de två
algoritmerna.
Extra övningsuppgifter: 5.9, 5.11 och 5.12.
Gruppövning 3 (Inlämnas och presenteras den 24/2 2000)
Obligatoriska uppgifter: 7.1, 7.2, 7.3 och 7.5.
Extra övningsuppgifter:
-
Låt G = (V,E) vara en sammanhängande oriktad graf med n hörn,
där V är mängden av hörn och E är mängden
av kanter i grafen. Grafen definierar en n x n adjecency-matris
A enligt:
aij = w(vi,vj)
om (vi,vj) tillhör E,
annars aij =
0,
där w(vi,vj) är kostnaden för
kanten (vi,vj). Eftersom grafen är oriktad så
finns det alltid en kant (vi,vj) om det finns en
kant (vi,vj) (som dessutom har samma kostnad). I
kursboken visas Prims sekventiella algoritm för att beräkna ett
minimalt uppspännande träd minimum spanning tre) för
grafen, dvs ett träd som innehåller alla hörn men bara
de kanter som ger lägst totalkostnad. Arbetsmängden W för
algoritmen är q(n2). Inparametern
r
i algoritmen är ett godtyckligt valt starthörn som blir rot i
det uppspännande trädet. I kursboken presenteras en parallell
motsvarighet till algoritmen Prims algoritm. Besvara följande frågor
för den algoritmen. (I analyserna behöver ej konstanter tas med,
dvs det räcker att ge svar i q-termer.)
-
Varför är inte while-loopen lämplig att parallellisera.
-
Beskriv den parallella algoritmen.
-
Givet en hyperkub med p processorer. Beräkna den parallella
tiden Tp, uppsnabbningen S och effektiviteten
E.
-
Avgör om algoritmen är kostnadsoptimal och för vilket förhållande
mellen n och p det i så fall gäller. Beräkna
algoritmens isoeffektivitet med avseende på kommunikation, parallellitet
och totalt (overall).