What every programmer should know about memory, Part 1（笔记）
每个程序员都应该知道内存知识第一部分
现在硬件的组成是对的pc机器基本上是一下结构：
由南桥和北桥两部分组成：
南桥芯片主要通过多条不同的总线和设备通信，主要包括PCI，SATA,USB等还支持PATA，IEEE 串口及并口1394。
需要注意的地方：
1.cpu它与北桥之间的通信需要连接总线
2.与RAM通信需要北桥芯片
3.RAM只有一个端口
4.CPU和南桥设备通信需要通过北桥
第一瓶颈：早期RAM访问必须通过cpu，影响整体性能，因此出现了DMA(直接内存访问)CPU但干扰会导致和CPU争夺北桥带宽。
第二个瓶颈：北桥和RAM因此，双通道出现在总线之间(带宽可以翻倍，内存访问可以在两个通道上交错分配)
除了并发访问模式，还有瓶颈看2.2
可能会出现更昂贵的系统：
北桥本身没有内存控制器，而是连接到多个外部内存控制器。其优点是支持更多的内存，可以同时访问不同的内存区域，减少延迟，但对北桥的内部带宽有很大的要求。
使用外部内存控制器不是唯一的方法。另一种流行方法是将控制器集成到cpu内部直接连接到内存CPU
系统中有几个这样的架构cpu可以有几个内存库（memory bank），内存带宽4倍，无需强大的北桥。但缺点也很明显：1.内存不再是统一的资源（NUMA的得名），2.cpu本地内存可以正常访问，但需要访问其他内存和其他内存cpu互通。 在讨论访问远端内存的成本时，我们使用它「NUMA因子」这个词。 比如说IBM的x445和SGI的Altix系列。CPU节点中的内存访问时间是一致的，或者只是很小NUMA因子。而在节点之间的连接代价很大，而且有巨大的NUMA因子。
RAM主要分为二中静态RAM，动态RAM，前者速度快，代价搞，后者速度慢代价低
动态RAM只有一个晶体管和一个电容
动态RAM优点很简单，但缺点是读取状态时需要放电电容器，所以这个过程不能无限重复，必须在某个点重新充电。更糟糕的是，为了容纳大量的单元（现在通常在单个芯片上容纳超过10个9次方RAM电容器的容量必须很小(0.000000000000001法拉以下)。这样，完全充电后持有数万个电子。即使电容器的电阻很大(几兆欧姆)，也只需要很短的时间就能耗光电荷，称为「泄漏」。这种泄漏现在是大多数DRAM芯片每隔64ms必须刷新原因。(附A关于三极管的输入输出特性)
同步DRAM，顾名思义，参照一个时间源工作。时钟的频率决定了前端总线(FSB)的速度。以今天的SDRAM例如，每次数据传输包含64位，即8字节。所以FSB传输速率应为有效总线频率乘于8字节(4倍传输200MHz总线传输速率为6.4GB/s)。听起来很高，但要知道这只是峰值速率，实际上达不到最高速率。我们RAM在没有数据传输的情况下，模块交流协议有很多时间处于非工作状态。为了获得最佳的性能，我们必须了解这些非工作时间，并尽量缩短它们。
这里忽略了很多细节，我们只关注时钟频率，RAS与CAS信号、地址总线和数据总线。首先，内存控制器将行地址放在地址总线上，并减少RAS读取周期开始。所有信号都在时钟(CLK)所以，只要信号在读取时间点保持稳定，即使不是标准的方波也没关系。设置行地址地址RAM芯片锁定指定行。
CAS信号在tRCD(RAS到CAS延迟)一个时钟周期后发出。内存控制器将列地址放在地址总线上，以减少CAS线。在这里，我们可以看到地址的两部分是如何通过同一条总线传输的。
由于数据传输需要这么多的准备，仅仅传输一个词显然是浪费。因此，DRAM模块允许内存控制指定此次传输多少数据。二、四、八个字。这样，高速缓存的整条线可以一次填满，而不需要额外的线RAS/CAS序列。此外，内存控制器还可以在不重置选择的情况下发送新的内存控制器CAS信号。这样，读取或写入连续地址可以变得非常快，因为不需要发送RAS不需要将行为置于非激活状态(见下文)。
在上图中，SDRAM每个周期输出一个单词的数据。这是第一代SDRAM。而DDR可以在一个周期中输出两个字。这种做法可以减少传输时间，但无法降低时延。
2.2.图1只是读取数据的一部分，还有以下部分:
两次显示CAS信号时序图。第一个数据是CL周期准备就绪。在图中的例子中SDRAM两个字的数据在两个周期内传输。如果换成DDR四个字可以传输。即使在命令速率为1的情况下DRAM在模块上，不能立即发出预充电命令，而是等待数据传输完成。上图为两个周期。刚好与CL一样，但只是巧合。预充电信号没有专用线，有些实现是同时降低写作能力(WE)线和RAS触发线的方式。
发出预充电信命令后，需要等待tRP(行预充电时间)一个周期后才能选择行。.9.这个时间(紫色部分)大部分与内存传输时间(浅蓝色部分)重叠。好的。tRP大于传输时间，所以下一个RAS信号只能等待一个周期。
数据总线的7个周期中只有2个周期才是真正在用的。再用它乘于FSB速度，结果就是，800MHz总线的理论速率6.4GB/s降到了1.8GB/s
我们会看到预充电指令被数据传输时间限制（途中为COL Addr的传输）除此之外，SDRAM模块在RAS信号之后，需要经过一段时间，才能进行预充电(记为tRAS)（ minimum active to precharge time（也就是RAS信号之后到充电的最小时间间隔））它的值很大，一般达到tRP的2到3倍。如果在某个RAS信号之后，只有一个CAS信号，而且数据只传输很少几个周期，那么就有问题了。假设在图2.9中，第一个CAS信号是直接跟在一个RAS信号后免的，而tRAS为8个周期。那么预充电命令还需要被推迟一个周期，因为tRCD、CL和tRP加起来才7个周期。
DDR模块往往用w-z-y-z-T来表示。例如，2-3-2-8-T1，意思是：
w 2 CAS时延(CL)
x 3 RAS-to-CAS时延(t RCD)
y 2 RAS预充电时间(t RP)
z 8 激活到预充电时间(t RAS)
T T1 命令速率
充电对内存是性能最大的影响，根据JEDEC规范，DRAM单元必须保持每64ms刷新一次我们在解读性能参数时有必要知道，它也是DRAM生命周期的一个部分。如果系统需要读取某个重要的字，而刚好它所在的行正在刷新，那么处理器将会被延迟很长一段时间。刷新的具体耗时取决于DRAM模块本身。
以下是SDR（SDRAME）的操作图比较简单
DRAM阵列的频率和总线的频率保持相同，但是当所有组件频率上升时，那么导致耗电量也上升代价很大，所以就出了DDR，在不提高频率的状况下提高吞吐量
SDR和DDR1的区别就是DDR1可以在上升沿和下降沿都传输数据，实现了双倍的传输。DDR引入了一个缓冲区。缓冲区的每条数据线都持有两位。它要求内存单元阵列的数据总线包含两条线。实现的方式很简单，用同一个列地址同时访问两个DRAM单元。对单元阵列的修改也很小。
为了进一步，于是有了DDR2，最明显的变化是，总线的频率加倍了。频率的加倍意味着带宽的加倍。如果对单元阵列的频率加倍，显然是不经济的，因此DDR2要求I/O缓冲区在每个时钟周期读取4位。也就是说，DDR2的变化仅在于使I/O缓冲区运行在更高的速度上。这是可行的，而且耗电也不会显著增加。DDR2的命名与DDR1相仿，只是将因子2替换成4
| 阵列频率 | 总线频率 | 数据率 | 名称(速率) | 名称 (FSB) |
|---|---|---|---|---|
| 133MHz | 266MHz | 4,256MB/s | PC2-4200 | DDR2-533 |
| 166MHz | 333MHz | 5,312MB/s | PC2-5300 | DDR2-667 |
| 200MHz | 400MHz | 6,400MB/s | PC2-6400 | DDR2-800 |
| 250MHz | 500MHz | 8,000MB/s | PC2-8000 | DDR2-1000 |
| 266MHz | 533MHz | 8,512MB/s | PC2-8500 | DDR2-1066 |
FSB速度是用有效频率来标记的，即把上升、下降沿均传输数据的因素考虑进去，因此数字被撑大了。所以，拥有266MHz总线的133MHz模块有着533MHz的FSB“频率”
DDR3变化更多，电压从1.8下降到了1.5于是耗电也变小了，或者说保持相同的耗电，ddr3可以达到更高的频率或者，保持同样的热能释放，实现容量翻番
DDR3模块的单元阵列将运行在内部总线的四分之一速度上，DDR3的I/O缓冲区从DDR2的4位提升到8位
DDR3可能会有一个问题，即在1600Mb/s或更高速率下，每个通道的模块数可能会限制为1。在早期版本中，这一要求是针对所有频率的。我们希望这个要求可以提高一些，否则系统容量将会受到严重的限制。
我们预计中各DDR3模块的名称。JEDEC目前同意了前四种。由于Intel的45nm处理器是1600Mb/s的FSB，1866Mb/s可以用于超频市场。随着DDR3的发展，可能会有更多类型加入
| 阵列频率 | 总线频率 | 数据速率 | 名称(速率) | 名称 (FSB) |
|---|---|---|---|---|
| 100MHz | 400MHz | 6,400MB/s | PC3-6400 | DDR3-800 |
| 133MHz | 533MHz | 8,512MB/s | PC3-8500 | DDR3-1066 |
| 166MHz | 667MHz | 10,667MB/s | PC3-10667 | DDR3-1333 |
| 200MHz | 800MHz | 12,800MB/s | PC3-12800 | DDR3-1600 |
| 233MHz | 933MHz | 14,933MB/s | PC3-14900 | DDR3-1866 |
所有的DDR内存都有一个问题：不断增加的频率使得建立并行数据总线变得十分困难。一个DDR2模块有240根引脚。所有到地址和数据引脚的连线必须被布置得差不多一样长。更大的问题是，如果多于一个DDR模块通过菊花链连接在同一个总线上，每个模块所接收到的信号随着模块的增加会变得越来越扭曲。
DDR2规范允许每条总线（又称通道）连接最多两个模块，DDR3在高频率下只允许每个通道连接一个模块。每条总线多达240根引脚使得单个北桥无法以合理的方式驱动两个通道。替代方案是增加外部内存控制器，但这会提高成本。
一种解法是，在处理器中加入内存控制器
另外一种是，Intel针对大型服务器方面的解法(至少在未来几年)，是被称为全缓冲DRAM(FB-DRAM)的技术。FB-DRAM采用与DDR2相同的器件，因此造价低廉。不同之处在于它们与内存控制器的连接方式。FB-DRAM没有用并行总线，而用了串行总线。串行总线可以达到更高的频率，串行化的负面影响，甚至可以增加带宽。使用串行总线后
- 每个通道可以使用更多的模块。
- 每个北桥/内存控制器可以使用更多的通道。
- 串行总线是全双工的(两条线)。
FB-DRAM只有69个脚。通过菊花链方式连接多个FB-DRAM也很简单。FB-DRAM规范允许每个通道连接最多8个模块。在对比下双通道北桥的连接性，采用FB-DRAM后，北桥可以驱动6个通道，而且脚数更少——6x69对比2x240。每个通道的布线也更为简单，有助于降低主板的成本。全双工的并行总线过于昂贵。而换成串行线后，这不再是一个问题，因此串行总线按全双工来设计的，这也意味着，在某些情况下，仅靠这一特性，总线的理论带宽已经翻了一倍。还不止于此。由于FB-DRAM控制器可同时连接6个通道，因此可以利用它来增加某些小内存系统的带宽。对于一个双通道、4模块的DDR2系统，我们可以用一个普通FB-DRAM控制器，用4通道来实现相同的容量。串行总线的实际带宽取决于在FB-DRAM模块中所使用的DDR2(或DDR3)芯片的类型。
| DDR2 | FB-DRAM | |
|---|---|---|
| 脚 | 240 | 69 |
| 通道 | 2 | 6 |
| 每通道DIMM数 | 2 | 8 |
| 最大内存 | 16GB | 192GB |
| 吞吐量 | ~10GB/s | ~40GB/s |
通过本节，大家应该了解到访问DRAM的过程并不是一个快速的过程。至少与处理器的速度相比，或与处理器访问寄存器及缓存的速度相比，DRAM的访问不算快。大家还需要记住CPU和内存的频率是不同的。Intel Core 2处理器运行在2.933GHz，而1.066GHz FSB有11:1的时钟比率(注: 1.066GHz的总线为四泵总线)。那么，内存总线上延迟一个周期意味着处理器延迟11个周期。绝大多数机器使用的DRAM更慢，因此延迟更大。
前文中读命令的时序图表明，DRAM模块可以支持高速数据传输。每个完整行可以被毫无延迟地传输。数据总线可以100%被占。对DDR而言，意味着每个周期传输2个64位字。对于DDR2-800模块和双通道而言，意味着12.8GB/s的速率。
但是，除非是特殊设计，DRAM的访问并不总是串行的。访问不连续的内存区意味着需要预充电和RAS信号。于是，各种速度开始慢下来，DRAM模块急需帮助。预充电的时间越短，数据传输所受的惩罚越小。
硬件和软件的预取(参见第6.3节)可以在时序中制造更多的重叠区，降低延迟。预取还可以转移内存操作的时间，从而减少争用。我们常常遇到的问题是，在这一轮中生成的数据需要被存储，而下一轮的数据需要被读出来。通过转移读取的时间，读和写就不需要同时发出了
除了CPU外，系统中还有其它一些组件也可以访问主存。高性能网卡或大规模存储控制器是无法承受通过CPU来传输数据的，它们一般直接对内存进行读写(直接内存访问，DMA)。在图2.1中可以看到，它们可以通过南桥和北桥直接访问内存。另外，其它总线，比如USB等也需要FSB带宽，即使它们并不使用DMA，但南桥仍要通过FSB连接到北桥。
DMA当然有很大的优点，但也意味着FSB带宽会有更多的竞争。在有大量DMA流量的情况下，CPU在访问内存时必然会有更大的延迟。我们可以用一些硬件来解决这个问题。例如，通过图2.3中的架构，我们可以挑选不受DMA影响的节点，让它们的内存为我们的计算服务。还可以在每个节点上连接一个南桥，将FSB的负荷均匀地分担到每个节点上。
三极管 有3个极1.发射极（e）,基极（b）,集电极(c)
输入特性：当b输入一定电压是，发射端导通
输出特性：当c，e之间加点压，电流大小，有基极输入电流控制c和e之间的电流大小
这样对动态内存单元中的电容来说每次读取就是一个放过程，所以读完之后要重新充电
Memory part 2: CPU caches
每个程序员都应该了解的 CPU 高速缓存
早期的一些系统就是类似的架构。在这种架构中，CPU核心不再直连到主存。数据的读取和存储都经过高速缓存。主存与高速缓存都连到系统总线上，这条总线同时还用于与其它组件通信。我们管这条总线叫“FSB”.
在高速缓存出现后不久，系统变得更加复杂。高速缓存与主存之间的速度差异进一步拉大，直到加入了另一级缓存。新加入的这一级缓存比第一级缓存更大，但是更慢。由于加大一级缓存的做法从经济上考虑是行不通的，所以有了二级缓存，甚至现在的有些系统拥有三级缓存.
L1d是一级数据缓存，L1i是一级指令缓存，等等。请注意，这只是示意图，
。CPU的设计者们在设计高速缓存的接口时拥有很大的自由。
我们有多核CPU，每个核心可以有多个“线程”。核心与线程的不同之处在于，核心拥有独立的硬件资源
默认情况下，CPU核心所有的数据的读或写都存储在缓存中。当然，也有内存区域不能被缓存的
如果CPU需要访问某个字(word)，先检索缓存。很显然，缓存不可能容纳主存所有内容(否则还需要主存干嘛)。系统用字的内存地址来对缓存条目进行标记。如果需要读写某个地址的字，那么根据标签来检索缓存即可(后面会介绍还会使用地址来计算缓存的地址)
标签是需要额外空间的，用字作为缓存的粒度显然毫无效率。因为标签可能也有32位（x86上）。内存模块在传输位于同一行上的多份数据时，由于不需要发送新CAS信号，甚至不需要发送RAS信号，因此可以实现很高的效率。基于以上的原因，缓存条目并不存储单个字，而是存储若干连续字组成的“线”。在早期的缓存中，线长是32字节，现在一般是64字节。对于64位宽的内存总线，每条线需要8次传输。而DDR对于这种传输模式的支持更为高效。
当处理器需要内存中的某块数据时，整条缓存线被装入L1d。缓存线的地址通过对内存地址进行掩码操作生成。对于64字节的缓存线，是将低6位置0。这些被丢弃的位作为线内偏移量。其它的位作为标签，并用于在缓存内定位。在实践中，我们将地址分为三个部分。32位地址的情况如下:
如果缓存线长度为2O，那么地址的低O位用作线内偏移量。上面的S位选择“缓存集”。后面我们会说明使用缓存集的原因。现在只需要明白一共有2S个缓存集就够了。剩下的32 - S - O = T位组成标签。它们用来同一个cache set中的各条线
当某条指令修改内存时，仍然要先装入缓存线，因为任何指令都不可能同时修改整条线。因此需要在写操作前先把缓存线装载进来。如果缓存线被写入，但还没有写回主存，那就是所谓的“脏了”。脏了的线一旦写回主存，脏标记即被清除。为了装入新数据，基本上总是要先在缓存中清理出位置。L1d将内容逐出L1d，推入L2(线长相同)。当然，L2也需要清理位置。于是L2将内容推入L3，最后L3将它推入主存。这种逐出操作一级比一级昂贵。（所以AMD公司通常使用exclusive caches见
，Intel使用inclusive cache）
在对称多处理器（SMP）架构的系统中，CPU的高速缓存不能独立的工作。在任何时候，所有的处理器都应该拥有相同的内存内容。保证这样的统一的内存视图被称为“高速缓存一致性”从一个处理器直接访问另一个处理器的高速缓存这种模型设计代价将是非常昂贵的，它是一个相当大的瓶颈。而是使用，当另一个处理器要读取或写入到高速缓存线上时，处理器会去检测。
如果CPU检测到一个写访问，而且该CPU的cache中已经缓存了一个cache line的原始副本，那么这个cache line将被标记为无效的cache line。接下来在引用这个cache line之前，需要重新加载该cache line。
更精确的cache实现需要考虑到其他更多的可能性，比如第二个CPU在读或者写他的cache line时，发现该cache line在第一个CPU的cache中被标记为脏数据了，此时我们就需要做进一步的处理。在这种情况下，主存储器已经失效，第二个CPU需要读取第一个CPU的cache line。通过测试，我们知道在这种情况下第一个CPU会将自己的cache line数据自动发送给第二个CPU。这种操作是绕过主存储器的，但是有时候存储控制器是可以直接将第一个CPU中的cache line数据存储到主存储器中。对第一个CPU的cache的写访问会导致第二个cpu的cache line的所有拷贝被标记为无效。
对于写入，cpu不需要等待安全的写入，只要能模拟这个效果，cpu就可以走捷径
以下是随机写入的图：
图中有三个比较明显的不同阶段。很正常，这个处理器有L1d和L2，没有L3。根据经验可以推测出，L1d有2**13字节，而L2有2**20字节。因为，如果整个工作集都可以放入L1d，那么只需不到10个周期就可以完成操作。如果工作集超过L1d，处理器不得不从L2获取数据，于是时间飘升到28个周期左右。如果工作集更大，超过了L2，那么时间进一步暴涨到480个周期以上。这时候，许多操作将不得不从主存中获取数据。更糟糕的是，如果修改了数据，还需要将这些脏了的缓存线写回内存。（
）
我们可以让缓存的每条线能存放任何内存地址的数据。这就是所谓的全关联缓存(fully associative cache)。这种缓存方式，如果处理器要访问某条线，那么需要所有的cacheline的tag和请求的地址比较。
全关联：优点，可以放任意地址的数据，不会出现类似直接映射一样的状况，如果数据分布不均匀导致被换出，从而导致miss增加
缺点，当cpu给出一个地址访问某一个缓存线，需要扫描所有的缓存
直接映射：优点，电路简单，查询某个元素的速度很快。因为一个元素出现在cache的位子是固定的。
缺点，如果数据分布在同一个set那么，会导致miss大大的提高
组关联：这个是当前普遍的使用方法。是直接映射和全关联的折中办法
| L2 Cache Size | Associativity | |||||||
|---|---|---|---|---|---|---|---|---|
| Direct | 2 | 4 | 8 | |||||
| CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | |
| 512k | 27,794,595 | 20,422,527 | 25,222,611 | 18,303,581 | 24,096,510 | 17,356,121 | 23,666,929 | 17,029,334 |
| 1M | 19,007,315 | 13,903,854 | 16,566,738 | 12,127,174 | 15,537,500 | 11,436,705 | 15,162,895 | 11,233,896 |
| 2M | 12,230,962 | 8,801,403 | 9,081,881 | 6,491,011 | 7,878,601 | 5,675,181 | 7,391,389 | 5,382,064 |
| 4M | 7,749,986 | 5,427,836 | 4,736,187 | 3,159,507 | 3,788,122 | 2,418,898 | 3,430,713 | 2,125,103 |
| 8M | 4,731,904 | 3,209,693 | 2,690,498 | 1,602,957 | 2,207,655 | 1,228,190 | 2,111,075 | 1,155,847 |
| 16M | 2,620,587 | 1,528,592 | 1,958,293 | 1,089,580 | 1,704,878 | 883,530 | 1,671,541 | 862,324 |
表说明：关联度，cache大小，cacheline大小对miss的影响。从上面数据得出的结论是CL64比CL32miss要少，cache越到miss越少，关联度越高miss越少
图是表数据的图标化更容易看出，问题其中CL大小为32。cache size越大miss越少，关联越大miss 越少
在其他文献中提到说增加关联度和增加缓存有相同的效果，这个当然是不正确的看图中，4m-8m直接关联和，2路关联是有一样的提升，但是当缓存越来越大就不好说了。测试程序的workset只有5.6M，使用8MB之后自然无法体现优势。但是当workset越来越大，小缓存的关联性就体现出了巨大的优势。
随着多核cpu的出现，相对来说cache的大小就被平分，因此关联性就显得比较重要。但是已经到了16路关联，如果再加显然比较困难，所以就有厂家开始考虑使用3级缓存。
用于测试程序的数据可以模拟一个任意大小的工作集：包括读、写访问，随机、连续访问。在图3.4中我们可以看到，程序为工作集创建了一个与其大小和元素类型相同的数组：
struct l {
struct l *n;
long int pad[NPAD];
};
2**N 字节的工作集包含2**N/sizeof(struct l)个元素。显然sizeof(struct l) 的值取决于NPAD的大小。在32位系统上，NPAD=7意味着数组的每个元素的大小为32字节，在64位系统上，NPAD=7意味着数组的每个元素的大小为64字节。(
关于如何CHECK，我还不知道)
最简单的情况就是遍历链表中顺序存储的节点。无论是从前向后处理，还是从后向前，对于处理器来说没有什么区别。下面的测试中，我们需要得到处理链表中一个元素所需要的时间，以CPU时钟周期最为计时单元。图显示了测试结构。除非有特殊说明, 所有的测试都是在Pentium 4 64-bit 平台上进行的，因此结构体l中NPAD=0，大小为8字节。
一开始的两个测试数据收到了噪音的污染。由于它们的工作负荷太小，无法过滤掉系统内其它进程对它们的影响。我们可以认为它们都是4个周期以内的。这样一来，整个图可以划分为比较明显的三个部分:
- 工作集小于2**14字节的。
- 工作集从2**15字节到2**20字节的。
- 工作集大于2**21字节的。
这样的结果很容易解释——是因为处理器有16KB的L1d和1MB的L2。
L1d的部分跟我们预想的差不多，在一台P4上耗时为4个周期左右。但L2的结果则出乎意料。大家可能觉得需要14个周期以上，但实际只用了9个周期。这要归功于处理器先进的处理逻辑，当它使用连续的内存区时，会 预先读取下一条缓存线的数据。这样一来，当真正使用下一条线的时候，其实已经早已读完一半了，于是真正的等待耗时会比L2的访问时间少很多。
在工作集超过L2的大小之后，预取的效果更明显了。前面我们说过，主存的访问需要耗时200个周期以上。但在预取的帮助下，实际耗时保持在9个周期左右。200 vs 9，效果非常不错。
在L2阶段，三条新加的线基本重合，而且耗时比老的那条线高很多，大约在28个周期左右，差不多就是L2的访问时间。这表明，从L2到L1d的预取并没有生效。这是因为，对于最下面的线(NPAD=0)，由于结构小，8次循环后才需要访问一条新缓存线，而上面三条线对应的结构比较大，拿相对最小的NPAD=7来说，光是一次循环就需要访问一条新线，更不用说更大的NPAD=15和31了。而预取逻辑是无法在每个周期装载新线的，因此每次循环都需要从L2读取，我们看到的就是从L2读取的时延。
(有一点想不通作者这里说是28个周期是L2的访问时间，但是上面为什么说是14个周期，有一种不靠谱的感觉。元素大小太大导致预取效果很差，但是顺序的访问方式很容易被预取，为什么不没有呢，作者的观点是
预取逻辑是无法在每个周期装载新线的所以导致预取无效)
另一个导致慢下来的原因是TLB缓存的未命中。TLB是存储虚实地址映射的缓存。为了保持快速，TLB只有很小的容量。如果有大量页被反复访问，超出了TLB缓存容量，就会导致反复地进行地址翻译，这会耗费大量时间。TLB查找的代价分摊到所有元素上，如果元素越大，那么元素的数量越少，每个元素承担的那一份就越多。
为了观察TLB的性能，我们可以进行另两项测试。第一项：我们还是顺序存储列表中的元素，使NPAD=7，让每个元素占满整个cache line，第二项：我们将列表的每个元素存储在一个单独的页上，忽略每个页没有使用的部分以用来计算工作集的大小。结果表明，第一项测试中，每次列表的迭代都需要一个新的cache line，而且每64个元素就需要一个新的页。第二项测试中，每次迭代都会访问一个cache，都需要加载一个新页。
基于可用RAM空间的有限性，测试设置容量空间大小为2的24次方字节，这就需要1GB的容量将对象放置在分页上。NPAD等于7的曲线。我们看到不同的步长显示了高速缓存L1d和L2的大小。第二条曲线看上去完全不同，其最重要的特点是当工作容量到达2的13次方字节时开始大幅度增长。这就是TLB缓存溢出的时候。我们能计算出一个64字节大小的元素的TLB缓存有64个输入。成本不会受页面错误影响，因为程序锁定了存储器以防止内存被换出。可以看出，计算物理地址并把它存储在TLB中所花费的周期数量级是非常高的。从中可以清楚的得到：TLB缓存效率降低的一个重要因素是大型NPAD值的减缓。由于物理地址必须在缓存行能被L2或主存读取之前计算出来，地址转换这个不利因素就增加了内存访问时间。这一点部分解释了为什么NPAD等于31时每个列表元素的总花费比理论上的RAM访问时间要高。
所有情况下元素宽度都为16个字节。第一条曲线“Follow”是熟悉的链表走线在这里作为基线。第二条曲线，标记为“Inc”，仅仅在当前元素进入下一个前给其增加thepad[0]成员。第三条曲线，标记为"Addnext0"， 取出下一个元素的thepad[0]链表元素并把它添加为当前链表元素的thepad[0]成员。
在没运行时，大家可能会以为"Addnext0"更慢，因为它要做的事情更多——在没进到下个元素之前就需要装载它的值。但实际的运行结果令人惊讶——在某些小工作集下，"Addnext0"比"Inc"更快。这是为什么呢？原因在于，
系统一般会对下一个元素进行强制性预取。当程序前进到下个元素时这个元素其实早已被预取在L1d里。但是，"Addnext0"比"Inc"更快离开L2，这是因为它需要从主存装载更多的数据。而在工作集达到2 21字节时，"Addnext0"的耗时达到了28个周期，是同期"Follow"14周期的两倍。这个两倍也很好解释。"Addnext0"和"Inc"涉及对内存的修改，因此L2的逐出操作不能简单地把数据一扔了事，而必须将它们写入内存。因此FSB的可用带宽变成了一半，传输等量数据的耗时也就变成了原来的两倍。
决定顺序式缓存处理性能的另一个重要因素是缓存容量。虽然这一点比较明显，但还是值得一说。图中展示了128字节长元素的测试结果(64位机，NPAD=15)。这次我们比较三台不同计算机的曲线，两台P4，一台Core 2。两台P4的区别是缓存容量不同，一台是32k的L1d和1M的L2，一台是16K的L1d、512k的L2和2M的L3。Core 2那台则是32k的L1d和4M的L2。
图中最有趣的地方，并不是Core 2如何大胜两台P4，而是工作集开始增长到连末级缓存也放不下、需要主存热情参与之后的部分。与我们预计的相似，最末级缓存越大，曲线停留在L2访问耗时区的时间越长。在2**20字节的工作集时，第二台P4(更老一些)比第一台P4要快上一倍，这要完全归功于更大的末级缓存。而Core 2拜它巨大的4M L2所赐，表现更为卓越。
如果换成随机访问或者不可预测的访问，情况就大不相同了。图3.15比较了顺序读取与随机读取的耗时情况。
换成随机之后，处理器无法再有效地预取数据，只有少数情况下靠运气刚好碰到先后访问的两个元素挨在一起的情形。
图3.15中有两个需要关注的地方。
，在大的工作集下需要非常多的周期。这台机器访问主存的时间大约为200-300个周期，但图中的耗时甚至超过了450个周期。我们前面已经观察到过类似现象(对比图3.11)。这说明，处理器的自动预取在这里起到了反效果。
，代表随机访问的曲线在各个阶段不像顺序访问那样保持平坦，而是不断攀升。为了解释这个问题，我们测量了程序在不同工作集下对L2的访问情况。结果如图3.16和表3.2。
| Set Size | Sequential | Random | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| L2 Hit | L2 Miss | #Iter | Ratio Miss/Hit | L2 Accesses Per Iter | L2 Hit | L2 Miss | #Iter | Ratio Miss/Hit | L2 Accesses Per Iter | |
| 220 | 88,636 | 843 | 16,384 | 0.94% | 5.5 | 30,462 | 4721 | 1,024 | 13.42% | 34.4 |
| 221 | 88,105 | 1,584 | 8,192 | 1.77% | 10.9 | 21,817 | 15,151 | 512 | 40.98% | 72.2 |
| 222 | 88,106 | 1,600 | 4,096 | 1.78% | 21.9 | 22,258 | 22,285 | 256 | 50.03% | 174.0 |
| 223 | 88,104 | 1,614 | 2,048 | 1.80% | 43.8 | 27,521 | 26,274 | 128 | 48.84% | 420.3 |
| 224 | 88,114 | 1,655 | 1,024 | 1.84% | 87.7 | 33,166 | 29,115 | 64 | 46.75% | 973.1 |
| 225 | 88,112 | 1,730 | 512 | 1.93% | 175.5 | 39,858 | 32,360 | 32 | 44.81% | 2,256.8 |
| 226 | 88,112 | 1,906 | 256 | 2.12% | 351.6 | 48,539 | 38,151 | 16 | 44.01% | 5,418.1 |
| 227 | 88,114 | 2,244 | 128 | 2.48% | 705.9 | 62,423 | 52,049 | 8 | 45.47% | 14,309.0 |
| 228 | 88,120 | 2,939 | 64 | 3.23% | 1,422.8 | 81,906 | 87,167 | 4 | 51.56% | 42,268.3 |
| 229 | 88,137 | 4,318 | 32 | 4.67% | 2,889.2 | 119,079 | 163,398 | 2 | 57.84% | 141,238.5 |
从图中可以看出，当工作集大小超过L2时，未命中率(L2未命中次数/L2访问次数)开始上升。整条曲线的走向与图3.15有些相似: 先急速爬升，随后缓缓下滑，最后再度爬升。它与耗时图有紧密的关联。L2未命中率会一直爬升到100%为止。只要工作集足够大(并且内存也足够大)，就可以将缓存线位于L2内或处于装载过程中的可能性降到非常低。
（工作集越大，随机访问，命中率就会越小）
而换成随机访问后，单位耗时的增长超过了工作集的增长，根源是TLB未命中率的上升。图3.17描绘的是NPAD=7时随机访问的耗时情况。这一次，我们修改了随机访问的方式。正常情况下是把整个列表作为一个块进行随机(以∞表示)，而其它11条线则是在小一些的块里进行随机。例如，标签为'60'的线表示以60页(245760字节)为单位进行随机。先遍历完这个块里的所有元素，再访问另一个块。这样一来，可以保证任意时刻使用的TLB条目数都是有限的。
（也就是上图的性能差距主要来自于TLB的未命中率）
NPAD=7对应于64字节，正好等于缓存线的长度。由于元素顺序随机，硬件预取不可能有任何效果，特别是在元素较多的情况下。这意味着，分块随机时的L2未命中率与整个列表随机时的未命中率没有本质的差别。随着块的增大，曲线逐渐逼近整个列表随机对应的曲线。这说明，在这个测试里，性能受到TLB命中率的影响很大，如果我们能提高TLB命中率，就能大幅度地提升性能(在后面的一个例子里，性能提升了38%之多)。（
作者在这里突出当元素长度>=cache line 长度的时候并且元素是随机访问硬件预取失效，为什么？我根据作者提供的结构体加上vtune，当结构体大小刚好为64B的时候并没有发现L1的miss）
为了保持cache和内存的一致性，当cache被修改后，我们要刷新到主存中（flush），可以通过2种方式实现：1.write through（写透），2.write back（写回）
写透是当修改cache会立刻写入到主存，
缺点：速度慢，占用FSB总线
优点：实现简单
写回是当修改cache后不是马上写入到主存，而是打上已弄脏(dirty)的标记。当以后某个时间点缓存线被丢弃时，这个已弄脏标记会通知处理器把数据写回到主存中，而不是简单地扔掉。
优点：速度快
缺点：当有多个处理器(或核心、超线程)访问同一块内存时，必须确保它们在任何时候看到的都是相同的内容。如果缓存线在其中一个处理器上弄脏了(修改了，但还没写回主存)，而第二个处理器刚好要读取同一个内存地址，那么这个读操作不能去读主存，而需要读第一个处理器的缓存线。
直接提供从一个处理器到另一处理器的高速访问，这是完全不切实际的。从一开始，连接速度根本就不够快。实际的选择是，在其需要的情况下，转移到其他处理器
现在的问题是，当该高速缓存线转移的时候会发生什么？这个问题回答起来相当容易：当一个处理器需要在另一个处理器的高速缓存中读或者写的脏的高速缓存线的时候。但怎样处理器怎样确定在另一个处理器的缓存中的高速缓存线是脏的？假设它仅仅是因为一个高速缓存线被另一个处理器加载将是次优的（最好的）。通常情况下，大多数的内存访问是只读的访问和产生高速缓存线，并不脏。在高速缓存线上处理器频繁的操作（当然，否则为什么我们有这样的文件呢？），也就意味着每一次写访问后，都要广播关于高速缓存线的改变将变得不切实际。
人们开发除了MESI缓存一致性协议(MESI=Modified, Exclusive, Shared, Invalid，变更的、独占的、共享的、无效的)。协议的名称来自协议中缓存线可以进入的四种状态:
- 变更的: 本地处理器修改了缓存线。同时暗示，它是所有缓存中唯一的拷贝。
- 独占的: 缓存线没有被修改，而且没有被装入其它处理器缓存。
- 共享的: 缓存线没有被修改，但可能已被装入其它处理器缓存。
- 无效的: 缓存线无效，即，未被使用。
MESI协议开发了很多年，最初的版本比较简单，但是效率也比较差。现在的版本通过以上4个状态可以有效地实现写回式缓存，同时支持不同处理器对只读数据的并发访问。
（写回如何被实现，通过监听其处理器的状态）
在协议中，通过处理器监听其它处理器的活动，不需太多努力即可实现状态变更。处理器将操作发布在外部引脚上，使外部可以了解到处理过程。
一开始，所有缓存线都是空的，缓存为无效(Invalid)状态。当有数据装进缓存供写入时，缓存变为变更(Modified)状态。如果有数据装进缓存供读取，那么新状态取决于其它处理器是否已经状态了同一条缓存线。如果是，那么新状态变成共享(Shared)状态，否则变成独占(Exclusive)状态。
如果本地处理器对某条Modified缓存线进行读写，那么直接使用缓存内容，状态保持不变。如果另一个处理器希望读它，那么第一个处理器将内容发给第二个处理器，然后可以将缓存状态置为Shared。而发给第二个处理器的数据由内存控制器接收，并放入内存中。如果这一步没有发生，就不能将这条线置为Shared。如果第二个处理器希望的是写，那么第一个处理器将内容发给它后，将缓存置为Invalid。这就是臭名昭著的"请求所有权(Request For Ownership,RFO)"操作。在末级缓存执行RFO操作的代价比较高。如果是写通式缓存，还要加上将内容写入上一层缓存或主存的时间，进一步提升了代价。
对于Shared缓存线，本地处理器的读取操作并不需要修改状态，而且可以直接从缓存满足。而本地处理器的写入操作则需要将状态置为Modified，而且需要将缓存线在其它处理器的所有拷贝置为Invalid。因此，这个写入操作需要通过RFO消息发通知其它处理器。如果第二个处理器请求读取，无事发生。因为主存已经包含了当前数据，而且状态已经为Shared。如果第二个处理器需要写入，则将缓存线置为Invalid。不需要总线操作。
Exclusive状态与Shared状态很像，只有一个不同之处: 在Exclusive状态时，本地写入操作不需要在总线上声明，因为本地的缓存是系统中唯一的拷贝。这是一个巨大的优势，所以处理器会尽量将缓存线保留在Exclusive状态，而不是Shared状态。只有在信息不可用时，才退而求其次选择shared。放弃Exclusive不会引起任何功能缺失，但会导致性能下降，因为E→M要远远快于S→M。
从以上的说明中应该已经可以看出，在多处理器环境下，哪一步的代价比较大了。填充缓存的代价当然还是很高，但我们还需要留意RFO消息。一旦涉及RFO，操作就快不起来了。
RFO在两种情况下是必需的:
- 线程从一个处理器迁移到另一个处理器，需要将所有缓存线移到新处理器。
- 某条缓存线确实需要被两个处理器使用。{对于同一处理器的两个核心，也有同样的情况，只是代价稍低。RFO消息可能会被发送多次。}
缓存一致性协议的消息必须发给系统中所有处理器。只有当协议确定已经给过所有处理器响应机会之后，才能进行状态跃迁。也就是说，协议的速度取决于最长响应时间。
对同步来说，有限的带宽严重地制约着并发度。程序需要更加谨慎的设计，将不同处理器访问同一块内存的机会降到最低。