Faire 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 avec le soi-disant neuvième nombre de Dedekind. Des industry experts du monde entier recherchent la valeur depuis 1991. Les scientifiques de Paderborn sont arrivés à la séquence exacte de nombres à l’aide du supercalculateur Noctua qui s’y trouve.
Les résultats seront présentés en septembre lors de l’Atelier worldwide sur les fonctions booléennes et leurs applications (BFA) en Norvège.
Ce qui a commencé comme un projet de thèse de learn par Lennart Van Hirtum, alors étudiant en informatique à la KU Leuven et maintenant chercheur associé à l’Université de Paderborn, est devenu un énorme succès. Les scientifiques rejoignent un groupe illustre avec leur travail : les premiers numéros 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 furthermore tard par des grands noms de l’informatique tels que Randolph Church et Morgan Ward.
« Pendant 32 ans, le calcul de D(9) était un défi ouvert, et on pouvait se demander s’il serait jamais probable de calculer ce nombre », déclare Van Hirtum.
Le nombre précédent de la séquence Dedekind, le 8e nombre Dedekind, a été trouvé en 1991 à l’aide d’un Cray 2, le supercalculateur le plus puissant à l’époque. « Il nous semblait donc concevable qu’il soit désormais feasible de calculer le 9e nombre sur un grand supercalculateur », déclare Van Hirtum, décrivant la motivation de l’ambitieux projet, qu’il a initialement mis en œuvre conjointement avec les directeurs de son mémoire de maîtrise à KU Louvain.
Grains de sable, échecs et superordinateurs
Le sujet principal des nombres de Dedekind est ce qu’on appelle les fonctions booléennes monotones. Van Hirtum explique : « Fondamentalement, vous pouvez considérer une fonction booléenne monotone en deux, trois et dimensions infinies comme un jeu avec un cube à n dimensions. Vous équilibrez le cube sur un coin, puis colorez chacun des cash restants soit en blanc.
ou rouge. Il n’y a qu’une seule règle : il ne faut 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 ce qui est défini comme le nombre Dedekind. Même si cela n’en a pas l’air, les nombres deviennent rapidement gigantesques dans le processus : le 8e nombre Dedekind a déjà 23 chiffres.
Des nombres relativement grands – mais incomparablement in addition faciles à calculer – sont connus d’une légende concernant l’invention du jeu d’échecs. « Selon cette légende, l’inventeur du jeu d’échecs ne demandait au roi 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 seconde, quatre sur la troisième, et deux fois in addition sur chacune des conditions suivantes. Le roi comprit rapidement que cette demande était not possible à satisfaire, vehicle il n’existe pas autant de riz dans le monde entier.
il est évident qu’il faudrait à la fois une méthode de calcul efficace et un ordinateur très rapide pour trouver D(9) », a déclaré Van Hirtum..
Jalon : les années deviennent des mois
Pour calculer D(9), les scientifiques ont utilisé une system développée par le directeur de mémoire Patrick De Causmaecker connue sous le nom de formule du coefficient P. Il fournit un moyen de calculer les nombres de Dedekind non pas en comptant, mais par une très grande somme. Cela permet à D(8) d’être décodé en seulement huit minutes sur un ordinateur transportable usual.
Mais, « Ce qui prend huit minutes pour D(8) devient des centaines de milliers d’années pour D(9). Même si vous utilisiez un grand supercalculateur exclusivement pour cette tâche, il faudrait encore de nombreuses années pour terminer le calcul », Van Hirtum fait remarquer. Le principal problème est que le nombre de termes dans cette formule augmente incroyablement rapidement.
« Dans notre cas, en exploitant les symétries dans la formule, nous avons pu réduire le nombre de termes à « seulement » 5,5*10^18 – une quantité énorme. En comparaison, le nombre de grains de sable sur Terre est d’environ 7,5* 10 ^ 18, ce qui n’est pas à négliger, mais pour un supercalculateur 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 de GPU, car or truck actuellement la technologie d’accélération matérielle la moreover rapide pour de nombreuses programs d’IA, n’est pas efficace pour cet algorithme.
La solution : un matériel spécifique à l’application utilisant des unités arithmétiques hautement spécialisées et parallèles – appelées FPGA (réseaux de portes programmables par l’utilisateur). Van Hirtum a développé un premier prototype pour l’accélérateur matériel et a commencé à chercher un superordinateur doté des cartes FPGA nécessaires. Dans le processus, il a pris connaissance de l’ordinateur Noctua 2 au « Paderborn Centre for Parallel Computing (Laptop2) » de l’Université de Paderborn, qui possède l’un des systèmes FPGA les as well as puissants au monde.
Le professeur Christian Plessl, responsable du Computer2, explique : « Lorsque Lennart Van Hirtum et Patrick De Causmaeker nous ont contactés, il nous a immédiatement semblé clair que nous voulions soutenir ce projet Moonshot. La résolution de problèmes combinatoires difficiles avec les FPGA est un domaine prometteur. d’application et Noctua 2 est l’un des rares supercalculateurs au monde avec lequel l’expérience est réalisable.
Les exigences extrêmes de fiabilité et de stabilité constituent également un défi et un check pour notre infrastructure. L’équipe de consultants experts en FPGA a travaillé en étroite collaboration avec Lennart pour adapter et optimiser l’application pour notre environnement. »
Après plusieurs années de développement, le programme a fonctionné sur le supercalculateur pendant environ cinq mois.
Et puis le minute était venu : le 8 mars, les scientifiques ont trouvé le 9e numéro Dedekind :.
Aujourd’hui, trois ans après le début du projet Dedekind, Van Hirtum travaille en tant que boursier de la NHR Graduate Faculty au Paderborn Center for Parallel Computing pour développer la prochaine génération d’outils matériels dans son doctorat. L’école doctorale NHR (Nationwide Significant Overall performance Computing) est l’école doctorale conjointe des centres NHR.
Il rendra compte de son extraordinaire succès avec Patrick De Causmaecker le 27 juin à 14h00 dans la salle de conférence O2 de l’Université de Paderborn. Le community intéressé est cordialement invité.
