Kurs-Projekt: Paralleles Sortieren einer intransitiv total geordneten Menge

Projektvorschlag: Sortieren einer transitiv total geordneten Menge ist eines der best erforschten Themen in der Informatik. Eine Verallgemeinerung davon ist das Sortieren einer intransitiv total geordneten Menge, was daher eine höhere Komplexität hat. Während für eine transitiv total geordnete Menge immer gilt a >= b und b >= c impliziert a >= c, muss das für eine intransitiv total geordnete Menge nicht immer stimmen. Nur a > b xor b > a ist gefordert. Nichtdestotrotz kann man beweisen, dass es immer eine Reihenfolge gibt, die a1 >= a2 >= a3 >= ... >= an erfüllt. Ein gutes Beispiel für eine solche Menge ist ein Turnier. Jeder Teilnehmer gewinnt entweder oder verliert gegen jeden anderen Teilnehmer. Aber sogar wenn man weiß, dass Spieler A Spieler B besiegt und Spieler B auch Spieler C besiegt, kann man damit nichts mit Sicherheit über den Ausgang des Spiels zwischen Spieler A und Spieler C aussagen.

Eines der Paper, die unten aufgeführt sind, schlägt einen Algorithmus vor, solch eine Menge auf einer EREW PRAM parallel zu sortieren. Ich habe diesen Algorithmus für ein Shared-Memory-System mittels pthread implementiert und ihn sowohl mit dem besten bekannten sequentiellen Algorithmus verglichen, als auch mit herkömmlichen Sortier-Algorithmen.

Ausgangs-Paper: Jie Wu: On Sorting an Intransitive Total Ordered Set Using Semi-Heap
Jie Wu, Stephen Olariu: On Cost-Optimal Merge of two Intransitive Sorted Sequences

Präsentation (PowerPoint-Datei, englisch) inkl. Fragebogen und Demo-Programm (für Windows, .NET Runtime erforderlich)
Abschlussbericht (PDF, englisch) und C-Source-Code der Implementierung.