隐式并行编程：概念、技术与实践

# 隐式并行编程：概念、技术与实践 ## 1 并行编程的背景与愿景 随着科技的发展，包含两到四个处理器的小型对称多处理器（SMP）并行机器变得经济实惠，许多用户都能使用。然而，当升级到 SMP 时，应用程序的性能并没有像升级更快的处理器或更好的内存系统那样显著提升。这是因为目前大多数应用程序都是用顺序语言编写的顺序程序，无法直接利用多个处理器。传统的并行编程方法是在顺序语言中添加并行结构，但这种方法对程序员要求较高，不易掌握。 我们期望未来并行编程成为默认方式，顺序编程只是特殊情况。高中生和本科生编写的第一个程序就是并行程序，之后再学习如何对部分程序进行顺序化处理。实现这一愿景的基础是一种隐式并行编程语言，即使没有可更新状态的概念，也能有很强的表达能力。函数式编程语言正适合这一目的，它提供了纯函数和值的计算模型，没有可更新变量的概念。现代函数式语言具有高阶函数和多态类型系统，表达能力很强，许多应用程序的大部分工作都可以在函数式范式中完成。 ## 2 并行编程的相关技术与概念 ### 2.1 变量与值 - **变量**：在编程中，变量有多种类型和操作。例如，变量有绑定出现和使用出现，有自由变量和绑定变量之分。为避免自由变量捕获问题，需要进行 α - 重命名和重命名绑定变量等操作。在函数式语言中，变量的使用也有其特点。此外，可更新单元与传统变量有所不同。 - **绑定出现**：变量在特定作用域内被绑定到某个值的出现。 - **使用出现**：变量在表达式中被使用的出现。 - **自由变量**：在表达式中未被绑定的变量。 - **绑定变量**：在表达式中被绑定到某个值的变量。 - **α - 重命名**：对绑定变量进行重命名，以避免名称冲突。 - **重命名绑定变量**：在需要时对绑定变量进行重命名，确保程序的正确性。 - **可更新单元与传统变量**：可更新单元可以在程序运行过程中更新其值，而传统变量一旦赋值，其值通常不可改变。 - **值**：值是程序中的重要概念。对于数组，有对应的值；基本值是构成程序的基础；函数也可以作为值。值还是 pH 程序的目标，通过堆项将名称绑定到值。此外，值还涉及存储和替换操作，如在 M - 数组、M - 单元和 M - 列表字段中进行存储和替换。 - **数组的值**：数组中存储的具体数据。 - **基本值**：如整数、浮点数等基本数据类型的值。 - **函数作为值**：函数可以作为参数传递给其他函数，也可以作为返回值返回。 - **值的存储**：可以将值存储在单元、M - 数组和 M - 单元中。 - **值的替换**：在 M - 字段、M - 数组和 M - 列表字段中可以进行值的替换操作。 ### 2.2 向量与相关操作 - **向量**：向量在编程中有多种操作。向量的加法可以通过 v_add 函数实现，计算向量长度可以使用 vector_length 函数，还可以将向量转换为广义向量（GV）。向量的内积计算也是常见操作，在 pH 和 Fortran 中对向量的处理有所不同，同时还有稀疏向量的概念。 - **向量加法**：使用 v_add 函数将两个向量对应元素相加。 - **向量长度计算**：使用 vector_length 函数计算向量的长度。 - **向量转换为 GV**：将普通向量转换为广义向量，以便进行更复杂的操作。 - **向量内积计算**：计算两个向量对应元素乘积的和。 - **pH 和 Fortran 中向量处理的差异**：pH 更注重隐式并行性，而 Fortran 可能更侧重于传统的顺序编程。 - **稀疏向量**：向量中大部分元素为零的向量。 ### 2.3 循环与条件表达式 - **while 循环**：while 循环有其一般形式，用于迭代操作。其语义和翻译也有相应规则，在编程中使用 while 循环可以实现特定的逻辑。 - **一般形式**：通常包含循环条件和循环体。 - **迭代操作**：在循环体中执行一系列操作，直到循环条件不满足为止。 - **语义和翻译**：编译器会将 while 循环翻译为特定的机器代码，以实现循环功能。 以下是相关操作的总结表格： | 操作类型 | 具体操作 | 相关函数或概念 | | ---- | ---- | ---- | | 变量操作 | 绑定出现、使用出现、自由变量、绑定变量、α - 重命名、重命名绑定变量、可更新单元与传统变量区分 | 无 | | 值操作 | 数组的值、基本值、函数作为值、值的存储和替换 | v_add、vector_length 等 | | 向量操作 | 向量加法、长度计算、转换为 GV、内积计算、pH 和 Fortran 差异、稀疏向量 | v_add、vector_length 等 | | 循环操作 | while 循环的一般形式、迭代、语义和翻译 | 无 | ### 2.4 并行编程的相关架构与语言 - **研究支持与人员贡献**：相关研究在 MIT 的计算结构组和剑桥研究实验室（CRL）进行。在 MIT，研究得到了国防高级研究计划局（DARPA）的支持；在 CRL，工作得到了数字