Algoritmos de clasificación más rápidos descubiertos mediante el aprendizaje de refuerzo profundo | Grupo de módulos de cámara USB de Shenzhen

Nature, volumen 618, páginas 257–263 (2023)Citar este artículo

88k Accesos

794 Altmetric

Detalles de métricas

Los algoritmos fundamentales, como la clasificación o el hashing, se utilizan billones de veces en un día determinado1. A medida que crece la demanda de computación, se ha vuelto fundamental que estos algoritmos tengan el mayor rendimiento posible. Mientras que en el pasado se ha logrado un progreso notable2, realizar mejoras adicionales en la eficiencia de estas rutinas ha demostrado ser un desafío tanto para los científicos humanos como para los enfoques computacionales. Aquí mostramos cómo la inteligencia artificial puede ir más allá del estado actual del arte al descubrir rutinas hasta ahora desconocidas. Para realizar esto, formulamos la tarea de encontrar una mejor rutina de clasificación como un juego para un solo jugador. Luego entrenamos a un nuevo agente de aprendizaje de refuerzo profundo, AlphaDev, para jugar este juego. AlphaDev descubrió pequeños algoritmos de clasificación desde cero que superaron los puntos de referencia humanos conocidos anteriormente. Estos algoritmos se han integrado en la biblioteca de clasificación C++ estándar de LLVM3. Este cambio en esta parte de la biblioteca de clasificación representa el reemplazo de un componente con un algoritmo que se ha descubierto automáticamente mediante el aprendizaje por refuerzo. También presentamos resultados en dominios adicionales, mostrando la generalidad del enfoque.

La intuición y el conocimiento humano han sido cruciales para mejorar los algoritmos. Sin embargo, muchos algoritmos han llegado a una etapa en la que los expertos humanos no han podido optimizarlos más, lo que genera un cuello de botella computacional cada vez mayor. El trabajo en la literatura clásica de síntesis de programas, que abarca muchas décadas, tiene como objetivo generar programas correctos y/u optimizar programas utilizando proxies para la latencia. Estos incluyen técnicas de búsqueda enumerativa4,5,6,7 y búsqueda estocástica5,6,8,9,10, así como la tendencia más reciente de utilizar el aprendizaje profundo en la síntesis de programas para generar programas correctos11,12,13,14,15,16 . Usando el aprendizaje de refuerzo profundo (DRL), podemos llevar esto un paso más allá al generar algoritmos correctos y de alto rendimiento al optimizar la latencia real medida en el nivel de instrucción de la CPU, al buscar y considerar de manera más eficiente el espacio de programas correctos y rápidos en comparación con el trabajo anterior. .

Una de las cuestiones fundamentales en informática es cómo ordenar una secuencia17,18,19,20. Esto se enseña en clases elementales de ciencias de la computación en todo el mundo21,22 y se usa de manera ubicua en una amplia gama de aplicaciones23,24,25. Décadas de investigación informática se han centrado en descubrir y optimizar algoritmos de clasificación26,27,28. Un componente clave de las soluciones prácticas es una clasificación pequeña sobre una secuencia corta de elementos; este algoritmo se llama repetidamente cuando se clasifican matrices grandes que utilizan enfoques de divide y vencerás29. En este trabajo, nos enfocamos en dos tipos de algoritmos de clasificación pequeña: (1) la clasificación fija y (2) la clasificación variable. Los algoritmos de clasificación fija clasifican secuencias de una longitud fija (por ejemplo, la clasificación 3 solo puede clasificar secuencias de longitud 3), mientras que los algoritmos de clasificación variable pueden clasificar una secuencia de tamaño variable (por ejemplo, la clasificación variable 5 puede clasificar secuencias que van de uno a cinco). elementos).

Formulamos el problema de descubrir nuevos algoritmos de clasificación eficientes como un juego para un solo jugador al que nos referimos como AssemblyGame. En este juego, el jugador selecciona una serie de instrucciones de CPU de bajo nivel, a las que nos referimos como instrucciones de ensamblaje30, para combinarlas y producir un algoritmo de clasificación nuevo y eficiente. Esto es un desafío ya que el jugador debe considerar el espacio combinatorio de las instrucciones de ensamblaje para producir un algoritmo que sea comprobablemente correcto y rápido. La dificultad de AssemblyGame surge no solo del tamaño del espacio de búsqueda, que es similar a juegos extremadamente desafiantes como el ajedrez (10120 juegos)31 y Go (10700 juegos)32, sino también de la naturaleza de la función de recompensa. Una sola instrucción incorrecta en el juego de ensamblaje puede potencialmente invalidar todo el algoritmo, lo que hace que la exploración en este espacio de juegos sea increíblemente desafiante.

Para jugar, presentamos AlphaDev, un agente de aprendizaje que está capacitado para buscar algoritmos correctos y eficientes. Este agente se compone de dos componentes principales, a saber (1) un algoritmo de aprendizaje y (2) una función de representación. El algoritmo de aprendizaje AlphaDev puede incorporar tanto DRL como algoritmos de optimización de búsqueda estocástica para jugar a AssemblyGame. El algoritmo de aprendizaje principal en AlphaDev es una extensión de AlphaZero33, un conocido algoritmo DRL, en el que se entrena una red neuronal para guiar una búsqueda para resolver AssemblyGame. La función de representación es intercambiable y captura la estructura subyacente de los programas de ensamblaje. La representación principal de AlphaDev se basa en Transformers34.

Usando AlphaDev, hemos descubierto algoritmos de clasificación fijos y variables desde cero que son nuevos y más eficientes que los puntos de referencia humanos de última generación. Las soluciones de clasificación fija para clasificación 3, clasificación 4 y clasificación 5 descubiertas por AlphaDev se han integrado en la función de clasificación estándar en la biblioteca C++ estándar LLVM3. Esta biblioteca es utilizada por varios millones de usuarios, incluidas universidades y numerosas empresas internacionales35. Además, analizamos los descubrimientos de nuevos algoritmos, comparamos AlphaDev con enfoques de optimización de búsqueda estocástica y aplicamos AlphaDev a otros dominios para mostrar la generalidad del enfoque.

Al compilar algoritmos para código de máquina desde un lenguaje de alto nivel como C++ (por ejemplo, la función de clasificación en la Fig. 1a), el algoritmo se compila primero en ensamblador (Fig. 1b). El ensamblador luego convierte el programa ensamblador en un código de máquina ejecutable. En este trabajo, optimizamos algoritmos a nivel de ensamblaje30. En un programa ensamblador típico, los valores se copian de la memoria a los registros, se manipulan entre registros y luego se vuelven a escribir en la memoria. El conjunto de instrucciones de ensamblaje admitidas depende de la arquitectura del procesador. A los efectos de este trabajo, nos centramos en un subconjunto de instrucciones de ensamblaje compatibles con la arquitectura del procesador x86 que utiliza la sintaxis de AT&T36. Cada instrucción tiene el formato Opcode⟨OperandA, OperandB⟩. Una instrucción de ejemplo es mov, que se define como mover un valor desde el origen (A) al destino (B). Más definiciones de instrucciones como comparar (cmp), movimiento condicional (cmovX) y salto (jX) se pueden encontrar en la Tabla de datos ampliados 1. En el ejemplo de la Fig. 1b, %eax, %ecx, %edx, %edi corresponden a cuatro ubicaciones de registro diferentes y (%rsi), 4(%rsi) corresponden a dos ubicaciones de memoria diferentes. El símbolo $2 es un marcador de posición para un valor constante, que corresponde a la longitud del vector en este ejemplo. Usamos los términos programa ensamblador y algoritmo ensamblador indistintamente en este trabajo. Esto se debe a que AlphaDev crea un programa ensamblador desde cero, a partir de un conjunto de instrucciones inicialmente desordenadas, cada vez que juega AssemblyGame, definiendo un algoritmo nuevo y eficiente.

a, Una implementación en C++ de una función de clasificación variable 2 que clasifica cualquier secuencia de entrada de hasta dos elementos. b, la implementación de C++ en a se compila en esta representación de ensamblaje de bajo nivel equivalente.

En esta sección, formulamos algoritmos de optimización en el nivel de instrucción de la CPU como un problema de aprendizaje por refuerzo (RL)37, en el que el entorno se modela como un juego para un solo jugador al que nos referimos como AssemblyGame. Cada estado en este juego se define como un vector St = ⟨Pt, Zt⟩ donde Pt es una representación del algoritmo generado hasta el momento en el juego y Zt representa el estado de la memoria y los registros después de ejecutar el algoritmo actual en un conjunto de valores predefinidos. entradas. Como se ve en la Fig. 2a, en el paso de tiempo t, el jugador recibe el estado actual St y ejecuta una acción en. Esto implica agregar una instrucción de ensamblaje legal (por ejemplo, mov) al algoritmo actual generado hasta el momento. Se recibe una recompensa que comprende tanto una medida de la corrección del algoritmo como de la latencia. La corrección del algoritmo (Fig. 2b) implica ingresar un conjunto de N secuencias de prueba en el algoritmo actual Pt para generar N salidas. Estas salidas se comparan luego con las salidas esperadas y se calcula una recompensa de corrección rt. Las recompensas por latencia pueden generarse (1) penalizando al agente por aumentar la longitud del algoritmo (cuando la longitud y la latencia están altamente correlacionadas) a lo que nos referimos como recompensa por la longitud del algoritmo, o (2) midiendo la latencia real del algoritmo. . El juego se ejecuta durante un número limitado de pasos, después de lo cual finaliza el juego. Ganar el juego corresponde a generar un algoritmo correcto y de baja latencia utilizando instrucciones de ensamblaje. Perder el juego corresponde a generar un algoritmo incorrecto o un algoritmo correcto pero ineficiente.

a, El juego de ensamblaje lo juega AlphaDev, que recibe como entrada el algoritmo de ensamblaje actual generado hasta el momento St y juega el juego seleccionando una acción para ejecutar. En este ejemplo, la acción es una instrucción de ensamblado mov, que se agrega al algoritmo actual. El agente recibe una recompensa que es función de la corrección del algoritmo, discutida en b, así como de la latencia del algoritmo. El juego lo gana el jugador que descubre un algoritmo correcto de baja latencia. b, los cálculos de latencia y corrección del programa se utilizan para calcular la recompensa rt. En este ejemplo, las secuencias de prueba se ingresan al algoritmo; por ejemplo, en el caso de ordenar tres elementos, las entradas de prueba comprenden todas las secuencias de elementos no ordenados de longitud 3. Para cada secuencia, la salida del algoritmo se compara con la salida esperada (en el caso de la ordenación, la salida esperada son los elementos ordenados ). En este ejemplo, la salida ${\bf{D}}{\boldsymbol{{\prime} }}$ no coincide con la salida esperada ${\bf{B}}{\boldsymbol{{\prime} }}$ y, por lo tanto, el algoritmo es incorrecto.

Nos referimos al agente que juega este juego para un solo jugador como AlphaDev. El algoritmo de aprendizaje principal del agente es una extensión del agente AlphaZero32 y guía un procedimiento de planificación de búsqueda de árbol de Monte Carlo (MCTS) utilizando una red neuronal profunda33,38. La entrada a la red neuronal es el estado St y la salida es una predicción de política y valor. La predicción de política es una distribución sobre acciones y la función de valor es una predicción de los rendimientos acumulativos R que el agente debería esperar recibir del estado actual St. Durante un juego, el agente recibe como entrada el estado actual St. El agente entonces ejecuta un procedimiento MCTS y lo utiliza para seleccionar la siguiente acción a realizar. Los juegos generados luego se usan para actualizar los parámetros de la red, lo que permite que el agente aprenda.

Es fundamental que AlphaDev tenga una representación39,40 capaz de representar estructuras algorítmicas complejas para explorar eficientemente el espacio de las instrucciones. Para lograr esto, presentamos la red de representación AlphaDev (Datos extendidos Fig. 1a). Esta red consta de dos componentes, a saber (1) una red de codificador de transformador que proporciona al agente una representación de la estructura del algoritmo y (2) la red de codificador de estado de la CPU que ayuda al agente a predecir cómo el algoritmo afecta la dinámica de la memoria y los registros. . La red del codificador de estado de la CPU comprende un perceptrón multicapa que recibe como entrada el estado de cada registro y ubicación de memoria para un conjunto dado de entradas. Cada una de estas redes genera incrustaciones que se combinan para producir la representación del estado AlphaDev.

Los transformadores son codificadores de texto natural y recientemente han tenido mucho éxito con los modelos de lenguaje14,34,41. Como tal, esto nos motivó a adaptar el transformador estándar a las instrucciones de montaje del modelo. Desarrollamos e incorporamos un codificador transformador, nuestra adaptación del codificador transformador MultiQuery42, en la red de representación AlphaDev para representar las instrucciones de ensamblaje. El código de operación de cada instrucción de ensamblaje y los operandos correspondientes se convierten en codificaciones one-hot y se concatenan para formar la secuencia de entrada sin formato. Esto se alimenta a través de un codificador de transformador multicapa, que lo asigna a los vectores de incrustación correspondientes (consulte la Fig. 1b de datos extendidos para ver una ilustración).

La latencia es una señal de recompensa importante que se utiliza para guiar al agente en el descubrimiento de algoritmos de rendimiento. Para estimar mejor la latencia, implementamos una configuración de función de valor dual, mediante la cual AlphaDev tiene dos cabezales de función de valor: uno que predice la corrección del algoritmo y el segundo que predice la latencia del algoritmo. El cabezal de latencia se usa para predecir directamente la latencia de un programa determinado mediante el uso de la latencia calculada real del programa como un objetivo de Monte Carlo para AlphaDev durante el entrenamiento. Este enfoque de cabezal doble logró resultados sustancialmente mejores que la configuración estándar de la función de valor de cabezal único al optimizar la latencia real.

Capacitamos al agente AlphaDev desde cero para generar una variedad de algoritmos de ordenación fija y variable que son correctos y logran una latencia más baja que los puntos de referencia humanos de última generación.

Consideramos tres algoritmos fundamentales: sort 3, sort 4 y sort 5. Los puntos de referencia humanos de última generación para estos algoritmos son redes de clasificación43, ya que generan código ensamblador sin ramificaciones condicional y eficiente. Esto significa que todas las instrucciones se ejecutan secuencialmente y no hay bifurcaciones involucradas. Mejorar estos algoritmos es un desafío, ya que ya están altamente optimizados. Como se ve en la Tabla 1a, AlphaDev puede encontrar algoritmos con menos instrucciones que los puntos de referencia humanos para la clasificación 3 y la clasificación 5 y coincide con el rendimiento de última generación en la clasificación 4. Estos algoritmos más cortos conducen a una latencia más baja como la longitud del algoritmo y la latencia están correlacionadas para el caso sin ramificación condicional; consulte el Apéndice B en Información complementaria para obtener más detalles. También exploramos escalar a clasificaciones ligeramente más grandes usando una variante de AlphaDev. Logramos guardar tres instrucciones en la clasificación 6, dos instrucciones en la clasificación 7 y una instrucción en la clasificación 8, lo que brinda una base prometedora para el trabajo futuro. Consulte el Apéndice C en Información complementaria para obtener una descripción general del enfoque.

Consideramos tres algoritmos de clasificación de variables: VarSort3, VarSort4 y VarSort5. El punto de referencia humano en cada caso se define como un algoritmo que, para una longitud de entrada determinada, llama a la red de clasificación correspondiente. En este caso, se requiere ramificación, lo que aumenta considerablemente la complejidad del problema, ya que el agente necesita (1) determinar cuántos subalgoritmos necesita construir y (2) construir el cuerpo del algoritmo principal en paralelo. Es posible que el agente también necesite llamar subalgoritmos desde otros subalgoritmos. En este caso, la optimización de la longitud conduce a algoritmos significativamente más cortos en comparación con los puntos de referencia humanos, como se ve en la Tabla 1a. Sin embargo, debido a las complejidades introducidas por la ramificación, la latencia y la longitud no siempre están correlacionadas; consulte Información complementaria para obtener más detalles. Como tal, implementamos un procedimiento que mide la latencia real de los programas tomando el quinto percentil de las mediciones de latencia en 100 máquinas diferentes, con intervalos de confianza calculados44, y optimizamos esta métrica. Consulte Métodos para la configuración completa de evaluación comparativa. Al optimizar la latencia, el agente mejora significativamente los puntos de referencia humanos en cada caso, como se ve en la Tabla 1b.

Las soluciones descubiertas por AlphaDev incluyen descubrimientos algorítmicos nuevos y emocionantes que conducen a un rendimiento más eficiente. En la configuración de clasificación fija, descubrimos que AlphaDev descubrió dos secuencias interesantes de instrucciones que, cuando se aplican a un algoritmo de red de clasificación, reducen el algoritmo en una instrucción de ensamblaje cada vez. Nos referimos a cada secuencia de instrucciones como (1) el movimiento de intercambio de AlphaDev y (2) el movimiento de copia de AlphaDev, respectivamente.

La Figura 3a presenta una red de clasificación óptima para tres elementos (consulte Métodos para obtener una descripción general de las redes de clasificación). Explicaremos cómo AlphaDev ha mejorado el segmento de red en un círculo. Hay muchas variantes de esta estructura que se encuentran en redes de clasificación de varios tamaños, y el mismo argumento se aplica en cada caso. La parte rodeada por un círculo de la red (los dos últimos comparadores) se puede ver como una secuencia de instrucciones que toma una secuencia de entrada ⟨A, B, C⟩ y transforma cada entrada como se muestra en la Tabla 2a (izquierda). Sin embargo, un comparador en los cables B y C precede a este operador y, por lo tanto, las secuencias de entrada donde B ≤ C están garantizadas. Esto significa que es suficiente calcular min(A, B) como la primera salida en lugar de min(A, B, C) como se muestra en la Tabla 2a (derecha). La diferencia de pseudocódigo entre la Fig. 3b, c demuestra cómo el movimiento de intercambio de AlphaDev guarda una instrucción cada vez que se aplica.

a, Una red de clasificación clásica óptima para tres entradas. AlphaDev ha mejorado los comparadores marcados con un círculo. Consulte el movimiento de intercambio de AlphaDev para obtener más detalles. b,c, el pseudocódigo de ensamblaje antes de aplicar el movimiento de intercambio AlphaDev (b) y después de aplicar el movimiento de intercambio AlphaDev (c), lo que da como resultado la eliminación de una sola instrucción. d, Una configuración óptima de comparación de red de clasificación clásica que ha sido mejorada por AlphaDev. Consulte el movimiento de copia de AlphaDev para obtener más detalles. e,f, el pseudocódigo de ensamblaje antes de aplicar el movimiento de copia de AlphaDev (e) y después de aplicar el movimiento de copia de AlphaDev (f), lo que da como resultado la eliminación de una sola instrucción.

La figura 3d presenta una configuración de red de clasificación, que consta de tres comparadores, que se aplica a través de cuatro cables. Esta configuración se encuentra en una red de clasificación tipo 8 y corresponde a un operador que toma cuatro entradas ⟨A, B, C, D⟩ y las transforma en cuatro salidas como se ve en la Tabla 2b (a la izquierda). Se puede mostrar que como parte del género 8, la entrada que fluye hacia el operador satisface la siguiente desigualdad: ${\rm{D}}\ge \min ({\rm{A}},{\rm{C} })$. Esto significa que el operador se puede mejorar aplicando el movimiento de copia AlphaDev que se define en la Tabla 2b (a la derecha), lo que da como resultado una instrucción menos que el operador original. La diferencia de código entre el operador original y el código después de aplicar el movimiento de copia AlphaDev se visualiza en la Fig. 3e, f, respectivamente.

El algoritmo VarSort4 descubierto por AlphaDev es particularmente interesante. El diagrama de flujo para el algoritmo de referencia humano y AlphaDev se puede ver en la Fig. 4a, b, respectivamente. El algoritmo de referencia humano determina la longitud del vector de entrada y luego llama a la red de clasificación correspondiente para clasificar los elementos. La solución AlphaDev tiene un enfoque completamente diferente, como se ve en la Fig. 4b. Si la longitud del vector de entrada es estrictamente mayor que 2, se llama inmediatamente a sort 3, lo que da como resultado que se ordenen los tres primeros elementos. Si el vector tiene más de tres elementos, se llama a un algoritmo de clasificación 4 simplificado que clasifica los elementos restantes sin clasificar en el vector de entrada. Es esta parte simplificada de la rutina la que produce ganancias significativas en términos de longitud algorítmica y latencia.

a, Un diagrama de flujo del algoritmo de referencia humana de tipo variable 4 (VarSort4). En este algoritmo, se ingresa una secuencia de números desordenados en el algoritmo. Si la longitud de la secuencia es de cuatro, tres o dos números, entonces se llama a la red de clasificación de clasificación 4, clasificación 3 o clasificación 2 correspondiente que clasifica la secuencia resultante. Luego, el resultado es devuelto y emitido por la función. b, El algoritmo VarSort4 descubierto por AlphaDev. Este algoritmo también recibe secuencias de longitud de cuatro, tres o dos números como entrada. En este caso, si la longitud es dos, llama a la red de clasificación de clasificación 2 y regresa. Si la longitud es tres, llama a ordenar 3 para ordenar los primeros tres números y regresa. Sin embargo, si la longitud es mayor que tres, entonces llama a sort 3, seguido de una rutina de sort 4 simplificada que clasifica el número restante sin clasificar. Es esta parte de la rutina la que genera importantes ahorros de latencia.

Es importante comprender las ventajas y limitaciones de RL en comparación con otros enfoques para la optimización de programas. Como tal, implementamos un enfoque de superoptimización estocástica de última generación8, lo adaptamos a la configuración de clasificación y lo usamos como algoritmo de aprendizaje en AlphaDev. Nos referimos a esta variante como AlphaDev-S (consulte Métodos para obtener más detalles). Ejecutamos este algoritmo con al menos la misma cantidad de recursos y tiempo de reloj de pared que AlphaDev. AlphaDev-S requiere una cantidad de tiempo prohibitiva para optimizar directamente la latencia, ya que la latencia debe calcularse después de cada mutación. Como tal, AlphaDev-S optimiza para un proxy de latencia, es decir, la longitud del algoritmo y, luego, al final del entrenamiento, buscamos en todos los programas correctos generados por AlphaDev-S y comparamos cada uno para encontrar la solución de latencia más baja. En general, encontramos que AlphaDev supera constantemente a AlphaDev-S cuando se aprende desde cero sin conocimientos previos. Además, a medida que aumenta el tamaño del programa, AlphaDev explora órdenes de magnitud menos programas (12 millones de programas en el peor de los casos) en comparación con AlphaDev-S (31 billones de programas en el peor de los casos). Esto puede deberse a que AlphaDev es capaz de explorar mejor el espacio de los algoritmos en comparación con el procedimiento de búsqueda estocástica en amplitud que se atasca más fácilmente en los óptimos locales; consulte Métodos para obtener una descripción general de esta hipótesis de exploración. Además, AlphaDev nunca evalúa la latencia durante la búsqueda, ya que utiliza las predicciones de la función de valor de latencia y, debido a esto, solo necesita calcular la latencia real medida en menos del 0,002 % de los programas generados. Al incorporar conocimientos previos en AlphaDev-S, como comenzar en caliente el algoritmo de aprendizaje con una solución casi óptima, AlphaDev-S es computacionalmente más eficiente para tipo 3, tipo 4 y tipo 5 (algoritmos de ensamblaje sin ramificación) y también genera algoritmos de latencia al de AlphaDev en cada caso. Sin embargo, para los algoritmos que requieren bifurcación (sentencias if-else), en los que la longitud del algoritmo y la latencia no están bien correlacionadas, AlphaDev descubre soluciones de latencia más bajas que AlphaDev-S, incluso cuando se inicia este algoritmo en caliente con una solución casi óptima. Ver Métodos para un análisis en profundidad de estos algoritmos.

Para probar la generalidad de AlphaDev, entrenamos al agente en un conjunto de dominios adicionales. Estos incluyen una subrutina de deserialización de búfer de protocolo llamada VarInt, que se presenta a continuación, y un problema de codificación competitivo (consulte el Apéndice D en Información complementaria para obtener más detalles). El rendimiento de latencia del dominio de codificación competitivo se informa en la Tabla 1b.

Protocol Buffer es el formato de datos de código abierto de Google que se utiliza para serializar datos estructurados45. Este formato se usa comúnmente en casos en los que el rendimiento o la carga de la red son una preocupación principal. El algoritmo VarInt46 es un componente clave en los procesos de serialización y deserialización. Entrenamos al agente AlphaDev como en clasificación variable para optimizar la función de deserialización VarInt con respecto a la corrección y la latencia medida. Por corrección, recompensamos al agente por deserializar correctamente cada entrada. Usamos un conjunto de 80 entradas y salidas correspondientes que cubren casos de uso comunes de protobuf. AlphaDev aprende una función de deserialización VarInt optimizada y logra superar significativamente el punto de referencia humano para entradas de valor único. Nuestro agente descubre una solución sin sucursales que es más corta (Tabla 1a) y aproximadamente tres veces más rápida que el punto de referencia humano (Tabla 1b). Al hacerlo, el agente también descubrió un nuevo movimiento de asignación de VarInt en el que AlphaDev aprende a combinar dos operaciones en una sola instrucción que genera ahorros en la latencia. Consulte el Apéndice D.1 en Información complementaria para obtener una descripción general completa de este movimiento. Esta es una fuerte indicación de que AlphaDev es capaz de generalizar para optimizar algoritmos no triviales del mundo real.

Los algoritmos sort 3, sort 4 y sort 5 en la biblioteca de clasificación estándar LLVM libc++ son llamados muchas veces por algoritmos de clasificación más grandes y, por lo tanto, son componentes fundamentales de la biblioteca. Hicimos ingeniería inversa de los algoritmos de ordenación de ensamblados de bajo nivel descubiertos por AlphaDev para ordenación 3, ordenación 4 y ordenación 5 a C++ y descubrimos que nuestras implementaciones de ordenación condujeron a mejoras de hasta un 70 % para secuencias de una longitud de cinco y aproximadamente un 1,7 % para secuencias secuencias que superan los 250.000 elementos. Estas mejoras son para los tipos de datos uint32, uint64 y float para arquitecturas de CPU ARMv8, Intel Skylake y AMD Zen 2; consulte el Apéndice E en Información complementaria para ver las tablas de rendimiento completas. Las mejoras de rendimiento se deben tanto al ensamblado condicional sin ramas generado por AlphaDev como al nuevo movimiento de intercambio de AlphaDev. Para la ordenación 5, usamos un algoritmo de longitud 43 descubierto por AlphaDev, ya que condujo a una implementación de C++ más eficiente. Estos algoritmos se enviaron para su revisión y se incluyeron oficialmente en la biblioteca de clasificación estándar de libc++3. Es el primer cambio a estas subrutinas en más de una década. Esta es también la primera vez que un componente de esta biblioteca de clasificación ha sido reemplazado por un algoritmo que se ha descubierto automáticamente mediante el aprendizaje por refuerzo. Estimamos que estas rutinas se llaman billones de veces al día1,35,47.

AlphaDev descubre nuevos algoritmos de clasificación de última generación desde cero que se han incorporado a la biblioteca LLVM C++, utilizada por millones de desarrolladores y aplicaciones en todo el mundo23,24,25. Tanto AlphaDev como la búsqueda estocástica son algoritmos potentes. Una dirección interesante para futuras investigaciones es investigar la combinación de estos algoritmos para darse cuenta de las ventajas complementarias de ambos enfoques.

Es importante tener en cuenta que AlphaDev puede, en teoría, generalizar a funciones que no requieren una verificación exhaustiva de los casos de prueba. Por ejemplo, las funciones hash48 así como las funciones hashing criptográficas49 definen la corrección de la función por el número de colisiones hash. Por lo tanto, en este caso, AlphaDev puede optimizar para minimizar las colisiones y la latencia. AlphaDev también puede, en teoría, optimizar componentes lógicos complicados dentro del cuerpo de funciones grandes e impresionantes. Esperamos que AlphaDev pueda proporcionar información interesante e inspirar nuevos enfoques tanto en la inteligencia artificial como en las comunidades de síntesis de programas.

AlphaZero33 es un algoritmo RL que aprovecha MCTS como operador de mejora de políticas. Consiste en (1) una red de representación frep que genera una representación latente ht del estado St; y (2) una red de predicción fpred que predice el rendimiento esperado (el valor) ${\hat{v}}_{t}$ y una política (es decir, distribución sobre el espacio de acción) ${\hat {\pi }}_{t}$ de un estado latente dado. El algoritmo utiliza la verdadera dinámica y la recompensa al planificar. MuZero38 es una variante de AlphaZero basada en modelos que tiene las mismas redes de representación y predicción, pero también aprende un modelo de la dinámica y predice recompensas, que utiliza para la planificación. Específicamente, aprende una red dinámica fdyn que predice el siguiente estado latente ${{\bf{\text{h}}}}_{t}^{k+1}$ y recompensa ${\hat{r }}_{t}^{k+1}$ resultante de una transición. Tenga en cuenta que el subíndice t denota pasos de tiempo en el entorno real y el superíndice k representa pasos de tiempo en el modelo.

Al llegar a un nuevo estado, AlphaZero procede codificando primero el estado en una representación latente con la red de representación. Luego, la verdadera dinámica o red dinámica (para MuZero) así como la red de predicción fpred(ht) se utilizan para simular varias trayectorias que completan un árbol de búsqueda, mediante el muestreo de transiciones de estado. En cada nodo, las acciones se seleccionan utilizando una estrategia optimista llamada límite superior del árbol de confianza del predictor32, destinado a equilibrar la exploración (probar nuevas acciones) y la explotación (progresar hacia abajo en el subárbol de la estimación actual de la mejor acción). Esta estrategia comienza siguiendo de cerca la política pronosticada ${\hat{\pi }}_{t}$ y cambia gradualmente hacia la maximización de la función de valor pronosticado. En última instancia, se recomienda una acción mediante el muestreo del nodo raíz con una probabilidad proporcional a su recuento de visitas durante MCTS. Luego, la política predicha se entrena para que coincida con los recuentos de visitas de la política MCTS en un intento de destilar el procedimiento de búsqueda en una política tal que las iteraciones posteriores de MCTS ignoren los nodos que no sean prometedores.

Las redes de clasificación son muy eficientes ya que sus estructuras se pueden paralelizar en arquitecturas de CPU modernas. Por lo tanto, tienden a lograr un rendimiento de tiempo de ejecución más rápido, especialmente en clasificaciones pequeñas, en comparación con los algoritmos de caso base populares y eficientes, como la clasificación por inserción17,43,50. Una red de clasificación43 consta de dos tipos de elementos llamados comparadores (líneas verticales) y cables (líneas horizontales) (Datos ampliados Fig. 2a). Cada cable lleva un valor de izquierda a derecha. Cuando dos cables se cruzan en un comparador, se comparan los valores de los dos cables. Si el valor del cable inferior es menor que el valor del cable superior, entonces los valores se intercambian entre los cables como se ve en Datos extendidos Fig. 2b. Una implementación programática de una red de clasificación consiste en ejecutar estos intercambios en pares particulares de elementos de la secuencia de entrada en un orden particular.

Podamos el espacio de acción eliminando algunas invariancias del programa (por ejemplo, el orden de asignación de registros) e instrucciones ilegales (por ejemplo, comparando dos ubicaciones de memoria). Esto ayuda a reducir el tamaño del espacio de acción y aumenta la tasa de convergencia. Para nuestros experimentos, usamos las siguientes reglas:

Las ubicaciones de memoria siempre se leen en orden incremental.

Los registros se asignan en orden incremental.

No podemos comparar o mover condicionalmente a una ubicación de memoria (ilegal).

Podemos leer y escribir en cada ubicación de memoria solo una vez.

No podemos utilizar registros no inicializados (ilegales).

No realice instrucciones de comparación consecutivas.

Entrenamos a AlphaDev en una unidad de procesamiento de tensor (TPU) v.3, con un tamaño de lote total de 1024 por núcleo de TPU. Usamos hasta 16 núcleos de TPU y entrenamos para 1 millón de iteraciones. En cuanto a los actores, los juegos se juegan en TPU independiente v.4 y usamos hasta 512 actores. En la práctica, en todas las tareas, el entrenamiento tarda, en el peor de los casos, 2 días en converger.

Es importante comprender las ventajas y limitaciones de RL en comparación con otros enfoques posibles para la optimización de programas. Como tal, implementamos un enfoque8 de superoptimización estocástica de última generación y lo incorporamos en AlphaDev como el algoritmo de aprendizaje para optimizar las funciones de clasificación. Nos referimos a esta versión adaptada como AlphaDev-S. Nuestra reimplementación se ha optimizado específicamente para el dominio de clasificación. Esto incluye implementar el algoritmo para que se ejecute con nuestro entorno de ensamblaje, definir una función de corrección y pérdida de rendimiento específica para clasificar y ejecutar barridos extensos de hiperparámetros para identificar la mejor variante. La función de costo utilizada para AlphaDev-S es c = corrección + α × rendimiento, donde la corrección corresponde al cálculo del número de elementos de secuencia de entrada incorrectos que aún no están ordenados, el rendimiento corresponde a la recompensa por la longitud del algoritmo y α es un peso que compensa los dos costos. funciones No podemos optimizar directamente la latencia, ya que esto ralentiza considerablemente el algoritmo de aprendizaje, lo que hace que el aprendizaje sea inviable. Cabe señalar que esta función se ha adaptado para admitir el mismo conjunto de instrucciones de ensamblaje que usa AlphaDev, así como para eliminar el mismo conjunto de acciones incorrectas o ilegales. También utiliza el mismo módulo de cálculo de corrección del programa (Fig. 2b) para calcular el término de corrección.

Luego, AlphaDev-S se ejecuta proponiendo primero una transformación al programa almacenado en el búfer (que puede estar vacío o inicializado con un programa ya ordenado). Los términos de corrección y rendimiento se calculan luego utilizando el módulo de corrección del programa y la longitud del algoritmo, respectivamente. Si el costo es inferior al mejor costo actual, el nuevo programa se acepta con alta probabilidad, de lo contrario se rechaza. Ahora discutiremos la función de costo de corrección y transformaremos los pesos con más detalle.

Para la función de costo de corrección, implementamos tres tipos de función de costo. El primero se define como el porcentaje de elementos colocados incorrectamente: $\frac{PP{C}_{t}}{P}$ donde P es el número total de elementos a colocar y PCt es el número de elementos colocados correctamente en el paso de tiempo t. La segunda variante es la raíz cuadrada de esta ecuación. La función de costo final toma la raíz cuadrada de la diferencia $\sqrt{-{PC}_{t}}$ y esto es lo que produjo el mejor rendimiento.

Habilitamos varias transformaciones de programas, como agregar una instrucción para aumentar el tamaño del programa (Agregar transformación), intercambiar dos instrucciones (Intercambiar transformación), cambiar aleatoriamente un código de operación por una instrucción (Transformar código de operación), muestrear aleatoriamente un operando para una instrucción elegida (Transformación de operando) y muestrear aleatoriamente un código de operación y sus operandos correspondientes (Transformación de instrucción). Es posible influir en el muestreo de estas transformadas para animar a que se muestreen algunas con mayor o menor frecuencia. Optimizamos los pesos para las transformaciones de muestreo mediante la ejecución de un extenso barrido de hiperparámetros.

Ahora presentamos un conjunto de estudios de investigación que ayudan a comprender mejor las ventajas y limitaciones del DRL y los algoritmos de aprendizaje de búsqueda estocástica utilizados en AlphaDev. Comparamos AlphaDev con AlphaDev-S. Implementamos dos variantes de AlphaDev-S: (1) Cold Start (AlphaDev-S-CS) y (2) Warm Start (AlphaDev-S-WS). AlphaDev-S-CS no utiliza información previa y tiene que generar un programa a partir de un búfer de programa vacío. El búfer de AlphaDev-S-WS se inicia en caliente con un programa de clasificación correcto (por ejemplo, un programa de ensamblaje de red de clasificación óptima) y edita el programa para optimizarlo aún más. Comparamos las variantes con AlphaDev en las configuraciones de algoritmo de clasificación individual y variable.

Debido a que AlphaDev siempre aprende desde cero sin conocimientos previos, la comparación directa sería con la versión de búsqueda estocástica de arranque en frío: AlphaDev-S-CS. Sin embargo, dado que a veces pueden estar disponibles programas iniciales casi óptimos, también comparamos AlphaDev con la versión de búsqueda estocástica de arranque en caliente: AlphaDev-S-WS.

Cabe señalar que las variantes de búsqueda estocástica no pueden optimizar directamente la latencia, ya que esto haría que el aprendizaje fuera inviable debido a la eficiencia computacional. Como tal, nuestras variantes AlphaDev-S optimizan la longitud del algoritmo. Luego, al final del entrenamiento, iteramos a través del conjunto de programas generados para AlphaDev-S a lo largo de distintas duraciones e identificamos el programa con la latencia más baja.

En cada caso, los algoritmos de búsqueda estocástica (AlphaDev-S) se ejecutan utilizando al menos los mismos recursos computacionales y el mismo tiempo de reloj que AlphaDev.

Primero examinamos el rendimiento de los diversos enfoques para los algoritmos de clasificación fija. En este caso, todas las variantes algorítmicas se optimizan para la longitud del algoritmo, ya que la longitud y la latencia del algoritmo están altamente correlacionadas en la configuración sin ramificación condicional (consulte la Información complementaria para obtener más detalles).

En la configuración de inicio en frío, AlphaDev-S-CS no puede encontrar los programas óptimos en cada caso, como se ve en la Tabla de datos extendidos 2a. Además, AlphaDev-S-CS explora órdenes de magnitud de más programas que AlphaDev, como se muestra en la Tabla de datos extendidos 2b. En la configuración de inicio en caliente, AlphaDev-S se inicia en caliente con un programa ordenado casi óptimo y es capaz de igualar el rendimiento de AlphaDev en cada caso, como se muestra en la Tabla de datos ampliados 2a. Es más eficiente desde el punto de vista computacional que AlphaDev, como se muestra en la Tabla de datos ampliados 2c, pero explora órdenes de magnitud de más programas para ordenar 3 y clasificar 5, como se muestra en la Tabla de datos ampliados 2b. Se puede argumentar que AlphaDev-S-WS tiene una ventaja sustancial en este escenario, ya que cuenta con un programa inicial casi óptimo. En la sección Ordenación de variables, mostraremos que cuando los algoritmos se vuelven más complicados y se introduce la bifurcación, no es suficiente comenzar en caliente el algoritmo de aprendizaje con un programa casi óptimo y puede provocar que se atasque en soluciones subóptimas.

También usamos un enfoque de fuerza bruta para demostrar que no existe ningún programa de menos de 17 instrucciones para el tipo 3. Tuvimos que enumerar aproximadamente 1032 programas e, incluso con la poda heurística, tomó más de 3 días probar esta hipótesis. Para el tipo 4 y superiores, este enfoque no es factible.

La longitud de un programa es solo un indicador del rendimiento de un algoritmo. A medida que introducimos estructuras de bifurcación, la duración y la latencia de un programa no están bien correlacionadas. Por lo tanto, ejecutamos los programas en máquinas reales y medimos su latencia. El microbenchmarking es un gran desafío dadas las numerosas fuentes de ruido que podrían afectar las mediciones. Esto es especialmente cierto cuando se ejecuta en máquinas compartidas donde podría haber interferencia de otros procesos. Nuestro enfoque es tener un servicio de evaluación comparativa independiente, replicado en máquinas separadas, de modo que podamos realizar rápidamente muchas mediciones en un entorno controlado en diferentes condiciones. El sistema funciona de la siguiente manera:

El agente RL procesa 1000 mediciones en las máquinas que utilizan el servicio replicado.

Para cada medición, el servicio ejecuta el algoritmo de clasificación dado en 10 000 entradas aleatorias (por ejemplo, para la clasificación 3, sería 3 × 10 000 = 30 000 números enteros aleatorios).

Medimos el tiempo necesario con un contador de rendimiento de la CPU (CPU_CLK_UNHALTED.CORE).

Luego, tomamos el quinto percentil como nuestra medida final, porque asumimos que la mayoría de las fuentes de ruido son unilaterales (por ejemplo, errores de caché, preferencia, etc.). Durante el entrenamiento, procesamos las mediciones en diez máquinas para obtener eficiencia computacional. Después de la capacitación, comparamos la solución de AlphaDev con las soluciones de referencia y procesamos las mediciones en 100 máquinas para lograr una mayor precisión y reducción del ruido. Para cada punto de referencia, calculamos los intervalos de confianza utilizando el intervalo de confianza bilateral sin distribución para un método tabular de cuantiles44.

Al optimizar directamente la latencia, AlphaDev supera a AlphaDev-S-WS en VarSort3, VarSort4 y VarSort5, como se ve en la tabla de datos ampliados 3a. AlphaDev-S-CS no logra encontrar una solución en cada caso. En los casos de VarSort4 y VarSort5, la duración del programa y la latencia no están correlacionadas (consulte la Información complementaria para obtener más detalles). Esto indica que cuando la duración del programa no se puede utilizar como indicador del rendimiento, AlphaDev puede encontrar soluciones de menor latencia en comparación con AlphaDev-S. Esto es incluso en el caso de que la búsqueda estocástica se inicie en caliente con un programa casi óptimo. Además, AlphaDev converge a la solución óptima después de explorar un máximo de 12 millones de programas, como se ve en la tabla de datos extendidos 3b. Esto es órdenes de magnitud inferior al de AlphaDev-S-CS y AlphaDev-S-WS, respectivamente (31 billones de programas en el peor de los casos).

Propusimos que AlphaDev-S lucha por descubrir programas cuando aprende desde cero y se atasca en los óptimos locales cuando se inicia en caliente debido a sus limitadas capacidades de exploración como resultado del procedimiento de búsqueda estocástica. Datos extendidos La Fig. 3 muestra proyecciones bidimensionales de incorporación de vecinos estocásticos t (t-SNE)51 de los algoritmos de ensamblaje de AlphaDev y AlphaDev-S descubiertos durante sus respectivos procedimientos de entrenamiento para VarSort5. Las funciones utilizadas en la proyección incluyen la corrección, la latencia, la longitud del algoritmo y un recuento de histograma de las instrucciones utilizadas por algoritmo. La Fig. 3a de datos extendidos indica las regiones en el espacio del algoritmo exploradas por AlphaDev, AlphaDev-S-CS y AlphaDev-S-WS, respectivamente, mientras que la Fig. 3b de datos extendidos superpone la corrección del algoritmo en cada punto en la proyección t-SNE en la que el el color indica la corrección de cada algoritmo descubierto, desde algoritmos incorrectos (púrpura) hasta algoritmos correctos (amarillo). Las variantes de AlphaDev-S cubren una región circular densamente empaquetada alrededor de su semilla inicial, lo que resalta la naturaleza de amplitud de su procedimiento de búsqueda estocástica. Esto ilustra que AlphaDev-S-CS no puede navegar por el espacio de los algoritmos incorrectos en un tiempo razonable y descubrir los algoritmos correctos cuando aprende desde cero. Un argumento similar se aplica a AlphaDev-S-WS por el cual, al optimizar a partir de una demostración experta ya correcta pero subóptima, el algoritmo está sesgado hacia la exploración de su vecindad y lucha por escapar de este máximo local. Por el contrario, AlphaDev tiene una cobertura de espacio de algoritmo más diversa, ya que la función de valor a largo plazo es una señal de guía para descubrir partes nuevas e interesantes del espacio de algoritmo. Como se ve en Extended Data Fig. 3b, es capaz de escapar del espacio de algoritmos incorrectos para descubrir un nuevo espacio de algoritmos correctos, destacando las ventajas de exploración que ofrece AlphaDev.

Existen numerosos enfoques para optimizar programas ensambladores, los cuales hemos clasificado en tres grupos: búsqueda enumerativa, búsqueda estocástica y búsqueda simbólica5.

En primer lugar, las técnicas de búsqueda enumerativa incluyen la enumeración de programas de fuerza bruta4,5,6, así como la enumeración implícita mediante la demostración de teoremas simbólicos52,53. Estos enfoques buscan a través del espacio de los programas para encontrar una solución basada en un conjunto predefinido de programas, funciones heurísticas y/o de costos. Estos enfoques luchan por abarcar grandes regiones del espacio del programa, especialmente a medida que aumenta el tamaño y la complejidad del programa.

En segundo lugar, las técnicas de búsqueda estocástica eluden la enumeración exhaustiva al depender de mecanismos de muestreo como el muestreo de Monte Carlo en cadena de Markov5,6,8,9. Rajeev Alur et al.5 definen una especificación de corrección, proporcionada por una fórmula lógica que utiliza símbolos de una teoría de fondo. El objetivo es encontrar una expresión de implementación tal que la fórmula lógica que define la especificación sea válida. La idea es agregar iterativamente casos de prueba y luego buscar y expandir el programa para resolver los casos de prueba dados. Optimizan para corregir problemas del libro Hacker's delight54. Phitchaya Mangpo Phothilimthana et al.6 presentan el algoritmo LENS que se basa en ejecutar búsquedas enumerativas, estocásticas y simbólicas en paralelo, mientras se basa en reglas de poda artesanales. Esta configuración es capaz de optimizar hasta 21 instrucciones y no puede optimizar la latencia ni admitir bifurcaciones. Otro algoritmo8 se basa en el muestreo de rechazo Monte Carlo de la cadena de Markov y aplica transformaciones a los programas en ensamblaje utilizando una función de pérdida que es una función de corrección y rendimiento. Muchos de estos enfoques son propensos a quedarse atascados en los mínimos locales y también pueden tener problemas a medida que aumenta el tamaño y/o la complejidad del programa. Además, la incorporación de la latencia real medida en estos enfoques es inviable o prohibitivamente costosa.

En tercer lugar, también se pueden implementar enfoques de búsqueda simbólica para optimizar los programas de ensamblaje. Estos incluyen solucionadores SAT55, solucionadores SMT5,6 y programas enteros mixtos (MIP)56,57. Sin embargo, estos enfoques adolecen de problemas de escala. Por ejemplo, los solucionadores clásicos requieren que un problema se traduzca a una determinada forma canónica. Por lo general, requiere un experto en dichos disolventes y una cantidad sustancial de tiempo para encontrar una formulación eficiente. Además, para cualquier nueva modificación del problema, esto debe repetirse. Los solucionadores clásicos también son difíciles de paralelizar y, por lo tanto, es un desafío aprovechar más hardware para acelerar el proceso de resolución. Otro algoritmo de búsqueda simbólica es Cholorphyll10 que implementa un enfoque de varias fases. Primero requiere como entrada un programa fuente con anotaciones de partición que especifiquen dónde residen el código y los datos. Luego, un sintetizador de diseño asigna fragmentos de programa a núcleos físicos para minimizar los costos computacionales. Luego, el código se separa en fragmentos de programa por núcleo y los fragmentos de programa se compilan en código de máquina. En este punto, un superoptimizador optimiza cada uno de estos fragmentos.

También se han aplicado varios enfoques58,59,60 a las funciones de clasificación que se ejecutan en la configuración de instrucción única, datos múltiples (SIMD)61. Esta configuración es capaz de paralelizar la ejecución de instrucciones, pero actualmente no es compatible con bibliotecas populares como la biblioteca libc++ std::sort de LLVM. Un ejemplo es el de Gilles Barthe et al.7 que propone una metodología para optimizar programas mediante la vectorización automática de bucles con instrucciones SIMD. Lo hacen introduciendo un marco para verificar la exactitud de las transformaciones en un programa y realizando un procedimiento basado en búsqueda utilizando dicha transformación. Su marco puede descubrir estructuras de bucle SIMD de hasta nueve instrucciones en 0,12 s, lo que corresponde a una aceleración mínima de 2x.

También hay varios estudios que utilizan RL para la optimización de programas. Kevin Ellis et al.62 aprenden una función de política y valor para escribir y evaluar código, además de realizar una estrategia de búsqueda estilo Monte Carlo durante la inferencia. Este trabajo requiere un paso de entrenamiento previo y tiene como objetivo generar programas correctos que satisfagan una especificación predefinida. El enfoque se aplica con éxito al diseño asistido por computadora y programas de edición de cadenas. SuperSonic63 usa un meta-optimizador de RL para seleccionar entre diferentes arquitecturas de RL, usando una búsqueda de políticas de bandidos de múltiples brazos para encontrar una representación de estado, una función de recompensa y un algoritmo de RL que sea óptimo para la tarea actual. Esto requiere realizar un seguimiento de muchos algoritmos y arquitecturas RL, que se utilizan como parte del espacio de estado. Por el contrario, nuestro enfoque solo se enfoca en entrenar una sola arquitectura RL, aprovechando la búsqueda MCTS y las poderosas representaciones de estado. Shypula et al.64 crean un conjunto de datos de ensamblaje supervisado y lo usan para entrenar un modelo de Transformador para mapear código no optimizado a optimizado, seguido de una etapa RL para mejorar la calidad de la solución. Nuestro método no requiere un conjunto de datos supervisado o dos etapas separadas de entrenamiento y ajuste, y optimiza todo de principio a fin usando RL y búsqueda en su lugar. Chen et al.65 definen su propio lenguaje específico de dominio y realizan una síntesis de programa de entrada-salida que utiliza mejor la representación del programa intermedio para guiar la rutina de síntesis. Muestran que esto se puede incorporar con RL, utilizando la configuración de Rudy Bunel et al.66 y mejorar la corrección de las funciones generadas. Sin embargo, no optimizan la duración del programa ni la latencia.

Una gran cantidad de trabajo aborda el problema de aprender programas a partir de pares de entrada-salida. Un tipo de enfoque aprende una red neuronal para hacer coincidir las entradas con las salidas directamente11,13,67,68. Este enfoque es difícil de integrar en las bibliotecas existentes y puede tener dificultades para generalizar a entradas nunca antes vistas, aunque ha habido algunos avances alentadores utilizando representaciones gráficas69. Otro tipo de enfoque es realizar una búsqueda en el espacio del programa, guiada por un modelo aprendido12,70,71,72. Por ejemplo, Chen et al.70 utilizan un modelo que predice el próximo token de programa sobre la base de un programa parcial y los pares de entrada-salida. Esto tiene algunas similitudes con la forma en que se guía la búsqueda en nuestro enfoque: la política aprendida antes en AlphaZero es un modelo para predecir el próximo token, aprendido sobre la base de una combinación de un programa parcial y los efectos de ese programa en las entradas. Sin embargo, estamos interesados en encontrar programas correctos y eficientes, lo que logramos mediante el aprendizaje adicional de una función de valor para aproximar la latencia esperada de programas parciales y el uso de AlphaZero para incorporar esta función de valor en el proceso de búsqueda.

También hay varios enfoques de aprendizaje profundo que usan modelos de lenguajes grandes para generar código. Estos enfoques varían en sus usos desde la transpilación, la refactorización de código y la explicación del código15 hasta la generación de código competitivo a nivel humano utilizando una descripción en lenguaje natural14. Ese trabajo en particular tiene como objetivo generar el código correcto, pero no se enfoca en generar soluciones de baja latencia.

Hay varios estudios de síntesis de programas que han abordado los algoritmos de clasificación. Por ejemplo, White et al.26 usan RL para aprender funciones de clasificación. Su trabajo utiliza varias heurísticas y un lenguaje específico de dominio para producir un algoritmo de clasificación llamado clasificación de programación de refuerzo. Srivastava et al.27 codifica la síntesis del programa como un problema de verificación. Específicamente, representan una tarea de síntesis como una tupla que consta de la expresión funcional, los dominios y guardias que aparecen en el programa sintetizado y las restricciones de recursos. La idea es que, dada una restricción de recursos preespecificada, su sintetizador produzca un programa que cumpla con la especificación predefinida para garantizar la corrección. Aplican esto para descubrir la ordenación por fusión y la ordenación rápida. Jason Ansel et al.28 toma como entrada algoritmos predefinidos (por ejemplo, ordenación por inserción, ordenación por fusión y ordenación rápida) y luego determina cuándo seleccionar estos algoritmos para su ejecución usando su función de sintonizador automático. Lo hace definiendo un lenguaje que contiene reglas y transformaciones que dictan cómo se seleccionan los algoritmos y dónde se ejecutan.

Los datos utilizados para entrenar el sistema se generaron sintéticamente de acuerdo con los procedimientos explicados en el documento. Los algoritmos descubiertos por AlphaDev para los operadores de copia e intercambio se presentan en el artículo principal. También lanzamos las implementaciones de ensamblaje AlphaDev descubiertas para los tipos 3–8, así como VarSort3, 4 y 5 en Github en https://github.com/deepmind/alphadev. Hemos incluido pruebas exhaustivas para asegurarnos de que cada implementación es correcta. Además, el Apéndice G en Información complementaria contiene una lista de algoritmos de clasificación correctos adicionales descubiertos por AlphaDev para clasificación 3, clasificación 4 y clasificación 5. tres arquitecturas de CPU diferentes, así como tipos de datos flotantes, int32 e int64 se detallan en el Apéndice E en la Información complementaria. Además, las implementaciones de clasificación 3, clasificación 4 y clasificación 5 de AlphaDev se pueden encontrar en la biblioteca de clasificación estándar LLVM libc++3.

También hemos lanzado un pseudocódigo en https://github.com/deepmind/alphadev que incluye el entorno, el actor completo y los bucles de entrenamiento, así como el algoritmo central de MCTS. Además, incluimos nuestra implementación JAX real de nuestras redes de política, valor y representación que permiten reproducir las arquitecturas. Finalmente, tenemos un archivo de configuración que contiene las definiciones de hiperparámetros que se utilizarán con el agente.

Amazonas. Amazon S3: dos billones de objetos, 1,1 millones de solicitudes por segundo. AWS https://aws.amazon.com/blogs/aws/amazon-s3-two-trillion-objects-11-million-requests-second/ (2013).

Cormen, TH et al. Introducción a los Algoritmos (MIT Press, 2022).

Gelmi, M. Introducir funciones de clasificación sin ramas para sort3, sort4 y sort5. LLVM.org https://reviews.llvm.org/D118029 (2022).

Bansal, S. & Aiken, A. Generación automática de superoptimizadores de mirilla. ACM SIGARCH Cómputo. Arco. Noticias 34, 394–403 (2006).

Alur, R. et al. Síntesis guiada por sintaxis (IEEE, 2013).

Phothilimthana, PM y col. Ampliación de la superoptimización. En Proc. XXI Conferencia Internacional sobre Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos 297–310 (ACM, 2016).

Barthe, G. et al. Desde la verificación relacional hasta la síntesis de bucles SIMD. En Proc. del 18º Simposio ACM SIGPLAN sobre Principios y Práctica de la Programación Paralela 123–134 (ACM, 2013).

Schkufza, E., Sharma, R. & Aiken, A. Superoptimización estocástica. ACM SIGPLAN Avisos 48, 305–315 (2013).

Bunel, R. et al. Aprender a superoptimizar programas. En Proc. Conferencia Internacional sobre Representaciones de Aprendizaje (ICLR, 2016).

Phothilimthana, PM y col. Clorofila: compilador asistido por síntesis para arquitecturas espaciales de bajo consumo. ACM SIGPLAN Avisos 49, 396–407 (2014).

Vinyals, O. et al. La gramática como lengua extranjera. Adv. Informe neuronal. proc. sist. 28, 2773–2781 (2015).

Chen, X., Liu, C. y Song, D. Hacia la síntesis de programas complejos a partir de ejemplos de entrada y salida. En Proc. Conferencia Internacional sobre Representaciones de Aprendizaje (ICLR, 2018).

Devlin, J. et al. Robustfill: aprendizaje de programas neuronales bajo E/S ruidosas. En Proc. Conferencia internacional sobre aprendizaje automático 990–998 (PMLR, 2017).

Li, Y. et al. Generación de código a nivel de competencia con AlphaCode. Ciencia 378, 1092–1097 (2022).

Pearce, H. et al. ¿Puede Codex y otros modelos de lenguaje extenso ayudarnos a corregir errores de seguridad? Preimpresión en https://arxiv.org/abs/2112.02125 (2021).

Chen, M. et al. Evaluación de grandes modelos de lenguaje entrenados en código. Preimpresión en https://arxiv.org/abs/2107.03374 (2021).

Bingmann, T., Marianczuk, J. & Sanders, P. Ingeniería de clasificadores más rápidos para conjuntos pequeños de artículos. Software: Práctico. Exp. 51, 965–1004 (2021).

Levcopoulos, C. & Petersson, O. Splitsort: un algoritmo de clasificación adaptativo. Informar. proc. Letón. 39, 205–211 (1991).

Helman, DR, Bader, DA & JáJá, J. Un algoritmo de clasificación paralelo aleatorio con un estudio experimental. J. Distribución Paralela. computar 52, 1–23 (1998).

Goodrich, MT Randomized shellsort: un simple algoritmo de clasificación ajeno. En Proc. del Vigésimo Primer Simposio Anual ACM-SIAM sobre Algoritmos Discretos 1262–1277 (ACM, 2010).

Mehlhorn, K., Sanders, P. & Sanders, P. Algoritmos y estructuras de datos: la caja de herramientas básica vol. 55. (Springer, 2008).

Knebl, H. Algoritmos y estructuras de datos (Springer, 2020).

Karatzoglou, A., Baltrunas, L. & Shi, Y. Aprendiendo a clasificar para sistemas de recomendación. En Proc. de la 7.ª Conferencia ACM sobre sistemas de recomendación 493–494 (ACM, 2013).

Yang, JY, Zhang, B. y Mao, Y. Estudio sobre el algoritmo de clasificación de recuperación de información en un entorno de fabricación basado en red. En Mecánica Aplicada y Materiales vol. 484, 183–186 (Trans Tech Publishing, 2014).

Krallmann, J., Schwiegelshohn, U. y Yahyapour, R. Sobre el diseño y evaluación de algoritmos de programación de tareas. En Workshop on Job Scheduling Strategies for Parallel Processing 17–42 (Springer, 1999).

White, SK, Martinez, T. & Rudolph, G. Generación de un algoritmo de clasificación novedoso mediante programación de refuerzo. En Proc. Congreso IEEE sobre Computación Evolutiva 1–8 (IEEE, 2010).

Srivastava, S., Gulwani, S. & Foster, JS De la verificación del programa a la síntesis del programa. En Proc. del 37º Simposio Anual ACM SIGPLAN-SIGACT sobre Principios de Lenguajes de Programación 313–326 (ACM, 2010).

Ansel, J. et al. Petabricks: un lenguaje y compilador para la elección algorítmica. Avisos de ACM Sigplan 44, 38–49 (2009).

Smith, DR El diseño de algoritmos de divide y vencerás. ciencia computar Programa. 5, 37–58 (1985).

Irvine, KR y col. Lenguaje ensamblador para computadoras basadas en Intel (Prentice Hall, 2003).

Shannon, CE XXII. Programación de una computadora para jugar al ajedrez. Londres, Edinb. Filosofía de Dublín. revista J. Ciencia. 41.314, 256–275 (1950).

Plata, D. et al. Dominar el juego de Go con redes neuronales profundas y búsqueda de árboles. Naturaleza 529, 484–489 (2016).

Plata, D. et al. Un algoritmo general de aprendizaje por refuerzo que domina el ajedrez, el shogi y el Go a través del autojuego. Ciencia 362, 1140–1144 (2018).

Vaswani, A. et al. La atención es todo lo que necesitas. Adv. Informe neuronal. proc. sist. 30, 5999–6009 (2017).

LLVM. Usuarios de LLVM https://llvm.org/Users.html (LLVM, 2022).

Bartlett, J. Learn to Program with Assembly 271–273 (Apress, 2021).

Sutton, RS & Barto, AG Aprendizaje por refuerzo: una introducción, 2.ª edición (MIT Press, 2018).

Schrittwieser, J. et al. Dominio de atari, go, ajedrez y shogi mediante la planificación con un modelo aprendido. Naturaleza 588, 604–609 (2020).

Maillard, O.-A., Ryabko, D. & Munos, R. Seleccionando la representación del estado en el aprendizaje por refuerzo. Adv. Informe neuronal. proc. sist. 24, 2627–2635 (2011).

Qian, R. et al. Aprendizaje de representaciones de video contrastivas espaciotemporales. En Proc. Conferencia IEEE/CVF sobre visión artificial y reconocimiento de patrones 6964–6974 (IEEE, 2021).

Marrón, T. et al. Los modelos de lenguaje son aprendices de pocas oportunidades. Adv. Informe neuronal. proc. sist. 33, 1877–1901 (2020).

Shazeer, N. Descodificación rápida del transformador: todo lo que necesita es un cabezal de escritura. Preimpresión en https://arxiv.org/abs/1911.02150 (2019).

Bundala, D. & Závodny, J. Redes de clasificación óptimas. En Proc. Conferencia internacional sobre teoría y aplicaciones del lenguaje y los autómatas 236–247 (Springer, 2014).

Hahn, GJ & Meeker, WQ Intervalos estadísticos: una guía para profesionales vol. 92 (John Wiley & Sons, 2011).

Google. Búferes de protocolo, versión 0.2.5; https://developers.google.com/protocol-buffers (2022).

Google. Serialización y deserialización del búfer del protocolo VarInt, versión 0.2.5; https://developers.google.com/protocol-buffers/docs/encoding (2022).

Protvin, R. & Levenberg, J. Por qué Google almacena miles de millones de líneas de código en un solo repositorio. común ACM 59, 78–87 (2016).

Berman, I. et al. Funciones hash resistentes a colisiones múltiples y sus aplicaciones. En Proc. Conferencia internacional anual sobre teoría y aplicaciones de técnicas criptográficas 133–161 (Springer, 2018).

Damgård, IB Funciones hash libres de colisiones y esquemas de firma de clave pública. En Workshop on the Theory and Application of Cryptographic Techniques 203–216 (Springer, 1987).

Hwang, M. Ordenar, Bitset (GitHub, 2021).

Van der Maaten, L. & Hinton, G. Visualización de datos usando t-SNE. J. Mach. Aprender. Res. 9.11, 2579–2605 (2008).

Gulwani, S. et al. Síntesis de programas libres de bucles. ACM SIGPLAN Avisos 46.6, 62–73 (2011).

Sasnauskas, R. et al. Souper: un superoptimizador sintetizador. Preimpresión en https://arxiv.org/abs/1711.04422 (2017).

Warren, HS Hacker's Delight (Pearson Education, 2013).

Hamadi, Y., Jabbour, S. & Sais, L. ManySAT: un solucionador SAT paralelo. J. Satisfacibilidad, Modelo Booleano. computar 6, 245–262 (2010).

Wolsey, LA Programación entera mixta. En Wiley Encyclopedia of Computer Science and Engineering 1–10 (Wiley, 2007).

Nair, V. et al. Resolución de programas enteros mixtos mediante redes neuronales. Preimpresión en https://arxiv.org/abs/2012.13349 (2020).

Inoue, H. et al. AA-sort: un nuevo algoritmo de clasificación en paralelo para procesadores SIMD multinúcleo. En Proc. Conferencia internacional sobre arquitectura paralela y técnicas de compilación (PACT 2007) 189–198 (IEEE, 2007).

Yin, Z. et al. Clasificación paralela eficiente en arquitecturas multinúcleo y multinúcleo basadas en avx-512. En Proc. 21.ª Conferencia internacional de IEEE sobre informática y comunicaciones de alto rendimiento 168–176 (IEEE, 2019).

Blacher, M. et al. Quicksort vectorizado y portátil para el rendimiento. Preimpresión en https://arxiv.org/abs/2205.05982 (2022).

Wikipedia. Instrucción única, datos múltiples https://en.m.wikipedia.org/wiki/SIMD (2022).

Ellis, K. et al. Escribir, ejecutar, evaluar: síntesis de programas con un REPL. Adv. Informe neuronal. proc. Sistema 32, 9137–9146 (2019).

Wang, H. et al. Automatización del diseño de la arquitectura de aprendizaje por refuerzo para la optimización del código. En Proc. 31.ª Conferencia internacional ACM SIGPLAN sobre construcción de compiladores 129–143 (ACM, 2022).

Shypula, AG et al. Aprender a superoptimizar programas del mundo real. Preimpresión en https://arxiv.org/abs/2109.13498 (2022).

Chen, X., Liu, C. y Song, D. Síntesis de programas neuronales guiada por ejecución. En Proc. Conferencia Internacional sobre Representaciones de Aprendizaje (ICLR, 2018).

Bunel, R. et al. Aprovechar la gramática y el aprendizaje por refuerzo para la síntesis de programas neuronales. En Proc. Conferencia Internacional sobre Representaciones de Aprendizaje (ICLR, 2018).

Aharoni, R. & Goldberg, Y. Hacia la traducción automática neuronal de cadena a árbol. En Proc. 55.ª Reunión Anual de la Asociación de Lingüística Computacional132–140 (ACL, 2017).

Dong, L. & Lapata, M. Lenguaje a forma lógica con atención neural. En Proc. 54.ª Reunión Anual de la Asociación de Lingüística Computacional 33–43 (ACL, 2016).

Ibarz, B. et al. Un aprendiz algorítmico neuronal generalista. En Proc. Conferencia de aprendizaje sobre gráficos vol. 198, 2:1–2:23 (PMLR, 2022).

Chen, X., Song, D. y Tian, Y. Ejecución latente para la síntesis de programas neuronales más allá de los lenguajes específicos de dominio. Adv. Informe neuronal. proc. sist. 34, 22196–22208 (2021).

Parisotto, E. et al. Síntesis de programas neurosimbólicos. Preimpresión en https://arxiv.org/abs/1611.01855 (2016).

Ellis, K., Solar-Lezama, A. & Tenenbaum, J. Sampling for Bayesian program learning. Adv. Informe neuronal. proc. sist. 29, 1297–1305 (2016).

Descargar referencias

Agradecemos a P. Kurylowicz, N. Anderson y Z. Ahmed por su asistencia en la coordinación de la investigación; L. Dionne y N. Klauser por revisar pacientemente nuestro código LLVM; y N. Vaish, D. Gove, D. Kutenin y A. Fawzi por sus útiles consejos durante el curso del proyecto. También agradecemos a nuestros colegas de DeepMind por su aliento y apoyo.

Estos autores contribuyeron igualmente: Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent

Deepmind, Londres, Reino Unido

Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq Iqbal, Jean-Baptiste Lespiau, Alex Ahern, Thomas Köppe, Kevin Millikin, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kieran Milan, Robert Tung, Taylan Cemgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhane, Thomas Hubert, Julian Steppwieser, Demis Hassabis, Pushmeet Kohli, Martin Riedmiller, Oriol Vinyals y David Silver

Google, Mountain View, CA, EE. UU.

Minjae Hwang

También puede buscar este autor en PubMed Google Scholar

DJM, A.Michi y AZ concibieron la idea y lideraron la investigación. A.Michi, DJM, AZ, MG, MS, CP, EL, SI y A.Mandhane desarrollaron la arquitectura y el entrenamiento de la red neuronal. J.-BL, CP, MG, DJM y EL desarrollaron la línea base. MG, AZ, DJM, MH, AA, TK y K.Millikin analizaron los algoritmos generados y ayudaron con el parche de clasificación. DJM, A.Michi, AZ, SG, SE, JB, RT, CG y K.Milan dirigieron la investigación. A.Michi, MG y MS lideraron la plataforma técnica. A.Mandhane, TH, YL, JS, TC, MB, PK, MR, DS, OV y DH contribuyeron con ideas y asesoramiento técnico. DJM y AZ concibieron el proyecto. DJM, CP, EL, A.Michi, MG, AZ, PK y MS escribieron el artículo.

Correspondencia a Daniel J. Mankowitz.

DJM, A.Michi, AZ, MG, MS, CP, EL, SI, A.Mandhane, PK, MR, DS y OV planean presentar una solicitud de patente relacionada con el contenido de este documento en nombre de DeepMind Technologies Limitado. Los autores restantes declaran no tener intereses contrapuestos.

Nature agradece a Zheng Wang y a los otros revisores anónimos por su contribución a la revisión por pares de este trabajo.

Nota del editor Springer Nature se mantiene neutral con respecto a los reclamos jurisdiccionales en mapas publicados y afiliaciones institucionales.

(a) La red de representación AlphaDev comprende una red Transformer Encoder que recibe como entrada el algoritmo de ensamblaje generado hasta el momento. También contiene una red de codificador de estado de CPU que recibe como entrada el estado actual de la memoria y los registros. La arquitectura exacta y los hiperparámetros se pueden encontrar en la Información complementaria, Apéndice A. (b) Antes de ingresar instrucciones en la red del codificador del transformador, el código de operación y los operandos de cada instrucción del programa se convierten en codificaciones one-hot y se concatenan. La codificación resultante luego se alimenta a la red del codificador del transformador.

(a) Las líneas horizontales se llaman alambres y las líneas verticales se llaman comparadores. (b) Una secuencia de valores inicialmente no clasificada se ingresa en la red de clasificación en el lado izquierdo. En varias etapas, dos cables se encuentran con un comparador. Si el valor en la parte superior del comparador es más pequeño que el valor en la parte inferior del comparador, los números cambian de cable. Una red de clasificación óptima coloca los comparadores en posiciones específicas para clasificar cualquier secuencia de valores sin clasificar utilizando el número mínimo de comparadores.

(a) Una proyección 2D t-SNE51 que indica las regiones exploradas por AlphaDev (azul) en comparación con AlphaDev-S. (b) La misma proyección 2D t-SNE que en (a) con la corrección del algoritmo superpuesta en cada punto desde los programas incorrectos (púrpura) hasta los programas correctos (amarillo). Como se ve en la figura, AlphaDev-S lucha por salir de los óptimos locales, mientras que AlphaDev puede explorar desde el espacio de los programas incorrectos al espacio de los programas correctos.

Acceso abierto Este artículo tiene una licencia internacional Creative Commons Attribution 4.0, que permite el uso, el intercambio, la adaptación, la distribución y la reproducción en cualquier medio o formato, siempre que se otorgue el crédito correspondiente al autor o autores originales y a la fuente. proporcionar un enlace a la licencia Creative Commons e indicar si se realizaron cambios. Las imágenes u otro material de terceros en este artículo están incluidos en la licencia Creative Commons del artículo, a menos que se indique lo contrario en una línea de crédito al material. Si el material no está incluido en la licencia Creative Commons del artículo y su uso previsto no está permitido por la regulación legal o excede el uso permitido, deberá obtener el permiso directamente del titular de los derechos de autor. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by/4.0/.

Reimpresiones y permisos

Mankowitz, DJ, Michi, A., Zhernov, A. et al. Algoritmos de clasificación más rápidos descubiertos mediante el aprendizaje de refuerzo profundo. Naturaleza 618, 257–263 (2023). https://doi.org/10.1038/s41586-023-06004-9

Descargar cita

Recibido: 25 julio 2022

Aceptado: 23 de marzo de 2023

Publicado: 07 junio 2023

Fecha de emisión: 08 de junio de 2023

DOI: https://doi.org/10.1038/s41586-023-06004-9

Cualquier persona con la que compartas el siguiente enlace podrá leer este contenido:

Lo sentimos, un enlace para compartir no está disponible actualmente para este artículo.

Proporcionado por la iniciativa de intercambio de contenido Springer Nature SharedIt

Al enviar un comentario, acepta cumplir con nuestros Términos y Pautas de la comunidad. Si encuentra algo abusivo o que no cumple con nuestros términos o pautas, márquelo como inapropiado.