Die Damen haben gerechnet: 22.09.2016 - Neuer Weltrekord für Queens@TUD-Team!
Nach 7 Jahren Weiterentwicklung der verfügbaren Technologie demonstrieren wir auf der Grundlage unserer quelloffenen, hochparallelen, FPGA-basierten Infrastruktur mit einem neuen Ansatz der Problempartitionierung die Leistungsfähigkeit der Beschleunigung durch FPGAs.
Springer Link http://dx.doi.org/10.1007/s11265-016-1176-8
GESCHAFFT!
Jetzt haben wir, erneut als weltweit erstes Team, das 27-Damenproblem gelöst! Die entwickelten Löser nutzten FPGAs (Field Programmable Gate Array), welche ein massiv paralleles Rechnen ermöglichen. Durch die Vorplatzierung einiger Damen wird der Lösungsansatz so zerlegt, dass die resultierenden Teilprobleme unabhängig und parallel zueinander bearbeitet werden können. Das 27-Damenproblem wurde in 2.024.110.796 Teilaufgaben zerlegt, von denen kontinuierlich um die 7000 gleichzeitig bearbeitet wurden. Für eine Aussicht auf Erfolg bedurfte es der weiteren mathematischen Optimierung des algorithmischen Ansatzes und einer enormen Steigerung der Leistungsfähigkeit von FPGAs. Schließlich mussten diverse FPGA-Boards an der Fakultät Informatik der TU Dresden immer noch über ein Jahr mit all ihrer Leerlaufzeit am 27-Damenproblem rechnen, bevor es geknackt war. Das Ergebnis ist eine einzige riesige Zahl, Q(27) = 234.907.967.154.122.528, die auch angibt, wie viele verschiedene Anordnungen von 27 Karten man als gut durchmischt ansehen kann. Es wird noch einige Zeit ins Land gehen, bevor diese Zahl auch für ein einfaches Skatblatt von 32 Karten bekannt sein wird.
In Anbetracht des explodierenden Rechenaufwandes und des dadurch begründeten langsamer werdenden Fortschritts bei der Analyse neuer Brettgrößen wird dieser Rekord wahrscheinlich über einige Jahre bestehen bleiben. Auch die Bestätigung dieses neuen Ergebnisses durch eine unabhängige Berechnung könnte auf sich warten lassen. Als hochparalleles Computer-Benchmark ist das n-Damenproblem inzwischen auch für Forscherteams interessant, die Grafikkarten als allgemeine Rechenbeschleuniger einsetzen (GPGPU). Die massiv parallele Architektur von GPUs könnte jedenfalls die Bewältigung ähnlicher oder gar größerer Problemgrößen ermöglichen
Kontakt: