Verktyg för ‘Sorting Networks’ (Swe)

Jag håller på att skriver ett verktyg för att analysera sk. Sorting Networks. Det är från början ett skolprojekt på kursen Programmering av Parallelldatorer men jag har kommit ifrån parallellprogrammeringen och inriktat mig mera på analysen av algoritmen.

Tanken är att man definierar sin egen algoritm som skall göras i sorteringsnätverket och använder programmet för att evaluera det. Just nu så får man en .dat-fil som man kan plotta i Gnuplot för att få en grafisk representation av algoritmen. I skrivande stund så har jag en halvfärdig implementation av Bubble sort och kan därför visa hur en grafisk representation kan se ut:

Sorting networks

Tyvärr kan jag inte lägga ut källkoden än. Dels eftersom det inte är klart och dels för att jag måste få det rättat av läraren innan någon annan får se det :).

Uppdatering

Nu har jag fått min Bubble-sort algoritm att generera bra sorteringsnätverk. Det fungerar även att sortera tal inom nätverket. Det jag skall lägga till nu är stöd för att hantera interna sorteringsnätverk.  Som det är nu kan man endast sortera  samma mängd tal som antalet processer, detta kommer nu förhoppningsvis att lösas.
Sorting Networks2Här är en bild på ett sorteringsnätverk av grad 80. (Algoritmen som används är Bubblesort)

Uppdatering (2009-06-04)
Jag har börjat testa min färdiga implementation och upptäckt att kommunikationen tyvärr är ett större problem än vad jag tidigare trott.
Här är några utskrifter från testprogrammet:

[niax0493@ra5 sorting_networks]$ time mpirun -np 8 sorting_networks 4096
We are using Bubblesort version 0.1, written by Niclas Axelsson
With depth=8189 and comparators=8386560

real    0m4.136s
user    0m0.022s
sys     0m0.027s
[niax0493@ra5 sorting_networks]$ time mpirun -np 1 sorting_networks 4096
We are using Bubblesort version 0.1, written by Niclas Axelsson
With depth=8189 and comparators=8386560

real    0m1.384s
user    0m0.019s
sys     0m0.018s

I båda utskrifterna använder jag mig av ett sorteringsnätverk av storlek 4096. Som ni ser så ökar tiden för en sortering med ca. 3gånger med 8 processorer istället för endast 1. Kommer lägga ut källkoden till programmet ifall det är någon som skulle vilja kolla lite på det.