实验7：并行性

截止日期：4月16日（星期四）晚上11:59:59 PT

Lab Slides

设置

您必须在hive机器（而不是您的本地机器）上完成此实验。如果您需要重新设置hive机器，请参见实验0。

在hive机器上的labs目录中，拉取您在过去实验中可能做出的任何更改：

git pull origin main

仍然在hive机器上的labs目录中，使用以下命令拉取此实验的文件：

git pull starter main

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

概述

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

  • 数据级并行性 (SIMD)
  • 线程级并行性 (OpenMP)
  • 进程级并行性 (Open MPI)

本实验将涵盖DLP和TLP。

示例：循环展开

ex1.c中的sum()函数是一个未优化的实现，用于对大型数组（大约2^16个元素）中值>=128（>127）的元素求和。我们使用外循环重复求和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编译器浏览器项目。当您将来需要优化任何代码时，它也可以提供很多见解。

SIMD

阅读Intel Intrinsics Guide以了解可用的SIMD指令（内联函数是一种实现由编译器处理的函数）。Intrinsics命名和使用文档将有助于理解文档内容。

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

虽然本节没有可交付成果，但阅读文档对本实验中的其他练习非常有用。

练习1：编写SIMD代码(Exercise 1: Writing SIMD Code)

以下代码演示如何使用SIMD指令对一个8元素整数数组进行加法运算。在此示例中，我们的寄存器是128位，整数是32位。这意味着我们可以在一个寄存器中容纳四个整数。

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个元素来说，这是很多工作。然而，这个过程大大提高了对大型数组元素求和的性能。

您的任务是完成以下两个步骤：

  1. 实现 sum_simd()，这是朴素sum()实现的向量化版本。换句话说，使用以下SIMD指令来向量化朴素示例。

  2. 复制您的sum_simd()代码到sum_simd_unrolled()中，并展开4次循环。换句话说，在步骤1之后，将您的向量化代码复制到sum_simd_unrolled()函数中，并对向量化实现进行循环展开。不要忘记处理尾部情况！

提示(Tips)

  • 您只需要用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指针。

测试(Testing)

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

make ex1
./ex1

朴素版本在hive机器上运行约7秒，而您的SIMD版本应该运行约1-2秒。展开的SIMD版本比sum_simd稍快，但很可能只是快几分之一秒。

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

常见错误(Common Bugs)

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

  • 我们在求和什么？：记住我们只对>=128（>127）的值求和。在求和之前我们需要做什么预处理？
  • 在尾部情况中忘记条件判断：在向总和添加内容之前我们一直在检查什么条件？
  • 向未初始化的数组添加值：如果在未初始化结果数组的情况下向其添加值，您是在向垃圾值添加，这会使数组仍然是垃圾！
  • 重新初始化求和向量：确保不要在内层循环的每次迭代中创建新的求和向量！
  • 尝试将求和向量存储到long long int数组中：使用int数组。此函数的返回值确实是long long int，但这是因为int不足以容纳外层循环所有迭代的所有值的总和。long long int和int有不同的位宽度，因此将int数组存储到long long int中会产生不同的数字！

通用SIMD建议(General SIMD Advice)

关于使用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 Directives)

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

For指令

OpenMP可以使用for指令自动将for循环的迭代分配给各个线程。您可以在#pragma omp parallel内的现有for循环中添加#pragma omp for，或者单独使用#pragma omp parallel for。

Critical指令

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

Reduction指令

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

练习2：OpenMP点积(Exercise 2: OpenMP Dot Product)

乍一看，实现点积似乎与练习1没有太大不同，因为我们现在应该执行逐元素乘法而不是加法。挑战在于如何将乘积添加到一个变量中（也就是归约）以获得最终答案。如果多个线程同时尝试将其结果添加到同一个变量中，这将导致数据竞争(data race)，从而导致结果不正确。

现在尝试运行测试：由于其他优化尚未实现，只有朴素解决方案应该通过。

make ex2
./ex2
  1. 实现 dotp_critical，使用OpenMP和临界区。
    • 注意到随着线程数量增加，性能会变差吗？通过将所有归约工作放在临界区中，我们"展平"了并行性，使得一次只能有一个线程做有用的工作（这与线程级并行的理念相悖）。
    • 这种竞争是有问题的；每个线程都在不断争夺临界区，而在任何给定时间只有一个线程在取得进展。随着线程数量的增加，竞争也会增加，性能就会受到影响。
  2. 实现 dotp_reduction，使用OpenMP和归约语句。
    • 提示：应该一次只由一个线程访问的变量是global_sum，对其执行的操作是加法（+）。
  3. 实现 dotp_manual_reduction，使用OpenMP和归约的思想，但不要使用reduction关键字。
    • 提示：为每个线程创建变量，并仅在绝对必要时才添加到最终总和中。您的解决方案中可能需要使用#pragma omp critical。

练习3：反思与反馈表(Exercise 3: Reflection and Feedback Form)

我们每周都在努力改进课程——请填写这份调查问卷，告诉我们您到目前为止在讨论课和实验中的体验！

提交(Submission)

保存、提交(commit)并推送(push)您的工作，然后在Gradescope上提交到Lab 7作业。