Des mathématiciens de l’Université de Paderborn et de la KU Leuven, utilisant le supercalculateur Noctua et des accélérateurs matériels spécialisés, ont résolu un problème vieux de plusieurs décennies en calculant le neuvième nombre de Dedekind, une séquence mathématique d’une énorme complexité. Le nombre exact, auparavant considéré comme impossible à calculer en raison de sa taille, est 286386577668298411128469151667598498812366.
Des scientifiques des universités de Paderborn et de Louvain résolvent un problème mathématique connu depuis longtemps.
Entrer dans l’histoire avec 42 chiffres : Des scientifiques de l’université de Paderborn et de la KU Leuven ont percé un mystère mathématique vieux de plusieurs décennies en trouvant le neuvième nombre de Dedekind. Les experts du monde entier recherchent cette valeur depuis 1991. Les scientifiques de Paderborn sont parvenus à la séquence exacte de nombres à l’aide du superordinateur Noctua situé dans l’université. Les résultats seront présentés en septembre lors de l’atelier international sur les fonctions booléennes et leurs applications (BFA) en Norvège.
Ce qui a commencé comme un projet de thèse de maîtrise de Lennart Van Hirtum, alors étudiant en informatique à la KU Leuven et aujourd’hui chercheur associé à l’université de Paderborn, est devenu un énorme succès. Les scientifiques rejoignent un groupe illustre grâce à leurs travaux : Les premiers nombres de la série ont été trouvés par le mathématicien Richard Dedekind lui-même lorsqu’il a défini le problème en 1897, et plus tard par des grands noms de l’informatique tels que Randolph Church et Morgan Ward. « Pendant 32 ans, le calcul de D(9) a été un défi ouvert, et l’on pouvait se demander s’il serait un jour possible de calculer ce nombre », explique M. Van Hirtum.
Crédit : Université de Paderborn, Besim Mazhiqi
Le nombre précédent de la séquence de Dedekind, le 8e nombre de Dedekind, a été trouvé en 1991 à l’aide d’un Cray 2, le superordinateur le plus puissant de l’époque. « Il nous a donc semblé concevable de pouvoir calculer le 9e nombre sur un grand superordinateur », explique M. Van Hirtum en décrivant la motivation de cet ambitieux projet, qu’il a d’abord mis en œuvre conjointement avec les directeurs de sa thèse de maîtrise à l’Université catholique de Louvain (KU Leuven).
Grains de sable, échecs et superordinateurs
Les fonctions booléennes monotones sont le principal sujet des nombres de Dedekind. Van Hirtum explique : « Fondamentalement, on peut considérer une fonction booléenne monotone en deux, trois et infinies dimensions comme un jeu avec un cube à n dimensions. Vous tenez le cube en équilibre sur un coin et vous colorez chacun des coins restants en blanc ou en rouge. Il n’y a qu’une seule règle : vous ne devez jamais placer un coin blanc au-dessus d’un coin rouge. Cela crée une sorte d’intersection verticale rouge-blanc. Le but du jeu est de compter le nombre de coupes différentes. Leur nombre est défini comme le nombre de Dedekind. Même si cela n’en a pas l’air, les nombres deviennent rapidement gigantesques au cours du processus : le 8e nombre de Dedekind compte déjà 23 chiffres. »
a figure montre toutes les coupes possibles pour les dimensions 0, 1, 2 et 3. Le nombre de ces coupes colorées en 2D, 3D et N dimensions qui peuvent être formées est défini comme le nombre de Dedekind. Crédit : Université de Paderborn
Des nombres de taille comparable – mais incomparablement plus faciles à calculer – sont connus grâce à une légende concernant l’invention du jeu d’échecs. « Selon cette légende, l’inventeur du jeu d’échecs demanda au roi de ne placer que quelques grains de riz sur chaque case de l’échiquier en guise de récompense : un grain sur la première case, deux grains sur la deuxième, quatre sur la troisième et deux fois plus sur chacune des cases suivantes. Le roi s’est vite rendu compte que cette demande était impossible à réaliser, car une telle quantité de riz n’existe pas dans le monde entier. Le nombre de grains de riz sur le plateau complet aurait 20 chiffres – une quantité inimaginable, mais toujours inférieure à D(8). Lorsque l’on prend conscience de ces ordres de grandeur, il est évident qu’une méthode de calcul efficace et un ordinateur très rapide seraient nécessaires pour trouver D(9) », a déclaré M. Van Hirtum.
Une étape importante : Les années deviennent des mois
Pour calculer D(9), les scientifiques ont utilisé une technique mise au point par Patrick De Causmaecker, directeur de thèse de maîtrise, connue sous le nom de formule du coefficient P. Cette formule permet de calculer les nombres de Dedekind non pas en comptant, mais en effectuant une très grande somme. Cette formule permet de calculer les nombres de Dedekind non pas en comptant, mais en faisant une très grande somme. Cela permet de décoder D(8) en seulement huit minutes sur un ordinateur portable normal. Mais « ce qui prend huit minutes pour D(8) devient des centaines de milliers d’années pour D(9). Même si l’on utilisait un grand superordinateur exclusivement pour cette tâche, il faudrait encore de nombreuses années pour effectuer le calcul », souligne M. Van Hirtum. Le principal problème est que le nombre de termes de cette formule croît incroyablement vite. Dans notre cas, en exploitant les symétries de la formule, nous avons pu réduire le nombre de termes à « seulement » 5,5*10^18, ce qui est énorme. À titre de comparaison, le nombre de grains de sable sur Terre est d’environ 7,5*10^18, ce qui n’est pas négligeable, mais pour un superordinateur moderne, 5,5*10^18 opérations sont tout à fait gérables », a déclaré l’informaticien. Le problème : le calcul de ces termes sur des processeurs normaux est lent et l’utilisation des GPU, qui constituent actuellement la technologie d’accélération matérielle la plus rapide pour de nombreuses applications d’intelligence artificielle, n’est pas efficace pour cet algorithme.
La solution : du matériel spécifique à l’application utilisant des unités arithmétiques hautement spécialisées et parallèles, appelées FPGA (field programmable gate arrays). Van Hirtum a développé un premier prototype d’accélérateur matériel et s’est mis à la recherche d’un superordinateur équipé des cartes FPGA nécessaires. C’est ainsi qu’il a découvert l’ordinateur Noctua 2 du « Paderborn Center for Parallel Computing (PC2) » de l’université de Paderborn, qui possède l’un des systèmes FPGA les plus puissants au monde.
Christian Plessl, directeur du PC2, explique : « Lorsque Lennart Van Hirtum et Patrick De Causmaeker nous ont contactés, nous avons tout de suite compris que nous voulions soutenir ce projet d’envergure. La résolution de problèmes combinatoires difficiles à l’aide de FPGA est un domaine d’application prometteur et Noctua 2 est l’un des rares supercalculateurs au monde avec lequel l’expérience est tout à fait réalisable. Les exigences extrêmes en matière de fiabilité et de stabilité constituent également un défi et un test pour notre infrastructure. L’équipe d’experts en FPGA a travaillé en étroite collaboration avec Lennart pour adapter et optimiser l’application à notre environnement.
Après plusieurs années de développement, le programme a fonctionné sur le supercalculateur pendant environ cinq mois. Le moment était venu : le 8 mars, les scientifiques ont trouvé le 9e nombre de Dedekind : 286386577668298411128469151667598498812366.
Aujourd’hui, trois ans après le début du projet Dedekind, Van Hirtum travaille en tant que boursier de la NHR Graduate School au Paderborn Center for Parallel Computing pour développer la prochaine génération d’outils matériels dans le cadre de son doctorat. La NHR (National High Performance Computing) Graduate School est l’école supérieure commune des centres NHR. Le 27 juin à 14 heures, dans l’amphithéâtre O2 de l’université de Paderborn, il rendra compte de son extraordinaire réussite en compagnie de Patrick De Causmaecker. Le public intéressé est cordialement invité.