Learning

CPU 内的并行编程 CPU 的功耗 $ P=C\cdot V^{2}\cdot f $ 导致纵使有更大的电路，热功耗限制了性能上限，从而有一堵“功耗墙”限制了 CPU 的性能，为此需要考虑如何在降低 $ V $ 和 $ f $ 的同时用面积换性能 有两个思路： 让一条指令能处理更多的数据：SIMD (Single Instruction, Multiple Data) “一条指令” 浪费的能量大致是定数 处理的数据越多，浪费越少 用更多更简单的处理器：多处理器系统、异构多处理器 同等面积，处理器越简单，数量越多 异构计算：最经典的例子是大小核架构（如 Apple M1） SIMD SIMD 的核心思想是在硬件层面实现数据级并行，它通过引入专门的硬件单元来达成这个目标： 宽位寄存器 (Wide Registers)：CPU 内部增加了比通用寄存器宽很多的专用寄存器 Intel 的 SSE 指令集引入了 128 位的 XMM 寄存器，而最新的 AVX-512 拥有 512 位的 ZMM 寄存器 这些宽位寄存器可以一次性装入多个数据元素，比如一个 128 位的寄存器可以同时容纳 4 个 32 位的浮点数，或者 16 个 8 位的整数 这些被打包在一起的数据被称为 Vector 向量处理单元 (Vector ALU)：CPU 内部也配备了能够对整个向量进行并行计算的 ALU ...

并发编程的核心抽象是实现一个计算图，计算发生在节点上，边表示节点之间的依赖关系，同时计算图在运行时可能是动态变化的 使用条件变量、锁、信号量等 api 去实现计算图并不是一个优雅的实现方式，因为这样会在代码中引入众多干扰代码，也可能导致一些问题 为此可以增加一些功能受限的语法，可以在同样描述计算图的功能下减少了许多潜在的问题 高性能计算中的并行编程 在高性能计算中，计算图通常易于静态切分，尤其适用于物理模拟的网格划分，为此 HPC 发展出多种高效的并行编程模型，具体学习可以参考 SJTU HPC 学习手册 MPI: 分布式内存并行 每个 MPI 进程有独立的内存空间，进程间通过显式消息传递（发送/接收）交换数据 OpenMP: 共享内存并行 多个线程在同一地址空间中并行执行，所有线程可以直接访问相同的数据，使用 #pragma omp 指令实现并行化 对非计算机专业来说非常友好，只需要在正常的代码上面加上编译指令即可，能轻松实现高效的并行优化 CUDA: GPU 异构并行 CPU 调度，GPU 执行大规模并行计算 概念： 核函数 (Kernel) ：在 GPU 上并行执行的函数 线程层次：线程 (threadIdx) 组成线程块 (blockIdx)，线程块组成网格 (gridDim) 内存层次：寄存器、共享内存（块内高速）、全局内存（所有线程可访问） 我们身边的并发编程 从 Web 1.0 到 Web 2.0 在 Web 时代用的最广泛的是 Javascript Asynchronous JavaScript and XML (Ajax; ~1999) 允许网页实现“后台刷新” jQuery $ (2006): A DOM Query Language (编程抽象) Web 2.0 时代的并发编程 线程开销大，并且大多数 Web 开发者难以进行并发编程 ...

数据竞争 大多并发 bug 最后都会体现为数据竞争 (Data Race) 对于顺序程序而言，函数 f() 返回之后就已经完成了所有的状态修改，对于其他部分而言这个修改是立即生效的；如果对于并发程序而言模式的切换也在瞬间完成，那就不会导致并发的问题 然而实际上模式的切换需要时间，执行的操作在未来一段时间之后才会就绪，但是我们在实际编程时总是容易有“立即生效”的肌肉记忆，这就导致了并发问题的可能性 不过对于函数式编程而言，操作不存在对外状态的修改，没有副作用（只会操作局部变量），这就不会导致并发问题 Data Race 发生的实质是不同的线程同时访问同一内存，并且至少有一个是写，形象的理解就是不同的内存访问在“赛跑”，跑赢的操作先执行 Not that easy: 虽然我们将数据竞争形象地比喻为“赛跑”，但实际上，哪一个操作能“跑赢”并没有想象中那么简单和确定，其复杂性主要体现在以下几个方面 弱内存模型 (Weak memory model)：在现代处理器架构中，为了提升性能，处理器可能会对内存操作进行重排序。这意味着，不同的线程或“观察者”在不同时间点看到共享内存的状态可能是不一致的。一个线程对内存的写入操作，可能不会立即对所有其他线程可见，导致不同线程观察到不同的结果。这种内存模型的一致性问题使得确定哪个操作“先发生”变得非常困难且不确定。 未定义行为 (Undefined Behavior)：从 C++11 标准开始，数据竞争被明确规定为未定义行为。这意味着，如果你的程序发生了数据竞争，编译器可以自由地产生任何行为，无论是崩溃、产生错误结果，还是看似正常运行但结果不可预测。这使得数据竞争成为非常危险且难以调试的并发错误，因为它的表现可能是不确定、不稳定的。 多线程与多内存的复杂交互：在实际的并发程序中，通常会有多个线程同时访问多个共享内存位置。这些线程和内存之间存在复杂的读（R）写（W）交互。一个线程对一个内存位置的写入可能影响到其他多个线程对该位置的读取，同时，多个内存位置之间也可能存在复杂的依赖关系和缓存一致性问题。这种错综复杂的交互网络进一步加剧了数据竞争的不可预测性。 为了消灭数据竞争，我们需要保证程序的 serializability ，可能竞争的内存访问要么互斥，要么同步 实际编程中遇到的数据竞争 bug 大多属于上错了锁和忘记上锁两种情况的变种 Case 1: 上错了锁 1 2 void T_1() { spin_lock(&A); sum++; spin_unlock(&A); } void T_2() { spin_lock(&B); sum++; spin_unlock(&B); } Case 2: 忘记上锁 1 2 void T_1() { spin_lock(&A); sum++; spin_unlock(&A); } void T_2() { sum++; } 但是实际系统面临的情况比这复杂的多，因为 内存可以是地址空间的任何内存，比如全局变量、堆内存分配的变量、程序的栈…… 访问可以发生在任何代码，比如自己的代码、框架代码、一行没读到的汇编指令、某条 ret 指令 “一行没读到的汇编指令”造成的访问的情况有编译器优化造成的指令重排、硬件层面弱内存模型的内存访问重排、还有一些高层语言操作的隐式内存访问 实际系统中虽然难以避免，但是会尽可能保证底层的结构对上层尽可能封闭来防止这种错误 死锁 死锁 (Deadlock) 是指一个群体中的每个成员都在等待其他成员（包括自身）采取行动的状态 死锁有两种： AA-Deadlock: 自己等待自己 1 2 3 4 5 6 7 lock(&lk); // lk->locked == ✅; proceed ... // Possibly in interrupt handler lock(&lk); // while (lk->locked == ❌) ; 这样的错误虽然看起来很傻，但是在真实程序复杂的控制流中是可能出现的 ...

信号量 互斥锁在某种意义上也可以认为实现了 “happens-before” 的依赖关系—— release 必然发生在 acquire 之前。我们可以试着利用这种依赖关系来实现计算图的调度：为每条边分配一个互斥锁，代表数据或前置任务的完成；一个节点必须获得所有入边对应的互斥锁才能开始计算，计算完成后，就释放所有出边对应的互斥锁，通知下游节点输出就绪（但是这种直接使用互斥锁作为边状态信号的方式是 undefined behavior，因为互斥锁主要用于保护临界区，其释放通常要求由持有它的线程完成，若释放未曾获取的锁，则行为未定义） 我们可以从这种想法中抽象出其本质，也就是用一个“信号”去获取资源的许可，类似餐厅的取号吃饭 这种信号的思想很适合用来管理计数类型的同类资源，比如停车场的空位，为了实现这种 producer-customer 的问题，用 条件变量 可以轻易解决，进入的条件就是存在空位 count < capacity ，那我们从减少变量的角度出发，这实际上也就是剩余空位的数量大于零，我们停车相当于消耗了一个车位，离开相当于创造了一个车位，这也就得到了所谓“信号量”的机制 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void P(sem_t *sem) { // Prolaag - try + decrease/down/wait/acquire mutex_lock(&sem->lk); while (!(sem->count > 0)) { cond_wait(&sem->cv, &sem->lk); } sem->count--; // 消耗一个信号 (车位) mutex_unlock(&sem->lk); } void V(sem_t *sem) { // Verhoog - increase/up/post/signal/release mutex_lock(&sem->lk); sem->count++; // 创建一个信号 (车位) cond_broadcast(&sem->cv); mutex_unlock(&sem->lk); } 根据这个一路推出信号量的思路，或许可以认为这是互斥锁的扩展 ...

同步和条件变量 互斥实现了原子性，但是无法实现确定性，也就是无法正确实现 “happens-before” 的关系 因此需要引入条件变量来实现线程的同步，形成受控制的并发事件的发生顺序（可以用乐团指挥来类比），把一系列不确定的状态在某一个时间点同步到了一个确定的状态，将发散的并发程序状态 “收束” 实现同步 实现 $ A\to B $： 1 2 3 4 5 6 7 A; can_proceed = true; (signal) while(!can_proceed); B // B: wait until the condition is satisfied 这样的思路大致正确，但是自选的循环有很大的性能问题，因此需要一个更加底层的机制来帮助实现这一点 最理想的 API 是 wait_until(cond) ，但是过去为了简化设计，变成了 条件不满足时等待：wait - 直接睡眠等待 条件满足时继续：signal/broadcast - 唤醒所有线程 （小时候的 scratch 编程其实已经有了这样的思想😂） 在 c++ 代码中我们可以把条件放到 $ \lambda $ 表达式中： 1 2 3 4 5 6 7 8 9 10 11 12 std::mutex mtx; std::condition_variable cv; void T_player() { std::unique_lock lk(mtx); cv.wait(lk, []{ return can_proceed; } ); cv.notify_all(); lk.unlock(); } 注意条件变量在等待时需要带着一把锁（需要确保检查和等待是原子操作） ...