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

这一节是中国科学技术大学所讲授的计算机体系结构的存储器层次结构设计部分。这一节的主要内容有:1.存储层次结构 2 Cache基本知识 3 基本的Cache优化方法 4 高级的Cache优化方法 5 存储器技术与优化 6 虚拟存储器-基本原理。存储器部分是学习计算机系统的最重要的内容,这一节作者讲的是非常的仔细。
展开查看详情

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