Umeå Universitet
Institutionen för datavetenskap
Elmroth, Kågström
Design och analys av algoritmer 
för parallelldatorsystem - vt2001
Laboration 2
19 Februari 2001

Laboration 2

Redovisas Onsdagen den 21/3 2001

Laborationen, är avsedd att lösas parvis (men individuellt eller i grupper om tre går också bra), består av två delar där den första är att på bästa möjliga sätt göra en implementation av en vald algoritm. Den andra delen består i att utvärdera algoritmen, både teoretiskt och genom praktiska testkörningar. Laborationen är avsedd att ge stort utrymme för egna idéer både vad gäller implementation och analys. Vid bedömningen av din laboration kommer vikt att fästas vid hur du valt att konstruera din algoritm för att nå bra prestanda och portabilitet. För att göra en bra utvärdering kan det vara nödvändigt att t.ex. prova flera olika datadistributioner, olika kommunikationsmönster etc.
 

Val av algoritm

Du får i samråd med lärare/handledare välja att implementera en av följande algoritmer.
1.
Kolumnorienterad block-algoritm för LU-faktorisering med pivotering på logiskt 2-dimensionellt nät av processorer (kan nog vara lite besvärligt, så extra information kommer att ges för de som väljer denna uppgift).
2.
Kortaste vägen mellan alla par av hörn i en graf med den "matrismultiplikationsbaserade algoritmen" (genom att vidareutveckla programmet från laboration 1) och med Floyds algoritm.
3.
Djupet-först-sökning med enkel "back-tracking" i ett godtyckligt träd med lastbalansering m.h.a. asynkron round-robin.
4.
Djupet-först-sökning med algoritmen "Iterativ fördjupning A*" i ett godtyckligt träd med lastbalansering m.h.a. asynkron round-robin.
5.
Bäst-först-sökning i ett godtyckligt träd med "random"-kommunikationsstrategi för fördelning av noder på "öppen-listan".
6.
FFT med binary-exchange-algoritmen.
7.
FFT med transponeringsalgoritmen.
8.
Konjugerade gradientmetoden (utan prekonditionering) för lösning av symmetriska positivt definita linjära ekvationssystem. (För att inte krångla till det räcker det att göra detta för täta matriser, dvs lagring av matriser i 2-dimensionella fält)
Du är också välkommen att föreslå någon annan algoritm som du är intresserad av att implementera.

Skicka ett mail till Erik Elmroth och meddela ditt val!
 

Utvärdering

Algoritmerna skall utvärderas teoretiskt och praktiskt, där den praktiska delen görs utifrån testkörningar på lämpliga problem och processorantal. Huvudmålen med den praktiska och teoretiska analysen är att förstå algoritmens uppförande, samt att göra en rättvis utvärdering av implementationen, där såväl svaga som starka sidor kommer fram. Du skall även kunna motivera varför du gjort implementationen på det sätt som du gjort genom att redovisa eventuella alternativ du har tagit ställning till samt varför du valt att göra så som du gjort.

Det ingår i uppgiften att avgöra och motivera vilka hjälpmedel och prestandamått som är lämpligast att använda för att göra denna utvärdering. Om du implementerar en rutin som även finns i t.ex. ESSL är naturligtvis prestandajämförelser med ESSL-implementationen intressanta.
 

Redovisning

Laborationen skall redovisas vid en halvdags mini-konferens där alla personer/grupper kommer att tilldelas ett antal minuter för att presentera sitt arbete och sina resultat. Vid bedömning av laborationen kommer stor vikt att fästas vid den information du ger under seminariet så du bör därför förbereda din presentation väl och försäkra dig om att du hinner presentera ditt material på den tid du tilldelas (antalet minuter per person/grupp kommer att meddelas då det är klart hur många grupper det blir). Det betyder att det är viktigt att tänka igenom vad som skall presenteras (vad är viktigt, releant etc) och hur man skall göra det på ett sätt som åhörarna kan tillgodogöra sig.

Förutom den muntliga redovisningen skall ni lämna in en liten lab-rapport bestående av: