Wir stehen vor einem Wandel. Einem tiefgreifenden. Nun nicht jeder wird davon etwas merken, aber wer Software baut wird nicht umhin kommen sich damit zu beschäftigen.
Viele Jahre lang konnte man die Performancesteigerung aktueller Prozessoren mitverfolgen, indem man auf die Taktung schaute. In meinen frühen Computertagen musste ich noch mit 300 MHZ auskommen (seltsamerweise war das für alle Programme genug). In heutigen Zeiten jedoch (vor allem solange Flash noch existiert), ist 2,6 GHZ ein guter Durchschnitt. Doch schon mehrere Jahre nun bewegen wir uns nicht mehr sonderlich weit davon weg. Dennoch werden die Prozessoren immer schneller. Warum? Man baut einfach mehrere davon ein. Die Obergrenze an Taktung ist erreicht, da die Abwärme eines Chips sehr von seiner Taktung abhängt. Wir sind also auf dem Weg ins Multicore Zeitalter - acht und mehr Kerne werden bald keine Seltenheit mehr sein.
Die Sache ist nur: Die meisten Programme, die vor wenigen Jahren entwickelt wurden und noch entwickelt werden, sind überhaupt nicht darauf ausgelegt mehrere Prozessorkerne zu nutzen. Schlicht und einfach aus dem Henne-Ei Problem heraus: Warum für mehr Kerne Software bauen, wenn keiner solche Hardware hat? Warum aber auch teure Hardware kaufen, wenn die Software ohnehin nicht schneller läuft? Erst seit kurzer Zeit erleben wir hier einen Wandel.
Multicore-Programmierung ist nicht unbedingt neu: In großen Rechenzentren wird diese Technik schon lange eingesetzt. Auf dem heimischen Rechner beginnt sich das aber gerade erst zu entwickeln.
Das führt dazu, dass viele Softwareentwickler umdenken müssen. Vieles kann man nicht mehr einfach auf die “alte” Art herunterschreiben und laufenlassen. Viele Komponenten müssen verändert und an die Verarbeitung mit mehreren Threads angepasst werden. Das bringt auch reichlich Komplexität mit sich.
In letzter Zeit habe ich mich auch ein wenig mit Multicore-Programmierung beschäftigt und bin dabei auf einige interessante Effekte gestoßen…
Konkret geht es um den Floyd-Steinberg Algorithmus. Es handelt sich dabei um einen Algorithmus zur Farbtiefenreduktion, der dafür sorgt, dass der Fehler, der bei jedem Pixel gemacht wird auf die umliegenden Pixel leicht übertragen wird.
Der Pseudocode des Algorithmus ist recht simpel (aus der englischen WP):
for each y from top to bottom
for each x from left to right
oldpixel := pixel[x][y]
newpixel := find_closest_palette_color(oldpixel)
pixel[x][y] := newpixel
quant_error := oldpixel - newpixel
pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error
pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error
pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error
pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error
find_closest_palette_color(oldpixel) = oldpixel / 256
Ziel war es nun diesen Algorithmus zu parallelisieren, so dass er auf Multicore-Rechnern schneller läuft. Die Grundidee die ich gewählt habe ist das Bild zeilenweise auf Threads aufzuteilen. Soweit so gut. Es gibt aber strenge Abhängigkeiten zwischen den Pixeln in verschiedenen Zeilen, da der Fehler auch auf Pixel in der darunter liegenden Zeile übertragen wird. Ein Thread muss beim Bearbeiten seiner Zeile also warten, bis das nächste Pixel, das er bearbeiten möchte, vom Thread in der überliegenden Zeile schon seinen kompletten Fehlerübertrag erhalten hat. Das wird gewährleistet, indem ein Thread immer einen Mindestabstand zum Thread in der vorausgehenden Zeile einhalten muss.
Wenn man sich die Abhängigkeit genauer anschaut, dann ergibt sich 3 als Mindestabstand:
Die Abstandsberechnung stützt sich auf ein globales Array, welches den Fortschritt jedes Threads in seiner entsprechenden Zeile enthält. Mit Hilfe dieser Vorgehensweise muss der Zugriff auf die Bilddaten nicht synchronisiert werden, denn es wird niemals dasselbe Pixel gleichzeitig geschrieben und gelesen. Ein wartender Thread wird nur genau dann via notifyAll() benachrichtigt, wenn sein Abstand zum Vorgänger-Thread genau gleich drei ist. In allen anderen Fällen kann er entweder ohnehin nicht weiterarbeiten, da der Abstand zu klein ist, oder der Abstand ist mehr als ausreichend - dann ist er aber bereits informiert worden.
Die Idee kurzerhand umgesetzt ergab ein durchaus gutes Ergebnis:
Es ist aber auch zu sehen, dass mit zu vielen Threads bei zu wenigen Kernen die Geschwindigkeit wieder abnimmt, da der Mehraufwand an Synchronisation den möglichen Performanceschub wieder verschluckt.
Warum das alles so spannend war? Das Cacheverhalten und die Synchronisation der Threads so hinzubekommen, dass sie sich nicht gegenseitig ausbremsen, weil sie nur mit Warten auf den anderen Thread beschäftigt sind war eine ziemlich große Herausforderung.
Falls ihr das alles auch mal ausprobieren wollt: Ich habe dazu auch ein kleines Progrämmchen gebastelt. Das könnt ihr euch hier als jar-File herunterladen. Um das auszuführen müsst ihr das JRE installiert haben. Für die Konvertierung werden hier immer 4 Threads benutzt. Wer 4 Kerne hat ist also klar im Vorteil! Nun denn: Viel Spaß beim Ausprobieren!
Es würde mich nicht wundern, wenn ihr einige Fehler im Programm findet. Ich wollte da jetzt nicht noch mehr Zeit reinstecken. Wäre toll, wenn ihr die Fehler einfach in die Kommentare postet. Vielleicht finde ich ja Zeit mich darum zu kümmern.