Traduit par Lydie
Des chercheurs de l’Université des Sciences et Technologies de Hong Kong (HKUST) et de Huawei Technologies ont conçu une machine Ising creuse sur FPGA qui résout des problèmes d’optimisation combinatoire jusqu’à 68 fois plus rapidement que les précédentes implémentations sur FPGA, en faisant quelque chose d’étonnamment direct : traiter les problèmes creux comme tels.
L’étude, publiée dans Nature Communications, cible le problème Max-Cut, une tâche d’optimisation combinatoire NP-difficile dont le but est de partitionner les sommets d’un graphe en deux ensembles de sorte que le nombre d’arêtes traversant la partition soit maximisé. Max-Cut a des applications dans la conception de circuits, la physique statistique et l’apprentissage automatique, et appartient à la même classe de problèmes que les machines Ising sont conçues pour accélérer.
L’approche de la parcimonie
Les graphes Max-Cut du monde réel sont typiquement creux ; ils ont relativement peu d’arêtes par rapport au nombre de nœuds. Mais les précédentes machines Ising sur FPGA les traitaient comme denses, gaspillant la mémoire sur puce avec des entrées nulles et limitant la taille des problèmes pouvant tenir sur une seule puce.
L’équipe a introduit un format de données en liste de coordonnées tuilées (TCOO), qui regroupe les entrées non nulles en tuiles de taille fixe alignées sur l’architecture de la RAM bloc (BRAM/URAM) du FPGA. Cela permet une multiplication matrice-vecteur creuse efficace directement sur le FPGA sans surcharge de streaming, exploitant la parcimonie naturelle du problème.
Combiné à une quantification entière sur 8 bits, réduisant l’empreinte mémoire d’un facteur quatre par rapport au traditionnel virgule flottante 32 bits, le concept permet à jusqu’à 20 000 variables de tenir sur une seule puce FPGA sans dégrader la qualité de la solution.
Performances
Sur la collection de graphes Gset, un benchmark standard pour Max-Cut, le concept a atteint une accélération de 10 à 68 fois par rapport aux machines Ising sur FPGA les plus avancées. Aucun réseau multi-FPGA ni cluster GPU n’était nécessaire ; l’intégralité du calcul s’est déroulée sur une seule puce.
L’équipe, dirigée par Baijian Yao, Xu Shi et Wei Zhang à HKUST, avec Daniel Ebler, Juntao Wang, Fan Zhang et Jie Sun chez Huawei Technologies, a conçu le matériel et le logiciel conjointement. Le flux de données, l’architecture du pipeline et la hiérarchie mémoire ont été co-optimisés pour minimiser la latence et maximiser le débit.
Le résultat est la première machine Ising sur FPGA capable de gérer 20 000 spins sur une seule puce, une échelle qui nécessitait auparavant des systèmes multi-FPGA ou à base de GPU.
Sources :
1. Yao B, Shi X, Zhang W, Ebler D, Wang J, Zhang F, Sun J. « Precision meets speed through an FPGA-based natively sparse Ising machine for combinatorial optimization. » Nature Communications. 2026. DOI : 10.1038/s41467-026-75119-0