Des scientifiques de l'Institut de technologie de Tokyo ont conçu une nouvelle architecture de processeur capable de résoudre les problèmes d'optimisation combinatoire beaucoup plus rapidement que les problèmes existants. Les optimisations combinatoires sont des problèmes complexes qui apparaissent dans de nombreux domaines de la science et de l'ingénierie et sont difficiles à gérer pour les ordinateurs conventionnels, rendant les architectures de processeurs spécialisées très importantes.

Souvent, les problèmes mathématiques utilisés dans l'ingénierie et d'autres applications scientifiques impliquent des calculs complexes qui dépassent les capacités des ordinateurs modernes en termes de temps et de ressources. C'est le cas pour les problèmes d'optimisation combinatoire.

L'optimisation combinatoire consiste à localiser un objet ou une solution optimale dans un ensemble fini d'objets possibles. De tels problèmes se manifestent en finance comme l'optimisation du portefeuille, en logistique comme le fameux "problème du voyageur de commerce, " en machine learning, et dans la découverte de médicaments. Cependant, les ordinateurs actuels ne peuvent pas faire face à ces problèmes lorsque le nombre de variables est élevé.

Une équipe de chercheurs du Tokyo Institute of Technology, en collaboration avec le laboratoire universitaire Hitachi Hokkaido, et l'Université de Tokyo, a maintenant conçu une nouvelle architecture de processeur pour résoudre spécifiquement des problèmes d'optimisation combinatoire exprimés sous la forme d'un modèle d'Ising. Le modèle d'Ising a été utilisé à l'origine pour décrire les états magnétiques des atomes (spins) dans les matériaux magnétiques. Cependant, ce modèle peut être utilisé comme une abstraction pour résoudre des problèmes d'optimisation combinatoire car l'évolution du spin, qui tend à atteindre l'état d'énergie dit le plus bas, reflète la façon dont un algorithme d'optimisation recherche la meilleure solution. En réalité, l'état des spins dans l'état d'énergie le plus bas peut être directement mappé à la solution d'un problème d'optimisation combinatoire.

L'architecture de processeur proposée, appelé STATICA, est fondamentalement différent des processeurs existants qui calculent les modèles d'Ising, appelés recuits. Une limitation de la plupart des recuits rapportés est qu'ils ne considèrent que les interactions de spin entre les particules voisines. Cela permet un calcul plus rapide, mais limite leurs applications possibles. En revanche, STATICA est entièrement connecté et toutes les interactions spin-to-spin sont prises en compte. Alors que la vitesse de traitement de STATICA est inférieure à celle des recuits similaires, son schéma de calcul est meilleur, car il utilise la mise à jour parallèle.

Dans la plupart des recuits, l'évolution des spins (mise à jour) est calculée de manière itérative. Ce processus est intrinsèquement sériel, ce qui signifie que les changements de spin sont calculés un par un car le changement d'un spin affecte tous les autres dans la même itération. Dans STATICA, le processus de mise à jour est effectué en parallèle à l'aide de ce que l'on appelle des automates à cellules stochastiques. Au lieu de calculer les états de spin en utilisant les spins eux-mêmes, STATICA crée des répliques des spins et les interactions spin-to-replica sont utilisées, permettant un calcul parallèle. Cela permet d'économiser énormément de temps en raison du nombre réduit d'étapes nécessaires. « Nous avons prouvé que les approches conventionnelles et STATICA dérivent la même solution sous certaines conditions, mais STATICA le fait en N fois moins d'étapes, où N est le nombre de spins dans le modèle, " dit le Pr Masato Motomura, qui a mené ce projet. Par ailleurs, l'équipe de recherche a mis en œuvre une approche appelée mise à jour de spin pilotée par delta. Parce que seuls les spins qui ont changé dans l'itération précédente sont importants pour le calcul de la suivante, un circuit de sélection est utilisé qui n'implique que les spins qui ont basculé à chaque itération.

STATICA offre une consommation électrique réduite, vitesse de traitement plus élevée, et une meilleure précision que les autres recuits. "STATICA vise à révolutionner les processeurs de recuit en résolvant des problèmes d'optimisation basés sur le modèle mathématique des automates à cellules stochastiques. Nos premières évaluations ont fourni des résultats solides, " déclare le professeur Motomura. D'autres améliorations feront de STATICA un choix attrayant pour l'optimisation combinatoire.