计算机的设计思想、设计原理、设计技术。

1 知识要点

1.1 冯式结构的五个组成部分

运算器、控制器、存储器、输入设备、输出设备。

1.2 CPU 发展趋势

性能计算：

$CPUTime = \frac{Seconds}{Program} = \frac{Instruction}{Program} \cdot \frac{Cycles}{Instruction} \cdot \frac{Seconds}{Cycles}$

性能提升：

  1. 半导体技术：
    • 特征尺寸。
    • 时钟频率。
  2. 计算机体系结构：
    • 高级语言编译器、标准化的操作系统。
    • 指令更为简单的RISC(精简指令集)结构。
  3. 多核技术出现的原因
    • 通过堆积晶体管密度提高性能遇到瓶颈
    • 硬件多线程的并发已经存在一段时间了。虽然可以减少内存延迟，但是只有30%的提升
    • 如今将多个处理内核封装在一个芯片中来提升性能
  4. 两个1G多核处理器 VS 一个2G单核处理器
    • 前者在同时处理两个小于1G的任务时比后者要快
    • 后者在处理一个大于1G小于2G的任务时比前者要快
    • 后者成本要低
  5. 编程模型：SIMD VS MIMD。
    • SIMD发掘数据级并行
      • 矩阵运算
      • 图像和声音处理
    • SIMD比MIMD能耗效率高
    • SIMD数据操作只需要取一条指令
    • SIMD对个人移动设备(PMD)具有吸引力；MIMD一般用于商用计算机和大型服务器。
    • SIMD编程者对并行思维要求较低；MIMD反之
  6. 虚拟化技术的意义
    • CPU的虚拟化技术可以单CPU模拟多CPU并行，允许一个平台同时运行多个操作系统，并且应用程序都可以在相互独立的空间内运行而互不影响，从而显著提高计算机的工作效率

1.3 Flynn’s 分类

  1. 单指令流、单数据流(SISD)—{指令级并行(ILP)}
    • 解释：传统的顺序执行的单处理器计算机，其指令部件每次只对一条指令进行译码，并且只对一个操作部分分配数据。
    • 例子：Intel Pentium4
  2. 单指令流、多数据流(SIMD)—{数据级并行(DLP)}
    • 解释：以同步方式，在同一时间执行同一条指令。
    • 例子：向量体系结构、多媒体指令扩展、GPU
  3. 多指令流、多数据流(MIMD)
    • 解释：使用多个控制器来异步地控制多个处理器，从而实现空间上的并行性。
    • 例子：Intel Xeon e5345(Clovertown)
    • 紧耦合：MIMD；松耦合：MIPD
  4. 多指令流、单数据流(MISD)
    • 没有实现商业化(why?)：显然多条指令处理同一数据可能频繁出现冲突，处理效率非常低。

1.4 网络和存储技术

网络技术 速度 存储接口 速度
WAN T1 56K/s SCSI 5MB/s
以太网 10Mb/s Fast SCSI 10MB/s
快速以太网 100Mb/s WideSCSI 20MB/s
ATM/OC-3 155Mb/s Ultra SCSI 40MB/s
千兆以太网 1Gb/s 光纤路径 2Gb/s
Infiniband 40Gb/s 光纤路径 4 or 8Gb/s

网络比存储发展快！

1.5 内存系统

存储技术的目标：最大，最快，最便宜。

技术趋势：

  • 集成电路
    • 晶体管密度：25% year
    • 晶片尺寸：10-20% year
    • 晶体管数目：40-55% year
  • DRAM容量：单个25-40% year (slowing)
  • 闪存容量：50-60% year
    • 15-20X cheaper/bit than DRAM
  • 磁盘技术：40% year
    • 15-25X cheaper/bit than Flash
    • 300-500X cheaper/bit than DRAM

局部性原理：

  • 时间局部性：程序结构中的循环
  • 空间局部性：数组或记录

层次：SRAM，DRAM，DISK，FLASH MEMORY

  • 顶层{CPU内}：寄存器、Cache
  • 二层{主板内}：主存、Cache
  • 三层{主板外}：磁盘、光盘
  • 底层{离线}：磁带

1.6 Cache的使用问题

Cache：

  • 高速缓存，也指基于局部性原理来管理的存储器。

使用Cache的问题：

  1. 如果要访问的数据不在Cache中怎么办？
    • 要访问的数据不在Cache中会导致缺失，缺失则将需要的数据装入Cache中。
  2. 从主存中装入数据时装到Cache中的什么位置？
    • 直接映射
      • 每个主存地址对应到Cache的确定的位置
    • 全相联映射
      • 一个块可以放在Cache中的任何位置
      • 需要检索Cache中的所有项：并行比较器
    • 组相联映射
      • 每个块有n个位置可放的Cache称为n路组相联Cache;
      • 存储器中的一个块对应到Cache中唯一的组，但是可以放在组内的任意位置上
  3. 从主存中装入数据时一次装入多少数据？
    • 从cache到处理器：以字为单位；
    • 从主存到cache：以块为单位；块设为多大？
      • 4K & 64块；16K & 64块；64K & 256块；256K & 256块。
  4. 如何判断Cache中对应的位置是否为有效的数据？
    • 有效位，有效位设置时表示一个块是有效的
  5. 如果Cache装满了怎么办？
    • 先入先出法(FIFO)
    • 随机替换法(RAND)
    • 最近最少使用法(LRU)
      • LRU算法实现：使用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
  6. 写Cache时会有什么问题？
    • 写命中和写不命中
    1. 写回法
      • 写命中：只修改Cache内容，不立即写入主存，当被替换时才写入主存。
      • 写不命中：将内存中包含欲写块的内容装入Cache中并修改。
    2. 写直达法
      • 写命中：同时修改Cache和主存。
      • 写不命中：直接写入主存。
    3. 写一次法
      • 与写回法基本相同，只是第一次写命中时同时修改Cache和主存。

1.7 Cache的优化方法

访问缺失：

  • 强制缺失(第一次访问)
  • 容量缺失(因容量不够，块被移除，又被访问)
  • 冲突失效(重复访问的多个地址映射在Cache中的同一位置)

$AMAT = \text{命中时间} + \text{缺失率} * \text{缺失代价}$

  1. 更大的块
    • 强制缺失减少
    • 容量和冲突缺失增加，缺失代价增加
  2. 更大的Cache容量
    • 缺失率降低
    • 命中时间，功耗增加
  3. 更高的相关度
    • 冲突缺失减少
    • 命中时间增加，功耗增加
  4. 更多级Cache
    • 内存访问时间减少
  5. 读缺失优先级更高
    • 缺失代价降低
  6. 缓存索引避免地址转移
    • 减少命中时间

优化度量：命中时间，缺失率，缺失代价，缓存带宽和功耗。

1.8 存储访问模型

  • UMA(uniform memory access)模型
    • 物理存储器被所有节点共享
    • 所有节点访问任意存储单元的访问时间相同
    • 发生访存竞争时，仲裁策略平等对待每个节点
    • 每个节点的CPU可带有局部私有的高速缓存
    • 外围I/O设备也可以共享，且每个节点有平等的访问权力
  • NUMA(Non-Uniform Memory Access)模型
    • 物理存储器被所有节点共享，任意节点可以直接访问任意内存模块
    • 节点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他节点内存模块的3倍以上
    • 发生访存竞争时，仲裁策略对节点可能是不平等的
    • 各节点的CPU可带有局部私有高速缓存cache
    • 外围I/O设备也可以共享，但对各节点是不平等的

1.9 单CPU上常见的提升性能的方法和并行计算

提升性能方法：

  • 提高单个处理器的工作频率
  • Locality：L1/L2/L3 Cache
  • 多级流水线(提高CPU频率的利器)
  • 超标量执行(多条流水线并同时发送多条指令)
  • 乱序执行(指令重排)
  • 单指令流多数据SIMD
  • 超长指令字处理器(依赖于编译器分析)

单CPU主要的并行：指令级并行(ILP)

1.10 多线程的好处

  • 创建一个线程比创建一个进程的代价小
  • 线程的切换比进程间切换的代价小
  • 充分利用多处理器
  • 数据共享
  • 快速响应特性

1.11 Tomasulo’s 算法

三步骤:

  • 发射
    • 从指令队列中获取指令，如果RS(Registers)可用，则发射指令到RS；
    • 如果操作数可用，则发送数据至RS；
    • 发射级完成了重命名。
  • 执行
    • 若有一个或几个操作数未就绪，等待该操作数，并同时监控CDB(CommonDataBus)；
    • 当操作数可用，则存储至保留站；当所有操作数可用，则执行命令；
    • 执行级检查了是否存在RAM竞争。
  • 写结果
    • 将结果写入CDB，并从CDB写入目的寄存器及等待此结果的保留站；
    • 连续写入同一寄存器时，只有最后一次才能写入；
    • 消除了WAW(Write After Write)竞争。

1.12 仓库级计算机(WSC)

  • 提供互联网服务
    • 搜索、社交网络、在线地图、视频分享、在线购物、电子邮件、云计算、etc.
  • 不同于HPC“集群”
    • HPC集群有更高性能的处理器和互联网络
    • HPC集群强调线程级并行，WSC强调请求级并行
  • 不同于数据中心
    • 数据中心集中运行不同的机器和软件
    • 数据中心强调虚拟机，具有硬件异构型，为不同客户提供服务

1.13 批处理框架：MapReduce

  • Map：
    • 将程序员提供的函数应用于每条记录
    • 在数千台计算机上运行
    • 生成由键值对组成的中间结果
  • Reduce：
    • 收集上述分布式任务的输出，使用另一个函数应用于中间结果

1.14 MESI协议图

1.15 基准程序的类别

基准程序(Benchmarks)：

  • 衡量一个系统，可通过运行一个或一组真实应用
    • 应用程序要有代表性，覆盖现实世界中常见的情况
    • 应用程序负载(workload)也要有代表性，与实际情况比较吻合
  • 好的基准程序可以加速计算机的发展
    • 改进基准程序的性能应该对大多数程序有益
  • 好基准程序可以加速计算机的发展进程
    • 是有益于运行真实程序, 还是销售机器/发表论文?
  • 创造真正有益于真实程序的基准程序，而不是有益于基准程序的基准程序

类别：

  • 玩具(Toy)基准程序
    • 10-100行
    • 例如：sieve，puzzle，quicksort
  • 合成(Synthetic)基准程序
    • 试图匹配真正工作负载的平均频度
    • 例如：Whetstone，Dhrystone
  • 内核(Kernels)程序
    • 时间密集(Time critical excerpts)
    • 例如：Livemore loops，FFT，tree search
  • 真实程序(Actual workloads)
    • 例如：gcc，spice

1.16 性能评测方法

  1. 经验：使用系统的现有实例执行性能测试。
    • 前提条件：
      • 真实系统的存在
      • 不同程度的可测性设计
    • 针对对象：
      • 系统用户(应用需求)
      • 系统设计者(设计验证)
  2. 分析：对系统进行数学抽象，推导出描述系统性能的公式。
  3. 仿真：开发一个实现系统模型的计算机程序。通过运行计算机程序进行性能测试。
  4. 统计：开发系统的统计抽象，并通过分析或模拟得出统计性能。

1.17 三种流水线冲突/冒险(Hazard)

Hazard:指流水线遇到无法正确执行后续指令或执行了不该执行的指令

  • Structural Hazards(hardware resource conflicts)
    • 现象：同一部件同时被不同指令所使用
    • 解决方案：
      • 一个部件每条指令只能使用一次，且只能在特定周期使用
      • 设置多个部件，以避免冲突，如指令寄存器IM和数据寄存器DM分开，或寄存器读口和寄存器写口分开。
  • Data Hazards(data dependencies)
    • 现象：后面指令用到前面指令结果时，前面指令结果还没产生
    • 解决方案：
      • 采用转发(Forwarding/Bypassing)技术
      • load use 冒险需要一次阻塞(stall)
      • 编译程序优化指令顺序
  • Control(Branch) Hazards(changes in program flow)
    • 现象：转移或异常改变执行流程，顺序执行指令在目标地址产生前已被取出
    • 解决方案：
      • 采用静态或动态分支预测
      • 编译程序优化指令顺序(实现分支延迟)

1.18 数据冒险(Data Hazards)

解决方法：

  1. 硬件阻塞(stall)
  2. 软件插入“NOP”指令
  3. 合理实现寄存器堆的读/写操作
    • 前半时钟周期写，后半时钟周期读。若在同一个时钟内前面指令写入的数据正好是后面指令所读数据，则不会发生数据冒险
  4. 转发技术(Forwarding或Bypassing旁路)
    • load use 问题(需要一次阻塞stall)
  5. 编译优化：调整指令顺序

1.19 Load指令的5个阶段(MIPS结构为例)

第一阶段 第二阶段 第三阶段 第四阶段 第五阶段
Ifetch Reg/Dec Exec Mem Wr
  1. Ifetch(取指)：从指令存储器取指令并计算PC+4
    • 指令存储器、Addr
  2. Reg/Dec(取数和译码)：寄存器取数，同时对指令进行译码
    • 寄存器堆读口、指令译码器
  3. Exec(执行)：计算内存单元地址
    • 扩展器、ALU
  4. Mem(读存储器)：从数据存储器中
    • 数据存储器
  5. Wr(写寄存器)：将数据写到寄存器中
    • 寄存器堆写口

Tips:这里寄存器读口和写口可看成两个不同的部件

1.20 动态分支预测

一位预测状态图
一位预测状态图
二位预测状态图
二位预测状态图

比较：

  • 一位预测位：当连续两次的分支情况发生改变时，预测错误
  • 二位预测位：在连续两次分支发生不同时，只会有一次预测错误

一般采用二位预测位！

2 后记

2018年12月3日

战场，考场
聒噪，沉静
忐忑，镇定
顾盼，专心
窃喜，自信
得意忘形，波澜不惊
举世皆浊我独清
众人皆醉我独醒

——YvanZh