Paralleles Programmieren & Algorithmen im Wettbewerb

Während die Taktrate bei Prozessoren gegenwärtig kaum noch Fortschritte macht, verlagert sich die Entwicklung immer mehr in Richtung Mehrkernprozessoren, also Prozessoren, die in der Lage sind, mehrere Befehlsstränge parallel abzuarbeiten. Natürlich kann man sich auch als Hobbyastroprogrammierer überlegen, Programme durch Ausnutzung der Parallelisierung zu beschleunigen. An dieser Stelle möchte ich jedoch auf einen ganz bestimmten Aspekt hinweisen.

Für viele astronomische Berechnungen ist es sinnvoll, mehr als einen Algorithmus zu implementieren, z.B. wenn für verschiedene Anwendungsfälle jeweils andere Algorithmen die größte Effizienz aufweisen.

In vielen Programmen findet man in solchen Fällen eine Auswahlmöglichkeit für den Benutzer, um sich auf einen der vorhandene Algorithmen festzulegen. Dies ist eigentlich jedoch aus mindestens zwei Gründen unpraktikabel:

  • Der Anwender hat möglicherweise kein Gespür für den effizientesten Rechenweg und wählt für sein konkretes Problem vielleicht einen unverhältnismäßig langsamen Algorithmus aus.
  • Die Art des Algorithmus ist oftmals nur ein Implementierungsdetail, mit dem der Benutzer nichts zu tun hat, das den Umgang mit dem Programm verkompliziert und eine unnötige Hemmschwelle darstellt.

Ein besserer Ansatz wäre, die Algorithmen in einer Wettbewerbssituation gegeneinander antreten zu lassen. Hier kommt nun die Parallelisierung ins Spiel. Für jeden Algorithmus werden eigene Threads (separate Befehlsstränge) erzeugt, die auf dem PC parallel ablaufen. Damit ist sichergestellt, daß der effizienteste Algorithmus zur Ausführung kommt.

Man kann dies sogar noch optimieren, indem man den Erfolg eines jeden Threads mißt und die den Algorithmen zugeteilte Rechenzeit entsprechend gewichtet: der effizienteste Thread bekommt die meiste Rechenzeit.

Dieses Verfahren (man könnte es Race Condition nennen, wäre dieser Begriff nicht schon anderweitig belegt) ist sicherlich geringfügig langsamer als wenn der leistungsfähigste Algorithmus exklusiv zur Ausführung käme, jedoch kommt es ohne jegliche Vorabannahmen aus und vermeidet sehr ungünstige Rechenwege gänzlich.

Auf einem Einzelkernprozessor funktioniert dieses Verfahren ebenso.