实验 7：并行¶

环境设置¶

Info

你必须在Hive机器上完成（本实验而非本地机器）。如需重新配置Hive机器环境，请参考Lab 0的说明。本次实验需使用Hive机器组：hive1-hive30（替代s275、s277等旧机器）。

在 hive 机器的labs目录中，拉取你在过去实验中可能做过的更改：

git pull origin main

仍然在 hive 机器的labs目录中，拉取本实验的文件：

git pull starter main

如果遇到任何git错误，请查看常见错误页面。

概述¶

在本课程中，我们涵盖三种主要的并行性类型：

数据级并行性（SIMD）
线程级并行性（OpenMP）
进程级并行性（Open MPI）

本实验将涉及数据级并行性（DLP）和线程级并行性（TLP）。你将在作业和项目中接触到其他形式的并行性。

SIMD¶

阅读Intel Intrinsics Guide以了解可用的 SIMD 指令（内部函数是一种其实现由编译器处理的函数）。Intrinsics Naming and Usage documentation将有助于理解该文档。

hive 机器支持 SSE、SSE2、SSE3、SSSE3、SSE4.1、SSE4.2、AVX 和 AVX2，因此你可以在过滤器列表中勾选这些选项。其他一些指令集也受支持，但在本实验中我们可以忽略它们。

虽然本节没有需要提交的内容，但阅读文档对本实验的其他练习和项目 4 非常有用。

示例：循环展开¶

ex1.c中的sum()函数是一个未优化的实现，用于对大型数组（约2^16个元素）中值大于等于128的元素求和。我们使用一个外层循环重复求和OUTER_ITERATIONS（约2^14）次，以便我们可以进行更准确的运行时间测量来计算加速比。我们通过计算开始和结束时间戳（使用clock()）之间的差值来计时代码的执行。文件ex1_test.c包含一个main函数，用于运行各种sum函数并计算它们的加速比。

让我们看看sum_unrolled()。这个函数是将sum函数展开四次的结果。内层循环每次迭代处理 4 个元素，而sum()中的内层循环每次迭代处理 1 个元素。注意主循环后的额外循环 —— 由于主循环以 4 个元素为一组遍历数组，我们需要一个尾部循环来处理长度不是 4 的倍数的数组。

在本实验中，我们提供了Makefile，因此请使用提供的make命令而不是gcc来编译你的代码。尝试编译并运行代码：

make ex1
./ex1

展开后的函数应该会快一点，虽然不会快太多。

问题：如果循环展开有帮助，为什么我们不把所有循环都展开？

展开后的代码更难读和写。除非你打算再也不看这段代码，否则代码的可读性可能会超过循环展开的好处！
有时，编译器会自动展开你写的简单循环！重点是 “有时”—— 很难弄清楚现代编译器会执行哪些神奇的操作（见下一段中的 Godbolt）。为了演示，在本实验中我们禁用了编译器优化。
循环展开意味着更多的指令，这意味着更大的程序和可能更差的缓存行为！
我们在ex1.c中的简化示例使用已知的数组大小。如果你不知道你正在处理的数组的大小，你展开的循环可能不适合该数组！

可选：你可以通过将代码输入到这个链接的代码环境中，来可视化向量和不同函数如何协同工作！

另一个可能帮助你理解 SIMD 指令行为的有趣工具是Godbolt Compiler Explorer项目。当你需要优化任何代码时，它也可以提供很多见解。

练习 1：编写 SIMD 代码¶

以下代码演示了如何使用 SIMD 指令对一个 8 元素的整数数组求和。在这个例子中，我们的寄存器是 128 位，整数是 32 位。这意味着我们可以在一个寄存器中放入 4 个整数。运行

int arr[8] = {3, 1, 4, 1, 5, 9, 2, 6};
// 初始化求和向量为{0, 0, 0, 0}
__m128i sum_vec = _mm_setzero_si128();

// 将数组元素0-3加载到临时向量寄存器
__m128i tmp = _mm_loadu_si128((__m128i *) arr);
// 添加到现有的求和向量
sum_vec = _mm_add_epi32(sum_vec, tmp);
// sum_vec = {3, 1, 4, 1}

// 将数组元素4-7加载到临时向量寄存器
tmp = _mm_loadu_si128((__m128i *) (arr + 4));
// 添加到现有的求和向量
sum_vec = _mm_add_epi32(sum_vec, tmp);
// sum_vec = {3 + 5, 1 + 9, 4 + 2, 1 + 6}

// 创建临时数组来保存sum_vec的值
// 我们必须将向量存储到数组中才能访问各个值（如下所示）
int tmp_arr[4];
_mm_storeu_si128((__m128i *) tmp_arr, sum_vec);
// 将sum_vec中的值收集到一个整数中
int sum = tmp_arr[0] + tmp_arr[1] + tmp_arr[2] + tmp_arr[3];

对 8 个元素求和需要做很多工作。然而，这个过程极大地提高了对大型数组元素求和的性能。

实现sum_simd()，一个sum()的向量化版本。
复制你的sum_simd()代码到sum_simd_unrolled()并将其展开4 次。不要忘记尾部情况！

提示¶

你只需要用 SIMD 对内部循环进行向量化。可以使用以下内部函数来实现：
__m128i _mm_setzero_si128() - 返回一个 128 位的零向量
__m128i _mm_loadu_si128(__m128i *p) - 返回存储在指针p处的 128 位向量
__m128i _mm_add_epi32(__m128i a, __m128i b) - 返回向量(a_0 + b_0, a_1 + b_1, a_2 + b_2, a_3 + b_3)
void _mm_storeu_si128(__m128i *p, __m128i a) - 将 128 位向量 a 存储到指针p处
__m128i _mm_cmpgt_epi32(__m128i a, __m128i b) - 返回向量(a_i > b_i ? 0xffffffff : 0x0 for i from 0 to 3)。换句话说，如果a[32*i : 32*(i+1)] > b[32*i : 32*(i+1)]，则out[32*i : 32*(i+1)]全为 1，否则全为 0。
__m128i _mm_and_si128(__m128i a, __m128i b) - 返回向量(a_0 & b_0, a_1 & b_1, a_2 & b_2, a_3 & b_3)，其中 & 表示按位与运算符
不要在内部循环完成之前使用存储函数（_mm_storeu_si128）！事实证明，存储操作的成本很高，在每次迭代中执行存储实际上会导致代码变慢。然而，如果你等到外部循环完成后再存储，可能会有溢出问题。
仔细阅读上面表格中的函数声明！你会注意到 loadu 和 storeu 接受__m128i*类型的参数。你可以将一个int数组转换为__m128i指针。

测试¶

要编译和运行你的代码，请运行以下命令（提醒：请使用make，而不是gcc）：

make ex1
./ex1

在 hive 机器上， naive 版本的运行时间约为 7 秒，你的 SIMD 化版本应该在 1-2 秒内运行完。展开的 SIMD 化版本比sum_simd稍快，但很可能只快几分之一秒。

自动评分器的测试与ex1_test.c中的类似，但可能有不同的常量（NUM_ELEMS和OUTER_ITERATIONS）和降低的加速比要求（以补偿自动评分器资源的更多可变性）。

常见错误¶

以下是工作人员在本练习的实现中注意到的常见错误。

忘记尾部情况中的条件：在添加内容到求和结果之前，我们一直在检查什么条件？
添加到未初始化的数组：如果你在没有初始化结果数组的情况下向其中添加内容，你是在向垃圾数据添加内容，这会使数组仍然是垃圾数据！
重新初始化求和向量：确保你没有为内部循环的每次迭代创建一个新的求和向量！
尝试将求和向量存储到long long int数组中：使用 int 数组。这个函数的返回值确实是long long int，但这是因为int不足以容纳所有外部循环迭代中所有值的总和。long long int和int有不同的位宽，所以将int数组存储到long long int中会产生不同的数字！

一般 SIMD 建议¶

关于使用 SIMD 指令的一些一般建议：

注意内存对齐。例如，_m256d _mm256_load_pd (double const * mem_addr)不能处理未对齐的数据 —— 你需要_m256d _mm256_loadu_pd。同时，如果你可以控制内存分配，保持数据对齐几乎总是可取的（可以使用特殊的内存分配 API 来实现）。对齐的加载可以作为内存操作数折叠到其他操作中，这会稍微减少代码大小和吞吐量。现代 CPU 对未对齐加载有很好的支持，但当加载跨越缓存行边界时，仍然会有显著的性能损失。
回想一下本学期早些时候你学到的各种 CPU 流水线冒险。数据冒险会严重影响性能。也就是说，如果你没有得到期望的性能，你可能需要检查相邻 SIMD 操作中的数据依赖关系。

OpenMP¶

OpenMP 代表Open specification for Multi-Processing（开放式多处理规范）。它是一个提供 C 接口的框架。它不是 C 语言的内置部分 —— 大多数 OpenMP 特性是编译器指令。（你过去见过的一个编译器指令示例是#include。）

使用 OpenMP 进行多线程编程的好处包括：

一个非常简单的接口，允许程序员将程序分为串行区域和并行区域。
方便的同步控制（线程中的数据竞争错误很难追踪）。

示例：OpenMP Hello World¶

考虑示例 hello world 程序（openmp_example.c），它从每个线程打印"hello world from thread #"：

int main() {
    #pragma omp parallel
    {
        int thread_id = omp_get_thread_num();
        printf("hello world from thread %d\n", thread_id);
    }
}

这个程序将创建一组并行线程。每个线程打印一个 hello world 消息，以及它自己的线程编号。

让我们分解#pragma omp parallel行：

#pragma告诉编译器，该行的其余部分是一个指令。
omp声明该指令是针对 OpenMP 的。
parallel表示下面的块语句 —— 大括号（{/}）内的部分 —— 应该由不同的线程并行执行。

重要在编写你自己的代码时，确保将左大括号放在新的一行。不要把它和指令放在同一行。

你可以通过设置环境变量OMP_NUM_THREADS或在程序中的并行部分之前使用omp_set_num_threads函数来更改 OpenMP 线程的数量。

尝试运行程序：

make openmp_example
./openmp_example

如果你多次运行./openmp_example，你可能会注意到打印的数字并不总是按递增顺序排列，而且很可能在不同的运行中有所不同。这是因为我们没有指定任何类型的同步选项，所以 OpenMP 不会强制执行任何执行顺序。（稍后会有更多相关内容。）同样重要的是要注意，变量thread_id是在并行块内部定义的，这意味着每个线程都有自己的thread_id副本。一般来说，在 OpenMP 中，在并行块内部声明的变量是每个线程私有的，而在并行块外部声明的变量在所有线程之间共享。有一些方法可以覆盖这一点，但稍后会详细介绍。

OpenMP 指令¶

OpenMP 指令的用法可以在OpenMP 摘要卡上找到。

For¶

在作业 9 中，你手动将for循环中的迭代分配给各个线程。OpenMP 可以使用for指令自动处理这个问题！你可以在现有的#pragma omp parallel中添加#pragma omp for到一个for循环，或者单独使用#pragma omp parallel for。

Critical¶

临界区中的代码在任何时候只能由单个线程执行。因此，拥有临界区自然可以防止多个线程读写相同的数据，否则会导致数据竞争。OpenMP 提供了critical原语，允许你在临界区中执行计算。

Reduction¶

临界区可能很慢，因此 OpenMP 有一种内置的方法通过使用reduction关键字来减少这个问题。reduction关键字将通过自动减少临界区中包含的代码量来提高代码的并行性。要使用这个关键字，你必须指定应该在临界区中的变量以及对该变量执行的操作。

练习 2：OpenMP 点积¶

乍一看，实现点积似乎与练习 1 中的v_add没有太大不同，因为我们现在只需要执行元素级乘法而不是加法。挑战在于如何将乘积添加到一个变量中（也就是归约）以得到我们的最终答案。如果多个线程试图同时将它们的结果添加到同一个变量中，将会导致数据竞争，这将导致不正确的结果。

现在尝试运行测试，只有 naive 解决方案应该通过，因为其他优化尚未实现。

make ex2
./ex2

使用 OpenMP 和临界区实现dotp_critical。
注意，随着线程数量的增加，性能会变得更差吗？通过将所有归约工作放在临界区中，我们已经扁平化了并行性，使得一次只有一个线程可以做有用的工作（这与线程级并行性的理念不完全一致）。
这种竞争是有问题的；每个线程都在不断争夺临界区，并且在任何时候只有一个线程在取得进展。随着线程数量的增加，竞争也会增加，性能也会受到影响。
使用 OpenMP 和归约语句实现dotp_reduction。
提示：应该一次只能由一个线程访问的变量是global_sum，对它执行的操作是加法（+）。
使用 OpenMP 和归约的思想实现dotp_manual_reduction，但不要使用reduction关键字。
提示：为每个线程创建变量，并且仅在绝对必要时才累加到最终总和中。在你的解决方案中，你可能需要使用#pragma omp critical。