Bend
A high-level, massively parallel programming language
Index
- Introduction
- Important Notes
- Install
- Getting Started
- Speedup Example
- 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
# 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
# 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
- Install HVM2 by running:
# HVM2 is HOC's massively parallel Interaction Combinator evaluator.
cargo install hvm
# This ensures HVM is correctly installed and accessible.
hvm --version
- Install Bend by running:
# This command will install Bend
cargo install bend-lang
# This ensures Bend is correctly installed and accessible.
bend --version
Getting Started
Running Bend Programs
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
# 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.
# 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)
bend run-rs sequential_sum.bend -s
Or you can run it using C interpreter (Sequential)
bend run-c sequential_sum.bend -s
If you have a NVIDIA GPU, you can also run in CUDA (Sequential)
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
# 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.
# 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)
bend run-rs parallel_sum.bend -s
Or you can run it using C interpreter (Parallel)
bend run-c parallel_sum.bend -s
If you have a NVIDIA GPU, you can also run in CUDA (Massively parallel)
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 secondsbend run-c: CPU, Apple M3 Max: 0.96 secondsbend run-cu: GPU, NVIDIA RTX 4090: 0.21 seconds
Click here for the Bitonic Sorter code
# 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)))
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!
一门高级的大规模并行编程语言。它用起来像 Python 或 Haskell(支持闭包、 unrestricted recursion、continuation),但无需编写任何线程或锁相关的代码,就能扩展到多核和 GPU 上运行。