¿Alguna vez te has enfrentado a un problema en el que tuviste que encontrar una solución óptima entre muchas opciones posibles, como encontrar la ruta más rápida a un lugar determinado, teniendo en cuenta tanto la distancia como el tráfico?

Si es así, el problema con el que estaba tratando es lo que se conoce formalmente como un "problema de optimización combinatoria". Si bien están formulados matemáticamente, estos problemas son comunes en el mundo real y surgen en varios campos, incluidos la logística, el enrutamiento de redes, el aprendizaje automático y la ciencia de los materiales.

Sin embargo, los problemas de optimización combinatoria a gran escala son muy intensivos desde el punto de vista computacional para resolverlos utilizando computadoras estándar, lo que hace que los investigadores recurran a otros enfoques. Uno de estos enfoques se basa en el "modelo de Ising", que matemáticamente representa la orientación magnética de los átomos, o "espines", en un material ferromagnético.

A altas temperaturas, estos espines atómicos se orientan aleatoriamente. Pero a medida que la temperatura disminuye, los espines se alinean para alcanzar el estado de energía mínima en el que la orientación de cada espín depende de sus vecinos. Resulta que este proceso, conocido como "recocido", se puede usar para modelar problemas de optimización combinatoria de modo que el estado final de los espines produzca la solución óptima.

Los investigadores han intentado crear procesadores de recocido que imitan el comportamiento de los espines utilizando dispositivos cuánticos y han intentado desarrollar dispositivos semiconductores utilizando tecnología de integración a gran escala (LSI) con el objetivo de hacer lo mismo. En particular, el grupo de investigación del profesor Takayuki Kawahara en la Universidad de Ciencias de Tokio (TUS) en Japón ha logrado avances importantes en este campo en particular.

En 2020, el profesor Kawahara y sus colegas presentaron en la conferencia internacional de 2020, IEEE SAMI 2020, uno de los primeros procesadores de recocido LSI totalmente acoplados (es decir, que tienen en cuenta todas las posibles interacciones espín-espín en lugar de las interacciones con espines vecinos únicamente), que comprende 512 giros totalmente conectados.

Su trabajo apareció en la revista IEEE Transactions on Circuits and Systems I:Regular Papers . Estos sistemas son notoriamente difíciles de implementar y mejorar debido a la gran cantidad de conexiones entre giros que deben tenerse en cuenta. Si bien el uso de varios chips completamente conectados en paralelo era una posible solución al problema de escalabilidad, esto hizo que la cantidad requerida de interconexiones (cables) entre chips fuera prohibitivamente grande.

En un estudio reciente publicado en Microprocessors and Microsystems , el Prof. Kawahara y su colega demostraron una solución inteligente a este problema. Desarrollaron un nuevo método en el que el cálculo del estado de energía del sistema se divide primero entre múltiples chips totalmente acoplados, formando una "calculadora de matriz".

Un segundo tipo de chip, llamado "chip de control", luego recopila los resultados del resto de los chips y calcula la energía total, que se utiliza para actualizar los valores de los giros simulados. "La ventaja de nuestro enfoque es que la cantidad de datos transmitidos entre los chips es extremadamente pequeña", explica el Prof. Kawahara. "Aunque su principio es simple, este método nos permite realizar un sistema LSI escalable y completamente conectado para resolver problemas de optimización combinatoria a través del recocido simulado".

Los investigadores implementaron con éxito su enfoque utilizando chips FPGA comerciales, que son dispositivos semiconductores programables ampliamente utilizados. Construyeron un sistema de recocido completamente conectado con 384 giros y lo usaron para resolver varios problemas de optimización, incluido un problema de coloración de gráficos de 92 nodos y un problema de corte máximo de 384 nodos.

Lo que es más importante, estos experimentos de prueba de concepto mostraron que el método propuesto brinda verdaderos beneficios de rendimiento. En comparación con una CPU moderna estándar que modela el mismo sistema de recocido, la implementación de FPGA fue 584 veces más rápida y 46 veces más eficiente energéticamente al resolver el problema de corte máximo.

Ahora, con esta exitosa demostración del principio operativo de su método en FPGA, los investigadores planean llevarlo al siguiente nivel. "Deseamos producir un chip LSI de diseño personalizado para aumentar la capacidad y mejorar en gran medida el rendimiento y la eficiencia energética de nuestro método", dice el profesor Kawahara. "Esto nos permitirá lograr el rendimiento requerido en los campos de desarrollo de materiales y descubrimiento de fármacos, que implican problemas de optimización muy complejos".

Finalmente, el Prof. Kawahara señala que desea promover la implementación de sus resultados para resolver problemas reales de la sociedad. Su grupo espera participar en investigaciones conjuntas con empresas y llevar su enfoque al núcleo de la tecnología de diseño de semiconductores, abriendo las puertas al renacimiento de los semiconductores en Japón. + Explora más

Un novedoso procesador que resuelve problemas matemáticos notoriamente complejos