by 李兆坤
如果解析相关内容还不能解决对第六章的某些疑惑，可以在企业微信上问我。
对串行、并发和并行等概念不清晰
==并发==是逻辑上的同时发生，而==并行==是物理上的同时发生。并发的关键是你有处理多个任务的能力，不一定要同时（也可以通过频繁切换多个线程来达到一段时间内的“伪并行”，但实际上还是串行的）；并行的关键是你有同时处理多个任务的能力。
在课本的本章中，使用并行与串行（serial）特指硬件支持，并发与顺序（sequential）特指软件行为。
对并行硬件的分类概念不清晰
一种对并行硬件的分类方法是基于指令流的数量和数据流的数量：
SISD（单指令流单数据流的处理器）是常规的单处理器。
MIMD（多指令流多数据流的处理器）是常规的多处理器。在其上编写的程序一般是 SPMD 风格（数据级并行（Data-Level Parallelism, DLP） 指处理器能够同时处理多条数据，是对不同的数据进行相同的操作获得的并行，属于单指令多数据（ Single Program Multiple Data, SPMD）模型），即在 MIMD 所有处理器上运行的单一程序，不同处理器通过条件语句执行不同的代码段。为 MIMD 上不同处理器编写不同的程序虽然可行，但扩展性较弱，一般不采用。
最接近 MISD（多指令流单数据流的处理器）的处理器是“流处理器（streamprocessor）”，即在流水线中对一个单独的数据流执行一系列计算和操作。
SIMD（单指令流多数据流的处理器）是将同样的指令在多个数据流上操作，相当于对向量数据进行操作。 SIMD 的优点是所有并行执行单元都是同步的，对源自同一 PC 的同一指令做出相应；另一个优点是降低指令宽度和空间， SIMD 只需要同时执行代码的一个副本，而 MIMD 需要在每个处理器上都有一个副本（消息传递的 MIMD）或多个指令 cache（共享内存的 MIMD）。
照抄答案
部分参考答案有明显错误，注意自己的思考
1
解析
虽然二分查找具有较好的串行性能，但在不修改代码的情况下很难实现并行。
比如，虽然可以在一个核心上进行 low 和 high 的比较、在第二个核上进行 mid 的计算、在第三个核心上进行 A[mid] 的比较，但这三步相互依赖。
如果没有合适的预测机制，并不会有任何的加速改进，时间复杂度仍为
(1) 没有影响
(2) 可以创建 N 个线程来将 N 个元素与值 X 同时进行比较，并并行执行这些操作，那么可以获得理想的加速比（Y），从而可以在执行单个比较的时间内完成比较
解析
强比例缩放（strong scaling），是指在问题规模固定情况下在多处理器上可获得的加速比；弱比例缩放（weak scaling），是指在问题规模与处理器数量按比例增长的多处理器上可获得的加速比。
4
解析
每个 C 中的元素计算都可以并行执行，因此加速比接近于 4
1
解析
伪共享（False Sharing）是并行计算中的一个概念。在许多现代处理器中，缓存是以行（cache line）为单位组织的。如果两个线程访问的数据在物理上相邻，并且位于同一缓存行，它们将共享该缓存行。但这些数据可能在逻辑上是独立的，此时就会发生伪共享（两个线程无意中共享同一个缓存行）。
每次更新 C 的值，如果都会将 4 个核心映射到相同的 cache 行（即各个核心上的并行线程发生伪共享），一个线程更新数据会导致整个 cache 行被替换，其他线程会发生 cache 缺失而无法并行。如此和串行就没有什么区别了，加速比下降为 1 。
可以将 C 矩阵从行存储变为列存储，这样可以将 C 中相邻元素映射到不同的 cache 块（行）。此外，保证在同一核心上按照列索引进行矩阵运算（就是按列组织并行计算）。
CPU SS : 每个核上都有两个功能单元（FU），双核共 4 个
CPU MT : 单核，有两个 FU
CPU SMT : 单核，有两个 FU
| Core1 | Core 2 |
|---|---|
| A3 | B1, B4 |
| A1, A2 | B1, B4 |
| A1, A4 | B2 |
| A1 | B3 |
总共需要 4 个周期
浪费 4 个发射槽
注意一个核心每次只能运行一个线程
| Core1 | Core 2 |
|---|---|
| A3 | B1, B4 |
| A1, A2 | B1, B4 |
| A1, A4 | B2 |
| A1 | B3 |
总共需要 4 个周期
浪费 4 个发射槽
或者分在两个 CPU 上，每个 CPU 执行一个线程。但这样虽然只需要 3 个周期，但会浪费 12 个发射槽
| FU1 | FU2 |
|---|---|
| A1 | A2 |
| A1 | |
| A1 | |
| B1 | B4 |
| B1 | B4 |
| A3 | |
| A4 | |
| B2 | |
| B3 |
总共需要 9 个周期
浪费 6 个发射槽
注意每周期只能运行一个线程
| FU1 | FU2 |
|---|---|
| A1 | B1 |
| A1 | B1 |
| A1 | B2 |
| A2 | B3 |
| A3 | B4 |
| A4 | B4 |
总共需要 6 个周期
无浪费
加速比为 4
可以将数据按行分配给不同的核心，每个核心计算 1/4
在 MIMD 机器上，每个 CPU 独立执行循环中的指令序列，通过不同的初始值 i 来划分工作负载，以实现并行处理。
以 CPU0 为例：
li $t0, 0 # i = 0
Loop_i:
li $t1, 0 # j = 0
Loop_j:
lw $t2, Y($t0, $t1) # Load Y[i][j] into $t2
addi $t2, $t2, 200 # Add 200 to $t2
sw $t2, X($t0, $t1) # Store $t2 into X[i][j]
addi $t1, $t1, 4 # j = j + 1 (each element is 4 bytes)
blt $t1, 12000, Loop_j # if (j < 3000) jump Loop_j
addi $t0, $t0, 4 # i = i + 1
blt $t0, 8000, Loop_i # if (i < 2000) jump Loop_iCPU1、 CPU2 和 CPU3 执行代码基本一样，只不过开始时让 i 分别为 500、 1000 和 1500。
clearall.v # Clear all SIMD registers
li $t0, 0 # i = 0
Loop_i:
li $t1, 0 # j = 0
lv Y($t0, $t1), $v1 # Load Y[i][j] into $v1
addi.v $v1, $v1, 200 # Add 200 to $v1
sv X($t0, $t1), $v1 # Store $v1 into X[i][j]
addi $t1, $t1, 8 # j = j + 8 (each SIMD reg holds 8 elements)
blt $t1, 24000, Loop_j # if (j < 3000) jump Loop_j
addi $t0, $t0, 8 # i = i + 8
blt $t0, 16000, Loop_i # if (i < 2000) jump Loop_iMIMD（每个 CPU 内） 和 SIMD 的指令数量都是 9 条。但SIMD 同时操作 8 个元素（向量宽度为 8）， MIMD 同时操作 4 个元素，前者并行程度更高一些。
所以相同时间内，SIMD 执行的指令数更多。
解析
参考课本 P381 ，向量指令沿用 MIPS 的指令名称，在其后增加一个字母 v，向量代码中的 $v 代表向量寄存器。
Whetstone 主要关注 CPU 的浮点运算性能
PARSEC 测试范围更广，不仅包括计算性能，还包括内存访问性能和可扩展性等方面的表现
只有 PARSEC 基准应受到共享和同步的影响，而 Whetstone 应该不受到这些影响。
解析
Whetstone 适用于评估单个处理器核心的性能，适合用于比较不同CPU架构或不同编译器优化选项对单个核心性能的影响。
PARSEC 适用于评估多核处理器在并行计算环境中的性能，适合用于评估多核系统的并行计算能力和整体性能。