Aufgrund von Wikipedia: Endgame-Tabellenbasis ist die Lomonosov-Endgame-Tabellenbasis immer noch die größte Tabellenbasis (mit einer Größe von 140 TB). Jetzt wurde diese Tabellenbasis im Jahr 2012 mit dem Lomonosov 1 berechnet ( Top500-Liste November 2012, Rang 26 ). Der Lomonosov 1 hatte 78.660 Kerne mit ~ 900 TFlop / s (Peak: 1.700 TFlop / s). Wenn ich mir die neueste Top500-Liste (Juni 2016) ansehe, sehe ich, dass der Lomonosov 2 mit ~ 2.100 TFlop / s (Spitzenwert: ~ 2.900 TFlop / s) auf Platz 41 der Welt steht. Computer hat 93.000 TFlop / s.
Ich frage mich also, warum die Lomonosov-Tischbasis nach 4 Jahren immer noch die größte Tischbasis ist. Sollte es mit der wachsenden Computerleistung nicht einfach sein, eine 8-Mann-Tischbasis zu berechnen? Oder ist der Schritt von 7 auf 8 einfach zu groß? Vielleicht würde die Größe exponentiell ansteigen, so dass Standardspeichersysteme damit einfach nicht umgehen können?
Würde mich über alle Informationen zu diesem Thema freuen. Danke im Voraus!
quelle
Antworten:
Ich bin ein Entwickler, der derzeit an Software zur Berechnung von Endgame-Tabellenbasen arbeitet. Der eigentliche Engpass bei der Berechnung von Positionen ist nicht der Speicher an sich, sondern der Arbeitsspeicher und die Rechenzyklen, die zur Berechnung eines Netzwerks für einen exponentiell wachsenden Satz von Positionen erforderlich sind.
Die Anzahl der Positionen wächst exponentiell entsprechend der Anzahl der Männer im Vorstand. Dies bedeutet , dass der Arbeitsspeicher benötigt werden (ob es RAM oder Festplatte liest, sein , das ist weniger teuer und besser skalierbar , aber signifikant langsamer) nimmt proportional zu ,
A^N
woA
ein Skalierungskonstante (etwas weniger als 64) undN
ist die Anzahl der Männer in dem Tischbasis. Der Lomonosov-Supercomputer verwendete 92 TiB RAM , was für eine 7-Mann-Tischbasis ausreicht. Wie Dfan in seinem Kommentar sagte, ist der Sprung zu groß.Wenn mehr Knoten zur Tabellenbasis hinzugefügt werden, steigt die Anzahl der Berechnungen schneller als linear zur Anzahl der Knoten. Zum Beispiel in einem Datenzugriff binären Suchbaum (BST) ist proportional zu ,
ln(M)
woM
die Anzahl der Knoten im Baum; DaM = A^N
für den einmaligen Zugriff auf jeden Knoten des BaumsA^N * ln(A^N)
Operationen erforderlich sind. Es gibt mehrere Schritte im retrograden Bewertungsalgorithmus der Tabellenbasis , die ähnlich skaliert werden.Kurz gesagt, der Speicher nimmt exponentiell zu und die Anzahl der Operationen steigt schneller als exponentiell, wenn mehr Männer hinzugefügt werden. Das Rechnen ist in (zum Zeitpunkt des Schreibens) 6 Jahren noch nicht so weit fortgeschritten.
quelle
Ich kann keinen Kommentar abgeben, da ich keinen "50-Ruf" habe, aber ich habe mich gefragt, ob man die 7-Tabellenbasis als Teil der Antwort für eine 8-Tabellenbasis verwenden könnte. Haben sie das für die 7 Tischbasis gemacht?
Das heißt, wenn Sie die Lösung für 8 Teile bestimmen, hören Sie auf, wenn Sie 7 Teile haben, und beziehen Sie sich einfach auf die 7 Tabellenbasis. Zugegeben, selbst damit wäre es riesig, weil es immer noch viele Kombinationen geben würde, bevor man zu 7 Teilen kommt, aber weniger als wenn man es herausfinden würde, ohne auf die 7 Tabellenbasis zu verweisen?
Wenn die Lösung eine Methode verwendet, um in die andere Richtung zu gehen, hilft es vielleicht nicht?
quelle