HigherOrderCO/Bend
GitHub: HigherOrderCO/Bend
Bend 是一种无需显式并行标注即可自动在 GPU 等大规模并行硬件上运行的高级编程语言，解决了并行编程中手动管理线程和锁的复杂性问题。
Stars: 19723 | Forks: 494
Bend
一种高级、大规模并行的编程语言
## 目录
1. [简介](#introduction)
2. [重要提示](#important-notes)
3. [安装](#install)
4. [快速入门](#getting-started)
5. [加速示例](#speedup-examples)
6. [其他资源](#additional-resources)
## 简介
Bend 提供了类似 Python 和 Haskell 等富有表现力的语言的风格和特性。这包括快速的对象分配、对带有闭包的高阶函数的全面支持、无限制的递归，甚至包括 continuations。
Bend 像 CUDA 一样具备扩展性，它可以运行在 GPU 等大规模并行硬件上，根据核心数量实现近乎线性的加速，并且不需要显式的并行标注：没有线程创建、锁、mutexes 或 atomics。
Bend 由 [HVM2](https://github.com/higherorderco/hvm) 运行时提供支持。
## 重要提示
* Bend 旨在实现核心性能的卓越扩展，支持超过 10000 个并发线程。
* 当前版本的单核性能可能较低。
* 随着我们改进代码生成和优化技术，您可以预期其性能将得到大幅提升。
* 我们仍在努力支持 Windows。请使用 [WSL2](https://learn.microsoft.com/en-us/windows/wsl/install) 作为替代方案。
* [我们目前仅支持 NVIDIA GPU](https://github.com/HigherOrderCO/Bend/issues/341)。
## 安装
### 安装依赖
#### 在 Linux 上
```
# 如果你还没有安装 Rust，请先安装。
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
# 对于 C 版本的 Bend，请使用 GCC。我们推荐使用 12.x 及以下的版本。
sudo apt install gcc
```
对于 CUDA 运行时，请[安装 12.x 版本的 Linux CUDA 工具包](https://developer.nvidia.com/cuda-downloads?target_os=Linux)。
#### 在 Mac 上
```
# 如果你还没有安装 Rust，请先安装。
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
# 对于 C 版本的 Bend，请使用 GCC。我们推荐使用 12.x 及以下的版本。
brew install gcc
```
### 安装 Bend
1. 运行以下命令安装 HVM2：
```
# HVM2 是 HOC 的大规模并行 Interaction Combinator evaluator。
cargo install hvm
# 这确保 HVM 已正确安装并且可以访问。
hvm --version
```
2. 运行以下命令安装 Bend：
```
# 此命令将安装 Bend
cargo install bend-lang
# 这确保 Bend 已正确安装并且可以访问。
bend --version
```
### 快速入门
#### 运行 Bend 程序
```
bend run
# uses the C interpreter by default (parallel)
bend run-rs # uses the Rust interpreter (sequential)
bend run-c # uses the C interpreter (parallel)
bend run-cu # uses the CUDA interpreter (massively parallel)
# 注意事项
# 你还可以使用 gen-c 和 gen-cu 将 Bend 编译为独立的 C/CUDA 文件，以获得最佳性能。
# 代码生成器仍处于早期阶段，不如 GCC 和 GHC 等编译器成熟。
# 你可以使用 -s 标志来获取更多信息
# Reductions
# Time the code took to run
# Interaction per second (In millions)
```
#### 测试 Bend 程序
下面的示例计算从 `start` 到 `target` 范围内所有数字的总和。它可以用两种不同的方法编写：一种是天生顺序执行的（因此无法并行化），另一种则很容易并行化。（为了便于演示，我们将在大多数示例中使用 `-s` 标志）
#### 顺序版本：
首先，创建一个名为 `sequential_sum.bend` 的文件
```
# 在你的终端中输入此命令
touch sequential_sum.bend
```
然后使用您的文本编辑器打开文件 `sequential_sum.bend`，复制下面的代码并将其粘贴到文件中。
```
# 定义带有两个参数的函数 Sum：start 和 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`
```
# 在你的终端中输入此命令
touch parallel_sum.bend
```
然后使用您的文本编辑器打开文件 `parallel_sum.bend`，复制下面的代码并将其粘贴到文件中。
```
# 定义带有两个参数的函数 Sum：start 和 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
# 一个可并行的从 1 到 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 中，只需更改运行命令即可实现并行化。如果您的代码**可以**并行运行，它**就一定**会并行运行。
### 加速示例
下面的代码片段实现了一个带有*不可变树旋转*的 [双调排序器](https://en.wikipedia.org/wiki/Bitonic_sorter)。这不是那种您会期望在 GPU 上快速运行的算法。然而，由于它采用了本质上并行的分而治之方法，Bend 将在多个线程上执行它，不需要线程创建，也不需要显式的锁管理。
#### 双调排序器基准测试
- `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 = 只需旋转树！
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)))
```
如果您对其他算法感兴趣，可以查看我们的 [examples 文件夹](https://github.com/HigherOrderCO/Bend/tree/main/examples)
### 其他资源
- 要了解 Bend 背后的技术，请查看 HVM2 [论文](https://paper.higherorderco.com/)。
- 我们正在编写官方文档，同时如需更深入的了解，
请查看 [GUIDE.md](https://github.com/HigherOrderCO/Bend/blob/main/GUIDE.md)
- 请在 [FEATURES.md](https://github.com/HigherOrderCO/Bend/blob/main/FEATURES.md) 阅读关于我们的功能特性
- Bend 由 [HigherOrderCO](https://higherorderco.com/) 开发 - 加入我们的 [Discord](https://discord.higherorderco.com)！标签：Rust, Vectored Exception Handling, 可视化界面, 并行计算, 编程语言, 网络流量审计, 通知系统, 高性能计算