Omnisolver: An extensible interface to Ising spin-glass and QUBO solvers: adding a distributed GPU brute-force plugin

In der weiten Landschaft des modernen Computings existiert eine Klasse von Problemen, die so komplex sind, dass das Finden der einen besten Lösung sich anfühlt wie die Suche nach einem bestimmten Sandkorn in einer Wüste, die sich mit jedem Schritt verdoppelt. Dies sind Optimierungsherausforderungen, die oft als Netzwerke interagierender Teile modelliert werden, bei denen das Ziel darin besteht, die Teile so anzuordnen, dass der niedrigstmögliche Energiezustand oder die niedrigsten Kosten erreicht werden. Wissenschaftler und Ingenieure nutzen diese Modelle, um alles zu verstehen, vom Verhalten von Materialien auf atomarer Ebene bis hin zur Steuerung des Verkehrs oder der Verwaltung von Finanzportfolios. Jahrzehntelang war die zuverlässigste Methode zur Lösung dieser Rätsel das Überprüfen jeder einzelnen möglichen Anordnung, eine Methode, die als erschöpfende Suche (Exhaustive Search) bekannt ist. Doch wenn die Anzahl der Teile wächst, explodiert die Anzahl der möglichen Anordnungen so schnell, dass selbst die leistungsstärksten Supercomputer der Welt die Aufgabe nicht innerhalb eines Menschenlebens bewältigen können. Dies schafft eine kritische Lücke: Ohne eine Möglichkeit, die absolut beste Antwort zu finden, können Forscher nicht sicher sein, ob die klugen Abkürzungen, die sie verwenden, um „gut genuge“ Antworten zu finden, tatsächlich der Wahrheit nahekommen.

Ein Team von Forschern aus Polen hat nun ein neues Werkzeug entwickelt, das darauf ausgelegt ist, diese Lücke für einen spezifischen Bereich schwieriger Probleme zu schließen. Sie haben ein Software-Update erstellt, das eine Standard-Grafikkarte – jene, die man in Hochleistungs-Computern für Gaming und Video findet – in eine Maschine verwandelt, die in der Lage ist, jede mögliche Anordnung für Probleme mit bis zu sechzig Teilen zu überprüfen. Durch die Kombination dieser rohen Prüfleistung mit einem System, das die Arbeit auf mehrere Computer verteilt, ist es ihnen gelungen, die perfekte Lösung für Probleme zu finden, die zuvor zu groß waren, um vollständig gelöst zu werden. Diese Errungenschaft liefert eine „Goldstandard“-Antwort, gegen die andere, schnellere Computerprogramme getestet werden können, um zu verifizieren, ob ihre Abkürzungen wirklich funktionieren oder ob sie die beste Lösung gänzlich übersehen.

Der Kern dieser Arbeit ist ein Software-Plugin namens Omnisolver-bruteforce, das als universeller Übersetzer für verschiedene Arten von Computer-Solvern fungiert. Man kann es sich wie einen Generalschlüssel vorstellen, der es Forschern ermöglicht, verschiedene Werkzeuge einzustecken, um dasselbe Problem anzugehen. Die Forscher nahmen ein bestehendes Werkzeug, das jede Möglichkeit auf einer einzelnen Grafikkarte prüfen konnte, und verbesserten es so, dass es gleichzeitig über ein Netzwerk von acht leistungsstarken Karten funktioniert. Sie erreichten dies, indem sie den massiven Suchraum in kleinere, unabhängige Stücke aufteilte. Stellen Sie sich eine Bibliothek vor, in der Sie ein bestimmtes Buch suchen müssen; anstatt dass eine Person jedes Regal überprüft, wird die Aufgabe so aufgeteilt, dass acht Personen gleichzeitig verschiedene Abschnitte prüfen und sich nur dann zurückmelden, wenn sie das Ziel finden. In diesem Fall ist die „Bibliothek“ die Menge aller möglichen Anordnungen des Problems, und die „Sucher“ sind die Grafikkarten, die parallel arbeiten.

Die Forscher testeten dieses neue System auf einem Cluster aus acht Hochleistungs-Grafikkarten, die jeweils über eine große Menge an Speicher verfügen. Sie stellten das System so ein, dass es zufällige Versionen dieser Optimierungsprobleme löst, wobei sie die Größe des Problems schrittweise von vierzig Teilen auf sechzig Teile erhöhten. Die Ergebnisse waren beeindruckend. Für Probleme mit sechzig Teilen benötigte das System etwa drei Tage, um jede einzelne Möglichkeit zu prüfen und die beste Antwort zu bestätigen. Das mag nach einer langen Zeit klingen, aber ohne diese neue Methode wäre die Aufgabe in einer angemessenen Zeitspanne unmöglich gewesen. Das Team beobachtete, dass sich die für die Lösung erforderliche Zeit bei jedem zusätzlich hinzugefügten Teil des Problems in etwa verdoppelte – ein Muster, das bei allen ihren Tests Bestand hatte. Dieses vorhersehbare Verhalten bestätigte, dass ihr System exakt so arbeitet, wie es die Gesetze der Physik und Mathematik für diese Art der erschöpfenden Suche vorschreiben.

Ein bedeutender Teil der Innovation bestand darin, sicherzustellen, dass der Computer bei einer solch massiven Menge an Arbeit keine kleinen Fehler macht. Grafik Karten sind auf Geschwindigkeit ausgelegt, oft auf Kosten extremer Präzision, was zu winzigen Fehlern führen kann, die sich über die Zeit aufsummieren. Die Forscher entwickelten eine Methode, um diese winzigen Fehler automatisch zu korrigieren, während sie entstehen, wodurch sichergestellt wurde, dass die endgültige Antwort mathematisch exakt ist. Sie verifizierten dies, indem sie ihre Ergebnisse mit einer bekannten perfekten Lösung für kleinere Probleme verglichen, und stellten fest, dass die Antworten bis auf die letzte Stelle übereinstimmten. Diese Zuverlässigkeit ist entscheidend, da das Werkzeug nicht dazu gedacht ist, alltägliche Geschäftsprobleme zu lösen, sondern als Referenzpunkt zu dienen. Es ermöglicht Wissenschaftlern, neue, schnellere Algorithmen – etwa solche, die von der Quantenphysik oder biologischen Systemen inspiriert sind – zu testen, um zu sehen, ob sie tatsächlich die beste Lösung finden oder ob sie nur raten.

Die Studie blickte auch voraus auf das, was mit noch größeren Computer-Clustern möglich sein könnte. Die Forscher berechneten, dass sie, wenn sie zweihundertsechzehn Grafikkarten verbinden könnten, ein Problem mit sechzig Teilen in nur dreiunddreißig Sekunden lösen könnten. Sie schätzten ferner, dass sie mit einem solch massiven Netzwerk theoretisch in der Lage wären, Probleme mit bis zu sechsundsiebzig Teilen innerhalb eines Monats zu lösen. Sie waren jedoch vorsichtig genug, darauf hinzuweisen, dass dies Projektionen basierend auf ihren aktuellen Daten sind und dass reale Faktoren wie Kommunikationsverzögerungen zwischen den Computern die genauen Zahlen verändern könnten. Das aktuelle System ist aufgrund der Art und Weise, wie die Software die Anordnungen zählt, auf Probleme mit vierundsechzig Teilen begrenzt, aber innerhalb dieser Grenze liefert es eine definitive Antwort.

Diese Arbeit beansprucht nicht, alle Optimierungsprobleme gelöst zu haben, noch legt sie nahe, dass die erschöpfende Suche die schnelleren, approximativen Methoden für den täglichen Gebrauch ersetzen wird. Stattdessen bietet sie eine Möglichkeit, die Qualität dieser schnelleren Methoden zu zertifizieren. Indem sie eine garantierte korrekte Antwort für Probleme einer bestimmten Größe liefern, haben die Forscher der wissenschaftlichen Gemeinschaft ein Lineal gegeben, um die Genauigkeit neuer Technologien zu messen. Während sich das Feld des Computings in Richtung komplexerer Herausforderungen bewegt, wird ein Werkzeug, das definitiv sagen kann: „Dies ist die bestmögliche Antwort“, zu einem unverzichtbaren Maßstab. Die Forscher haben ihre Software der Öffentlichkeit zur Verfügung gestellt und laden die Gemeinschaft ein, diese neue Fähigkeit zu nutzen, um ihre eigenen Entdeckungen zu verifizieren und die Grenzen dessen zu verschieben, was rechnerisch möglich ist.