3.26[a]paracompute homework

 5555

负载不平衡指多个线程的计算量差异显著，导致部分线程空转或等待，降低并行效率。其核心矛盾在于任务划分的静态性与计算动态性不匹配，尤其在处理不规则数据或动态任务时尤为突出。以稀疏矩阵的向量乘法为例，假设其非零元素分布极不均匀，会导致静态调度下线程负载差异很大。因此，采样动态调度，在运行时按需分配任务，当某线程完成其块后主动请求新块进行运算，并通过合理的锁机制来规避死锁问题。此外，进行数据重排与分块优化也可处理负载不平衡问题，即将高密度作为小块，低密度作为大块分发给不同线程。

444

区块分发基本原理为将任务空间划分为连续且大小相等的块，每个线程分配一个或多个完整块

循环分发基本原理为按轮询方式分配单个任务给各线程。

块循环分发结合以上两种方法，基本原理为依次为每个线程分发一个包含多个任务的固定块，重复分配直到全部任务都被处理

对比可以发现，区块分发的局部性好，在连续内存访问时，缓存命中率高，但存在问题为若任务执行时间差异大，可能导致部分线程空闲，即负载不平衡问题；而循环分发负载较为均衡，适用于任务执行时间差异大的场景；块循环分发结合区块和循环分发，通过调整块大小，使每个线程分配到缓存行整数倍大小的块，就可兼顾内存局部性和负载均衡，因此灵活性高，适用场景广。

虚假共享是循环分发的程序修改数组元素后，若其他线程要访问的元素与该元素同属一个缓存行中，就不得不重新载入数据；由于循环分发的跳跃式内存访问，若其跳跃的步长不足一个缓存行，那么相邻线程就会频繁出现虚假共享的问题。

3333

	​多线程	​多进程
​内存模型	共享同一进程的地址空间（全局变量、堆内存等）	每个进程拥有独立地址空间，需通过IPC（管道、共享内存等）通信
​资源开销	线程创建/切换仅需分配栈空间	需复制父进程资源（内存、文件描述符等），上下文切换成本高
​同步与互斥	需锁机制（互斥锁、信号量等）避免数据竞争	进程间资源隔离，天然避免内存竞争（但需处理IPC同步）
​稳定性	线程崩溃可能导致整个进程终止	进程间隔离，单个进程崩溃不影响其他进程

多线程主要目的在于避免空闲的未使用资源，多进程的目的在于利用冗余的资源。 

多线程可充分利用多核CPU并行执行；上下文切换仅涉及寄存器/栈，开销较小；线程之间能够更高效地实现资源共享，无需复杂的IPC机制。

​方法	​行为	​资源管理	​注意事项
​join()	阻塞调用线程，等待目标线程执行完成	自动回收线程资源（栈、寄存器状态等）	- 必须在析构前调用，否则触发std::terminate() - 同一线程只能join一次
​detach()	分离线程生命周期，使其成为后台守护线程	资源由运行时（C++）或init进程（Linux）回收	- 分离后无法再join - 需确保线程不访问已销毁对象

一句话来讲，join方法产生的子线程是由调用线程管理的，而detach产生的子线程脱离了调用线程，由系统负责管理 

22222 

虚假共享是指多个线程访问同一缓存行中不同变量时，因为修改导致缓存一致性协议频繁触发，从而降低性能。具体来说，现代CPU的缓存以64字节的缓存行为单位管理，当一个线程修改缓存行中的数据时，其他线程的该缓存行会被标记为无效，需要重新从内存加载，即使这些线程操作的是缓存行中不同的变量

原因可归纳为一下两点：1.变量在内存中连续存储，可能被分配到同一缓存行，而MESI协议以缓存行为最小单位维护一致性，无法区分变量是否真正共享。2.​不同线程修改同一缓存行中的独立变量，触发缓存行无效化

1111 

冯·诺依曼瓶颈指计算机中CPU与内存之间的数据传输速率远低于CPU计算速度，导致CPU因等待数据而空转的性能瓶颈。

在矩阵乘法运算中，利用缓存能够加快CPU获取矩阵数据，这主要基于空间局部性和时间局部性的原理；对于空间局部性，CPU按缓存行加载数据，一次加载可满足8次相邻地址浮点数之间的访问需求，此外，将B矩阵转置存储于缓存中，使 B[k][j] 按行访问，可避免跳跃式内存访问导致的缓存失效，从而可以进一步加快矩阵乘法计算速度；对于时间局部性，缓存可以避免重复从内存加载相同数据，如计算 C[i][j] 时需遍历 A 的第 i 行和 B 的第 j 列，若这些数据缓存在L1/L2中，后续计算 C[i][k] 或 C[k][j] 时可复用

其核心原因是冯·诺依曼架构中指令和数据共享同一总线，导致取指令和取数据无法并行

例如，当CPU需要频繁访问内存时，总线带宽不足会显著降低吞吐量，尤其在处理大规模数据时（如深度学习的矩阵运算）

在矩阵乘法W=U×V中，缓存通过以下机制缓解瓶颈：

1. ​时间局部性：频繁访问的行列元素（如U的行向量和V的列向量）被保留在高速缓存中，减少内存访问次数