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:
-
presentationsmaterial (OH-bilder, och/eller annat presentationsmaterial),
-
testkörningsresultat som visar att programmet är korrekt,
-
testresultat som visar programmets prestanda,
-
välkommenterad källkod,
-
samt sökväg till exekverbart program.