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

Queens@TUD

Mit FPGAs zum Weltrekord!

Q(26)=22.317.699.616.364.044

Queens@TUD ist ein massiv paralleler, FPGA-basierter Ansatz zur Suche und Zählung aller Lösungen zu einem gegebenen N-Damenproblem.
Zu Beginn des Projektes (2008) waren die Lösungszahlen für alle N bis 25 bekannt. Dieses Projekt war das erste, das am 11. Juli 2009 die Lösungszahl für N=26 zu Q(26)=22317699616364044 bestimmt hat. (mehr)

Wir evaluieren zur Zeit die Fortsetzung des Projektes zur Berechnung von Q(27). Ein zeitnaher Abschluss dieses Problems wird definitiv sowohl weitere methodische und algorithmische Verbesserungen als auch verstärktes FPGA-Sponsoring erforden. Für nützliche Hinweise und interessierte Kooperationspartner wären wir sehr dankbar.

Sponsoren

Signalion

Neuigkeiten

30. August 2009
Das russische MC#-Projekt hat seine Rechnung zum 26-Damenproblem mit zwei Superrechnern aus der Top500-Liste (Juni 2009) beendet und unser Ergebnis bestätigt.
11. Juli 2009
Die letzte Teillösung wurde um 16:28 Uhr in die Lösungsdatenbank eingetragen. Damit ist die Berechnung für das N-Damenproblem mit N=26 beendet, die am 14. Oktober 2008 um 10:10 Uhr begann. Die Gesamtlösungszahl wurde zu Q(26)=22317699616364044 ermittelt.
12. März 2009
Mit Signalion konnte ein erster großer Sponsor gefunden werden. Damit stehen uns zusätzlich, sehr effiziente FPGAs zur Verfügung. Wir arbeiten derzeit daran, diese in unser System einzubinden.
27. November 2008
Änderung des Berechnungsdesigns in den FPGA-Einheiten. Das neue Design benötigt nun einige zusätzliche Takte, um die Berechnung eines Teilproblems zu lösen, ist jedoch zudem wesentlich kompakter als das alte Design. Dadurch kann die Anzahl der parallel arbeitenden Einheiten auf dem FPGA vervierfacht werden. Zudem sind einige positive Seiteneffekte hinzugekommen. Durch die neuen und kompakten Strukturen, können die Einheiten auf dem FPGA effizienter platziert werden, was dazu führt, dass die Taktfrequenz durch kürzere kritische Wege des Entwurfes erhöht werden kann.
7. November 2008
Entdeckung von abweichenden Resultaten gegenüber dem konkurrierenden NQueens@Home Projekt. Der Grund für die nicht übereinstimmenden Teilresultate basiert, nach unser Analyse, auf einem overflow - Fehler in den weltweit verteilten Lösungszählern. Damit setzten wir einem seit langem offenen Disputüber die korrekte Lösung von N=24 ein Ende - ohne irgendeine eigene Berechnung auf der Problemgröße durchgeführt zu haben! War es bis zu diesem Zeitpunkt unbemerkt, dass die Fehlsumme der beiden differierenden Lösungen mit 227514171973736 - 226732487925864 = 781684047872 = 0xb600000000 = 182·232 auf einen 32 Bit überlauf schließen lies. Exakter gesagt, genau 182 überläufe des 32-Bit Zählers, welcher für die Addition der Teillösungen verwendet wurde. Damit ist auch die bisherige Arbeit von Nqueens@Home zum N=26 Problem in Frage gestellt - immerhin gut 12 Prozent der geschätzten Gesamtarbeit.
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