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

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