Simultanes Sortieren

Sortieren ist ein Prozeß, bei dem - abhängig vom gewählten Sortieralgorithmus - ggf. durchaus „an mehreren Stellen“ der zu sortierenden Menge gleichzeitig bzw. simultan das Ordnungsniveau der zu sortierenden Menge erhöht werden kann. Am offensichtlichsten ist das beim Quicksort, bei dem die Startmenge in zwei Teilmengen aufgespaltet wird (eine mit den kleineren und eine mit den größeren Elementen), die dann nichts mehr miteinander zu tun haben, es finden demnach keinerlei Vergleiche oder gar Vertauschungen zwischen diesen mehr statt. Deshalb können sie auch gleichzeitig, simultan oder auch (zeit-)parallel auf gleiche Weise sortiert werden, und zwar auf die gleiche Weise wie die Gesamtmenge zuvor, usw. (es handelt sich hierbei um einen sog. selbstähnlichen Prozeß). Wegen des starken, primären Geometriebezuges ist die Bezeichnung „parallel“ für „gleichzeitig“ aus Sicht des Programmautors unglücklich, hat sich allerdings genau wie „Sortieren“ durchgesetzt und wird demnach wenigstens teilweise verwendet.

Sofern diese Gleichzeitigkeit tatsächlich und nicht nur scheinbar (in Form sehr vieler und schneller Umschaltungen zwischen den einzelnen Teilsortierungen) existiert, kann damit auch eine Beschleunigung des Sortierens verbunden sein. Die Geschwindigkeitszunahme ist dabei keinesfalls (indirekt) proportional zum Maß der Parallelität, saloppes Beispiel: Wird immer an zwei Stellen gleichzeitig sortiert, dauert das Sortieren leider länger als die Hälfte der Zeit, die benötigt wird, als wenn immer nur eine Operation zu jedem Zeitpunkt erfolgt. Zum einen zehrt der Koordinations- und Verwaltungsaufwand vieler gleichzeitiger Aufgaben viel der Beschleunigung wieder auf, zum anderen gibt es teilweise Warteverluste beim ungleichzeitigen Beenden von Teilaufgaben, auf deren gemeinsames Ende gewartet wird. Auch im Bereich der menschlichen Wertschöpfung ist es schließlich so, daß etwas, was 10 Mannjahre benötigt (also von einer Arbeitskraft in 10 Jahren geschaffen werden kann), eher nicht von 10 Personen in einem Jahr und schon gar nicht von 100 Personen in einem Zehnteljahr abgearbeitet ist.

Einen Algorithmus, sofern er dafür überhaupt infragekommt, auf eine solche Weise umzugestalten, daß er - mehr oder weniger - gleichzeitig abläuft, heißt, ihn zu parallelisieren, er ist als nötige Voraussetzung dann parallelisierbar (das gilt nicht nur für Sortier-, sondern für alle Algorithmen, so z.B. auch für das Verschmelzen / Merging). Es gibt demnach die Eigenschaft der Parallelisierbarkeit, der „potentiellen Parallelität / Simultaneität“ als notwendige Voraussetzung der Eigenschaft der (tatsächlichen) Parallelität / Simultaneität. Beides sind verschiedene Eigenschaften, die streng voneinander unterschieden werden sollten. Gibt es jedoch keinerlei parallele Anteile an einem Algorithmus (egal, ob ein Algorithmus nicht parallelisiert wurde oder gar nicht erst parallelisierbar ist), dann läuft er hingegen rein sequentiell ab. Als Faustregel läßt sich sagen, daß (nicht nur Sortier-)Algorithmen dann parallelisierbar sind, wenn - zwangsläufig voneinander unabhängige - Dinge in ihnen in inverser oder gar beliebiger Reihenfolge und dann nämlich auch gleichzeitig abgearbeitet werden können. Um das zu verdeutlichen, wurden einige (rekursive) Algorithmen neben dem normalen und dem simultanen auch mit inversem und stackoptimiertem / zufälligem Verlauf implementiert.

Um einen solchen parallelisierbaren Algorithmus auch parallel zu realisieren, also zu parallelisieren, kommt man nicht umhin, sich mit der sog. Threadprogrammierung* zu beschäftigen, wobei es sich hierbei vor allem um Multithread(ing)programmierung handelt, bei der die Anzahl der (Sortier- und/oder Verschmelzungs-)Threads variabel ist. Jede Teilsortieraufgabe wird in einem eigenen Thread abgearbeitet. Diese Threads, die gar nicht gleichzeitig starten (können), sondern versetzt wie bei einem Kanon, arbeiten asynchron, aber auch nicht sequentiell, sondern eben „versetzt gleichzeitig“. Da sie in aller Regel unterschiedlich schnell ablaufen, weil sie verschieden oft und verschieden lang unterbrochen werden, werden sie sogar dann, wenn Sie alle gleichviel zu erledigen haben, im Gegensatz zu einem Kanon kaum in der (bzw. der gleichen) Reihenfolge und schon gar nicht mit den gleichen Zeitabständen fertigwerden, in der / mit denen sie begannen.

Was in der von der Programmierung abstrahierten Theorie noch recht simpel anmutet, weil man es auch im alltäglichen Leben so kennt (A erledigt dieses, B erledigt jenes, evtl. noch mehr Beteiligte, alle starten - mehr oder weniger - gleichzeitig, und wer fertig wird/ist, meldet es dem/den jeweils anderen und/oder seinem Vorgesetzten), hat in der Programmierung seine ganz eigene Tücken, seine Detailteufel. Teuflisch ist auch, daß man immer wieder auf die Denkweise hereinfällt und man sich doch von ihr lösen muß, daß die Dinge in der Reihenfolge stattfinden bzw. beendet werden, in der sie notiert sind bzw. begannen. Diese Gleichzeitigkeit, Asynchronizität und ggf. andere Beendigungs- als Startreihenfolge sind Dinge, die einem nicht immer bewußt sind, für die unser Denken im Verlaufe der Evolution wohl nicht optimiert wurde, auch wenn neuerdings modern ist, seine „Multitaskingfähigkeit“ hervorzuheben. Die Suche der Programm(ier)fehler über das sog. Debuggen ist bei Multithreadingalgorithmen zudem erschwert bis unmöglich, also muß sie stärker als sonst über das Betrachten des Quellcodes und vor allem Hineindenken in den Ablauf erfolgen.

Bei der Parallelisierbarkeit der Sortieralgorithmen gibt es deutliche Unterschiede: von

• ausgezeichnet / hervorragend (Quicksort, Radixsort most significant digit rekursiv, Splitsort) und
• sehr gut (Mergesort),
• theoretisch sehr gut, praktisch werden sie jedoch damit sehr langsam (Selection- und Plaselsort),
• theoretisch sehr gut, praktisch aber indiskutabel (Slowsort) über
• mäßig (Circle-, Comb-, Naturalmerge- und Partitsort, Radixsort most significant digit iterativ, Shear- und Shellsort),
• theoretisch mäßig, praktisch jedoch ungünstig (Insertion-, Oet- und - wenn darin „Mikrothreads“ verwendet werden - Comb-, Pancake-, Partit- und Shakersort) und
• eher gering (Partit- und Shakersort) bis
• gar nicht parallelisierbar.

Gerade die im drittletzten Punkt genannten Sortieralgorithmen benötigen Threads mit nur sehr geringem Arbeitsumfang: Jeweils zwei Elemente vergleichen und optional (wenn sie sich in der i.S. der Sortierung falschen Reihenfolge befinden) vertauschen. Das hat eine stark (quadratisch) mit der Anzahl der zu sortierenden Elemente wachsende Threadanzahl zur Folge, die Windows schnell an seine Leistungsfähigkeit bringen kann: Das Programm bleibt dann einfach ohne die Erzeugung neuer/weiterer Threads stehen (auch wenn die Anzahl gleichzeitiger Threads zu jedem Zeitpunkt recht gering bleibt), auch wird weder ein Fehler von Windows ausgegeben noch läßt sich ein Fehler vom Programm auslesen. Meine Experimente ergaben z.B. auf einem Windows XP, daß nach ca. 337.000 Threads Schluß ist, auch dann, wenn diese Anzahl erst nach wiederholten Multithreadsortierungen erreicht wird, diese Grenze ist nicht zu überschreiten (außer evtl., aber auch nicht sicher durch einen Neustart des Programmes). Auf Windows 7 ist diese Maximalanzahl deutlich höher, aber auch dieses Betriebsprogramm wird letztlich davon über Gebühr beansprucht, der Speicherbedarf wächst ins Uferlose. Sicher ist das eine Qual für Windows, eine „Vergewaltigung“ des Betriebsprogrammes und auch nicht im Sinne des Erfinders, eher ein Mißbrauch der Threadfunktionalität. Zudem ist der Verwaltungsaufwand für das ständige Erzeugen und Beenden der Threads dermaßen hoch, daß die Algorithmen deutlich langsamer als ihre nichtsimultanen Originale ablaufen. Plakativ ausgedrückt: Der Computer hat mehr mit den Threads als mit der eigentlichen Sortierung zu tun. Zurück zur Parallelisierbarkeit: Teilweise hängt sie auch von der konkreten Ausgestaltung des Sortieralgorithmus' ab, sodaß bei manchen Sortieralgorithmen verschiedene Varianten - parallel(isierbar)e und nichtparallel(isierbar)e - möglich sind, analog zur Stabilität.

Einen Sortieralgorithmus zu parallelisieren ist das eine. Dieses simultane Wirken aber auch adäquat zu animieren ist das andere. Windows wehrt sich auf unterschiedliche Weise dagegen: Mal ist die Ausgabe auf dem Bildschirm synchroner, als der Prozeß, die Threadmenge intern abläuft (das ist unschön, weil unrealistisch, aber wenigstens noch simultan), anderenmal ist sie so sequentiell, daß eine Gleichzeitigkeit nicht mehr erkennbar ist (völlig inakzeptabel, da kein Unterschied zur reinen Sequentialität). Der Grund für diese Schwierigkeiten, asynchron, aber nicht parallel und schon gar nicht sequentiell darzustellen, ist, daß die für die Ausgabe nötigen Zugriffe auf den Bildschirm (Linienzeichnenbefehle) meistens gleichzeitig und damit konkurrierend erfolgen, jedoch über eine Synchronisation nur sequentiell auf den Bildschirm erfolgen dürfen bzw. können, denn die Bildschirmausgabe erfolgt nicht per Multithreading, sondern die Graphikbefehle werden nacheinander abgearbeitet. Hinzu kommen konkurrierende (gleichzeitige lesende und/oder schreibende) Zugriffe auf gemeinsame Variablen aus verschiedenen Threads, was i.d.R. durch sogenannte kritische Abschnitte geschützt (also sequentialisiert) werden muß. Je mehr Wirklichkeitstreue man der Ausgabe abzuringen sich bemüht (ggf. auch durch behutsames Weglassen der Synchronisation und/oder Verkleinern/Weglassen der kritischen Abschnitte), desto eher neigt das Programm dazu, „hängenzubleiben“ oder sich mit einer Fehlermeldung „zu verabschieden“. Die verschiedenen Implementationen der Thread-Funktionalität in verschiedenen Delphi-Versionen kommen hinzu. Es ist viel Probieren bei dieser äußerst undankbaren und erfolgsunsicheren, aber auch faszinierenden Programmierung erforderlich, um halbwegs konsistente Ausgaben unter verschiedenen Windows' zu erreichen. Schon mit einer anderen Delphi-Version compiliert oder auf einem anderen Windows laufengelassen, kann das Ergebnis fragil sein, deshalb kann ich für nichts garantieren und bin über jedwede Rückmeldung dankbar. Hier stößt man mithin an eine Grenze dieser Programmierung. Meine Wahl fiel letztlich auf Delphi 7. Bis Delphi 5 laufen das simultane rekursive Bitonicmergesort und einfache simultane rekursive Mergesort, das die größte Anzahl gleichzeitiger Threads erzeugt, auf Windows XP (und kleiner?) völlig synchron, mit Delphi 6 sind auf Windows XP schon zarte Ansätze einer Asynchronizität zu erkennen. Erst ab Delphi 7 sind bei diesen Algorithmen die Ergebnisse zufriedenstellend (fehlerfrei und eben asynchron).

Das parallele Sortieren läuft tendenziell umso schneller ab, je stärker der Computer zur Parallelverarbeitung imstande ist, und das hängt in erster Linie von der Anzahl der Prozessoren bzw. Prozessorkerne ab, sofern das Betriebsprogramm mehrere überhaupt unterstützt, was heutzutage aber selbstverständlich ist. Außerdem wird der Multithreadingalgorithmus nicht mehr beschleunigt, wenn es mehr aktive (!) Threads als Prozessoren oder Prozessorkerne gibt. Auf diese hardwarebedingte Anzahl reagiert das Programm nicht (so können Multithreadingalgorithmen mit mehreren gleichzeitigen Threads auch auf Computern mit nur einem Prozessor ablaufen, was sich allerdings recht zäh gestaltet), jedoch kann die Maximalanzahl gleichzeitiger Threads „manuell“ begrenzt werden. Da die Graphikausgabe letztlich nur in einem Thread abläuft, ist diese der Engpaß (neudeutsch „Flaschenhals“), weshalb die Animationen der Multithreadingalgorithmen keine Chance haben, gegenüber ihren Single-Threads-Pendants signifikant schneller zu sein.

Nicht nur Sortier-, sondern auch viele andere Algorithmen lassen sich parallelisieren, so auch manche Mergingalgorithmen. Implementiert wurden bisher das rekursive simultane (bestens dafür geeignet) und das iterative simultane (sehr gut geeignet) bitonische Verschmelzen, zu finden unter den bitonischen Mergesorts.

Mein letzter bzw. jüngster - und erfolgreicher - Versuch war die Parallelisierung auf zwei Ebenen: Simultanes bitonisches Mergesort (iterativ und rekursiv) mit jeweiligen simultanen (bitonischen) Verschmelzungen; beides wurde und wird im Programm angeboten, jedoch bisher noch nicht miteinander kombiniert.

Inzwischen ist dieses Gebiet mit mittlerweile etlichen implementierten simultanen Sortieralgorithmen mein Steckenpferd geworden, es erforderte mithin den größten Zeitanteil an diesem Program und auch den größten Aufwand bei der Erstellung dieses Internetsauftrittes. Hinzu kommt, daß ich keine einzige Sortieranimation als Programm fand, die das simultane Sortieren einschließt. Nur auf youtube findet man unter Mühen Animationen mit parallelem Sortieren, z.B. hier, dort sind es aber nur Filmchen, bei denen man eben keine Parameter eingeben kann und die auch immer das gleiche zeigen.

*Angelsächsisch Thread (=Faden) ist in diesem Kontext ein einzelner Berechnungs- oder Anweisungsstrang (Befehlsfolge). In einem (jeden) Prozeß im Computerbetriebsprogramm können im Prinzip beliebig viele davon gleichzeitig existieren und auch ablaufen bzw. abgearbeitet werden.