Design and analysis of algorithms for parallel computer systems, VT08

Assignment 1: Obligatoriska teoriuppgifter

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 tisdag 15/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 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 tillsammans 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 för ringen (i uppgift 1 ovan) och hyperkuben som ger upphov till skillnaderna i isoeffektivitetsfunktionerna för de två algoritmerna.