Bend

<h1>Bend</h1> <p>一种高级、大规模并行编程语言</p>

简介

Bend提供了类似Python和Haskell等富有表现力的语言的感觉和特性。这包括快速对象分配、对带闭包的高阶函数的完全支持、无限制的递归，甚至是延续。 Bend的可扩展性类似于CUDA，它可以在GPU等大规模并行硬件上运行，几乎可以根据核心数量实现线性加速，而无需显式的并行注解：无需创建线程、锁、互斥量或原子操作。 Bend由HVM2运行时驱动。

重要说明

Bend旨在提高核心数量的扩展性能，支持超过10000个并发线程。
当前版本的单核性能可能较低。
随着我们改进代码生成和优化技术，您可以期待性能的显著提升。
我们仍在努力支持Windows。可以使用WSL2作为替代解决方案。
我们目前仅支持NVIDIA GPU。

安装

安装依赖项

在Linux上

# 如果尚未安装Rust，请安装。
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# 对于Bend的C版本，使用GCC。我们建议使用12.x版本。
sudo apt install gcc

对于CUDA运行时，为Linux安装CUDA工具包 12.x版本。

在Mac上

# 如果尚未安装Rust，请安装。
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# 对于Bend的C版本，使用GCC。我们建议使用12.x版本。
brew install gcc

安装Bend

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

# HVM2是HOC的大规模并行交互组合子评估器。
cargo install hvm

# 这确保HVM正确安装并可访问。
hvm --version

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

# 此命令将安装Bend
cargo install bend-lang

# 这确保Bend正确安装并可访问。
bend --version

入门

运行Bend程序

bend run    <file.bend> # 默认使用C解释器（并行）
bend run-rs <file.bend> # 使用Rust解释器（顺序）
bend run-c  <file.bend> # 使用C解释器（并行）
bend run-cu <file.bend> # 使用CUDA解释器（大规模并行）

# 注意
# 您还可以使用gen-c和gen-cu将Bend编译为独立的C/CUDA文件以获得最佳性能。
# 代码生成器仍处于早期阶段，尚不如GCC和GHC等编译器成熟。
# 您可以使用-s标志获取更多信息，包括：
  # 归约次数
  # 代码运行时间
  # 每秒交互次数（以百万为单位）

测试Bend程序

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

顺序版本：

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

# 在终端中输入此命令
touch sequential_sum.bend

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

# 定义带有两个参数的Sum函数：start和target
def Sum(start, target):
  if start == target:
    # 如果start的值与target相同，则返回start。
    return start
  else:
    # 如果start不等于target，递归调用Sum，
    # 将start增加1，并将结果加到start上。
    return start + Sum(start + 1, target)  

def main():
  # 这相当于 (1 + (2 + (3 + (...... + (999999 + 1000000)))))
  # 注意，这将超过Bend中数字的最大值
  return Sum(1, 1_000_000)

运行文件

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

bend run 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

# 在终端中输入此命令
touch parallel_sum.bend

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

# 定义带有两个参数的Sum函数：start和target
def Sum(start, target):
  if start == target:
    # 如果start的值与target相同，则返回start。
    return start
  else:
    # 如果start不等于target，计算中点（half），
    # 然后递归调用Sum计算两半。
    half = (start + target) / 2
    left = Sum(start, half)  # (Start -> Half)
    right = Sum(half + 1, target)
    return left + right

# 可并行化的从1到1000000的数字总和
def main():
  # 这相当于 (((1 + 2) + (3 + 4)) + ... (999999 + 1000000)...)
  return Sum(1, 1_000_000)

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

运行文件

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

bend run parallel_sum.bend -s

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

bend run-c parallel_sum.bend -s

如果你有NVIDIA GPU，你也可以在CUDA上运行（大规模并行）

bend run-cu parallel_sum.bend -s

在Bend中，只需改变运行命令就可以实现并行化。如果你的代码能够并行运行，它就会并行运行。

加速示例

下面的代码片段实现了一个使用不可变树旋转的双调排序器。这不是你期望在GPU上快速运行的那种算法。然而，由于它使用了分治法，这种方法本质上是并行的，Bend会在多个线程上执行它，无需创建线程，无需显式锁管理。

双调排序器基准测试

bend run：CPU，Apple M3 Max：12.15秒
bend run-c：CPU，Apple M3 Max：0.96秒
bend run-cu：GPU，NVIDIA RTX 4090：0.21秒

<details> <summary><b>点击此处查看双调排序器代码</b></summary>

# 排序网络 = 只需旋转树！
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))

# 旋转子树（蓝色/绿色框）
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))

# 交换远距离值（红色框）
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))

# 向下传播
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))

# 交换单个对
def swap(s, a, b):
  switch s:
    case 0:
      return (a,b)
    case _:
      return (b,a)

# 测试
# -------

# 生成一个大树
def gen(d, x):
  switch d:
    case 0:
      return x
    case _:
      return (gen(d-1, x * 2 + 1), gen(d-1, x * 2))

# 对大树求和
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)

# 对大树排序
def main:
  return sum(20, sort(20, 0, gen(20, 0)))