Lecture 3: Modern Multi-Core Architecture (Part II) + ISPC Programming Abstractions（日期：Sep 30, 2025）

目录 · ← l2 · l4 →

Lecture 3: Modern Multi-Core Architecture (Part II) + ISPC Programming Abstractions（日期：Sep 30, 2025）

概述：本讲前半部分完成”吞吐导向硬件”的最后一课：latency vs bandwidth（延迟 vs 带宽）。通过高速公路、洗衣、水管等类比讲清二者区别，再用”逐元素向量乘法”的思想实验证明现代机器常常是 bandwidth-limited（带宽受限）——喂不饱 ALU 的不是延迟而是带宽，克服带宽限制往往是并行软件优化最重要的挑战。后半部分引入本课程第一个正式并行编程抽象：ISPC（Intel SPMD Program Compiler），讲解 SPMD 编程模型下的 program instances（程序实例）、gang、programCount/programIndex、uniform/varying、foreach 与跨实例操作（reduce_add 等），并反复强调本课口号：区分抽象（semantics）与实现（implementation/scheduling）。

一、核心概念与定义

1. 复习：三种吞吐计算思想（multi-core / SIMD / multi-threading）

• 定义：Lecture 2 的三大主题——multi-core execution（多核，TLP）、SIMD execution（数据并行，DLP）、hardware multi-threading（硬件多线程，隐藏访存延迟）。本讲先补完多线程部分的”利用率”讨论，再转向内存系统。
• 现实类比：三个维度 = 多条流水线（多核）× 一条指令指挥多人（SIMD）× 等人时换活干（多线程）。
• 公式/图示：见 Lecture 2 笔记第 10–13 条；本讲新增的定量工具是下面的 latency/bandwidth 框架。

2. Latency（延迟）与 Bandwidth / Throughput（带宽 / 吞吐）

• 定义：
  • Latency（延迟）：完成一次操作所需的时间（如从 SF 开车到 Stanford 0.5 小时；内存响应一次请求 ~2 秒；洗一桶衣服 2 小时）。
  • Bandwidth（带宽）/ Throughput（吞吐）：系统单位时间能完成的操作数或提供的数据量（如高速公路每小时过多少辆车；内存 20 GB/s；洗衣每小时几桶）。
  • Memory bandwidth（内存带宽）：内存系统向处理器提供数据的速率（例：20 GB/s）。两者是正交的度量：延迟不随带宽提高而降低（加车道不改变单程时间），带宽可随管道/车道增加而提高。
• 现实类比（幻灯片三个类比）：
  • 高速公路：SF→Stanford 50 km，车速 100 km/hr → 延迟 0.5 小时。方案 1”开快点”（200 km/hr）→ 吞吐 4 辆/小时；方案 2”多修车道”（4 条车道）→ 吞吐 8 辆/小时；方案 3”车距 1 km”（不改变速度）→ 吞吐 100 辆/小时，4 条车道 → 400 辆/小时。三种提高吞吐的手段：提速、加资源、流水线/加密发车。
  • 洗衣：洗 45min + 烘 60min + 叠 15min = 延迟 2 小时/桶。复制资源（两台洗衣机两台烘干机 + 朋友）→ 2 桶 2 小时，吞吐翻倍；流水线（一台洗衣机一台烘干机，桶 1 烘干时桶 2 开洗）→ 延迟仍 2 小时，吞吐 1 桶/小时。
  • 两根水管：管 1 最大 100 L/s，管 2 最大 50 L/s，串联后最大流量 = 50 L/s（瓶颈 = 最细的那根管）。
• 公式/图示：

  latency = 单次操作时间（如 0.5 hr / 2 sec / ~248 cycles）
  bandwidth = 单位时间操作数（如 2 cars/hr、20 GB/s、1 instr/clock）
  系统吞吐 ≤ min(所有级联部件的带宽)   ← "两管相连"结论：短板决定流量
  

3. Bandwidth-Limited（带宽受限）执行

• 定义：当处理器请求数据的速度超过内存系统能提供数据的速度时，执行变成 bandwidth-bound：指令完成速率由内存供给速率决定，而不是由 ALU 数量决定。幻灯片的关键例子：线程重复执行 3 条相互依赖的指令（X = load 64 bytes; Y = add x+x; Z = add x+y），核心每时钟 1 条算术、可并行发 load、内存每时钟 8 字节——稳态下内存 100% 时间在搬数据仍喂不饱核心，核心周期性停顿（红色区域）。
• 现实类比：餐厅后厨（ALU）再快，传菜口（内存带宽）一次只能过 8 道菜，出菜速度就被传菜口卡死。
• 公式/图示（幻灯片结论）：

  稳态下核心利用率只取决于"指令吞吐 vs 内存吞吐"的比值，
  与内存延迟大小、未完成请求数无关！
  （延迟再小，带宽不够照样停顿；隐藏延迟的多线程也救不了带宽瓶颈）
  

4. 思想实验：逐元素向量乘法为什么是带宽受限（本讲核心数字）

• 定义：任务 C[i] = A[i] × B[i]（数百万元素）：每个元素需要 load A[i] + load B[i] + store C[i] = 3 个内存操作、12 字节，只换来 1 次 MUL。V100 有 5120 个 fp32 ALU（80 SM × 64），1.6 GHz 下每时钟可做 5120 次 MUL → 需要约 98 TB/s 带宽才能喂饱全部 ALU；而 V100 的 HBM2 只有 900 GB/s → 效率 <1%！对照：八核 3.2 GHz Xeon E5v4 + 76 GB/s 内存总线，该计算效率约 3%（但注意：GPU 即使 <1% 效率，绝对速度仍远快于八核 CPU——ALU 数量差距太大）。
• 现实类比：打字员（ALU）每秒能打 100 字，但送稿员（内存）每秒只送 1 页纸（100 字）——打字员 99% 时间在等稿子。
• 公式/图示：

  每元素: load A[i] (4B) + load B[i] (4B) + store C[i] (4B) = 12 字节 / 1 次 MUL
  V100 需要带宽 = 5120 MUL/clock × 1.6 GHz × 12 B = ~98 TB/s
  V100 实际带宽 = 900 GB/s（HBM2，4096-bit 接口）  → 效率 ≈ 900/98000 ≈ <1%
  

5. 带宽是临界资源（Bandwidth is the critical resource）

• 定义：现代高性能并行程序必须：
  1. 组织计算以减少取数频率——复用同一线程之前加载的数据（temporal locality 优化）、跨线程共享数据（inter-thread cooperation）；
  2. 宁愿多算也不要存了再读（”math is free”——算术几乎不要钱，数据搬运才要钱）；
  3. 核心结论：程序必须低频访问内存才能高效利用现代处理器。
• 现实类比：做菜时把所有配料一次性从仓库搬到厨房（一次大搬运），而不是每炒一个菜跑一趟仓库（反复小搬运）。多花点力气切配（算术）比反复取料（搬运）划算。
• 公式/图示：

  高带宽需求模式:  for i: C[i] = A[i]*B[i]      ← 每算一次读 12 字节（差）
  低带宽需求模式:  for i: 复用已加载的块、就地累加 ← 每字节数据多次复用（好）
  "performant programs access memory infrequently"
  

6. Instruction Pipeline（指令流水线）与 Throughput vs Latency

• 定义：一条指令从取指到写回分 4 阶段：IF（取指）、D（译码+读寄存器）、EX（执行）、WB（写回）。流水线化后：单条指令延迟 4 周期，但吞吐 1 条/周期（4 条指令在不同阶段并行推进）。现代 CPU 流水线可达约 20 级。幻灯片特别提醒：”核心每时钟做 1 次乘法”指的是指令吞吐（INSTRUCTION THROUGHPUT），不是延迟（LATENCY）；依赖相邻的两条指令需注意正确性（冒险处理）。
• 现实类比：汽车装配线——一辆车从进厂到出厂（延迟）要几天，但工厂每秒都能出厂一辆（吞吐），因为几十辆车同时在线上。
• 公式/图示：

  时钟:  1    2    3    4    5    6    7
  instr0 IF   D    EX   WB
  instr1      IF   D    EX   WB
  instr2           IF   D    EX   WB
  instr3                IF   D    EX   WB
  → 延迟 4 周期/条，吞吐 1 条/周期（前提：相邻指令无依赖冲突）
  

7. Abstraction vs Implementation（抽象 vs 实现）——本课口号

• 定义：Semantics（语义/抽象）：给定程序与所用操作的含义，程序算出的答案是什么；Implementation（实现，aka scheduling）：答案在并行机器上如何被算出来——操作以什么（可能并行的）顺序执行？哪些操作由哪个线程、哪个执行单元、向量指令的哪个 lane 计算？把抽象的意义与实现的细节混为一谈（conflating）是本课程最常见的困惑来源。 学生目标：给定程序 + 编程模型的实现方式，能在脑中”trace”出并行计算机各部分在程序每一步做什么。
• 现实类比：”把 100 个箱子搬上楼”（语义）可以有多种实现：一个人搬 100 趟、10 个人各搬 10 趟、用电梯一次 20 箱……结果相同，但实现天差地别。
• 公式/图示：

  抽象层（语义）:  程序会算什么？        ← 与硬件无关
  实现层（调度）:  谁（线程/ALU/lane）在何时算哪部分？ ← 决定性能
  

8. ISPC 与 SPMD 编程模型

• 定义：ISPC = Intel SPMD Program Compiler（https://ispc.github.com/；推荐阅读 Matt Pharr 的 “The Story of ISPC”）。SPMD = Single Program, Multiple Data：只定义一个函数，但并行运行该函数的多个实例（instances），每个实例处理不同的数据。调用一个 ISPC 导出函数会spawn 一个 gang 的 program instances（如 8 个），所有实例并发执行同一份 ISPC 代码，每个实例拥有自己的一份局部变量副本；函数返回时所有实例都已完成，控制流回到单线程。
• 现实类比：同一个”批改试卷”函数，8 个助教（program instances）同时各批一叠——程序只有一份，数据有 8 份。
• 公式/图示：

  C 代码:  main() ──► ispc_sinx() ──► 回到 main()
                       │
                       ▼
        gang 的 8 个程序实例（programCount = 8）:
        [实例0][实例1][实例2]...[实例7]   并发执行同一份 ISPC 代码
        每个实例有独立的局部变量（value、numer...）
  

9. Program Count / Program Index / Gang（程序实例数 / 实例编号 / 线程组）

• 定义：
  • programCount：gang 中同时执行的实例个数（uniform 值）；
  • programIndex：当前实例在 gang 中的编号（varying 值：每个实例不同）；
  • gang：一次 ISPC 函数调用产生的全部程序实例的集合。 ISPC 实现 gang 的方式是 SIMD 指令：gang 中实例数 = 硬件的 SIMD 宽度（或其小倍数）；ISPC 编译器生成一个包含 SIMD 指令的 C++ 函数二进制（.o），C++ 侧正常链接该目标文件。
• 现实类比：全班点名——”第几组”（programCount）和”第几号”（programIndex）决定每个学生的身份；老师（一条 SIMD 指令）一次同时给整组布置任务。
• 公式/图示：

  programCount = 8（gang 大小，uniform）
  programIndex = 0..7（当前实例编号，varying）
  int idx = i + programIndex;   ← 每个实例算不同的 idx，处理不同的 x[idx]
  

10. Uniform vs Varying（ISPC 类型修饰符）

• 定义：
  • uniform：变量在所有程序实例中值相同，只有一份存储（如 uniform int terms、uniform float denom）。使用 uniform 纯粹是优化（省去每个实例各存一份的开销、允许标量/广播指令），与正确性无关——写成 varying 结果也对。
  • varying（默认）：每个程序实例有各自独立的副本（如 float value、int idx），对应 SIMD 向量里的一个 lane。
• 现实类比：全班同上一门课（uniform：课表只有一份）；但每人笔记不同（varying：每人一份）。
• 公式/图示：

  uniform int N;      ← 所有实例共享一份（标量/广播）
  int idx = ...;      ← 每个实例各一份（SIMD 的 8 个 lane）
  类型规则: varying 值不能塞进 uniform 变量（编译期类型错误），
           uniform 值可以广播成 varying。
  

11. Interleaved 与 Blocked 分配（iteration assignment）

• 定义：把 N 个数组元素分给 gang 内 programCount 个实例的两种基本方式：
  • Interleaved（交错分配，幻灯片 v1）：for (uniform int i=0; i<N; i+=programCount) { int idx = i + programIndex; ... }——实例 k 处理元素 k, k+8, k+16, …。同一时刻 8 个实例访问的 8 个地址在内存中连续 → 编译器可用一条 packed vector load（如 vmovaps/_mm256_load_ps） 高效实现 float value = x[idx]。
  • Blocked（分块分配，幻灯片 v2）：uniform int count = N/programCount; int start = programIndex*count; for (uniform int i=0; i<count; i++) { int idx = start + i; ... }——实例 k 处理连续块 [k·count, (k+1)·count)。同一时刻各实例访问的地址不连续 → 需要 gather 指令（如 vgatherdps/_mm256_i32gather_ps） 实现，gather 更复杂、更贵。
• 现实类比：发扑克牌——交错 = 轮流每人发一张（同一时刻每人拿到的牌”相邻”）；分块 = 一人拿一叠（同一时刻大家拿到的牌分散在各处）。
• 公式/图示：

  interleaved（8 实例，programCount=8）:  元素 0..7 同一时刻被 8 个实例各取一个
     实例0→x[0] 实例1→x[1] ... 实例7→x[7]   ← 连续 → packed load（1 条指令）
  blocked（8 实例，每实例 N/8 个）:          实例0 拿 x[0..N/8-1] ...
     同一时刻 8 个实例的地址相隔 N/8        ← 不连续 → gather（昂贵）
  

12. foreach（ISPC 关键语言结构）

• 定义：foreach (i = 0 ... N) { ... } 声明循环迭代是并行的——程序员声明”这些迭代是整个 gang（不是每个实例）要完成的”，由 ISPC 实现负责把迭代分配给 gang 里的程序实例。许多简单情况下，foreach 让程序员几乎像写串行程序一样表达并行代码（”independently, for each element in the input array… do this…”）。
• 现实类比：老板只说”这些活都要干完”（foreach 迭代集合），至于谁干哪件（分配）由组长（ISPC 实现）安排——程序员不必操心。
• 公式/图示（foreach 的四种可能实现，幻灯片）：

  抽象:  foreach (i = 0 ... N) { work(i); }
  实现1: 实例 0 串行执行全部迭代（if (programIndex == 0) for i...）
  实现2: 交错分配（等价 v1 的显式写法）
  实现3: 分块分配（等价 v2 的显式写法）
  实现4: 动态分配——uniform int nextIter; if (programIndex==0) nextIter=0;
         int i = atomic_add_local(&nextIter, 1); while (i < N) { work(i); i = atomic_add_local(&nextIter, 1); }
  （幻灯片文本提取中实现 1/4 的"programCount == 0"应为 programIndex == 0 的笔误）
  

13. Cross-Instance Operations（跨实例操作，ISPC 标准库）

• 定义：gang 内实例之间的数据交换原语（幻灯片给出的库函数）：
  • reduce_add(x)：把变量 x 在所有实例中的值相加（返回 uniform）；
  • reduce_min(a)：取 gang 内最小值；
  • broadcast(value, index)：把某个实例的值广播给 gang 内所有实例；
  • rotate(value, offset)（示例代码中写作 shift(value, offset)）：对每个 i，把实例 i 的值传给实例 (i+offset) % programCount（循环移位）。
• 现实类比：小组汇报——每人报自己的数（reduce_add 汇总）、把某人的答案告诉所有人（broadcast）、传纸条给邻座（shift/rotate）。
• 公式/图示：

  reduce_add:  sum = Σ (各实例的 partial)         → uniform
  broadcast:   所有实例获得实例 index 的值         → uniform
  shift/rotate: 实例 i 收到实例 (i-offset) 的值    → 仍是 varying
  

14. ISPC Tasks（任务并行，实现 multi-core）

• 定义：gang 抽象由 SIMD 指令实现，运行在一个核上的一个线程内——前面所有 ISPC 代码都只用一个核。ISPC 提供第二种抽象 task（任务） 用于实现多核执行：task 函数 + launch（启动若干任务实例，每个任务跑在独立线程/核上）+ sync（等待所有任务完成）。任务内部仍可用 foreach 获得 SIMD。具体机制留待 Assignment 1 实践。
• 现实类比：gang = 一个班同时做卷子（SIMD）；task = 把 4 个班分到 4 个教室同时考（多核），每个班内部仍可并行做题。
• 公式/图示：

  gang(SIMD):  一个线程内、一个核上，8 个 lane 并行
  task(多核):  多个线程/核上并行，每个 task 内再 SIMD
  组合: 4 核 × 每核 8-wide SIMD = 32 个数据同时处理
  

15. 更高层抽象：Data-Parallel 思维（map）

• 定义：如果语言不暴露 programIndex/programCount，程序员只写 foreach，那么 foreach 之外的一切都必须是 uniform 值和 uniform 逻辑；再进一步，连数组下标都不给，改成”对 collection 的每个元素调用一次函数”——y = map(dowork, x)——这就是 NumPy / PyTorch 用户熟悉的模型（np.vectorize、Z = X + Y）。更高的抽象 = 更少的实现自由度，但更接近”顺序思维”。
• 现实类比：点外卖只说”要一份宫保鸡丁”（map 抽象），不必指定”哪个厨师、哪口锅、第几分钟炒”（实现细节）。
• 公式/图示：

  float dowork(float x) { ... }
  Collection y = map(dowork, x);        ← 对每个元素独立调用
  # Python/NumPy 对应:
  Z = X + Y;         # 逐元素加法
  Zplus1 = np.vectorize(addOne)(Z);
  

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

示例 1：ISPC 版 sinx——program instances、gang、uniform/varying、两种分配

代码（ispc + cpp）：

// sinx.ispc —— ISPC 版 sinx（显式使用 programCount / programIndex）
// 编译：ispc sinx.ispc -o sinx.o -h sinx_ispc.h --target=avx2-i32x8
//       g++ -O2 main.cpp sinx.o -o sinx
export void ispc_sinx(
    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;          // varying：每个实例不同
        float value = x[idx];
        float numer = x[idx] * x[idx] * x[idx];
        uniform int denom = 6;               // 3!：uniform，所有实例共享
        uniform int sign = -1;               // uniform
        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;
    }
}

// main.cpp —— 调用 ISPC 编译出的函数（链接 sinx.o 即可，用法与普通 C++ 函数无异）
#include "sinx_ispc.h"
#include <vector>
#include <iostream>

int main() {
    const int N = 1024;
    const int terms = 5;
    std::vector<float> x(N), result(N);
    for (int i = 0; i < N; ++i) x[i] = (i % 100) / 100.0f;
    ispc_sinx(N, terms, x.data(), result.data());   // 调用 = spawn 一个 gang
    std::cout << "result[0] = " << result[0] << "\n";
    return 0;
}

【代码做了什么？】

• ISPC 代码与 Lecture 2 的 C 版 sinx 算法完全一致，区别只在”谁算哪个元素”：外层循环步长是 programCount，每个实例用 int idx = i + programIndex 算出自己负责的元素下标——实例 0 处理元素 0, 8, 16, …；实例 1 处理 1, 9, 17, …（interleaved 分配）。
• uniform int N / terms：所有实例共享同一份（例如循环边界必须 uniform，因为 for (uniform int i ...) 的循环变量是 uniform，迭代次数全 gang 一致）。
• float value/numer/idx（无修饰符 = varying）：每个实例各一份，对应 SIMD 的 8 个 lane。
• uniform int denom/sign：虽然循环体内它们被修改，但修改方式对所有实例一致（denom 的递推、sign 的翻转都与 i 无关），所以声明为 uniform 是合法的纯优化（编译器可用标量指令/广播，而不必存 8 份）。
• C++ 侧：ispc_sinx(...) 调用看起来与普通函数无异——ISPC 编译器已生成含 SIMD 指令的 sinx.o，正常链接即可。

【并行机制解说】

• 对应概念：SPMD / gang / program instances / uniform vs varying / interleaved assignment。
• 调用 ispc_sinx 时，spawn 一个 gang（如 8 个实例，programCount = 8，与 AVX2 的 8-wide 对应），全部实例并发执行同一份代码；返回时全部完成，控制流回到单线程 C++。
• 实现层面：ISPC 编译器把这段代码翻译成 SIMD 指令——int idx = i + programIndex 变成”向量加法”，float value = x[idx] 变成一条 packed vector load（因为 interleaved 分配下 8 个实例同一时刻访问的地址连续，vmovaps 一条指令搞定，对应 _mm256_load_ps）。这就是”抽象（SPMD 语义）vs 实现（SIMD 指令）”的活例子。
• 若改成 blocked 分配（v2：uniform int count = N/programCount; int start = programIndex*count;），同一时刻各实例访问的地址不连续，value = x[idx] 需要昂贵的 gather 指令（vgatherdps）——同一抽象语义，不同实现，性能天差地别（这也是为什么”调度/实现”值得专门学习）。

示例 2：foreach 版 saxpy——用抽象写”像串行”的并行代码

代码（ispc + cpp）：

// saxpy.ispc —— 用 foreach 表达数据并行：y = a*x + y
// 编译：ispc saxpy.ispc -o saxpy.o -h saxpy_ispc.h --target=avx2-i32x8
//       g++ -O2 main.cpp saxpy.o -o saxpy
export void saxpy(uniform int n, uniform float a,
                  uniform float* x, uniform float* y)
{
    // foreach：声明这些迭代由整个 gang 完成，迭代如何分给实例由 ISPC 决定
    foreach (i = 0 ... n)
    {
        y[i] = a * x[i] + y[i];   // 对每个元素独立做一次乘加
    }
}

// main.cpp
#include "saxpy_ispc.h"
#include <vector>
#include <iostream>

int main() {
    const int n = 1 << 20;
    const float a = 2.0f;
    // 注意：ISPC 默认假设传入指针 16 字节对齐；std::vector 通常满足，
    // 若目标为 avx2 且编译器选择对齐访问，可用 aligned_alloc(32, ...) 保证 32 字节对齐
    std::vector<float> x(n, 1.0f), y(n, 2.0f);
    saxpy(n, a, x.data(), y.data());
    std::cout << "y[0] = " << y[0] << " (expect " << a * 1.0f + 2.0f << ")\n";
    return 0;
}

【代码做了什么？】

• saxpy 对 n 个元素逐个执行 y[i] = a*x[i] + y[i]（经典的 SAXPY 操作）。foreach (i = 0 ... n) 声明循环迭代相互独立、且由整个 gang 完成——程序员完全不写 programIndex、programCount，不关心实例如何分工，代码几乎就是串行 C 的样子。
• main 构造两个长度为 n 的数组（x 全 1、y 全 2），调用后验证 y[0] == 2*1+2 == 4。

【并行机制解说】

• 对应概念：foreach 抽象 / abstraction vs implementation。
• foreach 的语义是”这些迭代都要做、且互相独立”；实现（由 ISPC 决定）可以是幻灯片列举的任意一种：实例 0 串行全做（最差）、交错分配、分块分配、或 atomic_add_local 动态分配。程序的结果不受实现选择影响——这正是抽象的意义：语义与调度解耦。
• 与示例 1 对比：示例 1 用 programIndex/programCount 显式控制每个实例的工作（低层、可写出”只有特定 programCount 才正确”的程序）；示例 2 用 foreach 把分配权交给编译器（高层、更安全）。两者的等价关系：foreach 的典型展开就是示例 1 的交错写法（for (uniform int i=0; i<N; i+=programCount) { int idx = i + programIndex; ... }）。
• 注意 foreach 的陷阱：迭代之间不能有数据依赖。例如幻灯片 shift_negative 程序——if (i>=1 && x[i]<0) y[i-1] = x[i]; else y[i] = x[i];——迭代 i 可能写 y[i-1]、迭代 i-1 也可能写 y[i-1]，多个迭代写同一地址，输出未定义。foreach 只保证迭代独立时语义正确，程序员仍需保证”可安全并行”。

示例 3：ISPC 数组求和——uniform/varying 类型规则与跨实例归约

代码（ispc）：

// sum.ispc —— 数组求和的三种写法，演示 uniform/varying 类型规则

// 写法 1（错误）：把 varying 的 x[i] 累加进 uniform 变量 → 编译期类型错误
export uniform float sum_incorrect_1(uniform int N, uniform float* x) {
    uniform float sum = 0.0f;      // uniform：整个 gang 只有一份 sum
    foreach (i = 0 ... N) {
        sum += x[i];               // x[i] 对每个程序实例取值不同（varying）
    }                              // 8 个不同的 x[i] 无法"合并"进唯一一份 uniform 变量
    return sum;                    // → compile-time type error
}

// 写法 2（错误）：varying 的 sum 无法作为 uniform 返回值交给 C 代码
export uniform float sum_incorrect_2(uniform int N, uniform float* x) {
    float sum = 0.0f;              // varying：每个实例各有一份 sum
    foreach (i = 0 ... N) {
        sum += x[i];               // 每个实例累加自己的部分，语法上没问题
    }
    return sum;                    // 每个实例都有一份 sum —— C 代码只接收一个返回值
}                                  // → compile-time type error

// 写法 3（正确）：每实例私有 partial + 跨实例归约 reduce_add
export uniform float sum_array(uniform int N, uniform float* x) {
    uniform float sum;
    float partial = 0.0f;          // varying：每实例私有累加，实例间零通信
    foreach (i = 0 ... N) {
        partial += x[i];
    }
    sum = reduce_add(partial);     // 跨实例通信原语：把 gang 内所有 partial 相加
    return sum;                    // reduce_add 返回 uniform float
}

// 与 sum_array 语义等价的 C + AVX intrinsics 实现（幻灯片"自测"题）
// 理解"为什么这个实现正确实现了 ISPC gang 抽象的语义"，就说明你掌握了 ISPC
#include <immintrin.h>
float sum_summary_AVX(int N, float* x) {   // 调用方需保证 x 32 字节对齐
    alignas(32) float tmp[8];              // 幻灯片原注释"16 字节对齐"按 AVX 应为 32
    __m256 partial = _mm256_set1_ps(0.0f); // 幻灯片原文 __mm256 及 broadcast 用法为笔误
    for (int i = 0; i < N; i += 8)
        partial = _mm256_add_ps(partial, _mm256_load_ps(&x[i]));
    _mm256_store_ps(tmp, partial);         // 8 个 lane 的局部和落盘
    float sum = 0.f;
    for (int i = 0; i < 8; i++)
        sum += tmp[i];                     // 模拟 reduce_add 的水平归约
    return sum;
}

【代码做了什么？】

• 写法 1 和 2 是两个典型的编译期类型错误：varying 值（每个实例不同）不能写进 uniform 变量；varying 变量也不能作为 uniform 返回值交给 C 代码——类型系统在编译期就拦住”跨实例数据合并”这种需要显式原语的操作。
• 写法 3 是正确模式：每个实例先用私有的 varying partial 累加自己负责的那部分元素（实例间零通信、零同步，性能最好），最后用标准库 reduce_add(partial) 跨实例归约得到总和。
• 底下的 AVX 等价实现展示了 gang 抽象在 AVX2 上如何落地：__m256 partial 就是 8 个实例各自的 partial，_mm256_add_ps 是 foreach 循环的 SIMD 展开，最后的 8 次标量相加就是 reduce_add。

【并行机制解说】

• 对应概念：uniform vs varying 类型规则 / cross-instance operations（reduce_add）。
• 关键洞察：没有跨实例通信原语，就无法在 ISPC 内做”合并不同实例数据”的归约——这正是”低层语言语义严格”的体现（幻灯片总结：ISPC 是低层语言，暴露 programIndex/programCount 让程序员定义每个实例做什么，代价是可以写出输出未定义、或只对特定 programCount 正确的程序）。
• reduce_add 在 SIMD 实现上对应水平归约（把向量 8 个 lane 的值相加成标量）——这通常比逐元素运算贵，因此好的并行程序应尽量减少归约次数（每实例先本地累加，最后只归约一次，而不是每个元素归约一次）。
• 进阶（幻灯片”高级协作”示例 vec8product）：还可以用 shift/rotate 原语在 3 步内（lg 8 = 3）算出 8 个元素的乘积——每步 shift 把值沿实例编号移动 1/2/4 位，配合 programIndex % 2/4/8 == 0 的选择性相乘，构建一棵归约树。这类”实例间协作”程序正确性只在特定 gang 大小下成立（注释里明确”assumes the gang size is 8”）。

示例 4：ISPC task 并行——launch/sync 实现多核执行

代码（ispc + cpp）：

// saxpy_tasks.ispc —— ISPC 任务并行：把工作拆到多个核上
// 编译：ispc saxpy_tasks.ispc -o saxpy_tasks.o -h saxpy_tasks_ispc.h --target=avx2-i32x8
//       g++ -O2 main.cpp saxpy_tasks.o -o saxpy_tasks -pthread   （ISPC 任务需要 pthread）

// task 函数：处理数组的一段连续区间
task void saxpy_chunk(uniform int n, uniform float a,
                      uniform float* x, uniform float* y)
{
    // taskIndex / taskCount 是 ISPC 内置变量：本任务编号 / 本次 launch 的任务总数
    uniform int count = n / taskCount;
    uniform int start = taskIndex * count;        // 分块分配：每个任务一段
    foreach (i = start ... start + count) {       // 任务内部仍可用 foreach 获得 SIMD
        y[i] = a * x[i] + y[i];
    }
}

export void saxpy_tasks(uniform int n, uniform float a,
                        uniform float* x, uniform float* y)
{
    uniform int ntasks = 4;                       // 拆 4 个任务 → 4 个核并行
    launch[ntasks] saxpy_chunk(n, a, x, y);       // 启动 ntasks 个任务实例（各得 taskIndex）
    sync;                                         // 等待所有任务完成
}

// main.cpp —— 与普通 ISPC 函数调用方式相同
#include "saxpy_tasks_ispc.h"
#include <vector>
#include <iostream>

int main() {
    const int n = 1 << 20;
    const float a = 2.0f;
    std::vector<float> x(n, 1.0f), y(n, 2.0f);
    saxpy_tasks(n, a, x.data(), y.data());
    std::cout << "y[0] = " << y[0] << " (expect 4)\n";
    return 0;
}

【代码做了什么？】

• saxpy_chunk 是 task 函数：用内置变量 taskIndex（本任务编号）和 taskCount（任务总数）算出自己负责的连续区间，区间内再用 foreach 逐元素做 saxpy——每个任务内部仍然是 SIMD（gang）执行。
• saxpy_tasks 是导出入口：launch[4] saxpy_chunk(...) 启动 4 个任务实例（系统把它们调度到 4 个核/线程上），sync 等待全部完成。launch/sync 就是本讲的”同步点”。

【并行机制解说】

• 对应概念：ISPC tasks / multi-core 执行 / gang 与 task 的区别。
• 层次关系（幻灯片明确强调）：gang 抽象由 SIMD 指令实现，运行在一个核上的一个线程里——示例 1–3 的所有 ISPC 代码只用了四个核中的一个；task 抽象才实现多核。组合起来：4 个任务（4 核）× 每任务 8-wide SIMD = 同时处理 32 个元素——这正是 Assignment 1 中”四核 + AVX”获得 ~32–40x 加速的结构来源（再加上 hyper-threading 与编译器优化）。
• 与硬件对照：任务对应硬件多线程/多核（TLP），gang/foreach 对应 SIMD（DLP）；launch/sync 是显式的并行创建与同步点，与 Lecture 2 的 std::thread + join 在语义上同构。
• 幻灯片还预告了”更高层抽象”的走向：隐藏 programIndex/programCount、甚至隐藏数组下标，变成 map(dowork, x) 式的 collection 抽象（NumPy/PyTorch 模型）——抽象层次越高，程序员越不需要关心实现，但可表达的低层技巧（如 vec8product 的树形归约）也越难实现。

三、关键要点

1. Latency 与 Bandwidth 是两个正交概念：延迟是”一次操作花多久”，带宽是”单位时间能做多少次”（高速公路：提速 vs 加车道；洗衣：复制资源 vs 流水线）。加带宽不降延迟；瓶颈由最细的管子决定（50 L/s）。内存带宽的定义是”内存系统向处理器提供数据的速率”（如 20 GB/s）。
2. 现代并行机器常常是 bandwidth-limited：逐元素向量乘法每个元素要 3 次内存操作（12 字节）才换来 1 次 MUL；V100 需要约 98 TB/s 才能喂饱 5120 个 ALU，实际只有 900 GB/s → 效率 <1%（八核 Xeon 配 76 GB/s 总线约 3%）。克服带宽限制是面向吞吐优化系统的软件开发者最重要的挑战。
3. 带宽受限下，多线程/低延迟都救不了你：稳态下核心利用率只取决于”指令吞吐 vs 内存吞吐”，与延迟和未完成请求数无关。性能程序必须减少取数频率：复用已加载数据（temporal locality）、跨线程共享数据、用更多算术换更少搬运（”math is free”）。
4. 抽象（语义）≠ 实现（调度）：同一个 ISPC 程序（semantics 固定）可以有多种实现——交错/分块/动态分配迭代、packed load 或 gather、SIMD 或任务。把两者混为一谈是本课程最常见的困惑来源；好学生应能”在脑中 trace 出每个线程/ALU/lane 在每一步做什么”。
5. ISPC 的三层能力：foreach 让程序员像写串行程序一样写数据并行代码（迭代独立性由程序员保证）；programIndex/programCount/uniform/varying 让程序员低层控制每个实例的工作与数据；reduce_add/broadcast/shift 等跨实例原语 + task/launch/sync 实现归约协作与多核扩展。类型系统用编译期错误拦住”varying 塞进 uniform”这类错误。

四、常见陷阱与注意事项

1. 混淆 latency 与 bandwidth：以为”内存延迟低 = 性能好”。带宽受限的程序（如逐元素乘法）延迟再低也白搭；反之，延迟高但带宽充足时，多线程隐藏延迟即可。先判断程序是 latency-bound 还是 bandwidth-bound。
2. 忽视 12 字节/1 MUL 这类”算术强度”问题：每个数据只用一次的流式访问是带宽杀手。应尽量提高数据复用（缓存分块、线程间共享、寄存器内累加），而不是堆更多 ALU。
3. 把 uniform 当正确性工具 / 乱用 varying：uniform 只是优化（”Its use is purely an optimization. Not needed for correctness”）；而把 varying 值赋给 uniform 变量（uniform sum += x[i]）或把 varying 当 uniform 返回值，都是编译期错误——需要显式跨实例原语（reduce_add 等）。
4. 写 foreach 时留下迭代间数据依赖：shift_negative 一类程序（迭代 i 写 y[i-1]）多个迭代写同一地址，输出未定义——foreach 不检查依赖，正确性全靠程序员保证”迭代可安全并行”。
5. 以为 ISPC 自动用满多核：gang 由 SIMD 实现，只跑在一个核上；要上多核必须显式使用 task + launch/sync（Assignment 1 的关键一步）。同理，别以为 compiler 自动向量化一定生效——显式用 ISPC/foreach 才可控。
6. 忽视对齐与编译细节：ISPC 默认假设传入指针 16 字节对齐；AVX 的 256 位访问最好 32 字节对齐（aligned_alloc(32, ...)）。ISPC 代码用 ispc 编译器单独编译（--target=avx2-i32x8 等），任务并行还需 -pthread 链接。

五、思考题（带答案）

Q1. 幻灯片思想实验：为什么”逐元素向量乘法”在 V100 上效率 <1%，却仍然比八核 CPU 快？这说明什么？

• 答案：该计算每个元素需 3 次内存操作（12 字节）换 1 次 MUL，是极端带宽受限（bandwidth-limited）。V100 有 5120 个 fp32 ALU，要喂饱它们需要约 98 TB/s（= 5120 × 1.6 GHz × 12 B），而 HBM2 只有 900 GB/s → 效率 <1%。八核 CPU 效率约 3%，但其 ALU 总量远小于 GPU（8 核 × 标量/向量单元），所以绝对吞吐仍远低于 GPU。结论：效率（利用了多少硬件能力）与绝对性能（总吞吐）是两回事；对带宽受限程序，提升方向是减少每单位计算的数据搬运（复用、共享、算术换搬运），而不是加 ALU。

Q2. 为什么说”稳态下核心利用率只取决于指令吞吐与内存吞吐的比值，与延迟无关”？

• 答案：在幻灯片”load 64 字节 + 两次 add”的例子中，稳态时内存每时钟只能提供 8 字节，核心每 8 字节完成 1 次 load + 2 次 add；无论延迟是 8 周期还是 800 周期，只要未完成请求数足够覆盖延迟（用多线程或并发 load），稳态吞吐都由”内存供给速率”决定。延迟只影响”需要多少未完成请求/多少线程来填满管道”，不影响最终吞吐上限——这是 latency hiding 与 bandwidth 限制的根本区别。

Q3. foreach 的语义与实现有什么关系？请用”交错分配 + packed load”说明一个语义可以对应多种实现，并解释为什么 blocked 分配更慢。

• 答案：foreach 的语义只是”迭代集合互相独立、必须全部完成”，不规定哪个实例做哪个迭代（abstraction vs implementation）。ISPC 可以选择交错分配（实例 k 处理 k, k+8, …）：同一时刻 8 个实例访问连续地址，float value = x[idx] 可编译成一条 packed vector load（vmovaps/_mm256_load_ps）；也可以选择 blocked 分配（实例 k 处理连续块）：同一时刻各实例访问的地址相隔 N/8，只能编译成昂贵的 gather 指令（vgatherdps）。同一语义、两种实现、性能不同——这就是为什么理解”实现/调度”是优化并行程序的前提。

注意：本讲 ISPC 内容直接对应 Assignment 1（Analyzing Parallel Program Performance on a Quad-Core CPU）——作业要求先用 ISPC 的 foreach/task 在四核 CPU 上并行化程序（对比 -O3 单线程基线），再定量分析多核、SIMD、超线程各自的贡献（预期 ~32–40x 加速），并手写 AVX intrinsics 复现 ISPC 生成的向量代码（对应本讲”ISPC 用 SIMD 实现 gang”与 mask 处理分支的内容）。