第 1 章 计算机系统漫游

#include <stdio.h>

int main()
{
	printf ( "Hello, world\n") ;
	return 0;
}

• 尽管hello程序非常简单，但是为了它的运行，系统的每个主要组成部分需要协调工作，本书就是了解在系统执行hello程序时，系统发生了什么以及问什么会这样。
• 本章就是通过跟踪hello程序的生命周期来开始对系统进行学习——从它开始被程序员创建开始，到在系统上运行，输出简单的消息，然后终止的过程。

1.1 信息就是位 + 上下文

• 源程序实际上就是一个由值0和1组成的位（又称为比特）序列，8个位被组织成一组，称为字节（表示程序中的文本字符）。程序是以字节序列的方式存储在文件中的，每个字节都有一个整数值，对应于某些字符，每个文本行都是以一个看不见的换行符’\n‘来结束。只由ASCII字符构成的文件称为文本文件，所有其他文件都称为二进制文件。
• 系统中的所有信息———包括磁盘文件、内存中的程序、内存中存放的用户数据以及网络上传送的数据，都是由一串比特表示。区分不同的数据对象的唯一方法就是读到这些数据对象时的上下文。

1.2 程序被其他程序翻译成不同的格式

• 程序为了能够在系统上运行必须转化为一系列的低级机器语言指令，然后这些指令按照一种称为可执行目标程序的格式打包，并以二进制磁盘文件的形式存放起来。目标程序也称为可执行目标文件。
• Unix系统，从源文件到目标文件的转化是由编译器驱动程序完成：

  linux> gcc -o hello hello.c
  

  • 在这里，GCC编译器驱动程序将hello程序翻译成一个可执行的目标文件hello。由以下四个阶段完成
    
    1）、预处理阶段： 预处理器会根据以#开头的代码，来修改原始程序。
    2）、编译阶段：编译器翻译文本文件，包含一个汇编语言程序。其中编译这一阶段包括词法分析、语法分析、语义分析、中间代码生成以及优化等等一系列的中间操作。
    3）、汇编阶段：汇编器（as）将编译阶段的文本文件翻译成机器语言指令，将这些指令打包成可重定位目标程序的格式，并保存在目标文件hello.o中。
    4）、链接阶段：连接器（ld）负责处理合并标准C库中的函数合并，比如printf函数。结果得到一个可执行的目标文件，被加载到内存中由系统执行。

1.3 了解编译系统如何工作是大有益处

• 优化程序性能
• 理解链接时出现的错误
• 避免俺去安全漏洞

1.4 处理器读并解释存储在内存中的指令

• 1.4.1 系统的硬件组成
  
• 总线
  • 贯穿整个系统的一组电子管道，它携带信息字节并负责在各个部件间传递。现在大多数机器的字长4个字节（32位）或8个字节（64位）.
• I/O设备
  • 是系统与外界联系的通道。通过一个控制器或适配器与I/O总线相连。控制器和适配器的区别主要在于它们的封装方式。控制器是I/O设备本身或者系统的主印刷电路板（主板）上的芯片组。而适配器则是一块插在主板插槽上的卡。两者的功能都是在I/O总线和I/O设备之间传递信息。
• 主存
  • 是一个临时设备，用来存放程序和程序处理的数据。从物理上讲，内存是由动态随机存取存储器（DRAM）芯片组成；从逻辑上讲，内存可以看成一个从零开始的大数组，每个字节都有相应地址。
• 处理器
  • 中央处理单元（CPU，简称处理器），是解释或执行主存中指令的引擎。处理器的核心是一个大小为一个字的存储设备（或寄存器），也就是程序计数器（PC）。
    CPU指令可能执行的操作：加载、存储、操作、跳转。
• 1.4.2 运行hello程序
  • 1）通过键盘输入"./hello" 的字符串，shell 程序会将输入的字符逐一读入寄存器，处理器会把 hello 这个字符串放入内存中。
  • 2）然后执行一系列的指令来来加载可执行文件 hello ，这些指令将 hello 中的数据和代码从磁盘复制到内存。
    
  • 3）CPU会将 “hello , world\n” 这个字符串从内存复制到寄存器文件。然后再从寄存器文件复制到显示设备，最终hello , world显示在屏幕上。
    

1.5 高速缓存至关重要

• 通常情况下，大容量的存储设备的存取速度要比小容量的慢，运行速度更快的设备的价格相对于低速设备要更贵。例如：在一个系统上，磁盘的容量一般为 TB 级，内存的容量一般为 GB 级，磁盘的容量大概是内存的 1000 倍。
• 对于处理器而言，从磁盘上读取一个字所花费的时间开销比从内存中读取的开销大1000万倍。寄存器文件的只能存储几百个字节的信息，而内存的可以存放几十亿的字节信息（GB级），从寄存器文件读取数据比从内存读取差不多要快 100 倍。
• 针对处理器和内存之间的差异，系统设计人员在寄存器文件和内存之间引入了高速缓存（cache），处理能力比较强的处理器，一般有三级高速缓存，分别为 L1 cache ， L2 cache 以及L3 cache。
• L1 cache 的访问速度与访问寄存器文件几乎一样快，容量大小为数万字节（KB 级别）；L2 cache 的访问速度是 L1 cache 的五分之一，容量大小为数十万到数百万字节之间；L3 cache 的容量更大，同样访问速度与 L2 cache 相比也更慢。
  

1.6 存储设备形成层次结构

• 从这个层次结构来看，从上到下，设备的访问速度越来越慢，容量越来越大，每字节的造价也越来越便宜。这个层次结构的主要思想就是：上一层存储设备是下一层存储设备的高速缓存。例如，寄存器文件就是 L1 的高速缓存，L1 是 L2 的高速缓存，内存是磁盘的高速缓存等等。

1.7 操作系统管理硬件

• 可以把操作系统看成是应用程序和硬件之间插入的一层软件。
  

• 操作系统的两个基本功能：（1）防止硬件被失控的应用程序滥用；（2）向应用程序提供简单一致的的机制来控制复杂而又通常大不相同的低级硬件设备。主要通过进程、虚拟内存、文件来实现这两个功能。

• 文件是对I/O设备的抽象表示，虚拟内存是对主存和磁盘I/O设备的抽象表示，进程则是对处理器、主存和I/O设备的抽象表示。
  

• 1.7.1 进程

  • 进程是操作系统对一个正在运行的程序的一种抽象。在一个系统上可以同时运行多个进程，而每个进程就好像独占地使用硬件。
  • 并发运行是指一个进程的指令与另一个进程的指令是交错执行。
  • 无论实在单核还是多核系统，，一个CPU看上去都像是在并发的执行多个进程，这是通过处理器在进程间来回切换的。操作系统的这种机制叫做上下文切换。
  • 进程的上下文切换

• 1.7.2 线程

  • 一个进程实际上由多个线程的执行单元组成，每个线程都运行在进程的上下文中，并共享同样的代码和全局的数据，线程一般比进程更高效。

• 1.7.3 虚拟内存

  • 虚拟内存是一个抽象的概念，，它为每个进程提供了一种抽象，即每个进程独占的使用主存。每个进程看到的内存地址是一致的，称为虚拟地址空间。
    
  • 逐步向上介绍
    

• 1.7.4 文件

  • 文件就是字节序列，包括每个I/O设备、键盘、显示器，甚至网络都可以看成是文件。系统中所有的输入输出都是通过使用一小组称为Unix I/O的系统函数调用读写文件来实现的。

1.8 系统之间利用网络通信

1.9 重要主题

• 1.9.1 Amdahl 定律

  Amdahl 定律（也叫阿姆达尔定律）的主要思想是：当我们对系统的某个部分加速时，
  其对系统整体性能的影响取决于该部分的重要性和加速程度。
  

  • 若系统执行某应用程序需要的时间为T_old。假设系统某部分所需执行时间与该时间的比例为α，而该部分性能提升为k。即该部分初始所需时间为αT_old，现在所需时间为(αT_old)/k。因此，总的执行时间应为：
    
  • 例题：
    
    

• 1.9.2 并发和并行

  • 并发指一个同时具有多个活动的系统，并行指的是用并发来使一个系统运行得更快。
  • 1、线程级并发

    • 使用线程可以在一个进程中执行多个控制流。

    • 当构建一个由单操作系统内核控制的多处理器组成的系统时，我们就得到了一个多处理器系统
      

    • 多核处理器将多个CPU（核）集成到一个电路芯片上。
      

    • 超线程也称为同时多线程，是一项允许一个CPU执行多个控制流的技术。

  • 2、指令级并行
    • 可以同时执行多条指令
    • 如果处理器可以达到比一个周期一条指令更快的执行效率，就称之为超标量（super-scalar）处理器。大多数现代处理器都支持超标量操作。
  • 3、单指令、多数据并行
    • 允许一条指令产生多个可以并行执行的操作，这种方式称为单指令、多数据，即是SIMD并行

• 1.9.3 计算机系统中抽象的重要性

  • 在处理器里，指令集架构提供了对实际处理器硬件的抽象。使用这个抽象，机器代码程序表现得就好像运行在一个一次只执行一条指令的处理器上。
  • 文件是对I/O设备的抽象表示，虚拟内存是对主存和磁盘I/O设备的抽象表示，进程则是对一个正在运行的程序的抽象表示。虚拟机提供对整个计算机的抽象。

第 2 章 信息的表示和处理

2.1 信息存储

• 通常情况下，程序将内存视为一个非常大的数组，数组的元素是由一个个的字节组成，每个字节都由一个唯一的数字来表示，我们称为地址（address），这些所有的地址的集合就称为虚拟地址空间（virtual address space）。
• 一个字节是由8个位（bit）组成，在二进制表示法中，每一个位的值可能有两种状态：0或者1。当这8个位全为0时，表示一个字节的最小值；当这8个位全为1时，表示最大值。如果用十进制来表示，那么一个字节的取值范围就在0~255(包含0和255）之间。
• 2.1.1 十六进制表示
  
• 2.1.2 字数据大小
  • 每台计算机都有一个字长，指明指针数据的标称大小。字长决定了虚拟地址空间的最大大小。即，对于一个字长为w位的机器而言，虚拟地址的范围为0~2^w - 1，程序最多访问2^w。
  • C语言中，支持整数和浮点数多种数据格式，如图列式了不同数据类型在32位机器与64位机器上所占字节数的大小。
    
• 2.1.3 寻址和字节顺序
  • 例如：一个int类型的变量 x（0x01234567），假设地址位于0x100处，由于int类型占4个字节，因此变量x被存储在地址为 0x100,0x101,0x102,0x103 的内存处。
  • 内存中有两种方式存储对象：大端法（最高有效字节在最前面）、小端法（最低有效字节在最前面）
    
• 2.1.4 表示字符串
  • C语言中的字符串被编码为以NULL（其值为0）字符结尾的字符数组，例如字符串 “abcde" ，这个字符串虽然只有5个字符，但是长度却为6，就是因为结尾字符的存在。
    
• 2.1.5 表示代码
• 2.1.6 布尔代数简介
  
  • 详情参考离散数学中的介绍： http://www.vue5.com/discrete_mathematics/boolean_expressions_functions.html
• 2.1.7 C语言中的位级运算
  • 事实上，我们在布尔运算中使用的那些符号就是C语言所使用的：|就是OR（或），&就是AND（与），~就是NOT（取反），^就是EXCLUSIVE-OR（异或）。
    
• 2.1.8 C语言中的逻辑运算
  • C语言中的逻辑运算有：||、&&、！，分别对应命题逻辑中的OR、AND、NOT运算。但是逻辑运算认为所有非零的参数都表示TRUE，而参数0表示FALSE，返回1或者0。
    
• 2.1.9 C语言中的移位运算
  • 逻辑左移、逻辑右移；算数左移、算数右移
  • 算术左移和逻辑左移一样都是右边补0
  • 逻辑右移很简单，只要将二进制数整体右移，左边补0即可
  • 算术右移符号位要一起移动，并且在左边补上符号位，也就是如果符号位是1就补1符号位是0就补0
    

  斜体的数字表示移位填充的值
  

  • C语言没有明确规定使用移位过程中是逻辑右移还是算术右移，但是几乎所有的编译器/机器组合都对有符号数使用算术右移。
  • 与C相比，Java对于如何进行右移有明确的定义。表达式x>>k会将x算术右移k位，而x>>>k会对x做逻辑右移。
  • 如果移位量很大的话，可以直接采用公式kmodw计算实际的位移量（w是数据类型的位数，k为移位量）。

2.2 整数表示

• 2.2.1 整型数据类型
  • C语言支持多种整型数据类型——表示有限范围的整数，如下图所示：
    
    
    
• 2.2.2 无符号数的编码
  

  • 例如：
    

  • 原理：无符号数编码的唯一性

  • 函数B2U_w是一个双射。即，反过来，我们称其为U2B_w（无符号数到二进制）。

• 2.2.3 补码编码
  
  • 例如：
    
  • 原理：补码编码的唯一性
  • 函数B2T_w是一个双射。函数T2B_w（补码到二进制）作为B2T_w的反函数。
• 2.2.4 有符号数与无符号数之间的转换
  • C语言允许在各种不同的数字数据类型之间做强制类型转换。表达式（unsigned）x会将x的值转换成一个无符号数值，(int)x会将x装换成一个有符号数值。
    
  • 例如：
    
  • 在上图中可以看到T2U₁₆（-12345）= -12345 + 2¹⁶，同时T2U_w（-1） = -1 + 2^w = UMax_w。
    
• 2.2.5 C语言中的有符号数与无符号数
• 2.2.6 扩展一个数字的位表示
  
  
• 2.2.7 截断数字
  
  

2.3 整数运算

• 2.3.1 无符号加法
  
• 2.3.2 补码加法
  
• 2.3.3 补码的非
  
  • 对于w位的补码来说，TMin_w是自己加法的逆，而对其他任何数值x都要-x作为其加法的逆。
  • 补码非的位级表示
    在C语言中，对于任意整数，计算表达式-x和~x+1得到的结果完全一样。
    下面是一些示例，字长为4：
    
• 2.3.4 无符号乘法
  • 在范围0≤x,y≤2^w - 1内的整数相乘的取值范围为0到（2^w - 1）² = 2^w - 2^w+1 之间。
  • 将一个无符号数截断为w位等价于计算该值模2^w，得到：
    
• 2.3.5 补码乘法
  • 在范围-2^w-1 ≤x,y≤2^w-1 - 1内的整数相乘的取值范围为-2^w-1 · (2^w-1 - 1）=-2^2w-2 +2^w-1到 - 2^w-1 · - 2^w-1 = - 2^2w-2之间。
  • 将一个补码数截断为w位等价于计算该值模2^w，得到：
    
  • 示例：
    
• 2.3.6 乘以常数
  • 由于乘法指令的执行需要多个时钟周期，很多C语言的编译器试图用移位、加法以及减法来代替整数乘法的操作。
  • 首先我们看一下乘以2的幂的情况。x乘以2，对应于左移一位；x乘以4，对应于左移两位；x乘以2的k次方，就对应左移k位。
  • 例如：x乘以14，14的二进制表示如图所示。
    
• 2.3.7 除以2的幂
  • 对于除以2的幂也可以用移位来实现，不过除法的移位采用的是右移，而不是左移。
  • 除以2的幂无符号数除法
    
    
  • 示例：
    
    
  • 示例：
    

2.4 浮点数

• 2.4.1 二进制小数
  
  • 二进制小数示例：
    
• 2.4.2 IEEE浮点表示

  • V = (-1)^s x M x 2^e

  • 这个表达式，涉及三个变量：符号s、阶码E和尾数M。

  • 采用移码表示阶码E ，将浮点数的指数真值e变成阶码E时，
    应将指数e加上一个固定的偏移值127(01111111)，即
    E=e+127。

  • 一个规格化的32位浮点数x的真值表示为
    x=(-1)^S×(1.M)×2^E-127
    e=E-127

  • 规格化的64位浮点数x的真值为：
    x=(-1)^s×(1.M)×2^E-1023
    e=E-1023

  • IEEE754标准(规定了浮点数的表示格式,运算规则等)
    规则规定了单精度(32)和双精度(64)的基本格式。
    规则中,尾数用原码,指数用移码(便于对阶和比较)

    • 例如C语言中float类型的变量占4个字节，32个比特位，这32个比特位被划分成3个字段来解释，具体表示如图所示。
      
    • 对于64位双精度浮点数，其二进制位与浮点数的关系如图所示。
      

  • 例题：
    
    

  • 格式化的值
    当表示规格化的值时，其中阶码字段的取值范围如图所示。
    

  • 非规格化的值
    当阶码字段的二进制位全为0时，所表示的是非规格化的值，关于非规格化的数有两个用途：
    一是提供了表示数值0的方法，当符号位s等于0，阶码字段全为0，小数字段也全为0时，此时表示正零。当符号位s等于1，阶码字段全为0，小数字段也全为0时，此时表示负零。根据IEEE的浮点规则，正零和负零在某些方面被认为不同，而其他方面是相同的。

  • 特殊值
    最后一类数值是当指阶码全为1的时候出现的。当小数域全为0时，得到的值表达无穷，当s=0时是+∞，当s=1时是-∞。

• 2.4.3 数字示例
  
• 2.4.4 舍入
  • 对于值x，可能无法用浮点形式来精确的表示，因此我们希望可以找到“最接近的值 x’ 来代替x，这就是舍入操作的任务。
  • IEEE浮点格式定义了四种不同的舍人方式，分别是：向偶数舍入、向零舍入、向下舍入以及向上舍入。
    
• 2.4.5 浮点运算
  • 列如图中的两个表达式，其中表达式1的计算结果等于0.0，而表达式二的计算结果等于3.14。
    
  • 这是由于表达式1在计算3.14与1e10相加时，对结果进行了舍入，值3.14会丢失，因此，对于浮点数的加法是不具有结合性的。
  • 同样由于计算结果可能发生溢出，或者由于舍人而失去精度，导致浮点数的乘法也不具有结合性。同样也不具备分配性。
    
• 2.4.6 C语言中的浮点数
  • C语言提供了两种不同的浮点数据类型：单精度float类型和双精度double类型。当int，float、double不同数据类型之间进行强制类型转换时，得到的结果可能会超出我们的预期。

第 3 章 程序的机器级表示

3.1 历史观点

3.2 程序编码

• 假设有个C程序，有两个文件p1.c和p2.c。我们用Unix命令行编译这些代码：

  linux> gcc -Og -o p p1.c p2.c
  

  其中gcc指的就是GCC编译器，它是linux系统上默认的编译器，其中编译选项-Og是用来告诉编译器生成符合原始C代码整体结 构的机器代码。在实际项目中，为了获得更高的性能，会使用-01或者-02，甚至更高的编译优化选项。但是使用高级别的优化产生的代码会严重变形，导致产生的机器代码与最初的源代码之间的关系难以理解，这里为了理解方便，因此选择-Og这个优化选项。
  -o后面跟的参数p表示生成可执行文件的文件名。
• 3.2.1 机器级代码
  • 两种抽象： 1、有指令集体系机构或指令集架构来定义机器级程序的格式和行为；2、机器级程序使用的内存地址是虚拟地址。
  • x86-64的机器代码和原始的C代码差别非常大。一些通常对C语言程序员隐藏的处理状态都是可见的：
    1、程序计数器（称为“PC”，在x86-64中用%rip表示）给出将要执行的下一条指令在内存中的地址。
    2、整数寄存器文件包含16个命名位置，分别存储64位的值。
    3、条件码寄存器保存着最近执行的算术或逻辑指令的状态信息。
    4、一组向量寄存器可以存放一个或多个整数或浮点数值。
• 3.2.2 代码示例
  • 假设一个C语言代码文件mstore.c，如下所示：
    
  • 使用以下命令可以生成对应的汇编文件mstore.s：

  	linux> gcc -Og -S mstore.c
  

  • 汇编代码文件包含各种声明，包括下面几行：
    
  • 使用以下命令可以生成对应的汇编文件mstore.o：

  	linux> gcc -Og -c mstore.c
  

  • 这就是产生目标代码文件mstore.o，它是二进制格式，无法直接查看。机器执行的程序只是一个字节序列，它是对一系列指令的编码。
  • 要查看机器代码文件的内容，有一类称为反汇编器的程序非常有用。这些程序根据机器代码产生一种类似于汇编代码的格式。使用以下命令行可以实现：

  linux> objdump -d mstore.o
  

  • 结果如下：
    
• 3.2.3 关于格式的注解

• 首先以源文件mstore.c为例，看一下C代码与汇编代码之间的关系，使用以下命令可以生成对应的汇编文件mstore.s：

linux> gcc -Og -S mstore.c

• 其中以.开头的行都是指导汇编器和链接器工作的伪指令，也就是说我们完全可以忽略这些以.开头的行，删除了无关的信息之后，剩余这些汇编代码与源文件中C代码是相关的。

3.3 数据格式

3.4 访问信息

• 一个x86-64的中央处理单元（CPU）包含一组16个存储64位值的通用目的寄存器。这些寄存器用来存储整数数据和指针。
• 如图所示：
  
• 3.4.1 寻址方式
  
• 3.4.2 数据传送指令
  
  • 下面的MOV指令示例给出了源和目的类型的五种可能的组合。第一个是源操作数，第二个是目的操作数：
    
    
    
• 3.4.3 数据传送示例
  
  
• 3.4.4 压入和弹出栈数据
  • 栈在处理数据的过程中遵循“后进先出”的原则。栈向下增长，这样一来，栈顶元素的地址是所有栈中元素地址最低的。栈指针%rsp保存着栈顶元素的地址。
    

3.5 算数和逻辑操作

• 3.5.1 加载有效地址
  • 加载有效地址指令leap实际上是movq指令的变形。它的指令形式是从内存读数据到寄存器，但实际上它根本没有引用内存。例如，如果寄存器%rdx的值为x，那么指令leap7(%rdx,%rdx,4),%rax 将设置寄存器%rax的值为7 + x + 4x = 5x + 7。
  • 看下面的C程序：
    
  • 编译时产生的汇编代码如下：
    
• 3.5.2 一元和二元操作
  • 一元操作只有一个操作数，既是源又是目的。
  • 二元操作，源操作数是第一个，目的操作数是第二个。
• 3.5.3 移位操作
  • 移位量可以是立即数。x86-64中，移位操作对w位长的数据值进行操作，移位量是由%cl寄存器的低m位决定的。
    -3.5.5 特殊的算术操作
  • 下图描述的是支持产生两个64位数字的全128位乘积以及整数除法的指令。
    
  • 上图中的两条乘法指令都要求一个参数必须在寄存器%rax中，而另一个作为指令的源操作数给出。然后乘积存放在寄存器%rax(高64位)和%rax(低64位)中。
  • 有符号除法指令idivl将寄存器%rdx(高64位)和%rax(低64位)中的128位数作为被除数，而除数作为指令的操作数给出。指令将商存储在寄存器%rax中，将余数存储在寄存器%rdx中。
  • 除数常常是一个64位的值，这个值应该存放在%rax中，%rdx的位应该设置为全0（无符号运算）或者%rax的符号位（有符号运算）。后面的操作可以用指令cqto来完成，这条指令不需要任何操作数-----它隐含读出%rax的符号位，并将它复制到%rdx的所有位。
  • 乘法运算例子：
    C代码
    
    汇编代码
    

3.6 控制

• 3.6.1 条件码
  • CPU还维护一组单个位的条件码。可以检测这些寄存器来执行条件分支指令。最常用的条件码有：
    
    
• 3.6.2 访问条件码
  • 条件码通常不会直接读取，常见的使用方法有三种：
    1）可以根据条件码的某种组合，将一个字节设置为0或者1；
    2）可以条件跳转到程序的某个其他的部分；
    3）可以有条件的传送数据。
  • 一条set指令的目的操作数是低位单字节寄存器元素之一，或是一个字节的内存位置，指令会将这个字节设置成0或者1.一个计算C语言表达式a<b的典型指令序列如下所示，这里的a和b都是long类型：
    
• 3.6.3 跳转指令
  • 无条件跳转指令jmp
    
• 3.6.4 跳转指令的编码
  
  • 汇编器产生的“.o”格式的反汇编版本如下：
    
  • 这例子说明，当执行PC相对寻址时，程序计数器的值是跳转指令后面的那条指令的地址，而不是跳转指令本身的地址。
• 3.6.5 用条件控制实现条件分支
  
• 3.6.6 用条件传送来实现条件分支
  
  • 基于条件传送数据的代码会比基于条件控制转移的代码性能要好。这里涉及到现代处理器通过流水线来获得高性能。当遇到条件跳转时，处理器会根据分支预测器来猜测每条跳转指令是否执行，当发生错误预测时，会浪费大量的时间，导致程序性能严重下降。
  • 下图列举了x86-64上一些可用的条件传送指令。每条指令都有两个操作数：源寄存器或者内存地址S，和目的寄存器R。
    
• 3.6.7 循环
  • 1.do-while循环
    
    示例：
    
  • 2.while循环
    
  • 3.for循环
    
• 3.6.8 switch 语句
  • switch语句可以根据一个整数索引值进行多重分支。在处理具有多种可能结果的测试时，这种语句特别有用。不仅提高代码的可读性，而且通过使用跳转表这种数据结构使得实现更加高效。跳转表是一个数组。与很长的if-else语句相比，跳转表的优点是执行开关语句的时间与开关状况的数量无关。

3.7 过程

• 过程形式多样：函数、方法、子例程、处理函数等等。
• 假设过程P调用过程Q，Q执行后返回到P。这些动作包括下面一个或多个机制：
  传递控制：设置PC的起始地址。
  传递数据：P向Q传递参数，Q向P返回值。
  分配和释放内存：调用Q分配内存，返回前，释放内存。
• 3.7.1 运行时栈
  • 程序可以用栈来管理它的过程所需要的存储空间，栈和程序寄存器存放着传递控制的数据、分配内存所需的信息。
  • x86-64的栈向低地址方向增长，而栈指针%rsp指向栈顶元素。
    
• 3.7.2 转移控制
  
  • call指令相当于C语言中的函数调用
• 3.7.3 数据传送
  • x86-64中，可以通过寄存器最多传递6个整型参数。寄存器的使用是有特殊顺序的，寄存器使用的名字取决于要传递的数据类型的大小，如下图所示，会根据参数在参数列表中的顺序为它们分配寄存器。
    
  • 如果有一个函数参数超过6个，超出6个的部分就要通过栈来传递。
• 3.7.4 栈上的局部存储
  • 局部数据必须存放在内存中，常见的情况包括：
    寄存器不足存放所有本地数据。
    对一个局部变量使用地址运算符‘&’，因此必须能够为它产生一个地址。
    某些局部变量是数组或结构，因此必须通过数组或结构引用被访问到。
• 3.7.5 寄存器中的局部存储空间
  • 为了防止被调用者会覆盖使用的寄存器的值，x86-64采用了统一的寄存器使用惯例。
  • 根据惯例，寄存器%rbx、%rbp和%r12~%r15被划分为被调用者保存寄存器。P调用Q，Q保存这些寄存器的值不变。
  • 所有其他的寄存器，除了栈指针%rsp，都分类为调用者保存寄存器。这意味着任何函数都能修改它们，所以P在调用过程Q时，必须好这些寄存器的值不被改变。
• 3.7.6 递归过程
  

3.8 数组分配和访问

• 3.8.1 基本原则
  • 对于数据类型T和整型常数N，声明如下：
    T A[N];
    起始位置表示为x_A。这个声明有两个效果。首先，它在内存分配了L·N字节的连续区域，这里L是数据类型T的大小（单位为字节）。其次，引入了标识符A。
    示例：
    
    这些声明会产生带下列参数的数组：
    
• 3.8.2 指针运算
  • 单操作数操作符‘&’和‘*’可以产生指针和间接引用指针。
  • 如下表例子
    
• 3.8.3 嵌套数组
  • 声明 int A[5][3]等价于下面的声明
    
    
  • 声明如下数组：
    T D[R][C];
    它的数组元素D[i][j]的内存地址为： &D[i][j] = x_D + L(C · i + j)
• 定长数组
  • 假设如下声明一个定长数组：
    
• 3.8.5 变长数组
  • 程序员需要变长数组时不得不用malloc或calloc这样的函数为这些数组分配存储空间。在变长数组的C版本中，我们可以将一个数组声明如下：
    
  • 它可以作为一个局部变量，也可作为一个函数参数，通过对表达式expr和expr2求值来确定数组的维度。例如要访问n×n数组的元素i,j，我们可以写一个如下函数：
    
    GCC为这个引用函数产生的代码如下所示：
    

3.9 异质的数据结构

• 结构，用关键字struct来声明，将对各对象集合到一个单位中；联合，用关键字union来声明，允许用几种不同的类型来引用一个对象。
• 3.9.1 结构
  • 考虑下面这样的结构声明：
    
    这个结构包括四个字段：两个4字节int、一个由两个类型为int的元素组成的数组和一个8字节整型指针，总共是24个字节：
    
• 3.9.2 联合
  • 联合提供了一种方式，能够规避C语言的类型系统，允许以多种类型来引用一个对象。联合与结构声明语法一样，但语义相差比较大。它们是用不同的字段来引用相同的内存块》
  • 考虑下面的声明：
    
  • 在一台x86-64Linux机器上编译时，字段的偏移量、数据类型S3和U3的完整大小如下：
    
    联合体中的所有字段共享同一存储区域，因此联合体的大小取决于它最大字段的大小。
• 3.9.3 数据对齐
  • 无论数据是否对齐，x86-64硬件都能正确工作。不过，Intel还是建议要对齐数据以提高内存系统的性能。对齐原则是任何K字节的基本对象的地址必须是K的倍数。
    
  • 例如，考虑下面的结构声明：
    
    假设编译器用最小的9字节分配，画出来的图是这样的：
    
    显然这样的分配是不符合对齐原则的。取而代之地，编译器在字段c和j之间插入一个3字节的间隙：
    
    结果整个结构的大小为12字节，但是保证了对齐原则。
  • 另外，编译器结构的末尾可能需要一些填充，这样结构数组的每个元素都满足对齐要求。例如，如下声明：
    
    编译器会为结构S2分配12字节，最后3个字节是浪费的空间：
    

3.10 在机器级程序中将控制与数据结合起来

• 3.10.1 理解指针
  • 每个指针都对应一个类型
    这个类型表明该指针指向的是哪一类对象。例如：
    
    变量ip是一个指向int类型对象的指针，而cpp指针指向的对象自身就是一个指向char类型对象的指针。通常，如果对象类型为T，那么指针类型为T *。特殊的void * 类型代表通用指针。
  • 每个指针都有一个值
    这个值是某个指定类型的对象的地址。特殊的NULL(0)值表示该指针没有指向任何地方。
  • 指针用‘&’运算符创建
    &运算符额机器代码实现常常用这条指令来计算表达式的值。
  • *操作符用于间接引用指针
    其结果是一个值，它的类型与该指针的类型一致。间接引用是用内存引用来实现的，要么是存储到一个指定的地址，要么是从指定的地址读取。
  • 数组与指针紧密联系
    一个数组的名字可以像一个指针变量一样引用（但是不能修改）。例如a[3]与*（a+3）有一样的效果。
  • 将指针从一种类型强制转换成另一种类型，只改变它的类型，而不改变它的值
    强制类型转换的一个效果是改变指针运算的伸缩。例如：p是一个char * 类型的指针，那么表达式（int *）p+7计算为p + 28，而（int *）（p+7）计算为p+7。
  • 指针也可以指向函数
    例如，一个函数用下面的原型定义：
    
    然后，可以声明一个指针fp，将它赋值为这个函数，代码如下：
    
    然后用这个指针来调用函数：
    
    函数指针的值是该函数机器代码表示中的第一条指令的地址。
• 3.10.2 应用：使用GDB调试器
  • 用下面的命令来启动GDB：

  linux> gdb prog
  

  
• 3.10.3 内存越界引用和缓存区溢出
  • 缓冲区溢出，通常，在栈中分配某个字符数组来保存一个字符串，但是字符串的长度超出了为数组分配的空间。
  • 缓冲区溢出的一个致命使用就是让程序执行它本来不愿意执行的函数。通常，输入给程序一个字符串，这个字符串包含一些可执行代码的字节编码，称为攻击代码（exploit code），还有一些字节会用一个指向攻击代码的指针覆盖返回地址。那么ret指令的效果就是跳转到攻击代码。
• 3.10.4 对抗缓冲区溢出攻击
  • 1.栈随机化
    栈随机化的思想使得栈的位置在程序每次执行时都有变化。实现方式：程序开始时，在栈上分配一段0~n字节之间的随机大小的空间。
    在Linux系统中，栈随机化已经变成了标准行为。这类技术称为地址空间随机化，简称ASLR
    一个攻击可以用蛮力克服随机化，反复用不同的地址进行攻击。
    在实际的攻击代码中插入很长的一段nop(读作“no op”,no operating的缩写)指令。执行这种指令除了可以使程序计数器PC加1之外没有任何效果。这个序列用术语是“空操作雪橇（no sled）”，意思是程序会滑过这个序列。
  • 2.栈破坏检测
    计算机的第二道防线是能够检测到何时栈已经被破坏。在C语言中没有可靠的方法来防止对数组的越界写。但是，能够在发生了越界写的时候，在造成任何有害结果之前，尝试检测到它。
    最近的GCC版本在产生的代码中加入了一种栈保护者（stack protector） 机制，来检测缓冲区越界。其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的==金丝雀（canary） ==值，也称为哨兵值（guard value），是在程序每次运行时随机产生的，因此，攻击者没有简单的办法能够知道它是什么。在恢复寄存器状态和从函数返回前，程序检查这个金丝雀的值是否被该函数的某个操作或者该函数调用的某个函数的操作改变。如果是的，则程序中止。
    
  • 2.限制可执行代码区域
    这种方法是限制哪些内存区域能够存放可执行代码。在典型的程序中，只有保存编译器产生的代码的那部分内存才需要是可执行的，其他部分可以限制为只允许读和写。许多系统允许控制三种访问形式：读（从内存读数据）、写（写存储数据到内存）和执行（将内存的内容看作机器级代码）。以前x86体系结构将读和执行访问控制合并成1位的标志，这样任何被标记为可读的页也都是可执行的，栈上的字节也是可执行的。限制一些页可读但是不可执行的机制会带来严重的性能损失。
    AMD为它的64位处理器的内存保护引入了“NX”（No-Execute，不执行）位，将读和执行访问模式分开，Intel也跟进了。有了这个特性，栈可以标记为可读和可写，但是不可执行，而检查页是否可执行由硬件来完成，效率上没有损失。
    上面所讲的技术——随机化、栈保护和限制哪部分内存可以存储可执行代码——是用于最小化程序缓冲区溢出攻击漏洞三种最常见的机制。它们带来额性能代价少、不需要程序员做任何努力，它们组合起来变得更加有效。但是还是仍然有方法攻击计算机 。
• 3.10.5 支持变长栈帧
  • 有些函数，需要的局部存储是变长的。例如标准库函数alloca，可以在栈上分配任意字节数量的存储。
  • 为了管理变长栈帧，x86-64代码使用寄存器%rbp作为帧指针（frame pointer）（有时称为基指针（base pointer），这也是%rbp中bp两个字母的由来）
  • 在较早的x86代码中，每个函数调用都使用了帧指针。而现在，只在栈帧长可变的情况下才使用。

3.11 浮点代码

• 处理器的浮点体系结构包括多个方面，会影响对浮点数据操作的程序如何被映射到机器上，包括：
  • 如何存储和访问浮点数值。通常是通过某种寄存器方式来完成。
  • 对浮点数据操作的指令
  • 向函数传递浮点参数和从函数返回浮点数结果的规则。
  • 函数调用过程中保护寄存器的规则——例如，一些寄存器被指定为被调用者保护，而其他的被指定为被调用者保存。
  • 如下图所示，AVX浮点体系结构允许数据存储正在16个YMM寄存器中，当对标量数据操作时，这些寄存器只保存浮点数，而且只使用低32位或64位。汇编代码用寄存器的SSE XMM寄存器名字%xmm0~%xmm15来引用它们，每个XMM寄存器都是对应YMM寄存器的低128位（16字节）。
    
• 3.11.1 浮点传送和转换操作
  • 如下图给出了一组在内存和XMM寄存器之间以及从一个XMM寄存器到另一个不做任何转换的传送浮点数的指令。
    
  • 下面是一个不同浮点传送操作的例子，考虑以下C函数
    
  • 与之相关的x86-64汇编代码为
    
  • 如下图中的指令从一个XMM寄存器或内存中读出的浮点值进行转换，并将结果写入一个通用寄存器（例如：%rax、%ebx等）。把浮点值转换成整数时，指令会进行截断（truncation），把值向0进行舍入，这是C和大多数其他编程语言的要求。
    
  • 如下图中的指令把整数转换成浮点数。它们使用的是不同常见的三操作数格式，有两个源和一个目的。第一个操作数读自预内存或一个通用目的寄存器。这里可以忽略第二个操作数，因为它的值之后影响结果的高位字节，而我们的目标必须是XMM寄存器。
• 3.11.2 过程中的浮点代码
  • 在x86-64中，XMM寄存器用来向函数传递浮点参数，以及从函数返回浮点值。
  • XMM寄存器%xmm0~%xmm7最多可以传递8个浮点参数，额外的浮点参数通过栈传递。
  • 函数使用寄存器%xmm0来返回浮点值。
  • 所有的XMM寄存器都是调用者保存的。被调用者可以不用保存这些寄存器中任意一个。
  • 当函数包含指针、整数和浮点数混合的参数时，指针和整数通过寄存器传递，而浮点值通过XMM寄存器传递。
  • 例子：
    
• 3.11.3 浮点运算操作
  • 下图描述了一组执行算术运算的标量AVX2浮点指令。每条指令有一个（S1）或两个（S1，S2）源操作数，和一个目的操作数D。第一个源操作数S1可以是一个XMM寄存器或一个内存位置。第二个源操作数和目的操作数都必须是XMM寄存器。每个操作都有一条针对单精度的指令和一条针对双精度的指令，结果存放在目的寄存器中。
    
• 3.11.4 定义和使用浮点常数
  • 和整数运算操作不同，AVX浮点操作不能以立即数值作为操作数。相反，编译器必须为所有的常量值分配和初始化存储空间。然后代码再把这些值从内存读入。
• 3.11.5 在浮点代码中使用位级操作
  
• 3.11.6 浮点比较操作
  • AVX2提供了两条用于比较浮点数值的指令：
    
  • 浮点比较指令会设置三个条件码：零标志位ZF、进位标志位CF和奇偶标志位PF。根据惯例，C语言中如果有个参数为NaN，就认为比较失败了，当x为NaN时，比较x==x都会得到0。条件码的设置条件如下：
    
• 3.11.7 对浮点代码的观察结论
  • 用AVX2为浮点数上的操作产生的机器代码风格类似于为整数上的操作产生的代码风格。它们都使用一组寄存器来保存和操作数据值，也都使用这些寄存器来传递函数参数。同时，AVX2代码包括许多只执行整数运算的函数更加不同的指令和格式，还能在封装好的数据上执行并行操作，使计算执行更快。

第 4 章 处理器体系结构

4.1 Y86-64 指令集体系结构

• 4.1.1 程序员可见的状态
  
• 4.1.2 Y86-64 指令
  下面是Y86-64指令的一些细节
  • x86-64的movq指令分成了4个不同的指令：irmovq、rrmovq、mrmovq和rmmovq，分别显示地指明源和目的的格式。源可以是立即数（i）、寄存器（r）或内存（m）。
    
    
• 4.1.3 指令编码
  • 指令的字节级编码，每条指令的第一个字节表明指令的类型。这个字节分为两个部分，每部分4位：== 高4位是代码部分，低4位是功能部分==。如上图所示，代码值为0~0xB。功能值只有在一组相关指令共用一个代码时才有用。图4-3给出了整数操作、分支和条件传送指令的具体编码。
    
  • 如图4-4所示，15个程序寄存器中每个都有一个相对应的范围在0到0xE之间的寄存器标识符（register ID）。Y86-64中的寄存器编号跟x86-64中的相同。
    
• 4.1.4 Y86-64 异常
  
• 4.1.5 Y86-64 程序
  • 图4-6 给出了下面这个C函数的x86-64和Y86-64汇编代码：
    
    
  • x86-64 代码是由GCC编译器产生的。Y86-64 代码与之类似，但有以下不同点：
    • Y86-64 将常数加载到寄存器，因为它在算术指令中不能使用立即数。
    • 要实现从内存读取一个数值并将其与一个寄存器相加，Y86-64代码需要两条指令，而x86-64只需要一条addq指令。
    • 我们手工编写的Y86-64实现有一个优势，即subq指令同时还设置了条件码，因此GCC生成代码中的testq指令就不是必须的。不过为此，Y86-64 代码必须用addq指令在进入循环之前设置条件码。
• 4.1.6 一些Y86-64 指令的详情
  • 大多数Y86-64 指令是以一种直接明了的方式修改程序状态的，不过，两个特别的指令组合需要特别注意一些。
  • pushq指令会把栈指针减去8，并且将一个寄存器值写入内存中。因此当执行pushq%rsp指令时，处理器的行为是不确定的。通常有两种不同的约定：1）压入%rsp的原始值，2）压入减去8的%rsp的值。

4.2 逻辑设计和硬件控制语言HCL

• 4.2.1 逻辑门
  
• 4.2.2 组合电路的HCL布尔表达式
  • 将很多的逻辑门组合成一个网，就能构建计算块，称为组合电路。构建这些网友以下限制：
    • 每个逻辑门的输入必须连接到下述选项之一：1）一个系统输入（称为主输入），2）某个存储单元的输出，3）某个逻辑门的输出。
    • 两个或多个逻辑门的输出不能连接在一起。否则它们可能会使线上的信号矛盾，可能会导致一个不合法的电压或电路故障。
    • 这个网必须是无环的。也就是在网中不能形成一个回路。
  • 图4-10用HCL来写这个网的函数就是：
    bool eq = (a && b) || (!a && !b);
    
    
  • 图4-11的组合电路称为==多路复用器（multiplexor，通常称为“”MUX）。HCL表达式为：
    bool out = (s && a) || (!s && b);
  • HCL 表达式与C语言中的逻辑表达式有以下区别：
    
• 4.2.3 字级的组合电路和HCL整数表达式
  • 执行字级计算的组合电路根据输入字的各个位，用逻辑门来计算出字的各个位。例如下图中的一个组合电路，它测试两个64位字A和B是否相等。也就是，当且仅当A的每一位都和B的相应位相等时，输出才为1。
    
  • 在上图中右边所示，在画字级电路的时候，我们用中等粗度的线来表示携带字的每个位的线路，而用虚线来表示布尔信号结果。
  • 图4-13是字级的多路复用器电路。这个电路根据控制输入位s，产生一个64位的字Out，等于两个输入字A或者B中的一个。这个电路由64个相同的子电路组成，每个子电路的结构类似图4-11中的位级多路复用器。不过这个字级的电路并没有简单地复制64次位级多路复用器，它只产生一次!s，然后再每个位的地方都重复使用它，从而减少反相器或非门（inverters）的数量。
  • 在HCL中，多路复用函数是用情况表达式来描述的。情况表达式的通用格式如下：
    
    
  • 同C的switch语句不同，我们不要求不同的选择表达式之间互斥。允许不互斥的选择表达式使得HCL代码的可读性更好。实际的硬件多路复用器的信号必须互斥，它们要控制哪个输入字应该被传送到输出，就像图4-13中的信号s和!s。例如，图4-14中所示的四路复用器的图。这个电路根据控制信号s1和s0，从四个输入字A、B、C和D中选择一个，将控制信号看作一个两位的二进制数。我们可以用HCL来表示这个电路，用布尔表达式描述控制位模式的不同组合：
  • word Out4 = [
    !s1 && !s0 : A; #00
    !s1 : B; #01
    !s0 : C; #10
    1 : D; #11
    ]
    
  • 最后一个例子，假设想设计一个逻辑电路来找一组字A、B和C中最小值，如下图所示：
    
  • 用HCL来表达就是：
    
  • **算术/逻辑单元（ALU）**是一种很重要的组合电路。图4-15是它的一个抽象的图示。这个电路有三个输入：标号为A和B的两个数据输入，以及一个控制输入。这个ALU中画的四个操作对应于Y86-64指令集支持的四种不同的整数操作，而控制值和这些操作的功能码相对应（图4-3）。操作数的顺序是输入B减去输入A，这是为了使这个顺序与subq指令的参数顺序一致。
    
• 4.2.4 集合关系
  • 在处理器的设计中，很多时候都需要将一个信号与许多可能匹配的信号做比较，以此来检测正在处理某个指令代码是否属于某一类指令代码。
  • 例子： 假设想从一个两位信号code中选择高位和低位来为图4-14中的四路复用器产生信号s1和s0，
  • 如下图所示：
    
  • 在这个电路中，两位信号code就可以用来控制4个数据字A、B、C和D做选择。根据可能的code值，可以用相等测试来表示信号s1和s0的产生：
    
  • 可以注意到：当code在集合{2,3}中时，s1为1，而code在集合{1,3}中时，s0为1：
  • 因此更简洁的表达式为：
    
    
• 4.2.5 存储器和时钟
  • 组合电路不存储任何信息。只是简单的响应输入，产生等于输入的某个函数的输出。为了产生时序电路，必须引入按位存储信息的设备。存储设备都是由同一个时钟控制的，时钟是一个周期性信号，决定什么时候要把新值加载到设备中。以下两种存储器设备：
    
  • 图4-16更详细的说明了一个硬件寄存器是如何工作的。大多数时候，寄存器都保持在稳定状态（用x表示），产生的输出等于它当前状态。信号沿着寄存器前面的组合逻辑传播，这时，产生了一个新的寄存器输入（用y表示），只要时钟是低电位的，寄存器的输入仍然保持不变。当时钟变成高电位的时候，输入信号就加载到寄存器中，成为下一个状态y，直到下一个时钟上升沿，这个状态就一直是寄存器的新输出。每当每个时钟到达上升沿时，值才会从寄存器的输入传送到输出。Y86-64处理器会用会用时钟寄存器保存程序计数器（PC）、条件码（CC）和程序状态（Stat）。
    
    
    
  • 向寄存器文件写入字是由时钟信号控制的，控制方式类似于将值加载到时钟寄存器。每次时钟上升时，输入valW上的值会被写入输入dstW上的寄存器ID指示的程序寄存器。当dstW设为特殊的ID值0xF时，不会写任何程序寄存器。
    
    

4.3 Y86-64的顺序实现

• 首先，描述一个称为SEQ（“se-quential”顺序的）的处理器。每个时钟周期上，SEQ执行处理一条完整的指令所需的所有步骤。
• 4.3.1 将处理组织成阶段
  • 处理一条指令包括很多操作。将它们组织成某个特殊的阶段序列，下面是关于各个阶段以及各阶段内执行操作的简略描述：
    
    
  • 处理器无限循环，执行这些阶段。在我们简化的实现中，发生任何异常时，处理器就会停止：它执行 halt 指令或非法指令，或它试图读或者写非法地址。在更完整的设计中，处理器会进人异常处理模式，开始执行由异常的类型决定的特殊代码。
  • 从前面的讲述可以看出，执行一条指令是需要进行很多处理的。我们不仅必须执行指令所表明的操作，还必须计算地址、更新栈指针，以及确定下一条指令的地址。幸好每条指令的整个流程都比较相似。因为我们想使硬件数量尽可能少，并且最终将把它映射到一个二维的集成电路芯片的表面，在设计硬件时，一个非常简单而一致的结构是非常重要的。降低复杂度的一种方法是让不同的指令共享尽量多的硬件。
  • 图4-18给出了对OPq（整数和逻辑运算）、rrmovq（寄存器-寄存器传送）和irmovq（立即数-寄存器传送）类型的指令所需的处理。
    
• 4.3.2 SEQ硬件结构
  • 图4-22 给出了一个能执行这些计算的硬件结构的抽象表示。程序计数器放在寄存器中，在图中左下角（标明为“PC”）。然后，信息沿着线流动，先向上，再向右。
    
  • 硬件单元与各个处理阶段相关联：
  • 取指：将程序计数器寄存器作为地址，指令内存读取指令的字节。 PC 增加器（PC incremcntcr ）计算 valP ，即增加了的程序计数器。
  • 译码：寄存器文件有两个读端口 A 和 B , 从这两个端口同时读寄存器值 valA 和 valB。
  • 执行：执行阶段会根据指令的类型，将算术／逻辑单元（ ALU ）用于不同的目的。对整数操作，它要执行指令所指定的运算。对其他指令，它会作为一个加法器来计算增加或减少栈指针，或者计算有效地址，或者只是简单地加 0 ，将一个输人传递到输出。条件码寄存器（ CC ）有三个条件码位。 ALU 负责计算条件码的新值。当执行条件传送指令时，根据条件码和传送条件来计算决定是否更新目标寄存器。同样，当执行一条跳转指令时，会根据条件码和跳转类型来计算分支信号 cnd 。
  • 访存：在执行访存操作时，数据内存读出或写人一个内存字。指令和数据内存访问的是相同的内存位置，但是用于不同的目的。
  • 写回：寄存器文件有两个写端口。端口 E 用来写 ALU 计算出来的值，而端口 M 用来写从数据内存中读出的值。
  • PC 更新：程序计数器的新值选择自： vaIP ，下一条指令的地址； valC ，调用指令或跳转指令指定的目标地址； valM，从内存读取的返回地址。
• 4.3.3 SEQ的时序
  • SEQ的实现包括组合逻辑和两种存储设备：时钟寄存器（程序计数器和条件码寄存器），随机访问存储器（寄存器文件、指令内存和数据内存）。组合逻辑不需要任何时序或控制——只要输入变化了，值就通过逻辑门网络传播。
  • 现在还剩四个硬件单元需要对它们的时序进行明确的控制 ― 程序计数器、条件码寄存器、数据内存和寄存器文件。这些单元通过一个时钟信号来控制，它触发将新值装载到寄存器以及将值写到随机访问存储器。每个时钟周期，程序计数器都会装载新的指令地址。只有在执行整数运算指令时，才会装载条件码寄存器。
  • 处理器从来不需要为了完成一条指令的执行而去读由该指令更新了的状态。
  • 用时钟来控制状态单元，以及值通过组合逻辑来传播，足够控制我们SEQ实现中每条指令执行的计算了。每次时钟由低变高时，处理器开始执行条新的指令。
• 4.3.4 SEQ阶段的实现
  • 图4-26 列出了我们使用的常数。按照习惯，常数值都是大写的。
    
  • 取指阶段
    
  • 译码和写好阶段
    
  • 执行阶段
    
  • 访存阶段
    
  • 更新PC阶段
    

4.4 流水线的通用原理

• 流水线化的一个重要特性就是提高了系统的吞吐量（throughput），也就是单位时间内服务的顾客总数，不过它也会轻微地增加延迟（latency），也就是服务一个用户所需要的时间。
• 4.4.1 计算流水线
  
  • 电路延迟以微微秒或皮秒（picosecond，简写成“ps”），也就是10^-12秒为单位来计算。
    
  • 图4-33 这些方框在垂直方向上并没有相互重叠。下面这个公式给出了运行这个系统的最大吞吐量：
    
  • 以每秒千兆条指令（GIPS），也就是每秒十亿条指令，为单位来描述吞吐量。
• 4.4.2 流水线操作的详细说明
  
  • 图4-34给出了前面我们看到过的三阶段流水线。每隔120ps，信号从0上升至1，开始下一站流水线阶段的计算。
    
  • 图4-35跟踪了时刻240~360之间的电路活动，指令I1经过阶段C，I2经过阶段B，而I3经过阶段A。
• 4.4.3 流水线的局限性
  • 1.不一致的划分
    图 4 - 36 展示的系统中和前面一样，我们将计算划分为了三个阶段，但是通过这些阶段的延迟从 50ps 到 150ps 不等。通过所有阶段的延迟和仍然为 300Ps 。不过，运行时钟的速率是由最慢的阶段的延迟限制的。流水线图表明，每个时钟周期，阶段 A 都会空闲（用白色方框表示） 100ps ，而阶段 C 会空闲 50ps 。只有阶段 B 会一直处于活动状态。我们必须将时钟周期设为 150 十 20 = 170ps ，得到吞吐量为 5.88 GIPS 。
    
  • 2.流水线过深，收益反而下降
    
  • 为了提高时钟频率，现代处理器采用了很深的（ 15 或更多的阶段）流水线。处理器架构师将指令的执行划分成很多非常简单的步骤，这样一来每个阶段的延迟就很小。电路设计者小心地设计流水线寄存器，使其延迟尽可能得小。芯片设计者也必须小心地设计时钟传播网络，以保证时钟在整个芯片上同时改变。所有这些都是设计高速微处理器面临的挑战。
• 4.4.4 带反馈的流水线系统
  • 每对相邻的指令之间都有数据相关，条件控制相关
    
  • 图 4 - 38 举例说明了将流水线引人含有反馈路径的系统中的危险。在原来的系统（图 4 - 38a ) 中，每条指令的结果都反馈给下一条指令。流水线图（图 4 - 38b ）就说明了这个情况， I1 的结果成为 I2 的输人，依此类推。如果试图以最直接的方式将它转换成一个三阶段流水线（图 4 - 38c ) , 我们将改变系统的行为。如图 4 -38c 所示， I1 的结果成为 I4 的输入。为了通过流水线技术加速系统，我们改变了系统的行为。

4.4 Y86-64 的流水线实现

• 4.5.1 SEQ+：重新安排计算阶段

  • 重新调整SEQ五个阶段的顺序，称为“SEQ+”
    
  • SEQ 到 SEQ ＋中对状态单元的改变是一种很通用的改进的例子，这种改进称为电路重定时。重定时改变了一个系统的状态表示，但是并不改变它的逻辑行为。通常用它来平衡一个流水线系统中各个阶段之间的延迟。

• 4.5.2 插入流水线寄存器
  

  • 在SEQ+的各个阶段之间插入流水线寄存器，并对信号重新排列，得到PIPE—处理器，“—”代表这个处理器和最终的处理器设计相比，性能要差一点。PIPE—的抽象结构如图4-41所示
    
    

• 4.5.3 对信号进行重新排列和标号

  • 顺序实现SEQ和SEQ+在一个时刻只处理一条指令，在流水线化的设计中，与各个指令相关联的这些值有多个版本，会随着指令一起流过系统。

• 4.5.4 预测下一个PC

  • 流水线化设计的目的就是每个时钟周期都发射一条新指令，也就是说每个时钟周期都有一条新指令进入执行阶段并最终完成。要做到这一点，我们必须在取出当前指令之后，马上确定下一条指令的位置。不幸的是，如果取出的指令是条件分支指令，要到几个周期后，也就是指令通过执行阶段之后，才能知道是否选择分支。如果取出的指令是ret，要到指令通过访存阶段，才能确定返回地址。
  • 根据取指阶段中计算出的信息，我们能够确定下一条指令的地址。对于call和jmp来说，下一条指令的地址就是指令中的常数valC，其他指令就是valP。因此，通过预测PC的下一个值，在大多数情况下，我们能达到每个时钟周期发射一条新指令的目的。

• 4.5.5 流水线冒险

• 4.5.6 异常处理

• 4.5.7 PIPE各阶段的实现

• 4.5.8 流水线控制逻辑

• 4.5.9 性能分析

• 4.5.10 未完成的工作

第 5 章 优化程序性能

5.1 优化编译器的能力和局限性

• 现代编译器适用复杂的算法来确定一个程序中计算的是什么，以及它们是被如何使用的。然后会利用一些机会来简化表达式，在几个不同的地方使用同一个计算，以降低一个给定的计算必须被执行的次数。大多数编译器，包括GCC，向用户提供了一对它们所使用的优化的控制。
• 最简单的控制就是指定优化级别。例如，以命令行选项“-0g”调用GCC是让CC使用一组基本的优化以选项“-01”或更高(如“-02”或“-03”)调用GCC会让它使用更大量的优化。这样做可以进一步提高程序的性能，但是也可能增加程序的规模，也可能使标准的调试工具更难对程序进行调试。虽然对于大多数使用GCC的软件项目来说，优化级别-o2已经成为了被接受的标准,但是还是主要考虑以优化级别1编译出的代码我们特意限制了优化级别,以展示写C语言函数的不同方法如何影响编译器产生代码的效率。我们会发现可以写出的C代码，即使用-o1选项编译得到的性能，也比用可能的最高的优化等级编译一个更原始的版本得到的性能好。

5.2 表示程序性能

• 我们引人度量标准每元素的用期数(Cycles Per Elenvent,CPE)，作为一种表示程序性能并指导我们改进代码的方法。CPE这种度量标帮助我们在更细节的级别上理解迭代程序的循环性能。这样的度量标准对执行重复计算的程序来说是很适当的，例如处理图像中的像素，或是计算矩乘积中的元素。
• 处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹(GHz)，即十亿周期每秒来表示。例如，当表明一个果统有“4GHz”处理器，这表示处理器时钟运行频率为每秒4×10⁹个周期。每个时钟周期的时间是时钟照率的倒数。通常是以纳秒(nanosecond，1秒等于10^-9秒)或皮秒(picosecond，1皮秒等于10^-12秒)为单位的。例如，一个4GHz的时钟其周期为0.25倍秒，或者250皮秒。从程序的角度来看，用时钟期来表示量标准要比用纳秒或皮秒来表示有帮助得多，时钟周期来表示，度量值表示的是执行了多少条指令，而不是时钟运行得有多快。

5.3 程序示例

• 图5-5中所示的代码，它使用某种运算，将一个向量中所有的元素合并成一个值。通过使用常数IDENT和OP的不同定义，可以执行不同的运算。
• 对向量求和，使用声明如下：
  
• 计算向量元素的乘积，使用声明如下：
  
  
• 为了评估性能变化，我们会在一个具有 Intel Core i7 Haswel处理器的机器上测量这些函数的CPE性能,这个机器称为参考机。这些测量值刻的是程序在某个特定的机器上的性能,所以在其他机器和编译器组合中不保证有同等的性能。
• 下表给出的是 conbinel1的CPE度量值，它运行在我们的参考，上尝试了操作(加法或乘法)和数据类型(长整数和双精度浮点数)的不同组合，使用多个不同的程序,我们的实验显示32位整数操作和64位整数操作有相同的性能，除了涉及除法操作的代码之外。同样，对于操作单精度和双精度浮点数据的程序，其性能也是相同的。因此在表中，我们将只给出整数数据和浮点数据各自的结果。
  
• 未经优化的代码是从C语言代码到机器代码的直接翻译，通常效率明显较低。简单地使用命令行选项“-O1”,就会进行一些基本的优化。正如可以看到的，程序员不需要做什么，就会显著地提高程序性能一一超过两个数量级。通常，养成至少使用这个级别优化的习惯是很好的。

5.4 消除循环的低效率

• 可以观察到，过程 conbine1调用函数 vec_length作为tor循环的测试条件，每次循环选代时都必须对测试条件求值，另一方面向量的长度并不会随看循环的进行改变。因此，只需计算一次向量的长度，然后在我们的测试条件中都使用这个值。
• 图5-6是一个修改了的版本，称为 conbine2，它在开始时调用 vec_length，并将结果赋值给局部变量 length。对于某些数类型和操作，这个变换明显地影响了某些数据类型和操作的整体性能，对于其他的则只有很小甚至没有影响。无论是哪种情况，都需要这种变换来消除这个低效率，这有可能成为尝试进一步优化时的瓶颈。
  
  
• 这种优化称为代码移动（code motion）

5.5 减少过程调用

• 过程调用会带来开销，而且妨碍大多数形式的程序优化。从combine2的代码(见图5-6)中我们可以看出，每次循环代都会调用get_vec_element来获取下一个向量元素。对每个向量引用，这个函数要把向量索引i与循环边界做比较，很明显造成低效率。
• 为抽象数据类型增加一个函数 get_vec_start。这个函数返回数组的起始地址，如图5-9所示。然后就能写出此图中 combine3所示的过程，其内循环里有函数调用。
  
  
• 性能没有明显的提升，显然，内循环中的其他操作形成了瓶颈，限制性能超过调用get_vec_element。

5.6 消除不必要的内存引用

• combine3的代码将合并运算计算的值累积在指针dest指定的位置。每次迭代时，累积变量的数值都要从内存读出再写入到内存，这样的读写很浪费。
• 要消除这种不必要的内存读写，按照图5-10中的combine4所示的方式重写代码，引入一个临时变量acc，在循环中用来累积计算出来的值，循环结束之后才将结果存放在dest中。与combine3中的循环相比，从两次读和一次写减少到只需要一次读。
  
  

5.7 理解现代处理器

• 到目前为止，我们适用的优化都不依赖于目标机器的任何特性。这些优化只是简单地降低了过程调用的开销，以及消除了一些重大的“妨碍优化的因素”，这些因素会优化编译器造成困难。随着试图进一步提高性能，必须考虑利用处理器微体系构的优化，也就是处理器用来执行指令的底层系统设计。要想充分捏高性，需要仔细分析程序，同时代码的生成也要针对目标处理器行调整。
• 5.7.1 整体操作
  
  • 图5-11是现代微处理器的一个非常简单化的示意图。我们假想的处理器设计是不太严格地基于近期的 Intel处理器的结构。这些处理器在工业界称为超标量(super scalar)意思是它可以在每个时钟周期执行多个操作，而且是乱序的(outof-order)意思就是指令执行的顺序不一定要与它们在机器级程序中的顺序一致。整个设计有两个主要部分：指令控制单元(Instruction Control Unit,CU)和执行单元(Execution Unit)前者负从内存中读出指令序列，并根据这些指令序列生成一组针对程序数据的基本操作；而后者执行这些操作。
  • ICU从指令高速缓存(instruction cache)中读取指令，指令高速缓存是一个特殊的高速存储器，它包含最近访问的指令。通常ICU会在当前正在执行的指令很早之前取指，这样它才有足够的时间对指令译码，并把操作发送到EU。不过，当程序遇到分支时，程序有两个可能的前进方向。一种可能会选择分支，控制被传递到分支目标。另一种可能是，不选择分支，控制被传递到指令序列的下一条指令。现代处理器采用了种称为分支预测(branch prediction)的技术，处理器会猜测是否会选择分支，同时还预测分支的目标地址。使用投机执行(speculative execution)的技术，处理器会开始取出位于它预测的分支会跳到的地方的指令，并对指令译码甚至在它确定分支预测是否正确之开始执行这些操作。如果过后确定分支预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向上的指令。标记为取指控制的块包括分预测，以完成确定取哪些指令的任务。
  • 指令译码逻辑接收实际的程序指令，并将它们转换成一组基本操作（有时称为微操作）。每个这样的操作都完成某个简单的计算任务。
  • EU接收来自取指单元的操作。
  • 读写内存是由加载和存储单元实现的。
• 5.7.2 功能单元的性能
  • 图5-12提供了 Intel Core i7 Haswell参考机的一些算术运算的性能,有的是测量出来的,有的是引用 Intel的文献。这些时间对于其他处理器来说也是具有代表性的。每个运算都是由以下这些数值来刻画的：一个是延迟(latency），它表示完成运算所需要的总时间；另一个是发射时间(issue time)，它表示两个连续的同类型的运算之间需要的最小时钟周期数；还有一个是容量(capacity)，它表示能够执行该运算的功能单元的数量。
    
  • 我们看到，从整数运算到浮点运算，延迟是增加的。还可以看到加法和乘法运算的发射时间都为1，意思是说在每个时钟周期，处理器都可以开始条新的这样的运算。这种很短的发射时间是通过使用流水线实现的。流水化的功能单元实现为一系列的阶段(stag)，每个阶段完成部分的运算。
  • 我们还看到，除法器（用于整数和浮点除法，还用来计算浮点平方根）不是完全水线化的一一它的发射时间等于它的延迟。这就意味着在始一条新运算之前，除法器必完成整个除法。
  • 发射时间的一种更常见的方法是指这个功能单元的最大吞吐量，定义为发射间的倒数。一个完全流水线化的功能单元有最大的吐量，每个时周期一个运算，而发射时间较大的功能单元的最大吞吐量比较小。具有多个功能单元可以进一步提高吞吐量。对一个容量为C，发射时间为I的操作来说，处理器可能获得的吐量为时钟周C/I个操作。
  • 用CPE值的两个基本界限来描述这种影响：
    
  • 延迟界限给出了任何必须按照严格顺序完成合并运算的函数所需要的最小CPE值。根据功能单元产生结果的最大速率，吞吐量界限给出了CPE的最小界限。
• 5.7.3 处理器操作的抽象模型
  

  • 我们可以看到，除了整数加法的情况，这些测量值与处理器的延迟界限是一样的。这不是巧合——它表明这些函数的性能是由所执行的求和或者乘积计算主宰的。计算n个元素的乘积或者和需要大约L·n+K个时钟周期，这里L是合并运算的延迟，而K表示调用函数和初始化以及终止循环的开销。因此CPE就等于延迟界限L。

  • 1.从机器级代码到数据流图
    

    • 图5-14是对图5-13的图形化表示的进一步改进，目标是只给出影响程序执行时间的操作和数据相关。
      

  • 2.其他性能因素

5.8 循环展开

• 循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

5.9 提高并行性

• 程序的性能是受运算单元的延迟限制的。
• 5.9.1 多个累积变量
  • 对于一个可结合和可交换的合并运算来说，比如说整数加法或乘法，我们可以通过将一组合并运算分割成两个或更多的部分，并在最后合并结果来提高性能。
    
  • 比较只做循环展开和既做循环展开同时也使用两路并行这两种方法，得到如下性能：
    
• 5.9.2 重新结合变换
  • 图5-26给出了一个函数combine7，它与combine5的唯一区别在于内循环中元素的合并方式。在combine5中，合并是这样的：
    
  • 而在combine7中，合并是这样的：
    
  • 差别仅在于两个括号的放置位置，这种称之为重新结合变换（reassociation transformation）。
    
    
  • 总的来说，重新结合变换能够减少计算中关键路径上操作的数量，通过更好地利用功能单元的流水线能力得到更好的性能。大多数编译器不会尝试对浮点运算做重新结合，因为这些运算不保证是可结合的。当前的GCC版会对整数运算执行重新结合，但不是总有好的效果。通常，我们发现循环展开和并行地累积在多个值中，是提高程序性能的更可靠的方法。

5.10 优化合并代码的结果小结

• 下表总结了对于标量代码所获得的结果，没有使用AVX向量指令提供的向量并行性：
  
• 使用多项优化技术，我们获得的CPE已经接近于0.50和1.00的吞吐量界限，只受限于功能单元的容量。

5.11 一些限制因素

• 我们已经看到在一个程序的数据流图表示中，关键路径指明了执行该程序所需时间的一个基本的下界。也就是说，如果程序中有某条数据相关链，这条链上的所有延迟之和等于T，那么这个程序至少需要T个周期才能执行完。
• 我们还看到功能单元的吞吐量界限也是程序执行时间的一个下界。也就是说，假设一个程序一共需要N个某种运算的计算，而微处理器只有C个能执行这个操作的功能单元，并且这些单元的发射时间为I，那么，这个程序的执行至少需要N·I/C个周期。
• 在本节中，我们会考虑其他一些制约程序在实际机器上性能的因素。
• 5.11.1 寄存器溢出
  • 循环并行性的好处受汇编代码描述计算的能力限制。如果我们的并行度p超过了可用的寄存器数量，那么编译器会诉诸溢出(spilling)，将某些临时值存放到内存中，通常是在运行时堆栈上分配空间。举个例子，将 combine6的多累积变量模式扩展到k=10和k=20,其结果的比较如下表所示：
    
  • 我们可以看到对这种循环展开程度的增加没有改善CPE，有些甚至还变差了。现代x86-64处理器有16个寄存器，并可以使用16个YMM寄存器来保存浮点数。一旦循环变量的数量超过了可用寄存器的数量，程序就必须在栈上分配一些变量。
• 5.11.2 分支预测和预测错误处罚
  • 1.不要过分关心可预测的分支
    • 我们已经看到错误的分支预测的影响可能非常大，但是这并不意味着所有的程序分支都会减缓程序的执行。实际上，现代处理器中的分支预测逻辑非常善于辨别不同的分支指令的有规律的模式和长期的趋势。例如，在合井函数中结束循环的分支通常会被预测为选择分支，因此只在最后一次会导致预测错误处罚。
  • 2.书写适合用条件传送实现的代码
    • 分支预测只对有规律的模式可行。程序中的许多测试是完全不可预测的，依赖于数的任意特性，例如一个数是负数还是正数。对于这些测试，分支预测逻会处理得档糕，对于本质上无法预测的情况，如果编译器能够产生使用条件数据传送而不是使用条件控制转移的代码，可以极大地提高程序的性能。这不是C语言程序员可以直接控制的，但是有些表达条件行为的方法能够更接地被翻译成条件传送，而不是其他操作。
    • 我们发现GCC能够为以一种更“功能性的”风格书写的代码产生条件传送，在这种风格的代码中，我们用条件操作来计算值，然后用这些值来更新程序状态，这种风格对立于一种更“命令式的”风格，这种风格中，我们用条件语句来有选择地更新程序状。
    • 如下示例：
      

5.12 理解内存性能

• 5.12.1 加载的性能
  • 一个包含加载操作的程序的性能既依赖于流水线的能力，也依赖于加载单元的延迟。一条加载操作的结果决定下一条操作的地址。
• 5.12.2 存储的性能
  • 存储操作是将一个寄存器值写到内存。与加载操作一样，在大多数情况下，存储操作能够在完全流水线化的模式中工作，每个周期开始一条新的存储。
  • 对于寄存器操作，在指令被译码成操作的时候，处理器就可以确定哪些指令会影响其他哪些指令。另一方面，对于内存操作，只有到计算出加载和存储的地址被计算出来以后，处理器才能确定哪些指令会影响其他的哪些。高效地处理内存操作对许多程序的性能来说至关重要。内存子系统使用了很多优化，例如当操作可以独立地进行时，就利用这种潜在的并行性。

5.13 应用：性能提高技术

• 优化程序性能的基本策略：
  • 1)高级设计。为遇到的问题选择适当的算法和数据结构要特别警觉，避免使用那些会渐进地产生槽糕性能的算法或编码技术。
  • 2)基本编码原则。避免限制优化的因素，这样编译器就能产生高效的代码。
    • 消除连续的函数调用。在可能时,将计算移到循环外。考虑有选择地妥协程序的模块性以获得更大的效率。
    • 消除不必要的内存引用。引人临时变量来保存中间结果。只有在最后的值计算出来时，才将结果存放到数组或全局变量中。
  • 3)低级优化。结构化代码以利用硬件功能。
    • 展开循环，降低开销，并且使得进一步的优化成为可能。
    • 通过使用例如多个累积变量和重新结合等技术，找到方法提高指令级并行。
    • 用功能性的风格重写条件操作，使得编译采用条件数据传送。

5.14 确认和消除性能瓶颈

• 本节会描述如何使用代码剖析程序（code profiler），这是在程序执行时收集性能数据的分析工具。
• 5.14.1 程序剖析
  • 程序剖析(profiling)运行程序的一个版本，其中插入了工具代码，以确定程序的各个部分需要多少时间。这对于确认程序中我们需要集中注意力优化的部分是很有用的。剖析的一个有力之处在于可以在现实的基准数据( henchmark)上运行实际程序的同时，进行制析。
  • Unix系统提供了一个剖析程序 GPROF。这个序产生两种形式的信息。首先，它确定程序中每个函数花费了多少CPU时间。其次，它计算每个函数调用的次数，以执行调用的函数来分类。
  • 用 GPROF进行剖所需要3个步骤：
    • 1）程序必须为剖析而编译和链接
    • 2）然后程序像往常一样执行
    • 3）调用GPROF来分析gmon.out中的数据
  • GPROF有些属性值得注意：
    • 计时不是很准确。它的计时基于一个简单的隔计数( interval counting)机制，编译过的程序为每个函数护一个计数器，记录花费在执行该函数上的时间。
    • 假设没有执行内联替换，则调用信息相当可靠。编译过的程序为每对调用者和被洞用者维护一个计数器。每次调用一个过程时就会对适当的计数器加1。
    • 默认情况下，不会显示对库函数的计时。相反，库函数的时间都被计算到调用它们的函数的时间中。
• 5.14.2 使用剖析程序来指导优化

5.15 小结

• 我们研究了一系列技术，包括循环展开，创建多个累积变量和重新结合，它们可以利用现代处理器提供的指级并行。随着对优化的深，研究产生的汇编代码以及试看理解机器如何执行计算变得重要来。确认由程序中的数据相关决定的关键路径，尤其是循环的不同迭代之间的数据相关，会收获良多。我们还可以根据必须要计算的操作数量以及执行这些操作的功能单元的数量和发射时间，计算一个吐量界限。
• 包含条件分支或与内存系统复杂交互的程序，比我们最开始考虑的简单循环程序，更难以分析和优化。基本策略是使分支更容易预测，或者使它们很容易用条件数据传送来实现。我们还必须注意存储和加载操作，将数值保存在局变量中，使得它们可以存放在存器中，这会很有帮助。
• 当处理大型程序时,将注意力集中在最耗时的部分变得很重要。代码剖析程序和相关的工具能帮助我们系统地评价和改进程序性能。我们描述了GPROF，一个标准的Unix析工具，还有更加复杂完善的剖析程序可用，例如 Intel的VTUNE程序开发系统，还有 Linux系统基本上都有的VALGRIND。这些工具可以在过程级分解执行时间，估计程序每个基本块( basic block)的性能。(基本块是内部没有控制转移的指令序列，因此基本块总是整个执行的。）

第 6 章 存储器层次结构

• 存储器系统(memory system)是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU寄存器保存着最常用的数据。靠近CPU的小的、快速的高速缓存存储器(cache memory)作为一部分存储在相对慢速的主存储器(main memory)中数据和指令的缓冲区域。主存缓存存储在容量较大的、慢速磁盘上的数据，而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域。

6.1 存储技术

• 6.1.1 随机访问存储器
  • 随机访问存储器(Random-Access- Memory,AM)分为两类：静态的和动态的。静态RAM(SRAM)比动态RAM(DRAM)更快，但也贵得多。SRAM用来作为高速缓存存储器，既可以在CPU芯片上，也可以在片下。DRAM用来作为主存以及图形系统的帧缓冲区。典型地，一个桌面系统的SRAM不会超过几兆字节，但是DRAM却有几百或几千兆字节。
  • 1.静态RAM
    • SRAM将每个位存储在一个双稳态的( bista ble)存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路有这样一个属性，它可以无限期地保持在两个不同的电压配置(configuration)或状态(state)之一。其他任何状态都是不稳定的——从不稳定状态开始，电路会迅速地转移到两个稳定状态中的一个。
    • 由于SRAM存储单元的双稳态特性，只要有电，它就会永远保持它的值。即使有干扰（例如电子噪音）来扰乱电压，当干扰消除时，电路就会恢复到稳定值。
  • 2.动态RAM
    • DRAM将每个位存储为对一个电容的充电。这个电容非常小,通常只有大约30毫微微法拉(femtofarad)30×10^-15法拉。DRAM存储器可以制造得非常密集——每个单元由一个电容和一个访问晶体管组成。但是，与SRAM不同，DRAM存储器单元对干扰非常敏感。当电容的电压被扰乱之后，它就永远不会恢复了。暴露在光线下会导致电容电压改变。实际上,数码照相机和摄像机中的传感器本质上就是DRAM单元的阵列。
    • 图6-2总结了SRAM和DRAM存储器的特性。
      
  • 3.传统的DRAM
    • DRAM芯片中的单元(位)被分成d个超单元(supercell)，每个超单元都由w个DRAM单元组成。一个d×w的DRAM总共存储了dw位信息。超单元被组织成一个r行c列的长方形阵列，这里rc=d。每个超单元有形如(i,j）的地址，这里i表示行，而j表示列。
    • 例如,图6-3展示的是一个16×8的DRAM芯片的组织，有d=16个超单元，每个超单元有w=8位，r=4行，c=4列。带阴影的方框表示地址(2,1)处的超单元。信息通过称为引脚(pin)的外部连接器流入和流出芯片。每个引脚携带一个1位的信号。图6-3给出了两组引脚：8个data引脚，它们能传送一个字节到芯片或从芯片传出一个字节，以及2个addr引脚，它们携带2位的行和列超单元地址。其他携带控制信息的引脚没有显示出来。
      
  • 4.内存模块
    • DRAM芯片封装在内存模块（memory module）中，它插到主板的扩照槽上。Core i7系统使用的240个引脚的双列直格内存块(Dual Inline Memory Module ，DIMM)，它以64位为块传送数据到内存控制器和从内存控器传出数据。
      
  • 5.增强的DRAM
    • 快页模式DRAM(Fast Page Mode DRAM, FPM DRAM)。传统的DRAM将超单元的一整行复制到它的内部行缓冲区中，使用一个，然后丢弃剩余的。FPM DRAM允许对同一行连续地访问可以直接从行缓冲区得到服务，从而改进了这一点。
    • 扩展数据输出DRAM（Extended Data Out DRAM，EDO DRAM）。FPM DRAM的一个增强形式，它允许各个CAS信号在时间上靠得更紧密一点。
    • 同步DRAM(Synchronous DRAM, SDRAM)。就它们与内存控制器通信使用一组显式的控制信号来说，常规的、FPM和 EDO DRAM都是异步的。SDRAM用与驱动内存控制器相同的外部时钟信号的上升沿来代替许多这样的控制信号。
    • 双倍数据速率同步DRAM( Double Data-Rate Synchronous DRAM, DDR SDRAM） DDR SDRAM是对 SDRAM的一种增强，它通过使用两个时钟沿作为控制信号，从而使DRAM的速度翻倍。不同类型的DDR SDRAM是用提高有效带宽的很小的预取缓冲区的大小来划分的：DDR(2位)、DDR2(4位)和DDR(8位)。
    • 视频RAM(Video RAM,VRAM)。它用在图形系统的帧缓冲区中。VRAM的思想与 FPM DRAM类似。两个主要区别是：1)VRAM的输出是通过依次对内部缓冲区的整个内容进行移位得到的；2)VRAM允许对内存并行地读和写。因此，系统可以在写下一次更新的新值(写)的同时，用帧缓冲区中的像素刷屏幕(读)。
  • 6.非易失性存储器
    • 如果断电,DRAM和SRAM会失它们的信息。它们是易失存储器。非易失存储器( nun voiatile memary)即使是在关电后,仍然保存着它们的信息。现在有很多种非易失性存储器。虽然ROM中有的类型可以读也可以写，但是它们整体上都被称为只读存储器(Read-Only Memory，ROM)。ROM是以它们能够被重编程(写)的次数和对它们进行重编程所用的机制来区分的。
    • PROM(Programmable ROM，可编程ROM)只能编程一次。PROM的每个存器单元有一种熔丝(fuse)，只能用高电流熔断一次。
    • 可擦写可编程ROM(Erasable Programmable ROM，EPROM)有一个透明的石英口，允许光到达存储单元。紫外线光照射过窗口，EPROM单元就被清除为0。对EPROM编程是通过使用一种把1写EPROM的特殊设备来完成的。EPROM能够被擦除和重编程的次数的数量级可以达到1000次。
    • 电子可擦除PROM(Electrieally Erasable PROM, EEPROM)类似于 EPROM，但是它不需要一个物理上独立的编程设备，因此可以直接在印制电路卡上编程。EEPROM能被编程的次数的数量级可以达到10⁵次。
    • 闪存（flash memory）是一类非易失性存储器，基于 EEPROM，它已经成为了一种重要的存储技术。闪存无处不在，为大量的电子设备提供快速而持久的非易失性存储，包括数码相机、手机、音乐播放器、PDA和笔记本、台式机和服务器计算机系统。
    • 存储在ROM 设备中的程序通常被称为固件(firmware)。当一个计算机系统通电以后，它会运行存储在ROM 中的固件。
  • 7.访问主存
    • 图6-6展示了计算机系统的基本配置。主要部件是CPU 芯片、我们将称为I/O桥接器的芯片组（其中包括内存控制器），以及组成主存的DRAM 内存模块。这些部件由一对总线连接起来， 其中一条总线是系统总线(system bus)，它连接CPU 和I/O桥接器， 另一条总线是内存总线(memory bus), 它连接I/O桥接器和主存。I/O桥也将系统总线和内存总线连接到I/O总线， 像磁盘和图形卡这样的I/O设备共享I/O总线。
      
    • 读事务
      考虑当CPU 执行一个如下加载操作时会发生什么
      movq A,%rax
      这里，地址A 的内容被加载到寄存器％ rax 中。
      读事务是由三个步骤组成：
      （1）首先，CPU将地址A放到系统总线上。I/O桥将信号传到内存总线(图6-7a)。
      （2）接下来，主存感觉到内存总线上的地址信号，从内存总线读地址，从DRAM取出数据字，并将数据写到内存总线。I/桥将内存总线信号翻译成系统总线信号，然后沿着系统总线传递(图6-7b)。
      （3）最后，CPU感到系统总线上的数据，从总线上读数据，并将数据复制到寄存器%rax(图6-7c)。
      
    • 写事务
      反过来，当CPU执行一个像下面这样的存储操作时
      movq %rax, A
      这里，寄存器％ rax 的内容被写到地址A，CPU发起写事务。
      同样有三个基本步骤组成：
      （1）CPU将地址放到系统总线上。内存从内存总线读出地址，并等待数据到达(图6-8a)。
      （2）接下来，CPU将%rax中的数据字复制到系统总线(图6-8b)。
      （3）最后主存从内存总线读出数据字，并且将这些位存储到DRAM中(图6-8c)。
      
• 6.1.2 磁盘存储
  • 1.磁盘构造
    下图展示的是一个磁盘的基本组成
  • 图6-9a展示了一个典型的磁盘表面的结构。每个表面是由一组称为磁道（track)的同心圆组成的。每个磁道被划分为一组扇区（sector)。每个扇区包含相等数量的数据位（通常是512字节），这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙（gap)分隔开，这些间隙中不存储数据位。间隙存储用来标识扇区的格式化位。
  • 磁盘是由一个或多个叠放在一起的盘片组成的，它们被封装在一个密封的包装里，如图6-9b所示。整个装置通常被称为磁盘驱动器（disk drive),我们通常简称为磁盘（disk)。有时，我们会称磁盘为旋转磁盘（rotating disk),以使之区别于基于闪存的固态硬盘(SSD),SSD是没有移动部分的。
    
  • 2.磁盘容量
  • 磁盘容量由以下技术因素决定：
    • 记录密度(recordi ng dens ity）（位／英寸）：磁道一英寸的段中可以放入的位数。
    • 磁道密度(track dens ity）（道／英寸）：从盘片中心出发半径上一英寸的段内可以有的磁道数。
    • 面密度(areal dens ity）（位／平方英寸）：记录密度与磁道密度的乘积。
  • 磁盘容量的大小 = 每个扇区的字节数 * 每个磁道的平均扇区数 * 每个盘面的磁道数 * 2个盘面 * 盘片数量
  • 3.磁盘操作
    • 磁盘用读/写头（read/write head)来读写存储在磁性表面的位，而读写头连接到一个传动臂（actuator arm)一端，如图6-10a所示。通过沿着半径轴前后移动这个传动臂，驱动器可以将读/写头定位在盘面上的任何磁道上。这样的机械运动称为寻道（seek)。一旦读/写头定位到了期望的磁道上，那么当磁道上的每个位通过它的下面时，读/写头可以感知到这个位的值（读该位）,也可以修改这个位的值（写该位）。有多个盘片的磁盘针对每个盘面都有一个独立的读/写头，如图6-10b所示。读/写头垂直排列，一致行动。在任何时刻，所有的读/写头都位于同一个柱面上。
      
    • 磁盘以扇区大小的块来读写数据。对扇区的访问时间（access time)有三个主要的部分：寻道时间（seek time)、旋转时间（rotational latency)和传送时间（transfer time)：
      • 寻道时间（seek time)：为了读取某个目标扇区的内容，传动臂首先将读/写头定位到包含目标扇区的磁道上。移动传动臂所需的时间称为寻道时间。现代驱动器中平均寻道时间是通过对几千次对随机扇区的寻道求平均值来测量的，通常为3~9ms。一次寻道的最大时间可以高达20ms。
      • 旋转时间（rotational latency)：读/写头在期望的磁道上，驱动器等待目标扇区的第一个位旋转到读写头下的时间。最大旋转延迟（以秒为单位）是
        
      • 传送时间（transfer time)：当目标扇区的第一个位位于读／写头下时，驱动器就可以开始读或者写该扇区的内容的时间。
  • 4.逻辑磁盘块
    为了对操作系统隐藏这样的复杂性，现代磁盘将它们的构造呈现为一个简单的视图，一个B个扇区大小的逻辑块的序列，编号为0, 1, …, B-1。磁盘封装中有一个小的硬件／固件设备，称为磁盘控制器，维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。
    当操作系统想要执行一个I/O操作时，例如读一个磁盘扇区的数据到主存，操作系统会发送一个命令到磁盘控制器，让它读某个逻辑块号。控制器上的固件执行一个快速表查找，将一个逻辑块号翻译成一个==（盘面，磁道，扇区）的三元组==，这个三元组唯一地标识了对应的物理扇区。控制器上的硬件会解释这个三元组，将读／写头移动到适当的柱面，等待扇区移动到读／写头下，将读／写头感知到的位放到控制器上的一个小缓冲区中，然后将它们复制到主存中。
  • 5.连接I/O设备
    
  • 6.访问磁盘
    • CPU使用一种称为==内存映射I/O(memory-mapped I/O)==的技术来向I/O设备发射命令(图6-12a)。在使用内存映射I/O的系统中，地址空间中有一块地址是为与I/O设备通信保留的。每个这样的地址称为一个I/O端口（I/O port)。当一个设备连接到总线时，它与一个或多个端口相关联（或它被映射到一个或多个端口）。
      
• 6.1.3 固态硬盘
  • 固态硬盘（Solid State Disk,SSD)是一种基于闪存的存储技术，在某些情况下是传统旋转磁盘的极有吸引力的替代产品。图6-13展示了它的基本思想。SSD封装插到I/O总线上标准硬盘插槽（通常是USB或SATA)中，行为就和其他硬盘一样，处理来自CPU的读写逻辑磁盘块的请求。一个SSD封装由==一个或多个闪存芯片和闪存翻译层（flash translation layer)==组成，闪存芯片替代传统旋转磁盘中的机械驱动器，而闪存翻译层是一个硬件/固件设备，扮演与磁盘控制器相同的角色，将对逻辑块的请求翻译成对底层物理设备的访问。
    
    一个闪存由B 个块的序列组成，每个块由P页组成。通常，页的大小是512 字节～ 4KB, 块是由32~ 128 页组成的，块的大小为16KB~512KB。
    数据是以页为单位读写的。只有在一页所属的块整个被擦除之后，才能写这一页（通常是指该块中的所有位都被设置为1)。不过， 一旦一个块被擦除了，块中每一个页都可以不需要再进行擦除就写一次。
    大约10万次重复写入后，一个块就会磨损。
    
    随机写很慢的两个原因：擦除一个块需要很长时间(约1毫秒)；修改一个块页需要将所有其他页复制到新的块。
    在早期的ssd中，读/写的差距要大得多。
• 6.1.4 存储技术的趋势
  图6-16清楚地表明了各种趋势。
  

6.2 局部性

一个良好的计算机程序常常具有良好的局部性（locality）。
程序访问的局部性原理指的是：内存中某个地址被访问后，短时间内还有可能继续访问这块地址。内存中的某个地址被访问后，它相邻的内存单元被访问的概率也很大。
程序访问的局部性包含两种：
+ 时间局部性：某个内存单元在较短时间内很可能被再次访问
+ 空间局部性：某个内存单元被访问后相邻的内存单元较短时间内很可能被访问

• 6.2.1 对程序数据引用的局部性
  
  
• 6.2.2 取指令的局部性
  • 因为程序指令是存放在内存中的，CPU必须取出（读出）这些指令，所以我们也能够评价一个程序关于取指令的局部性。例如，图6-17中for循环体里的指令是按照连续的内存顺序执行的，因此循环有良好的空间局部性。因为循环体会被执行多次，所以它也有很好的时间局部性。
  • 代码区别于程序数据的一个重要属性是在运行时它是不能被修改的。当程序正在执行时，CPU只从内存中读出它的指令。CPU很少会重写或修改这些指令。
• 6.2.3 局部性小结
  • 重复引用相同变量的程序有良好的时间局部性。
  • 对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。具有步长为1的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差。
  • 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

6.3 存储器层次结构

• 6.3.1 存储器层次结构中的缓存
  • 图6-22展示了存储器层次结构中缓存的一般性概念。第k+1层的存储器被划分成连续的数据对象组块（chunk),称为块（block)。每个块都有一个唯一的地址或名字，使之区别于其他的块。块可以是固定大小的（通常是这样的）,也可以是可变大小的（例如存储在Web服务器上的远程HTML文件）。例如，图6-22中第k+1层存储器被划分成16个大小固定的块，编号为0~15。
    
  • 1.缓存命中
    当程序需要第k+1层的某个数据对象d 时,它首先在当前存储在第k层的一个块中查找d。如果d刚好缓存在第k层中， 那么就是我们所说的缓存命中。
  • 2.缓存不命中
    顾名思义，也就是第k层中没有缓存数据d。此时第k层的缓存从第k+1层缓存中，取出d的块，如果k满了，会通过一定的策略，选出一个k中的块进行替换。
  • 3.缓存不命中的种类
    如果第k层的缓存是空的，那么对任何数据对象的访问都会不命中。一个空的缓存有时被称为冷缓存（cold cache),此类不命中称为强制性不命中（compulsory miss)或冷不命中（cold miss)。冷不命中很重要，因为它们通常是短暂的事件，不会在反复访问存储器使得缓存暖身（warmed up)之后的稳定状态中出现。
    将第k+1层的某个块限制放置在第k层块的一个小的子集中（有时只是一个块）。例如，在图6-22中，我们可以确定第k+1层的块i必须放置在第k层的块（i mod 4)中。例如，第k+1层的块0、4、8和12会映射到第k层的块0;块1、5、9和13会映射到块1；依此类推。这种限制性的放置策略会引起一种不命中，称为冲突不命中（conflict miss),在这种情况中，缓存足够大，能够保存被引用的数据对象，但是因为这些对象会映射到同一个缓存块，缓存会一直不命中。
    一个嵌套的循环可能会反复地访问同一个数组的元素。这个块的集合称为这个阶段的工作集（working set)。当工作集的大小超过缓存的大小时，缓存会经历容量不命中（capacity miss)。换句话说就是，缓存太小了，不能处理这个工作集。
    +4.缓存管理
    存储器层次结构的本质是，每一层存储设备都是较低一层的缓存。在每一层上，某种形式的逻辑必须管理缓存。这里，我们的意思是指某个东西要将缓存划分成块，在不同的层之间传送块，判定是命中还是不命中，并处理它们。管理缓存的逻辑可以是硬件、软件，或是两者的结合。
• 6.3.2 存储器层次结构概念小结
  • 利用时间局部性
  • 利用空间局部性
  • 现代系统中都使用了缓存，如图6-23所示：
    

6.4 高速缓存存储器

由于CPU和主存之间逐渐增大的差距，系统设计者被迫在CPU寄存器文件和主存之间插入了一个小的SRAM高速缓存存储器，称为L1高速缓存（一级缓存），如图6-24所示。L1高速缓存的访问速度几乎和寄存器一样快，典型地是大约4个时钟周期。

随着CPU和主存之间的性能差距不断增大，系统设计者在L1高速缓存和主存之间又插人了一个更大的高速缓存，称为L2高速缓存，可以在大约10个时钟周期内访问到它。有些现代系统还包括有一个更大的高速缓存，称为L3高速缓存，在存储器层次结构中，它位于L2高速缓存和主存之间，可以在大约50个周期内访问到它。

• 6.4.1 通用的高速缓存存储器组织结构
  
  当一条加载指令指示CPU从主存地址A中读一个字时，它将地址A发送到高速缓存。如果高速缓存正保存着地址A处那个字的副本，它就立即将那个字发回给CPU。那么高速缓存如何知道它是否包含地址A处那个字的副本的呢？高速缓存的结构使得它能通过简单地检查地址位，找到所请求的字，类似于使用极其简单的哈希函数的哈希表。下面介绍它是如何工作的：
• 6.4.1 直接映射高速缓存
  • 根据每个组的高速缓存行数E，高速缓存被分为不同的类。每个组只有一行（E=1)的高速缓存称为直接映射高速缓存（direct-mapped cache)(见图6-27)。直接映射高速缓存是最容易实现和理解的，所以我们会以它为例来说明一些高速缓存工作方式的通用概念。
    
  • 1.直接映射高速缓存中的组选择
    6-28展示了直接映射高速缓存的组选择是如何工作的。在这个组索引为00001₂被解释为选择组1的整数索引。
    
  • 2.直接映射高速缓存中的行匹配
    图6-29展示了直接映射高速缓存中行匹配是如何工作的。在这个例子中，选中的组中只有一个高速缓存行。这个行的有效位设置了，所以我们知道标记和块中的位是有意义的。因为这个高速缓存行中的标记位与地址中的标记位相匹配，所以我们知道我们想要的那个字的一个副本确实存储在这个行中。换句话说，我们得到一个缓存命中。另一方面，如果有效位没有设置，或者标记不相匹配，那么我们就得到一个缓存不命中。
    
  • 3.直接映射高速缓存中的字选择
    一旦命中，我们知道w就在这个块中的某个地方。最后一步确定所需要的字在块中是从哪里开始的。如图6-29所示，块偏移位提供了所需要的字的第一个字节的偏移。就像我们把高速缓存看成一个行的数组一样，我们把块看成一个字节的数组，而字节偏移是这个数组的一个索引。在这个示例中，块偏移位是100₂,它表明w的副本是从块中的字节4开始的。
  • 4.直接映射高速缓存中不命中时的替换
    如果缓存不命中，那么它需要从存储器层次结构中的下一层取出被请求的块，然后将新的块存储在组索引位指示的组中的一个高速缓存行中。一般而言，如果组中都是有效高速缓存行了，那么必须要驱逐出一个现存的行。对于直接映射高速缓存来说，每个组只包含有一行，替换策略非常简单：用新取出的行替换当前的行。
• 6.4.3 组相联高速缓存
  图6-32展示了一个2路组相联高速缓存的结构
  
  
  
  • 组相联高速缓存中不命中时的行替换
    如果CPU请求的字不在组的任何一行中，那么就是缓存不命中，高速缓存必须从内存中取出包含这个字的块。不过，一旦高速缓存取出了这个块，该替换哪个行呢？当然，如果有一个空行，那它就是个很好的候选。但是如果该组中没有空行，那么我们必须从中选择一个非空的行，希望CPU不会很快引用这个被替换的行。
    最简单的替换策略是随机选择要替换的行。其他更复杂的策略利用了局部性原理，以使在比较近的将来引用被替换的行的概率最小。例如，最不常使用（Least-Frequently-Used,LFU)策略会替换在过去某个时间窗口内引用次数最少的那一行。最近最少使用（Least-Recently-Used,LRU)策略会替换最后一次访问时间最久远的那一行。所有这些策略都需要额外的时间和硬件。但是，越往存储器层次结构下面走，远离CPU,一次不命中的开销就会更加昂贵，用更好的替换策略使得不命中最少也变得更加值得了。
• 6.4.4 全相联高速缓存
  
  
  
• 6.4.5 有关写的问题
  • 假设我们要写一个已经缓存了的字w（写命中， write hit)。在高速缓存更新了它的w的副本之后， 怎么更新w在层次结构中紧接着低一层中的副本呢？
  • 最简单的方法，称为直写（write-through),就是立即将w的高速缓存块写回到紧接着的低一层中。虽然简单，但是直写的缺点是每次写都会引起总线流量。
  • 另一种方法，称为写回（write-back),尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的低一层中。由于局部性，写回能显著地减少总线流量，但是它的缺点是增加了复杂性。
  • 高速缓存必须为每个高速缓存行维护一个额外的修改位（dirty bit),表明这个高速缓存块是否被修改过。
  • 另一个问题是如何处理写不命中。一种方法，称为写分配（write-allocate),加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。写分配试图利用写的空间局部性，但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。另一种方法，称为非写分配（not-write-allocate),避开高速缓存，直接把这个字写到低一层中。直写高速缓存通常是非写分配的。写回高速缓存通常是写分配的。
• 6.4.6 一个真实的高速缓存层次结构的解剖
  
  
• 6.4.7 高速缓存参数的性能影响
  有许多指标来衡量高速缓存的性能：
  ● 不命中率（miss rate)。在一个程序执行或程序的一部分执行期间，内存引用不命中的比率。它是这样计算的：不命中数量/引用数量。
  ●命中率（hit rate)。命中的内存引用比率。它等于1一不命中率。
  ●命中时间（hit time)。从高速缓存传送一个字到CPU所需的时间，包括组选择、行确认和字选择的时间。对于L1高速缓存来说，命中时间的数量级是几个时钟周期。
  ●不命中处罚（miss penalty)。由于不命中所需要的额外的时间。L1不命中需要从L2得到服务的处罚，通常是数10个周期；从L3得到服务的处罚，50个周期；,从主存得到的服务的处罚，200个周期。

6.5 编写高速缓存友好的代码

1)让最常见的情况运行得快。程序通常把大部分时间都花在少量的核心函数上，而这些函数通常把大部分时间都花在了少量循环上。所以要把注意力集中在核心函数里的循环上，而忽略其他部分。
2)尽量减小每个循环内部的缓存不命中数量。在其他条件（例如加载和存储的总次数）相同的情况下，不命中率较低的循环运行得更快。

6.6 综合：高速缓存对程序性能的影响

• 6.6.1 存储器山
  一个程序从存储系统中读数据的速率称为读吞吐量（read throughput),或者有时称为读带宽（read bandwidth)。如果一个程序在s秒的时间段内读n个字节，那么这段时间内的读吞吐量就等于n/s,通常以兆字节每秒（MB/s)为单位。
  如果我们要编写一个程序，它从一个紧密程序循环（tight program loop)中发出一系列读请求，那么测量出的读吞吐量能让我们看到对于这个读序列来说的存储系统的性能。图6-40
  
  run函数是一个包装函数，调用test函数，并返回测量出的读吞吐量。第37行对test函数的调用会对高速缓存做暖身。第38行的fcyc2函数以参数elems调用test函数，并估计test函数的运行时间，以CPU周期为单位。注意，run函数的参数size是以字节为单位的，而test函数对应的参数elems是以数组元素为单位的。另外，注意第39行将MB/s计算为106字节/秒，而不是220字节/秒。
  run函数的参数size和stride允许我们控制产生出的读序列的时间和空间局部性程度。size的值越小，得到的工作集越小，因此时间局部性越好。stride的值越小，得到的空间局部性越好。如果我们反复以不同的size和stride值调用run函数，那么我们就能得到一个读带宽的时间和空间局部性的二维函数，称为存储器山（memory moun-tain)。
  • 每个计算机都有表明它存储器系统的能力特色的唯一的存储器山。例如，图6-41展示了 Intel Core i7系统的存储器山。在这个例子中，size从16KB变到128KB,stride从1变到12个元素，每个元素是一个8个字节的long int。
    
  • 这座Corei7山的地形地势展现了一个很丰富的结构。垂直于大小轴的是四条山脊，分别对应于工作集完全在L1高速缓存、L2高速缓存、L3高速缓存和主存内的时间局部性区域。注意，L1山脊的最高点（那里CPU读速率为14GB/s)与主存山脊的最低点（那里CPU读速率为900MB/s)之间的差别有一个数量级。
  • 在L2、L3和主存山脊上，随着步长的增加，有一个空间局部性的斜坡，空间局部性下降。注意，即使当工作集太大，不能全都装进任何一个高速缓存时，主存山脊的最高点也比它的最低点高8倍。因此，即使是当程序的时间局部性很差时，空间局部性仍然能补救，并且是非常重要的。
  • 从这座山中取出一个片段，保持步长为1，如图6-42所示，我们就能很清楚地看到高速缓存的大小和时间局部性对性能的影响。
    
  • 以相反的方向横切这座山，保持工作集大小不变，我们从中能看到空间局部性对读吞吐量的影响。如图6-43
    
• 6.6.2 重新排列循环以提高空间局部性
  
  • 矩阵乘法函数通常是用3个嵌套的循环来实现的，分别用索引i、j和k来标识。如果改变循环的次序，对代码进行一些其他的小改动，我们就能得到矩阵乘法的6个在功能上等价的版本，如图6-44所示。每个版本都以它循环的顺序来唯一地标识。
    为了分析，我们做了如下假设：
    ●每个数组都是一个double类型的n * n的数组，sizeof(double)=8。
    ● 只有一个高速缓存，其块大小为32字节（B=32)。
    ● 数组大小 n 很大，以至于矩阵的一行都不能完全装进 L1 高速缓存中。
    ·编译器将局部变量存储到寄存器中，因此循环内对局部变量的引用不需要任何加载或存储指令
  • 图6-45总结了对循环的分析结果
    
  • 图6-46小结了一个Corei7系统上矩阵乘法各个版本的性能。这个图画出了测量出的每次内循环迭代所需的CPU周期数作为数组大小（n)的函数。
    
    
• 6.6.3 在程序中利用局部性
  • 正如我们看到的，存储系统被组织成一个存储设备的层次结构，较小、较快的设备靠近顶部，较大、较慢的设备靠近底部。由于采用了这种层次结构，程序访问存储位置的实际速率不是一个数字能描述的。相反，它是一个变化很大的程序局部性的函数（我们称之为存储器山）,变化可以有几个数量级。有良好局部性的程序从快速的高速缓存存储器中访问它的大部分数据。局部性差的程序从相对慢速的DRAM主存中访问它的大部分数据。理解存储器层次结构本质的程序员能够利用这些知识编写出更有效的程序，无论具体的存储系统结构是怎样的。特别地，我们推荐下列技术：
    ●将你的注意力集中在内循环上，大部分计算和内存访问都发生在这里。
    ●通过按照数据对象存储在内存中的顺序、以步长为1的来读数据，从而使得你程序中的空间局部性最大。
    ● 一旦从存储器中读入了一个数据对象，就尽可能多地使用它，从而使得程序中的时间局部性最大。

待更新……