Un recuit d’Ising calculant en mémoire, compact et numérique, avec bits SRAM probabilistes en 28 nm pour le problème du voyageur de commerce

Pourquoi des itinéraires et des puces plus intelligents comptent

Chaque jour, des camions de livraison, des avions et des paquets de données doivent choisir quel trajet emprunter pour que tout arrive à l’heure avec un coût minimal. Ce type de casse-tête, connu sous le nom de problème du voyageur de commerce, devient rapidement ingérable pour même des ordinateurs puissants à mesure que le nombre d’arrêts augmente. L’article résumé ici présente un nouveau type de puce spécialisée qui aborde ces problèmes de planification de routes beaucoup plus efficacement, en empruntant des idées aux matériaux magnétiques et en les intégrant directement dans la mémoire informatique standard.

Un casse-tête classique : visiter chaque arrêt une seule fois

Le problème du voyageur de commerce pose une question simple : étant donné une liste de villes et les distances entre elles, quel est le plus court tour qui visite chaque ville exactement une fois et revient au point de départ ? Le piège est que le nombre de tours possibles explose lorsque l’on ajoute des villes, si bien qu’examiner toutes les options est impossible en pratique. Au lieu de cela, les approches modernes cherchent des itinéraires très bons, si ce n’est parfaits. Une approche prometteuse imite la façon dont un réseau de petits aimants, appelé modèle d’Ising, peut se stabiliser dans un état d’énergie faible représentant une bonne solution. En laissant ce réseau « osciller » par des changements aléatoires qui s’apaisent progressivement, le système échappe aux mauvais optimums locaux et trouve de meilleurs itinéraires.

Transformer une puce mémoire en résolveur de problèmes

Plutôt que d’exécuter ce processus sur des processeurs ordinaires, les auteurs l’intègrent directement dans le matériel mémoire, une stratégie appelée calcul-en-mémoire. Ils conçoivent une puce compacte en technologie 28 nanomètres où chaque cellule mémoire minuscule stocke à la fois l’information de distance et participe directement aux calculs. Astucieusement, la puce utilise les imperfections naturelles de fabrication de ses cellules mémoire comme source intégrée d’aléa, éliminant le besoin de générateurs de nombres aléatoires volumineux. En perturbant brièvement les valeurs stockées par une « poussée » de tension contrôlée, certains bits basculent de manière probabiliste, fournissant le léger hasard nécessaire au processus de recuit sans circuits supplémentaires.

Découper de grandes cartes en petits quartiers

Un des principaux obstacles à l’utilisation de solveurs de type Ising pour de larges tâches de planification de routes est la quantité massive de données requise : une représentation détaillée d’un tour de 96 villes nécessiterait normalement un vaste réseau de connexions et de mémoire. Pour éviter cela, les chercheurs regroupent les villes proches en petits clusters puis organisent ces clusters en plusieurs niveaux hiérarchiques. Au niveau le plus élevé, la puce résout l’ordre des clusters ; au niveau suivant, elle affine l’ordre des villes à l’intérieur de chaque cluster ; et ainsi de suite. Cette approche par étapes réduit considérablement la mémoire et les connexions nécessaires, faisant passer la complexité matérielle d’une croissance en puissance quatre du nombre de villes à une croissance en puissance deux, puis en compressant encore plus les distances stockées en ne regroupant étroitement que celles réellement nécessaires.

Comment la puce met à jour de nombreux choix à la fois

À l’intérieur de la puce, des groupes de trois villes forment des blocs de base traités en parallèle. La matrice mémoire est organisée de sorte que, dans chaque cluster, le circuit peut calculer rapidement la variation de longueur totale du tour si des sections du parcours sont permutées. Parce que certains clusters n’interagissent pas directement, le système peut mettre à jour tous les clusters « impairs » en une étape puis tous les clusters « pairs » à la suivante, accélérant la recherche tout en se comportant comme si les changements étaient faits un par un. À chaque cycle, la puce utilise ses cellules mémoire bruitées pour décider d’accepter ou non un mouvement défavorable avec une certaine probabilité — élevée au début pour explorer, puis plus faible pour se stabiliser — mimant le refroidissement d’un métal et orientant l’itinéraire vers des distances de plus en plus courtes.

De la puce de laboratoire aux itinéraires à grande échelle

La puce prototype contient un modeste 6 kilobits de cette mémoire spéciale mais peut déjà résoudre des instances du problème du voyageur de commerce à 96 villes en environ 620 microsecondes tout en consommant moins d’un microjoule d’énergie. Par rapport aux matériels précédemment conçus pour la même tâche, elle réalise des gains allant jusqu’à plusieurs centaines de fois en mémoire requise par unité de taille de problème. Des simulations montrent également qu’en plaçant de nombreux blocs mémoire de ce type côte à côte, ce même concept pourrait s’étendre à des problèmes comptant des milliers de villes tout en gardant une croissance matérielle presque linéaire. Pour le lecteur non spécialiste, la leçon principale est que transformer une puce mémoire familière en résolveur actif — et faire d’imperfections de fabrication inévitables une caractéristique utile — ouvre la voie à du matériel petit, rapide et économe en énergie capable d’aider à planifier en temps réel des itinéraires et des emplois du temps complexes.

Citation: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

Mots-clés: problème du voyageur de commerce, recuit d’Ising, calcul-en-mémoire, matériel SRAM, optimisation combinatoire