周学海 xhzhou@ustc.edu.cn 0551-63601556, 63492149 中国科学技术大学 2018/9/16 计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63601556, 63492149 中国科学技术大学 中国科学技术大学.

Presentation on theme: "周学海 xhzhou@ustc.edu.cn 0551-63601556, 63492149 中国科学技术大学 2018/9/16 计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63601556, 63492149 中国科学技术大学 中国科学技术大学."— Presentation transcript:

1 周学海 xhzhou@ustc.edu.cn 0551-63601556, 63492149 中国科学技术大学
2018/9/16 计算机体系结构 周学海 , 中国科学技术大学 中国科学技术大学

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

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

4 技术发展趋势 Capacity Speed (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 Kb 250 ns Kb 220 ns Mb 190 ns Mb 165 ns Mb 145 ns Mb 120 ns 1000:1! 2:1! Here is a table showing you quantitatively what I mean by high density. In 1980, the biggest DRAM chip you can buy has around 64Kb on it and their cycle time is around 250ns. This year you can buy 64 Mb DRAMs chips, that is an order of magnitude bigger than those back in with a speed that is twice as fast. The general rule for DRAM has been quadruple in size every 3 years. We will talk about DRAM cycle time later today. For now, I want you to point out an important point: The logic speed of your processor is doubling every 3 years but the DRAM speed only gets 40% improvement every 10 years. This mean DRAM speed relative to your processor is getting slower every day. That is why we believe Memory System design will become more and more important in the future because getting to your DRAM will become one of the biggest bottlenecks. +2 = 28 min. (Y:08) (8 Gbi) 2018/9/16 计算机体系结构

5 Trends in DRAM 2018/9/16 计算机体系结构

6 微处理器与DRAM 的性能差异 Processor-DRAM Memory Gap (latency) Processor-Memory
Performance Gap Growing 2018/9/16 计算机体系结构

7 Microprocessor-DRAM性能差异
利用caches缓解微处理器与存储器性能上的差异 Microprocessor-DRAM 性能差异 time of a full cache miss in instructions executed 1st Alpha : 340 ns/5.0 ns =  68 clks x 2 or 136 instructions 2nd Alpha : 266 ns/3.3 ns =  80 clks x 4 or 320 instructions 3rd Alpha : 180 ns/1.7 ns =108 clks x 6 or 648 instructions 1st generation Latency 1/2 but Clock rate 3X and IPC is 3X Now move to other 1/2 of industry 2018/9/16 计算机体系结构

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

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

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

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

12 典型的存储器访问模式 2018/9/16 计算机体系结构

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

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

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

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

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

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

19 -review 浮点数流水线示例 (MIPS R4000) 存储系统的性能评估与优化 平均访存时间= 命中时间 + 失效率*失效开销
长流水线（浮点数流水线）引起的“相关”问题 长流水线中精确中断的处理方法 浮点数流水线的性能 RAW相关引起的性能损失是主要因素 浮点数流水线示例 (MIPS R4000) 存储系统的分层结构 目标：速度快、容量大、价格低的存储系统 局部性原理 存储系统涉及的基本概念：Block, 命中和失效，数据一致性等 Cache 和 VM 存储系统的性能评估与优化 平均访存时间= 命中时间 + 失效率*失效开销 2018/9/16 计算机体系结构

20 4.2 Cache基本知识 2018/9/16 计算机体系结构

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

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: block 12 can go anywhere Block no. Direct mapped: block 12 can go only into block 4 (12 mod 8) Block no. Set associative: block 12 can go anywhere in set 0 (12 mod 4) Set 1 2 3 Block no. Block-frame address Block no. 2018/9/16 计算机体系结构

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

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

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

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

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

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

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

30 直接映像Cache查找过程 2018/9/16 计算机体系结构

31 全相联Cache查找过程 2018/9/16 计算机体系结构

32 Example: 1 KB Direct Mapped Cache with 32 B Blocks
对于容量为 2 N 字节的cache: 最高(32-N)位部分 为 Cache Tag 最低M位为字节选择位 (Block Size = 2 M) Cache Index 1 2 3 : Cache Data Byte 0 4 31 Cache Tag Example: 0x50 Ex: 0x01 0x50 Stored as part of the cache “state” Valid Bit Byte 1 Byte 31 Byte 32 Byte 33 Byte 63 Byte 992 Byte 1023 Byte Select Ex: 0x00 9 Block address Let’s use a specific example with realistic numbers: assume we have a 1 KB direct mapped cache with block size equals to 32 bytes. In other words, each block associated with the cache tag will have 32 bytes in it (Row 1). With Block Size equals to 32 bytes, the 5 least significant bits of the address will be used as byte select within the cache block. Since the cache size is 1K byte, the upper 32 minus 10 bits, or 22 bits of the address will be stored as cache tag. The rest of the address bits in the middle, that is bit 5 through 9, will be used as Cache Index to select the proper cache entry. +2 = 30 min. (Y:10) 2018/9/16 计算机体系结构

33 Example: Set Associative Cache
N-way set associative: 每一个cache索引对应N个cache entries 这N个cache项并行操作 Example: Two-way set associative cache Cache index 选择cache中的一组 这一组中的两块对应的Tags与输入的地址同时比较 根据比较结果选择数据 Cache Index Valid This is called a 2-way set associative cache because there are two cache entries for each cache index. Essentially, you have two direct mapped cache works in parallel. This is how it works: the cache index selects a set from the cache. The two tags in the set are compared in parallel with the upper bits of the memory address. If neither tag matches the incoming address tag, we have a cache miss. Otherwise, we have a cache hit and we will select the data on the side where the tag matches occur. This is simple enough. What is its disadvantages? +1 = 36 min. (Y:16) Cache Tag Cache Data Cache Data Cache Block 0 Cache Tag Valid : Cache Block 1 : : : Compare Adr Tag Compare 1 Sel1 Mux Sel0 OR Cache Block Hit 2018/9/16 计算机体系结构

34 Q3：替换算法 主存中块数一般比cache中的块多，可能出现该块所对应的一组或一个Cache块 已全部被占用的情况，这时需强制腾出其中的某一块，以接纳新调入的块，替换 哪一块，这是替换算法要解决的问题： 直接映象，因为只有一块，别无选择 组相联和全相联有多种选择 替换方法 随机法（Random)，随机选择一块替换 优点：简单，易于实现 缺点：没有考虑Cache块的使用历史，反映程序的局部性较差，失效率较高 FIFO－选择最早调入的块 优点：简单 虽然利用了同一组中各块进入Cache的顺序，但还是反映程序局部性不够，因为 最先进入的块，很可能是经常使用的块 最近最少使用法（LRU) (Least Recently Used) 优点：较好的利用了程序的局部性，失效率较低 缺点：比较复杂，硬件实现较困难 2018/9/16 计算机体系结构

35 LRU和Random的比较（失效率） 观察结果（失效率） 相联度高，失效率较低。 Cache容量较大，失效率较低。
Data Cache misses per 1000 instructions comparing LRU, Random, FIFO replacement for several sizes and associativities. These data were collected for a block size of 64 bytes for the Alpha architecture using 10 SPEC2000 benchmarks. Five are from SPECint2000(gap, gcc, gzip, mcf and perl) and five are from SPECfp2000(applu, art, equake, lucas and swim) 观察结果（失效率） 相联度高，失效率较低。 Cache容量较大，失效率较低。 LRU 在Cache容量较小时，失效率较低 随着Cache容量的加大，Random的失效率在降低 2018/9/16 计算机体系结构

36 Q4: 写策略 程序对存储器读操作占26％， 写操作占9％ 大概率事件优先原则－优化Cache的读操作
写所占的存储器访问比例 9/( ) 大约为7％ 占访问数据Cache的比例： 9/(26+9) 大约为25% 大概率事件优先原则－优化Cache的读操作 Amdahl定律：不可忽视“写”的速度 “写”的问题 读出标识，确认命中后，对Cache写 （串行操作） Cache与主存内容的一致性问题 写策略就是要解决: 何时更新主存问题 2018/9/16 计算机体系结构

37 两种写策略 写直达法（Write through) 写回法 当发生写失效时的两种策略 优点：易于实现，容易保持不同层次间的一致性
缺点：速度较慢 写回法 优点：速度快，减少访存次数 缺点：一致性问题 当发生写失效时的两种策略 按写分配法(Write allocate)：写失效时，先把所写单元所在块调入 Cache，然后再进行写入，也称写时取（Fetch on Write)方法 不按写分配法（no-write allocate): 写失效时，直接写入下一级存储 器，而不将相应块调入Cache，也称绕写法（Write around) 原则上以上两种方法都可以应用于写直达法和写回法，一般情况下 Write Back 用Write allocate Write through 用no-write allocate 2018/9/16 计算机体系结构

38 Write-back, Write Allocate
2018/9/16 计算机体系结构

39 Write-Through, No Write Allocate
2018/9/16 计算机体系结构

40 03/15-Review 存储系统的性能指标：速度、容量和价格 Cache 4Q 平均访存时间=命中时间+失效率×失效开销 映射规则
查找方法 替换策略 写策略 2018/9/16 计算机体系结构

41 Alpha AX 21064 Cache结构（数据Cache)
基本技术特性 容量 8KB ，Block 32Bytes, 共256个Blocks，每个字为8个字节 直接映象 写直达法，写失效时，no-write allocate 方法 写缓冲：4个blocks 21064物理地址34位 21位tag##8位index ##5位块内偏移 Cache命中的步骤 读命中 写命中 Cache失效 Cache向CPU发暂停信号 块传送，21064 Cache与下一级存储器之间数据通路16字节，传送全部32 字节需要10个cycles 2018/9/16 计算机体系结构

42 Alpha AX 21064 Cache结构（数据Cache)
基本技术特性 Block 32bytes per Block, 共256个Block 直接映象 写直达法，写失效时，no-write allocate 方法 21064物理地址34位 21位tag##8位index ##5位块内偏移 Cache命中的步骤 读命中 写命中 Cache失效 Cache向CPU发暂停信号 块传送，21064Cache与下一级存储器之间数据通路16字节， 传送全部32字节需要10个cycles 2018/9/16 计算机体系结构

43 Alpha 21264 Data Cache 基本技术特征
Cache size: 64Kbytes Block size: 64-bytes Two-way 组相联 Write back, 写失效时，write allocate bits 虚拟地址，虚实映射为44-bits 的物理地址，也支持43-bits虚拟地址，虚实映 射为41-bits的物理地址 29位tags##9位index##6位 Block offset 2018/9/16 计算机体系结构

44 Alpha Data Cache 2018/9/16 计算机体系结构

45 Cache 性能分析 CPU time = (CPU execution clock cycles Memory stall clock cycles) x clock cycle time Memory stall clock cycles = (Reads x Read miss rate x Read miss penalty Writes x Write miss rate x Write miss penalty) Memory stall clock cycles = Memory accesses x Miss rate x Miss penalty Different measure: AMAT Average Memory Access time (AMAT) = Hit Time + (Miss Rate x Miss Penalty) Note: memory hit time is included in execution cycles. 2018/9/16 计算机体系结构

46 性能分析举例 Suppose a processor executes at
Clock Rate = 200 MHz (5 ns per cycle), Ideal (no misses) CPI = 1.1 50% arith/logic, 30% ld/st, 20% control Miss Behavior: 10% of memory operations get 50 cycle miss penalty 1% of instructions get same miss penalty CPI = ideal CPI + average stalls per instruction = 1.1(cycles/ins) + [ 0.30 (DataMops/ins) x 0.10 (miss/DataMop) x 50 (cycle/miss)] + [ 1 (InstMop/ins) x 0.01 (miss/InstMop) x 50 (cycle/miss)] = ( ) cycle/ins = 3.1 65% (2/3.1) of the time the proc is stalled waiting for memory! AMAT=(1/1.3)x[1+0.01x50]+(0.3/1.3)x[1+0.1x50]=2.54 指令命中时间为1，失效率为1%,失效开销为50，取指令所占比例100/(100+30) Load和store操作失效率为10%,失效开销为50，取指令所占比例30/(100+30) (1.5+.5)/( ) = 65% 2018/9/16 计算机体系结构

47 Example: Harvard Architecture
Unified vs Separate I&D (Harvard) Statistics (given in H&P): 16KB I&D: Inst miss rate=0.64%, Data miss rate=6.47% 32KB unified: Aggregate miss rate=1.99% Which is better (ignore L2 cache)? Assume 33% data ops  75% accesses from instructions (1.0/1.33) hit time=1, miss time=50 Note that data hit has 1 stall for unified cache (only one port) AMATHarvard=75%x(1+0.64%x50)+25%x(1+6.47%x50) = 2.05 AMATUnified =75%x(1+1.99%x50)+25%x( %x50)= 2.24 Proc I-Cache-1 Unified Cache-1 Cache-2 D-Cache-1 2018/9/16 计算机体系结构

48 假设：36%为数据传送类instructions
Missrate for 16kB inst-cache = (3.82/1000)/1 = 0.4% 16kb data-cache = (40.9/1000)/0.36 = 11.4% Missrate for 32kb unified = (43.3/1000)/(1+0.36) = 3.18% 2018/9/16 计算机体系结构

49 （1）假设平均失效率为2%，平均每条指令访存1.5次 （2）假设每1000条指令cache失效次数为30次
以顺序执行的计算机 UltraSPARC III为例. 假设Cache失效开销为100 clock cycles，所有指令忽略存储器停顿需要1个cycle, Cache失效可以用两种方式给出 （1）假设平均失效率为2%，平均每条指令访存1.5次 （2）假设每1000条指令cache失效次数为30次 分别基于上述两种条件计算处理器的性能 结论： CPUtime = IC * (1 + 2%*1.5*100 ) * T = IC * 4 * T (1) CPI越低，固定周期数的Cache失效开销的相对影响就越大 (2) 在计算CPI时，失效开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的失效开销会较大，其CPI中存储器停顿部分也就较大。 因此 Cache对于低CPI，高时钟频率的CPU来说更加重要 (2) 失效率 = （30/1000）/1.5 = 2% 2018/9/16 计算机体系结构

50 考虑不同组织结构的Cache对性能的影响:
B-19例题：直接映像Cache 和两路组相联Cache，试问他们对CPU性能的影响？先求平均访存时间，然后再计算CPU性能。分析时请用以下假设： （1）理想Cache(命中率为100%）情况下CPI 为2.0，时钟周期为2ns，平均每条指令访存1.4次 （2）两种Cache容量均为128KB，块大小都是64B （3）采用组相联时，由于多路选择器的存在，时钟周期增加到原来的1.35倍 （4）两种结构的失效开销都是65ns (在实际应用中，应取整为整数个时钟周期） （5）命中时间为1个cycle，128KB直接映像Cache的失效率为2.1%, 相同容量的两路组相联Cache 的失效率为1.9% （6）理想CPI为1.6 2018/9/16 计算机体系结构

51 失效开销与Out-of-Order执行的处理器
需要确定两个参数： Length of memory latency Length of latency overlap 例如：在 前面的例子中，若假设允许处理器乱序执行，则对于直接映射方式，假设30%的失效开销可以覆盖（overlap)，那么原来的70ns失效开销就变为49ns. 2018/9/16 计算机体系结构

52 -review Cache基本原理 4Q Cache性能分析
CPU time = (CPU execution clock cycles Memory stall clock cycles) x clock cycle time Memory stall clock cycles = (Reads x Read miss rate x Read miss penalty Writes x Write miss rate x Write miss penalty) Memory stall clock cycles = Memory accesses x Miss rate x Miss penalty Different measure: AMAT Average Memory Access time (AMAT) = Hit Time + (Miss Rate x Miss Penalty) 2018/9/16 计算机体系结构

53 Summary of performance equations in this chapter
2018/9/16 计算机体系结构

54 4.3 基本Cache优化方法 降低失效率 减少失效开销 缩短命中时间 1、增加Cache块的大小 2、增大Cache容量 3、提高相联度
5、使读失效优先于写失效 缩短命中时间 6、避免在索引缓存期间进行地址转换 2018/9/16 计算机体系结构

55 改进Cache 性能的方法 平均访存时间＝命中时间＋失效率×失效开销 从上式可知，基本途径 降低失效率 减少失效开销 缩短命中时间
2018/9/16 计算机体系结构

56 降低失效率 Cache失效的原因 可分为三类 3C 强制性失效 (Compulsory)
第一次访问某一块，只能从下一级Load，也称为冷启动或首次访问失效 容量失效（Capacity) 如果程序执行时，所需块由于容量不足，不能全部调入Cache， 则当某些块被替换后，若又重新被访问，就会发生失效。 可能会发生“抖动”现象 冲突失效（Conflict (collision)) 组相联和直接相联的副作用 若太多的块映像到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置)，然后又被重新访问的情况，这就属于冲突失效 2018/9/16 计算机体系结构

57 各种类型的失效率 2018/9/16 计算机体系结构

58 从统计规律中得到的一些结果 相联度越高，冲突失效就越小 强制性失效和容量失效不受相联度的影响 强制性失效不受Cache容量的影响
容量失效随着容量的增加而减少 符合2:1Cache经验规则 即大小为N的直接映象Cache的失效率约等于大小为N/2的两路 组相联的Cache失效率。 2018/9/16 计算机体系结构

59 减少3C的方法 从统计规律可知 增大Cache容量 增大块 通过预取可帮助减少强制性失效 对冲突和容量失效的减少有利 减缓强制性失效
可能会增加冲突失效（因为在容量不变的情况下，块 的数目减少了） 通过预取可帮助减少强制性失效 必须小心不要把你需要的东西换出去 需要预测比较准确（对数据较困难，对指令相对容易） 2018/9/16 计算机体系结构

60 增加块的大小 2018/9/16 计算机体系结构

61 块大小、容量对失效率的影响 Given: miss rates for different cache sizes & block sizes Memory latency = 80 cycles + 1 cycle per 8 bytes Latency of 16-byte block = = 82 clock cycles Latency of 32-byte block = = 84 clock cycles Latency of 256-byte block = = 112 clock cycles Which block has smallest AMAT for each cache size? 2018/9/16 计算机体系结构

62 块大小、容量对AMAT的影响 Solution: assume hit time = 1 clock cycle
Regardless of block size and cache size Cache Size = 4 KB, Block Size = 16 bytes AMAT = % × 82 = clock cycles Cache Size = 256 KB, Block Size = 256 bytes AMAT = % × 112 = clock cycles 2018/9/16 计算机体系结构

63 块大小、容量对AMAT的影响 降低失效率最简单的方法是增加块大小；统计结果如图所示
假定存储系统在延迟40个时钟周期后，每2个时钟周期能送出16个字节，即： 经过42个时钟周期，它可提供16个字节；经过44个四周周期，可提供32个字 节；依此类推。试根据图5-6列出的各种容量的Cache，在块大小分别为多少 时，平均访存时间最小？ 2018/9/16 计算机体系结构

64 块大小、容量的权衡 从统计数据可得到如下结论 分析 设计块大小的原则，不能仅看失效率
对于给定Cache容量，块大小增加时，失效率开始是下 降，但后来反而上升 Cache容量越大，使失效率达到最低的块大小就越大 分析 块大小增加，可使强制性失效减少（空间局部性原理） 块大小增加，可使冲突失效增加（Cache中块数量减少） 失效开销增大（上下层间移动，数据传输时间变大） 设计块大小的原则，不能仅看失效率 原因：平均访存时间 ＝ 命中时间＋失效率×失效开销 2018/9/16 计算机体系结构

65 提高相联度 8路组相联在降低失效率方面的作用已经和全相联一样有效 2:1Cache经验规则 提高相联度，会增加命中时间
容量为N的直接映象Cache失效率与容量为N/2的两路组相联Cache的失效 率差不多相同 提高相联度，会增加命中时间 2018/9/16 计算机体系结构

66 Victim Cache(1/2) 在Cache和Memory之间增加一个小的全相联 Cache 2018/9/16 计算机体系结构

67 Victim Cache(2/2) 基本思想 通常Cache为直接映象时冲突失效率较大 Victim cache采用全相联－失效率较低 Victim cache存放由于失效而被丢弃的那些块 失效时，首先检查Victim cache是否有该块，如果有就将该块 与Cache中相应块比较。 Jouppi (DEC SRC)发现，含1到5项的Victim cache对 减少失效很有效，尤其是对于那些小型的直接映象数据 Cache 。测试结果，项为4的Victim Cache能使4KB直 接映象数据Cache冲突失效减少20%-90% 2018/9/16 计算机体系结构

68 减少失效开销 减少CPU与存储器间性能差异的重要手段 基本手段： 平均访存时间＝命中时间＋失效率×失效开销
4、多级Cache技术(Multilevel Caches) 5、让读优先于写(Giving Priority to Read Misses over Writes) 2018/9/16 计算机体系结构

69 采用多级Cache 一级cache保持较小容量 增加二级cache 多级cache的优点
降低命中时间 降低每次访问的能耗 增加二级cache 减少与存储器的gap 减少存储器总线的负载 多级cache的优点 减少失效开销 缩短平均访存时间（AMAT） 较大容量的L2 cache可以捕捉许多L1 cache的失效 降低全局失效率 2018/9/16 计算机体系结构

70 多级包容性(multilevel inclusive)
L1 cache 的块总是存在于L2 cache中 浪费了L2 cache 空间，L2 还应当有存放其他块的空间 L1中miss, 但在L2中命中，则从L2拷贝相应的块到L1 在L1和L2中均miss, 则从更低级拷贝相应的块到L1和L2 对L1写操作导致将数据同时写到L1和L2 Write-through 策略用于L1到L2 Write-back 策略可用于L2 到更低级存储器，以降低存储总 线的数据传输压力 L2的替换动作（或无效)对L1可见 即L2的一块被替换出去，那么其在L1中对应的块也要被替换出去。 2018/9/16 计算机体系结构

71 多级不包容（Multilevel Exclusive）
L1 cache 中的块不会在L2 cache中，以避免浪费空间 在L1中miss, 但在L2中命中，将导致Cache间块的互换 在L1和L2中均miss, 将仅仅从更低层拷贝相应的块到L1 L1的被替换的块移至L2 L2 存储L1抛弃的块，以防后续L1还需要使用 L1到L2的写策略为 Write-Back L2到更低级cache的写策略为 Write-Back L1和L2的块大小可以相同也可以不同 Pentium 4 had 64-byte blocks in L1 but 128-byte blocks in L2 Core i7 uses 64-byte blocks at all cache levels (simpler) 2018/9/16 计算机体系结构

72 多级cache的性能分析 局部失效率：该级Cache的失效次数 / 到达该级Cache的访存次数
Miss rateL1 for L1 cache Miss rateL2 for L2 cache 全局失效率：该级Cache的失效次数/ CPU发出的访存总次数 Miss rateL1 × Miss rateL2 for L2 cache 全局失效率是度量L2 cache性能的更好方法 性能参数 AMAT = Hit TimeL1+Miss rateL1×Miss penaltyL1 Miss penaltyL1 = HitTimeL2 + Miss rateL2×Miss penaltyL2 AMAT = Hit TimeL1+Miss rateL1× (Hit TimeL2+Miss rateL2×Miss penaltyL2) 2018/9/16 计算机体系结构

73 L1 cache 失效率 对于I-Cache和D-Cache分开的L1 Cache
Miss RateL1 = %inst × Miss RateI-Cache + %data × Miss RateD-Cache %inst = Percent of Instruction Accesses = 1 / (1 + %LS) %data = Percent of Data Accesses = %LS / (1 + %LS) %LS = Frequency of Load and Store instructions 每条指令的L1 失效次数: Misses per InstructionL1 = Miss RateL1 × (1 + %LS) Misses per InstructionL1 = Miss RateI-Cache + %LS × Miss RateD-Cache 2018/9/16 计算机体系结构

74 具有二级Cache的AMAT举例 Problem: 计算AMAT Solution：
I-Cache 失效率 = 1%， D-Cache失效率 = 10% L2 Cache失效率 = 40% L1 命中时间 = 1 cycle ( I-Cache 和D-Cache相同） L2 命中时间 = 8 cycles， L2 失效开销 = 100 cycles Load + Store 指令频度 = 25% Solution： 平均每条指令访存次数 = 1+25% = 1.25 平均每条指令的失效次数 = 1%+25%× 10% = 0.035 L1的失效率= 0.035/1.25=0.028 L1的失效开销 = ×100 = 48 cycles AMAT = ×48 = 2.344 2018/9/16 计算机体系结构

75 -review 基本Cache优化方法 降低失效率： 引起失效的3C 1、增加Cache块的大小 2、增大Cache容量 3、提高相联度
减少失效开销 4、多级Cache 5、使读失效优先于写失效 缩短命中时间 6、避免在索引缓存期间进行地址转换 2018/9/16 计算机体系结构

76 Memory Stall Cycles Per Instruction
Memory Stall Cycles per Instruction = Memory Access per Instruction × Miss RateL1 × Miss PenaltyL1 = (1 + %LS) × Miss RateL1 × Miss PenaltyL1 = (1 + %LS) × Miss RateL1 × (Hit TimeL2 + Miss RateL2 × Miss PenaltyL2) = Misses per InstructionL1 × Hit TimeL2 + Misses per InstructionL2 × Miss PenaltyL2 Misses per InstructionL1 = (1 + %LS) × Miss RateL1 Misses per InstructionL2 = (1 + %LS) × Miss RateL1 × Miss RateL2 2018/9/16 计算机体系结构

77 两级Cache的性能 Solution： Problem: 程序运行产生1000个存储器访问
I-Cache misses = 5, D-Cache misses = 35, L2 Cache misses = 8 L1 Hit = 1 cycle, L2 Hit = 8 cycles, L2 Miss penalty = 80 cycles Load + Store frequency = 25%, CPIexecution = 1.1 (perfect cache) 计算memory stall cycles per instruction 和有效的CPI 如果没有L2 cache, 有效的CPI是多少？ Solution： L1 Miss Rate = (5 + 35) / 1000 = 0.04 (or 4% per access) L1 misses per Instruction =0.04 × ( ) = 0.05 L2 misses per Instruction =(8 / 1000) × 1.25 = 0.01 Memory stall cycles per Instruction =0.05 × × 80 = 1.2 CPIL1+L2 = = 2.3, CPI/CPIexecution = 2.3/1.1 = 2.1x slower CPIL1only = × 80 = 5.1 (worse) 2018/9/16 计算机体系结构

78 不同大小的L2cache对应的执行时间 2018/9/16 计算机体系结构

79 Miss rates versus cache size for multilevel caches
2018/9/16 计算机体系结构

80 两级Cache的一些研究结论 在L2比L1大得多得情况下，两级Cache全局失效率和容量与第二级Cache相同的单级Cache的失效率接近
容量：一般很大，可能没有容量失效，只有强制性失效和冲突失效 相联度对第二级Cache的作用 Cache可以较大，以减少失效次数 多级包容性问题：第一级Cache中的数据是否总是同时存在于第二级Cache中。 如果L1和L2的块大小不同，增加了多级包容性实现的复杂性 2018/9/16 计算机体系结构

81 多级Cache举例 Given the data below, what is the impact of second-level cache associativity on its miss penalty? Hit timeL2 for direct mapped = 10 clock cycles Two-way set associativity increases hit time by 0.1 clock cycles to 10.1clock cycles Local miss rateL2 for direct mapped = 25% Local miss rateL2 for two-way set associative = 20% Miss penaltyL2 = 100 clock cycles 结论：提高相联度，可减少第一级Cache的失效开销 第二级Cache特点：容量大，高相联度，块较大，重点减少失效次数。 练习：Appendix B B10 若采用多级包容inclusive hierarchy, 在L1中发生失效 1、访问L2 2、如果在L2中命中，则从L2中调入相应的块到L1中，同时，L1中要换出的块 存放到L2中（如果L2中不存在该丢弃的块，何时出现这种情况？答，当L2中的块大小大于L1中的块大小时 ？？？） 3、如果在L2中没命中，则从 Memory中调入对应的块到L1和L2，同时，L1中要换出的块 存放到L2中（如果L2中不存在该丢弃的块，何时出现这种情况？） 4、在这两种情况下，如果在L2中存储L1中换出的块导致L2的换出动作，那么L1必须检查L2换出的块是否在L1中，如果该块在L1中，则需要invalidated 该块。 若采用多级互斥exclusive hierarchy, 在L1中发生失效 2、如果在L2中命中，则从L2中调入对应的块到L1中，同时，将L2中该对应块置为失效(invalidated), 将L1中换出的块写到L2中（可能L2中不存在该L1丢弃的块） 3、如果在L2中没命中，则从Memory中调入对应的块到L1,同时，将L2中该对应块置为失效(invalidated), 将L1中换出的块写到L2中（可能L2中不存在该L1丢弃的块） 无论是inclusive 还是exclusive， 如果L1中被丢弃的块是脏块，则L1中被丢弃的块必须写入L2中。 2018/9/16 计算机体系结构

82 让读优先于写图示 2018/9/16 计算机体系结构

83 让读失效优先于写 由于读操作为大概率事件，需要读失效优先，以提高性能
Write-Through Cache ->Write Buffer (写缓冲)，特别对写直达法更有效 Write Buffer: CPU不必等待写操作完成，即将要写的数据和地址送到Write Buffer后，CPU继续作其他操作。 写缓冲导致对存储器访问的复杂化 在读失效时写缓冲中可能保存有所读单元的最新值，还没有写回 例如，直接映射、写直达、512和1024映射到同一块。则 SW R3, 512(R0) LW R1, 1024(R0) 失效 LW R2, 512(R0) 失效 解决问题的方法 推迟对读失效的处理，直到写缓冲器清空，导致新的问题——读失效开销增大。 在读失效时，检查写缓冲的内容，如果没有冲突，而且存储器可访问，就可以继续处理读失效 写回法时，也可以利用写缓冲器来提高性能 把脏块放入缓冲区，然后读存储器，最后写存储器 Write-Back Cache ->Victim Buffer 被替换的脏块放到了victim buffer 在脏块被写回前，需要处理读失效 问题: victim buffer 可能含有该读失效要读取的块 Solution: 查找victim buffer，如果命中直接将该块调入Cache 2018/9/16 计算机体系结构

84 Copyright © 2011, Elsevier Inc. All rights Reserved.
缩短命中时间 虚拟地址Cache VS. 物理地址Cache Figure B.16 Miss rate versus virtually addressed cache size of a program measured three ways: without process switches (uniprocess), with process switches using a process-identifier tag (PID), and with process switches but without PIDs (purge). PIDs increase the uniprocess absolute miss rate by 0.3% to 0.6% and save 0.6% to 4.3% over purging. Agarwal [1987] collected these statistics for the Ultrix operating system running on a VAX, assuming direct-mapped caches with a block size of 16 bytes. Note that the miss rate goes up from 128K to 256K. Such nonintuitive behavior can occur in caches because changing size changes the mapping of memory blocks onto cache blocks, which can change the conflict miss rate. Copyright © 2011, Elsevier Inc. All rights Reserved.

85 Copyright © 2011, Elsevier Inc. All rights Reserved.
虚拟地址转换与Cache定位 并行 8 Figure B.17 The overall picture of a hypothetical memory hierarchy going from virtual address to L2 cache access. The page size is 16 KB. The TLB is two-way set associative with 256 entries. The L1 cache is a direct-mapped 16 KB, and the L2 cache is a four-way set associative with a total of 4 MB. Both use 64-byte blocks. The virtual address is 64 bits and the physical address is 40 bits. Copyright © 2011, Elsevier Inc. All rights Reserved.

86 2018/9/16 计算机体系结构

87 4.4 高级Cache优化方法 缩短命中时间 增加Cache带宽 减小失效开销 降低失效率 通过并行降低失效代价或失效率
2、路预测方法 增加Cache带宽 3、Cache访问流水化 4、无阻塞Cache 减小失效开销 5、多体Cache 6、关键字优先和提前重启 7、合并写 降低失效率 8、编译优化 通过并行降低失效代价或失效率 9、硬件预取 10、编译器控制的预取 2018/9/16 计算机体系结构

88 1、Small and simple first level caches
The University of Adelaide, School of Computer Science 16 September 2018 1、Small and simple first level caches Small and simple first level caches 容量小，一般命中时间短，有可能做在片内 另一方案，保持Tag在片内，块数据在片外，如DEC Alpha 第一级Cache应选择容量小且结构简单的设计方案 Critical timing path: 1) 定位组(tag), 确定tag的位置 2) 比较tags, 3) 选择正确的块 Direct-mapped caches can overlap tag compare and transmission of data 数据传输和tag 比较并行 Lower associativity reduces power because fewer cache lines are accessed 简单的Cache结构、可有效减少tag比较的次数，进而降低功耗 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

89 L1 Size and Associativity
The University of Adelaide, School of Computer Science 16 September 2018 L1 Size and Associativity Access time vs. size and associativity 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

90 L1 Size and Associativity
The University of Adelaide, School of Computer Science 16 September 2018 L1 Size and Associativity Energy per read vs. size and associativity 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

91 The University of Adelaide, School of Computer Science
16 September 2018 2、Way Prediction 为改进命中时间，预测被选中的路(way) 预测错误会导致更长的命中时间 预测的准确性 90%+ for two-way 80%+ for four-way I-cache比D-cache具有更好的准确性 90年代中期第一次用于MIPS R10000 用于ARM Cortex-A8 Way Prediction方法也可降低功耗：直接预测要 访问的块 也称“路选择”“Way selection” 可有效降低功耗，但一旦预测错误会有更长的命中时间 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

92 高级Cache优化方法 缩短命中时间 增加Cache带宽 减小失效开销 降低失效率 通过并行降低失效代价或失效率
2、路预测方法 增加Cache带宽 3、Cache访问流水化 4、无阻塞Cache 减小失效开销 5、多体Cache 6、关键字优先和提前重启 7、合并写 降低失效率 8、编译优化 通过并行降低失效代价或失效率 9、硬件预取 10、编译器控制的预取 2018/9/16 计算机体系结构

93 The University of Adelaide, School of Computer Science
16 September 2018 3、Pipelining Cache 实现Cache访问的流水化 提高Cache的带宽，有利于采用高相联度的缓存 L1 cache的访问由多个时钟周期构成 Pentium: 1 cycle Pentium Pro – Pentium III: 2 cycles Pentium 4 – Core i7: 4 cycles IBM Power7：3 cycles 缺点：增加流水线的段数 增加了分支预测错误造成的额外开销 增加了Load指令与要使用其结果的指令间的latency 增加了I-Cache和D-Cache的延时 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

94 2018/9/16 计算机体系结构

95 2018/9/16 计算机体系结构

96 The University of Adelaide, School of Computer Science
16 September 2018 4、Nonblocking Caches 允许在Cache失效下继续命中 在Cache失效时，CPU无需stall 主要用于乱序执行和多线程处理器 Hit under a Miss 减少有效的失效开销 增加Cache的带宽 Hit under Multiple Misses 针对多个未解决的Cache失效 可能会更多地减少有效的失效开销 增加了Cache控制器的复杂性 存储系统可以支持多个失效时的存储服务 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

97 Nonblocking Cache Timeline
2018/9/16 计算机体系结构

98 Effectiveness of Non-Blocking Cache
2018/9/16 计算机体系结构

99 Miss Status Holding Register (MSHR)
相同的块可以包含多个未解决的Load/Store 失效 可以有多个未解决的块地址 失效可以分为 Primary: 第一次发起存取请求时的失效块 Secondary: 在后续过程中的失效 Structural Stall miss： MSHR 硬件资源耗尽 2018/9/16 计算机体系结构

100 NonBlocking Cache Operation
当Cache失效时，检查MSHR是否有匹配的块地址 如果有，为该地址分配新的load/store 表项 如果没有，分配新的MSHR和load/store表项 如果所有MSHR资源都分配完，则Stall（结构相关） 当从底层传输Cache块时 处理该块中的Load和Store指令引起的失效 Load：根据block offset从该块中装载数据到寄存器 Store：根据block offset将数据写入该块指定位置 完成该块所有的失效的Load/Store后，释放MSHR中的 对应表项 2018/9/16 计算机体系结构

101 Multi-Ported Cache Dual-Ported Data Cache
两个地址端口（每个Cycle支持两条load/store 指令） 在现代处理器中保持较高的指令吞吐率 True Multi-ported Cache Design 所有的控制和数据通路在Cache中是多份的 显著地增加了Cache的面积和访问时间 Multi-Banked Cache 将cache组织成多个banks 每个bank是一个端口 可以并行访问不同的Bank 2018/9/16 计算机体系结构

102 The University of Adelaide, School of Computer Science
16 September 2018 5、Multibanked Caches 将Cache组织为多个独立的banks，以支持并行访问 ARM Cortex-A8 supports 1-4 banks for L2 Intel i7 supports 4 banks for L1 and 8 banks for L2 根据块号进行多体交叉编址 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

103 03/22-review 高级Cache优化方法 缩短命中时间 增加Cache带宽 减小失效开销 降低失效率 通过并行降低失效代价或失效率
2、路预测方法 增加Cache带宽 3、Cache访问流水化 4、无阻塞Cache 减小失效开销 5、多体Cache 6、关键字优先和提前重启 7、合并写 降低失效率 8、编译优化 通过并行降低失效代价或失效率 9、硬件预取 10、编译器控制的预取 2018/9/16 计算机体系结构

104 6、Critical Word First, Early Restart
The University of Adelaide, School of Computer Science 16 September 2018 6、Critical Word First, Early Restart 关键字优先 首先请求CPU所需要的字 请求字一到达就发给CPU，使其继续执行，同时从存 储器中调入其他字 提前重启 请求字的顺序不变 通常在块比较大时，这些技术才有效 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

105 The University of Adelaide, School of Computer Science
16 September 2018 7、Merging Write Buffer 在向写缓冲器写入地址和数据时，如果写缓冲器中存在被修改过的块，就检查其地址，看看本次写入数据的地址是否与写缓冲器内的某个有效块地址匹配，如果匹配，就把新数据与该块合并，称为“合并写” 可以缓解由于写缓冲满而造成的CPU停顿 不适用于I/O地址空间？？ No write buffering Write buffering 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

106 8、编译器优化 无需对硬件做任何改动，通过软件优化降低失效率 研究从两方面展开： 减少指令失效，重新组织程序（指令调度）而不影响程序的正确性
减少数据失效 减少指令失效，重新组织程序（指令调度）而不影响程序的正确性 Mc-Farling 的研究结果：通过使用profiling信息来判断指令组间可能发生的冲突，并将指令重新排序以减少失效。 研究表明： 容量为2KB, 块大小为 4Bytes的直接映象Icache，通过使用指令调度可以使失效率降低50％。容量增大到 8KB, 失效率可降低75％ 在有些情况下，当能够使某些指令不进入ICache时，可以得到最佳性能。即使不这样做，优化后（指令调度）的程序在直接映象Cache中的失效率也低于未优化程序在同样大小的8路组相联Cache中的失效率。 减少数据失效，主要通过优化来改善数据的空间局部性和时间局部性，基本方法为： 数据合并 内外循环交换，循环融合 分块 2018/9/16 计算机体系结构

107 编译器优化方法举例之一：数组合并 // Original Code for (i = 0; i < N; i++)
a[i] = b[i] + c[i]; d[i] = a[i] + b[i] * c[i]; Blocks are replaced in first loop then accessed in second // After Loop Fusion for (i = 0; i < N; i++) { } Revised version takes advantage of temporal locality 2018/9/16 计算机体系结构

108 编译器优化方法举例之二：内外循环交换 /* Before */ for (j = 0; j < 100; j = j+1) for (i = 0; i < 5000; i = i+1) x[i][j] = 2 * x[i][j]; /* After */ 2018/9/16 计算机体系结构

109 N3次操作，产生的存储器访问次数为: 2N3+N2
编译器优化方法举例之三：分块 (1/2) /* Before */ for (i = 0; i < N; i = i+1) for (j = 0; j < N; j = j+1) { r = 0; for (k = 0; k < N; k = k + 1) r = r + y[i][k]*z[k][j]; x[i][j] = r; }; N3次操作，产生的存储器访问次数为: 2N3+N2 2018/9/16 计算机体系结构

110 编译器优化方法举例之三：分块 (2/2) /* After */ for (jj = 0; jj < N; jj = jj+B) for (kk = 0; kk < N; kk = kk+B) for (i = 0; i < N; i = i+1) for (j = jj; j < min(jj+B,N); j = j+1) { r = 0; for (k = kk; k < min(kk+B,N); k = k + 1) r = r + y[i][k]*z[k][j]; x[i][j] = x[i][j] + r; }; 2018/9/16 计算机体系结构

111 9、Hardware Prefetching
CPU在执行当前块代码时，硬件预取下一块代码 CPU可能马上就要执行这块代码，这样可以降低或消除Cache的访问失效 当块中有控制指令时，预取失效 预取的指令可以放在Icache中，也可以放在其他地方（存取速度比Memory块的地方） AXP21064失效时，取2块指令块 目标块放在Icache，下一块放在ISB(指令流缓冲）中 如果访问的块在ISB中，取消访存请求，直接从ISB中读，并发出对下一指令块的预取访存请求 Jouppi研究结果：块大小为16字节，容量为4KB的直接映象Cache，1个块的指令流缓冲器，可以捕获15％－25％的失效，4个块 ISB可捕获50％的失效，16块ISB可捕获72％的失效 2018/9/16 计算机体系结构

112 硬件预取 预取数据 出发点：CPU访问一块数据，可能马上要访问下一块数据 Jouppi研究结果：块大小16字节，4KB直接映象Cache， 1Block DSB－25％ 4Block DSB － 43％ Palacharla和Kessler 1994年研究 一个具有两个64KB四路组相联(Icache, Dcache)的处理器来说，8Blocks流缓冲器能够捕获其50％－70％的失效 举例：Alpha AXP21064采用指令预取技术，其实际失效率是多少？若不采用指令预取技术，Alpha AXP 21064的指令Cache必须为多大才能保持平均访存时间不变？ 假设当指令不在指令Cache中，在预取缓冲区中找到时，需要多花1个时钟周期。 假设预取命中率为25%，命中时间为1个时钟周期，失效开销为50个时钟周期 8KB指令Cache的失效率为1.10%，16KB指令cache的失效率为0.64% AMAT（预取）= 命中时间+失效率*预取命中率*1+失效率*（1-预取命中率）*失效开销 注意：预取是利用存储器的空闲带宽，而不是与正常的存储器操作竞争。 2018/9/16 计算机体系结构

113 The University of Adelaide, School of Computer Science
16 September 2018 硬件预取 Fetch two blocks on miss (include next sequential block) Pentium 4 Pre-fetching 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

114 10、Compiler Prefetching（1/2)
在ISA中增加预取指令，让编译器控制预取 预取的种类 寄存器预取 : 把数据取到R中 Cache预取：只将数据取到Cache中，不放入寄存器 故障问题 两种类型的预取可以是故障性预取，也可以是非故障性预取 所谓故障性预取指在预取时若出现虚地址故障，或违反保护权限，就会有异常发生 非故障性预取，如导致异常就转化为空操作 只有在预取时，CPU可以继续执行的情况下，预取才有意义 Cache在等待预取数据返回的同时，可以正常提供指令和数据，称为非阻塞Cache或非锁定Cache 2018/9/16 计算机体系结构

115 由编译器控制预取 （2/2) 循环是预取优化的主要目标 失效开销较小时，Compiler简单的展开一两次，调度好预取与执行的重叠
失效开销较大时，编译器将循环体展开多次，以便为较远的循 环预取数据 由于发出预取指令需要花费一条指令的开销，因此要避免不必 要的预取 重点放在那些可能导致失效的访问 举例1：P93（70） （Hennessy & Patterson 5th /中译本） 举例2：P94（71）（Hennessy & Patterson 5th/中译本） 2018/9/16 计算机体系结构

116 举例1 Example ：For the code below, determine which accesses are likely to cause data cache misses. Next, insert prefetch instructions to reduce misses. Finally, calculate the number of prefetch instructions executed and the misses avoided by prefetching. Let’s assume we have an 8 KB direct-mapped data cache with 16-byte blocks, and it is a write-back cache that does write allocate. The elements of a and b are 8 bytes long since they are double-precision floating-point arrays. There are 3 rows and 100 columns for a and 101 rows and 3 columns for b. Let’s also assume they are not in the cache at the start of the program. for (i = 0; i < 3; i = i+1) for (j = 0; j < 100; j = j+1) a[i][j] = b[j][0] * b[j+1][0]; 2018/9/16 计算机体系结构

117 for (j = 0; j < 100; j = j+1) { prefetch(b[j+7][0]); /
for (j = 0; j < 100; j = j+1) { prefetch(b[j+7][0]); /* b(j,0) for 7 iterations later */ prefetch(a[0][j+7]); /* a(0,j) for 7 iterations later */ a[0][j] = b[j][0] * b[j+1][0];}; for (i = 1; i < 3; i = i+1) prefetch(a[i][j+7]); /* a(i,j) for +7 iterations */ a[i][j] = b[j][0] * b[j+1][0];} 2018/9/16 计算机体系结构

118 举例2 Example ： Calculate the time saved in the example above. (1) Ignore instruction cache misses and assume there are no conflict or capacity misses in the data cache. (2) Assume that prefetches can overlap with each other and with cache misses, thereby transferring at the maximum memory bandwidth. (3) Here are the key loop times ignoring cache misses: The original loop takes 7 clock cycles per iteration, the first prefetch loop takes 9 clock cycles per iteration, and the second prefetch loop takes 8 clock cycles per iteration (including the overhead of the outer for loop). A miss takes 100 clock cycles. 2018/9/16 计算机体系结构

119 cache -review 10 种高级优化方法 基本优化方法 扩大Cache容量 增大Cache块 提高相联度 Victim Cache
AMAT = Hit TimeL1+Miss rateL1× (Hit TimeL2+Miss rateL2×Miss penaltyL2) 让读失效优先于写写失效 10 种高级优化方法 2018/9/16 计算机体系结构

120 The University of Adelaide, School of Computer Science
16 September 2018 Summary 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

121 -review 10 种高级优化方法 基本优化方法 扩大Cache容量 增大Cache块 提高相联度 Victim Cache
AMAT = Hit TimeL1+Miss rateL1× (Hit TimeL2+Miss rateL2×Miss penaltyL2) 让读失效优先于写写失效 10 种高级优化方法 2018/9/16 计算机体系结构

122 The University of Adelaide, School of Computer Science
16 September 2018 Summary 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

123 4.5 存储器技术与优化 存储器的访问源 存储器性能指标 种类：DRAM和SRAM 取指令、取操作数、写操作数和I/O 容量、速度和每位价格
访问时间（Access Time) 存储周期（Cycle Time) 种类：DRAM和SRAM Memory: DRAM, Cache: SRAM Time Access Time Cycle Time 2018/9/16 计算机体系结构

124 Column Decoder & Sense Amplifiers
DRAM DRAM 破坏性读：读后需要重新写回,必须要周期性的刷新 每位1个 transistor 地址线复用: Lower half of address: column access strobe (CAS) Upper half of address: row access strobe (RAS) SRAM 每位6个transistors 只需较低的功率来保持位状态 Row Address Decoder Col. 1 Col. 2M Row 1 Row 2N Column Decoder & Sense Amplifiers M N N+M bit lines word lines Memory cell (one bit) D Data 2018/9/16 计算机体系结构

125 DRAM Packaging (Laptops/Desktops/Servers)
Address lines multiplexed row/column address Clock and control signals Data bus (4b,8b,16b,32b) DRAM chip ~12 ~7 DIMM (Dual Inline Memory Module) contains multiple chips with clock/control/address signals connected in parallel (sometimes need buffers to drive signals to all chips) Data pins work together to return wide word (e.g., 64-bit data bus using 16x4-bit parts) 2018/9/16 计算机体系结构 CS252 S05

126 Memory 优化 Some optimizations: Fast Page Mode Operation
N rows N cols DRAM Column Address M-bit Output M bits N x M “SRAM” Row Some optimizations: Fast Page Mode Operation Multiple accesses to same row Synchronous DRAM Added clock to DRAM interface Burst mode with critical word first Wider interfaces Double data rate (DDR) Multiple banks on each DRAM device 2018/9/16 计算机体系结构

127 The University of Adelaide, School of Computer Science
16 September 2018 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

128 The University of Adelaide, School of Computer Science
16 September 2018 Memory Optimizations 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

129 The University of Adelaide, School of Computer Science
16 September 2018 DDR: DDR2：Lower power (2.5 V -> 1.8 V)，Higher clock rates (266 MHz, 333 MHz, 400 MHz) DDR3：1.5 V，800 MHz DDR4：1-1.2 V，1600 MHz GDDR5 is graphics memory based on DDR3 Graphics memory: Achieve 2-5 X bandwidth per DRAM vs. DDR3 Wider interfaces (32 vs. 16 bit) Higher clock rate 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

130 3D-Stacked DRAM and Processing in Memory (PIM)
3D-stacked DRAM主要是为了解决Memory wall问题，最早在90年代提出，但当时工艺上不能很好解决堆叠问题。近些年来随着工艺上的进步，3D-Stacked 重新被变成热门方向 3D-stacked 在降低访存延迟方面优势很明显。Wire latency & pin count limitation.

131 The University of Adelaide, School of Computer Science
16 September 2018 Memory 功耗 Reducing power in SDRAMs: Lower voltage Low power mode (ignores clock, continues to refresh) 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

132 The University of Adelaide, School of Computer Science
16 September 2018 03/24-review 2018/9/16 计算机体系结构 Chapter 2 — Instructions: Language of the Computer

133 DRAM DRAM performance DRAM是由单个信息位构成的阵列 所有DRAM的访问至少三个阶段 Latency
通过行选择线和列选择线访问 所有DRAM都由这些阵列构成 不同的结构根据性能的需求选择的阵列数可能不 同 所有DRAM的访问至少三个阶段 Precharge，row access, column access DRAM performance Latency 处理器发出请求到所请求的第一组数据处理器输入 引脚到达所需要的cycle数 Bandwidth 第一组数据到达后，后续数据到达的速率

134 DRAM的演进 DRAM Fast-page-mode (FPM) Extended-data-out (EDO)
Burst-EDO (BEDO) Synchronous DRAM (SDRAM) Single-data-rate (SDR) SDRAM Double-data-rate (DDR) SDRAM, DDR2 Rambus DRAM (RDRAM) Direct Rambus DRAM (DRDRAM)

135 三种存储器组织方式 Wide: Interleaved: Simple:
CPU/Mux 1 word; Mux/Cache, Bus, Memory N words (Alpha: 64 bits & 256 bits) Interleaved: CPU, Cache, Bus 1 word: Memory N Modules (4 Modules); example is word interleaved Simple: CPU, Cache, Bus, Memory same width (32 bits) 2018/9/16 计算机体系结构

136 提高主存性能的方法-增大存储器的宽度（并行访问存储器）
最简单直接的方法 优点：简单、直接，可有效增加带宽 缺点 增加了CPU与存储器之间的连接通路的宽度，实现代价提高 主存容量扩充时，增量应该是存储器的宽度 写操作问题（部分写操作） 冲突问题 取指令冲突，遇到程序转移时，一个存储周期中读出的n条指令中，后面的指令将无用 读操作数冲突。一次同时读出的几个操作数，不一定都有用 写操作冲突。这种并行访问，必须凑齐n个字之后一起写入。如果只写一个字，必须先 把属于同一个存储字的数据读到数据寄存器中，然后在地址码的控制下修改其中一个字， 最后一起写。 读写冲突。当要读写的字在同一个存储字内时，无法并行操作。 冲突的原因 从存储器本身看，主要是地址寄存器和控制逻辑只有一套。 2018/9/16 计算机体系结构

137 采用简单的多体交叉存储器 一套地址寄存器和控制逻辑 存储器组织为多个体（Bank） 存储体的宽度，通常为一个字，不需要改变总线的宽度
目的：在总线宽度不变的情况下，完成多个字的并行读写 存储模块中所包含的体数，为避免访问冲突，基本原则为： 体的数目 >= 访问体中一个字所需的时钟周期数 例如：某一向量机的存储系统，CPU发出访存请求10个时钟周期后，CPU将从存储体0得到一个字，随后体0开始读该存储体的下一个字，而CPU依次从其余7个存储体中得到后继的7个字。在第18个周期，CPU 将需要存储体0提供下一个字，但该字要到第20个时钟周期才被读出，CPU只好等待。 缺陷：不能对单个体单独访问，对解决冲突没有帮助，逻辑上是一种宽存储器，对各个存储体的访问被安排在不同的时间段 2018/9/16 计算机体系结构

138 Increasing Bandwidth - Interleaving
Access Pattern without Interleaving: CPU Memory D1 available Start Access for D1 Start Access for D2 Memory Bank 0 Access Pattern with 4-way Interleaving: Memory Bank 1 CPU Memory Bank 2 Without interleaving, the frequency of our access will be limited by the DRAM cycle time. With interleaving, that is having multiple banks of memory, we can access the memory much more frequently by accessing another bank while the last bank is finishing up its cycle. For example, first we will access memory bank 0. Once we get the data from Bank 0, we will access Bank 1 while Bank 0 is still finishing up the rest of its DRAM cycle. Ideally, with interleaving, how quickly we can perform memory access will be limited by the memory access time only. Memory interleaving is one common techniques to improve memory performance. + 1 = 68 min. (Y:48) Memory Bank 3 Access Bank 1 Access Bank 0 Access Bank 2 Access Bank 3 We can Access Bank 0 again 2018/9/16 计算机体系结构

139 2018/9/16 计算机体系结构

140 地址映射方法 ( m个存储体，每个存储体容量为n)
2018/9/16 计算机体系结构

141 例题： 举例：假设某台机器的特性及其Cache的性能为： 试问多体交叉和增加存储器宽度对提高性能各有何作用？ 假设：送地址：4cycles,
块大小为1个字 存储器总线宽度为1个字 Cache失效率为3% 平均每条指令访存1.2次 Cache失效开销为32个时钟周期 平均CPI（忽略Cache失效）为2 试问多体交叉和增加存储器宽度对提高性能各有何作用？ 假设：送地址：4cycles, 每个字的访问时间（存取周期）为24cycles, 传送一个字的数据需要4cycles 2018/9/16 计算机体系结构

142 如果当把Cache块大小变为2个字时，失效率降为 2%；块大小变为4个字时，失效率降为1%。 根据前面给出的访问时间，求在采用2路、4路多体 交叉存取以及将存储器和总线宽度增加一倍时，性 能分别提高多少？ 在改变前的机器中，Cache块大小为一个字，其 CPI为： 2＋(1.2×3%×（4+24+4）)＝3.15 2018/9/16 计算机体系结构

143 当将块大小增加为2个字时，在下面三种情况下的CPI分别为： 32位总线和存储器，不采用多体交叉： 2＋(1. 2×2%×2×32)＝3
性能基本上随着总线宽度和交叉技术的应用程比例增长。 这是一个相对简单直观的例子。 2018/9/16 计算机体系结构

144 如果将块大小增加到4个字，则： 32位总线和存储器，不采用多体交叉： 2＋(1. 2×1%×4×32)＝3
如果将块大小增加到4个字，则： 32位总线和存储器，不采用多体交叉： 2＋(1.2×1%×4×32)＝ 位总线和存储器，采用多体交叉： 2＋(1.2×1%×(4＋24＋4×4)) ＝2.53 性能提高了25% 64位总线和存储器，不采用多体交叉： 2＋(1.2×1%×2×32)＝ 2.77 性能提高了14% 2018/9/16 计算机体系结构

145 4.6 虚拟存储器－基本原理 允许应用程序的大小，超过主存容量。目的是提高 存储系统的容量 帮助OS进行多进程管理
每个进程可以有自己的地址空间 提供多个进程空间的保护 可以将多个逻辑块映射到共享的物理存储器上 静态重定位和动态重定位 应用程序运行在虚地址空间 虚实地址转换对用户是透明的 虚拟存储管理的是主存－辅助存储器这个层面上 失效：页失效或地址失效 块：页或段 2018/9/16 计算机体系结构

146 2018/9/16 计算机体系结构

147 Cache与VM的区别 目的不同 替换的控制者不同 地址空间 下一级存储器 Cache是为了提高访存速度 VM是为了提高存储容量
VM的页失效通常由OS处理 一般页失效开销很大，因此替换算法非常重要 地址空间 VM空间由CPU的地址尺寸确定 Cache的大小与CPU地址尺寸无关 下一级存储器 Cache下一级是主存 VM下一级是磁盘，大多数磁盘含有文件系统，文件系统寻址与主存不同，它通 常在I/O空间中，VM的下一级通常称为SWAP空间 2018/9/16 计算机体系结构

148 虚拟存储器页式管理的典型参数与Cache的比较
2018/9/16 计算机体系结构

149 页式管理和段式管理 VM可分为两类：页式和段式 页式：每页大小固定 段式：每段大小不等 两者区别： 2018/9/16 计算机体系结构

150 2018/9/16 计算机体系结构

151 VM的四个问题 (1/2) 映象规则 查找算法－用附加数据结构 选择策略：低失效率和复杂的映象算法，还是简单的映射方法，高 失效率
由于失效开销很大，一般选择低失效率方法，即全相联映射 查找算法－用附加数据结构 固定页大小－用页表 VPN －> PPN Tag标识该页是否在主存 可变长段 －段表 段表中存放所有可能的段信息 段号 －>段基址 再加段内偏移量 可能存在许多小尺寸段 页表 页表中所含项数：一般为虚页的数量 功能: VPN－>PPN，方便页重新分配，有一位标识该页是否在内存 2018/9/16 计算机体系结构

152 VM的四个问题（2/2) 替换规则 写策略 LRU是最好的 但真正的LRU方法，硬件代价较大 用硬件简化，通过OS来完成
为了帮助OS寻找LRU页，每个页面设置一个 use bit 当访问主存中一个页面时，其use bit置位 OS定期复位所有使用位，这样每次复位之前，使用位的值 就反映了从上次复位到现在的这段时间中，哪些页曾被访 问过。 当有失效冲突时，由OS来决定哪些页将被换出去。 写策略 总是用写回法，因为访问硬盘速度很慢。 2018/9/16 计算机体系结构

153 2018/9/16 计算机体系结构

154 页面大小的选择 页面选择较大的优点 页面选择较大的缺点 减少了页表的大小 如果局部性较好，可以提高命中率 内存中的碎片较多，内存利用率低
进程启动时间长 失效开销加大 2018/9/16 计算机体系结构

155 Alpha VPN－>PPN 2018/9/16 计算机体系结构

156 TLB （Translation look-aside Buffer)
页表一般很大，存放在主存中。 导致每次访存可能要两次访问主存，一次读取页表项，一次读写数据 解决办法：采用 TLB TLB 存放近期经常使用的页表项，是整个页表的部分内容的副本。 基本信息： VPN##PPN##Protection Field##use bit ## dirty bit OS修改页表项时，需要刷新TLB，或保证TLB中没有该页表项的副本 TLB必须在片内 速度至关重要 TLB过小，意义不大 TLB过大，代价较高 相联度较高（容量小） 2018/9/16 计算机体系结构

157 TLB的典型参数 block size - same as a page table entry - 1 or 2 words
hit time - 1 cycle miss penalty - 10 to 30 cycles miss rate - .1% to 2% TLB size - 32 B to 8 KB 2018/9/16 计算机体系结构

158 举例：Alpha 21064的TLB 2018/9/16 计算机体系结构

159 Summary of Virtual Memory and Caches
2018/9/16 计算机体系结构