El nuevo procesador de recocido es el mejor en la resolución de problemas de optimización combinatoria

Durante los últimos dos años, IEEE Spectrum ha destacado varios enfoques nuevos para resolver problemas de optimización combinatoria, particularmente Recortador digital de Fujitsu y más recientemente Algoritmo de bifurcación simulada de Toshiba. Ahora, los investigadores en el Instituto de Tecnología de Tokio, con la ayuda de colegas de Hitachi, la Universidad de Hokkaido y la Universidad de Tokio, han diseñado una nueva arquitectura de recocido para hacer frente a este tipo de tarea que ha resultado demasiado exigente para las computadoras convencionales.

Doblado STATICA (Arquitectura del anillador de autómatas celulares estocásticos), el procesador está diseñado para asumir desafíos tales como la cartera, la logística y la optimización del flujo de tráfico cuando se expresan en forma de Ising modelos.

Originalmente utilizado para describir los giros de los imanes que interactúan, los modelos Ising también se pueden utilizar para resolver problemas de optimización. Esto se debe a que las interacciones magnéticas en evolución en un sistema progresan hacia el estado de energía más baja, lo que refleja convenientemente cómo un algoritmo de optimización busca lo mejor, es decir. estado fundamental: solución. En otras palabras, la respuesta a una pregunta de optimización particular se convierte en el equivalente de buscar el estado de energía más bajo del modelo Ising.

Recocidoras actuales como Recocido cuántico de D-Wave computadora y Digital Annealer de Fujitsu calculan las evoluciones de giro en serie, señala Profesor masato motomura en el Instituto de Investigación Innovadora de Tokyo Tech y líder del proyecto STATICA. Como un giro afecta a todos los otros giros en una iteración dada, los cambios de giro se calculan uno por uno, lo que lo convierte en un proceso en serie. Pero en STATICA, señala, que la actualización se realiza en paralelo utilizando autómatas celulares estocásticos (SCA). Esa es una forma de simular sistemas complejos utilizando las interacciones de un gran número de “células” vecinas (giros en STATICA) con reglas de actualización simples y algo de estocasticidad (aleatoriedad).

En los sistemas de recocido convencionales, si un giro gira, afecta a todos los giros conectados y, por lo tanto, todos los giros deben procesarse en la siguiente iteración. Pero en STATICA, SCA introduce copias (réplicas) de los giros originales en el proceso. Todas las interacciones originales spin-spin se redirigen a sus réplicas individuales.

“En este método, todos los giros de réplica se actualizan en paralelo utilizando estas interacciones de giro a giro”, explica Motomura. Si un giro original gira, afecta a su giro de réplica pero no a ninguno de los otros giros originales porque no hay interacción entre ellos, a diferencia del recocido convencional. Y en la siguiente iteración, los giros de la réplica se interpretan como giros originales y se repite la actualización de giros paralelos.

Además de permitir el procesamiento en paralelo, STATICA también utiliza resultados precalculados para reducir el cálculo. “Entonces, si no hay giro de giro, no hay nada que calcular”, dice Motomura. “Y si la influencia de un giro invertido ya se ha calculado, ese resultado se reutiliza”.

Como prueba de concepto, los investigadores tenían un chip STATICA de 3 por 4 mm fabricado utilizando un proceso CMOS de 65 nm que funciona a una frecuencia de 320 megahercios y funciona con 649 milivatios. La memoria comprende una SRAM de 1.3 megabits. Esto permitió probar un modelo Ising de 512 giros, equivalente a 262,000 conexiones.

“Es posible escalar al menos dos órdenes de magnitud”, señala Motomura. Y el chip puede fabricarse utilizando el mismo proceso que los procesadores estándar y puede agregarse fácilmente a una PC como coprocesador, por ejemplo, o agregarse a su placa base.

“En el Conferencia ISSCC en febrero, donde presentamos un documento sobre STATICA, montamos el chip en una placa de circuito con una conexión USB “, dice,” y lo demostramos conectado a una computadora portátil como prueba de concepto “.

Para comparar el rendimiento de STATICA con las tecnologías de recocido existentes (utilizando los resultados dados en los artículos publicados), los investigadores emplearon un Prueba de referencia de Maxcut de 2,000 conexiones. STATICA ocupó el primer lugar en velocidad de procesamiento, precisión y eficiencia energética. En comparación con su competidor más cercano, el Algoritmo de Bifurcación Simulada de Toshiba, STATICA tardó 0,13 milisegundos para completar la prueba, frente a 0,5 ms para SBA. En eficiencia energética, STATICA funcionó con una potencia estimada de 2 vatios, muy por debajo de los 40 vatios para SBA. Y en las comparaciones de precisión del histograma, STATICA también salió adelante, según Motomura.

Para el siguiente paso, dice que el equipo escalará el procesador y lo probará usando problemas realistas.

Aparte de eso, no hay más obstáculos tecnológicos que superar.

“STATICA está lista”, afirma Motomura. “La única pregunta es si existe suficiente demanda en el mercado para un procesador de recocido de este tipo. Esperamos ver interés, por ejemplo, de compañías de viajes compartidos como Uber y distribuidores de productos como Amazon. Los gobiernos locales que desean controlar problemas como la congestión del tráfico también podrían estar interesados. Estos son solo algunos ejemplos de cómo se puede usar STATICA además de aplicaciones más obvias como la optimización de la cartera y el descubrimiento de fármacos “.

El nuevo procesador de recocido es el mejor en la resolución de problemas de optimización combinatoria

Recent Articles

Hashtag Trending: otro 1 a 1 con Gates; DuckDuckGo está creciendo; Grupo de derechos civiles llama a Facebook

Bloomberg se enfrenta cara a cara con Bill Gates, DuckDuckGo está ganando impulso y un grupo de derechos civiles llama a Facebook.Son todas las...

Fornite: Save The World extraído de Mac

La última víctima en la disputa legal de Apple y Epic Games es Fortnite: salvar el mundo. No, no es la batalla real que...

6 cosas a considerar al comprar en línea en el Reino Unido – Guía 2020

img fuente: freepik.com Si hablamos de las tendencias que han conquistado el mundo, pero también el Reino Unido, en los últimos años y cuya expansión...

Related Stories

DEJA UNA RESPUESTA

Por favor ingrese su comentario!
Por favor ingrese su nombre aquí