Bend - Un lenguaje de alto nivel que corre en GPU (usa HVM2)

 (github.com/HigherOrderCO)
1 puntos por GN⁺ 2024-05-18 | 1 comentarios | Compartir por WhatsApp
  • Bend es un lenguaje de programación paralela de alto nivel que busca combinar la expresividad de Python y Haskell con la ejecución masivamente paralela al estilo CUDA, y funciona sobre el runtime HVM2
  • Se ejecuta en hardware paralelo como GPUs sin anotaciones explícitas de paralelización como creación de hilos, locks, mutex o atomic, mientras soporta funciones de orden superior con cierres, asignación rápida de objetos, recursión sin límites y continuations
  • Su objetivo de diseño actual es escalar el rendimiento según la cantidad de núcleos, y soporta más de 10,000 hilos concurrentes, pero la versión actual puede tener bajo rendimiento en un solo núcleo y todavía se están mejorando la generación de código y la optimización
  • Los modos de ejecución se dividen en bend run-rs, bend run-c y bend run-cu, y el código que puede paralelizarse puede ejecutarse en paralelo en el intérprete de C o en el intérprete de CUDA con solo cambiar el comando de ejecución
  • El soporte para Windows todavía está en desarrollo, así que WSL2 es una alternativa, y la ejecución en GPU actualmente solo soporta GPUs de NVIDIA

El modelo de programación al que apunta Bend

  • Bend es un lenguaje de programación que busca mantener la experiencia de uso de un lenguaje de alto nivel mientras se ejecuta sobre hardware masivamente paralelo
  • Ofrece funciones de lenguajes expresivos como Python y Haskell
    • asignación rápida de objetos
    • funciones de orden superior con cierres
    • recursión sin límites
    • continuations
  • Se ejecuta en hardware masivamente paralelo como GPUs, al estilo de CUDA, y busca una aceleración casi lineal basada en la cantidad de núcleos
  • Para la ejecución paralela no hace falta escribir directamente lo siguiente
    • creación de hilos
    • locks
    • mutex
    • atomic
  • El runtime usa HVM2

Limitaciones y precauciones actuales

  • Bend se enfoca en escalar el rendimiento según la cantidad de núcleos y está diseñado para soportar más de 10,000 hilos concurrentes
  • La versión actual puede tener bajo rendimiento en un solo núcleo
  • Se espera que el rendimiento mejore conforme evolucionen la generación de código y las técnicas de optimización
  • El soporte para Windows todavía está en desarrollo, y como alternativa se puede usar WSL2
  • El soporte de GPU actualmente solo funciona con GPUs de NVIDIA

Instalación y formas de ejecución

  • Tanto Linux como Mac requieren tener Rust instalado
  • La versión en C de Bend usa GCC, y el README recomienda GCC 12.x o inferior
  • Para usar el runtime de CUDA, en Linux se necesita instalar CUDA Toolkit 12.x
  • HVM2 se instala con cargo install hvm, y Bend con cargo install bend-lang
  • Los comandos para ejecutar programas de Bend se dividen según el ejecutor
    • bend run <file.bend>: usa el intérprete de C por defecto, ejecución paralela
    • bend run-rs <file.bend>: usa el intérprete de Rust, ejecución secuencial
    • bend run-c <file.bend>: usa el intérprete de C, ejecución paralela
    • bend run-cu <file.bend>: usa el intérprete de CUDA, ejecución masivamente paralela
  • Se puede compilar a archivos independientes de C/CUDA usando gen-c y gen-cu
  • El generador de código todavía está en una etapa temprana y no es tan maduro como compiladores como GCC o GHC
  • Con la bandera -s se puede ver la cantidad de reductions, el tiempo de ejecución y las interactions por segundo

Ejemplo de suma secuencial y suma paralela

  • El ejemplo de suma del README compara dos formas de código para sumar los números desde start hasta target
  • La versión secuencial tiene una estructura donde al resultado de Sum(start + 1, target) se le suma el valor actual de start
    • el siguiente cálculo depende del resultado de la suma anterior
    • no se puede avanzar al siguiente paso antes de que termine el cálculo actual, así que no puede paralelizarse
    • el ejemplo llama a Sum(1, 1_000_000) e incluye una nota de que podría desbordar el valor máximo de los números de Bend
  • La versión paralelizable divide el rango por la mitad y luego calcula recursivamente las sumas de la izquierda y la derecha
    • el cálculo de (3 + 4) no depende del cálculo de (1 + 2)
    • ambos cálculos pueden ocurrir al mismo tiempo, así que es posible la ejecución paralela
  • En Bend, si el código puede ejecutarse en paralelo, basta con cambiar el comando de ejecución para que corra en paralelo

Ejemplo de rendimiento con Bitonic Sorter

  • El README presenta como ejemplo de velocidad un bitonic sorter implementado con rotaciones inmutables de árbol
  • Aunque este algoritmo no parece del tipo que uno esperaría que fuera rápido en GPU, Bend lo ejecuta en múltiples hilos usando un enfoque de divide y vencerás
  • No hace falta crear hilos explícitamente ni gestionar locks
  • Los resultados del benchmark son los siguientes
    • bend run-rs: CPU, Apple M3 Max, 12.15 segundos
    • bend run-c: CPU, Apple M3 Max, 0.96 segundos
    • bend run-cu: GPU, NVIDIA RTX 4090, 0.21 segundos
  • Se pueden revisar otros algoritmos en la carpeta examples

Material de referencia

  • La tecnología base de Bend puede consultarse en el paper de HVM2
  • La documentación oficial todavía está en desarrollo, y una explicación más profunda está en GUIDE.md
  • La lista de funciones se puede consultar en FEATURES.md
  • Bend es desarrollado por HigherOrderCO

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-05-18
Comentarios de Hacker News

  • Al pasar el ejemplo de sum a Python puro, tomó 4.478 segundos en un solo hilo con pypy3, y 1 minuto con 42.148 segundos en Python 3.12
    En cambio, la versión de Bend de un solo hilo lleva 42 minutos corriendo en mi laptop, usa 6 GB de memoria y todavía no termina. El entorno es 12th Gen Intel(R) Core(TM) i7-1270P, Ubuntu 24.04
    Si va así de lento en un ejemplo tan simple, cuesta esperar mucho de tareas complejas, y me pregunto si esto se ha probado o desarrollado fuera de Mac/aarch64. Más tarde pienso volver a ejecutarlo con el argumento -s

    • Que corra durante 42 minutos probablemente sea un bug. Aún no se ha probado mucho fuera de M3 Max, y ya sabemos que en CPU no Apple es 2 veces más lento, así que planeamos mejorarlo
      En el ejemplo de sum, Bend tiene la gran desventaja de asignar 2 nodos IC por cada operación numérica, mientras que Python no. Igual que en HVM1, pronto podremos evitarlo, pero eso todavía no está implementado en HVM2
      La mayor parte del trabajo en Bend se fue en hacer bien el evaluador paralelo, y ejecutar closures y recursión sin restricciones en GPU fue muy difícil. Esa parte apenas se acaba de terminar, así que casi no se ha invertido esfuerzo en microoptimizaciones, y la generación de código de HVM2 todavía es bastante mala
      Si lo comparas con casos como el ejemplo de Bitonic Sort, donde ambos lados hacen la misma cantidad de asignaciones, se podrá ver el rendimiento real de forma más justa. HVM1 era unas 3 veces más lento que GHC en un solo núcleo, y creo que HVM2 también puede llegar pronto a ese nivel
      Entiendo que decir “todavía está mal, pero va a mejorar” puede desinflar el entusiasmo. Aun así, la base ya está puesta, así que las microoptimizaciones son la parte más fácil, y creo que el rendimiento va a subir mucho desde aquí
    • No tengo ningún interés personal en esta discusión, pero la recursión se parece más a una prueba de qué tan eficientemente el compilador/intérprete construye y destruye la pila de llamadas que a una prueba de rendimiento de cómputo
      Este lenguaje apunta a aplicaciones de GPU intensivas en cálculo y todavía está en una etapa temprana. La recursión no es la aplicación objetivo y no me parece una referencia adecuada para benchmark relacionado
    • Hilo en GPU y CPU no significa lo mismo; en GPU es más cercano a un SIMD lane
      Es parecido a cómo ISPC puede compilar para ejecutar 32 llamadas de función simultáneamente por cada hilo de CPU. Por ejemplo, en AVX512 usando datos de 16 bits, podrían avanzar al mismo tiempo 2048 ejecuciones: 32 núcleos × 2 hilos SMT por núcleo × 32 ejecuciones del compilador
    • Python es muy malo con la recursión, y esa es una de las razones por las que no es adecuado para programación funcional, así que quizá no sea un benchmark justo
      Una implementación al estilo Python habría usado bucles y estado mutable
    • No entiendo por qué hace falta +0. ¿No es una operación que no hace nada?

  • Hay muchas reacciones negativas en este hilo, pero aun así quiero darle kudos al autor solo por haber llegado hasta aquí
    Como proyecto parecido, solo conozco Futhark, pero su sintaxis estilo Haskell puede resultar bastante críptica para desarrolladores comunes acostumbrados a C/C++/Python/JS/Java y demás
    Mi mayor decepción es que, a diferencia de Futhark, esto parece apuntar solo a CUDA o multicore. Futhark puede apuntar a OpenCL, CUDA, ISPC, HIP, CPU de un solo núcleo y CPU multinúcleo. Creo que los problemas de rendimiento que otros señalaron se pueden resolver perfectamente

  • El OP suele traer algunas de las cosas más geniales que han aparecido recientemente en HN, y da pena que aquí parezca recibir solo críticas largas, aunque claramente sigue siendo una versión temprana

    • HN se parece más a una comunidad donde la gente quiere publicar cosas nuevas u originales. Si alguien quiere felicitar a otro, muchas veces le da voto positivo a un comentario ya existente en vez de escribir otro “qué genial”
      En cambio, las críticas tienen pocas formas de acertar y muchísimas de equivocarse, así que pueden variar sin fin. Por eso los comentarios positivos suelen ser pocos, y la mayoría termina viéndose como crítica o como “también debería hacer esto”. No es culpa de una persona concreta; más bien la cultura técnica actual tiende en esa dirección
    • Si fuera mi proyecto, agradecería bastante que la gente lo criticara. Así es como uno crece
      Si la gente solo ocultara las verdades brutales detrás de aplausos, el mundo se vendría abajo
    • Recibió 905 votos, así que también tuvo una reacción positiva más que suficiente
      La crítica también significa que la gente se interesa por la idea y por el enfoque y participa en la conversación, así que muchas veces es una señal positiva
    • No criticar proyectos nuevos y ambiciosos es una buena norma social. Ese tipo de intentos debería alentarse y no desanimarse
      Pero criticar proyectos que hacen afirmaciones confusas, poco fundamentadas o falsas también es una buena norma social, porque ayuda a reducir ese tipo de afirmaciones
    • Las cosas más geniales suelen ser las más difíciles de entender
      Lo difícil de entender a menudo se siente amenazante, y la crítica es una reacción común ante la amenaza y una forma de responder que requiere el menor nivel de comprensión

  • La página principal está realmente muy bien hecha. Queda clarísimo de inmediato qué hace.
    La gente que trabaja con “combinadores” normalmente quiere usar mucha jerga intimidante, pero el OP sí muestra la idea simple detrás de la herramienta. Me gusta porque es lo contrario del enfoque académico de mostrar hasta el último detalle sin explicar qué está pasando en realidad. Ojalá hubiera más cosas así.

  • La teoría suena genial y entiendo la propuesta de valor, pero sinceramente no parece que esto vaya a convertirse en una herramienta relevante en la práctica.
    Son notas basadas en la primera impresión y en haber hojeado el paper. Sé que es software muy temprano.
    Bend parece un DSL muy limitado. No tiene FFI, no hay forma de interactuar con buffers primitivos y el formato de punto flotante de 24 bits también es raro.
    Hay una razón por la que los IC no son mainstream. Es muy probable que el rendimiento siga siendo terrible, y recorrer grafos no encaja bien con el hardware.
    La premisa de la reducción óptima es válida, pero al final igual hay que escribir kernels de una forma paralelizable. O sea, no debe haber dependencias de datos y también hay que pensar en el uso de recursión.
    No hay ejemplos serios que comparen directamente código Bend/HVM con programas equivalentes en OMP/CUDA. Es difícil evaluar cuánto se reduce la complejidad de implementación y qué tanto rendimiento se obtiene.
    En la computación paralela de alto rendimiento del mundo real casi no hay estructuras tipo árbol; los arreglos mandan. Eso se debe a las propiedades físicas de cómo funciona la memoria a nivel de hardware. Lo que mejor funciona sobre buffers de memoria contigua mutables son los bucles. Si HVM implementa eso, lo observaré con interés.
    Por ahora parece un lenguaje a medio cocinar, casi totalmente aislado de los datos externos, muy lento y con una abstracción gigantesca encima del hardware. Tampoco aprovecha cosas como cachés multinivel, tensor cores, SIMD u operaciones atómicas.
    Perdón si sonó brusco, pero la implementación técnica y el trasfondo teórico me siguen pareciendo muy interesantes. Simplemente todavía no me convence su utilidad en el mundo real.

    • Gracias por el feedback. Solo para corregir algunos puntos: sí usamos cachés multinivel y, si se usan bien, pueden dar un rendimiento 5 veces mayor.
      El FFI ya está implementado, pero todavía no lo hemos publicado. Queremos lanzarlo junto con renderizado gráfico, y creemos que va a quedar bastante bien.
      Haskell/GHC también usa grafos y árboles, pero nadie diría que no es práctico. Es cierto que los arreglos mandan, pero muchos algoritmos modernos que no encajan bien con arreglos —como compiladores, verificadores de tipos y solvers— están implementados en Haskell.
      La razón principal por la que los IC no han sido rápidos es que nadie ha hecho realmente trabajo serio de optimización de bajo nivel sobre ellos. Todas las implementaciones previas eran extremadamente ineficientes, y en mi caso hasta ahora el tiempo se ha ido en lograr que corra correctamente en la GPU.
      Igual que decir que todavía no hay bucles, la solución es simplemente agregar bucles. Si crees que ahí hay una limitación esencial, te vas a sorprender.
      HVM2 por fin ya es un algoritmo correcto y escalable, y ahora toca optimizar el rendimiento real de bajo nivel.
    • Sobre el punto 5, los árboles son distintos a las implementaciones típicas de ciencias de la computación, pero sí se usan bastante.
      En algoritmos como Fast Multipole o Barnes-Hut se usa el orden de Morton o el orden H-index para reducir operaciones por pares de O(n²) a O(n) y O(n log n), respectivamente. Barnes-Hut es más común en astrofísica, y Fast Multipole se ve más seguido en dinámica molecular en química.

  • Hace 10 años tomé 15-210, el curso de algoritmos paralelos de CMU. Explicaban que, como la ley de Moore estaba llegando a sus límites, el paralelismo iba a ser el futuro de la computación, y eso me convenció de querer experimentar con ello.
    Pero no había muchas opciones de programación paralela de propósito general. Incluso SML, que usábamos en clase, no era paralelo, y al final había una sección con extensiones y CUDA, pero según recuerdo era limitada.
    Después, gracias a Rust, pude experimentar un poco con multithreading, y gracias a Shadertoy pude hacer cosas creativas con shaders. Pero un lenguaje paralelo de propósito general sobre GPU suena muy emocionante; tengo muchísimas ganas de probarlo.

    • Hoy en día 210 sí es realmente paralelo. Si usas MaPLe(https://github.com/MPLLang/mpl), puedes ejecutar código estilo 210 y además obtener un rendimiento competitivo frente a C/C++.
      Si te gustó 210, también podría gustarte https://futhark-lang.org/. Es un lenguaje de la familia ML, compila a GPU y tiene buen rendimiento.
    • Una de las razones por las que decidí aprender Elixir fue justamente la tendencia de las máquinas hacia el multicore.

  • La idea está muy buena, pero si no me estoy perdiendo algo, parece muy lento.
    Escribí un bucle simple en C++ para sumar de 0 a 2³⁰, y en mi laptop tardó 1.7 segundos en un solo hilo sin optimizaciones, lo cual es parecido al rendimiento de Bend en una RTX 4090. Con -O3, el bucle se vectoriza y corre en menos de 80 ms.

    • Bend todavía no tiene optimización de llamadas de cola. Está asignando una pila de mil millones de elementos, mientras que C simplemente ejecuta un bucle.
      Si se compara con un programa en C que realmente haga esa asignación, es muy probable que Bend sea más rápido incluso con solo unos cuantos hilos.
      La generación de código de Bend todavía es bastante mala, pero eso es de lo más fácil de mejorar. La mayor parte del trabajo se ha ido en hacer correcto un evaluador paralelo muy difícil.
      Sé que suena a “créanme”, pero cuando empecemos con compilación de procedimientos, generación de bucles, etc., el rendimiento en un solo hilo va a mejorar muchísimo. Simplemente todavía no lo hemos hecho.
      Incluso me pregunto si debí esperar un poco más antes de publicarlo.
    • Conviene revisar con objdump si el bucle realmente se vectorizó o si el compilador simplemente lo optimizó por completo.
      Ese bucle provoca overflow de entero con signo, y en C++ eso es comportamiento indefinido. El compilador legalmente puede producir cualquier resultado.
      Para evitarlo, habría que declarar sum como unsigned. El overflow de enteros sin signo sí está bien definido, y las optimizaciones igual ocurren, pero al menos la corrección queda garantizada.
    • Si lo compilas con -O3 en clang, el bucle desaparece por completo: https://godbolt.org/z/M1rMY6qM9
      Probablemente no sería una comparación justa.
    • Creo que la clave es que Bend es mucho más de alto nivel que C++.
      Aunque claro, también podría estar pasando por alto el punto.

  • Quiero felicitar al autor. Es un trabajo realmente impresionante.
    Lograr una paralelización automática correcta nunca es fácil, y hay motivos de sobra para sentirse orgulloso. Tengo muchas ganas de ver cómo evoluciona el proyecto.

  • No entiendo por qué hay tantas reacciones negativas. Parecía una turba enfurecida, como bots tratando de escarbar en las debilidades del README para cambiar el contexto y la intención del texto.
    Pasarse horas discutiendo sin dedicar ni 2 minutos a leerlo bien es ignorante y cruel. El OP llegó hasta aquí con un proyecto de una sola persona, así que ojalá siga adelante.

  • Tenía curiosidad por saber si HVM2 compila las interaction nets, por ejemplo, a SPIR-V, o si es un intérprete que corre en GPU como el HVM original.
    Hace tiempo probé compilar interaction nets a C tratándolas como una especie de optimización de programa completo: reducía el programa tanto como fuera posible, pero no la entrada. Apuntar a un lenguaje de shaders tampoco parecía tan difícil.
    Viendo el repositorio, dice que ofrece un lenguaje IR de bajo nivel para describir redes de HVM2 y un compilador hacia C/CUDA: https://github.com/HigherOrderCO/HVM
    Pero al revisar de nuevo, el runtime CUDA de HVM2 parece más bien un intérprete que recorre un grafo en memoria y aplica reducciones: https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
    Lo que yo decía era recorrer las interaction nets para reconstruir términos más cercanos al cálculo lambda y luego bajarlos a C en fragmentos pequeños para minimizar el overhead del runtime.
    La motivación franca es que, con Bend, parece difícil superar kernels GPU escritos a mano en cargas de trabajo como ML. En teoría, HVM podría servir como pegamento para unir kernels de cómputo y paralelizar su orden de ejecución, pero para eso necesitaría un buen FFI.
    Las interaction nets son difíciles de traducir a través de un límite de FFI, pero si pones nodos de kernel de cómputo FFI dentro de la red de interacción y compilas la red a C, podrías recuperar un FFI razonable sin overhead de traducción.
    La otra opción es implementar HVM en hardware; he estado jugueteando un poco con eso en una FPGA que tenía libre.

    • Es un intérprete que corre en GPU, y también es un compilador hacia C nativo y CUDA.
      No apunta directamente a SPIR-V, pero está en los planes.
      El compilador a C sí logra la mejora de velocidad esperada, es decir, de 3 a 4 veces y pronto más, pero el runtime CUDA no consiguió una gran mejora frente a la versión no compilada.
      Creo que la causa es la divergencia de warp. En el procedimiento no compilado, todas las llamadas a funciones pueden fusionarse en un único expansor de funciones “genérico” estilo intérprete, y los hilos del warp pueden reducir sin ramificarse. Planeo investigar esto más a fondo.