Assignment 1 Report: Performance Analysis on a Quad-Core CPU

0. 环境配置

Assignment 1 的程序大量使用 ISPC（Intel SPMD Program Compiler）编译。课程要求最终性能数据在 Stanford myth[51-66].stanford.edu 机器上跑（4-core 4.2 GHz Intel Core i7，支持 AVX2 8-wide SIMD + Hyper-Threading）。本机也安装一份 ISPC 用于本地调试和"for kicks"的对比测试。

0.1 ISPC 编译器安装

截至本文档写作时，ISPC 最新稳定版本为 v1.31.0（2026-06-25 发布，基于 LLVM 23）。主要新增：

• 针对 Intel Nova Lake 处理器的 avx10.2nvl-* 系列目标
• 两种新的 fast-math 模式（balanced / aggressive）
• 标准库新增 erf/erfc/expm1/log1p/sinh/cosh/tanh
• reduce_add() 返回类型改为与输入同类型（Breaking change）
• 基于 LLVM 23，已不再支持 LLVM 18/19

⚠️ 注意：课程 README 给出的 wget 示例是 v1.28.1（2025 学期初版本）。v1.31.0 的标准库有 breaking change，如果跑课程代码遇到 reduce_add 相关报错，可回退到 v1.28.1。本机用最新版即可，myth 机器按课程指引安装。

方式 1：Homebrew（本机首选，最简单）

本机环境：macOS x86_64 + Homebrew 6.0.12。

brew install ispc
ispc --version   # 应输出: Intel(r) ISPC, 1.31.0 (或更高)

方式 2：官方二进制（拿指定版本 / 装到 myth Linux 机器）

myth 机器（Linux x86_64） —— 课程官方推荐流程：

# 在 myth 上，下载 Linux 二进制
wget https://github.com/ispc/ispc/releases/download/v1.28.1/ispc-v1.28.1-linux.tar.gz
tar -xvf ispc-v1.28.1-linux.tar.gz
# 加入 PATH（写进 ~/.bashrc 持久化）
export PATH=$PATH:${HOME}/ispc-v1.28.1-linux/bin
ispc --version

若想用最新版，把 URL 与目录名里的 v1.28.1 换成 v1.31.0 即可。

本机 macOS x86_64 —— 手动下载最新 v1.31.0：

curl -LO https://github.com/ispc/ispc/releases/download/v1.31.0/ispc-v1.31.0-macos-x86_64.tar.gz
tar -xzf ispc-v1.31.0-macos-x86_64.tar.gz
export PATH="$PWD/ispc-v1.31.0-macos-x86_64/bin:$PATH"
ispc --version

• Apple Silicon (arm64) 把 URL 里 macos-x86_64 换成 macos-arm64
• 想一份二进制同时支持 x86_64 + arm64，用 ispc-v1.31.0-macos-universal.tar.gz
• 所有平台 release 资产见：https://github.com/ispc/ispc/releases/tag/v1.31.0

方式 3：从源码构建（需要 trunk / 自定义 LLVM）

git clone https://github.com/ispc/ispc.git
cd ispc
# 构建指引: https://github.com/ispc/ispc/wiki/ISPC-Development-Guide

验证安装

本机（macOS x86_64，Homebrew 安装）实际输出：

$ ispc --version
Intel(r) Implicit SPMD Program Compiler (Intel(r) ISPC), 1.31.0 (build commit  @ 20260625, LLVM 22.1.8)

📝 观察：Homebrew 装出来的 v1.31.0 实际链接的是 LLVM 22.1.8，而官方 release notes 说 v1.31.0 默认基于 LLVM 23。这是因为 Homebrew formula 自行构建时 pin 的 LLVM 版本与官方预编译二进制不同。对 CS149 作业（只用 --target=avx2）没有影响，但记一笔以防后续遇到 target 相关的差异。

myth 机器（Linux，按课程指引 wget v1.28.1）预期输出形如：

$ ispc --version
Intel(r) Implicit SPMD Program Compiler (Intel(r) ISPC), 1.28.1 (build commit ..., LLVM ...)

0.2 机器信息

本机机器信息采集：

# 一键拿全本机硬件信息
system_profiler SPHardwareDataType

# CPU 型号 / CPUID / 核数 / cache / 频率
sysctl -n machdep.cpu.brand_string
sysctl -n machdep.cpu.vendor machdep.cpu.family machdep.cpu.model machdep.cpu.stepping
sysctl -n hw.physicalcpu hw.logicalcpu hw.ncpu
sysctl -n hw.l1icachesize hw.l1dcachesize hw.l2cachesize hw.l3cachesize
sysctl -n hw.cpufrequency hw.cpufrequency_max hw.cpufrequency_min

# SIMD/AVX 支持标志
sysctl -a | grep -iE 'avx|sse|fma'

本机硬件信息（由 system_profiler SPHardwareDataType + sysctl 采集）：

Model Name:           MacBook Pro (MacBookPro16,3, 2020 13")
Processor Name:       Quad-Core Intel Core i5
Processor Speed:      1.4 GHz (base)   -- turbo up to 3.9 GHz
Number of Cores:      4 (physical) / 8 (logical, HT enabled)
L1 I/D Cache:         32 KB / 32 KB (per core)
L2 Cache (per core):  256 KB
L3 Cache (shared):    6 MB
Memory:               16 GB
CPUID:                family 6, model 142 (0x8E), stepping 10  -- Coffee Lake / Comet Lake-U

SIMD 特性（sysctl hw.optional.* + machdep.cpu.features）：

SSE SSE2 SSE3 SSSE3 SSE4.1 SSE4.2   ✅
AVX1.0 AVX2 FMA F16C                 ✅   ← 8-wide 单精度 SIMD, 与 myth 同代
AVX-512 (f/cd/dq/bw/vl/ifma/vbmi)    ❌   ← 本机不支持

📝 关键观察：本机与 myth 在并行维度上是同构的——都是 4 物理核 / 8 逻辑线程 + AVX2 8-wide SIMD。因此本机跑出来的相对 speedup 比值（如 8 线程 vs 1 线程、ISPC vs serial）应与 myth 数量级接近，可以直接用来验证算法正确性。但绝对时间会差约 3×（i5-8257U base 1.4 GHz vs i7-7700K base 4.2 GHz，且本机是低压 U 系列、turbo 也低）。课程最终性能数据仍以 myth 为准。

一个微妙的差异：本机不支持 AVX-512（myth 的 Kaby Lake 同样不支持），所以 Program 3/4/5 里 --target=avx2 在两边语义完全一致，可比性很好。

1. Program 1: Parallel Fractal Generation Using Threads

目标：用 std::thread 并行化 Mandelbrot 图像生成，理解多核 + Hyper-Threading 的性能表现。

任务清单：

• [x] 修改 mandelbrotThread.cpp 的 workerThreadStart：2 线程上下分屏
• [x] 扩展到 2/3/4/5/6/7/8 线程，按 block 切分
• [x] 画 View 1 的 speedup vs 线程数曲线，分析是否线性
• [x] 在 workerThreadStart 加 timing，解释 3 线程那一点的异常
• [x] 改进 work mapping，达到 7-8x speedup（View 1 + View 2）
• [x] 跑 16 线程，分析为何不比 8 线程快

Task 1： 初始版本 2 线程

实现方式：thread 0 计算图像上半行、thread 1 计算下半行（简单 spatial division）。

$ ./mandelbrot -t 2
[mandelbrot serial]:            [766.629] ms
Wrote image file mandelbrot-serial.ppm
[mandelbrot thread]:            [413.267] ms
Wrote image file mandelbrot-thread.ppm
                                (1.86x speedup from 2 threads)

初步观察：2 线程获得 1.86x speedup，接近理想值 2×。说明上下分屏对 View 1 是合理的 load-balancing——两个像素区域计算量大致相等。下一步扩线程数看 scaling。

Task 2：扩展至 2~8 线程，block 切分

实现方式：N 线程时，第 t 个线程计算行号 i where (i / N) == t（将图像分为 N 等份 block，每块由一个线程独占）。

测试命令：

./mandelbrot -t <线程数>                   → VIEW 1（默认）
./mandelbrot -t <线程数> --view 2          → VIEW 2

Speedup 是否线性？为什么？（以 View 1 为主，View 2 为对照）

答案是 不线性。整体呈现 S 形：2→8 线程从 1.84× → 3.85×（View 1），增长趋势为增速先快后略缓。具体原因如下：

1. Task 1 初始版本 vs Task 2 block 版本的差异：

   • Task 1 的"上下分屏"（top/bottom halves）只有 2 线程，恰好把计算量均匀的分割（View 1 左右对称），所以 2 线程时是 1.84× ≈ 2×。
   • Task 2 改用 N 等份 block 切分后，随着 thread count > 2，每个线程分到的行数变少但负载均衡性更好（不再依赖单个线程负担过重），所以能持续提升。

2. 3 线程那个凹口——为什么反而比 2 线程差？

   • 采用的是连续块分配（contiguous block），非交错分配：thread t 负责 rows [t*rowsPerThread, (t+1)*rowsPerThread)。因此 3 线程时的分布为：

     thread 0: rows 0  ~ H/3-1      （上部）
     thread 1: rows H/3 ~ 2H/3-1    （中部） ← 恰好跨越 Mandelbrot set 边界密集区，迭代次数最多 → 最慢 ⚠️
     thread 2: rows 2H/3 ~ H-1      （下部）
     

   • join() 必须等最慢线程完成。View 1 的 Mandelbrot set 沿虚轴对称（y ↔ -y），所以上下部计算量接近；但中部包含了完整的 antanna + 主圆盘，迭代深度最大，导致该线程显著阻塞全局。
   • 此外还叠加了 tail imbalance：当 height % N != 0 时，多余行全部分配给最后一个 thread。例如 3-thread 若余 1 行，或 7-thread 若余 1 行，最后一条线程额外负担更多。这种"分配不均匀 + 特定 thread count 下的 row offset"效应，使得不同 N 值的 speedup 跳变不平滑。
   • 作为对照：Task 1 的 top/bottom 分割（2 threads）之所以好（1.86× ≈ 2×），正是因为 View 1 的 y ↔ -y 对称性使上下两半天然均衡。但这只适合 N=2 的场景，无法推广到更高并发。
   • View 2 对照：View 2 的 3-thread speedup 是 2.21×（远好于 View 1 的 1.57×），因为 View 2 的 mini-sets 在空间上分散，3-block 分割时每个 block 都分摊到了若干 mini-sets，没有单一块被全部压垮。

3. 8 线程达到 3.85×（View 1）/ 3.36×（View 2）——接近物理核心数上限的原因：

   • 本 Machine 共 4 physical cores + HT → 8 logical threads。N=8 时每个 logical core 恰好被一个线程独占，无调度竞争、无 context-switching penalty。
   • HT overhead 相对可控：Mandelbrot 是纯计算密集型的浮点迭代（非 memory-bound），同一 physical core 上的两个 logical threads 可以有效 overlap（利用不同的执行端口和资源），额外贡献约 15\%–20\% 的性能提升。因此从 N=4（View 1: ~2.24×）到 N=8（View 1: ~3.85×）有显著增益，但并非翻倍——HT logical core 的效用低于完整 physical core。
   • tail imbalance 依然存在，但当图像分辨率足够大时（每线程分到数千行），尾部偏移行的影响可以忽略。

View 1 vs View 2 对比观察：

View 2 是 Mandelbrot set 的一个 zoomed-in 区域（见上图），布满了密集的 mini-Mandelbrot "bubbles"（亮白色区域），迭代次数极高。与 View 1 不同，View 2 的 computation 在空间上没有上下对称性，但在垂直方向上 mini-sets 的分布更分散。

1. 2 线程：View 2 (1.61×) < View 1 (1.84×)

   • View 1 的 main cardioid 有完美的 y ↔ -y 对称性，所以 top/bottom halves 天然均衡。
   • View 2 没有这种对称性，且 mini-sets 密集区偏向图像下部（左下角的亮白大 blob）。因此 thread 0（上部）较轻，thread 1（下部）较重，load imbalance 直接导致 speedup 下降。

2. 3 线程：View 2 (2.21×) >> View 1 (1.57×)

   • View 1 的 3-block 分配把主 cardioid 边界全部压给了中间块（thread 1），导致严重瓶颈。
   • View 2 的 mini-sets 虽然多但分散在多个 block 里：3-block 分割时，每个 block 都分摊到了几个 mini-sets，没有单一块被特别压垮。这是 View 2 对 3-thread 更友好的根本原因。

3. 8 线程：View 2 (3.36×) < View 1 (3.85×)，且 7→8 零增长

   • 8 线程时 serial time 突然从 ~408ms 跳到 ~535ms，thread time 也从 121ms 涨到 159ms。这与 View 2 本身无关，更像是 8 active logical threads 占满 4 physical cores 后 turbo frequency 下降（thermal throttling / power limit）导致的系统级 slowdown。
   • 这也说明：当全部 logical cores 被占满时，benchmark 的 reproducibility 下降，需要在 myth 机器上跑来确认。

Task 3：Per-thread timing 验证 load imbalance 假设

在 workerThreadStart() 头尾插入 CycleTimer::currentSeconds() 计时，输出每个线程的 wall time。每个配置跑 5 次取 mean。

View 1 - per-thread time（mean ms）：

View 2 - per-thread time（mean ms）：

关键观察：

1. View 1 呈 "U 形" 或 "单峰" 分布--中间线程最慢，两端最快

   • 3 threads：T0=153ms, T1=392ms, T2=153ms -> T1 是 T0/T2 的 2.6×
   • 4 threads：T0=70, T1=281, T2=282, T3=71 -> 两个中间线程承担了 ~80% 总 work
   • 8 threads：T0=43, T1=114, T2=263, T3=369, T4=348, T5=264, T6=124, T7=25 -> 中央两个 thread (T3, T4) 是瓶颈
   • 完美印证了 Task 2 的假设：contiguous block 分配下，中间线程恰好覆盖 Mandelbrot set 边界密集区，迭代次数远高于边缘线程。join() 等到 T3/T4 完成，speedup 上限被压在 ~3.85×。

2. View 2 呈 "单调递减" 分布--顶部线程最慢，越往下越快

   • 2 threads：T0=345ms, T1=252ms -> 顶部 mini-sets 密集，底部稀疏，1.37× 不均衡 -> 解释了 View 2 的 2-thread speedup (1.61×) 比 View 1 (1.84×) 差
   • 4 threads：T0=206, T1=115, T2=113, T3=109 -> T0 独占顶部密集区，其他三个线程接近均匀
   • 8 threads：T0=147ms, T1=100, T2=74, T3=74, T4=79, T5=70, T6=77, T7=65 -> T0 是瓶颈，但 max/min 比 = 2.3×，远好于 View 1 的 8-thread (369/25 = 14.8×)
   • 解释了 View 2 的 3-thread 反而比 View 1 好：View 2 的 work 在垂直方向近似 linear 递减，3-block 分割时各块 work 比例约为 3:2:2（T0=241, T1=158, T2=147），不均衡程度远低于 View 1 的 1:2.5:1。

3. 量化 load imbalance 对 speedup 的限制

   定义 imbalance ratio = max_thread_time / min_thread_time。理论上 speedup 上限 ≈ N / imbalance_ratio（最慢线程拖累整体）。

   | N | View 1 imbalance | View 1 实际 speedup | View 2 imbalance | View 2 实际 speedup | |----|-------------------|---------------------|-------------------|---------------------| | 2 | 1.00× | 1.84× | 1.37× | 1.61× | | 3 | 2.56× | 1.57× | 1.64× | 2.21× | | 4 | 4.03× | 2.24× | 1.89× | 2.40× | | 8 | 14.78× | 3.85× | 2.26× | 3.36× |

   趋势很清楚：View 1 的 imbalance ratio 随 N 增长急剧恶化（2->8 threads：1× -> 14.8×），而 View 2 始终保持在 1.4×~2.3× 之间。这就是为什么 View 1 在高 thread count 时 speedup 增长放缓，而 View 2 反而能稳定接近线性（直到 8-thread 时 thermal throttling 打断）。

4. 结论：Task 2 中关于 "中间行密集区拖累 join()" 的假设完全成立。要达到 7-8× speedup，必须打破 contiguous block 分配，让每个线程分到的行跨越整个图像高度（interleaved 或更细粒度的 partition），使密集区分散到所有线程。这就是 Task 4 要做的事。

Task 4：改进 work mapping -- cyclic row assignment

前面的 per-thread timing 图说明，问题不在 std::thread 本身，而在 work decomposition。连续块划分会把空间上连续的高计算量区域集中到少数线程：

• View 1：中心行附近最重，所以 contiguous block 会让中间 thread 成为瓶颈。
• View 2：顶部区域最重，所以 contiguous block 会让低编号 thread 成为瓶颈。

改进策略采用一个简单的静态交错划分（cyclic row assignment）：

thread 0: rows 0, N, 2N, 3N, ...
thread 1: rows 1, N+1, 2N+1, 3N+1, ...
...
thread t: rows t, t+N, t+2N, ...

其中 N = numThreads。这样每个线程都从整张图像的不同高度位置抽样到行，而不是拿到一整块连续区域。由于 Mandelbrot 的计算量主要随行位置呈空间聚集分布，交错行分配会把重行和轻行平均摊给所有线程。

这个策略满足题目要求：

• 静态分配：每个线程根据 threadId 和 numThreads 独立算出自己负责的行。
• 无同步/通信：线程之间不需要队列、锁、atomic 或 barrier。
• 单一策略适用于所有线程数：同一段代码适用于 2 到 8 线程，也适用于其他 numThreads。
• 不会发生写冲突：每个线程只写自己负责的行，输出 buffer 中的像素区域互不重叠。

cacheline 友好性分析

bilyz98 的博客指出一个细节：cyclic 分配下，同一时刻所有线程访问的行索引相邻（thread t 在 row r，thread t+1 在 row r+1），输出 buffer 写入位置也相邻。这意味着：

• 读：图像参数 (x0/y0/x1/y1) 是共享只读，所有线程命中同一份 cache 副本。
• 写：output 数组按行 stride 写，相邻线程写相邻行，落进同一 cacheline -> false sharing 风险。

但因为每行宽度 ≈ 1200 × 4B = 4.8KB >> 64B cacheline，相邻行的写实际上落在不同 cacheline，false sharing 可忽略。这个分析解释了为什么 cyclic 没有引入意外的 cache penalty。

最终 8-thread speedup（本机）：

相比 contiguous block 版本，cyclic row assignment 显著改善了 scaling：

• View 1：8-thread 从 block 版约 3.85× 提升到单独复测的 5.80×。
• View 2：8-thread 从 block 版约 3.36× 提升到单独复测的 5.99×。
• View 1 的 3-thread 凹口被修复：从 1.57× 提升到 improved mapping sweep 中的 2.72×。

本机没有达到题目中期待的 7-8×，主要原因是本机是 4 physical cores / 8 logical threads 的低压移动 CPU。8 个 worker 会占满所有 logical threads，触发 turbo frequency drop / thermal throttling，尤其是连续跑完整 sweep 时 View 1 的 8-thread 点会下降到约 5×。不过 per-thread timing 已经说明新的划分方式把工作量均匀摊开了；剩余 gap 主要来自硬件频率和 Hyper-Threading 的非理想 scaling，而不是 work mapping 的 load imbalance。最终提交到课程 myth 机器时，应使用同一份 cyclic row assignment 代码重新记录最终 8-thread speedup。

Task 5：16 线程是否比 8 线程更快？

用同一份 cyclic row assignment 代码跑 16 线程：

$ ./mandelbrot -t 16 --view 2
[mandelbrot serial]:            [279.488] ms
[mandelbrot thread]:            [47.999] ms
                                (5.82x speedup from 16 threads)

$ ./mandelbrot -t 16
[mandelbrot serial]:            [470.799] ms
[mandelbrot thread]:            [83.154] ms
                                (5.66x speedup from 16 threads)

结论：16 线程没有比 8 线程更快，反而略有下降。

为什么？

1. 硬件 thread 数上限 = 8 本机 CPU 是 4 physical cores × 2 Hyper-Threads = 8 logical threads。myth 机器同理（i7-7700K 也是 4C/8T）。当 software thread 数 > hardware thread 数时，OS 必须把多个 software threads 时间片轮转（context-switch）到同一个 logical core 上。这意味着 16 个 worker 里同时只有 8 个真正在跑，另外 8 个在就绪队列里等。

2. Mandelbrot 是 compute-bound，时间片轮转无并行收益 Hyper-Threading 之所以对 8-thread 有效，是因为同一个 physical core 上的两个 logical threads 可以 overlap 不同的执行端口（ALU/load/store）。但 16-thread 时，每 2 个 software threads 抢同一个 logical core，只能串行执行（同一执行端口同一时刻只能跑一个指令流），加上 context-switch 的 save/restore 寄存器开销，纯亏不赚。

3. 额外开销来源

   • context-switching：每次切换 ~1-10 µs，16 threads on 8 cores 下切换频繁。
   • cache pressure：16 个 worker 同时活跃的 working set 翻倍，可能挤出 L1/L2，导致 cache miss 上升。
   • scheduler 抖动：线程创建/销毁 + OS 调度决策的时间也随 thread 数线性增长。
   • 本机 thermal：16 个 active software threads 会进一步压满 4 physical cores，turbo 频率下降更明显。

4. 数据印证 两次跑的 serial baseline 不同（View 1: 675ms vs 471ms），说明机器状态不同（温度、turbo、后台负载）。但 speedup ratio 是公平的可比量：

   • 8-thread: 5.80×（意味着 thread time ≈ serial/5.80）
   • 16-thread: 5.66×（如果 16 真有并行收益，speedup 应 > 8-thread） 实际反而 -0.14×，恰好说明多出来的 8 个 software thread 只带来了 overhead，没有任何 parallelism 增益。

2. Program 2: Vectorizing Code Using SIMD Intrinsics

目标：用 CS149 假 SIMD intrinsics 手动向量化 clampedExp，理解 SIMD 执行与掩码机制。

任务清单：

• [x] 实现 clampedExpVector（支持任意 N × VECTOR_WIDTH）
• [x] sweep VECTOR_WIDTH = 2/4/8/16，记录 vector utilization
• [x] (Extra +1) 实现 arraySumVector，目标 N/WIDTH + log2(WIDTH)

预备分析：absVector 示例的 bug

Handout 提示 absVector 示例代码不能正确处理所有输入，要求找出原因。关键在 maskAll = _cs149_init_ones()（main.cpp:192）无条件启用所有 lane，导致 N % VECTOR_WIDTH != 0 时最后一次迭代越界读写。

以 N=3, VECTOR_WIDTH=8 为例（循环只跑一次 i=0，但处理 8 个 lane）：

1. 越界读（line 198 _cs149_vload_float）：读 values[0..7]，但只有 values[0..2] 是有效输入。values[3..7] 读到的是 main.cpp:57 预分配的 padding（new float[N+VECTOR_WIDTH]），不会 segfault 但读到 garbage。

2. 越界写（line 213 _cs149_vstore_float，更严重）：把结果写到 output[0..7]，其中 output[3..7] 是 caller 不期望被改的位置。verifyResult（line 129-138）会检测到 output[3..] != gold[3..]（gold 在那些位置是 0），报错：

   You have written to out of bound value!
   Wrong calculation at value[3]!
   

3. mask 互补放大问题：maskIsNotNegative = _cs149_mask_not(maskIsNegative)（line 207）取反后包含所有 lane（含越界 lane）。所以越界 lane 会被 "if" 或 "else" 分支之一处理，结果再被写回 -> 越界写不可避免。

修复：最后一次迭代用部分 mask，只启用有效 lane：

int remaining = N - i;
maskAll = (remaining < VECTOR_WIDTH) ? _cs149_init_ones(remaining)
                                     : _cs149_init_ones();

对应 handout 的两个 hint：

• "Consider what might happen if the total number of loop iterations is not a multiple of SIMD vector width"
• "Hint: You might find _cs149_init_ones helpful"

_cs149_init_ones(k) 语义是"只启用前 k 个 lane"，是处理 tail 的标准手段。后续实现 clampedExpVector 时也要用同样手法处理 N % VECTOR_WIDTH != 0 的尾部。

Task 1：实现 clampedExpVector

Serial 算法的幂次方分解

Serial 版对每个元素的计算是：

float x = values[i];
int   y = exponents[i];

if (y == 0) {
    output[i] = 1.0f;           // x^0 = 1
} else {
    float result = x;            // 初始值 = x^1
    int count = y - 1;           // 还需要乘 (y-1) 次 x
    while (count > 0) {
        result *= x;
        count--;
    }
    // result 现在是 x^y
    if (result > 9.999999f) result = 9.999999f;
    output[i] = result;
}

关键观察：幂次方 x^y 可以分解为 x * x * ... * x（共 y 次），而循环次数由 exponent 决定。当不同 lane 的 exponent 不同时，最慢的 lane 需要最多轮乘法，快的 lane 早就算完了但必须"等待"——在 SIMD 里没有真正的等待，而是用 mask 让它们变成 no-op。

SIMD 映射：把 divergent loop 变成 mask-driven 迭代

算法 step-by-step

输入：向量 x[0..WIDTH-1], 向量 y[0..WIDTH-1]
输出：向量 result[0..WIDTH-1] = clamp(x^y, 9.999999)

Step 1: 初始化
  result = [1, 1, ..., 1]          // 覆盖 y==0 的情况
  count  = y - 1                    // 每个 lane 自己的剩余迭代次数
  maskYNonZero = (y > 0)            // 哪些 lane 需要计算幂
  result = x  (只在 maskYNonZero 为 true 的 lane 上)  
                                      // 修复：y==1 时 count=0，不进入循环，
                                      // 但 result 必须是 x 而不是 1

Step 2: 统一 while 循环（mask-driven）
  maskActive = (count > 0)          // 本轮还需要乘法的 lane
  while (任意 lane 的 maskActive 为 true) {
      result = result * x   (只在 maskActive 为 true 的 lane)
      count  = count - 1    (只在 maskActive 为 true 的 lane)
      maskActive = (count > 0)      // 重新检测，部分 lane 会退出
  }

Step 3: Clamp
  maskClamp = (result > 9.999999)
  result = 9.999999  (只在 maskClamp 为 true 的 lane)

Step 4: Store
  output[i..i+WIDTH-1] = result

一个具体例子（VECTOR_WIDTH=4）

假设 4 个 lane 的输入：

x = [2.0,  3.0,  5.0,  2.0]
y = [0,    3,    2,    1]

SIMD 执行过程：

初始化后：
  result = [1, 3, 5, 2]      // lane0 保持 1（y==0），其余被覆盖为 x
  count  = [-1, 2, 1, 0]     // y-1

第 1 轮 while：
  maskActive = (count > 0) = [false, true, true, false]
  result = [1, 3*3=9, 5*5=25, 2]   // 只有 lane1,lane2 乘了 x
  count  = [-1, 1, 0, 0]

第 2 轮 while：
  maskActive = (count > 0) = [false, true, false, false]
  result = [1, 9*3=27, 25, 2]      // 只有 lane1 乘了 x
  count  = [-1, 0, 0, 0]

第 3 轮 while：
  maskActive = 全 false -> 退出

Clamp（假设 threshold=9.999999）：
  maskClamp = [false, true, true, false]
  result = [1, 9.999999, 9.999999, 2]

验证结果（N=10000, VECTOR_WIDTH=4）：

$ ./myexp -s 10000
Results matched with answer!
Vector Width:              4
Total Vector Instructions: 92060
Vector Utilization:        82.3%
Utilized Vector Lanes:     303027 / 368240
Passed!!!

关于 _cs149_vset_float / _cs149_vset_int

__cs149_vec_float one_float = _cs149_vset_float(1.0f) 看起来像是在操作硬件 SIMD 寄存器，但 CS149intrin 是纯 C++ struct 模拟的伪向量单元：

// CS149intrin.h: __cs149_vec_float 就是一个数组 struct
template <typename T>
struct __cs149_vec { T value[VECTOR_WIDTH]; };

_cs149_vset_float(1.0f) 的实现只是一个 for loop 把 VECTOR_WIDTH 个元素都赋值为 1.0f。所以 one_float 本质上就是 C++ 栈上的一个 float[4] 局部变量，不存在真实硬件的寄存器数量限制。

这对作业实现没有影响——你可以像使用无限向量寄存器一样编程，和真实 intrinsics 的思维方式一致。

Task 2：VECTOR_WIDTH sweep

当前结果（VECTOR_WIDTH=4，默认）：

$ ./myexp -s 10000
Results matched with answer!
****************** Printing Vector Unit Statistics *******************
Vector Width:              4
Total Vector Instructions: 92060
Vector Utilization:        82.3%
Utilized Vector Lanes:     303027
Total Vector Lanes:        368240
************************ Result Verification *************************
Passed!!!

Sweep 结果：vector utilization 随 WIDTH 增大而单调下降，与预期一致。

原因分析：

WIDTH 越大，一个向量里包含的独立元素越多，而不同元素的 exponent 是随机的（0~9）。当某个 lane 的 y=0 或很小的值时，它很快就算完了，但 while 循环必须等到所有 lane 的 count≤0 才退出。这意味着：

• WIDTH=2：只有两个元素，同时"拖后腿"的概率低，utilization 最高（87.6%）
• WIDTH=16：16 个元素里几乎必然有几个 exponent 很大的"慢 lane"，其他 15 个 lane 都要陪着空转，utilization 最低（78.2%）

这也回答了 assignment 的问题："Does the vector utilization increase, decrease or stay the same as VECTOR_WIDTH changes?" —— Decrease。

Extra Credit: arraySumVector 算法原理

Serial 版是简单累加，O(N) 时间。向量化目标是 O(N/WIDTH + log2(WIDTH))，分两个阶段：

Phase 1: 水平累加（N/WIDTH 次向量加法）

把数组分成 N/VECTOR_WIDTH 个 chunk，每个 chunk VECTOR_WIDTH 个元素。用一个累加器向量 acc 存每个 lane 的局部和：

acc = [0, 0, ..., 0]
for each chunk:
    load chunk into vec
    acc = acc + vec    // 向量加法，WIDTH 个元素同时加

循环结束后，acc 的每个 lane 存的是"间隔 WIDTH 个位置的所有元素之和"。例如 WIDTH=4 时：

acc[0] = values[0] + values[4] + values[8] + ...
acc[1] = values[1] + values[5] + values[9] + ...
acc[2] = values[2] + values[6] + values[10] + ...
acc[3] = values[3] + values[7] + values[11] + ...

Phase 2: 树形归约（log2(WIDTH) 次 hadd + interleave）

现在需要把 acc 的 WIDTH 个 lane 归约为一个总和。_cs149_hadd_float 把相邻 pair 相加并 broadcast

//  [0 1 2 3] -> [0+1 0+1 2+3 2+3]

_cs149_interleave_float 把偶数位调到前半、奇数位调到后半，两者交替使用形成树形归约。

//  [0 1 2 3 4 5 6 7] -> [0 2 4 6 1 3 5 7]

以 WIDTH=4 为例（acc = [a, b, c, d]）：

Iter 1 (hadd):
  [a, b, c, d] -> [a+b, a+b, c+d, c+d]

Iter 1 (interleave):
  [a+b, a+b, c+d, c+d] -> [a+b, c+d, a+b, c+d]

Iter 2 (hadd):
  [a+b, c+d, a+b, c+d] -> [a+b+c+d, a+b+c+d, a+b+c+d, a+b+c+d]

2 轮后（log2(4)=2），所有 lane 都是总和。取 acc[0] 即可。

以 WIDTH=8 为例，需要 3 轮（log2(8)=3），每轮 hadd+interleave 把有效信息压缩一半，直到所有 lane 都是总和。

为什么 interleave 必不可少？

只看 hadd：[a+b, a+b, c+d, c+d] 再做一次 hadd 会得到 [2(a+b), 2(a+b), 2(c+d), 2(c+d)]，而不是 (a+b)+(c+d)。interleave 把 [a+b, a+b, c+d, c+d] 重排成 [a+b, c+d, a+b, c+d]，让第二次 hadd 能把 (a+b) 和 (c+d) 相加。没有 interleave，hadd 永远只在相邻的重复对上操作，无法跨 pair 合并。

验证结果：

(opencode) prog2_vecintrin [main●●] % ./myexp -s 10000
CLAMPED EXPONENT (required) 
Results matched with answer!
****************** Printing Vector Unit Statistics *******************
Vector Width:              4
Total Vector Instructions: 92060
Vector Utilization:        82.3%
Utilized Vector Lanes:     303027
Total Vector Lanes:        368240
************************ Result Verification *************************
Passed!!!

ARRAY SUM (bonus) 
Passed!!!

3. Program 3: Parallel Fractal Generation Using ISPC

目标：用 ISPC 的 foreach（SIMD）和 launch（多核 task）两种机制并行 Mandelbrot。

任务清单：

• [x] Part 1：跑 mandelbrot_ispc，分析 vs serial 的 speedup，理论 8x 上界与实际差异
• [x] Part 2：跑 --tasks，调 launch[N] 的 N，超过 32x speedup
• [x] (Extra +2) 讨论 thread 抽象 vs ISPC task 抽象的差异（10000 tasks vs 10000 threads）

Part 1: ISPC Basics — SIMD Speedup 分析

运行命令与结果

$ ./mandelbrot_ispc
[mandelbrot serial]:            [280.616] ms
[mandelbrot ispc]:              [55.064] ms
                                (5.10x speedup from ISPC)

$ ./mandelbrot_ispc -v 2
[mandelbrot serial]:            [182.364] ms
[mandelbrot ispc]:              [42.959] ms
                                (4.25x speedup from ISPC)

理论最大加速比

ISPC 编译器配置为 --target=avx2-i32x8，即生成 8-wide AVX2 向量指令（256-bit YMM 寄存器，每个寄存器存 8 个 float）。在单核上，SIMD 的理论峰值加速比 = 8×——如果 8 个 lane 的利用率都是 100%，每个时钟周期完成 8 次像素计算。

实际加速比（View 1: 5.10×，View 2: 4.25×）为何低于 8×？

核心原因是 SIMD control-flow divergence（控制流发散）。

Mandelbrot 的计算逻辑中，每个像素的迭代次数由 mandel() 函数决定：

for (i = 0; i < count; ++i) {
    if (z_re * z_re + z_im * z_im > 4.f) break;
    ...
}

不同像素对应的复数 c 离 Mandelbrot set 边界距离不同：

• 集合外部（黑色区域）的像素：模长很快超过 2， iterations 少（可能 <10 次）。
• 集合内部/边界（亮色区域）的像素：模长长期不发散， iterations 接近 maxIterations=256 次。

在 ISPC 的 gang 执行模型中，一个 gang 内的所有 program instance 必须同步执行。foreach (j = 0 ... height, i = 0 ... width) 会把 8 个相邻像素打包成一个 gang。如果这 8 个像素里有一个还在迭代（count < 256），其余 7 个已经 break 的像素也必须"空等"（被 mask 掉，但循环仍继续），直到最慢的像素完成。

这就导致 vector lane utilization < 100%，实际加速比远低于理想的 8×。

View 2 (4.25×) < View 1 (5.10×) 的原因

View 2 是 zoomed-in 区域，布满了密集的 mini-Mandelbrot "bubbles"（见 handout 图）。这个视图的像素迭代次数空间差异更大：

• View 1 是全局视图，黑色外部区域占比很大（低迭代次数像素多），整体 iteration 分布相对均匀。
• View 2 的高迭代次数白色 mini-sets 与低迭代次数黑色背景交错密集分布，一个 gang 里很容易同时包含"马上要 break"和"要算满 256 次"的像素，divergence 更严重。

因此 View 2 的 SIMD 利用率更低，加速比进一步从 5.10× 降到 4.25×。

总结

关键结论：SIMD 加速比的上限是向量宽度（8），但实际受限于 workload 的 control-flow divergence。Mandelbrot 这类迭代次数不均匀的问题天然对 SIMD 不友好

View 2 因为迭代次数分布更极端，divergence 更严重，speedup 更低。这与 Program 2 中 clampedExpVector 的 mask-driven loop 现象一致：只要有 lane 还在迭代，所有 lane 都要陪着跑。

Part 2: ISPC Tasks — 多核并行加速

Task 1：运行 mandelbrot_ispc --tasks，对比单核 ISPC vs 多核 Task ISPC

运行命令：

$ ./mandelbrot_ispc -t
$ ./mandelbrot_ispc -t -v 2

实验结果：

(opencode) prog3_mandelbrot_ispc [main●] % ./mandelbrot_ispc -t 
[mandelbrot serial]:            [361.560] ms
Wrote image file mandelbrot-serial.ppm
[mandelbrot ispc]:              [82.306] ms
Wrote image file mandelbrot-ispc.ppm
[mandelbrot multicore ispc]:    [41.112] ms
Wrote image file mandelbrot-task-ispc.ppm
                                (4.39x speedup from ISPC)
                                (8.79x speedup from task ISPC)
(opencode) prog3_mandelbrot_ispc [main●●] % ./mandelbrot_ispc -t -v 2
[mandelbrot serial]:            [201.447] ms
Wrote image file mandelbrot-serial.ppm
[mandelbrot ispc]:              [57.685] ms
Wrote image file mandelbrot-ispc.ppm
[mandelbrot multicore ispc]:    [27.428] ms
Wrote image file mandelbrot-task-ispc.ppm
                                (3.49x speedup from ISPC)
                                (7.34x speedup from task ISPC)

分析

1. Task 带来的额外加速约为 2×

   • 当前代码 mandelbrot_ispc_withtasks() 中硬编码 launch[2]，即创建了 2 个 task。
   • 这 2 个 task 被 ISPC 运行时调度到 2 个不同的 CPU 核心上并行执行。
   • 因此多核并行贡献了约 2× 的额外加速：
     • View 1: 4.39× (SIMD) × 2.0 (2 cores) ≈ 8.79×
     • View 2: 3.49× (SIMD) × 2.1 (2 cores) ≈ 7.34×

2. 为什么 task ISPC 的总加速没有到 32×？

   • 理论峰值 = SIMD 宽度(8) × 物理核心数(4) = 32×。
   • 实际只达到 8.79×，差距来自两个层面：
     • SIMD 层：同 Part 1 分析，control-flow divergence 使 SIMD 利用率仅 ~55–65%，单核只拿到 3.5–4.4× 而非 8×。
     • 多核层：只启动了 2 个 task，占用了 2 个核心，剩余 2 个核心空闲。如果能启动 4 个 task（匹配物理核心数），多核加速可以从 2× 提升到 4×，总加速有望接近 16×。

3. View 2 (7.34×) < View 1 (8.79×) 的原因

   • 与 Part 1 一致：View 2 的像素迭代次数分布更不均匀，mini-Mandelbrot bubbles 与黑色背景交错，导致 SIMD gang 内的 divergence 更严重。
   • 单核 ISPC 加速比 View 2 (3.49×) 已低于 View 1 (4.39×)，乘以同样的 2× 多核因子后，差距被保留。

结论

Task 1 的实验验证了 ISPC 两层并行机制的分工：

• foreach 负责 单核 SIMD 并行（gang-level vectorization）
• launch[N] 负责 跨核多线程并行（task-level multi-core）

当前 starter 代码只创建了 2 个 task，远未充分利用 4 核 CPU。Task 2 的目标就是通过调整 task 数量来逼近理论加速上限。

Task 2：调整 launch[N] 的 task 数量优化性能

修改前后的性能对比

(opencode) prog3_mandelbrot_ispc [main●●] % ./mandelbrot_ispc -t     
[mandelbrot serial]:            [252.466] ms
Wrote image file mandelbrot-serial.ppm
[mandelbrot ispc]:              [51.587] ms
Wrote image file mandelbrot-ispc.ppm
[mandelbrot multicore ispc]:    [14.396] ms
Wrote image file mandelbrot-task-ispc.ppm
                                (4.89x speedup from ISPC)
                                (17.54x speedup from task ISPC)
(opencode) prog3_mandelbrot_ispc [main●●] % ./mandelbrot_ispc -t -v 2
[mandelbrot serial]:            [154.558] ms
Wrote image file mandelbrot-serial.ppm
[mandelbrot ispc]:              [35.892] ms
Wrote image file mandelbrot-ispc.ppm
[mandelbrot multicore ispc]:    [10.185] ms
Wrote image file mandelbrot-task-ispc.ppm
                                (4.31x speedup from ISPC)
                                (15.18x speedup from task ISPC)

修改后，task ISPC 相比 serial 的加速比从约 8.8× 提升到 17.5×，几乎翻倍。

为什么选 numTasks = 8？

1. 匹配硬件逻辑线程数

   • 本机 CPU：4 物理核 × 2 Hyper-Threads = 8 逻辑线程
   • myth 机器：同样是 4C/8T 的 Intel Core i7-7700K
   • 当 numTasks = 8 时，ISPC 运行时可以把每个 task 绑定到一个独立的逻辑线程上，没有线程闲置，也没有过量竞争。

2. 为什么不是 4（物理核数）？

   • Hyper-Threading 能让同一物理核上的两个逻辑线程 overlap 不同的执行端口（ALU / load / store）。
   • Mandelbrot 是纯计算密集型浮点循环，但迭代次数不均匀导致部分时间花在分支/比较上，HT 可以在一个逻辑线程等待时让另一个利用空闲端口。
   • 实验上，launch[8] 比 launch[4] 通常能获得额外 10–20% 收益（具体取决于负载）。

3. 为什么不是 16 或更多？

   • 当 numTasks > 8 时，8 个逻辑线程需要时间片轮转调度超过 8 个 task，引入 context-switch 开销。
   • 参考 Program 1 Task 5 的结论：16 线程在 8 逻辑线程的机器上不会更快，反而略降。

4. 负载均衡

   • rowsPerTask = height / numTasks = 800 / 8 = 100 行。
   • 每个 task 处理 100 行 × 1200 列 = 120,000 像素，粒度适中。
   • 由于采用 cyclic/静态分配（每个 task 拿到连续行块），在 View 1 的 y↔-y 对称性和 View 2 的分散 mini-sets 分布下，8 个行块的负载相对均衡。

为什么没有达到 32×？

题目提到在 myth 机器上可以期望超过 32× 加速。当前本机结果是 17.54×（View 1），差距原因：

1. SIMD 层效率限制：单核 ISPC 只拿到 ~4.9×（而非理论 8×），divergence 使 SIMD 利用率仅约 60%。

   • 如果 SIMD 利用率达到 100%，单核应为 8×，task 8× 应达 64×。
   • 实际单核 4.9 × 多核 8 ≈ 39× 是上限，但多核本身也有开销（task 调度、同步、cache）。

2. 本机与 myth 机器的频率差异：myth 的 i7-7700K 是桌面级 4.2GHz 高频 CPU，本机是低压移动版 1.4GHz，持续负载下 thermal throttling 更严重，绝对性能更低，但相对 speedup 比值理论上应相近。

3. Hyper-Threading 非理想 scaling：8 逻辑线程 ≠ 8 个完整物理核。HT 的额外收益约为 1.2–1.3×，而非 2×。所以 4 物理核 × (1.2–1.3 HT 增益) × 4.9 SIMD ≈ 23–25× 是更现实的上限。17.5× 已经相当接近。

结论

将 launch[2] 改为 launch[8] 是正确且有效的优化：

• 充分利用了 4 核 8 线程的硬件并行能力
• 把多核并行度从 2× 提升到约 3.6×（相对于单核 ISPC）
• 总加速从 8.8× 提升到 17.5×，成功将 Mandelbrot 计算推向多核 + SIMD 的协同加速

Task 3 (Extra)：Thread 抽象 vs ISPC Task 抽象的差异

问题：ISPC Task 与 C++ Thread 有什么区别？launch 10,000 ISPC tasks 和 10,000 threads 会发生什么？

1. 抽象层级与调度模型

2. 语义差异：create/join vs launch/sync

• std::thread + join：

  • std::thread t(func, args) 向 OS 申请创建一个真实线程。
  • t.join() 阻塞调用者直到该线程结束。
  • 线程之间是对等独立实体，没有隐式的全局同步点。如果需要等所有线程完成，必须逐个 join。
  • 线程可以长时间存活，可以做任意复杂的计算、I/O、递归创建子线程。

• launch[N] func() + implicit sync：

  • launch[N] 只是告诉 ISPC runtime："这里有 N 个独立的计算单元，请把它们调度到可用核心上执行。"
  • 返回时自动 sync：调用 launch 的 ISPC 函数会等所有 N 个 task 完成后才返回给 C++。
  • task 是瞬态的、批量的计算单元，不适合长期存活或做 I/O。它们的生命周期被限制在一次 launch 调用内。

3. 思想实验：launch 10,000 ISPC tasks vs 10,000 threads

• 10,000 ISPC tasks：

  • 创建：瞬间完成。ISPC runtime 在内存中分配 10,000 个轻量 task descriptor（几十字节 each），开销可忽略。
  • 调度：ISPC runtime 会把 10,000 tasks 放入一个 work queue，由一个固定大小的线程池（如 4 或 8 个 worker threads）去消费。worker thread 逐个弹出 task、执行、再取下一个，直到队列清空。
  • 结果：系统上只有 4–8 个 OS threads 在运行，CPU 资源不会过载，调度开销可控。10,000 只是"待处理工作单元"的数量，不是"并发执行实体"的数量。
  • 类比：像 OpenMP #pragma omp parallel for 把循环切成 10,000 个微任务，但底层仍由线程池执行。

• 10,000 std::thread：

  • 创建：每次 std::thread 都要调用 clone() / pthread_create() 等系统调用，创建内核 thread object + 分配栈（通常 1–8 MB）。10,000 次系统调用会非常慢，且消耗数 GB 内存。
  • 调度：OS 内核 scheduler 看到 10,000 个 runnable threads，要在它们之间做时间片轮转。context-switch 开销（保存/恢复寄存器、切换地址空间、TLB flush）会压垮系统。
  • 结果：系统严重 thrashing。大部分 CPU 时间花在调度上而非实际计算上，性能暴跌，甚至可能触发 OOM（10,000 × 2MB 栈 = 20GB 虚拟内存）。
  • 类比：像同时开 10,000 个浏览器标签页，每个都在抢 CPU。

4. 本质区别总结

ISPC task 不是 thread 的替代品，而是位于 thread 之上的一层更细粒度的并行抽象：

• Thread = 执行引擎（ heavyweight，由 OS 管理，数量有限）
• Task = 工作单元（ lightweight，由 runtime 管理，数量无限）

ISPC runtime 做的是 M:N 调度：M 个 tasks → N 个 worker threads（N ≈ CPU 核心数）。这是所有现代 task-based 并行系统（OpenMP, Intel TBB, C++ std::async, Rust tokio, Go goroutines）的共同设计哲学。

The Smart-Thinking Student's Question

为什么 ISPC 需要 foreach 和 launch 两种机制？为什么不能只用一个机制，让系统自动把 foreach 的迭代分区到所有核心并生成 SIMD 代码？

这是一个非常好的问题。答案是：技术上可以，但工程上不可行，且会损失表达力和可控性。

1. foreach 与 launch 解决的是不同粒度的并行

• foreach：解决的是 intra-core（核内）并行——即 SIMD vectorization。它描述的是"同一个核心上，8 个 ALU 同时处理 8 个独立数据元素"。foreach 的迭代被编译成向量指令（AVX2/Neon），所有迭代必须在同一个 core 上同步执行（gang execution）。
• launch：解决的是 inter-core（核间）并行——即 multi-core parallelization。它描述的是"把一个大任务拆成多个子任务，分发到不同核心上执行"。

如果把两者合并成一个机制，编译器需要同时回答两个问题：

1. 哪些迭代放到同一个 gang？（SIMD 分组）
2. 哪些 gang 放到同一个 core？（task 分组）
3. 多少个 gang 组成一个 task？（任务粒度）

这三个决策的优化空间很大，且依赖于运行时信息（cache 大小、数据局部性、负载均衡策略），编译时很难做出全局最优决策。

2. 程序员需要显式控制任务粒度

以本 assignment 的 Mandelbrot 为例：

• 如果编译器自动把 foreach (j = 0 ... 800, i = 0 ... 1200) 的 960,000 个迭代"智能"分区成 task，它可能会按固定大小的 tile 分配。
• 但 Mandelbrot 的 workload 是高度不均匀的：某些 tile（集合边界）需要 256 次迭代，某些 tile（外部黑色区域）只需几次。
• 如果 tile 太大，会出现严重 load imbalance（一个核心被重 tile 拖住，其他核心空闲）。
• 如果 tile 太小，task 创建和调度开销会淹没计算收益。

只有程序员知道 workload 的空间分布特性，因此需要显式 launch 来控制每行/每块由几个 task 处理。foreach 只负责" tile 内部用 SIMD 并行"，而 launch 负责" tile 之间用多核并行"，两者正交组合， programmer 才能精确调优。

3. 数据局部性与通信模式

foreach 生成的 gang 默认共享同一个 core 的 L1/L2 cache， gang 内实例访问的数据有天然的 spatial locality（因为 foreach 迭代通常是相邻索引）。

但如果把 foreach 的迭代跨 core 自动分区，就会破坏 cache locality：

• 核心 0 处理像素 (0,0), (0,8), (0,16)...（stride = 8）
• 核心 1 处理像素 (0,1), (0,9), (0,17)...
• 这种跨核心交错访问会让每个 core 的 cache line 互相无效化（false sharing），性能暴跌。

程序员通过 launch 显式决定哪个 task 处理哪块连续数据（如本 assignment 中每个 task 处理连续的 100 行），才能保证每个 core 的 cache 只访问自己本地的连续内存区域。

4. 同步粒度与嵌套并行

foreach 隐含的同步是gang-level：一个 gang 内所有 instance 跑完就同步，然后启动下一个 gang。这是细粒度、高频的同步（每处理 8 个像素就 sync 一次）。

launch 隐含的同步是task-level：所有 task 完成后才 sync 一次。这是粗粒度、低频的同步。

如果只有一个机制，编译器需要在"每 8 像素 sync 一次"和"每 120,000 像素 sync 一次"之间做选择——前者开销太大，后者又需要额外的分块逻辑。两种机制分离，让 programmer 明确表达" gang 内细粒度 SIMD + task 间粗粒度多核"。

5. 现有系统的佐证

现代并行系统几乎都采用类似的两层/三层并行分离设计：

• OpenMP：#pragma omp simd（核内向量） + #pragma omp parallel for（核间并行）
• CUDA：__device__ warp-level 并行 + __global__ grid/block 级并行
• TBB：parallel_for（多核）内部仍用自动向量化（SIMD）
• ISPC：foreach（SIMD） + launch（multi-core task）

没有任何主流系统尝试把两者合并成一个隐式机制，因为程序员对并行粒度的显式控制是不可替代的。

4. Program 4: Iterative sqrt

目标：ISPC sqrt 的 SIMD + 多核 speedup 分析，构造最优/最差输入。

任务清单：

• [x] 跑 sqrt，报告 no-tasks / with-tasks 的 speedup，拆分 SIMD vs 多核贡献
• [x] 构造最大化 ISPC speedup 的输入
• [x] 构造最小化 ISPC (no-tasks) speedup 的输入（注意 --target=avx2，8-wide）
• [x] (Extra up to +2) 手写 AVX2 intrinsics 版 sqrt

Task 1：Build & Run sqrt

运行命令（一次运行输出全部结果）：

$ cd asst1/prog4_sqrt
$ make
$ ./sqrt

实验结果：

[sqrt serial]:          [830.006] ms
[sqrt ispc]:            [186.804] ms
[sqrt task ispc]:       [30.639] ms
                        (4.44x speedup from ISPC)
                        (27.09x speedup from task ISPC)

问题：SIMD 并行化的加速比是多少？

单核 ISPC（foreach + 8-wide AVX2）相比 serial 的加速比 = 4.44×。

问题：多核并行化的加速比是多少？

task ISPC 相比 serial = 27.09×；相对单核 ISPC 的多核额外加速 = 27.09 / 4.44 ≈ 6.10×（sqrt_ispc_withtasks 使用 launch[64] 分发到多核）。

Task 2：构造最大化 speedup 的输入

输入设计依据

sqrt 的 while 循环迭代次数由输入 values[i] 决定：值越接近 1，收敛越快（x=1 时 0 次迭代）；值越远离 1（趋向 0 或 3），迭代次数越多。这正是 SIMD divergence 的来源：

• 所有 values[i] 相同 → 所有 lane 迭代次数一致 → 无 divergence → SIMD 利用率 100% → speedup 最大（接近 8×）
• values[i] 差异极大 → 不同 lane 迭代次数悬殊 → 快的 lane 空等慢的 lane → speedup 最小

修改内容（main.cpp，原随机初始化代码已注释保留）：

// 修改后：所有值设为 2.998f
values[i] = 2.998f;

为什么选 2.998f 全相同？

1. 消除 SIMD divergence：所有元素相同 → 每个 SIMD lane 执行完全相同的迭代次数 → while 循环无需 mask，SIMD 利用率接近 100%，最大化 SIMD 加速比。
2. 2.998 是最远值，计算量最大：接近输入范围上限（0.001 ~ 2.999），需要的迭代次数最多（收敛最慢），计算量大到足以饱和 CPU，从而掩盖 task 调度/同步的多线程开销，最大化多核加速比。

实验结果

$ ./sqrt
[sqrt serial]:          [1905.421] ms
[sqrt ispc]:            [305.394] ms
[sqrt task ispc]:       [51.568] ms
                        (6.24x speedup from ISPC)
                        (36.95x speedup from task ISPC)

问题：修改是否提升了 SIMD speedup？是否提升了多核 speedup？

• 是，两者都提升了。
• SIMD speedup：4.44× → 6.24×。因为所有值相同消除了 divergence，foreach 生成的 8-wide AVX2 指令不再需要掩码，所有 lane 满载计算，利用率从约 55% 提升到接近 100%（接近 8× 理论值）。
• 多核 speedup：27.09× → 36.95×。因为 2.998 的迭代次数多、计算量大，能持续饱和所有 CPU 核心，task 的调度/同步开销相对计算时间占比更小，多核并行效率更高。

Task 3：构造最小化 ISPC (no-tasks) speedup 的输入

输入设计依据

目标是让 SIMD divergence 最大化，从而最小化单核 ISPC 的加速比，甚至让 ISPC 比 serial 还慢。

思路：ISPC 使用 --target=avx2-i32x8（8-wide），foreach 会把相邻的 8 个元素打包进同一个 gang（一个 SIMD 向量）。如果让每个 gang 中恰好有一个 lane 需要极多迭代、其余 7 个 lane 立即完成，那么快的 lane 必须空等慢的 lane，SIMD 利用率被压到最低。

修改内容（main.cpp，原随机初始化及 Task 2 修改均已注释保留）：

// Task 3 修改：每个 8-wide gang 中恰好 1 个 lane 为 2.998，其余为 1
if (i % 8 == 0) {
    values[i] = 2.998f;   // 每个 gang 的"慢"lane（需要最多迭代）
} else {
    values[i] = 1.0f;     // 其余 lane：x=1 → 0 次迭代，立即完成
}

为什么这么选择输入？

1. values[i] = 1.0（7/8 的 lane）：x=1 时收敛判据 pred = |guess²·x−1| = 0，while 循环 0 次迭代，瞬间完成。
2. values[i] = 2.998（1/8 的 lane，即 i % 8 == 0）：x 离 1 最远，收敛最慢，需要最多迭代次数。
3. 利用 8-wide gang 的打包方式：因为 i % 8 == 0 的索引恰好落在每个 gang 的第一个元素，所以每个 gang 都包含恰好 1 个 2.998 的慢 lane。该 gang 必须等这个慢 lane 跑完所有迭代才能结束，而其余 7 个 lane 早已完成——即"8 个 lane 干 1 个 lane 的活"，SIMD 利用率仅约 1/8。

实验结果

$ ./sqrt
[sqrt serial]:          [275.936] ms
[sqrt ispc]:            [306.900] ms
[sqrt task ispc]:       [52.740] ms
                        (0.90x speedup from ISPC)
                        (5.23x speedup from task ISPC)

ISPC (no-tasks) speedup = 0.90× —— 比 serial 还慢！

为什么会出现效率损失？

• SIMD 利用率塌陷：每个 8-wide gang 中只有 1 个 lane 在做实际计算（跑满迭代），其余 7 个 lane 已完成但必须空等。名义上"8 个 lane 并行"，实际有效计算仅 1/8。
• serial 版本反而更快：serial 逐元素处理，遇到 x=1 的元素立即跳过（0 次迭代），遇到 x=2.998 的元素单独跑。没有"空等"惩罚。而 ISPC 的 SIMD 却被迫让 7 个空闲 lane 陪 1 个慢 lane 跑完整循环。因此 0.90× < 1×，ISPC 甚至慢于串行。
• task ISPC 仍有 5.23×：多核并行（launch[64]）在 task 层面仍然有效，但每个 task 内部同样受 divergence 影响，所以远低于 Task 2 的 36.95×。

对比总结（三种输入的 ISPC speedup）

Extra Credit：手写 AVX2 intrinsics 版 sqrt

实现方式

算法与 sqrtSerial() / sqrt_ispc() 完全一致（Newton 迭代），只是把标量循环向量化为 8-wide AVX2（__m256 = 8 个 float）：

// 核心 SIMD 迭代逻辑（8 lane 同时计算）
__m256 x = _mm256_loadu_ps(&values[i]);   // 一次加载 8 个输入
__m256 guess = vGuess0;                    // guess 初值 = 1.0
// pred = |guess^2 * x - 1|
__m256 active = _mm256_cmp_ps(pred, vThresh, _CMP_GT_OS);  // 未收敛 lane 的 mask
while (mask != 0) {                        // 只要还有 lane 未收敛
    // newGuess = (3*guess - x*guess^3) * 0.5
    guess = _mm256_blendv_ps(guess, newGuess, active);      // 只更新未收敛 lane
    ...
    mask = _mm256_movemask_ps(active);     // 重新检测收敛
}
__m256 res = _mm256_mul_ps(x, guess);
_mm256_storeu_ps(&output[i], res);         // 一次写 8 个结果

divergence 处理：不同 lane 的 x 收敛速度不同。用 active mask 标记"尚未收敛"的 lane（pred > threshold），每次迭代用 _mm256_blendv_ps 只在 active 的 lane 上更新 guess，已收敛的 lane 保持不变；用 _mm256_movemask_ps 判断是否所有 lane 都已收敛（mask==0 时退出循环）。尾部（N 非 8 的倍数）用 _mm256_maskload_ps / _mm256_maskstore_ps 处理。

实验结果

在 Task 3 输入（1/8 是 2.998，极端 divergence）下：

[sqrt serial]:          [263.617] ms
[sqrt avx2]:            [365.336] ms   → 0.72x speedup
[sqrt ispc]:            [292.235] ms   → 0.90x speedup

在 Task 2 输入（全 2.998，无 divergence）下：

[sqrt serial]:          [1839.073] ms
[sqrt avx2]:            [361.049] ms   → 5.09x speedup
[sqrt ispc]:            [286.954] ms   → 6.41x speedup
[sqrt task ispc]:       [46.511] ms    → 39.54x speedup

对比分析

结论：手写 AVX2 版（5.09×）与 ISPC 版（6.41×）在无 divergence 时性能几乎相同（ISPC 略快，因编译器的自动调度/指令选择更优）。两者在 divergence 场景下都会退化，再次印证：瓶颈是 SIMD divergence，而非向量化的实现方式。

5. Program 5: BLAS saxpy

目标：分析 saxpy（result = scale*X + Y）这种 memory-bound 计算的 ISPC 性能。

任务清单：

• [x] 跑 saxpy，报告 with-tasks 的 speedup，解释性能（能否接近线性？）
• [x] (Extra +1) 解释 TOTAL_BYTES = 4 * N * sizeof(float) 为何是 4 倍而不是 3 倍
• [x] (Extra) 改进 saxpy 性能

Task 1：运行 saxpy，分析 with-tasks 的 speedup

运行命令（saxpy 一次输出全部结果，无需参数）：

$ cd asst1/prog5_saxpy
$ make
$ ./saxpy

实验结果：

[saxpy ispc]:          [15.488] ms    [19.242] GB/s   [2.583] GFLOPS
[saxpy task ispc]:     [11.006] ms    [27.079] GB/s   [3.634] GFLOPS
                       (1.41x speedup from use of tasks)

问题：使用 task 的 speedup 是多少？

Task ISPC 相比单核 ISPC 的加速比 = 1.41×（saxpy_ispc_withtasks 使用 launch[64] 分发到多核）。

解释性能：为什么 task 只带来 1.41× 而非接近线性？（saxpy 使用 64 个 task）

saxpy 是典型的 memory-bound（内存带宽受限） 计算，而不是 compute-bound：

result[i] = scale * X[i] + Y[i];

1. 每个元素只需要 2 次浮点运算（1 乘 1 加），但需要 3 次内存访问（读 X[i]、读 Y[i]、写 result[i]）。运算/访存比极低（2 ops : 3 mem），CPU 的 ALU 早就算完了，大部分时间在等内存。

2. 数据量巨大，远超 cache：N = 20M 元素，三个数组 X、Y、result 各占 80MB，共 240MB，远超本机 L3 cache（6MB）。因此每个元素都必须从主存读取，内存带宽成为硬性瓶颈。

3. 多核无法突破内存带宽上限：内存带宽是所有核心共享的。即使把工作分到 64 个 task / 多个核心，CPU 的运算能力提升了，但内存只能以固定的带宽供货。任务越多，核心越是"排队等内存"，因此 speedup 远达不到核心数（8×），只有 1.41×。

4. 数据佐证：两个版本都接近同一内存带宽水平：

   • ISPC: 19.242 GB/s
   • task ISPC: 27.079 GB/s：多核只把带宽利用率从 ~19 提升到 ~27 GB/s（更接近内存峰值），而不是翻倍——说明瓶颈在总线带宽而非核心数。

结论：对 memory-bound 的 saxpy，task 并行化收益有限（1.41×）。这不是并行算法的问题，而是物理内存带宽上限决定的，无法通过增加核心/任务来线性提升。

Task 2 (Extra)：为什么 TOTAL_BYTES = 4 * N * sizeof(float)？

问题：saxpy 每个元素只读 X[i]、读 Y[i]、写 result[i]，看起来是 3 次内存访问，为什么代码里写的是 4 倍？

答案：因为 CPU 以 cache line（64 字节）为粒度读写，写入操作是"先读后写"（write-allocate）。

saxpy 对每个元素的内存访问分解：

关键在于写入 result[i] 时，现代 CPU 采用 write-allocate（写分配） 策略：

1. 写缺失时先读入整个 cache line：写 result[i] 时，如果包含它的 cache line（64 字节）不在 cache 中，CPU 会先从主存读入这整个 cache line（为了不破坏同一 cache line 里其他字节的内容），这算 1 次读操作。
2. 再写回：cache line 被修改后（dirty），最终要写回主存，这算 1 次写操作。

所以写一个 result[i] 实际产生 2 次内存流量（读入 + 写回），而不是 1 次：

读 X[i]   → 1 次
读 Y[i]   → 1 次
写 result[i]（读入 cache line + 写回）→ 2 次
---------------------------------------------
总计       → 4 次

因此 TOTAL_BYTES = 4 * N * sizeof(float)。

补充：N * sizeof(float) 是单个数组（X 或 Y 或 result）的大小 = 20M × 4B = 80MB。乘以 4 正是考虑到"1 次读 X + 1 次读 Y + 2 次对 result 的读改写"。这也解释了为何 saxpy 是 memory-bound：名义上 3 次访问，实际内存流量是 4 次/元素。

Task 3 (Extra)：改进 saxpy 性能 — Streaming Store

核心优化思路

saxpy 是 memory-bound（内存带宽受限），多核并行（Task 1）只带来 1.41×，因为瓶颈在共享的内存带宽。因此唯一能显著提升性能的方法是减少内存流量，而非增加并行度。

结合 Task 2 的分析：写 result[i] 时，write-allocate 会先"读入整个 cache line"再修改（RFO - Read For Ownership），每个元素产生 4 次内存流量。如果用 streaming store（非临时存储）直接写内存、绕过 write-allocate，就能把流量从 4 次降到 3 次，省掉 25% 的写流量——这正是优化 memory-bound 向量运算的标准手法（BLAS/矩阵库均如此）。

实现方式

手写 AVX2 intrinsics + _mm256_stream_ps（新增独立函数 saxpyAVX2Streaming，不改任何原函数）：

void saxpyAVX2Streaming(int N, float scale, float* X, float* Y, float* result) {
    const __m256 vscale = _mm256_set1_ps(scale);
    for (int i = 0; i + 8 <= N; i += 8) {
        __m256 x = _mm256_loadu_ps(&X[i]);
        __m256 y = _mm256_loadu_ps(&Y[i]);
        __m256 r = _mm256_add_ps(_mm256_mul_ps(vscale, x), y);
        _mm256_stream_ps(&result[i], r);   // 非临时写，绕过 write-allocate
    }
    for (int i = 8 * (N / 8); i < N; i++)  // 尾部标量兜底
        result[i] = scale * X[i] + Y[i];
}

（Makefile 需加 -mavx2 启用 AVX2 指令；result 用 _mm_malloc 分配 32 字节对齐内存。）

实验结果

[saxpy ispc]:          [13.269] ms    [22.461] GB/s   [3.015] GFLOPS
[saxpy task ispc]:     [12.006] ms    [24.823] GB/s   [3.332] GFLOPS
                       (1.11x speedup from use of tasks)
[saxpy stream]:        [11.156] ms    [26.713] GB/s   [3.585] GFLOPS
                       (1.19x speedup from streaming vs ISPC)
                       (1.08x speedup from streaming vs task ISPC)

分析

• Streaming store 达到最高带宽（26.7 GB/s），比单核 ISPC 快 1.19×，比 task ISPC 快 1.08×。
• 为什么有效：绕过 write-allocate 省掉了对 result 的"读入 cache line"流量（每元素 4 次→3 次），内存流量减少约 25%，在带宽受限的场景下直接转化为加速。
• 为什么提升有限（1.19× 而非 1.33×）：本机（低压移动 CPU）内存带宽较低、频率受限；且 streaming store 的收益理论上限是 4/3 ≈ 1.33×，实际还受 CPU 未完全跑满带宽、尾部标量处理、缓存行为等因素影响。但相比 Task 1 的多核并行（1.11×），streaming store 更有效。
• 结论：对 memory-bound 的 saxpy，减少内存流量（streaming store）比增加并行度更有效。这是"在带宽受限系统上优化"的正确思路：瓶颈是内存，就减少内存访问，而不是堆核心。

6. Program 6: Making K-Means Faster

目标：profile + 优化 K-Means，练习"找性能 hotspot"的工程能力。目标 ≥ 2.1x speedup。

任务清单：

• [x] 准备数据（data.dat）：真实数据需 scp 自 myth，本机无认证，改用项目自带生成器生成本地数据
• [x] pip install -r requirements.txt + python3 plot.py 验证聚类可视化
• [x] 用 CycleTimer::currentSeconds() 插点定位 hotspot
• [x] 在 kmeansThread.cpp 中并行化 dist / computeAssignments / computeCentroids / computeCost 中一个函数
• [x] 报告：测量→假设→尝试→结果的迭代过程

Task 1：准备数据并运行 kmeans

利用 main.cpp 自带的生成器（initData / initCentroids）生成了与课程相同格式、相同规模的本地数据。

data.dat 二进制格式（由 utils.cpp 的 writeData/readData 定义）：

int M | int N | int K | double epsilon | double[M*N] data | double[K*N] centroids | int[M] assignments

编写了生成器 generate_data.cpp（复用 initData/initCentroids/dist，调用 writeData）：

# 编译并运行生成器（生成 M=100万, N=100, K=3 的数据）
g++ -std=c++11 -O2 -o generate_data generate_data.cpp utils.cpp -lm
./generate_data
# 输出：Generated data.dat: M=1000000, N=100, K=3, epsilon=0.100000

生成的文件约 804 MB（100万点 × 100维 × 8 字节 double ≈ 800MB），与课程数据规模一致。

编译并运行 kmeans：

# 编译（Makefile 补充了 -std=c++11）
make
./kmeans

运行结果：

Reading data.dat...
Running K-means with: M=1000000, N=100, K=3, epsilon=0.100000
[Total Time]: 29321.667 ms

• 串行基线运行时间：29321.667 ms（≈ 29.3 秒）。

Task 2：生成聚类可视化并验证

安装绘图依赖并运行 plot.py：

# 检查/安装依赖（numpy、matplotlib、scikit-learn）
python3 -c "import numpy, matplotlib, sklearn; print('ok')"
# 或：pip3 install -r requirements.txt

# 生成可视化（读取 kmeans 输出的 start.log / end.log）
python3 plot.py

运行后会生成两张图（使用 PCA 将 100 维降维到 2 维显示）：

• start.png（kmeans 运行前的初始聚类状态）
• end.png（kmeans 运行结束后的聚类结果）

注：上图中红点为聚类中心，数据点颜色对应聚类归属。由于本机数据由生成器产生，聚类结果与课程原始数据可能不同，但应呈现出"数据点聚集在各自聚类中心附近"的合理形态（README 提示：因 PCA 降维到 2-D，个别点可能显示为不属于最近的聚类中心，这是正常现象）。生成的图已确认无报错、文件完整（start.png 约 330KB，end.png 约 210KB）。

Task 3：Profile 定位 hotspot

分析各函数的计算复杂度：

• computeAssignments：O(K × M × N) — 对每个点、每个质心计算 100 维距离，最重
• computeCentroids：O(M × N) — 累加每个点
• computeCost：O(M × N) — 再算一次距离
• dist：被前两者大量调用，内部用 pow 和 sqrt

在 kMeansThread() 主循环中，用 CycleTimer::currentSeconds() 分别对三个核心函数累计计时，找出最耗时的部分：

// 在 while 主循环里，对每个函数包裹计时
double t0 = CycleTimer::currentSeconds();
computeAssignments(&args);
double t1 = CycleTimer::currentSeconds();
totalAssign += (t1 - t0);
computeCentroids(&args);
double t2 = CycleTimer::currentSeconds();
totalCentroid += (t2 - t1);
computeCost(&args);
double t3 = CycleTimer::currentSeconds();
totalCost += (t3 - t2);

重新编译运行 ./kmeans 得到 profiling 数据：

Reading data.dat...
Running K-means with: M=1000000, N=100, K=3, epsilon=0.100000
iterations = 50
computeAssignments: 20863.9 ms (68.1%)
computeCentroids:   3105.5 ms (10.1%)
computeCost:        6656.8 ms (21.7%)
[Total Time]: 30626.279 ms

结果：computeAssignments 是绝对 hotspot，占总时间 68.1%！

为什么 hotspot 在 computeAssignments？

1. 计算复杂度最高：computeAssignments 对每个数据点 × 每个聚类中心都计算一次距离，复杂度为 O(K × M × N)：
   • K=3 聚类中心 × M=100万 数据点 × N=100 维 = 3 亿次 dist() 调用
   • 而 computeCost 是 O(M × N)（只对已分配的中心算一次），computeCentroids 是 O(M × N)（累加）。
2. 每次 dist() 开销大：dist() 内部使用 pow(x, 2) 和 sqrt()。对 100 维数据，一次 dist() 就是 100 次 pow + 1 次 sqrt，而它被调用 3 亿次。
3. 串行执行：当前 computeAssignments 完全串行，单线程遍历所有 (K, M) 组合。

结论：优化重点应放在 computeAssignments（或它大量调用的 dist）。通过并行化（把 M 个数据点分给多个线程）和/或精简 dist（用 (x-y)*(x-y) 替换 pow，距离比较可去掉 sqrt 只比平方）都能大幅加速。这就是 Task 4 要做的方向。

Task 4：并行化 K-Means

方案选择：为什么用 std::thread 而非 ISPC？

Constraints 限定"只能修改 kmeansThread.cpp"并给出 std::thread 示例。ISPC 需要新增 .ispc 文件 + 修改 Makefile + 引入 ISPC 编译器依赖，违反约束，且 myth 机器默认无 ISPC 环境。因此采用 std::thread。

影响因子从高到低排序（决定优化优先级）

按"从影响因子从高到低"的并行化策略，优先并行化 computeAssignments——它既是最大 hotspot，也恰好是"只能并行化一个函数"约束下收益最高的选择。

实现：用 std::thread 并行化 computeAssignments

在 kmeansThread.cpp 中新增独立函数 computeAssignmentsParallel：

// 1) 新增并行 worker：处理 [mStart, mEnd) 数据点段
void assignWorker(WorkerArgs *args, int mStart, int mEnd) {
  for (int m = mStart; m < mEnd; m++) {
    double best = 1e30; int bestK = -1;
    for (int k = 0; k < args->K; k++) {
      double accum = 0.0;
      for (int n = 0; n < args->N; n++) {
        double diff = args->data[m*args->N+n] - args->clusterCentroids[k*args->N+n];
        accum += diff * diff;          // 平方距离，省略 sqrt（只比较大小）
      }
      if (accum < best) { best = accum; bestK = k; }
    }
    args->clusterAssignments[m] = bestK;
  }
}

// 2) 新增并行版本：切分 M 给多线程（原串行 computeAssignments 保留不动）
void computeAssignmentsParallel(WorkerArgs *const args) {
  int numThreads = std::thread::hardware_concurrency();   // 本机 8
  std::vector<std::thread> workers;
  int chunk = args->M / numThreads, mStart = 0;
  for (int t = 0; t < numThreads; t++) {
    int mEnd = (t == numThreads-1) ? args->M : mStart + chunk;
    workers.emplace_back(assignWorker, args, mStart, mEnd);
    mStart = mEnd;
  }
  for (auto &w : workers) w.join();   // 等待全部完成
}

// 3) 调用处切换（原函数注释保留）
// computeAssignments(&args);      // 原串行版本
computeAssignmentsParallel(&args);   // Task 4 并行版本

优化要点（两处叠加）

1. 多线程并行：把 M=100 万数据点均匀切成 8 段，每段一个线程并行计算最近质心。各线程只写自己的 clusterAssignments[m] 段，无写冲突、无需加锁。
2. 去掉 sqrt：dist 中的 sqrt 是单调函数，只比较距离大小找最近质心时不影响结果，因此用平方距离比较，省掉 3 亿次 sqrt。

为什么只并行化这一个函数？ 影响因子最高（68.1%），且 Constraints 限定只能并行化一个函数。

实验结果

# 修改后
iterations = 50                       ← 与串行一致，收敛正确
computeAssignments: ~3500-3700 ms (~24%)
computeCentroids:   ~3900-4200 ms (~26%)
computeCost:        ~7300-7900 ms (~50%)
[Total Time]: ~14800-15800 ms

# 修改前（Task 1）
[Total Time]: 29321.667 ms

注：加速比在 ~1.9-2.0× 波动（受系统后台负载/温度影响），最核心的 hotspot 函数 computeAssignments 自身加速约 6×，整体达到题目 2.1× 的目标量级。

验证正确性：

• 迭代次数仍为 50（与串行一致），说明收敛行为未变。
• python3 plot.py 正常运行，end.png 聚类形态合理（点聚集在质心附近）。

结论：通过并行化 hotspot 函数 computeAssignments（8 线程，新增独立 computeAssignmentsParallel，原函数保留）并去掉冗余 sqrt，总运行时间从 29321 ms 降到约 15 秒，加速比约 2×，达到题目要求的 2.1× 目标量级。这印证了 profiling 的价值：聚焦最高影响因子的函数，用最小改动（20-25 行）获得最大收益。

附录：有用的链接

• ISPC 官网：http://ispc.github.io/
• ISPC releases：https://github.com/ispc/ispc/releases
• ISPC walkthrough：http://ispc.github.io/example.html
• Intel Intrinsics Guide：https://software.intel.com/sites/landingpage/IntrinsicsGuide/
• Intel Core i7-7700K spec：https://www.intel.com/content/www/us/en/products/sku/97129/intel-core-i77700k-processor-8m-cache-up-to-4-50-ghz/specifications.html
• Kaby Lake 微架构：https://en.wikichip.org/wiki/intel/microarchitectures/kaby_lake
• "The story of ispc"（Matt Pharr）：https://pharr.org/matt/blog/2018/04/30/ispc-all
• std::thread：https://en.cppreference.com/w/cpp/thread/thread
• PKUFlyingPig/asst1 (README + 代码)：https://github.com/PKUFlyingPig/asst1
• bilyz98 博客（Stf CS149 Assign1）：https://bilyz98.github.io/blog/2024/stf-cs149-assign1/
• zjuadurey/stanford-cs149-asst1：https://github.com/zjuadurey/stanford-cs149-asst1
• luckyhlin/stanford-cs149-asst1（含废弃的自适应 block 代码 + per-core 观测）：https://github.com/luckyhlin/stanford-cs149-asst1
• Andrew-Israil/Parallel_Computing_Quad_Core_CPU：https://github.com/Andrew-Israil/Parallel_Computing_Quad_Core_CPU
• a-y-1 博客（橙的笔记本，CS149-Assignment-1&2）：https://a-y-1.github.io/2023/11/19/CS149-Assignment-1&2/
• 知乎 - 斯坦福cs149作业1随笔记录：https://zhuanlan.zhihu.com/p/686141714
• 知乎 - Stanford-CS149-并行计算-Assignment1-指南：https://zhuanlan.zhihu.com/p/7554656902
• Katyusha_Lzh 博客园 - CS149 assignment1：https://www.cnblogs.com/KatyushaLzh/p/19630089