并行程序设计
基础小测

下面是某气象模拟程序中的两个并行化方案。

1. 方案 A 主要属于数据并行（data parallelism，数据并行）还是任务并行（task parallelism，任务并行）？为什么？
2. 方案 B 主要属于数据并行还是任务并行？为什么？
3. 如果方案 A 中某个区域的计算量远大于其他区域，可能出现什么性能问题？

8 个处理器分别保存一个数 x0～x7。要求把这 8 个数相加，并最终将结果保存在处理器 0 中。采用树形归约（tree reduction，树状逐层汇总）：

第 1 轮：1 → 0，3 → 2，5 → 4，7 → 6
第 2 轮：2 → 0，6 → 4
第 3 轮：4 → 0

1. 整个过程一共发送了多少条消息？
2. 整个过程一共执行了多少次加法？
3. 处理器 0 一共接收了多少条消息、执行了多少次加法？
4. 如果让其他 7 个处理器依次直接把数据发送给处理器 0，处理器 0 需要连续接收 7 次。与这种方法相比，树形方法的主要优点是什么？

C 语言中的二维数组按照“行优先”方式连续存放。比较下面两个对同一数组求和的程序：

double sum = 0.0;
for (int i = 0; i < 1024; i++)
  for (int j = 0; j < 1024; j++)
    sum += a[i][j];

double sum = 0.0;
for (int j = 0; j < 1024; j++)
  for (int i = 0; i < 1024; i++)
    sum += a[i][j];

已知一个 double 占 8 字节，一个缓存行（cache line，缓存一次传输的数据块）占 64 字节。

1. 哪个程序通常运行得更快？
2. 一个缓存行可以容纳多少个 double 数据？
3. 结合空间局部性（spatial locality，连续访问相邻数据的特性），解释两个程序性能不同的原因。
4. 如果数组非常小，能够完全放入高速缓存中，两者的性能差距会增大还是减小？为什么？

某程序使用单个处理器运行需要 120 秒，使用 8 个处理器并行运行需要 30 秒。

1. 计算加速比（speedup，加速比）。
2. 计算并行效率（efficiency，并行效率），并写成百分数。
3. 在完全理想的情况下，使用 8 个处理器需要多少秒？实际运行时间是理想运行时间的多少倍？
4. 假设程序有 10% 的部分无法并行。根据阿姆达尔定律计算使用 8 个处理器时的理论最大加速比。

其中 p = 8，不可并行部分比例 r = 0.1。

下面的程序使用开放式多处理（OpenMP）计算数组中所有元素的和：

double sum = 0.0;

#pragma omp parallel for
for (int i = 0; i < n; i++) {
    sum += a[i];
}

printf("%f\n", sum);

1. 这段程序可能得到错误结果吗？为什么？
2. 多个线程同时执行 sum += a[i] 时，发生了什么问题？
3. 使用 OpenMP 的归约子句（reduction clause，将各线程局部结果合并）修改程序，使其能够正确计算。
4. 说明 a、n、i、每个线程计算期间使用的局部 sum 分别属于共享变量还是线程私有变量。
5. 也可以在每次更新 sum 时使用临界区（critical section，一次只允许一个线程执行的代码区域）。为什么求和时通常更推荐使用归约？

有 8 次循环迭代，编号为 0～7。第 i 次迭代的运行时间为 i+1 毫秒。使用两个线程运行该循环。

1. 方式 A 中，线程 0 和线程 1 分别需要多少毫秒？整个循环需要多少毫秒？
2. 方式 B 中，线程 0 和线程 1 分别需要多少毫秒？整个循环需要多少毫秒？
3. 哪种方式的负载均衡（load balancing，让各线程工作量尽量接近）更好？为什么？
4. 动态调度（dynamic scheduling，线程完成任务后再领取新任务）可能进一步改善不规则循环的负载均衡，但它有什么代价？