ayayadesu.net

[ blog / entry ]

CS149 Lecture 4：Parallel Programming Basics

~11 min read

学习笔记

#CS149.Parallel-Computing
[ contents ] 10 sections

现在来考虑编写和优化并行程序的过程

创建一个并行程序

我们的思考过程

  • 识别可以并行执行的工作
  • 分配工作(同样分配并行的数据)
  • 管理数据获取, 通信与同步的问题

一个通常的目标是最大化加速比(有时也包括提高效率) 工作流可以做以下的抽象

            Problem
               |
               v
        +---------------+
        | Decomposition |
        +---------------+
               |
               v
      +----+ +----+ +----+
      | T1 | | T2 | | T3 | ...      Tasks
      +----+ +----+ +----+
               |
               v
        +---------------+
        |  Assignment   |
        +---------------+
               |
               v
      +----+ +----+ +----+
      | W1 | | W2 | | W3 | ...      Workers
      +----+ +----+ +----+
        | \    |    / |
        |  \   |   /  |             Orchestration
        |   \  |  /   |
               v
        +---------------+
        | HW Assignment |
        +---------------+
               |
               v
      +-----+ +-----+ +-----+
      |Core0| |Core1| |Core2| ...    Hardware
      +-----+ +-----+ +-----+

Problem decomposition

把任务分解为可以平行解决的子任务. 一般地, 尽可能多地分解出任务, 让机器的每个单元都在工作, 这个任务的挑战是: 正确地识别任务之间的数据依赖关系

Amdahl’s law : dependencies limit maximum speedup due to parallelism

考虑 SS 为程序中不能并行执行的部分的占比, 则并行最大加速比有上界 1/S1/S

一个简单的例子是: 考虑在一个 N×NN\times N 大小的图像上的两步计算

  • 把每个像素上的亮度乘 2
  • 计算图像像素亮度的平均值

如果直接串行执行, 每步都需要约 N2N^2 时间, 故总时间为 2N22N^2

并行的第一次尝试: 对于第一个乘 2 操作, 可以用 P 个处理器并行计算, 时间压缩到 N2/PN^2/P , 最终加速比

2N2N2P+N2=2P1+P≤2\frac{2N^2}{\frac{N^2}{P}+N^2}=\frac{2P}{1+P}\leq 2

对于第二步, 我们也可以尝试并行: 使用 partial sum 的思路加速计算, 总的时间消耗为 N2/P+PN^2/P +P , 最终加速比

2N22N2/P+P=2PN22N2+P2→PN≫P\frac{2N^2}{2N^2/P+P}=\frac{2PN^2}{2N^2+P^2}\to P\quad N\gg P

对于一般的, 我们有最大加速比上界

speedup≤1S+1−SP\text{speedup}\leq \frac{1}{S+\frac{1-S}{P}}

一个小的串行部分就可以限制一个大型并行机器的加速上限! 当然, 程序自动化分解串行任务仍然是一个有挑战性的问题

Assignment

将任务分配给 workers

  • tasks 是什么?
  • workers 是什么? (线程, 程序实例, 向量lane 等)

目标: 实现良好的负载平衡, 降低通信成本. 既可以静态分配, 也可以动态由程序分配

一个例子是 cpp 的静态分配线程

void my_thread_start(int N, int terms, float* x, float* results) {
    sinx(N, terms, x, results);  // do work
}

void parallel_sinx(int N, int terms, float* x, float* result) {

    int half = N / 2;

    // launch thread to do work on first half of array
    std::thread t1(my_thread_start, half, terms, x, result);

    // do work on second half of array in main thread
    sinx(N - half, terms, x + half, result + half);

    t1.join();
}

将任务分配给 2 个 线程, 然后用 join() 等待副线程结果

对于 ISPC, foreach 这一抽象允许实现选择任务分配方式, 当前 ISPC 实现采用静态分配; launch 则提供动态任务分配

void foo(uniform float* input,
         uniform float* output,
         uniform int N)
{
    // create a bunch of tasks
    launch[100] my_ispc_task(input, output, N);
}

ISPC 可以动态分配任务

                 task queue
                     |
                     v
+------+------+------+------+-----+------+
| T0   | T1   | T2   | T3   | T4  | ...  |
+------+------+------+------+-----+------+
                              ^
                              |
                       next task ptr

       ↑          ↑          ↑          ↑
       |          |          |          |
    Worker 0   Worker 1   Worker 2   Worker 3

Orchestration

这一步包含

  • 组织通信
  • 对于依赖关系, 加入同步
  • 组织内存中的数据结构
  • 调度任务

目标: 降低通信成本, 保证数据依赖的局域性, 降低额外开销 通常来说, 很多选择受到具体机器细节的限制

Assignment to hardware

对执行硬件单元分配任务

一些例子:

  • 操作系统将任务分配给硬件
  • 编译器将任务分配给硬件
  • 硬件将 CUDA thread block 分配给 GPU core

许多有趣的决策

  • 将相关的线程分配在同一个核心 (最大化局域性, 数据共享, 降低通信成本)
  • 将不相关的线程分配在同一个核心 (一个线程受带宽限制但另一个受到计算能力限制) 来提高机器的利用效率

一个并行计算例子

我们考虑在一个二维格点上编程一个 PDE 数值求解器 首先需要考虑任务的分解

考虑以下数值求解

A[i,j] = 0.2 * (A[i,j] + A[i,j-1] + A[i-1,j] + A[i,j+1] + A[i+1,j]);

const int n;
float* A;  // assume allocated for grid of N+2 x N+2 elements

void solve(float* A) {

    float diff, prev;
    bool done = false;

    while (!done) {                     // outermost loop: iterations
        diff = 0.f;

        for (int i = 1; i < n; i++) {  // iterate over non-border points of grid
            for (int j = 1; j < n; j++) {

                prev = A[i,j];

                A[i,j] = 0.2f * (A[i,j]   + A[i,j-1] +
                                 A[i-1,j] + A[i,j+1] +
                                 A[i+1,j]);

                diff += fabs(A[i,j] - prev);  // compute amount of change
            }
        }

        if ((diff / (n*n)) < TOLERANCE)  // quit if converged
            done = true;
    }
}

这种按行传播的方式本身可以正确求解, 但格点更新之间存在迭代内的数据依赖: 后面的格点会读到前面刚更新的值, 因此很难直接并行化. 我们需要重排更新顺序, 让同一批格点可以并行计算

另一种改进是按对角线推进, 在对角线上的点可以被并行处理 但是这种处理并没有提供太大的并行度, 并且还需要频繁地同步数据

另一种方式即为 red-black Gauss-Seidel method: 将格点按棋盘颜色交错分成两组, 每个阶段只更新一种颜色. 同色格点彼此不相邻, 它们依赖的另一色格点在当前阶段保持不变, 因此同一组内没有数据依赖 重复这样的交替更新, 直到收敛

这样每次更新的格点上的计算都是并行的, 所以我们可以任意切分格点分配给不同的 worker

整个程序的运行就是

  • 并行更新一半格点的值
  • 等待所有处理器完成计算和更新
  • 各个处理器之间通信同步数据
  • 并行更新另一半格点的值
  • 等待所有处理器完成计算和更新
  • 各个处理器之间通信同步数据
  • 重复直到收敛

现在我们要考虑不同分配方式带来的通信成本: 通信发生在切分区域的边缘, 这些区域必须让处理器之间同步, 否则计算会错误

两种方式思考

  • 数据平行思维
  • SPMD / 共享内存地址空间

求解器的数据并行写法

我们来看求解器的伪代码

const int n;
float* A = allocate(n+2, n+2);   // 分配网格

void solve(float* A) {

    bool done = false;
    float diff = 0.f;

    while (!done) {

        for_all (red cells (i,j)) {
            float prev = A[i,j];

            A[i,j] = 0.2f * (A[i-1,j] + A[i,j-1] + A[i,j] +
                             A[i+1,j] + A[i,j+1]);

            reduceAdd(diff, abs(A[i,j] - prev));
        }

        if ((diff / (n*n)) < TOLERANCE)
            done = true;
    }
}
  • Decomposition: 将格点更新分解为彼此独立的任务
  • Assignment: 将这些任务分配给处理器
  • Orchestration: 系统控制通信

求解器共享地址空间的写法

程序员需要自己负责同步, 一般的工具

  • Locks: 只允许同时有一个处理器在指定地址上更新
  • Barriers: 等待所有线程的完成

同样有例子

int     n;              // grid size
bool    done = false;
float   diff = 0.0;
LOCK    myLock;
BARRIER myBarrier;

// allocate grid
float* A = allocate(n+2, n+2);

void solve(float* A) {
    float myDiff;
    int threadId = getThreadId();

    int myMin = 1 + (threadId * n / NUM_PROCESSORS);
    int myMax = myMin + (n / NUM_PROCESSORS);

    while (!done) {
        float myDiff = 0.f;
        diff = 0.f;

        barrier(myBarrier, NUM_PROCESSORS);

        for (j = myMin to myMax) {
            for (i = red cells in this row) {
                float prev = A[i,j];

                A[i,j] = 0.2f * (A[i-1,j] + A[i,j-1] + A[i,j]
                                 + A[i+1,j] + A[i,j+1]);

                myDiff += abs(A[i,j] - prev);
            }
        }

        lock(myLock);
        diff += myDiff;
        unlock(myLock);

        barrier(myBarrier, NUM_PROCESSORS);

        if (diff/(n*n) < TOLERANCE)    // check convergence, all threads get same answer
            done = true;

        barrier(myBarrier, NUM_PROCESSORS);
    }
}

这是在 SPMD 模型上的表达, 注意代码中 lock 和 barrier 的位置 由于 diff 是所有处理器一起维护的值, 所以需要加 lock 保护 第一个 barrier 保护 diff 确实做了初始化, 第二个确保所有处理器完成更新, 最后一个确保所有处理器完成循环条件检查

Synchronization in a shared address space

我们将上面的共享地址空间模型进行抽象:

即多个处理器同时维护某个地址上的值, 如果不加 lock 保护, 就可能值被错误地修改, 使得程序错误

Atomicity 表示一组操作对其他线程表现得不可分割: 其他线程不能观察到或插入这组操作的中间状态

各种编程语言提供了维护 atomicity 的工具 如 lock , atomic{} , atomicAdd 等操作

共享地址模型

线程之间的通信:

  • 在共享地址空间中维护变量
  • 操作各种同步语句

线程不需要显式“发消息”给彼此；它们通过共同读写内存来交换信息，再用同步机制保证这些读写的顺序和正确性。

通常, 这种操作的 workload 是很大的, 不同线程需要抢同一个 lock , 所以对于线程局域处理的数据, 最好不要频繁使用 lock , 只在最终使用一次是最好的

同样, 频繁使用 barrier 也会导致机器实际利用率降低, 线程需要都完成后才能进行下一步 上面 3 个 barrier 的做法可以压缩到 1 个 barrier : 做法是直接维护一个 diff 向量, 同时维护不同阶段的 diff 这里使用了 3 个 diff 槽位, 每轮仍然保留一次 barrier. 在这次同步之后, 快线程可以使用新的 diff 开始下一轮计算, 而较慢的线程仍可安全读取上一轮的槽位; triple buffering 避免旧值被过早覆盖, 但并没有完全消除同步

第 k 轮使用 diff[0]

          各线程并行计算
                |
                v
      local myDiff 累加完成
                |
                v
      lock: diff[0] += myDiff
                |
                v
   提前初始化下一轮：diff[1] = 0
                |
                v
        ===== barrier =====
                |
                v
      所有人第 k 轮计算完成
                |
                v
      各自读取 diff[0] 判断
          /             \
       快线程           慢线程
          |                |
          v                |
      进入第 k+1 轮        |
      使用 diff[1]         |
          |                |
          v                |
   提前初始化 diff[2]      |
          |                |
          |          仍在读取 diff[0]
          |                |
          v                v
        ===== 第 k+1 轮 barrier =====
                    |
                    v
          所有人肯定已经读完 diff[0]
                    |
                    v
             现在 diff[0] 可复用

当然这样的 trade off 是我们使用了更大的内存

Grid solver 的两种实现:

Data-parallel:

  • 同步: 单个逻辑线程, 但由 forall 循环由系统分配多个线程并行计算(通常有一个隐式 barrier )
  • 通信: 隐含在对内存的 load/store 中, 通常也有更复杂的隐式通信模式

Shared address space

  • 同步: 对共享变量修改时, 需要互斥, 用 barrier 来表达依赖
  • 通信: 同样隐含在共享内存的 load/store 中
Data Parallel
-------------------------
并行任务怎么分        系统管
barrier               隐式
reduction             系统提供
控制流                 看起来还是单线程逻辑


Shared Address Space
-------------------------
并行任务怎么分        程序员管得更多
barrier               显式写
lock / synchronization 显式写
通信                   通过共享内存

Amdahl’s Law: 并行化带来的最大加速比被程序中的串行部分制约

并行编程的考虑的方面:

  • Decomposition
  • Assignment
  • Orchestration
  • Mapping to hardware

本次课我们的重点是识别程序中的依赖关系

← Back to blog