BSP函数式编程：基于成本方法的示例

# BSP 函数式编程：基于成本方法的示例 ## 1. 批量同步并行 ML（BSML）基础 BSML 基于 8 个原语构建，其中 3 个用于访问机器参数。这些原语的实现依赖于 MPI、PUB 或 OCaml 的 Unix 模块提供的 TCP/IP 函数。BSML 程序是在名为并行向量的并行数据结构上构建的顺序程序，其 ML 类型为 `α par`，表示在 `p` 个处理器的每个处理器上都包含一个类型为 `α` 的值。 ### 1.1 BSML 原语 | 原语 | 描述 | | --- | --- | | `bsp p: unit→int` | 获取处理器数量 | | `bsp l: unit→float` | 获取机器的参数 `l` | | `bsp g: unit→float` | 获取机器的参数 `g` | | `mkpar: (int→α )→α par` | 创建一个并行向量，其中进程 `i` 存储 `(f i)` | | `apply: (α →β ) par→α par→β par` | 将并行函数向量应用于并行参数向量 | | `put: (int→α ) par→(int→α ) par` | 进行通信，返回包含接收值的并行向量 | | `proj: α par→int→α` | 返回一个函数，用于获取并行向量的第 `n` 个值 | | `super: (unit→α )→(unit→β )→α ∗β` | 允许将两个 BSML 表达式作为 BSP 计算的交错线程进行评估 | ### 1.2 BSP 异步阶段编程 使用 `mkpar` 和 `apply` 原语进行 BSP 异步阶段的编程： - `mkpar f = (f 0) · · · (f i) · · · (f (p−1))` - `apply · · · fi · · · · · · vi · · · = · · · (fi vi) · · ·` ### 1.3 通信原语 - `put`：接受一个并行函数向量作为参数，返回包含接收值的并行向量。 - `proj`：`(proj vec)` 返回一个函数 `f`，其中 `(f n)` 返回并行向量 `vec` 的第 `n` 个值。 ### 1.4 `super` 原语 `super` 原语允许将两个 BSML 表达式作为 BSP 计算的交错线程进行评估。其语义与配对相同，但评估方式不同：`E1` 和 `E2` 的异步计算阶段并行运行，然后 `E1` 和 `E2` 的通信阶段合并，只出现一个屏障。如果 `E1` 的评估需要比 `E2` 更多的超级步骤，则 `E1` 的评估继续（反之亦然）。 ```mermaid graph TD; A[开始] --> B[E1 异步计算]; A --> C[E2 异步计算]; B --> D[E1 通信阶段]; C --> D; D --> E[合并通信阶段]; E --> F{E1 超级步骤是否更多}; F -- 是 --> G[继续 E1 评估]; F -- 否 --> H[继续 E2 评估]; G --> I[结束]; H --> I; ``` ## 2. 常用并行函数 ### 2.1 `replicate` 函数 `replicate:α →α par` 创建一个在每个位置都包含相同值的并行向量。 ### 2.2 `apply2` 函数 `apply2:(α →β →γ )→α par→β par→γ par` 用于处理接受两个参数的函数。 ### 2.3 `parfun` 函数 - `parfun:(α →β )→α par→β par` - `parfun2:(α →β →γ )→α par→β par→γ par` 这些函数用于在每个处理器上应用相同的顺序函数，只是应用的参数数量不同。 ### 2.4 总交换操作 `rpl total:α par→α list v0 · · · vp−1` 的结果是 `[v0, . . . , vp−1]`，即每个处理器上的值的列表。 ## 3. BSP 参数的计算 BSP 模型的一个主要优点是其成本模型简单而准确。通过 BSML 实现的程序对机器的 BSP 参数进行基准测试和确定，计算了 3 个库（MPICH、OPEN-MPI 和 PUB）对应的 BSP 参数。 ### 3.1 BSP 参数的变化 | 库 | 参数 `l` 变化 | 参数 `g` 变化 | | --- | --- | --- | | PUB | 准线性增长 | 开始较高，随后更稳定 | | MPI | 有两个跳跃 | 开始较高，随后更稳定 | 参数 `l` 在 PUB 库中准线性增长，而在 MPI 库中有两个跳跃，原因尚不清楚。参数 `g` 开始时较高，随着处理器数量的增加变得更稳定，这可能是由于通信协议和操作系统中的缓冲区管理。 ```mermaid graph LR; A[处理器数量增加] --> B[缓冲区快速填充]; B --> C[消息立即传输]; C --> D[参数 g 更稳定]; ``` ## 4. BSML 中的 BSP 问题示例 为了说明方法，介绍了两个经典问题：埃拉托斯特尼筛法和 N 体计算。对于每个问题，给出了并行方法、BSP 成本公式以及理论性能（取决于 BSP 参数）和实验性能的比较。 ### 4.1 埃拉托斯特尼筛法 埃拉托斯特尼筛法用于生成小于给定整数 `n` 的素数列表。研究了 3 种并行化方法： #### 4.1.1 对数归约方法 使用经典的并行前缀计算（也称为折叠归约），采用分治 BSP 算法。每个处理器 `i` 持有 `i × n / p + 1` 到 `(i + 1) × n / p` 之间的整数，计算局部筛法，然后应用扫描操作。有 `log(p)` 个超级步骤，每个处理器最多发送/接收 2 个值（最大大小为 `√n` 的列表）。BSP 成本为：`log(p) × (√m×m / log(m) + 2 × √n × g + l)`，其中 `m = n / p`。 #### 4.1.2 直接方法 初始分布的负载平衡较差，因此采用循环方式分配整数。每个处理器计算局部筛法，然后全局交换小于 `√n` 的整数，应用新的筛法得到素数，最后每个处理器在自己的列表中消除这些素数的倍数。BSP 成本为：