Skip to content.

TUD TU Dresden

Queens@TUD

DE EN 

TU Dresden » Faculty of Computer Science » Institute for Computer Engineering » Chair for VLSI – EDA » Queens
Queens@TUD-Logo

Ergebnisse

Ansatz

Die Berechnung des 26-Damenproblems wurde durch die Vorbelegung der ersten sechs Spalten aufgeteilt. Unter Berücksichtigung der Symmetrie and der Mittelhorizontalen konnte die Vorbelegung der ersten Spalte auf die untere Hälfte beschränkt werden. Die ermittelte Lösungszahl wurde verdoppelt, so dass sie sowohl die berechneten Teillösungen als auch deren ausgelassenen Bilder umfassen. Die sich so ergebenden 25.204.802 Teilaufgaben wurden unabhängig voneinander auf unseren Lösern berechnet.

Ergebnisse

Gesamtlösungszahl

22.317.699.616.364.044 Lösungen.
Siehe auch die eindeutigen und selbstsymmetrischen Lösungszahlen.

Teillösungen

Lösungszahlen der Teilprobleme

Die Teillösungszahlen zu allen 25.204.802 Vorplatzierungen stehen zum Herunterladen bereit.
Beachten Sie jedoch die Dateigröße: 169.6 MByte (komprimiert), 639.7 MByte (unkomprimiert).

Eine erste Übersicht gibt die Tabelle mit den Teilproblemen unter Vorbelegung der ersten beiden Spalten.

Verlauf

Zeitlicher Projektfortschritt

Der zeitliche Rechenfortschritt des Projektes ist in nebenstehender Grafik dargestellt. Deutlich zu erkennen sind sowohl der periodische Verlauf des Projektfortschrittes als auch die Beschleunigung der Berechnung durch unsere iterativen Entwurfsverbesserungen und die Beteiligung unseres Sponsors Signalion. Es offenbart auch einen vorübergehenden Ausfall unserer Haupt-FPGAs Mitte Mai.

Die 13 deutlich konvexen Perioden des Fortschrittverlaufes korrellieren mit den Platzierungen der Dame in der ersten Spalte, die im wesentlichen nacheinander abgearbeitet wurden. Es ist festzustellen, dass die Lösungssuche für ein Teilproblem tendenziell umso aufwändiger ist, je näher sich die Damen der Vorplatzierung an der Brettmitte befinden. Bemerkenswerterweise steigen mit der Suchkomplexität auch die für die Teilprobleme ermittelten Lösungszahlen.

Rechenleistung und Energieverbrauch

Rechenleistung im Vergleich

Diese Graphik illustriert die Rechenleistung der von uns genutzten FPGA-Baustein insbesondere auch im Vergleich zu einigen High-End-Universal-Prozessoren.

Man beachte außerdem, dass wir acht der Virtex-4 LX160-Bausteine mit einem einzigen 400 Watt-PC-Netzteil betrieben haben. Die gemessene Steckdosenleistung dieses Systems betrug 110 W. Für die gelieferte Rechenleistung wären 8*22 2.5 GHz-QuadCore-Systeme notwendig, die jeweils 180 W Steckdosenlast verursachen. Die für die Lösung eines Teilproblems aufgewendete Energie ist beim QuadCore-System also um das 288-fache größer als bei dem FPGA-System. Bei Prozessoren mit weniger Kernen wird dieses Verhältnis noch größer, da sich die Last der Systemperipherie auf weniger parallele Rechnungen verteilt.

Sponsors
Signalion
Contact

Prof. Rainer G. Spallek
rainer.spallek@tu-dresden.de

Thomas B. Preußer
thomas.preusser@tu-dresden.de

Bernd Nägel
bernd.naegel@mailbox.tu-dresden.de

Telefax
+49 (0)351 463 38324
Street Address
Nöthnitzer Straße 46, Room 1095
01187 Dresden
Mail Address
Chair for VLSI – EDA
Fakultät Informatik
Technische Universität Dresden
D-01062 Dresden