Un anilador Ising compacto de cálculo-en-memoria digital con bits SRAM probabilísticos en 28 nm para el problema del viajante

Por qué importan rutas y chips más inteligentes

Cada día, camiones de reparto, aviones y paquetes de datos deben decidir qué camino tomar para que todo llegue a tiempo con el menor coste posible. Este tipo de rompecabezas, conocido como el Problema del Viajante, se vuelve rápidamente inabordable incluso para ordenadores potentes a medida que crecen las paradas. El artículo que resume este texto presenta un nuevo tipo de chip especializado que aborda estos problemas de planificación de rutas de forma mucho más eficiente, usando ideas inspiradas en materiales magnéticos e integradas directamente en la memoria estándar del ordenador.

Un rompecabezas clásico: visitar cada parada una vez

El Problema del Viajante plantea una pregunta simple: dada una lista de ciudades y las distancias entre ellas, ¿cuál es el recorrido más corto que visita cada ciudad exactamente una vez y vuelve al punto de partida? La dificultad es que el número de recorridos posibles se dispara al añadir ciudades, por lo que comprobar todas las opciones es imposible en la práctica. En su lugar, los métodos modernos buscan rutas muy buenas, aunque no siempre perfectas. Un enfoque prometedor imita cómo una red de pequeños imanes, llamada modelo de Ising, puede asentarse en un estado de baja energía que representa una buena solución. Dejando que esta red “vibre” mediante cambios aleatorios que se van rebajando gradualmente, el sistema escapa de elecciones locales malas y encuentra rutas mejores.

Convertir un chip de memoria en un solucionador

En lugar de ejecutar este proceso en procesadores ordinarios, los autores lo integran en el propio hardware de memoria, una estrategia llamada cálculo-en-memoria. Diseñan un chip compacto en tecnología de 28 nanómetros donde cada diminuta celda de memoria almacena tanto información de distancias como participa directamente en los cálculos. De forma ingeniosa, el chip aprovecha las imperfecciones naturales de fabricación de sus celdas de memoria como fuente integrada de aleatoriedad, eliminando la necesidad de generadores de números aleatorios voluminosos. Al perturbar brevemente los valores almacenados con un “empujón” de tensión controlado, algunos bits se invierten de forma probabilística, proporcionando la suavidad aleatoria necesaria para el proceso de anillamiento sin circuitería adicional.

Dividir mapas grandes en vecindarios pequeños

Uno de los principales obstáculos para usar solucionadores tipo Ising en tareas grandes de planificación de rutas es la enorme cantidad de datos requerida: una representación completa de un recorrido de 96 ciudades normalmente necesitaría una vasta red de conexiones y memoria. Para evitarlo, los investigadores agrupan ciudades cercanas en pequeños clústeres y luego ordenan esos clústeres en varios niveles de jerarquía. En el nivel más alto, el chip resuelve cómo deben ordenarse los clústeres; en el siguiente nivel, refina el orden de las ciudades dentro de cada clúster; y así sucesivamente. Este enfoque por etapas reduce drásticamente la memoria y las conexiones necesarias, bajando la complejidad del hardware de algo que crece con la cuarta potencia del número de ciudades a algo que solo crece con el cuadrado, y además comprime aún más las distancias almacenadas agrupando estrechamente solo las necesarias.

Cómo el chip actualiza muchas opciones a la vez

Dentro del chip, grupos de tres ciudades forman bloques básicos que se manejan en paralelo. La matriz de memoria está organizada de modo que, dentro de cada clúster, el circuito puede calcular rápidamente el cambio en la longitud total del recorrido si se intercambian secciones del mismo. Dado que algunos clústeres no interactúan directamente, el sistema puede actualizar todos los clústeres “impares” en un paso y todos los “pares” en el siguiente, acelerando la búsqueda mientras se comporta como si los cambios se hicieran uno a la vez. Durante cada ronda, el chip usa sus celdas de memoria ruidosas para decidir si acepta un movimiento peor con cierta probabilidad—alta al principio para explorar y más baja después para estabilizarse—imitando el enfriamiento de un metal y guiando la ruta hacia distancias cada vez más cortas.

Del chip de laboratorio a rutas a gran escala

El prototipo contiene unos modestos 6 kilobits de esta memoria especial y ya puede resolver instancias del Problema del Viajante con 96 ciudades en aproximadamente 620 microsegundos usando menos de un microjoule de energía. En comparación con hardware previo diseñado para la misma tarea, logra mejoras de hasta cientos de veces en la cantidad de memoria requerida por unidad de tamaño del problema. Simulaciones también muestran que colocando muchos de estos bloques de memoria uno junto a otro, el mismo diseño podría escalar a problemas con miles de ciudades manteniendo un crecimiento de hardware casi lineal. Para el lector general, la idea principal es que, al reconvertir una memoria familiar en un solucionador activo—y al transformar fallos inevitables de fabricación en una característica útil—este trabajo apunta a hardware pequeño, rápido y energético eficiente que puede ayudar a planificar rutas y horarios complejos en tiempo real.

Cita: 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

Palabras clave: problema del viajante, anilador Ising, cálculo-en-memoria, hardware SRAM, optimización combinatoria