计算机系统中的层次概念#

1. 计算机系统 = 软件 + 硬件/固件
2. 计算机语言由低级向高级发展：高一级语言的语句相对于低级语言功能更强，更便于应用，但又都以低级语言为基础
3. 从计算机语言的角度，把计算机系统按系统功能划分成多层次结构

计算机体系结构定义#

1. 计算机体系结构定义：程序员所看到的计算机属性，即概念性结构与功能特性
2. 按照计算机系统的多级层次结构，不同级程序员所看到的计算机具有不同属性
3. 透明性：在计算机技术中，对这种本来是存在的事物或属性，但从某种角度看又好像不存在
4. Amdahl提出的体系结构：传统机器级体系结构————即一般所说的机器语言，程序员所看到的传统机器级所具有的属性
5. 对通用寄存器型机器，属性主要指
   1. 数据表示（硬件能直接辨认和处理的数据类型）
   2. 寻址规则（最小寻址单元、寻址方式及其表示）
   3. 寄存器定义（各种寄存器的定义、数量和使用方式）
   4. 指令集（机器指令的操作类型和格式、指令间的排序和控制机构等）
   5. 中断系统（中断类型和中断响应硬件的功能等）
   6. 机器工作状态的定义切换（管态和目态等）
   7. 存储系统（主存容量、程序员可用的最大存储容量等）
   8. 信息保护（信息保护方式和硬件对信息保护的支持）
   9. I/O结构（I/O连接方式、处理机/存储器与I/O设备间数据传送的方式和格式以及I/O操作的状态等）

经典计算机体系结构概念的实质 计算机系统中软硬件界面的确定，界面之上是软件功能，界面之下是硬件和固件功能

计算机组成和计算机实现技术#

1. 计算机组成：计算机体系结构的逻辑实现
2. 计算机实现：计算机组成的物理实现

一种体系结构可以有多种组成
一种组成可以有多种物理实现

3. 系列机/兼容机/软件兼容
   1. 系列机：在一个厂家内生产的具有相同体系结构，但具有不同组成和实现的一系列不同型号的机器

计算机的分代和分类#

• 桌面计算机

• 服务器

• 物联网/嵌入式计算机

• 个人移动装置

• 集群/数据中心计算系统

• Flynn分类法：按照指令流和数据流的多倍性特征对计算机系统进行分类

  • 指令流：机器执行的指令序列
  • 数据流：由指令调用的数据序列，包括输入数据和中间结果
  • 多倍性(multiplicity)：在系统性能瓶颈不见上同时处于同一执行阶段的指令或数据的最大可能个数
  1. 单指令流单数据流SISD — Single Instruction Stream Single Data Stream
  2. 单指令流多数据流SIMD — Single Instruction Stream Multiple Data Stream
  3. 多指令流单数据流MISD — Multiple Instruction Stream Single Data Stream
  4. 多指令流多数据流MIMD — Multiple Instruction Stream Multiple Data Stream

• SISD：传统顺序处理机

  • 包括单指令功能部件处理机，多功能部件处理机，流水线处理机————标量流水线处理机

• SIMD：

  • 包括并行处理机，阵列处理机，向量处理机，超标量处理机，超流水线处理机，即多个PU按一定的方式互联，在同一个CU控制下，并行的对多个数据进行处理

• MIMD：

  • 多处理机系统

• MISD：实际不存在

性能设计和评测的基本原则#

冯诺依曼结构及其改进#

• 存储程序原理的基本点：指令驱动
  • 程序预先存放再计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作
• 冯诺依曼结构的主要特点
  • 计算机以运算器为中心
  • 在存储器中，指令和数据同等对待
    • 指令和数据一样可以进行运算，即由指令组成的程序是可以修改的
  • 存储器是按地址访问、按顺序线性编址的一维结构，每个单元的位数是固定的
  • 指令的执行是顺序的
    • 一般是按照指令在存储器中存放的顺序执行
    • 程序的分支由转移指令实现
    • 由指令计数器PC指明当前正在执行的指令在存储器中的地址
  • 指令由操作码和地址吗组成
  • 指令和数据均以二进制编码表示，采用二进制运算
• 对系统结构进行的改进
  • 输入/输出方式的改进
    • 程序控制
      • 程序等待
      • 程序中断
    • DMA
      • 成组传递
      • 周期挪用
    • I/O处理机
      • 通道
      • 外围处理机
  • 采用并行处理技术
  • 存储器组织结构的发展
    • 相联存储器与相联处理机
    • 通用寄存器组
    • 高速缓冲存储器Cache
  • 指令系统的发展
    • 复杂指令集计算机CISC
    • 精简指令集计算机RISC

并行性的概念#

• 并行性
  • 计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。——只要在时间上相互重叠，就存在并行性
• 同时性：两个或两个以上的事件在同一时刻发生
• 并发性：两个或两个以上的事件在同一时间间隔内发生
• 从处理数据的角度来看，并行性等级从低到高可分为
  • 字串位串：每次只对一个字的一位进行处理：最基本的串行处理方式，不存在并行性
  • 字串位并：同时对一个自的全部位进行处理，不同字之间是串行的 —— 开始出现并行性
  • 字并位串：同时对许多字的同一位（称为位片）进行处理 —— 具有较高的并行性
  • 全并行：同时对许多字的全部位或部分位进行处理 —— 最高一级的并行
• 从执行程序的角度来看，并行性等级从低到高可分为
  • 指令内部并行：单挑指令中各微操作之间的并行
  • 指令级并行：并行执行两条或以上的指令
  • 线程级并行：并行执行两个或以上的线程 —— 通常是一个进程内派生的多个线程为调度单位
  • 任务级或过程级并行：并行执行两个或以上的过程或任务（程序段）—— 以子程序或进程为调度单元
  • 作业或程序级并行：并行执行两个或以上的作业或程序

提高并行性的技术途径#

• 时间重叠
  • 引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度
• 资源重复
  • 引入空间因素，以数量取胜。通过重复设置硬件资源，大幅度地提高计算机系统的性能
• 资源共享
  • 一种软件方法，使多个任务按照一定时间顺序轮流使用同一套硬件设备

单片系统中并行性的发展#

• 在发展高性能单处理机过程中，起主导作用的是时间重叠原理
  • 实现时间重叠的基础：部件功能专用化
    • 把一件工作按功能分割为若干相互联系的部分
    • 把每一部分指定给专门的部件完成
    • 然后按时间重叠原理把各部分的执行过程在时间上重叠起来，使所有部件依次分工完成一组同样的工作
• 在单处理机中，资源重复原理的运用也已十分普遍
  • 多体存储器
  • 多操作部件
    • 通用部件被分解为若干个专用部件，如加法、乘法、触发、逻辑运算部件等，而且同一种部件也可以重复设置多个
    • 如果指令所需的操作部件空闲，就可以开始执行这条指令（操作数已经准备好）。实现了指令级并行
  • 阵列处理机（并行处理器）
    • 设置许多相同的处理单元，让它们在同一个控制器的指挥下，按照同一条指令的要求，对向量或数组的各元素同时进行同一操作，就形成了阵列处理机
    • 在单处理机中，资源共享的概念实质上是用单处理机模拟多处理机的功能，形成所谓虚拟机的概念
    • 分时系统

多机系统中并行性的发展#

• 多机系统遵循时间重叠、资源重复、资源共享原理，发展为3中不同的多处理机
  • 同构型多处理机、异构型多处理机、分布式系统
• 耦合度
  • 反映多机系统中各机器之间物理连接的紧密程度和交互作用能力的强弱
  • 紧密耦合系统（直接耦合系统）：在这种系统中，计算机之间的物理连接的频带较高，一般是铜鼓哦总线或告诉开关互联，可以共享主存
  • 松散耦合系统（简介耦合系统）：一般是铜鼓哦通道或通信线路实现计算机之间的互联，可以共享外存设备（磁盘、磁带等）。机器之间的相互作用是在文件或数据集一级上进行
    • 表现为两种形式
    • 多台计算机和共享的外存设备连接，不同机器之间实现功能上的分工（功能专用化），机器处理的结果以文件或数据集的形式发送到共享外存设备，供其它机器继续处理
    • 计算机网，通过通信线路连接，实现更大范围的资源共享
• 功能专用化（实现时间重叠）
  • 专用外围处理机：e.g. 输入/输出功能的分离
  • 专用处理机：e.g. 数组运算、高级语言翻译、数据库管理等，分离出来
  • 异构型多处理机系统
    • 由于多个不同类型、至少担负不同功能的处理机组成，它们按照作业要求的顺序，利用时间重叠原理，一次对它们的多个任务进行加工，各自完成规定的功能动作
• 机间互联
  • 容错系统
  • 可重构系统
  • 同构型多处理机系统

流水线的分类#

• 部件级、处理机级及处理机间流水线（按照流水技术用与计算机系统的等级不同）
  • 部件级流水线（运算操作流水线）：把处理机中的部件分段，再把这些分段相互连接起来，使得各种类型的运算操作都能够按照流水方式进行
  • 处理机级流水线（指令流水线）：把指令的执行过程按照流水方式处理。把每一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行
  • 系统级流水线（宏流水线）：把多台处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分
• 单功能流水线与多功能流水线
  • 单功能流水线：只能完成一种固定功能的流水线
  • 多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能
• 静态流水线与动态流水线（按照同一时间内各段之间的连接方式对多功能流水线作进一步的分类）
  • 静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作
    • 对于静态流水线来说，只有当输入的是统一穿相同的运算任务时候流水线的效率才能得到充分的发挥
  • 动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式hi链接，同时执行多种功能
    • 优点：灵活，能够提高流水线各段的使用率，从而提高处理速度
    • 缺点：控制复杂
• 线性流水线与非线性流水线（按照流水线中是否由反馈回路来进行分类）
  • 线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次
  • 非线性流水线：流水线中除了有串行的连接外，还有反馈回路
  • 非线性流水线的调度问题：确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突——争用流水段
• 顺序流水线与乱序流水线（根据任务流入和流出的顺序是否相同来进行分类）
  • 顺序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一个顺序流动的
  • 乱序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成（从输出端流出）

吞吐率#

吞吐率： 在单位时间内流水线所完成的任务数量或输出结果的数量 $TP = \frac{n}{T_k}$

流水线的加速比#

加速比：完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比

假设：不使用流水线（顺序执行）所用的时间为$T_s$，使用流水线后所用的时间为$T_k$，则该流水线的加速比$S=\frac{T_s}{T_k}$

流水线的效率#

流水线的效率：流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率

由于流水线有通过时间和排空时间，所以在连续完成n个任务的时间内，各段并不是满负荷的工作

从时空图的角度来看，效率就是n个任务占用的时空面积/k个段的总时空面积(最大矩形的面积)

流水线设计中的若干问题#

• 瓶颈问题
  • 理想情况下，流水线在工作时，其中的任务是同步地每一个时钟周期往前流动一段
  • 当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间
  • 在设计流水线时，要尽可能使各段时间相等
• 流水线的额外开销
  • 流水寄存器延迟：建立时间，传输延迟
  • 时钟偏移开销：时钟到达各流水寄存器的最大差值时间
• 明确意义
  • 流水线不能减少（而且一般是增加）单条指令的执行时间，但却能提高吞吐率
  • 适当增加流水线的深度（段数）可以提高流水线的性能
  • 流水线的深度受限于流水线的额外开销
  • 当时钟周期小到与额外开销相同时，流水已经没有意义。因为这时在每一个时钟周期中已经没有时间来做有用的工作

单功能非线性流水线的最优调度#

• 向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离
• 会引起非线性流水线功能段使用冲突的启动距离则称为禁用启动距离
• 启动距离和禁用启动距离一般都是用时钟周期数来表示，是一个正整数
• 预约表
  • 横向（向右）：时间（一般用时钟周期表示）
  • 纵向（向下）：流水线的段
  • 如果在第n个时钟周期使用了第k段，则在第k行和第n列的交叉处各自里又一个勾
  • 如果在第k行和第n列的交叉处的格子里有一个勾，则表示在第n个时钟周期要使用第k段

经典5段流水线#

• IF取指令周期
  • 以程序计数器PC中的内容作为地址，从存储器中取出指令并放入寄存器IR
  • 同时PC值加4，指向顺序的下一条地址
• ID指令译码/读寄存器周期
  • 对指令进行译码，并用IR中的寄存器地址去访问通用寄存器组，读出所需的操作数
• EX执行/有效地址计算周期
  • load和store指令：ALU把指令中所指定的寄存器的内容与偏移量相加，形成访存有效地址
  • 寄存器-寄存器ALU指令：ALU按照操作码指定的操作对通用寄存器组中读出的数据进行运算
  • 寄存器-立即数ALU指令：ALU按照操作码指定的操作对从通用寄存器组中读出的操作数和指令中给出的立即数进行运算
  • 分支指令：ALU把指令中给出的偏移量与PC相加，形成转移目标的地址。同时，对在前一个周期读出的操作数进行判断，确定分支是否成功
• MEM存储器访问/分支完成周期
  • load指令：用上一个周期计算出的有效地址，从存储器中读出相应的数据
  • store指令：把指定的数据写入这个有效地址所指出的存储器单元（完成）
  • 分支指令：如果分支成功，把转移目标地址送入PC。（分支指令也在此阶段全部完成）
  • 其它指令在该周期无操作
• WB写回周期
  • ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组

在以上的实现方案中，分支指令和store指令需要4个周期，其它指令需要5个周期

相关#

• 相关：两条指令之间存在某种依赖关系。
• 如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行
• 三种相关类型
  • 数据相关
  • 名相关
  • 控制相关

冲突#

• 冲突：对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行
• 类型
  • 结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突
  • 数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突
  • 控制冲突：流水线遇到分支指令和其它会改变PC值的指令所引起的冲突
• 问题
  • 导致错误的执行结果
  • 流水线可能会出现停顿，从而降低流水线的效率和实际的加速比
  • 当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行

动态调度的基本思想#

• 把指令流出的工作拆分为两步
  • 检测结构冲突
  • 等待冲突数据消失
  • 只要检测到没有结构冲突，就可以让指令流出，并且流出后的指令一旦其操作数就绪就可以立即执行
• 乱序执行
  • 指令的执行顺序与程序顺序不相同
  • 指令的完成也是乱序完成的：指令的完成顺序与程序顺序不相同
• 为了支持乱序执行，把5段流水线的译码阶段再分成两个阶段
  • 流出(Issue, IS)：指令译码，检查是否存在结构冲突(in order issue)
  • 读操作数(Read Operands, RO)：等待数据冲突消失，然后读操作数
  • 本来的5段流水线中，是不会发生WAR冲突和WAW冲突的，但是乱序执行就有可能发生了。
• 动态调度的流水线支持多条指令同时处于执行当中
  • 要求：具有多个功能部件、或者功能部件流水化、或者兼而有之

分支历史表BHT#

• Branch History Table
  • 最简单的动态分支预测方法
  • 用BHT来记录分支指令最近一次或几次的执行情况（成功还是失败），并据此进行预测
• 只有一个预测位的分支预测
  • 记录分支指令最近一次的历史，BHT中之需要1位二进制位
• 采用两位二进制位来记录历史
  • 提高预测的准确度
  • 两位分支预测的性能与n位分支预测的性能差不多
  • 两位分支预测的状态转换，图略
  • 但是在之前的五段流水线中，哪怕是在ID段判断分支计算目标地址，BHT也仍然是在ID段执行的，没法带来什么好处

采用分支目标缓冲器BTB#

• 目标：将分支的开销降为0
• 方法：分支目标缓冲
  • 将分支成功的分支指令地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识
  • 这个缓冲区就是分支目标缓冲区Branch Target Buffer，或者分支目标cache

基于静态调度的多流出技术#

• 在典型的超标量处理器中，每个时钟周期可以可以流出1到8条指令
• 指令按序流出，在流出时进行冲突检测
  • 由硬件检测当前流出的指令之间是否存在冲突以及当前流出的指令与正在执行的指令是否有冲突

超长指令字技术#

• 把能并行执行的多条指令组装称一条很长的指令
• 设置多个功能部件
• 指令字被分割成一些字段，每个字段称为一个操作槽，直接独立地控制一个功能部件
• 在VLIW处理机中，在指令流出时不需要进行复杂的冲突检测，而是依靠编译器全部安排号了
• 存在的问题
  • 程序代码长度增加了
    • 提高并行性而进行的大量的循环展开
    • 指令字中的操作槽并非总能填满
      • 解决：采用指令共享立即数字段的方法，或者采用指令压缩存储、调入cache或译码时展开的方法
  • 采用了锁步机制
    • 任何一个操作部件出现停顿时，整个处理机都要停顿
  • 机器代码的不兼容性

多流出处理器受到的限制#

• 程序所固有的指令级并行性
• 硬件实现上的困难
• 超标量和超长指令字处理器固有的技术限制

超流水线处理机#

• 将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令，这种处理机称为超流水线处理机
• 对于一台每个时钟周期都能流出n条指令的超流水线计算机来说，这n条指令不是同时流出的，而是每隔1/n个时钟周期流出一条指令
  • 实际上该超流水线计算机长度流水线周期为1/n个时钟周期
• 有时候把指令流水线级数位8及以上的流水线处理机称为超流水线处理机

存储系统的层次结构#

采用多种存储技术，构成多级存储层次结构

• 程序访问的局部性原理：对于绝大多数程序来说，程序锁访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的
• 程序访问的局部性包含两个方面
  • 时间局部性：程序马上将要用到的信息很可能就是现在正在使用的信息
  • 空间局部性：程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的
• 原理：加快经常性事件

存储层次的性能参数#

当整个存储系统只有两个层次M1，M2时候

• 存储容量
  • 一般来说，整个存储系统的容量只用算第二级存储器M2的容量，即S=S2
• 每位价格C
  • $C = \frac{C_1S_1 + C_2S_2}{S_1 + S_2}$
  • 当$S_1 << S_2$时,$C \approx C_2$
• 命令率H和不命中率F
  • 命中率：CPU访问存储系统时，在M1中找到所需信息的概率
    • $H=\frac{N_!}{N_1 + N_2}$
    • N1：访问M1的次数
    • N2：访问M2的次数
  • 不命中率F：F = 1 - H
• 平均访问时间$T_A$
  • $T_A = HT_1 + (1 - H) * (T_1 + T_M) = T_1 + (1 - H) T_M$
  • 或者$T_A = T_1 + FT_M$
  • 当命中时，访问时间即为$T_1$
  • 当不命中时，miss开销$T_M = T_2 + T_B$：从向M2发出访问请求到把整个数据块调入M1锁需要的时间
    • $T_B$为传入一个信息块所需的时间
  • 不命中时的总访问时间为$T_1 + T_2 + T_B$

三级存储系统#

• 三级
  • cache
  • 主存
  • 外存（辅存）
• 可以看成是由cache-主存和主存-辅存层次构成的系统

存储层次的四个问题#

• 当把一个块调入高一层（靠近CPU）存储器时，可以放在哪些位置上？ —— 影响规则
• 当所要访问的块在高一层存储器中时候，如何找到该块？ —— 查找算法
• 当发生不命中时，应替换哪一块？ —— 替换算法
• 当进行写访问时，应进行哪些操作？ —— 写策略

基本结构和原理#

• cache是按块进行管理的
• cache和主存均被分割称大小相同的块（cache line）
• 信息以块为单位调入cache
  • 主存块地址（块号）用于查找该块在cache中的位置
  • 块内位移用于确定所访问的数据在该块中的位置
  • 主存地址：块地址+块内位移

映像规则#

• 全相联映像
  • 全相联：主存中的任意块可以被放置到cache中的任意一个文职
  • 特点：空间利用率最高，冲突概率最低，实现最复杂，查找速度慢
• 直接映像：主存中断每一块只能被防止到cache中的位移一个位置
  • 特点：空间利用率最低，冲突概率最高，实现最简单，查找速度最快
  • 对于主存的第i块，若它映像到cache的第j块，则$j = i mod (M)$，其中M为cache的块数
  • 当$M=2^m$时，则当表示为二进制数时，j实际上就是i的低m位
• 组相联映像
  • 组相联：主存中的每一块可以被防止到cache中唯一的一个组中的任何一个位置（直接映像到组，组内全相联）
  • 组相联是直接印象和全相联的一种折中
  • 组的选择
    • 若主存低i块映像到低k组，则$k = i mod (G)$
    • 设$G=2^g$，当二进制表示的时候，k实际上就是i的低j位
  • n路组相联：每组中有n个块($n = M \div G$)
    • n称为相联度
    • 相联度越高，cache空间的利用率就越高，块冲突概率就越低，不命中概率也就越低

查找算法#

• 通过查找目录表来实现
  • 目录表的结构
    • 主存块的块地址的高位部分，称为标识Tag
    • 每个主存块嫩巩唯一地由其标识来确定
  • 只需查找候选位置所对应的目录表项
• 并行查找的实现方法
  • 相联存储器
    • 目录由$2^g$个相联存储区域构成，每个相联存储区的大小为$n \times (h + log_2 n)$位
    • 根据所查找到的组内块地址，从cache存储体中读出的多个信息字中选一个，发送给CPU
  • 但体多字的按地址访问的存储器和比较器

替换算法#

• 解决的问题：当新调入一块时，二cache有已经被占满时，如何替换
  • 直接映像的cache中替换很简单，因为只有一个
• 替换算法
  • 随机
  • 先进先出FIFO
    • FIFO中，不管一个块是否命中，只要是先进入的块，就一定先出去
  • 最近最少使用发LRU
    • 选择近期最少被访问的块作为被替换的块
    • 实际上选择最久没有被访问过的块作为被替换的块
    • 优点：命中率较高

写策略#

• 占的访存比例不大，但是影响力很大
• 写操作必须在确认是命中后才可以进行
• 写访问有可能导致cache和主存内容的不一致
• 两种写策略
  • 写直达法（写穿）：执行写操作时，不仅写入cache，而且也写入下一级存储器
  • 写回：执行写操作时，只写入cache，仅当cache中相应的块被替换时，才写回主存
  • 写策略是区分不同cache设计方案的一个重要标志
• 两种写策略的比较
  • 写回：速度块，所使用的存储器带宽低
  • 写穿：易于实现，一致性好
• 采用写穿法的时候，若在进行写操作，CPU必须等待，直到写操作结束，称为CPU写停顿
  • 减少些停顿的一种常用的优化技术：采用写缓冲器
• 写操作时的调块
  • 按写分配（写时取）
    • 写不命中时，先把所写单元所在的块调入cache，再行写入
  • 不按写分配（绕写法）
    • 写不命中时，直接写入下一级存储器而不调块
• 写策略与调块
  • 写回——按写分配
  • 写穿——不按写分配

cache的性能分析#

• 不命中率
  • 与硬件速度无关
• 平均访存时间
  • 平均访存时间 = 命中时间 + 不命中率 * 不命中开销
• 程序执行时间
  • CPU时间 = （CPU执行周期数 + 存储器停顿周期数） * 时钟周期时间
  • 存储器停顿时钟周期数 = “读”的次数 * 读不命中率 * 读不命中开销 + “写”的次数 * 写不命中率 * 写不命中开销
  • = 访存次数 * 不命中率 * 不命中开销
  • CPU时间 = IC * （CPI + 访存次数 / 指令数 * 不命中率 * 不命中开销） * 时钟周期时间
  • = IC * （CPI + 每条指令的平均访存次数 * 不命中率 * 不命中开销） * 时钟周期时间

三种类型的不命中#

• 强制性不命中

  • 当第一次访问一个块时，该块不在cache中，需从下一级存储器中调入cache，这就是强制性不命中（冷启动不命中，首次访问不命中）

• 容量不命中

  • 如果程序执行时所需的块不能全部调入cache中，则当某些块被替换后，若又重新被访问，就会发生不命中。

• 冲突不命中

  • 在组相联或直接映像cache中，若太多的块映像到同一组（块）中，则回出现该组中某个别块被别的块替换（即使别的组或块又空闲位置），然后又被重新访问的情况。（碰撞不命中）

• 结论

  • 相联度越高，冲突不命中越少
  • 强制性不命中和容量不命中不受相联度的影响
  • 强制性不命中不受cache容量的映像
  • 容量不命中随着容量的增加而减少

• 减少三种不命中的方法

  • 强制性不命中：增加块大小，预取（本身很少）
  • 容量不命中：增加容量（成本、抖动现象）
  • 冲突不命中：提高相联度（理想情况、全相联）

• 许多降低不命中率的方法回增加命中时间或不命中开销

增加cache块大小#

• 不命中率与块大小的关系
  • 对于给定的cache容量，当块大小增加时，不命中率开始下井，后来反而上升了
  • 原因
    • 一方面减少了强制性不命中
    • 另一方面，增加块大小回减少cache中的块的数目，所以增加冲突不命中
  • cache容量越大，使不命中率达到最低的块大小就越大
• 增加块大小：增加冲突，增加不命中开销

增加cache的容量#

• 增加成本
• 可能增加命中时间
• 一般在片外cache中用得比较多

提高相联度#

• 采用相联度超过16的方案实际意义不大
• 2:1cache经验规则
  • 容量位N的直接映像，cache的不命中率和容量位N/2的两路组相联cache的不命中率差不多相同
• 提高相联度是以增加命中时间位代价的

伪限量cache（列相联cache）#

多路组相联的低命中率和直接映像的命中速度

• 伪相联cache的优点
  • 命中时间小
  • 不命中率低
• 基本思想及工作原理
  • 在逻辑上把直接映像cache的空间上下分为两个区，对于任何一次访问，伪相联cache先按直接映像cache的方式去处理，若命中，则其访问过程与直接映像cache的情况一样。若不命中，则再去零一去相应位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。
• 快速命中与慢速命中
  • 要保证绝大多数命中都是快速命中
• 缺点：多种命中时间->CPU流水线复杂化

硬件预取#

• 指令和数据都可以预取
• 预取内容既可以放入cache，也可放在外缓冲器中
• 指令预取通常由cache之外的硬件完成
• 预取利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能

编译器控制的预取#

在编译时加入预取指令，在数据被用到之前发出预取请求

• 按照预取数据所存放的位置，可以把预取分为两种类型
  • 寄存器预取：把数据取到寄存器中
  • cache预取：指将数据取到cache中
• 按照预取的处理方式不同，可把预取分为
  • 故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常
  • 非故障性预取：在遇到这种情况时则不会发生异常，因为这是它会放弃预取，转变为空操作
• 在预取数据的同时，处理器应能继续执行，只有这样预取才又意义（非阻塞，不锁定cache）
• 编译器控制预取的目的：使执行指令和读取数据能重叠执行
• 每次预取需要花费一条指令的开销
  • 保证这种开销不超过预取所带来的收益
  • 避免不必要的预取（预取准，何时预取）

编译器优化#

• 基本思想：通过对软件进行优化来降低不命中率
• 程序代码和数据重组
  • 可以重新组织程序而不映像程序的正确性
    • 把一个程序中的过程重新排序，就可能会减少冲突不命中
    • 把基本块对齐，使得程序的入口点与cache块的起始位置对齐，就可以减少顺序代码执行时所发生的cache不命中的可能性（提高大cache块的效率）
  • 如果编译器知道一个分支指令很可能成功转移，那么就可以通过两步来改善空间局部性
    • 把转移目标出的基本快和紧跟着该分支指令后的基本快进行对调
    • 把该分支指令转换为操作语义相反的分支指令
  • 数据对存储位置的限制更少，更便于调整数据

“牺牲”cache#

• 基本思想
  • 在cache和它从下一级存储器调数据的通路之间设置一个全相联的小cache，称为“牺牲”cache，用于存放被替换出去的块（称为牺牲者），以备重用

采用两级cache#

• 性能分析 $平均访存时间 = 命中时间_{L1} + 不命中率_{L1} * 不命中开销_{L1}$ $不命中开销_{L1} = 命中时间_{L2} + 不命中率_{L2} * 不命中开销_{L2}$
• 局部不命中率与全局不命中率
  • 局部不命中率 = 该级cache的不命中次数 / 到达该级cache的访问次数
  • 全局不命中率 = 该级cache的不命中次数 / CPU发出的访存的总次数
  • $全局不命中率_{L2} = 不命中率_{L1} * 不命中率_{L2}$
  • 评价第二级cache的时候，应使用全局不命中率这个指标。它指出了在CPU发出的访存中，究竟又多大比例是穿过各级cache，最终到达存储器的。
• 采用两级cache时候，每条指令的平均访存停顿时间
  • $每条指令的平均访存停顿时间 = 每条指令的平均不命中次数_{L1}*命中时间_{L2} + 每条指令的平均不命中次数_{L2}*不命中开销$

第二级cache的参数#

• 容量
  • 第二级cache的容量一般比第一级大许多
• 相联度
  • 第二级cache可采用较高的相联度或伪相联方法
• 块大小
  • 第二季cache采用较大的块
  • 为减少平均访存时间，可以让容量较小的第一级cache采用较小的块，而容量较大的第二级cache采用较大的块

让读不命中优先于写#

写缓冲器：在写穿法的时候，一般也不是直接把数据写到内存上，而是写到一个写缓冲器中，等CPU写完以后写缓冲器中的内容又再写到主存上。但是这样会带来问题：

• cache中的写缓冲器导致存储器访问的复杂化
  • 在读不命中时，所读单元的最新值有可能还在写缓冲器中，尚未写入主存
• 解决方法（读不命中的处理）
  • 推迟对读不命中的处理，直至写缓冲器清空（缺点：读不命中的开销增加）
  • 检查写缓冲器的内容（没有冲突就继续读）

写缓冲合并#

写穿cache。依靠写缓冲来减少对下一级存储器写操作的时间。

• 如果写缓冲器为空，就把数据和相应地址写入该缓冲器
• 把这次的写入地址于写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据于该项合并，就叫做写缓冲合并

请求字处理技术#

• 请求字
  • 从下一级存储器调入cache的块中，只有一个字是立即需要的，这个字称为请求字
• 应尽早把请求字发送给CPU
  • 尽早重启动：调块时，从块的起始位置开始读起，一旦请求字到达，就立即发送给CPU，让CPU继续执行
  • 请求字优先：调块时，从请求字所在的位置

非阻塞cache技术#

• 非阻塞cache：cache不命中中时仍然允许CPU进行其它的命中访问
• 进一步提高性能
  • 多重不命中下命中
  • 不命中下不命中

虚拟cache#

• 物理cache
  • 使用物理地址进行访问的传统cache
  • 表示存储器中存放的是物理地址，进行地址检测也是用物理地址
  • 缺点：地址转换和访问cache串行进行，访问速度很慢
• 虚拟cache
  • 可以直接用虚拟地址进行访问的cache，表示存储器中存放的是虚拟地址，进行地址检测用的也是虚拟地址
  • 优点：再不命中时不需要进行地址转换，省去了地址转换的时间。即使不命中，地址转换和访问cache也是并行进行的，起速度比物理cache块很多
  • 清空问题
    • 解决方法：再地址标识中增加PID字段（进程标识符）
• 虚拟索引 + 物理标识
  • 优点：兼等虚拟cache和物理cache的好处
  • 局限性：cache容量受到限制

cache访问流水化#

基本原理#

• 页式存储器把空间划分为大小相同的块
• 段式存储器把空间划分为可变长的块
• 页是对空间的机械化分，而段是按程序的逻辑意义进行划分

快速地址转换技术#

• 地址变换缓冲器TLB
  • TLB是一个专用的告诉缓冲器，用于存放近期经常使用的页表项
  • TLB中的内容是页表部分内容的一个副本
  • TLB也利用了局部性原理
• TLB中的项由两部分构成：标识和数据
  • 标识中存放的是虚地址的一部分
  • 数据部分中存放的则是物理页帧号、有效位、存储保护信息、使用位、修改位等

可靠性模型#

可靠度R(t)，不可靠度F(t)，关系: $R(t) + F(t) = 1$

• 串联系统
  • 系统由n个部件串联而称，其中任何一个部件失效就引起系统的失效
  • 串联系统寿命等于其中最先失效部件的寿命
  • 若每个单元的可靠度分别为$R_1, ..., R_n$，且每个单元相互独立，则系统可靠度为$R_s = \prod _{i=1}^n R_i$
  • 想要提高串联系统的可靠性，就要提高单元可靠度，减少串联单元数目
• 并联系统
  • 系统由n个部件并联而称，当这n个部件都失效时才引起系统失效
  • 并联系统寿命等于其中最后失效部件的寿命
  • 若每个单元的可靠度分别为$R_1, ..., R_n$,且每个单元相互独立，则系统可靠度为$R_s = 1 - \prod _{i=1}^n (1-R_i)$
  • 想要提高并联系统可靠性，就要提高单元可靠度，增加并联单元数目
• 串并联系统，n代表串联倍数，m代表并联倍数
  • $R(t) = 1 - [1-R_i^n(t)]^m$
  • e.g. RAID01是串并联系统
• 并串联系统
  • $R(t) = [1-(1-R_i(t))^m]^n$
  • e.g. RAID10是并串联系统

RAID0#

• 非冗余磁盘真理，无冗余信息
• 严格来说不属于RAID系列
• 把数据切分称条带，以条带位单位交叉地分布存放到多个磁盘中

RAID1#

• 镜像磁盘，对所有磁盘数据提供一份冗余的备份
  • 每当数据写入磁盘时，将该数据也写入其镜像盘。在系统中所有的数据都有两份
• 特点
  • 能实现快速的读取操作
  • 对于写入操作，镜像的两个磁盘都要写入。但可以并行进行，而且不需要计算校验信息，所以其速度比某些级别的RAID快
  • 可靠性高，数据恢复很简单
  • 实现成本最高

RAID2#

• 存储器式的磁盘阵列（按汉明码的思路构建）

RAID3#

• 位交叉奇偶校验磁盘阵列
• 特点
  • 采用奇偶校验
    • 写数据时，为每行数据形成奇偶校验位并写入校验盘
    • 读出数据时，如果控制器发现某个磁盘出故障，就可以根据故障盘意外的所有其它盘中的正确信息恢复故障盘中的数据（通过异或运算实现）
  • 细粒度的磁盘阵列，即采用的条带宽度较小（可以式一个字节或一位）
    • 多个磁盘的并行访问
    • 不能同时进行多个I/O请求的处理
  • 只需要一个礁岩盘，校验空间开销比较小

RAID4#

• 块交叉就校验磁盘阵列
• 采用比较大的条带，以块为单位进行交叉存放和计算奇偶校验
  • 实现目标：能同时处理多个小规模访问请求
• 读写特点
  • 读取操作
    • 每次只需访问数据所在的磁盘
    • 仅在该磁盘出现故障时，才会去读礁岩盘，并进行数据重建
  • 写入操作
    • 假定：有3个数据盘和一个冗余盘
    • 写数据需要2次磁盘读和2次磁盘写操作

RAID3,4存在的问题 每次读写都必须读写校验盘压力太大，会成为读写速度的瓶颈

RAID5#

• 块交叉分布奇偶校验磁盘阵列
• 数据以块交叉的方式存于各盘，无专用冗余盘，校验信息均匀分布在所有磁盘上
• 重建与初始化
  • 重建：读出非故障盘上的数据，按照校验信息的计算方法得到故障盘上的数据，然后写入到新替换的盘上
  • 重构：重建的微观操作过程

RAID6#

• P+Q双校验磁盘阵列
• 特点
  • 校验空间开销是RAID5的两倍
  • 容忍两个磁盘出错
  • 应用越来越广

RAID10和RAID01#

• RAID10又称RAID1+0，先进行镜像，再进行条带存放
• RAID01先进行条带存放，再进行镜像

RAID的实现与发展#

• 实现盘阵列的方式主要有三种
  • 软件方式：阵列管理软件由主机来实现
    • 优点：成本低
    • 缺点：过多地占用主机时间，且打款指标上不去
  • 阵列卡方式：把RAID管理软件固化在I/O控制卡上，从而可不占用主机时间，一般用于工作站和PC机
  • 子系统方式：一种基于通用接口总线的开放式平台，可用于各种主机平台和网络系统

总线的设计#

• 总线设计存在很多技术难点
  • 一个重要原因：总线上信息传送的速度极大地受限于各种物理因素，如总线的长度、设备数目、信号强度灯
  • 另外，我们一方面需要I/O操作响应快，另一方面又要提高吞吐量，这可能造成设计需求上的冲突
• 设计总线时需要考虑的一些问题

• 分离事务总线（流水总线）
  • 在由多个主设备时，可以通过包交换来提高总线带宽
  • 基本思想
    • 将总线事务分成请求和应答两部分
    • 在请求和应答之间的空闲时间内，总线可以供其它的I/O使用，这样就不必再整个I/O过程中都独占总线
  • 分离事务总线有较高的带宽，但是它的数据传送延迟通常比独占总线方法大
• 同步总线
  • 同步总线的控制线中包含一个时钟，总线上所有设备的所有通信操作都以该时钟为基准
  • 优点：速度快、成本低
  • 缺点：
    • 由于时钟通过长距离传输后会扭曲，因而同步总线不能用于长距离的连接，特别是对于告诉同步总线来说，更是如此
    • 总线上的所有设备都必须以同样的时钟频率工作
  • CPU-存储器通常采用同步总线
• 异步总线
  • 没有同一的参考时钟，每个设备都有各自的定时方法
  • 采用握手协议
  • 不存在时钟扭曲和同步的问题，传输距离可以比较长
  • 很多I/O总线都采用异步总线
  • 同步总线通常比异步总线快
• 总线标准和实例
  • I/O总线标准：定义如何将设备于计算机进行连接的文档

与CPU的连接#

• I/O总线的物理连接方式有两种选择
  • 连接到存储器上
  • 连接到cache上
• I/O总线连接到存储器总线上的方式
  • 一种典型的组织结构
• CPU对I/O设备的编址有两种方式
  • 存储器映射I/O（也成为I/O设备统一编址）
    • 将一部分存储器地址空间分配给I/O设备，用load指令和store指令对这些地址进行读写将引起I/O设备的数据传输
    • 将一部分存储空间流出用于设备控制，对这一部分地址空间进行读写就是向设备发出控制命令
  • 给I/O设备独立编址
    • 需要再CPU中设置专用的I/O指令来访问I/O设备
    • CPU需要发出一个标志信号来表示所访问的地址是I/O设备的地址
• CPU与外部设备进行输入/输出的方式分为4种
  • 程序查询
  • 中断
  • DMA
  • 通道

DMA和虚拟存储器#

• DMA使用虚拟地址还是物理地址？
  • 使用物理地址进行DMA传输，存在以下两个问题
    • 对于超过一页的数据缓冲区，由于缓冲区使用的页面在物理存储器中不一定是连续的，所以传输可能会发生问题
    • 如果DMA正在存储器和缓冲区之间传输数据时，操作系统从存储器中移出（或重定位）一些页面，那么，DMA将会在存储器中错误的页面上进行数据传输
  • 解决方法
    • 使操作系统I/O在传输过程中确保DMA设备所访问的页面都位于物理存储器中，这些页面被称为”钉在了主存中“
    • “虚拟DMA”技术
      • 允许DMA设备直接使用虚拟地址，并在DMA期间由硬件将虚拟地址转换为物理地址
      • 在采用虚拟DMA的情况下，如果进程在内存中被移动，操作系统应该能够及时地修改响应的DMA地址表

I/O和cache数据一致性#

• Cache会使一个数据出现两个副本，一个在cache中，另一个在主存中
• I/O设备可以修改存储器中的内容
  • 把I/O连接到存储器上， 会出现以下情况
    • CPU修改了cache的内容后，由于存储器的内容跟不上cache内容的变化，I/O系统进行输出操作时所看到的数据是旧值（写穿cache没有这样的问题）
    • I/O系统进行输入操作后，存储器的内容发生了变化，但CPU在cache中所看到的内容依然是旧值
• 解决内容一致性问题的方法（不管cache是写穿还是写回）
  • 软件方法
    • 设法保证I/O缓冲器中的所有各块都不在cache中
    • 具体做法有两种
      • 把I/O缓冲器的页面设置为不可进入cache的，在进行输入操作时，操作系统总是把输入的数据放到该页面上
      • 在进行输入操作之前，操作系统先把cache中与I/O缓冲器相关的数据“赶出”cache，即把响应的数据块设置为无效状态
  • 硬件方法
    • 在进行输入操作时，检查响应的I/O地址（I/O缓冲器中的单元）是否在cache中（即是否有数据副本）
    • 如果发现I/O地址在cache中有匹配的项，就把响应的cache块设置为“无效”
  • 把I/O直接连接到cache上
    • 不会产生由I/O导致的数据不一致的问题
      • 所有I/O设备和CPU都能在cache中看到最新的数据
      • I/O会和CPU竞争访问cache，在进行I/O时，会造成CPU的挺短
      • I/O还可能会破坏cache中CPU访问的内容，因为I/O操作可能导致一些新数据被加入cache，而这些新数据可能在近期内并不会被CPU访问

串联系统#

• 假设n各部件的工作是相互独立的，第i个部件寿命为$T_i$，可靠度为$R_i=P\{T_i>t\}$，失效率为$\lambda _i(t)$
• $T=min(T_1, ..., T_n)$
• 可靠度$R(t) = P{T>t} = \pod R_i (t)$
• 即可靠度$R(t) = \pod _{i=1}^k R_i(t)$

并联系统#

• 假设n各部件的工作是相互独立的，第i个部件寿命为$T_i$，可靠度为$R_i=P\{T_i>t\}$，失效率为$\lambda _i(t)$
• $T=max(T_1, ..., T_n)$
• 可靠度$R(t) = P{T > t} = 1-\pod (1 - R_i(t)) = \pod_{i=1}^m(1-R_i(t))$
• 不可靠度$F(t) = \pod_{i=1}^m(F_i(t))$

互联网络的结构参数#

• 网络通常是用有向边或无向边连接有限个节点的图来表示
• 互联网的主要特性参数有
  • 网络规模N：网络中节点的个数
    • 表示该网络所能连接的部件的数量
  • 节点度d：与节点相连接的边数（通道数），包括入度和出度
    • 进入节点的边叫入度
    • 从节点出来的边叫出度
  • 节点距离：对于网络中的任意两个节点，从一个节点触发到另一个节点终止所需要跨越的边数的最小值
  • 网络直径D:网络中任意两个节点之间距离的最大值
    • 网络直径应尽可能的小
  • 等分宽度b：把由N各节点构成的网络切成节点数相同(N/2)的两半，在各种切法中，沿切口边数的最小值
    • 线等分宽度：$B=b \times w$
      • w为通道宽度（用位表示）
      • 该参数主要反映了网络最大流量
  • 对称性：从任何节点看到的拓扑结构都相同的网络称为对称网络
    • 对称网络的实现比较容易，也容易编程

几种基本的互连函数#

• 恒等函数：实现同号输入端和输出端之间的连接
  • $I(x_{n-1}...x_1x_0) = x_{n-1}...x_1x_0$
• 交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接
  • $E(x_{n-1}...x_{k+1}x_kx_{k-1}...x_0) = x_{n-1}...x_{k+1}\overline{x_k}x_{k-1}...x_0$
  • 主要用于构造立方体互连网络和各种超立方体互连网络
  • 共有$n=log_2 N$中互连函数（N位节点个数）
  • 当N=8，n=3时，可得到常用的立方体互连函数
    • $Cube_0(x_2x_1x_0)=x_2x_1\overline{x_0}$
    • $Cube_1(x_2x_1x_0)=x_2\overline{x_1}x_0$
    • $Cube_3(x_2x_1x_0)=\overline{x_2}x_1x_0$
• 均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）
  • 也称为混洗函数（置换）
  • $\sigma(x_{n-1}...x_0)=x_{n-2}...x_0x_{n-1}$
  • 即把输入端的二进制编号循环左移一位
  • $\sigma^{(n)}(X) = \sigma _{(n)}(X) = \sigma(X)$
  • $\sigma ^{(1)} = \sigma _{(1)}(X) = X$
  • 逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所有连接的输出端编号
• 碟式函数：把输入端的二进制编号的最高位于最低为互换位置，便得到输出端的编号
  • $\beta(x_{n-1}...x_1x_0) = x_0x_{n-2}...x_1x_{n-1}$
  • 第k个子函数：$\beta _{(k)}(x_{n-1}...x_kx_{k-1}x_{k-2}...x_1x_0)=x_{n-1}...x_kx_0x_{k-2}...x_1x_{k-1}$
    • 把输入端的二进制编号的低k位中的最高位与最低位互换
  • 第k个超函数：$\beta ^{(k)}(x_{n-1}x_{n-2}...x_{n-j+1}x_{n-k}x_{n-k-1}...x_1x_0)=x_{n-k}x_{n-2}...x_{n-k+1}x_{n-1}x_{n-k-1}...x_1x_0$
    • 把输入端的二进制编号位中的高k位中的最高位与最低位互换
  • $\beta ^{(n)}(X) = \beta _{(n)}(X) = \beta(X)$
  • $\beta ^{(1)} = \beta _{(1)}(X) = X$
• 反位序函数：将输入端二进制编号的位序颠倒过来得相应输出端的编号
  • $\rho(x_{n-1}x_{n-2}...x_1x_0)=x_0x_1...x_{n-2}x_{n-1}$
  • 第k个子函数：$\rho _{(k)}(x_{n-1}...x_kx_{k-1}x_{k-2}...x_1x_0)=x_{n-1}...x_kx_0x_1...x_{k-2}x_{k-1}$
    • 把输入端的二进制编号的低k位中各位的次序颠倒过来
  • 第k个超函数：$\rho ^{(k)}(x_{n-1}x_{n-2}...x_{n-k+1}x_{n-k}x_{n-k-1}...x_1x_0)=x_{n-k}x_{n-k+1}...x_{n-2}x_{n-1}x_{n-k-1}...x_1x_0$
    • 把输入的那的二进制编号的高k位中各位的次序颠倒过来
  • $\rho ^{(n)}=\rho _{(n)}(X) = \rho(X)$
  • $\rho ^{(1)}(X) = \rho _{(1)}(X) = X$
• 移数函数：将各输入端都错开一定的位置（模N）后连到输出端
  • $\alpha (x) = (x \pm k) mod N$
• PM2I函数
  • P和M分别表示加和减，2I表示$2^i$
    • 即“加减$2^i$”函数
  • 移数函数的一种，将各输入端都错开一定的位置（模N）后连接到输出端
  • $PM2_{+i}(x) = x + 2^i mod N$
  • $PM2_{-i}(x) = x - 2^i mod N$
  • PM2I互连网络供有2n个互连函数

单级立方体网#

• 该网络由立方体函数定义，立方体函数族有n个成员，$Cube_0, ..., Cube_{n-1}$
• 最坏情况下传输需对输入节点编号的全部n位取反，所以单级立方体网络直径是n，成本$N \cdot log_2 N$
• 立方体函数性质：结合律、交换律以及自反律

单级混洗——交换网#

• 该网络由混洗函数与交换函数定义
• 混洗函数定义
  • shuffle(j) = 2j mod (N-1), 当j < N-1
  • shuffle(j) = N-1, 当j = N-1
• 网络直径是2n-1,成本$N \cdot 2$

e.g. 当n=3的混洗网络还不足以构成一个连通图，所以还要加上一个$Cube_0$函数，才能偶构成完整的单级混洗——交换网络

单级加减$2^i$网#

• 该网络由PM2I函数定义，PM2I函数供有n对成员，分别是$PM2_{\pm 0}, PM2_{\pm 1}, ..., PM2_{\pm (n-1)}$
• 性质1：对相同的i值，$PM2_{+i}$与$PM2_{-i}$函数的传送路径相同，方向相反
• 性质2：$PM2_{+(n-1)} = PM2_{-(n-1)}$，所以单级PM2I网络实际只能实现2n-1种不同的置换
• 单级PM2I网络的直径是$\lceil \frac{n}{2} \rceil$
• 成本$N(2 \times log_2 N -1)$
• 该网络包含多个强连通子图（即除去若干边以后仍能保证任何一对节点互相可达），所以这2n个函数并不是实现互联网的最小集合。实际应用中，可以使用他们的一个子集来构造互连网。

总线网络#

• 由一组导线和插座构成，经常被i用来实现计算机系统中处理机模块、存储模块和外围设备之间的互连。
  • 每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送
  • 多个功能模块之间的竞争总线或时分总线
  • 特点：
    • 结构简单、实现成本低、带宽较窄
• 一种由总线连接的多处理机系统
  • 系统总线再处理机、I/O子系统、主存储器以及辅助存储设备（磁盘、磁带机）之间提供了一条公用通路
  • 设备总线通常设置再印刷电路板底板上。处理器板、存储器板和设备接口板都通过插座或电缆插入底板
• 解决总线带宽较窄问题：采用多总线或多层次的总线
  • 多总线：设置多条总线
    • 为不同的功能设置专用的总线
    • 重复设置相同功能的总线
  • 多层次的总线式按层次的架构设置速度不同的总线，使得不同速度的模块有比较适合的总线连接

交叉开关网络#

• 单级开关网络
  • 交叉点开关能在对偶（源、目的）之间形成动态连接，同时实现多个对偶之间的无阻塞连接
  • 带宽和互连特性最好
  • 一个$n \times n$的交叉开关网络，可以无则色地实现$n!$中置换
  • 对一个$n\times n$的交叉开关网络来说，需要$n^2$套交叉开关以及大量的连线。
• C.mmp多处理机的互连结构
  • 用16×16的交叉开关网络把16台处理机与16个存储模块连接在一起
  • 最多可同时实现16台处理机对16个不同存储模块的并行访问
    • 每个存储模块一次只能满足一台处理机的请求
    • 当多个请求要同时访问同一存储模块时，交叉开关就必须分解所发生的冲突，每一列只能接通一个交叉点开关。
    • 为了支持并行（或交叉）存储器访问，可以在同一行中接通一个交叉点开关

多级互连网络#

MIMD和SIMD计算机都采用多级互连网络MIN(Multistage Interconnection Network)

• 由a×b开关模块和级间连接构成的通用多级互连网络结构
• 每一级都用了多个a×b开关
  • a个输入和b个输出
  • 在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即$a=b=2^k$
  • 相邻各级开关之间都有固定的级间连接

多处理机cache一致性#

• 多处理机的cache一致性问题
  • 允许共享数据进入cache，就可能出现多个处理器的cache中都有同一存储块的副本。
  • 当其中某个处理对其cache中的数据进行修改后，就会使得其cache中的数据与其它cache中的数据不一致
• 存储器的一致性：如果对某个数据项的任何度操作均可得到其最新写入的值，则认为这个存储系统是一致的
  • 存储系统行为的两个不同方面
    • what：度操作得到的是什么值
    • when：什么时候才能将已写入的值返回给度操作
  • 存储器是一致的，当满足以下条件
    • 处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其它处理器对单元X进行写，则P读到的值总是前面写进去的值
    • 处理器P对单元X进行写之后，零一处理器Q对单元X进行读，读和写之间无其它写，则Q读到的值应位P写进去的值
    • 对同意单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各处理器的角度看来顺序都是相同的
  • 重要假设
    • 直到所有的处理器均看到了写的结果，这个写操作才算完成
    • 处理器的任何访存均不能改变写的顺序。即允许处理器对读进行重新排序，但必须以程序规定的顺序进行写。

实现一致性的基本方案#

• 在一致的多处理机中，cache提供两种功能
  • 共享数据的迁移：减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求
  • 共享数据的赋值：不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突
  • 一般情况下，小规模对处理机是采用硬件的方法来实现cache的一致性
• cache一致性协议：在多个处理器中用来维护一致性的协议
  • 关键：跟踪记录共享数据快的状态
  • 两类协议（采用不同技术跟踪共享数据状态）
    • 监听式协议(snooping)
      • 每个cache除了包含物理存储器中块的数据拷贝外，也保存着各块的共享状态信息
      • 所有cache都可以通过某种广播介质访问，所有cache控制器监听总线来判断它们是否有总线上请求的数据块
    • 目录式协议(directory)
      • 物理存储器中数据块的共享状态被保存位一个称为目录的地方。开销稍大于前者，但可用于实现更大规模的的多处理机。
• 采用两种方法来解决cache一致性问题
  • 写作废协议：在处理器对某数据项写入之前，保证它拥有对该数据项的唯一访问权（作废其它副本）
  • 写更新协议：当一个处理器对某数据项进行写入时，通过广播使其它cache中所有对应于该数据项的副本进行更新
  • 性能差异
    • 在对同一个数据进行多次写操作而中间无操作时，写更新协议需进行多次广播，而写作废协议之需要一次作废操作
    • 在对同一cache块的多个字进行操作时，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可（写操作是针对cache块的，写更新则是针对字/字节）
    • 考虑从一个处理器A进行写操作后到另一个处理器B能都读到该写入数据之间的延迟时间（写更新协议的延迟时间较小）

监听协议的实现#

• 监听协议的基本实现技术
  • 实现写作废协议的关键：使用广播介质执行作废（假定采用的是总线）
    • 当一个处理器cache响应本地CPU访问时涉及全局操作，cache控制器需取得总线访问权后，在总线上发相应消息。
    • 所有处理器都一直在监听总线，检测总线上的地址是否在它们的cache中。若在，则相应处理。
  • 写操作的串行化：由总线实现（获取总线控制权的顺序性）
• cache发送到总线上的消息主要有以下两种
  • RdMiss——读不命中
  • WtMiss——写不命中
  • 需要通过总线找到相应数据块的最新副本，然后调入本地cache中。
    • 写穿cache：因为所有写入的数据同时都被写回主存，所以从主存中总可以取到其最新的值
    • 写回cache：得到数据的最新值会困难一些，因为最新值可能在某个cache中，也可能在主存中（不用掌握）
  • 有的监听协议还增设了invalidate消息，用来通知其它各处理器作废其cache中相应的副本
    • 与WtMiss的区别：invalidate不引起调块
  • cache的标识(tag)可直接用来实现监听
  • 修改位——最新副本（写回法）
  • 作废一个块只需将其有效位置为无效
  • 给每个cache块增设一个共享位
    • “1”：该块是被多个处理器所共享
    • “0”：仅被某个处理器所独占
    • 块的拥有者：拥有该数据块的唯一副本的处理器
• 监听协议距离
  • 在每个节点内嵌入一个有限状态控制器
    • 该控制器根据来自处理器或总线的请求以及cache块的状态，做出相应的响应
  • 每个数据块的状态取以下3种状态中的一种
    • 无效(Ivalid): cache中该块的内容为无效
    • 共享(Shared): 该块可能处于共享状态
      • 在多个处理器中都有副本，这些副本都相同，且与存储器中响应的块相同
    • 已修改(Modified): 该块已经被修改过，并且还没写入存储器（块中的内容是最新的，系统中唯一的最新副本）

目录协议的基本思想#

• 广播和监听的机制使得监听一致性协议的可扩放性很差
• 寻找替代监听协议的一致性协议

即使用目录协议

• 目录协议
  • 目录：一种集中的数据结构。对于存储器中的每一个可以调入cache的数据块，在目录中设置一条目录项，用于记录该块的数据状态以及那些cache中有副本等相关信息
  • 特点
    • 对于任何一个数据块，都可以快速地在唯一的一个位置中找到相关的信息。这使一致性协议避免了广播操作
  • 位向量：记录哪些cache中有副本
    • 每一位对应于一个处理器
    • 长度与处理器的个数成正比
    • 由位向量指定的处理机的集合称为共享集S
  • 分布式目录
    • 目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的节点进行。
  • 最简单的实现方案：对于存储器中每一块都在目录中设置一项。目录中的信息量与M×N成正比。
    • M：存储器中存储块的总数
    • N：处理器的个数
    • 由于M=K×N，K是每个处理器中存储块的数量，所以如果K保持不变，则目录中的信息量就与$N^2$成正比
• 在目录协议中，存储块的状态有3种
  • 未缓冲：该块尚未被调入cache，所有处理器的cache中都没有这个块的副本
  • 共享：该块在一个或多个处理机上有这个块的副本， 且这些副本与存储器中的该块相同。
  • 独占：仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已经过时。
• 本地节点、宿主节点以及远程节点的关系
  • 本地节点：发出访问请求的节点
  • 宿主节点：包含所访问的存储单元及其目录项的节点
  • 远程节点：包含cache block的副本
• 在节点之间发送的消息
  • 本地节点发给宿主节点（目录）的消息
    • P：发出请求的处理机编号，K：所要访问的地址
    • RdMiss(P, K): 处理机P读取地址位K的数据时不命中，请求宿主节点提供数据（块），并要求把P加入共享集
    • WtMiss(P, K): 处理机P对地址K进行写入不命中，请求宿主节点提供数据，并使P成为所访问数据块的独占者
    • Invalidate(K): 请求向所拥有响应数据块副本（包含地址K）的远程cache发Invalidate消息，作废这些副本。
  • 宿主节点（目录）发送给远程节点的消息
    • Invalidate(K): 作废远程cache中包含地址K的数据块
    • Fetch(K): 从远程cache中取出包含地址K的数据块，并送到宿主节点。把远程cache中那个块的状态改为“共享”
    • Fetch&Inv(K): 从远程cache中取出包含地址K的数据块，并送到宿主节点。然后作废远程cache中的那个块。
  • 宿主节点发送给本地节点的消息
    • DReply(D): D表示数据内容。把从宿主存储器获得的数据返回给本地cache
  • 远程节点发送给宿主节点的消息
    • WtBack(K, D): 把远程cache中包含地址K的数据块写回到宿主节点中，该消息是远程节点对宿主节点发来的“取数据”或“取/作废”消息的响应。
  • 本地节点发送给被替换块的宿主节点的消息
    • MdSharer(P, K): 用于当本地cache中需要替换一个包含地址K的块、且该块未被修改过。这个消息发给该块宿主节点，请求它将P从共享集中删除。如果删除后共享集位空，则宿主节点还要将该块状态改为“未缓存”(U)
    • WtBack2(P, K, D): 用于当本地cache中需要替换一个包含地址K的块、且该块已经被修改过。这个消息发给该块宿主节点，完成两步：1. 写回该块；2. 进行与MdSharer相同操作

目录协议实例#

• 在基于目录的协议中，目录承担了一致性协议操作主要功能
  • 本地节点把请求发给宿主节点中的目录，再由目录控制器有选择的向远程节点发出相应小欧希
  • 发出的消息会产生两种不同类型动作
    • 更新目录状态
    • 使远程节点完成相应操作
• 目录的状态转换及相应的操作
  • 目录中存储器块的状态有3种
    • 未缓存
    • 共享
    • 独占
  • 位向量记录拥有其副本的处理器集合。该集合称为共享集合
  • 对于从本地节点发来的请求，目录所进行的操作包括
    • 向远程节点发送消息以完成相应的操作。这些远程节点由共享集合指出
    • 修改目录中该块的状态
    • 更新共享集合
  • 目录可能收到3中不同的请求
    • 读不命中
    • 写不命中
    • 数据写回
  • 当一个块处于未缓存状态时，对该块发出的请求及处理操作为
    • RdMiss(读不命中): 将所要访问的存储器数据送往请求方处理机，且该处理机成为该块的唯一共享节点，本块的状态编程共享
    • WtMiss(写不命中): 将所要访问的存储器数据送往请求方处理机，该块的状态变成独占，表示该块仅存在唯一的副本。其共享集合仅包含该处理机，指出该处理机是其拥有者。
  • 当一个块处于共享状态时，其在处理器中的数据是当前最新的，对该块发出的请求及其处理操作为
    • RdMiss: 将存储器数据送往请求方处理机，并将其加入共享集合
    • WtMiss: 将数据送往请求方处理机，对共享集合中所有的处理机发送作废消息，且将共享集改为仅含有该处理机，该块的状态变为独占
  • 当一个块处于独占状态时，该块的最新值保存在共享集合所指出的唯一处理机（拥有者）中
    • RdMiss: 将“取数据”的消息发送往拥有者处理机，将它所返回给宿主节点的数据写入存储器，并进而把该数据送回请求方处理机，将请求方处理机加入共享集合。此时共享集合中仍保留拥有者处理机（因为它仍然拥有一个可读副本）。该块状态变为共享。
    • WtMiss: 该块将拥有一个新的拥有者。给旧的拥有者处理机发送消息，要求它将数据块送回宿主节点写入存储器，然后再从该节点送给请求方处理机。同时还要求旧拥有者处理机中把该块作废。把请求处理机加入共享者集合，使之成为新的拥有者。该块的状态仍然是独占。
    • WtBack: 当一个块的拥有者处理机要从其cache中把该块替换出去时，必须将该块写回其宿主节点的存储器中，从而使存储器中相应的块中存放的数据是最新的（宿主节点实际成为拥有者）。该块的状态变成未缓冲，其共享集合为空。

目录的三种结构#

• 不同目录协议的主要区别主要有两个
  • 所这是的存储器块的状态及其个数不同
  • 目录的结构
• 目录协议分为3类
  • 全映像目录
  • 有限映像目录
  • 链式目录

多处理机的锁存储模型#

多处理机系统都用多个局部cache满足各处理机并行访存的需要，但对进程控制用的信号灯（或锁）来说，多副本就破坏了它们的唯一性，造成同一变量再不同处理机看来有不同值的后果。因此信号灯（锁）的管理需要遵循以下原则

• 读信号灯再当地cache进行，只要复件有效
• 写信号灯必须直接作用于主存元件，采用“写穿”策略
• 写过程有排它性，硬件推迟其它处理机的写请求
• 写完元件要通知所有其它cache中的复件作废，即“一写多废”，让其它处理机随后发生“读失效”或“写失效”
• 信号灯管理系统的时间开销主要来源于“读失效”和“写失效”，或称“总线事务处理”次数
• 探讨不同的锁管理机制，目的是在程序正确前提下，减少时间开销

基本硬件原语#

• 在多处理机中实现同步，所需要的主要功能是：

  • 一组能以原子操作的方式读出并修改存储单元的硬件原语。它们都能以原子操作的方式读/修改存储单元，并指出所进行的操作是否以原子的方式进行。
  • 通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。，

• 典型操作：原子交换EXCH(automic exchange)

  • 功能：将一个存储单元的值和一个寄存器值进行交换。建立一个锁，锁值：
    • 0：表示开的（可用）
    • 1：表示已上锁（不可用）
  • 处理器上锁时，将对应于该锁的存储单元的值于存放在某寄存器中的的1进行交换。
    • 如果返回值为1，别的处理器已经上了锁
    • 如果返回值为0，存储单元的值此时已经置换为了1，防止了别的进程竞争该锁
  • 实现同步的关键：交换操作的原子性

• 测试并置定(test_and_set)

  • 先测试一个存储单元的值，如果符合条件则修改其值

• 读取并加1(fetch_and_increment)

  • 返回存储单元的值并自动增加该值

• 使用指令对

  • LL(load linked 或 load locked)：读取“锁”单元原值到指定寄存器。注意该指令通常只访问cache
  • SC(store conditional)：一条特殊写指令，它首先再读“锁”单元，如果与LL所读值相同，则将指定寄存器中的新值送给“锁”单元，并返回只1表示成功，如果内容不同，直接返回0表示失败。
  • 指令顺序执行：
    • 如果由LL指明的存储单元的内容在SC对其进行写之前已被其它指令改写过，则第二条指令SC执行失败
    • 如果在两条指令件进行切换也会导致SC执行失败
  • SC将返回一个值来指出该指令操作是否成功
    • “1”：成功
    • “0”：不成功
  • LL返回该存储单元初始值

1
# implement fetch_and_increment
2
try:LL R2, 0(R1) # 把0(R1)中的值放入R2中
3
    ADD R2, R2, 1
4
    SC R2, 0(R1) # 再次读取0(R1)，如果和LL读取时候的值相同，则把R2中的值放入0(R1)，R2置1；如果0(R1)的值变化，不动0(R1)的内容，R2置0。
5
    BEQZ R2, try

用一致性实现锁#

• 采用多处理机的一致性机制来实现自旋锁
• 自旋锁：处理器环绕一个锁不停地请求获得该锁。适合：锁被占用的时间很少，再获得锁后加锁过程延迟很小
• 无cache一致性机制：在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求使用权。
  • e.g. 利用原子交换操作，并通过测试返回值二直到锁的使用情况。释放锁的时候，处理器只需简单地将锁置为0
• 机器支持cache一致性
  • 将锁调入cache，并通过一致性机制使锁值保持一致
  • 优点：
    • 可使“环绕”的进程只对本地cache中的锁（副本）进行操作，而不用在每次请求占用锁时都进行一次全局的存储器访问
    • 可利用访问锁时所具有的局限性，即处理机最近使用过的锁不久又会使用（减少为获得锁而花费的时间）
  • 改进自旋锁（获得第一条优点，避免写操作）：只对本地cache中锁的副本进行读取和检测，直到发现该锁已经被释放。然后，该程序立即进行交换操作，去跟在其它处理器上的进程征用该锁变量。

同步性能问题#

简单自旋锁不能很好地适应可扩缩性。大规模多处理机中，若所有的处理器都同时争用同一个锁，则会导致大量的争用和通信开销。

• 自旋锁的不足
  • 由于自旋锁的无序竞争，可能造成等待时间演唱，并且存在“不公平”的问题
    • 随着处理器个数的不断增加，自旋锁竞争性操作增加了系统负担，从而导致更长的等待时间
    • 一个处理器释放自旋锁时要通知等待中的所有处理器，将cache副本作废，那么集合距离上临近它的处理器可能会较先的更新cache，因而增大了获得自旋锁的纪律
  • 由于每个申请自旋锁的处理器均在全局变量slock上忙等待，系统总线将因为处理器件的cache同步而导致繁重的流量（即因读失效或写失效引起的cache调入、调出），从而降低了系统整体的性能。

amdahl公式#

在一个系统中，Fe表示可改进部分占用的比例，Se表示可改进部分可提升的比例，则系统加速比 $S_n = \frac{1}{(1 - Fe) + \frac{Fe}{Se}}$ 当有多个比例的时候，可以使用公式$S_n = \frac{1}{(1-\sum _i f_i) + \sum _i \frac{f_i}{S_i}}$，但是更推荐画出比例图以后手动计算一下。

CPU性能#

$CPU时间 = \frac{总时钟周期数}{时钟频率}$ 指令时钟数CPI(Cycles Per Instruction) $CPI = 总时钟周期数 \div InstructionCount$ 因此，CPU时间也可以改写为$CPU时间=CPI \times IC \div 时钟频率$

流水线性能指标#