第2章
2.1 速度的障碍
我们把计算实体称为进程，比如snow包中的worker。
并行计算中主要有两个性能相关的问题：
通信开销
负载平衡
2.2 性能和硬件结构
多处理器系统
就像它的名字所说一样，有两个或多个处理器，
例如，有两个或多个CPU，因此，两个或多个程序(或同一个程序的多个部分)可以同时进行运算。
我们会在后面讲到，家庭中常见的多核系统，本质上就是低端的多处理器。由于共享同一个物理内存，多处理器也被称为共享内存系统。
现在，几乎所有的个人电脑和笔记本电脑都至少是双核的。如果你拥有
这样一台机器，恭喜你，你拥有一个多处理器系统!
GPU是特殊的共享内存系统。
集群
一个集群是由多个可以独立运行的电脑构成的，这些电脑由网络连接在一起，使得它们能够协同起来解决大型的数值问题。
如果你的家里有网络，比如使用无线或者有线路由器的网络，恭喜你，你
拥有一个集群
2.3 内存的基础知识
一般来说，x和y都被保存在内存–例如RAM(随机存储器，random
access memory)–中的某个位置。
因此编译器(如C/C++/FORTRAN)或解释器(如R等语
言)，会在保存x和y的内存中分配具体的地址。通过机器将一个字赋值到
另一个字，来执行上述的赋值操作。
一般来说，向量会被存储在一个由连续字构成的集合中。矩阵也是同样的，但它还涉及到是按行存储还是按列存储。
C/C++使用行主序:先存储第一行(称为“第0行”)中的所有元素，然后存储第二行的所有元素，以此类推。
R和FORTRAN使用列主序:先存储第一列(称为“第1列”)中的所有元素。因此，如果z是R中一个的5x8的矩阵，那么z[2，3]在z所使用的内存空间中，是第12个字(5+5+2)。我们将会看到，这些方式会影响性能。
2.3.1 高速缓存
高速缓存（Cache）是一种小型、高速的存储器，位于处理器和主内存之间，主要用于存储最常用的数据。其目的是通过减少数据访问延迟来提高程序的执行效率。高速缓存通常分为多个层次，例如 L1、L2 和 L3 缓存，L1 缓存速度最快但容量最小，L3 缓存容量最大但速度较慢。缓存的工作原理是，处理器首先检查数据是否在缓存中，如果有则直接访问，如果没有，则从主内存中加载并放入缓存。缓存替换策略如 LRU 和 FIFO 确定当缓存满时哪些数据被替换。缓存大大提升了系统的性能，特别是对于频繁访问的数据和计算密集型任务。但也存在缓存未命中和缓存污染等挑战。
更详细的介绍
高速缓存的定义：
高速缓存（Cache）是一种小型、快速的内存存储，用于存放最近或最常使用的数据。它位于处理器和主内存（RAM）之间，目的是减少数据访问的延迟，提高数据访问速度。缓存的工作原理：
当处理器需要访问内存中的数据时，首先检查高速缓存是否有这个数据（叫做缓存命中）。如果缓存中有这个数据，处理器直接从缓存获取，速度非常快（称为“缓存命中”）。
如果缓存中没有该数据（叫做缓存未命中），则处理器从较慢的主内存中读取数据，并把这个数据加载到缓存中，供以后使用（称为“缓存未命中”）。缓存的层次结构：
L1 缓存：最接近处理器核心，速度最快，但容量最小（通常几十KB）。
L2 缓存：比 L1 缓存稍慢一些，但容量更大（通常几百 KB 到几 MB）。
L3 缓存：在多个核心之间共享，容量最大，但速度最慢（通常为几 MB）。
现代处理器通常包含 L1、L2 和 L3 缓存。不同层级的缓存速度和容量不同，作用是逐层存储数据，减少处理器访问内存的延迟。缓存替换策略：
当缓存已满且需要存储新的数据时，系统需要决定哪些数据应该被替换。常见的缓存替换策略包括：
LRU（Least Recently Used）：替换最近最少使用的数据。
FIFO（First In, First Out）：替换最早进入缓存的数据。
LFU（Least Frequently Used）：替换最少访问的数据。
5. 缓存一致性：
在多核处理器中，每个核心可能有自己的缓存，缓存中的数据可能不一致。这时候需要缓存一致性协议（如 MESI 协议）来确保所有核心的缓存数据保持一致。
- 缓存的优势：
提高数据访问速度：通过缓存数据的频繁访问，可以显著减少访问主内存的时间。
减少延迟：尤其是对于计算密集型应用和需要大量内存访问的程序，缓存可以大大减少计算时间。 - 缓存的挑战：
缓存未命中：虽然缓存可以加速数据访问，但缓存未命中的时候，处理器仍然需要从较慢的主内存中读取数据，这会带来较大的延迟。
缓存污染：当缓存中的数据不再被使用时，这些无用的数据占用了宝贵的缓存空间，导致缓存效率降低。
2.3.2 虚拟内存
直接用物理内存的不足?
解耦?管理?内存碎片?
2.3.3 检测高速缓存未命中及缺页错误
缓存未命中:
缓存结构?替换策略?
缺页错误:
硬件会触发一个缺页中断给OS
局部性原理?
R矩阵按列遍历
2.4 网络基础
…
2.5 延迟和带宽
2.6 线程调度
时间片?
状态切换:就绪状态,运行状态,等待状态
2.9 “大O”标记法
时间复杂度…
2.11 “易并行”是啥?
有的算法或算法的某一个步骤很难并行,就没必要并行了(例如:归并排序的最后一趟排序)
