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

Dans le vaste paysage de l'informatique moderne, il existe une classe de problèmes si complexes que trouver la meilleure solution unique donne l'impression de chercher un grain de sable spécifique dans un désert qui double de taille à chaque pas que l'on fait. Ce sont des défis d'optimisation, souvent modélisés comme des réseaux de parties en interaction où l'objectif est d'organiser les pièces pour atteindre l'état d'énergie ou de coût le plus bas possible. Les scientifiques et les ingénieurs utilisent ces modèles pour comprendre tout, du comportement des matériaux au niveau atomique à la gestion du trafic ou des portefeuilles financiers. Pendant des décennies, la méthode la plus fiable pour résoudre ces énigmes a été de vérifier chaque arrangement possible, une méthode connue sous le nom de recherche exhaustive. Cependant, à mesure que le nombre de pièces augmente, le nombre d'arrangements possibles explose si rapidement que même les superordinateurs les plus puissants du monde ne peuvent terminer la tâche en une vie humaine. Cela crée un fossé critique : sans un moyen de trouver la réponse absolument parfaite, les chercheurs ne peuvent être certains si les raccourcis astucieux qu'ils utilisent pour trouver des réponses « assez bonnes » sont réellement proches de la vérité.

Une équipe de chercheurs de Pologne a maintenant construit un nouvel outil conçu pour combler ce fossé pour une gamme spécifique de problèmes difficiles. Ils ont créé une mise à jour logicielle qui transforme une carte graphique standard, le type de carte que l'on trouve dans les ordinateurs haut de gamme pour le jeu vidéo et la vidéo, en une machine capable de vérifier chaque arrangement possible pour des problèmes comprenant jusqu'à soixante pièces. En combinant cette puissance de vérification brute avec un système qui répartit le travail sur plusieurs ordinateurs, ils ont réussi à trouver la solution parfaite pour des problèmes qui étaient auparavant trop vastes pour être résolus complètement. Cette réussite fournit une réponse de « référence » (gold standard) contre laquelle d'autres programmes informatiques plus rapides peuvent être testés, permettant aux scientifiques de vérifier si leurs raccourcis fonctionnent réellement ou s'ils passent à côté de la meilleure solution.

Le cœur de ce travail est un plugin logiciel appelé Omnisolver-bruteforce, qui agit comme un traducteur universel pour différents types de solveurs informatiques. Considérez-le comme une clé maîtresse qui permet aux chercheurs de brancher divers outils pour s'attaquer au même problème. Les chercheurs ont pris un outil existant capable de vérifier toutes les possibilités sur une seule carte graphique et l'ont amélioré pour qu'il fonctionne sur un réseau de huit cartes puissantes simultanément. Ils y sont parvenus en découpant l'immense espace de recherche en blocs plus petits et indépendants. Imaginez une bibliothèque où vous devez trouver un livre spécifique ; au lieu d'une seule personne vérifiant chaque étagère, la tâche est divisée de sorte que huit personnes vérifient différentes sections en même temps, ne signalant leur présence que lorsqu'elles trouvent la cible. Dans ce cas, la « bibliothèque » est l'ensemble de tous les arrangements possibles du problème, et les « chercheurs » sont les cartes graphiques travaillant en parallèle.

Les chercheurs ont testé ce nouveau système sur un cluster de huit cartes graphiques haute performance, chacune dotée d'une grande quantité de mémoire. Ils ont configuré le système pour résoudre des versions aléatoires de ces problèmes d'optimisation, augmentant progressivement la taille du problème de quarante à soixante pièces. Les résultats ont été frappants. Pour des problèmes à soixante pièces, le système a mis environ trois jours pour vérifier chaque possibilité et confirmer la meilleure réponse. Cela peut sembler long, mais sans cette nouvelle méthode, la tâche aurait été impossible à accomplir dans un délai raisonnable. L'équipe a observé que pour chaque pièce supplémentaire ajoutée au problème, le temps requis pour le résoudre doublait approximativement, un schéma qui s'est maintenu lors de tous leurs tests. Ce comportement prévisible a confirmé que leur système fonctionnait exactement comme les lois de la physique et des mathématiques l'exigent pour ce type de recherche exhaustive.

Une partie importante de l'innovation a consisté à s'assurer que l'ordinateur ne commette pas de petites erreurs lors d'un travail aussi massif. Les cartes graphiques sont conçues pour être rapides, souvent au détriment d'une précision extrême, ce qui peut conduire à de minuscules erreurs qui s'accumulent avec le temps. Les chercheurs ont développé une méthode pour corriger automatiquement ces minuscules erreurs au fur et à mesure qu'elles se produisent, garantissant que la réponse finale soit mathématiquement exacte. Ils ont vérifié cela en comparant leurs résultats à une solution parfaite connue pour des problèmes plus petits et ont constaté que les réponses correspondaient jusqu'au dernier chiffre. Ce niveau de fiabilité est crucial car l'outil n'est pas destiné à résoudre les problèmes quotidiens des entreprises, mais plutôt à servir de point de référence. Il permet aux scientifiques de tester de nouveaux algorithmes plus rapides — tels que ceux inspirés par la physique quantique ou les systèmes biologiques — pour voir s'ils trouvent réellement la meilleure solution ou s'ils ne font que deviner.

L'étude a également regardé vers l'avenir, vers ce qui pourrait être possible avec des clusters informatiques encore plus grands. Les chercheurs ont calculé que s'ils pouvaient connecter deux cent seize cartes graphiques, ils pourraient résoudre un problème de soixante pièces en seulement trente-trois secondes. Ils ont également estimé qu'avec un réseau aussi massif, ils pourraient théoriquement résoudre des problèmes allant jusqu'à soixante-seize pièces en un mois. Cependant, ils ont pris soin de noter que ce sont des projections basées sur leurs données actuelles, et que des facteurs réels comme les délais de communication entre les ordinateurs pourraient modifier les chiffres exacts. Le système actuel est limité aux problèmes de soixante-quatre pièces en raison de la manière dont le logiciel gère le comptage des arrangements, mais à l'intérieur de cette limite, il fournit une réponse définitive.

Ce travail ne prétend pas avoir résolu tous les problèmes d'optimisation, ni suggère que la recherche exhaustive remplacera les méthodes plus rapides et approximatives pour l'usage quotidien. Au contraire, il offre un moyen de certifier la qualité de ces méthodes plus rapides. En fournissant une réponse garantie correcte pour des problèmes d'une certaine taille, les chercheurs ont donné à la communauté scientifique une règle pour mesurer la précision des nouvelles technologies. Alors que le domaine de l'informatique évolue vers des défis plus complexes, posséder un outil capable de dire de manière définitive « c'est la meilleure réponse possible » devient un critère de référence essentiel. Les chercheurs ont rendu leur logiciel disponible pour les autres, invitant la communauté à utiliser cette nouvelle capacité pour vérifier leurs propres découvertes et repousser les limites de ce qui est computationnellement possible.