Dynamic Tree Splitting
Beim parallel denkenden Schachprogramm wird der Rechenprozess zunächst auf einem Prozessor gestartet. Dieser erzeugt bei seinen Berechnungen einen Variantenbaum mit Listen der möglichen Züge an den verschiedenen Abzweigungen. Die Zuglisten schreibt er in den gemeinsamen Speicher an eine Art Tafel - im Programmierer-Jargon Hash-Tabellen genannt. Nun kommen die übrigen Prozessoren, schauen nach, was Prozessor 1 gerechnet hat und rechnen an anderen Stellen weiter. Auch sie schreiben ihre Ergebnisse für die Prozessorkollegen in den Speicher. Genutzt werden kann die Technik jedoch nur auf einem Rechner, in dem die Prozessoren gemeinsamen Zugriff auf den Arbeitspeicher haben. In einem Cluster aus mehreren separaten Computern wäre sie wirkungslos.
Während die meisten Schachprogramme sich an dieser Stelle mit dem erreichten Geschwindigkeitszuwachs durch gemeinsamen Zugriff auf die Hash-Tabellen zufrieden geben, geht Deep Fritz einen Schritt weiter. Prozessor 1 nimmt nämlich auch noch eine Aufgabenverteilung vor und weist den übrigen Rechnerkernen vor, welche Bereiche sie im Suchbaum bearbeiten sollen. Dieses Verfahren des Dynamic Tree Splitting ist sehr viel effizienter und sorgt für weiteren Geschwindigkeitszuwachs.
In Bonn spielt Deep Fritz auf einem Rechner mit zwei Intel Core 2 Duo. Jeder dieser Prozessoren besitzt zwei Prozessorkerne im gleichen Chip, die einen eigenen First Level Cache nutzen und sich den Second Level Cache teilen. Die Kommunikation zwischen den beiden Einheiten ist sogar schneller als bei zwei normalen parallelen Prozessoren. Gegenüber der Singleversion kommt Deep Fritz damit auf einen Zuwachs, der sehr deutlich über Faktor drei liegt.
Schmetterlings-Effekt im Computer
Dabei sorgt die Rechnerarchitektur mitunter für seltsame Effekte. Während im Singlebetrieb mit einem Prozessor die Zugvorschläge von Schachprogrammen sehr gut reproduzierbar sind - ein Programm rechnet unter gleichen Hardwarebedingungen bei gleicher Bedenkzeit immer wieder das gleiche Ergebnis aus -, ist dies im Parallelbetrieb nicht der Fall.
Ein wesentlicher Faktor dabei ist beispielsweise die Zeit, die der Bediener braucht, um den Zug von Kramnik einzugeben. Das Programm rechnet auch in der Zeit, in der es nicht am Zug ist im sogenannten Permanent Brain. Gibt der Bediener seinen Zug eine Millisekunde früher oder später ein, verändern sich die in der Hashtabelle abgelegten bisherigen Rechnergebnisse.
Minimale Abweichungen in der Berechnungsfolge der einzelnen Teilprozessoren können am Ende zu einer Art Schmetterlings-Effekt und der Ausführung eines ganz andern Zuges am Brett führen. Selbst wenn Kramnik also einen Vierprozessor-Rechner dieses Typs zur Vorbereitung verwenden würde, könnte er immer noch nicht sicher sein, dass in einer bestimmten Position immer der gleiche Zug ausgespielt wird.
Auch die Größe der Hash-Tabellen spielt eine Rolle für eine mögliche Reproduzierbarkeit der Züge. Deshalb wird sie vom Deep-Fritz-Hersteller ChessBase geheim gehalten.
Obwohl das eigentliche Schachspiel zu Ergebnissen führt, die für den Fortgang der menschlichen Geschichte von ziemlicher Nutzlosigkeit sind, führt das Nachdenken über eine effiziente maschinelle Bearbeitung der damit verbundenen Probleme, wie hier beim Symmetrical Multi Processing, zu nützlichen Techniken, die dann anderswo mit Gewinn einsetzbar sind. An komplexen Rechenaufgaben, die mit Multi-Core-Prozessoren deutlich schneller bewältigt werden können, herrscht kein Mangel - siehe Berechnung des Klimawandels.
Der Artikel ist zuerst bei "Spiegel Online" erscheinen. (wl)