Bend

A massively parallel, high-level programming language

19,677 stars Rust Markdown Skills API Spec
AI Prompts & Specs

Repository: HigherOrderCO/Bend


Stars: 19331

README.md

<h1 >Bend</h1>
<p>A high-level, massively parallel programming language</p>

Index


1. Introduction
2. Important Notes
3. Install
4. Getting Started
5. Speedup Example
6. Additional Resources

Introduction

Bend offers the feel and features of expressive languages like Python and Haskell. This includes fast object allocations, full support for higher-order functions with closures, unrestricted recursion, and even continuations.
Bend scales like CUDA, it runs on massively parallel hardware like GPUs, with nearly linear acceleration based on core count, and without explicit parallelism annotations: no thread creation, locks, mutexes, or atomics.
Bend is powered by the HVM2 runtime.


Important Notes

* Bend is designed to excel in scaling performance with cores, supporting over 10000 concurrent threads.
* The current version may have lower single-core performance.
* You can expect substantial improvements in performance as we advance our code generation and optimization techniques.
* We are still working to support Windows. Use WSL2 as an alternative solution.
* We only support NVIDIA Gpus currently.


Install

Install dependencies

#### On Linux

sh
Install Rust if you haven't already.

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
For the C version of Bend, use GCC. We recommend a version up to 12.x.

sudo apt install gcc

For the CUDA runtime install the CUDA toolkit for Linux version 12.x.


#### On Mac

sh
Install Rust if you haven't it already.

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
For the C version of Bend, use GCC. We recommend a version up to 12.x.

brew install gcc


Install Bend

1. Install HVM2 by running:

sh
HVM2 is HOC's massively parallel Interaction Combinator evaluator.

cargo install hvm
This ensures HVM is correctly installed and accessible.

hvm --version

2. Install Bend by running:
sh
This command will install Bend

cargo install bend-lang
This ensures Bend is correctly installed and accessible.

bend --version

Getting Started


#### Running Bend Programs
sh
bend run    <file.bend> # uses the C interpreter by default (parallel)
bend run-rs <file.bend> # uses the Rust interpreter (sequential)
bend run-c  <file.bend> # uses the C interpreter (parallel)
bend run-cu <file.bend> # uses the CUDA interpreter (massively parallel)
Notes

You can also compile Bend to standalone C/CUDA files using gen-c and gen-cu for maximum performance.

The code generator is still in its early stages and not as mature as compilers like GCC and GHC.

You can use the -s flag to have more information on

  # Reductions
  # Time the code took to run
  # Interaction per second (In millions)

#### Testing Bend Programs
The example below sums all the numbers in the range from start to target. It can be written in two different methods: one that is inherently sequential (and thus cannot be parallelized), and another that is easily parallelizable. (We will be using the -sflag in most examples, for the sake of visibility)

#### Sequential version:
First, create a file named sequential_sum.bend

sh
Write this command on your terminal

touch sequential_sum.bend

Then with your text editor, open the file sequential_sum.bend, copy the code below and paste in the file.

py
Defines the function Sum with two parameters: start and target

def Sum(start, target):
  if start == target:
    # If the value of start is the same as target, returns start.
    return start
  else:
    # If start is not equal to target, recursively call Sum with
    # start incremented by 1, and add the result to start.
    return start + Sum(start + 1, target)  
def main():
  # This translates to (1 + (2 + (3 + (...... + (999999 + 1000000)))))
  # Note that this will overflow the maximum value of a number in Bend
  return Sum(1, 1_000_000)

##### Running the file
You can run it using Rust interpreter (Sequential)

sh
bend run-rs sequential_sum.bend -s

Or you can run it using C interpreter (Sequential)

sh
bend run-c sequential_sum.bend -s

If you have a NVIDIA GPU, you can also run in CUDA (Sequential)

sh
bend run-cu sequential_sum.bend -s

In this version, the next value to be calculated depends on the previous sum, meaning that it cannot proceed until the current computation is complete. Now, let's look at the easily parallelizable version.


#### Parallelizable version:
First close the old file and then proceed to your terminal to create parallel_sum.bend

sh
Write this command on your terminal

touch parallel_sum.bend

Then with your text editor, open the file parallel_sum.bend, copy the code below and paste in the file.

py
Defines the function Sum with two parameters: start and target

def Sum(start, target):
  if start == target:
    # If the value of start is the same as target, returns start.
    return start
  else:
    # If start is not equal to target, calculate the midpoint (half),
    # then recursively call Sum on both halves.
    half = (start + target) / 2
    left = Sum(start, half)  # (Start -> Half)
    right = Sum(half + 1, target)
    return left + right
A parallelizable sum of numbers from 1 to 1000000

def main():
  # This translates to (((1 + 2) + (3 + 4)) + ... (999999 + 1000000)...)
  return Sum(1, 1_000_000)

In this example, the (3 + 4) sum does not depend on the (1 + 2), meaning that it can run in parallel because both computations can happen at the same time.

##### Running the file
You can run it using Rust interpreter (Sequential)

sh
bend run-rs parallel_sum.bend -s

Or you can run it using C interpreter (Parallel)

sh
bend run-c parallel_sum.bend -s

If you have a NVIDIA GPU, you can also run in CUDA (Massively parallel)

sh
bend run-cu parallel_sum.bend -s

In Bend, it can be parallelized by just changing the run command. If your code can run in parallel it will run in parallel.


Speedup Examples


The code snippet below implements a bitonic sorter with immutable tree rotations. It's not the type of algorithm you would expect to run fast on GPUs. However, since it uses a divide and conquer approach, which is inherently parallel, Bend will execute it on multiple threads, no thread creation, no explicit lock management.

#### Bitonic Sorter Benchmark

- bend run-rs: CPU, Apple M3 Max: 12.15 seconds
- bend run-c: CPU, Apple M3 Max: 0.96 seconds
- bend run-cu: GPU, NVIDIA RTX 4090: 0.21 seconds

<details>
<summary><b>Click here for the Bitonic Sorter code</b></summary>

py
Sorting Network = just rotate trees!

def sort(d, s, tree):
  switch d:
    case 0:
      return tree
    case _:
      (x,y) = tree
      lft   = sort(d-1, 0, x)
      rgt   = sort(d-1, 1, y)
      return rots(d, s, (lft, rgt))
Rotates sub-trees (Blue/Green Box)

def rots(d, s, tree):
  switch d:
    case 0:
      return tree
    case _:
      (x,y) = tree
      return down(d, s, warp(d-1, s, x, y))
Swaps distant values (Red Box)

def warp(d, s, a, b):
  switch d:
    case 0:
      return swap(s ^ (a > b), a, b)
    case _:
      (a.a, a.b) = a
      (b.a, b.b) = b
      (A.a, A.b) = warp(d-1, s, a.a, b.a)
      (B.a, B.b) = warp(d-1, s, a.b, b.b)
      return ((A.a,B.a),(A.b,B.b))
Propagates downwards

def down(d,s,t):
  switch d:
    case 0:
      return t
    case _:
      (t.a, t.b) = t
      return (rots(d-1, s, t.a), rots(d-1, s, t.b))
Swaps a single pair

def swap(s, a, b):
  switch s:
    case 0:
      return (a,b)
    case _:
      return (b,a)
Testing

-------
Generates a big tree

def gen(d, x):
  switch d:
    case 0:
      return x
    case _:
      return (gen(d-1, x  2 + 1), gen(d-1, x  2))
Sums a big tree

def sum(d, t):
  switch d:
    case 0:
      return t
    case _:
      (t.a, t.b) = t
      return sum(d-1, t.a) + sum(d-1, t.b)
Sorts a big tree

def main:
  return sum(20, sort(20, 0, gen(20, 0)))

</details>

if you are interested in some other algorithms, you can check our examples folder


Additional Resources


- To understand the technology behind Bend, check out the HVM2 paper.
- We are working on an official documentation, meanwhile for a more in depth
explanation check GUIDE.md
- Read about our features at FEATURES.md
- Bend is developed by HigherOrderCO - join our Discord!