Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 4: Parallelizing Code: An Example Thought Process（并行化代码：思考过程实例）（日期：Oct 02）

目录 · ← l3 · l5 →

Lecture 4: Parallelizing Code: An Example Thought Process（并行化代码：思考过程实例）（日期：Oct 02）

概述：本讲首先补完第 3 讲的 ISPC 语义（SPMD 抽象 vs SIMD 实现、foreach、uniform/varying、跨 program instance 操作），随后以”编写并优化一个并行程序”为案例，系统介绍并行程序设计的四步思考过程：decomposition（分解）→ assignment（分配）→ orchestration（编排）→ mapping（映射到硬件）。全讲围绕两个编程模型展开——data parallel（数据并行）与 shared address space（共享地址空间），并以一个 2D grid solver（Gauss-Seidel 迭代求解器）为贯穿案例，展示同一算法在两种模型下的不同表达方式、同步方式与性能取舍。

注意：本讲内容与 Assignment 1（”Analyzing Parallel Program Performance on a Quad-Core CPU”，截止 Oct 6）直接对应——ISPC 的 foreach、ISPC tasks、静态/动态分配的思想正是该作业的核心内容。

一、核心概念与定义

1. SPMD（Single Program, Multiple Data，单程序多数据）

  • 定义：一种编程模型：程序员只写一个函数，但在并行执行时，该函数会以多个”program instance（程序实例）”的形式同时运行，每个实例处理不同的输入数据。调用 SPMD 函数时产生一个”gang（组）”；函数返回时所有实例都必须执行完毕，控制流回到单一顺序执行。
  • 现实类比：就像一家连锁店的总部发布同一份”开店手册”，各家分店（实例）同时照着手册执行，但各自面对的是自己街区（数据）的情况。
  • 公式/图示：
单线程控制流                    SPMD 执行（多个实例并行）            单线程控制流
───────►  ispc_sinx()  ────────►  0  1  2  3  4  5  6  7  ────────►  （返回后继续）
        （顺序执行 C 代码）          （programCount = 8 个实例）        （顺序执行 C 代码）

2. programCount 与 programIndex

  • 定义：programCount 是当前 gang 中同时执行的 program instance 总数（uniform 值）；programIndex 是当前实例在 gang 中的编号（varying 值，每个实例不同）。它们让 ISPC 成为一门”低级”语言——程序员可以精确指定每个实例做什么工作、访问哪些数据。
  • 现实类比：programIndex 就像电影院里每个人的座位号，programCount 就是影院总座位数——”坐在 3 号座的人负责处理数据 3、11、19……”。
  • 公式/图示：
interleaved（交错）分配:  idx = i + programIndex      （i 每次步进 programCount）
  实例0 → 元素 0, 8, 16, 24, ...
  实例1 → 元素 1, 9, 17, 25, ...
blocked（分块）分配:     idx = start + i,  start = programIndex * (N/programCount)
  实例0 → 元素 0..31,  实例1 → 元素 32..63, ...

3. uniform 与 varying（ISPC 类型修饰符）

  • 定义：uniform 变量在所有 program instance 中取值相同（编译器可将其放在寄存器/内存的单份拷贝中）；varying（默认）变量每个实例各有一份。使用 uniform 纯粹是优化手段，不影响正确性——但类型错误会在编译期暴露。
  • 现实类比：uniform 像公司统一印发的通知（每人内容一样），varying 像每人手写的笔记（每人内容不同）。
  • 公式/图示：无（类型系统概念）。注意：programCount 是 uniform，programIndex 是 varying。

4. foreach（ISPC 的关键语言构造）

  • 定义：foreach (i = 0 ... N) 声明循环迭代是可并行的。程序员说”这些迭代是整个 gang（而非每个实例）要完成的工作”，由 ISPC 实现负责把迭代分配给 gang 内的各 program instance。它把程序员的思考层次从”并行执行”提升到”迭代”——多数情况下可以像写串行程序一样思考。
  • 现实类比：foreach 就像把一摞试卷交给一组助教：”这 100 份你们每人分一些批改，怎么分你们自己商量。”而手写 programIndex 则像”我指定 1 号助教批第 1~25 份……”。
  • 公式/图示：foreach 的四种可能实现（由编译器/运行时选择）：
foreach (i = 0 ... N) { ... }
  实现1（实例0 干所有活）:  if (programCount == 0) for (i=0; i<N; i++) ...
  实现2（交错）:            for (loop_i=0; loop_i<N; loop_i+=programCount) i = loop_i + programIndex;
  实现3（分块）:            count = N/programCount; start = programIndex*count; ...
  实现4（动态）:            i = atomic_add_local(&nextIter, 1); while (i < N) {...}

5. ISPC task（ISPC 任务）

  • 定义：gang 抽象由单核上的 SIMD 指令实现，因此之前所有 ISPC 代码只跑在一个核上。ISPC 还提供”task”抽象实现多核执行：launch[numTasks] myTask(...) 创建一批任务，由 ISPC 运行时（对程序员不可见）把任务动态分配给线程池中的 worker 线程。
  • 现实类比：gang 是”一个班里做小组作业”（一个核上的向量化），task 是”整个年级分工”（多核协作）。
  • 公式/图示：
Worker thread 0 ──► task0  task3  ...
Worker thread 1 ──► task1  task4  ...   （完成后从任务列表取下一个未完成任务）
Worker thread 2 ──► task2  task5  ...
Worker thread 3 ──► ...    ...   ...    ← 共享任务列表 + "next task" 指针

6. Data Parallelism（数据并行）与 Task Parallelism（任务并行）

  • 定义：数据并行指对大量数据元素执行同一序列操作（”对每个元素独立地做这件事”），典型的表达是 foreach、#pragma omp parallel for、map()；任务并行指把问题分解为多个相互独立的子任务，每个任务可能是不同的工作（甚至不同函数），通过任务队列/任务图调度。本讲两个编程模型：data parallel 模型（单逻辑控制流 + 系统处理并行化）与 shared address space 模型（多 SPMD 线程 + 程序员负责同步）。
  • 现实类比：数据并行像流水线上每个工位用同一道工序处理不断流过的零件；任务并行像装修队里瓦工、电工、木工各干各的活。
  • 公式/图示：见第 5 讲（B[i] = foo(A[i]) 是数据并行；enqueue_task(foo) 是任务并行）。

7. Shared Address Space（共享地址空间模型）

  • 定义：线程通过读写共享内存中的变量进行通信——通信隐式地发生在 load/store 中；程序员还需要操作同步原语（lock、barrier、atomic 操作）来协调访问。它是顺序编程的自然延伸（本课程此前所有讨论都假设了共享地址空间）。
  • 现实类比：讲义中的经典比喻——公告板（bulletin board）：任何人都能读、能写；但要防止两个人同时修改同一张通知，就得靠”谁先到谁先写”的规矩（锁）。
  • 公式/图示：
        ┌───────────────┐
        │  共享地址空间    │  ← x = 0
        └──────┬────────┘
    Thread 1   │   Thread 2
   store x=1   │   while(x==0); print x;
               ▼
      （红色箭头 = 通信操作：load/store）

8. Data Race（数据竞争）

  • 定义：多个线程同时访问同一内存位置，且至少有一个是写操作，且没有同步机制保证顺序——结果不确定。例如两个线程同时执行 x++（它由 load、add、store 三条指令组成），可能都读到旧值 0，最终 x 只变成 1 而非 2。
  • 现实类比：两个人同时往同一张表格的同一格填数字，最后写上去的是谁的内容完全取决于先后——没人能保证。
  • 公式/图示：
T1: r1 ← x (0)   T2: r1 ← x (0)
T1: r1 ← r1+1    T2: r1 ← r1+1
T1: x ← r1 (1)   T2: x ← r1 (1)   → 最终 x = 1（应为 2）

9. Decomposition（分解）、Assignment（分配）、Orchestration（编排）、Mapping（映射）

  • 定义：创建并行程序的四个步骤：
    1. Decomposition：把问题分解成可并行执行的子问题（tasks），关键挑战是识别依赖（dependencies）；
    2. Assignment：把任务分配给 worker（线程、program instance、vector lane……），目标是好的负载均衡与低通信成本，可静态或动态执行；
    3. Orchestration：组织通信结构、加入同步以保持依赖、组织内存中的数据布局、调度任务；
    4. Mapping：把线程映射到硬件执行单元（由 OS / 编译器 / 硬件完成）。 这些职责可能由程序员承担，也可能由系统（编译器、运行时、硬件）承担。
  • 现实类比：做一顿宴席——分解=把”做菜”拆成”洗菜、切菜、炒菜”；分配=给每位厨师分工；编排=决定传菜顺序与”等菜齐了再上桌”的同步；映射=决定哪个灶台给哪位厨师用。
  • 公式/图示：
Problem → 子问题(tasks) → 并行线程(workers) → 并行程序(通信线程) → 并行机器执行
             分解           分配                 编排              映射

10. Amdahl’s Law（阿姆达尔定律）

  • 定义：设 S 为程序中本质上串行（依赖阻止并行）的执行时间占比，则并行带来的最大加速比 ≤ 1/S。一条很小的串行代码段就能限制大型并行机上的加速比。
  • 现实类比：九个月生一个孩子——即使雇 100 个保姆，怀孕这件事（串行部分）本身就要 9 个月，加速比被它锁死。
  • 公式/图示：
Speedup(P) ≤ 1 / (S + (1-S)/P)  →  Speedup(∞) ≤ 1/S

例：Summit 超算 = 27,648 GPUs × 5,376 ALUs/GPU ≈ 148,635,648 个 ALU
   若应用中 0.1% 是串行的：最大加速比 ≤ 1/0.001 = 1000 倍
   （148M 个并行单元只换来 1000 倍——串行比例才是瓶颈）

11. Lock（锁）与 Barrier（屏障）

  • 定义：lock 提供互斥（mutual exclusion）：临界区（critical section）内同时只允许一个线程进入；barrier(n) 让 n 个线程都到达后才能继续，是表达依赖的保守方式——它把计算分成阶段（phase），保证所有线程在屏障前的计算都完成后，任何线程才能开始屏障后的计算。
  • 现实类比：锁=办公室只有一把钥匙，谁拿钥匙谁进门；barrier=接力赛，必须所有队员都到达接力区，下一棒才能出发。
  • 公式/图示：
          barrier
P1 ──计算──┤
P2 ──计算──┤  （所有线程到齐后一起放行）
P3 ──计算──┤
P4 ──计算──┤

12. Red-Black Coloring（红黑着色重排）

  • 定义：改变 Gauss-Seidel 迭代中网格单元的更新顺序，使其更适合并行：把网格按棋盘格染色，先并行更新所有红格，全部完成后再并行更新所有黑格（黑格依赖红格的新值），如此反复直至收敛。收敛到同一解（误差阈值内），但浮点中间值与串行版本不同。
  • 现实类比：棋盘上的马走日字——同色格互不”相邻”，所以同色格之间没有依赖，可以同时更新。
  • 公式/图示：
N×N 网格（(N+2)×(N+2) 含边界）          红黑着色：
  A[i,j] = 0.2*(A[i,j] + A[i,j-1]      R B R B R
                  + A[i-1,j]           B R B R B
                  + A[i,j+1]           R B R B R
                  + A[i+1,j])          B R B R B
     第1阶段: 并行更新所有 R
     第2阶段: 并行更新所有 B（依赖相邻 R 的新值）

二、代码示例与详细解说（本讲重点）

示例 1：ISPC 的 foreach 与手写 programIndex 交错分配（sinx 泰勒展开）

代码（ISPC + C++）：

// sinx.ispc —— ISPC 代码
// 版本 A：手写交错分配（低级写法，程序员亲自分配迭代）
export void ispc_sinx_interleaved(
    uniform int N,
    uniform int terms,
    uniform float* x,
    uniform float* result)
{
    // 假设 N % programCount == 0
    for (uniform int i = 0; i < N; i += programCount)
    {
        int idx = i + programIndex;          // 每个实例负责的元素：交错分布
        float value = x[idx];
        float numer = x[idx] * x[idx] * x[idx];
        uniform int denom = 6;               // 3!
        uniform int sign = -1;
        for (uniform int j = 1; j <= terms; j++)
        {
            value += sign * numer / denom;
            numer *= x[idx] * x[idx];
            denom *= (2*j+2) * (2*j+3);
            sign *= -1;
        }
        result[idx] = value;
    }
}

// 版本 B：foreach 版本（高级写法，把分配交给系统）
export void ispc_sinx_foreach(
    uniform int N,
    uniform int terms,
    uniform float* x,
    uniform float* result)
{
    foreach (i = 0 ... N)                    // 声明迭代可并行
    {
        float value = x[i];
        float numer = x[i] * x[i] * x[i];
        uniform int denom = 6;               // 3!
        uniform int sign = -1;
        for (uniform int j = 1; j <= terms; j++)
        {
            value += sign * numer / denom;
            numer *= x[i] * x[i];
            denom *= (2*j+2) * (2*j+3);
            sign *= -1;
        }
        result[i] = value;
    }
}

// main.cpp —— 调用 ISPC 函数的 C++ 代码
#include "sinx_ispc.h"
#include <cstdlib>

int main(int argc, char** argv) {
    int N = 1024;
    int terms = 5;
    float* x = new float[N];
    float* result = new float[N];
    // 初始化 x 数组（略）
    // 执行 ISPC 代码：调用会 spawn 一个 gang
    ispc_sinx_foreach(N, terms, x, result);
    delete[] x;
    delete[] result;
    return 0;
}

【代码做了什么？】

  1. ISPC 代码计算 sin(x) 的 Taylor 展开近似：x - x³/3! + x⁵/5! - ...（terms 项）。numer 依次是 x³, x⁵, ...，denom 依次是 6, 120, ...，sign 交替 ±1。
  2. 版本 A 用 programIndex/programCount 手写”交错”迭代分配：外层 uniform 循环每次步进 programCount，实例 programIndex 处理 i + programIndex 号元素——即实例 0 处理元素 0,8,16,…；实例 1 处理 1,9,17,…。
  3. 版本 B 用 foreach：程序员只声明”这些迭代可并行”，不再关心谁做哪份。
  4. C++ 的 main 像调用普通函数一样调用 ISPC 函数；调用期间程序进入 SPMD 执行，返回时所有实例已完成。

【并行机制解说】

  • 线程/实例如何创建：调用 ispc_sinx_foreach 时，ISPC 运行时”spawn”一个 gang——programCount 个 program instance 并发执行同一份 ISPC 代码（此处 gang 由硬件 SIMD 宽度决定，如 AVX2 的 8 宽）。
  • 工作如何分配：版本 A 是程序员管理的静态分配（交错）；版本 B 把分配交给系统——foreach 抽象允许动态分配，但当前 ISPC 实现用的是静态方案。ISPC 编译器把 gang 实现为 SIMD 指令：交错分配下，一次 float value = x[idx] 对所有实例恰好是连续内存，编译器生成一条 packed vector load（如 vmovaps / _mm256_load_ps）；若改成 blocked 分配（见版本 2 幻灯片），则一次访问的是 8 个不连续的值，需要更昂贵的 vgatherdps（_mm256_i32gather_ps）gather 指令。
  • 数据如何共享：x、result 是 uniform 指针（所有实例共享同一数组），局部变量（value、numer）每个实例各一份。
  • 同步点在哪：函数返回即隐式同步（所有实例完成）。
  • 对应概念：SPMD 抽象 vs SIMD 实现（abstraction vs implementation）、foreach、data parallelism、interleaved vs blocked assignment。

示例 2：C++11 std::thread 的静态分配（parallel_sinx）

代码（C++）：

#include <thread>

// 串行核心：计算 [0, N) 区间内每个元素的 sinx
void sinx_range(int N, int terms, float* x, float* result) {
    for (int i = 0; i < N; i++) {
        float value = x[i];
        float numer = x[i] * x[i] * x[i];
        int denom = 6, sign = -1;
        for (int j = 1; j <= terms; j++) {
            value += sign * numer / denom;
            numer *= x[i] * x[i];
            denom *= (2*j+2) * (2*j+3);
            sign *= -1;
        }
        result[i] = value;
    }
}

// 并行版本：把数组分成两半，分别交给两个执行单元
void parallel_sinx(int N, int terms, float* x, float* result) {
    int half = N / 2;

    // 启动一个线程，负责数组的前一半
    std::thread t1(sinx_range, half, terms, x, result);

    // 主线程负责后一半（指针偏移 half）
    sinx_range(N - half, terms, x + half, result + half);

    t1.join();   // 等待 t1 完成（同步点）
}

【代码做了什么？】

  1. sinx_range 是串行的 sinx 计算函数，参数化区间起点（通过指针偏移）。
  2. parallel_sinx 把 N 个元素按 block（分块）静态分配：新线程 t1 处理 [0, half)，主线程处理 [half, N)——各自独立读写数组的不同区域，互不干扰。
  3. t1.join() 阻塞主线程直到 t1 完成，保证返回时所有工作结束。

【并行机制解说】

  • 线程如何创建：std::thread t1(...) 创建一个新线程，与主线程并发。
  • 工作如何分配：程序员手动按循环迭代分块分配（blocked fashion）——这是典型的静态分配（static assignment）：分配不依赖运行时行为，只有一点点索引计算的开销。
  • 数据如何共享/同步：两个线程通过共享地址空间（同一个 x、result 数组）间接共享；因为各自区间不相交，无需锁；join 是唯一的同步点。
  • 对应概念：shared address space 模型、static assignment、blocked assignment、decomposition by loop iteration。

示例 3：数据竞争（Data Race）与用锁修复

代码（C++，共享地址空间）：

#include <thread>
#include <mutex>
#include <cstdio>

int x = 0;                     // 共享变量
std::mutex mylock;

void worker_racy() {           // 有数据竞争的版本
    for (int i = 0; i < 100000; i++)
        x++;                   // 实际是 load → add → store 三条指令！
}

void worker_safe() {           // 加锁修复
    for (int i = 0; i < 100000; i++) {
        mylock.lock();         // 进入临界区（互斥）
        x++;                   // 三条指令被锁保护，整体"原子"
        mylock.unlock();
    }
}

int main() {
    std::thread t1(worker_racy), t2(worker_racy);
    t1.join(); t2.join();
    std::printf("有竞争时 x = %d（期望 200000）\n", x);

    x = 0;
    std::thread t3(worker_safe), t4(worker_safe);
    t3.join(); t4.join();
    std::printf("加锁后  x = %d（期望 200000）\n", x);
    return 0;
}

【代码做了什么？】

  1. 两个线程各自执行 10 万次 x++。理想结果 x = 200000。
  2. worker_racy 无同步：两个线程可能同时读出旧值、各自加 1、再写回，丢失更新——x 通常小于 200000，且每次运行结果不同（未定义行为）。
  3. worker_safe 用 mutex 把 x++ 包成临界区，保证 load-add-store 三步原子执行，结果稳定为 200000。

【并行机制解说】

  • 为什么需要互斥：x++ 在机器层面是 load、add、store 三条指令。两个线程的交错（interleaving）可能让两次加 1 都基于旧值 0，最终 x=1。这组指令必须”原子”（不可分割）。
  • 保证原子性的手段（讲义列举）：lock/unlock 包临界区；硬件原子 read-modify-write 指令（如 atomicAdd(x, 10)）；语言级 atomic { ... } 块。
  • 对应概念：shared address space、data race、mutual exclusion、critical section、lock。
  • 另附 ISPC 中的数据竞争形态（讲义 shift_negative 例子）：foreach 迭代之间可能写同一内存位置——迭代 i 写 y[i-1] 而迭代 i-1 写 y[i]，输出未定义。数据竞争不只存在于线程间，也存在于”逻辑并行迭代”之间：
export void shift_negative(uniform int N, uniform float* x, uniform float* y) {
    foreach (i = 0 ... N) {
        if (i >= 1 && x[i] < 0)
            y[i-1] = x[i];   // 与相邻迭代写 y[i] 冲突 → 输出未定义
        else
            y[i] = x[i];
    }
}

示例 4：跨 program instance 规约——reduce_add（数组求和）

代码（ISPC）：

// 错误版本 1：sum 是 uniform，x[i] 是 varying —— 编译期类型错误
export uniform float sum_incorrect_1(uniform int N, uniform float* x) {
    float sum = 0.0f;        // 错误：sum 是 varying（每个实例一份），
    foreach (i = 0 ... N)    //       但函数声明返回 uniform float，
        sum += x[i];         //       无法把"很多份"sum 汇成一个返回值
    return sum;              //       → compile-time type error
}

// 错误版本 2：sum 是 uniform，但 foreach 体内每个实例都想加自己的 x[i]
export uniform float sum_incorrect_2(uniform int N, uniform float* x) {
    uniform float sum = 0.0f;
    foreach (i = 0 ... N)
        sum += x[i];         // 错误：x[i] 每个实例不同，加到哪份 uniform sum 上？
    return sum;              //       → compile-time type error
}

// 正确版本：每个实例私有累加 + 跨实例规约
export uniform float sum_array(uniform int N, uniform float* x) {
    uniform float sum;
    float partial = 0.0f;
    foreach (i = 0 ... N) {
        partial += x[i];     // 每个实例在自己的 partial 上累加（零通信）
    }
    sum = reduce_add(partial);   // 跨实例规约：把各实例的 partial 加起来
    return sum;                  // reduce_add 返回 uniform float
}

【代码做了什么？】

  1. 两个”错误”版本分别演示了 uniform/varying 混用的两种编译期错误：把 varying 值赋给 uniform 返回值、以及在 uniform 变量上做 varying 累加。
  2. 正确版本：每个 program instance 先把自己的 partial 累加好（无通信），再用 ISPC 标准库的跨实例原语 reduce_add(partial) 把所有实例的部分和相加，得到统一的总和。

【并行机制解说】

  • 数据如何共享/通信：foreach 迭代并行执行时实例之间零通信（各算各的 partial）；唯一的通信发生在 reduce_add——这是 ISPC 的 cross program instance operation（跨实例操作），把 gang 内所有实例的某个 varying 值规约成一个 uniform 值。讲义指出，这段 ISPC 代码的执行方式几乎等价于手写 AVX intrinsics 的 C 代码（_mm256_add_ps 累加 + 最后把 8 个 lane 相加）。
  • 其他跨实例原语：reduce_min（求最小值）、broadcast(value, index)（从某个实例广播）、rotate(value, offset)（实例间循环移位，用于如 vec8product 那种 3 步求 8 元素乘积的树形归约）。
  • 对应概念：uniform/varying、foreach、SPMD 抽象、data parallelism、跨实例通信原语（data-parallel 模型中”由系统提供的内建通信原语”）。

示例 5：Grid Solver 在两种编程模型下的表达（本讲案例研究）

背景：在 (N+2)×(N+2) 网格上迭代求解 PDE（Gauss-Seidel 扫描直至收敛），每点更新公式：

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

第 1 步——识别依赖（decomposition）：每个元素依赖左邻元素与上一行元素；行内存在从左到右的链式依赖，行间存在自上而下的依赖。好消息是对角线方向存在独立工作（一条对角线上的点互不依赖），但”按对角线并行”在计算开始与结束阶段并行度很低、且每完成一条对角线就要同步一次，不易利用。第 2 步——改算法：利用 Gauss-Seidel 的领域知识，把更新顺序重排为红黑着色：先并行更新所有红格，再并行更新所有黑格。第 3 步——分配：blocked 分配比 interleaved 分配通信量更小（相邻行数据在同一个处理器上，只需在边界交换 ghost 数据）。

代码 A（数据并行表达，伪代码）：

const int n; float* A = allocate(n+2, n+2);
void solve(float* A) {
    bool done = false;
    while (!done) {
        float diff = 0.f;
        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, fabs(A[i,j] - prev));   // 内建通信原语
        }
        if (diff/(n*n) < TOLERANCE) done = true;
    }
}
// 分解：每个网格单元的处理是独立工作
// 分配：由系统负责（???）
// 编排：系统处理 —— for_all 块结束处是隐式 barrier（回到顺序控制流之前）
//       通信由内建原语 reduceAdd 处理

代码 B（共享地址空间 + SPMD 线程表达，伪代码）：

int n; bool done = false; float diff = 0.0;
LOCK myLock; BARRIER myBarrier;
float* A = allocate(n+2, n+2);

void solve(float* A) {
    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);     // ① 确保所有线程都看到 diff=0
        for (j = myMin to myMax)
            for (i = red cells in row j) {
                float prev = A[i,j];
                A[i,j] = 0.2f * (...);          // 更新公式
                myDiff += fabs(A[i,j] - prev);  // 先本地累加！
            }
        lock(myLock);                           // ② 每个线程只加锁一次
        diff += myDiff;
        unlock(myLock);
        barrier(myBarrier, NUM_PROCESSORS);     // ③ 确保所有线程完成累加
        if (diff/(n*n) < TOLERANCE) done = true;
        barrier(myBarrier, NUM_PROCESSORS);     // ④ 确保所有线程看到 done
    }
}

【代码做了什么？】

  1. 两种表达都实现同一个算法：迭代红黑更新，直至 diff/(n*n) < TOLERANCE。
  2. 数据并行版：程序员只描述”对每个红格做什么”，分配与编排（含隐式 barrier、reduceAdd）全交给系统。
  3. 共享地址空间版：程序员用 threadId 算出自己负责的行区间（静态分块分配），并用 3 个 barrier + 1 个 lock 亲手编排同步。

【并行机制解说】

  • 同步点的三个 barrier 各司其职：① 防止某线程抢先进入下一轮并把 diff 清零，而其他线程还在累加上一轮结果；② 保证所有线程都完成 diff 累加后再做收敛判断（所有线程读到相同的 diff）；③ 保证所有线程都看到 done 的更新后再开始下一轮（避免一线程开始下一轮清零 diff 时另一线程还在读）。
  • 性能优化一（减少锁的争用）：把”每格更新一次就 lock 一次”改成”先累加到本地 myDiff，一轮结束只 lock 一次”——锁的获取次数从 O(每个 (i,j)) 降到 O(每线程每轮)。这是”减少同步频率”的典型编排优化。
  • 性能优化二（减少 barrier 数量）：讲义进一步给出”单 barrier”版本——用 diff[3] 三个副本 + 索引 index = (index+1)%3 循环使用：把 diff 清零移到上一轮屏障之后执行（写入下一轮才用的槽位），从而去掉第 ① 个 barrier。用内存足迹（footprint）换取去掉依赖，是常见的并行编程技巧。
  • 对应概念：decomposition（识别依赖）、assignment（静态分块）、orchestration（barrier/lock/reduceAdd）、shared address space 模型 vs data parallel 模型、lock 与 barrier、red-black coloring、Amdahl’s law（串行合并部分限制加速比：phase 2 部分和合并开销 P，当 N » P 时加速比趋近 P）。

三、关键要点

  1. 抽象 vs 实现（abstraction vs implementation）是本课程的贯穿主线：ISPC 的抽象是 SPMD（programCount 个逻辑指令流），实现是 SIMD 向量指令；foreach 的抽象是”声明可并行迭代”，实现可以交错、分块或动态分配。判断一个程序”做了什么”，要区分抽象语义与具体实现。
  2. 创建并行程序的思考过程四步走：decomposition（识别依赖，找独立工作）→ assignment（分配工作给 worker，兼顾负载均衡与通信成本）→ orchestration（组织通信与同步、数据布局、任务调度）→ mapping（映射到硬件）。每一步都可能由程序员、系统或双方共同完成。
  3. Amdahl’s Law 是硬约束：最大加速比 ≤ 1/S，S 是串行占比。负载不均、串行合并、临界区串行化都是”隐性串行部分”，都会压低加速比。
  4. foreach 让你像写串行程序一样思考迭代，但 ISPC 是低级语言——暴露 programIndex/programCount 也允许你写出输出未定义的程序（如 shift_negative）或只对特定 programCount 正确的程序；跨实例通信必须通过显式原语（reduce_add 等）。
  5. 数据并行模型把编排交给系统（隐式 barrier + 内建 reduce），共享地址空间模型把同步责任交给程序员（lock + barrier）——后者的优化空间更大，但出错（数据竞争、死锁、过度同步）的风险也更高。

四、常见陷阱与注意事项

  1. 把 varying 当 uniform 用（反之亦然）：如 sum_incorrect_1/2，在 uniform 变量上累加 varying 值或在 varying 变量上期待单一返回值——编译期就报错，要理解这是 ISPC 类型系统在保护你。
  2. foreach 迭代间写同一位置（数据竞争）：shift_negative 中迭代 i 写 y[i-1] 与迭代 i-1 写 y[i] 冲突，输出未定义。foreach 只保证”迭代可并行”，不保证”迭代互不干扰”——依赖必须由程序员保证。
  3. 忽略依赖直接并行：Gauss-Seidel 按行扫描时行间有依赖；直接并行化会得到错误结果。先做 decomposition 识别依赖，必要时改算法（如红黑着色）换取可并行性——但注意改算法后的浮点结果与串行不同（仍收敛到误差阈值内）。
  4. 过度同步：每格更新都加锁、或滥用 barrier（barrier 是保守的依赖表达，它假设”屏障后所有计算依赖屏障前所有计算”）。先本地累加再一次性合并、用多副本消除依赖，能显著减少同步开销。
  5. 负载不均与分配方案的选择：静态分配零开销，但若各块工作量不均（P4 做 2 倍工作→50% 时间串行化），加速比被 Amdahl 定律锁死，需要时可换动态分配（ISPC tasks）或半静态重分配；同时 assignment 还直接影响通信量——interleaved 分配在 SIMD 实现下更优（连续内存可向量加载），blocked 分配在多处理器下通信更少（ghost 数据量小）——”哪种更好取决于运行的系统”，没有普适答案。

五、思考题（带答案）

  1. 问：ISPC 的 foreach 声明了”N 个迭代可并行”。如果 N % programCount != 0，讲义中手写的交错循环会有问题，但 foreach 抽象本身不会有问题。为什么？ 答：手写版本假设 N % programCount == 0，否则某些实例会多处理一个或少处理一个元素（越界或漏算）。foreach 把”迭代到实例”的分配责任交给实现，实现可以选择动态分配（如实现 4 用 atomic_add_local 抢任务）或处理余数，从而对任意 N 都正确。这也体现了 abstraction（foreach 的语义与 N 无关）vs implementation（具体分配方案）的分离。

  2. 问：共享地址空间版 grid solver 里，为什么”把 diff 清零”必须放在 barrier ① 之后（而不是 while 循环开头直接清零）？ 答：diff 是共享变量。如果某线程先进入下一轮迭代并清零 diff，而其他线程仍在执行上一轮的 lock/unlock 累加，就会出现”累加被清零覆盖”的竞争，收敛判断失效。barrier ① 保证所有线程都完成上一轮累加后，才允许任何线程清零——这是 barrier 作为”保守依赖表达”的典型用法。讲义中的单 barrier 版本用 diff[3] 多副本把清零延迟到”上一轮数据已被消费之后”，从而去掉这个 barrier（以内存换同步）。

  3. 问：讲义说 ISPC 的 gang 抽象由 SIMD 指令实现，因此只用一个核；要利用多核需要 ISPC tasks。那么”交错分配”与”分块分配”在 SIMD 实现下各有什么代价？ 答：交错分配下，同一时刻 8 个实例访问的 x[idx] 在内存中连续，编译器可生成一条 packed vector load（vmovaps）高效完成”所有实例的取值”；分块分配下，同一时刻 8 个实例访问的是 8 个相距很远的元素，需要 gather 指令（vgatherdps），更复杂、更昂贵。但分块分配在”多处理器、跨节点”场景下通信更少（如 red-black solver 中 blocked assignment 只需在块边界交换数据）。这就是讲义反复强调的：分配方案的好坏取决于目标系统的实现。