缓存（续）.

Presentation on theme: "缓存（续）."— Presentation transcript:

1 缓存（续）

2 分析右侧代码，假设： sizeof(int) = 4 数组x开始于内存地址0x0并以行顺序存储 缓存开始为空
除数组外，局部变量保存于寄存器中 回答下列问题： 假设缓存为512字节、直接映射、块大小为16字节。不命中率是多少？ 不命中率为100% 由于每次对x[1][i]的访问与前次对x[0][i]的访问冲突 如果将缓存大小加大一倍至1024字节，不命中率是多少？ 不命中率为25% 因为整个数组可放进缓存，因此不命中只会发生于每个新块中首个数组元素的冷不命中，而每个块包含4个数组元素，因此1/4=25% 假设缓存为512字节、2路组相联且使用LRU 替换策略、块大小为16字节。不命中率是多少？ 因为2路组相联使得x[1][i]和x[0][i]分别缓存于同一组的不同行中 ，因此不命中只会发生于每个新块中首个数组元素的冷不命中，因此1/4=25%

3 假设编写一函数用于清空显示屏幕，屏幕大小为640× 480 像素。计算机具有64 KB 直接映射的缓存，每行4字节。所用C结构如右图所示。
假设： sizeof(char) == 1，sizeof(int) == 4 数组buffer开始于内存地址0x0 缓存开始为空 除数组外，局部变量i、j、cptr、iptr等保存于寄存器中 右侧代码运行时会有多少比例的写操作不命中？ 25% 每一像素结构为4字节，因此每一缓存行包含一结构 因此，对每一结构会出现1次不命中，后跟3次命中

4 分析右侧代码，假设： sizeof(int) = 4 数组square开始于内存地址0x0并以行顺序存储 缓存初始为空，大小为2048字节，直接映射，块为32字节 除数组外，局部变量i、j等保存于寄存器中 回答下列问题： 写操作的总数是多少？ 1024 其中不命中的写操作的总数是多少？ 256 对每一结构，发生1次不命中，后跟3次命中

5 数组square开始于内存地址0x0并以行顺序存储 缓存初始为空，大小为2048字节，直接映射，块为32字节
分析右侧代码，假设： sizeof(int) = 4 数组square开始于内存地址0x0并以行顺序存储 缓存初始为空，大小为2048字节，直接映射，块为32字节 除数组外，局部变量i、j等保存于寄存器中 回答下列问题： 写操作的总数数多少？ 1024 其中不命中的写操作的总数是多少？ 256 第一个循环执行256次写操作，而每一缓存行包含2个结构，因此1/2命中，1/2不命中 第二个循环执行768次写操作。对（一缓存行中）每组2个结构，发生1次冷不命中，后跟5次命中。因此循环将遇到128次不命中 因此，总共 = 1024次写操作，其中 = 256次不命中

6 假设编写一函数用于清空显示屏幕，屏幕大小为640× 480 像素。计算机具有64 KB 直接映射的缓存，每行4字节。所用C结构如右图所示。
假设： sizeof(char) == 1，sizeof(int) == 4 数组buffer开始于内存地址0x0 缓存开始为空 除数组外，局部变量i、j、cptr、iptr等保存于寄存器中 下列代码运行时会有多少比例的写操作不命中？ 25% 下列代码运行时会有多少比例的写操作不命中？ 100%

7 对右图所示3个求和函数，假设计算机具有4KB直接映射缓存，每个内存块16字节，并且：
sizeof(int) == 4 数组a开始于内存地址0x 缓存开始为空 除数组外，局部变量i、j、sum等保存于寄存器中 计算缓存不命中率并填写下表: 25% 25% 100% 25% 50% 25%

8 第五讲：虚拟存储器（Virtual Memory）
虚拟地址空间、虚拟存储器的实现

9 缩写的含义 基本参数（按字节编址） N = 2n : 虚拟地址空间大小 M = 2m : 物理地址空间大小 P = 2p : 页大小
虚拟地址 (VA)中的各字段 TLBI: TLB index（TLB索引） TLBT: TLB tag（TLB标记） VPO: Virtual page offset （页内偏移地址） VPN: Virtual page number （虚拟页号） 物理地址(PA)中的各字段 PPO: Physical page offset (页内偏移地址) PPN: Physical page number（物理页号） CO: Byte offset within cache line（块内偏移地址） CI: Cache index（cache索引） CT: Cache tag（cache标记）

10 虚地址到物理地址的映射

11 页表 页表项示例

12 虚存与进程 虚存是每一进程具有独立的地址空间，同时支持不同进程对同一物理地址的共享访问。 虚存方便实现针对进程的页级内存访问保护。

13 页命中与页缺失处理流程

14 TLB - translation lookaside buffer

15 TLB命中与缺失

16 一个简化的存储系统举例 假定以下参数，则虚拟地址和物理地址如何划分？共多少页表项？
14-bit virtual addresses（虚拟地址14位） 12-bit physical address（物理地址12位） Page size = 64 bytes（页大小64B） 页表项数应为：214-6=256 13 12 11 10 9 8 7 6 5 4 3 2 1 VPO VPN Virtual Page Number Virtual Page Offset 11 10 9 8 7 6 5 4 3 2 1 PPO PPN Physical Page Number Physical Page Offset

17 一个简化的存储系统举例（续） 假定部分页表项内容（十六进制表示）如右：
– 007 006 1 16 005 004 02 003 33 002 001 28 000 Valid PPN VPN 1 0D 02F 11 02E 2D 02D – 02C 02B 09 02A 17 029 13 028 Valid PPN VPN 假定部分页表项内容（十六进制表示）如右： 假定TLB如下：16 个TLB项，4路组相联，则TLBT和TLBI各占几位？ 13 12 11 10 9 8 7 6 5 4 3 2 1 VPO VPN TLBI TLBT – 02 1 34 0A 0D 03 07 3 06 08 2 04 2D 00 09 Valid PPN Tag Set

18 一个简化的存储系统举例（续） 假定Cache的参数和内容（十六进制）如下：16 行，主存块大小为4B，直接映射，则主存地址如何划分？ 11
10 9 8 7 6 5 4 3 2 1 PPO PPN CO CI CT 03 DF C2 11 1 16 7 – 31 6 1D F0 72 36 0D 5 09 8F 6D 43 32 4 3 08 04 02 00 1B 2 15 23 99 19 B3 B2 B1 B0 V Tag Idx – 14 F D3 1B 77 83 1 13 E 15 34 96 04 16 D 12 C 0B B 3B DA 93 2D A 9 89 51 00 3A 24 8 B3 B2 B1 B0 V Tag Idx

19 一个简化的存储系统举例（续） 假设该存储系统所在计算机采用小端方式， CPU执行某指令过程中要求访问一个16位数据，给出的逻辑地址为0x03D4，说明访存过程。 VPN ___ TLBI ___ TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____ 物理地址为 CO ___ CI___ CT ____ cache Hit? __ 数据: ____ 13 12 11 10 9 8 7 6 5 4 3 2 1 VPO VPN TLBI TLBT 0x0F 0x3 0x03 Y N 0x0D 问题：逻辑地址为0x0A7A、0x0507时的访存过程如何？ TLB缺失/cache缺失、TLB缺失/缺页 11 10 9 8 7 6 5 4 3 2 1 PPO PPN CO CI CT 0x5 0x0D Y 0x7236

20 页表存储 大多数虚存实现方案将页表存储于虚存而不是实存（主存）中，即页表自身也会发生paging。
当一个进程运行时，至少一部分它的页表（包括当前执行使用到的页表项）要装入主存中 典型情况下，一个页表的最大尺寸与一页的大小相同 为减少页表的大小，一些处理器使用两级的页表组织： 第一级为页目录（page directory），其中每一目录项指向一个页表（第二级） 如果一页目录额长度为X且页表的最大长度为Y，则一个进程最大可访问X*Y个页

21 两级页表层次结构

22 两级页表结构实例（ARM处理器）

23 两级页表结构实例（Pentium处理器）

24 K级页表结构