- Bend est un langage de programmation parallèle de haut niveau qui vise à combiner l’expressivité de langages comme Python et Haskell avec l’exécution massivement parallèle de type CUDA, et fonctionne sur le runtime HVM2
- Il prend en charge les fonctions d’ordre supérieur avec closures, l’allocation rapide d’objets, la récursion sans limite et les continuations, tout en s’exécutant sur du matériel parallèle comme les GPU sans notation explicite de parallélisation comme la création de threads, les verrous, les mutex ou les opérations atomiques
- Son objectif de conception actuel est la montée en performance en fonction du nombre de cœurs, avec la prise en charge de plus de 10 000 threads simultanés, mais la version actuelle peut avoir des performances monocœur faibles et des améliorations de génération de code et d’optimisation sont en cours
- Les modes d’exécution sont répartis entre
bend run-rs,bend run-cetbend run-cu, et pour le code parallélisable il suffit de changer la commande d’exécution pour lancer l’exécution parallèle via l’interpréteur C ou l’interpréteur CUDA - Le support de Windows est encore en cours, donc WSL2 est l’alternative, et l’exécution sur GPU ne prend actuellement en charge que les GPU NVIDIA
Le modèle de programmation visé par Bend
- Bend est un langage de programmation conçu pour s’exécuter sur du matériel massivement parallèle tout en conservant l’ergonomie d’un langage de haut niveau
- Il offre des fonctionnalités de langages expressifs comme Python et Haskell
- allocation rapide d’objets
- fonctions d’ordre supérieur avec closures
- récursion sans limite
- continuations
- Comme CUDA, il s’exécute sur du matériel massivement parallèle tel que les GPU, avec pour objectif une accélération presque linéaire en fonction du nombre de cœurs
- Pour l’exécution parallèle, il n’est pas nécessaire d’écrire soi-même
- la création de threads
- des verrous
- des mutex
- des opérations atomiques
- Le runtime utilise HVM2
Limites actuelles et points d’attention
- Bend se concentre sur la montée en performance selon le nombre de cœurs et est conçu pour prendre en charge plus de 10 000 threads simultanés
- La version actuelle peut avoir de faibles performances monocœur
- Des améliorations de performance sont attendues à mesure que la génération de code et les techniques d’optimisation progressent
- Le support de Windows est encore en cours, et WSL2 peut être utilisé comme alternative
- Le support GPU est actuellement limité aux GPU NVIDIA
Installation et modes d’exécution
- Sous Linux comme sur Mac, l’installation de Rust est nécessaire
- La version C de Bend utilise GCC, et le README recommande GCC 12.x ou inférieur
- Pour utiliser le runtime CUDA, il faut installer le CUDA Toolkit 12.x pour Linux
- HVM2 s’installe avec
cargo install hvm, et Bend aveccargo install bend-lang - Les commandes d’exécution d’un programme Bend varient selon l’exécuteur
bend run <file.bend>: utilise par défaut l’interpréteur C, exécution parallèlebend run-rs <file.bend>: utilise l’interpréteur Rust, exécution séquentiellebend run-c <file.bend>: utilise l’interpréteur C, exécution parallèlebend run-cu <file.bend>: utilise l’interpréteur CUDA, exécution massivement parallèle
gen-cetgen-cupermettent de compiler en fichiers C/CUDA autonomes- Le générateur de code en est encore à un stade initial et n’est pas aussi mature que des compilateurs comme GCC ou GHC
- Le flag
-spermet de voir le nombre de réductions, le temps d’exécution et le nombre d’interactions par seconde
Exemple de somme séquentielle et de somme parallèle
- L’exemple de somme du README compare deux façons d’écrire du code qui additionne les nombres de
startàtarget - La version séquentielle ajoute la valeur actuelle de
startau résultat deSum(start + 1, target)- le calcul suivant dépend du résultat de la somme précédente
- on ne peut pas passer à l’étape suivante avant la fin du calcul courant, donc cela ne peut pas être parallélisé
- l’exemple appelle
Sum(1, 1_000_000)et inclut un commentaire indiquant que cela peut dépasser la valeur maximale des nombres de Bend
- La version parallélisable découpe l’intervalle en deux moitiés puis calcule récursivement les sommes de gauche et de droite
- le calcul de
(3 + 4)ne dépend pas de celui de(1 + 2) - les deux calculs peuvent avoir lieu en même temps, ce qui permet une exécution parallèle
- le calcul de
- Dans Bend, si le code peut s’exécuter en parallèle, il suffit de changer la commande d’exécution pour obtenir une exécution parallèle
Exemple de performances du Bitonic Sorter
- Le README présente comme exemple de vitesse un bitonic sorter implémenté avec des rotations d’arbres immuables
- Ce type d’algorithme n’est pas a priori censé être rapide sur GPU, mais grâce à une approche diviser pour régner, Bend l’exécute sur plusieurs threads
- Aucune création explicite de threads ni gestion de verrous n’est nécessaire
- Les résultats de benchmark sont les suivants
bend run-rs: CPU, Apple M3 Max, 12,15 secondesbend run-c: CPU, Apple M3 Max, 0,96 secondebend run-cu: GPU, NVIDIA RTX 4090, 0,21 seconde
- D’autres algorithmes sont disponibles dans le dossier examples
Références
- La technologie sous-jacente de Bend est présentée dans le paper de HVM2
- La documentation officielle est en cours de rédaction, et des explications plus approfondies figurent dans GUIDE.md
- La liste des fonctionnalités est disponible dans FEATURES.md
- Bend est développé par HigherOrderCO
1 commentaires
Avis de Hacker News
J’ai porté l’exemple
sumen Python pur : avecpypy3, il prend 4,478 s en monothread, et avec Python 3.12, 1 min 42,148 s.À l’inverse, la version monothread de Bend tourne depuis 42 minutes sur mon ordinateur portable et n’a toujours pas fini, tout en utilisant 6 Go de mémoire. Environnement : Intel(R) Core(TM) i7-1270P 12th Gen, Ubuntu 24.04.
Si c’est aussi lent sur un exemple aussi simple, il est difficile d’espérer grand-chose pour des tâches complexes, et je me demande si cela a été testé ou développé dans des environnements autres que Mac/aarch64. Je compte le relancer plus tard avec l’argument
-s.Dans l’exemple
sum, Bend a un gros désavantage : il alloue 2 nœuds IC pour chaque opération numérique, contrairement à Python. Comme avec HVM1, nous devrions bientôt pouvoir l’éviter, mais ce n’est pas encore implémenté dans HVM2.L’essentiel du travail sur Bend a consisté à rendre l’évaluateur parallèle correct, et exécuter des closures ainsi qu’une récursion non bornée sur GPU a été extrêmement difficile. Comme nous venons tout juste de terminer cette partie, très peu d’efforts ont été consacrés aux micro-optimisations, et la génération de code de HVM2 est encore vraiment médiocre.
En comparant avec un cas où les deux côtés effectuent la même quantité d’allocations, comme l’exemple
Bitonic Sort, on aura une vision plus juste des performances réelles. HVM1 n’était qu’environ 3 fois plus lent que GHC sur un seul cœur, et je pense que HVM2 pourra atteindre ce niveau assez bientôt.Je comprends que dire « c’est encore mauvais, mais ça va s’améliorer » puisse sembler décevant. Mais maintenant que les bases sont en place, les micro-optimisations sont la partie la plus facile, et je suis convaincu que les performances vont beaucoup progresser à partir de là.
Ce langage vise des applications GPU à fort volume de calcul et en est encore à ses débuts. La récursion n’est pas l’application cible, et je ne pense pas que ce soit un benchmark pertinent.
C’est similaire à la manière dont ISPC peut compiler du code pour exécuter simultanément 32 appels de fonction par thread CPU. Par exemple, avec AVX512 et des données 16 bits, on peut avoir 32 cœurs × 2 threads SMT par cœur × 32 exécutions générées par le compilateur, soit 2048 exécutions simultanées.
Une implémentation idiomatique en Python aurait utilisé une boucle et un état mutable.
+0est nécessaire. Ce n’est pas une opération qui ne fait rien ?Il y a beaucoup de réactions négatives dans ce fil, mais je veux quand même adresser un grand bravo à l’auteur pour être allé jusque-là.
Comme projet similaire, je ne connais guère que Futhark, mais sa syntaxe à la Haskell peut être assez déroutante pour des développeurs généralistes habitués à C/C++/Python/JS/Java, etc.
Mon plus grand regret est que, contrairement à Futhark, il ne cible que CUDA ou le multicœur. Futhark peut cibler OpenCL, CUDA, ISPC, HIP, le CPU monocœur et le CPU multicœur. Je pense que les problèmes de performance signalés par d’autres peuvent tout à fait être résolus.
Court exemple : https://github.com/m4rs-mt/ILGPU/blob/master/Samples/SimpleM...
Il prend aussi en charge des fonctionnalités avancées comme l’assembleur PTX inline : https://github.com/m4rs-mt/ILGPU/blob/master/Samples/InlineP...
NVIDIA a aussi soutenu des variantes Haskell, .NET, Java et Julia pour CUDA, il existe également un JIT Python, et ils collaborent aussi avec l’équipe de Mojo.
Il a été créé par Tucker Taft, qui travaille sur la conception d’Ada depuis 1995, et certaines fonctionnalités parallèles de ParaSail ont été intégrées à Ada 2022.
L’OP apporte certaines des choses les plus intéressantes vues récemment sur HN, et je trouve dommage qu’il reçoive surtout de longues critiques alors qu’il est évident que c’est encore une version initiale.
En revanche, les critiques peuvent varier à l’infini, car il y a peu de façons d’avoir raison et beaucoup de façons de se tromper. Résultat : il n’y a que quelques commentaires positifs, et la plupart ressemblent à des critiques ou à des « il faudrait aussi faire ceci ». Ce n’est pas tant la faute d’individus en particulier que le reflet d’une certaine culture technique actuelle.
Si les gens ne faisaient que cacher les vérités brutales derrière des applaudissements, le monde s’effondrerait.
Les critiques signifient aussi que les gens s’intéressent aux idées et à l’approche et s’y impliquent ; c’est donc souvent un signal positif.
Mais critiquer les projets qui avancent des affirmations trompeuses, insuffisamment étayées ou fausses est aussi une bonne norme sociale, car cela contribue à réduire ce type d’affirmations.
Ce qui est difficile à comprendre paraît souvent menaçant, et la critique est une réaction fréquente face à une menace, ainsi que la façon de répondre qui exige le moins de compréhension.
La page d’accueil est vraiment bien faite. On voit immédiatement ce que ça fait.
Les gens qui manipulent des « combinateurs » ont généralement envie d’employer beaucoup de jargon intimidant, mais l’OP montre concrètement l’idée simple derrière l’outil. J’apprécie que ce soit l’inverse de l’approche académique qui montre tout jusqu’au dernier détail sans jamais dire de quoi il s’agit vraiment. Il en faudrait davantage comme ça.
C’est théoriquement élégant et je comprends la proposition de valeur, mais honnêtement je ne pense pas que cela devienne réellement un outil pertinent.
Ce sont mes notes après une première impression et un survol de l’article. Je sais que c’est un logiciel très jeune.
Bend ressemble à un DSL très limité. Pas de FFI, aucun moyen d’interagir avec des buffers bruts, et le format de flottants 24 bits est étrange.
Il y a une raison pour laquelle l’IC n’est pas grand public. Les performances risquent fort de rester épouvantables, et le parcours de graphes colle mal au matériel.
Le principe de la réduction optimale est valable, mais au final il faut écrire les kernels d’une façon parallélisable. Autrement dit, il ne doit pas y avoir de dépendances de données, et il faut aussi tenir compte de l’usage de la récursion.
Il n’y a pas d’exemple sérieux comparant directement du code Bend/HVM avec un programme OMP/CUDA équivalent. Difficile d’évaluer à quel point la complexité d’implémentation baisse et quelles performances on obtient.
Dans le calcul parallèle haute performance réel, on trouve très peu de structures arborescentes et les tableaux règnent en maîtres. C’est dû aux propriétés physiques de la mémoire au niveau matériel. Ce qui fonctionne le mieux sur des buffers de mémoire contigus et mutables, ce sont les boucles. Je regarderai si HVM implémente cela.
Pour l’instant, cela semble presque totalement isolé des données externes, très lent, et ressemble à un langage à moitié mûr posant une énorme abstraction au-dessus du matériel. Il n’exploite pas non plus des fonctions comme les caches multiniveaux, les Tensor Cores, le SIMD ou les opérations atomiques.
Désolé si cela paraît rude, mais je trouve toujours l’implémentation technique et le contexte théorique très intéressants. Simplement, je ne suis pas encore convaincu de son utilité dans le monde réel.
La FFI est déjà implémentée, mais pas encore publiée. Nous voulons la sortir avec le rendu graphique, et je pense que ce sera assez impressionnant.
Haskell/GHC utilise aussi des graphes et des arbres, mais personne ne dira que ce n’est pas pratique. Il est vrai que les tableaux règnent, mais beaucoup d’algorithmes modernes qui se prêtent mal aux tableaux — compilateurs, vérificateurs de types, solveurs, etc. — sont implémentés en Haskell.
La principale raison pour laquelle l’IC n’est pas rapide est que personne n’a vraiment fait le travail d’optimisation bas niveau par-dessus. Les implémentations existantes étaient toutes terriblement inefficaces, et mon travail jusqu’ici a surtout consisté à faire en sorte que cela s’exécute correctement sur GPU.
Comme pour le fait qu’il n’y ait même pas encore de boucles, la solution est simplement d’ajouter des boucles. Si vous pensez qu’il y a là une limite fondamentale, vous risquez d’être surpris.
HVM2 est enfin devenu un algorithme correct et extensible ; il est maintenant temps d’optimiser les vraies performances bas niveau.
Dans les algorithmes Fast Multipole ou Barnes-Hut, on utilise l’ordre de Morton ou l’ordre H-index pour réduire les opérations pair à pair en O(n²) à respectivement O(n) et O(n log n). Barnes-Hut est plus courant en astrophysique, tandis que Fast Multipole se voit plus souvent en dynamique moléculaire en chimie.
Il y a 10 ans, j’ai suivi 15-210, le cours d’algorithmes parallèles de CMU. Il expliquait que, la loi de Moore atteignant ses limites, le parallélisme deviendrait l’avenir du calcul, et cela m’avait convaincu au point de vouloir expérimenter.
Mais il n’y avait pas beaucoup d’options pour faire de la programmation parallèle généraliste. Même le SML utilisé en cours n’était pas parallèle ; il y avait à la fin une section avec une extension et CUDA, mais dans mon souvenir c’était limité.
Depuis, Rust m’a permis d’expérimenter un peu le multithreading, et Shadertoy m’a permis de faire des choses créatives avec des shaders. Mais un langage parallèle généraliste sur GPU, j’ai vraiment hâte de pouvoir le prendre en main.
Si 210 vous a plu, https://futhark-lang.org/ pourrait aussi vous intéresser. C’est un langage de la famille ML, il compile vers le GPU et ses performances sont bonnes.
L’idée est très séduisante, mais si je n’ai rien raté, cela semble très lent.
J’ai écrit en C++ une simple boucle qui additionne de 0 à 2³⁰ ; sans optimisation, en mono-thread, elle prend 1,7 s sur mon ordinateur portable, ce qui est comparable aux performances de Bend sur une RTX 4090. Avec
-O3, la boucle est vectorisée et s’exécute en moins de 80 ms.Si on le compare à un programme C qui effectue réellement des allocations, Bend pourrait être plus rapide avec seulement quelques threads.
La génération de code de Bend est encore médiocre, mais ce sont des fruits à portée de main. La majeure partie du travail a consisté à rendre correct un évaluateur parallèle très difficile.
Je sais que ça sonne comme un « faites-nous confiance », mais quand nous commencerons la compilation procédurale, la génération de boucles, etc., les performances mono-thread s’amélioreront nettement. Nous ne l’avons simplement pas encore fait.
Je me demande d’ailleurs si nous n’aurions pas dû attendre un peu plus avant de le publier.
objdumpsi la boucle a réellement été vectorisée, ou si le compilateur l’a simplement optimisée entièrement.Cette boucle provoque un dépassement d’entier signé, ce qui est un comportement indéfini en C++. Le compilateur peut légalement produire n’importe quel résultat.
Pour l’éviter, il faut déclarer
sumenunsigned. Le dépassement d’entier non signé est bien défini, et l’optimisation se produit toujours, mais au moins la correction est garantie.-O3, la boucle est complètement supprimée : https://godbolt.org/z/M1rMY6qM9Ce n’est probablement pas une comparaison équitable.
Bien sûr, je peux aussi passer à côté de l’essentiel.
Je veux féliciter l’auteur. C’est vraiment un travail impressionnant.
Réaliser une parallélisation automatique correcte n’est jamais une tâche facile, et vous pouvez largement en être fier. J’ai hâte de voir comment le projet va évoluer.
Je ne comprends pas pourquoi il y a autant de réactions négatives. On aurait dit une foule en colère, comme des bots qui fouillent le README à la recherche de failles pour détourner le contexte et l’intention du texte.
Passer des heures à débattre sans même prendre 2 minutes pour le lire correctement, c’est ignorant et cruel. L’OP est arrivé jusque-là avec un projet mené seul, donc j’espère qu’il continuera à pousser dans cette voie.
Je me demandais si HVM2 compile les réseaux d’interaction vers, par exemple, SPIR-V, ou s’il s’agit d’un interpréteur qui tourne sur GPU comme le HVM d’origine.
Il y a quelque temps, j’avais essayé de compiler des réseaux d’interaction en C en réduisant autant que possible le programme tout en laissant l’entrée non réduite, en traitant ça comme une optimisation de programme entier. Cibler un langage de shaders ne m’aurait pas semblé beaucoup plus difficile.
En regardant le dépôt, il est indiqué qu’il fournit un langage IR bas niveau pour spécifier des réseaux HVM2, ainsi qu’un compilateur vers C/CUDA : https://github.com/HigherOrderCO/HVM
Mais en y regardant de nouveau, le runtime CUDA de HVM2 ressemble à un interpréteur qui parcourt le graphe en mémoire et applique les réductions : https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
Ce dont je parlais, c’est d’une approche qui parcourt les réseaux d’interaction pour reconstruire un terme proche du lambda-calcul, puis l’abaisse vers C par petits morceaux afin de minimiser le surcoût du runtime.
La motivation honnête, c’est qu’avec Bend il sera difficile de battre des kernels GPU écrits à la main sur des workloads de ML, par exemple. En théorie, HVM pourrait servir de colle pour assembler des kernels de calcul et paralléliser l’ordre d’exécution, mais il faudrait pour cela une bonne FFI.
Les réseaux d’interaction sont difficiles à traduire à travers une frontière FFI, mais si l’on place les nœuds de kernels de calcul FFI dans le réseau d’interaction et qu’on compile le réseau en C, on peut retrouver une FFI raisonnable sans surcoût de traduction.
Une autre option serait d’implémenter HVM en matériel ; je bricole un peu là-dessus sur un FPGA qui traîne.
Il ne cible pas directement SPIR-V, mais c’est un objectif.
Le compilateur C apporte le gain de vitesse attendu, c’est-à-dire 3 à 4×, et bientôt davantage, mais le runtime CUDA n’a pas obtenu de gain significatif par rapport à la version non compilée.
Nous pensons que la cause est la divergence de warp. Dans les procédures non compilées, on peut fusionner tous les appels de fonctions en un unique expanseur de fonctions « générique » de type interpréteur, et les threads du warp peuvent réduire sans branchement. Nous allons étudier ce point plus en profondeur à l’avenir.