04 计算机体系结构--存储层次结构设计

1 .计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学 

2 . 基本流水线小结 • 流水线提高的是指令带宽（吞吐率），而不是单条指令的执行速度 • 相关限制了流水线性能的发挥 − 结构相关：需要更多的硬件资源 − 数据相关：需要定向，编译器调度 − 控制相关：尽早检测条件，计算目标地址，延迟转移，预测 • 编译器可降低数据相关和控制相关的开销 − Load 延迟槽 \Branch Branch 延迟槽 \Branch Branch 预测 • 增加流水线的级数会增加相关产生的可能性 • 异常，浮点运算使得流水线控制更加复杂 − 长流水线（浮点数流水线）引起的“相关”问题 − 长流水线中精确中断的处理方法 − 浮点数流水线的性能 : RAW 相关引起的性能损失是主要因素 • 浮点数流水线示例 (MIPS R4000)MIPS R4000) 中国科学技术大学 chapter3.2 

3 . 第 4 章 存储层次结构设计 • 4.1 存储层次结构 • 4.2 Cache 基本知识 • 4.3 基本的 Cache 优化方法 • 4.4 高级的 Cache 优化方法 • 4.5 存储器技术与优化 • 4.6 虚拟存储器－基本原理 18/9/22 计算机体系结构 3 

4 . 4.1 存储层次结构 • 存储系统设计是计算机体系结构设计的关键问题之一 − 价格，容量，速度的权衡 • 用户对存储器的“容量，价格和速度”要求是相互矛盾的 − 速度越快，每位价格就高 − 容量越大，每位价格就低 − 容量越大，速度就越慢 − 目前主存一般由 DRAM 构成 • Microprocessor 与 Memory 之间的性能差异越来越大 − CPU 性能提高大约 60%/yearyear − DRAM 性能提高大约 9 ％ /yearyear 18/9/22 计算机体系结构 4 

5 . 技术发展趋势 • Capacity Speed (MIPS R4000)latency) • Logic: 2x in 3 years 2x in 3 years • DRAM: 4x in 3 years 2x in 10 years • Disk: 4x in 3 years 2x in 10 years Year DRAMSize Cycle Time 1000:1! 2:1! 1980 64 Kb 250 ns 1983 256 Kb 220 ns 1986 1 Mb 190 ns 1989 4 Mb 165 ns 1992 16 Mb 145 ns 1995 64 Mb 120 ns 2009 8192 (8 Gbi) 18/9/22 计算机体系结构 5 

6 . Trends in DRAM 18/9/22 计算机体系结构 6 

7 . 微处理器与 DRAM 的性能差异 Processor-DRAM Memory Gap (latency) 100,000 10,000 Performance 1,000 Processor-Memory Processor Performance Gap 100 Growing 10 Memory 1 1980 1985 1990 1995 2000 2005 2010 Year 18/9/22 计算机体系结构 7 

8 . Microprocessor-DRAM 性能差异 • 利用 caches 缓解微处理器与存储器性能上的差异 • Microprocessor-DRAM 性能差异 − time of a full cache miss in instructions executed − 1st Alpha : 340 ns/year5.0 ns =  68 clks x 2 or136 instructions68 clks x 2 or136 instructions − 2nd Alpha :266 ns/year3.3 ns =  68 clks x 2 or136 instructions80 clks x 4 or320 instructions − 3rd Alpha :180 ns/year1.7 ns =108 clks x 6 or648 instructions 18/9/22 计算机体系结构 8 

9 . 存储系统的设计目标 Workload or Benchmark programs Processor reference stream <op,addr>, <op,addr>,<op,addr>,<op,addr>, . . . op: i-fetch, read, write Memory 通过优化存储系统的组织来使得针对典型应 $ 用平均访存时间最短 MEM 18/9/22 计算机体系结构 9 

10 . 基本解决方法：多级层次结构 • 多级分层结构 Mn M2 M1 ……….. CPU − M1 速度最快，容量最小，每位价格最高 − Mn 速度最慢，容量最大，每位价格最低 • 并行 • 存储系统接近 M1 的速度，容量和价格接近 Mn 18/9/22 计算机体系结构 10 

11 . 计算机系统的多级存储层次 L1 L2 L3 CPU C C C A A A Register C C C MEMORY I/O device H H H E E E Server 300ps 1ns 3-10ns 10-20ns 50-100ns 5-10ms 1000B 64KB 256K 2-4MB 4-16GB 4-16TB L1 L2 CPU C C A A Register C C MEMORY I/O device H H E E PMD 500ps 2ns 10-20ns 50-100ns 25-50μs 500B 64KB 256K 256-512MB 4-8GB 18/9/22 计算机体系结构 11 

12 . 存储层次工作原理： Locality! • 应用程序局部性原理 : 给用户 − 一个采用低成本技术达到的存储容量 . （容量大，价格低） − 一个采用高速存储技术达到的访问速度 . （速度快） • Temporal Locality (MIPS R4000) 时间局部性 ): => 保持最近访问的数据项最接近微处理器 • Spatial Locality (MIPS R4000) 空间局部性 ): 以由地址连续的若干个字构成的块为单位，从低层 复制到上一层 Lower Level To Processor Upper Level Memory Memory Blk X From Processor Blk Y 18/9/22 计算机体系结构 12 

13 . 典型的存储器访问模式 18/9/22 计算机体系结构 13 

14 . 存储层次结构涉及的基本概念 • Block − Block : 不同层次的 Block 大小可能不同 − 命中和命中率 − 失效和失效率 • 镜像和一致性问题 − 高层存储器是较低层存储器的一个镜像 − 高层存储器内容的修改必须反映到低层存储器中  数据一致性问题 • 寻址：不管如何组织，我们必须知道如何访问数据 • 要求：不同层次上块大小可以不同 − 在 L0 cache 可能以 Double, Words, Halfwords, 或 bytes − 在 L1cache 仅以 cache line 或 slot 为单位访问 − 在更低层… .. − 因此总是存在地址映射问题 − 物理地址格式 Block Frame Address + Block Offset 18/9/22 计算机体系结构 14 

15 . 存储层次的性能参数 (MIPS R4000)1/year2) 假设采用二级存储： M1 和 M2 − M1 和 M2 的容量、价格、访问时间分别为： S1 、 C1 、 TA1 S2 、 C2 、 TA2 Lower Level To Processor Upper Level Memory Memory Blk X From Processor Blk Y 18/9/22 计算机体系结构 15 

16 . 存储层次的性能参数 (MIPS R4000)2/year2) • 存储层次的平均每位价格 C − C=(MIPS R4000)C1*S1+C2*S2)/year(MIPS R4000)S1+S2) • 命中 (MIPS R4000)Hit): 访问的块在存储系统的较高层次上 − 若一组程序对存储器的访问，其中 N1 次在 M1 中找到所需数据， N2 次在 M2 中找到 数据 则 − Hit Rate （命中率） : 存储器访问在较高层命中的比例 H= N1/year(MIPS R4000)N1+N2) − Hit Time （命中时间） : 访问较高层的时间， TA1 • 失效 (MIPS R4000)Miss): 访问的块不在存储系统的较高层次上 − Miss Rate （失效） = 1 - (MIPS R4000)Hit Rate) = 1 – H ＝ N2/year(MIPS R4000)N1+N2) − 当在 M1 中没有命中时：一般必须从 M2 中将所访问的数据所在块搬到 M1 中，然后 CPU 才能在 M1 中访问。 − 设传送一个块的时间为 TB, 即不命中时的访问时间为： TA2+TB+TA1 = TA1+TM − TM 通常称为失效开销 • 平均访存时间 : − 平均访存时间 TA = HTA1+(MIPS R4000)1-H)(MIPS R4000)TA1+TM) = TA1+(MIPS R4000)1-H)TM 18/9/22 计算机体系结构 16 

17 . 常见的存储层次的组织 • Registers <-> Memory − 由编译器完成调度 • cache <-> memory − 由硬件完成调度 • memory <-> disks − 由硬件和操作系统（虚拟管理） − 由程序员完成调度 18/9/22 计算机体系结构 17 

18 . Cache Memory ? • 小而快（ SRAM ）的存储技术 − 存储正在访问的部分指令和数据 • 用于减少平均访存时间 − 通过保持最近访问的数据在处理器附近来挖掘时间局部 性 − 通过以块为单位在不同层次移动数据来挖掘空间局部性 • 主要目标： − 提高访存速度 − 降低存储系统成本 18/9/22 计算机体系结构 18 

19 . Cache 无处不在 • 体系结构中， Cache 无处不在 • 寄存器： Cache on variables • 一、二级 Cache ： Cache on memory • Memory ： Cache on hard disks − 存储最近执行的程序和数据 − Hard disks 可以视为主存的扩展（ VM ） • 分支目标缓存及分支预测缓存 − 缓存分支目标及预测信息 18/9/22 计算机体系结构 19 

20 . 4.2 Cache 基本知识 18/9/22 计算机体系结构 20 

21 . Q1 ：映象规则 • 当要把一个块从主存调入 Cache 时，如何放置问题 • 三种方式 − 全相联方式：即所调入的块可以放在 cache 中的任何位置 − 直接映象方式：主存中每一块只能存放在 cache 中的唯一位置 一般，主存块地址 i 与 cache 中块地址 j 的关系为： j ＝ i mod （ M) ， M 为 cache 中的块数 − 组相联映象：主存中每一块可以被放置在 Cache 中唯一的一个组中的任意一 个位置，组由若干块构成，若一组由 n 块构成，我们称 N 路组相联  组间直接映象  组内全相联 若 cache 中有 G 组，则主存中的第 i 块的组号 K K = i mod (MIPS R4000)G), 18/9/22 计算机体系结构 21 

22 .Q1: Where can a block be placed in the upper level? • Block 12 placed in 8 block cache: − Fully associative, direct mapped, 2-way set associative − S.A. Mapping = Block Number Modulo Number Sets Fully associative: Direct mapped: Set associative: block 12 can go block 12 can go block 12 can go anywhere only into block 4 anywhere in set 0 (12 mod 8) (12 mod 4) Block 01234567 Block 01234567 Block 01234567 no. no. no. Set Set Set Set Block-frame address 0 1 2 3 Block 1111111111222222222233 no. 01234567890123456789012345678901 18/9/22 计算机体系结构 22 

23 . Q1 的讨论 • N-Way 组相联：如果每组由 N 个块构成， cache 的 块数为 M ，则 cache 的组数 G 为 M/yearN • 不同相联度下的路数和组数 路数 组数 全相联 M 1 直接相联 1 M 其他组相联 1 < N <M 1<G<M − 相联度越高， cache 空间利用率就越高，块冲突概率就越 小，失效率就越低 − N 值越大，失效率就越低，但 Cache 的实现就越复杂，代 价越大 − 现代大多数计算机都采用直接映象，两路或四路组相联。 18/9/22 计算机体系结构 23 

24 . Q2(MIPS R4000)1/year2): 查找方法 • 在 CACHE 中每一 block 都带有 tag 域（标记域），标记 分为两类 − Address Tags ：标记所访问的单元在哪一块中，这样物理地址 就分为三部分： Address Tags ## Block index## block Offset 全相联映象时，没有 Block Index 显然 Address tag 越短，查找所需代价就越小 − Status Tags ：标记该块的状态，如 Valid, Dirty 等 Block Address Block Tag Index offset Set Select 计算机体系结构 18/9/22 Data Select 24 

25 . Q2 （ 2/year2) 查找方法 • 原则：所有可能的标记并行查找， cache 的速度至 关重要，即并行查找 • 并行查找的方法 − 用相联存储器实现，按内容检索 − 用单体多字存储器和比较器实现 • 显然相联度 N 越大，实现查找的机制就越复杂， 代价就越高 • 无论直接映象还是组相联，查找时，只需比较 tag ， index 无需参加比较 18/9/22 计算机体系结构 25 

26 . Tag 和数据阵列并行访问的逻辑结构 18/9/22 计算机体系结构 26 

27 .Tag 和数据阵列并行访问的流水线模式 18/9/22 计算机体系结构 27 

28 . Tag 和数据阵列串行访问的逻辑结构 18/9/22 计算机体系结构 28 

29 .Tag 和数据阵列串行访问的流水线模式 18/9/22 计算机体系结构 29