64807d68d425bdd22cc43233 Copy Of Alphadev 01 06 Crops Crop5 0114 1.png

Nuevos algoritmos transformarán las bases de la informática

La sociedad digital está impulsando una creciente demanda de informática y uso de energía. Durante las últimas cinco décadas, hemos dependido de las mejoras en el hardware para mantener el ritmo. Pero a medida que los microchips se acercan a sus límites físicos, es fundamental mejorar el código que se ejecuta en ellos para hacer que la informática sea más potente y sostenible. Esto es especialmente importante para los algoritmos que componen el código que se ejecuta billones de veces al día.

En nuestro artículo publicado hoy en Naturalezapresentamos AlphaDev, un sistema de inteligencia artificial (IA) que utiliza el aprendizaje por refuerzo para descubrir algoritmos informáticos mejorados, superando a los perfeccionados por científicos e ingenieros durante décadas.

AlphaDev descubrió un algoritmo de clasificación más rápido, un método para ordenar datos. Miles de millones de personas utilizan estos algoritmos todos los días sin darse cuenta. Respaldan todo, desde clasificar los resultados de búsqueda en línea y las publicaciones sociales hasta cómo se procesan los datos en computadoras y teléfonos. Generar mejores algoritmos utilizando IA transformará la forma en que programamos las computadoras e impactará todos los aspectos de nuestra sociedad cada vez más digital.

Al abrir el código fuente de nuestros nuevos algoritmos de clasificación en la biblioteca principal de C++, millones de desarrolladores y empresas de todo el mundo lo utilizan ahora en aplicaciones de IA en todas las industrias, desde la computación en la nube y las compras en línea hasta la gestión de la cadena de suministro. Este es el primer cambio en esta parte de la biblioteca de clasificación en más de una década y la primera vez que se agrega a esta biblioteca un algoritmo diseñado mediante aprendizaje por refuerzo. Vemos esto como un paso importante en el uso de la IA para optimizar el código mundial, un algoritmo a la vez.

¿Qué es ordenar?

La clasificación es un método para organizar una serie de elementos en un orden particular. Los ejemplos incluyen alfabetizar tres letras, ordenar cinco números de mayor a menor u ordenar una base de datos de millones de registros.

Este método ha evolucionado a lo largo de la historia. Uno de los primeros ejemplos se remonta a los siglos II y III, cuando los eruditos alfabetizaron a mano miles de libros en los estantes de la Gran Biblioteca de Alejandría. Después de la revolución industrial, se inventaron máquinas que podían ayudar a clasificar: las máquinas de tabulación almacenaban información en tarjetas perforadas que se utilizaron para recopilar los resultados del censo de 1890 en los Estados Unidos.

Y con el auge de las computadoras comerciales en la década de 1950, vimos el desarrollo de los primeros algoritmos informáticos para la clasificación. Hoy en día, existen muchas técnicas y algoritmos de clasificación diferentes que se utilizan en bases de código de todo el mundo para organizar cantidades masivas de datos en línea.

Ilustración de lo que hace un algoritmo de clasificación. Se ingresa una serie de números sin clasificar en el algoritmo y se generan números ordenados.

Los algoritmos contemporáneos tardaron décadas de investigación en informáticos y programadores. Son tan eficientes que realizar mejoras adicionales es un desafío importante, similar a tratar de encontrar una nueva forma de ahorrar electricidad o un enfoque matemático más eficiente. Estos algoritmos también son una piedra angular de la informática y se enseñan en clases de introducción a la informática en las universidades.

Buscando nuevos algoritmos

AlphaDev descubrió algoritmos más rápidos comenzando desde cero en lugar de refinar los algoritmos existentes, y comenzó a buscar donde la mayoría de los humanos no lo hacen: las instrucciones de ensamblaje de la computadora.

Las instrucciones de ensamblaje se utilizan para crear código binario para que las computadoras lo pongan en acción. Si bien los desarrolladores escriben en lenguajes de codificación como C++, conocidos como lenguajes de alto nivel, esto debe traducirse a instrucciones ensambladoras de «bajo nivel» para que las computadoras las entiendan.

Creemos que existen muchas mejoras en este nivel inferior que pueden ser difíciles de descubrir en un lenguaje de codificación de nivel superior. El almacenamiento y las operaciones de la computadora son más flexibles en este nivel, lo que significa que hay muchas más mejoras potenciales que podrían tener un mayor impacto en la velocidad y el uso de energía.

El código suele escribirse en un lenguaje de programación de alto nivel como C++. Luego, esto se traduce a instrucciones de CPU de bajo nivel, llamadas instrucciones de ensamblaje, utilizando un compilador. Luego, un ensamblador convierte las instrucciones ensambladoras en código de máquina ejecutable que la computadora puede ejecutar.
Figura A: Un algoritmo de C++ de ejemplo que ordena hasta dos elementos.
Figura B: La representación ensambladora correspondiente del código.

Encontrar los mejores algoritmos con un juego

AlphaDev se basa en alfacero, nuestro modelo de aprendizaje por refuerzo que derrotó a campeones mundiales en juegos como Go, ajedrez y shogi. Con AlphaDev, mostramos cómo este modelo puede transferirse de juegos a desafíos científicos y de simulaciones a aplicaciones del mundo real.

Para entrenar a AlphaDev para que descubra nuevos algoritmos, transformamos la clasificación en un «juego de ensamblaje» para un solo jugador. En cada turno, AlphaDev observa el algoritmo que ha generado y la información contenida en la unidad central de procesamiento (CPU). Luego realiza un movimiento eligiendo una instrucción para agregar al algoritmo.

El juego de ensamblaje es increíblemente difícil porque AlphaDev tiene que buscar de manera eficiente entre una enorme cantidad de combinaciones posibles de instrucciones para encontrar un algoritmo que pueda ordenar y que sea más rápido que el mejor actual. El número de combinaciones posibles de instrucciones es similar al número de partículas en el universo o al número de combinaciones posibles de movimientos en una partida de ajedrez (10120 juegos) y Go (10700 juegos). Y un solo movimiento en falso puede invalidar todo el algoritmo.

Figura A: El juego de montaje. El jugador, AlphaDev, recibe el estado del sistema st como entrada y realiza un movimiento seleccionando una instrucción de ensamblaje para agregar al algoritmo que se ha generado hasta el momento.
Figura B: El cálculo de la recompensa. Después de cada movimiento, el algoritmo generado recibe secuencias de entrada de prueba; para sort3, esto corresponde a todas las combinaciones de secuencias de tres elementos. Luego, el algoritmo genera una salida, que se compara con la salida esperada de las secuencias ordenadas para el caso de clasificación. El agente es recompensado en función de la corrección y latencia del algoritmo.

A medida que se construye el algoritmo, una instrucción a la vez, AlphaDev verifica que sea correcta comparando la salida del algoritmo con los resultados esperados. Para los algoritmos de clasificación, esto significa que entran números desordenados y salen números ordenados correctamente. Recompensamos a AlphaDev tanto por ordenar los números correctamente como por la rapidez y eficiencia con la que lo hace. AlphaDev gana la partida al descubrir un programa correcto y más rápido.

Descubriendo algoritmos de clasificación más rápidos

AlphaDev descubrió nuevos algoritmos de clasificación que llevaron a mejoras en la biblioteca de clasificación LLVM libc++ que eran hasta un 70% más rápidos para secuencias más cortas y aproximadamente un 1,7% más rápido para secuencias que superaban los 250.000 elementos.

Nos centramos en mejorar los algoritmos de clasificación para secuencias más cortas de tres a cinco elementos. Estos algoritmos se encuentran entre los más utilizados porque a menudo se les llama muchas veces como parte de funciones de clasificación más grandes. La mejora de estos algoritmos puede acelerar la clasificación de cualquier cantidad de elementos.

Para que el nuevo algoritmo de clasificación sea más utilizable para las personas, realizamos ingeniería inversa en los algoritmos y los tradujimos a C++, uno de los lenguajes de codificación más populares que utilizan los desarrolladores. Estos algoritmos ahora están disponibles en el Biblioteca de clasificación estándar LLVM libc++utilizado por millones de desarrolladores y empresas de todo el mundo.

Encontrar enfoques novedosos

AlphaDev no sólo encontró algoritmos más rápidos, sino que también descubrió enfoques novedosos. Sus algoritmos de clasificación contienen nuevas secuencias de instrucciones que guardan una única instrucción cada vez que se aplican. Esto puede tener un impacto enorme ya que estos algoritmos se utilizan billones de veces al día.

A estos los llamamos ‘movimientos de intercambio y copia de AlphaDev’. Este novedoso enfoque recuerda al ‘movimiento 37’ de AlphaGo, una jugada contraintuitiva que sorprendió a los espectadores y condujo a la derrota de un legendario jugador de Go. Con el movimiento de intercambio y copia, AlphaDev se salta un paso para conectar elementos de una manera que parece un error pero que en realidad es un atajo. Esto muestra la capacidad de AlphaDev para descubrir soluciones originales y desafía la forma en que pensamos sobre cómo mejorar los algoritmos informáticos.

Izquierda: La implementación original con min(A,B,C).
Bien: AlphaDev Swap Move: AlphaDev descubre que solo necesitas min(A,B).
Izquierda: La implementación original con max (B, min (A, C, D)) se utiliza en un algoritmo de clasificación más grande para ordenar ocho elementos.
Bien: AlphaDev descubrió que solo se necesita max (B, min (A, C)) cuando se usa su movimiento de copia.

De la clasificación al hashing en estructuras de datos

Después de descubrir algoritmos de clasificación más rápidos, probamos si AlphaDev podía generalizar y mejorar un algoritmo informático diferente: el hash.

Hashing es un algoritmo fundamental en informática que se utiliza para recuperar, almacenar y comprimir datos. Al igual que un bibliotecario que utiliza un sistema de clasificación para localizar un determinado libro, los algoritmos hash ayudan a los usuarios a saber qué están buscando y exactamente dónde encontrarlo. Estos algoritmos toman datos para una clave específica (por ejemplo, el nombre de usuario «Jane Doe») y los codifican, un proceso en el que los datos sin procesar se convierten en una cadena única de caracteres (por ejemplo, 1234ghfty). La computadora utiliza este hash para recuperar los datos relacionados con la clave rápidamente en lugar de buscar todos los datos.

Aplicamos AlphaDev a uno de los algoritmos más utilizados para hash en estructuras de datos para intentar descubrir un algoritmo más rápido. Y cuando lo aplicamos al rango de 9 a 16 bytes de la función hash, el algoritmo que descubrió AlphaDev fue un 30% más rápido.

Este año, el nuevo algoritmo hash de AlphaDev se lanzó en código abierto. biblioteca de rappeldisponible para millones de desarrolladores en todo el mundo, y estimamos que ahora se utiliza billones de veces al día.

Optimizando el código del mundo, un algoritmo a la vez

Al optimizar y lanzar algoritmos mejorados de clasificación y hash utilizados por desarrolladores de todo el mundo, AlphaDev ha demostrado su capacidad para generalizar y descubrir nuevos algoritmos con impacto en el mundo real. Vemos a AlphaDev como un paso hacia el desarrollo de herramientas de inteligencia artificial de uso general que podrían ayudar a optimizar todo el ecosistema informático y resolver otros problemas que beneficiarán a la sociedad.

Si bien la optimización en el espacio de las instrucciones ensambladoras de bajo nivel es muy poderosa, existen limitaciones a medida que el algoritmo crece y actualmente estamos explorando la capacidad de AlphaDev para optimizar algoritmos directamente en lenguajes de alto nivel como C++, que sería más útil para los desarrolladores.

Los descubrimientos de AlphaDev, como los movimientos de intercambio y copia, no sólo muestran que puede mejorar los algoritmos sino también encontrar nuevas soluciones. Esperamos que estos descubrimientos inspiren a investigadores y desarrolladores a crear técnicas y enfoques que puedan optimizar aún más los algoritmos fundamentales para crear un ecosistema informático más potente y sostenible.

Obtenga más información sobre cómo optimizar el ecosistema informático: