Bend - uma linguagem de alto nível executada na GPU (usando HVM2)

 (github.com/HigherOrderCO)
1 pontos por GN⁺ 2024-05-18 | 1 comentários | Compartilhar no WhatsApp
  • Bend é uma linguagem de programação paralela de alto nível que busca combinar a expressividade de Python e Haskell com a execução massivamente paralela ao estilo CUDA, e roda sobre o runtime HVM2
  • Ela oferece funções de ordem superior com closures, alocação rápida de objetos, recursão sem limites e continuation, mas ainda assim executa em hardware paralelo como GPUs sem anotações explícitas de paralelização como criação de threads, locks, mutexes ou atomics
  • O objetivo atual de design é escalabilidade de desempenho conforme o número de núcleos, com suporte a mais de 10.000 threads simultâneas, embora a versão atual possa ter baixo desempenho em núcleo único e melhorias em geração de código e otimização ainda estejam em andamento
  • Os modos de execução se dividem em bend run-rs, bend run-c e bend run-cu; códigos que podem ser paralelizados podem ser executados em paralelo no interpretador C ou no interpretador CUDA apenas mudando o comando de execução
  • O suporte a Windows ainda está em desenvolvimento, então o WSL2 é a alternativa; a execução em GPU atualmente suporta apenas GPUs NVIDIA

O modelo de programação que o Bend busca

  • Bend é uma linguagem de programação feita para rodar em hardware massivamente paralelo, mantendo a experiência de uso de uma linguagem de alto nível
  • Ela oferece recursos de linguagens expressivas como Python e Haskell
    • alocação rápida de objetos
    • funções de ordem superior com closures
    • recursão sem limites
    • continuation
  • Assim como CUDA, roda em hardware massivamente paralelo como GPUs, buscando aceleração quase linear com base no número de núcleos
  • Para execução paralela, não é preciso escrever diretamente
    • criação de threads
    • locks
    • mutexes
    • atomics
  • O runtime usado é o HVM2

Limitações e cuidados atuais

  • O Bend foca em escalar desempenho conforme o número de núcleos e foi projetado para suportar mais de 10.000 threads simultâneas
  • A versão atual pode ter baixo desempenho em núcleo único
  • Espera-se melhora de desempenho à medida que técnicas de geração de código e otimização evoluírem
  • O suporte a Windows ainda está em desenvolvimento e, como alternativa, é possível usar o WSL2
  • O suporte a GPU atualmente se limita a GPUs NVIDIA

Instalação e modos de execução

  • Tanto no Linux quanto no Mac é necessário ter Rust instalado
  • A versão em C do Bend usa GCC, e o README recomenda GCC 12.x ou inferior
  • Para usar o runtime CUDA, é necessário instalar o CUDA Toolkit 12.x no Linux
  • O HVM2 é instalado com cargo install hvm, e o Bend com cargo install bend-lang
  • Os comandos para executar programas Bend variam conforme o executor
    • bend run <file.bend>: usa o interpretador C por padrão, com execução paralela
    • bend run-rs <file.bend>: usa o interpretador Rust, com execução sequencial
    • bend run-c <file.bend>: usa o interpretador C, com execução paralela
    • bend run-cu <file.bend>: usa o interpretador CUDA, com execução massivamente paralela
  • É possível compilar para arquivos C/CUDA independentes com gen-c e gen-cu
  • O gerador de código ainda está em estágio inicial e não é tão maduro quanto compiladores como GCC ou GHC
  • Com a flag -s, é possível ver o número de reductions, o tempo de execução e o número de interactions por segundo

Exemplo de soma sequencial e soma paralela

  • O exemplo de soma no README compara duas formas de somar os números de start até target
  • A versão sequencial soma o valor atual de start ao resultado de Sum(start + 1, target)
    • o próximo cálculo depende do resultado da soma anterior
    • não é possível avançar para a etapa seguinte antes de o cálculo atual terminar, então não dá para paralelizar
    • o exemplo chama Sum(1, 1_000_000) e inclui um comentário dizendo que isso pode estourar o valor máximo dos números do Bend
  • A versão paralelizável divide o intervalo pela metade e então calcula recursivamente as somas da esquerda e da direita
    • o cálculo de (3 + 4) não depende do cálculo de (1 + 2)
    • os dois cálculos podem ocorrer ao mesmo tempo, permitindo execução paralela
  • No Bend, se o código puder rodar em paralelo, basta mudar o comando de execução para obter execução paralela

Exemplo de desempenho com Bitonic Sorter

  • O README apresenta um bitonic sorter implementado com rotações de árvore imutável como exemplo de velocidade
  • Esse tipo de algoritmo não parece, em princípio, algo que seria rápido em GPU, mas com uma abordagem de divisão e conquista o Bend o executa em várias threads
  • Não é necessário criar threads explicitamente nem gerenciar locks
  • Os resultados de benchmark são os seguintes
    • bend run-rs: CPU, Apple M3 Max, 12,15 s
    • bend run-c: CPU, Apple M3 Max, 0,96 s
    • bend run-cu: GPU, NVIDIA RTX 4090, 0,21 s
  • Outros algoritmos podem ser vistos na pasta examples

Materiais de referência

  • A tecnologia que fundamenta o Bend pode ser consultada no paper do HVM2
  • A documentação oficial ainda está em andamento, e uma explicação mais aprofundada está em GUIDE.md
  • A lista de recursos pode ser vista em FEATURES.md
  • O Bend é desenvolvido pela HigherOrderCO

Leituras relacionadas

1 comentários

 
GN⁺ 2024-05-18
Opiniões no Hacker News

  • Ao portar o exemplo sum para Python puro, levou 4,478 segundos em single-thread no pypy3 e 1 minuto e 42,148 segundos no Python 3.12
    Já a versão single-thread do Bend está rodando há 42 minutos no meu notebook e ainda não terminou, mesmo usando 6 GB de memória. O ambiente é um 12th Gen Intel(R) Core(TM) i7-1270P, Ubuntu 24.04
    Se ele é tão lento em um exemplo muito simples, é difícil esperar muito em tarefas complexas, e fico curioso se ele foi testado ou desenvolvido em ambientes fora de Mac/aarch64. Mais tarde pretendo rodar de novo com o argumento -s

    • Rodar por 42 minutos provavelmente é um bug. Ainda não testamos muito em ambientes além do M3 Max, e sabemos que em CPUs que não são da Apple ele é 2× mais lento; pretendemos melhorar isso
      No exemplo sum, o Bend tem uma grande desvantagem: aloca 2 nós IC a cada operação numérica, enquanto Python não faz isso. Como no HVM1, em breve pretendemos conseguir evitar isso, mas ainda não foi implementado no HVM2
      A maior parte do trabalho no Bend foi para fazer o avaliador paralelo funcionar corretamente, e executar closures e recursão sem limites na GPU foi extremamente difícil. Como acabamos de concluir essa parte, quase nenhum esforço foi dedicado a micro-otimizações, e a geração de código do HVM2 ainda é péssima
      Comparando com casos em que os dois lados fazem a mesma quantidade de alocações, como no exemplo Bitonic Sort, deve ser possível ver o desempenho real de forma mais justa. O HVM1 era cerca de 3× mais lento que o GHC em um único core, e acredito que o HVM2 também possa chegar a esse nível em breve
      Entendo que dizer “ainda está ruim, mas vai melhorar” possa ser desanimador. Mesmo assim, agora que a base está pronta, micro-otimização é a parte mais fácil, e acredito que o desempenho vai subir bastante daqui em diante
    • Não tenho interesse direto nessa discussão, mas recursão está mais para testar a eficiência com que o compilador/interpretador cria e destrói a pilha de chamadas do que o desempenho computacional em si
      Esta linguagem mira aplicações de GPU com alta carga computacional e ainda está em estágio inicial. Recursão não é a aplicação-alvo, e acho difícil vê-la como um benchmark relevante
    • Threads significam coisas diferentes em GPU e CPU; em GPU, estão mais próximas de lanes SIMD
      É parecido com o ISPC poder compilar para executar 32 chamadas de função simultaneamente por thread de CPU. Por exemplo, usando dados de 16 bits no AVX512, pode haver 32 cores × 2 threads SMT por core × 32 execuções do compilador, totalizando 2048 execuções acontecendo ao mesmo tempo
    • Python é muito fraco em recursão, o que é um dos motivos pelos quais não é adequado para programação funcional; portanto, talvez não seja um benchmark justo
      Uma implementação mais idiomática em Python teria usado loops e estado mutável
    • Não entendo por que +0 é necessário. Não é uma operação que não faz nada?

  • Há muitas reações negativas nesta thread, mas eu gostaria de dar kudos ao autor só por ter construído isso até aqui
    De projetos parecidos, só conheço algo como Futhark, mas a sintaxe no estilo Haskell pode ser bem difícil para desenvolvedores comuns acostumados com C/C++/Python/JS/Java etc.
    O maior ponto negativo é que, ao contrário do Futhark, ele mira apenas CUDA ou multicore. O Futhark pode ter como alvo OpenCL, CUDA, ISPC, HIP, CPU single-core e CPU multicore. Acho que os problemas de desempenho apontados por outras pessoas são perfeitamente solucionáveis

  • O OP traz algumas das coisas mais legais que apareceram recentemente no HN, então é uma pena ver que, mesmo sendo claramente uma versão inicial, parece receber apenas críticas longas

    • O HN é mais uma comunidade de gente que quer postar coisas novas ou originais. Quando alguém quer elogiar, muitas vezes dá upvote em um comentário existente em vez de escrever mais um comentário dizendo “legal”
      Já a crítica tem formas limitadas de acertar e muitas formas de errar, então pode se diversificar infinitamente. Por isso, acabam aparecendo só alguns comentários positivos, enquanto a maior parte parece crítica ou “seria bom se também fizesse isto”. Não é tanto culpa de uma pessoa específica; a cultura técnica de hoje é meio assim
    • Se fosse meu projeto, eu ficaria bastante grato pelas críticas das pessoas. É assim que se cresce
      Se as pessoas apenas escondessem verdades duras atrás de aplausos, o mundo desmoronaria
    • Recebeu 905 upvotes, então também teve bastante reação positiva
      Críticas também significam que as pessoas estão interessadas nas ideias e na abordagem e estão participando; por isso, muitas vezes são um sinal positivo
    • Não criticar projetos novos e ambiciosos é uma boa norma social. Esse tipo de tentativa deve ser incentivado, não desencorajado
      Mas criticar projetos que fazem afirmações enganosas, mal fundamentadas ou falsas também é uma boa norma social. Isso ajuda a reduzir esse tipo de afirmação
    • As coisas mais legais geralmente são as mais difíceis de entender
      O que é difícil de entender muitas vezes parece ameaçador, e a crítica é uma reação comum a ameaças, além de ser a forma de resposta que exige o menor nível de compreensão

  • A página inicial é muito bem feita. Fica imediatamente claro o que ela faz
    Pessoas que lidam com “combinadores” normalmente gostam de usar muita terminologia assustadora, mas o OP realmente mostra a ideia simples por trás da ferramenta. Gosto por ser o oposto da abordagem acadêmica de mostrar até o último detalhe sem dizer o que está acontecendo de fato. Precisamos de mais disso

  • Em teoria é legal, e entendo a proposta de valor, mas, sinceramente, não acho que isso vá se tornar uma ferramenta relevante de verdade
    São minhas anotações depois da primeira impressão e de folhear o artigo. Sei que é um software em estágio muito inicial
    Bend parece uma DSL bastante limitada. Não há FFI, não há como interagir com buffers primitivos, e o formato de ponto flutuante de 24 bits também é estranho
    Há uma razão para IC não ser mainstream. É provável que o desempenho continue terrível, e percorrer grafos não combina bem com o hardware
    A premissa de redução ótima é válida, mas no fim você precisa escrever kernels de um jeito que possa ser paralelizado. Ou seja, sem dependências de dados, e também é preciso considerar o uso de recursão
    Não há exemplos sérios que comparem diretamente código Bend/HVM com programas OMP/CUDA equivalentes. Fica difícil avaliar quanto a complexidade de implementação diminui e qual é o nível de desempenho
    Na computação paralela de alto desempenho do mundo real, estruturas em árvore quase não aparecem, e arrays são reis. Isso se deve às propriedades físicas de como a memória funciona no nível do hardware. O que funciona melhor em buffers de memória contígua e mutável são loops. Vou observar se o HVM implementar isso
    No momento, parece quase totalmente isolado de dados externos, muito lento, e uma linguagem meio crua com uma abstração enorme em cima do hardware. Também não consegue aproveitar recursos como caches multinível, tensor cores, SIMD e operações atômicas
    Desculpe se soou duro, mas ainda acho a implementação técnica e o embasamento teórico muito interessantes. Só que ainda não estou convencido da utilidade no mundo real

    • Obrigado pelo feedback. Corrigindo alguns pontos: nós usamos caches multinível e, quando usados corretamente, eles podem gerar desempenho 5 vezes maior
      FFI já está implementada, mas ainda não foi publicada. É porque queremos lançá-la junto com renderização gráfica, e acho que vai ficar bem legal
      Haskell/GHC também usam grafos e árvores, mas ninguém diria que não são práticos. Arrays são reis, sim, mas muitos algoritmos modernos que não se encaixam bem em arrays — compiladores, verificadores de tipos, solvers etc. — são implementados em Haskell
      O principal motivo de IC não ser rápido é que ninguém fez trabalho sério de otimização de baixo nível em cima dele. Todas as implementações anteriores eram extremamente ineficientes, e meu trabalho até agora também dedicou tempo a fazê-lo executar corretamente na GPU
      Como no comentário de que ainda nem há loops, a solução é simplesmente adicionar loops. Se você acha que há uma limitação intrínseca nisso, acho que vai se surpreender
      O HVM2 finalmente se tornou um algoritmo correto e escalável, e agora é hora de otimizar o desempenho real em baixo nível
    • Sobre o ponto 5, árvores são bem diferentes das implementações comuns de ciência da computação, mas são usadas de forma bastante ampla
      Nos algoritmos Fast Multipole e Barnes-Hut, usa-se a ordem de Morton ou a ordem H-index para reduzir operações pareadas O(n²) para O(n) e O(n log n), respectivamente. Barnes-Hut é mais comum em astrofísica, enquanto Fast Multipole aparece com mais frequência em dinâmica molecular na química

  • Há 10 anos cursei 15-210, a disciplina de algoritmos paralelos da CMU. Ela explicava que, com a Lei de Moore chegando aos limites, o paralelismo seria o futuro da computação, e isso me convenceu e me deixou com vontade de experimentar
    Mas não havia muitas opções de programação paralela de uso geral. Até o SML usado na aula não era paralelo, e havia uma seção no final usando extensões e CUDA, mas, pelo que lembro, era limitada
    Depois, graças ao Rust, experimentei um pouco de multithreading, e graças ao Shadertoy pude fazer coisas criativas com shaders. Mas uma linguagem paralela de uso geral em cima de GPU? Estou muito animado para mexer nisso

    • Hoje em dia, a 210 é de fato paralela. Com MaPLe (https://github.com/MPLLang/mpl), você pode executar código no estilo da 210 e obter desempenho competitivo em relação a C/C++
      Se você gostou da 210, talvez também goste de https://futhark-lang.org/. É uma linguagem da família ML, compila para GPU e tem bom desempenho
    • A tendência de as máquinas seguirem para multicore foi um dos motivos pelos quais decidi aprender Elixir

  • A ideia é muito legal, mas, a menos que eu tenha deixado algo passar, ela parece muito lenta
    Escrevi em C++ um loop simples que soma de 0 até 2³⁰ e, sem otimização, em uma única thread, levou 1,7 s no meu notebook, o que é parecido com o desempenho do Bend em uma RTX 4090. Com -O3, o loop é vetorizado e roda em menos de 80 ms

    • O Bend ainda não tem otimização de chamada em cauda. Ele está alocando uma pilha de tamanho 1 bilhão, enquanto C está apenas rodando um loop
      Comparado a um programa em C que realmente faça alocações, é bem possível que o Bend seja mais rápido mesmo com apenas algumas threads
      A geração de código do Bend ainda é péssima, mas isso é fruto fácil de colher. A maior parte do trabalho foi para fazer o avaliador paralelo, que é muito difícil, funcionar corretamente
      Sei que soa como “confie em mim”, mas quando começarmos a fazer compilação procedural, geração de loops etc., o desempenho em uma única thread vai melhorar muito. Só ainda não fizemos isso
      Às vezes acho que talvez devesse ter esperado um pouco mais antes de publicar
    • Vale conferir com objdump se o loop foi de fato vetorizado ou se o compilador simplesmente otimizou tudo fora
      Esse loop causa estouro de inteiro com sinal e, em C++, isso é comportamento indefinido. O compilador pode legalmente produzir qualquer resultado
      Para evitar isso, sum deve ser declarado como unsigned. O estouro de inteiro sem sinal é bem definido, e a otimização ainda acontece, mas pelo menos a correção é garantida
    • Compilando com -O3 no clang, o loop é removido por completo: https://godbolt.org/z/M1rMY6qM9
      Provavelmente não é uma comparação justa
    • Acho que o ponto principal é que Bend é de muito mais alto nível que C++
      Claro, eu também posso estar perdendo o ponto

  • Quero parabenizar o autor. É um trabalho realmente incrível
    Criar paralelização automática correta não é nada fácil, e você pode se orgulhar bastante. Estou ansioso para ver como o projeto vai evoluir

  • Não entendo por que há tantas reações negativas assim. Parecia uma multidão enfurecida, como bots fuçando falhas no README e tentando mudar o contexto e a intenção do texto
    Discutir por horas sem gastar nem 2 minutos para ler direito é ignorante e cruel. O OP chegou até aqui com um projeto de uma pessoa só, então espero que continue tocando em frente

  • Fiquei curioso se o HVM2 compila redes de interação, por exemplo, para SPIR-V, ou se é um interpretador que roda na GPU, como o HVM original
    No passado, experimentei compilar redes de interação para C tratando-as como uma otimização de programa inteiro, reduzindo o programa tanto quanto possível e deixando a entrada sem reduzir. Ter como alvo uma linguagem de shader também não parecia muito difícil
    Olhando o repositório, ele diz oferecer uma linguagem IR de baixo nível para especificar redes HVM2 e um compilador para C/CUDA: https://github.com/HigherOrderCO/HVM
    Mas, olhando de novo, o runtime CUDA do HVM2 parece um interpretador que percorre um grafo na memória e aplica reduções: https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
    O que eu tinha em mente é percorrer a rede de interação, reconstruir termos próximos ao cálculo lambda e baixá-los em pequenos pedaços para C, minimizando o overhead de runtime
    A motivação honesta é que, com Bend, é difícil superar kernels de GPU escritos à mão em coisas como workloads de ML. Em teoria, o HVM pode servir como cola para juntar kernels de computação e paralelizar a ordem de execução, mas, para isso, é preciso uma boa FFI
    Redes de interação são difíceis de traduzir através de uma fronteira de FFI, mas, se você colocar nós de kernel de computação de FFI dentro da rede de interação e compilar a rede para C, dá para recuperar uma FFI razoável sem overhead de tradução
    Outra opção é implementar o HVM em hardware; estou mexendo um pouco nisso em um FPGA sobrando

    • É ao mesmo tempo um interpretador que roda na GPU e também um compilador para C e CUDA nativos
      Ele não tem SPIR-V como alvo direto, mas isso está nos planos
      O compilador C entrega o ganho de velocidade esperado, isto é, 3 a 4 vezes e em breve mais do que isso, mas o runtime CUDA não obteve um grande ganho de velocidade em comparação com a versão não compilada
      Acredito que a causa sejam divergências de warp. Em procedimentos não compilados, dá para juntar todas as chamadas de função em um único expansor de funções “genérico” no estilo de interpretador, e as threads do warp conseguem reduzir sem desvios. Pretendo pesquisar essa parte mais a fundo daqui para frente