Laboration 4
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, t.ex. relaterat till någon
intressant grid-programvara.
Skicka ett mail till handledaren
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.
Redovisning
Laborationen skall redovisas vid det
redovisningstillfälle som anges på schemat (mer information ges senare)
eller vid ett annat tillfälle för de som har giltig frånvaro från det
ordinarie tillfället. 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, relevant 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.
|