Umeå Universitet  Institutionen för datavetenskap  Elmroth, Kågström

Design och analys av algoritmer  för parallelldatorsystem - vt2001 Obligatoriska teoriuppgifter 2 Februari 2001

Laboration 3 utgörs av tre uppsättningar obligatoriska teoriuppgifter som 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.

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 29/1)

• Antag att en algoritm har den asymptotiska isoeffektivitetsfunktionen q(p^3/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 = n² och
              T_p = n²/p + 2 p^1/2 t_s + n t_w.
1. 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 = n² och p = n.
2. Beräkna med tre decimalers noggrannhet den effektivitet som erhålls för p = 4, n = 100, t_s = 30 och t_w = 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 8/2)

• 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 P_i håller radblock i och att B är partionerad kolumnvis med block-striped partitioning så att processor P_i håller kolumnblock i.
1. 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.
2. Antag att en addition och en multiplikation tar en tidsenhet. Beräkna arbetet W (= T₁), tiden på p processorer T_p, uppsnabbningen S och effektiviteten E. Antag att t_s är uppstartningstiden och t_w är tiden per element (tal i matriserna) vid meddelandeöverföring.
3. 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.
4. 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

        T_p = n³/p + 2 p^1/2 t_s + 2 t_w n² /p^1/2
och algoritmens asymptotiska isoeffektivitetsfunktion q(p^3/2). Försök förklara vilka skillnader i algoritmerna som ger upphov till skillnaderna i isoeffektivitetsfunktionerna för de två algoritmerna.

Gruppövning 3 (Inlämnas och presenteras den 22/2)

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:

        a_ij = w(v_i,v_j) om (v_i,v_j) tillhör E,
        annars a_ij = 0,
där w(v_i,v_j) är kostnaden för kanten (v_i,v_j). Eftersom grafen är oriktad så finns det alltid en kant (v_i,v_j) om det finns en kant (v_i,v_j) (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(n²). 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.)
1. Varför är inte while-loopen lämplig att parallellisera.
2. Beskriv den parallella algoritmen.
3. Givet en hyperkub med p processorer. Beräkna den parallella tiden T_p, uppsnabbningen S och effektiviteten E.
4. 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).