Bend

一种高级、大规模并行编程语言

目录

1. 简介
2. 重要说明
3. 安装
4. 入门指南
5. 加速示例
6. 其他资源

简介

Bend 提供了类似 Python 和 Haskell 等表达性语言的感觉和功能。这包括快速的对象分配、对带有闭包的高阶函数的完全支持、无限制的递归，甚至延续 (continuations)。
Bend 像 CUDA 一样扩展，它运行在 GPU 等大规模并行硬件上，基于核心数量实现近乎线性的加速，且无需显式的并行标注：无需线程创建、锁、互斥锁或原子操作。
Bend 由 HVM2 运行时驱动。

重要说明

• Bend 旨在在核心扩展性能方面表现出色，支持超过 10000 个并发线程。
• 当前版本单核性能可能较低。
• 随着我们推进代码生成和优化技术，您可以期待性能有显著提升。
• 我们仍在努力支持 Windows。请使用 WSL2 作为替代方案。
• 我们目前仅支持 NVIDIA 显卡。

安装

安装依赖项

在 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

对于 CUDA 运行时，请为 Linux 安装 CUDA toolkit 12.x 版本。

在 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

安装 Bend

1. 通过运行以下命令安装 HVM2：

# HVM2 is HOC's massively parallel Interaction Combinator evaluator.
cargo install hvm

# This ensures HVM is correctly installed and accessible.
hvm --version

2. 通过运行以下命令安装 Bend：

# This command will install Bend
cargo install bend-lang

# This ensures Bend is correctly installed and accessible.
bend --version

入门指南

运行 Bend 程序

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)

测试 Bend 程序

下面的示例计算从 start 到 target 范围内所有数字的和。它可以写成两种不同的方法：一种是本质上顺序执行的（因此无法并行化），另一种是易于并行化的。（为了可见性，我们将在大多数示例中使用 -s 标志）

顺序版本：

首先，创建一个名为 sequential_sum.bend 的文件

# Write this command on your terminal
touch sequential_sum.bend

然后使用文本编辑器打开文件 sequential_sum.bend，复制以下代码并粘贴到文件中。

# 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)

运行文件

您可以使用 Rust 解释器（顺序执行）运行它

bend run-rs sequential_sum.bend -s

或者您可以使用 C 解释器（顺序执行）运行它

bend run-c sequential_sum.bend -s

如果您有 NVIDIA GPU，也可以使用 CUDA 运行（顺序执行）

bend run-cu sequential_sum.bend -s

在此版本中，下一个要计算的值取决于之前的总和，这意味着在当前计算完成之前无法继续。现在，让我们看看易于并行化的版本。

可并行化版本：

首先关闭旧文件，然后进入终端创建 parallel_sum.bend

# Write this command on your terminal
touch parallel_sum.bend

然后使用文本编辑器打开文件 parallel_sum.bend，复制以下代码并粘贴到文件中。

# 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)

在此示例中，(3 + 4) 的求和不依赖于 (1 + 2)，意味着它可以并行运行，因为两个计算可以同时发生。

运行文件

您可以使用 Rust 解释器（顺序执行）运行它

bend run-rs parallel_sum.bend -s

或者您可以使用 C 解释器（并行）运行它

bend run-c parallel_sum.bend -s

如果您有 NVIDIA GPU，也可以使用 CUDA 运行（大规模并行）

bend run-cu parallel_sum.bend -s

在 Bend 中，只需更改运行命令即可进行并行化。如果您的代码可以并行运行，它就会并行运行。

加速示例

下面的代码片段实现了一个带有不可变树旋转 (immutable tree rotations) 的 比特尼克排序器 (bitonic sorter)。这通常不是你会预期能在 GPU 上快速运行的算法类型。然而，由于它采用了本质上具有并行性的分治法 (divide and conquer)，Bend 将在多个线程上执行它，无需创建线程，也无需显式的锁管理 (lock management)。

比特尼克排序器基准测试

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

# 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)))

如果你对某些其他算法感兴趣，可以查看我们的 示例文件夹

其他资源

• 要了解 Bend 背后的技术，请查阅 HVM2 论文。
• 我们正在编写官方文档，在此期间，若要了解更深入的说明，请查看 GUIDE.md
• 在 FEATURES.md 阅读关于我们功能的信息。
• Bend 由 HigherOrderCO 开发 —— 加入我们的 Discord!

Bend 快速上手指南

Bend 是一种高级、大规模并行的编程语言。它支持在 GPU 等大规模并行硬件上运行，无需显式编写多线程代码即可实现线性加速。

环境准备

• 操作系统: 推荐 Linux 或 macOS。Windows 用户请使用 WSL2。
• 硬件要求: 支持 NVIDIA GPU（用于 CUDA 模式）。
• 前置依赖:
  • Rust: 用于编译和运行。
  • GCC: C 语言编译器（建议版本 12.x 以下）。
  • CUDA Toolkit: 如需使用 GPU 加速，请安装 Linux 版 CUDA 12.x。

安装步骤

1. 安装基础依赖

Linux:

# 安装 Rust
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# 安装 GCC
sudo apt install gcc

# 安装 CUDA Toolkit (仅需要 GPU 加速时)
# 请参考官方下载页面：https://developer.nvidia.com/cuda-downloads?target_os=Linux

macOS:

# 安装 Rust
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# 安装 GCC
brew install gcc

2. 安装 Bend 运行时与工具

# 安装 HVM2 运行时
cargo install hvm
hvm --version

# 安装 Bend 语言
cargo install bend-lang
bend --version

基本使用

运行程序

Bend 提供了多种解释器模式，可根据需求选择：

• bend run <file.bend>: 默认使用 C 解释器（并行）。
• bend run-rs <file.bend>: 使用 Rust 解释器（串行）。
• bend run-cu <file.bend>: 使用 CUDA 解释器（大规模并行，需 NVIDIA GPU）。

添加 -s 参数可显示执行统计信息（如耗时、交互次数等）。

示例：并行求和

创建一个名为 parallel_sum.bend 的文件，内容如下：

# 定义函数 Sum，计算从 start 到 target 的并行求和
def Sum(start, target):
  if start == target:
    return start
  else:
    half = (start + target) / 2
    left = Sum(start, half)
    right = Sum(half + 1, target)
    return left + right

def main():
  return Sum(1, 1_000_000)

在终端中运行该文件（以 C 解释器为例）：

bend run-c parallel_sum.bend -s

若拥有 NVIDIA GPU，可使用 CUDA 模式获得更高性能：

bend run-cu parallel_sum.bend -s

注意: 如果代码逻辑本身支持并行，只需更改运行命令，Bend 会自动利用多核或 GPU 进行加速。