IS CS-2018S2-04

题目来源：Problem 4 日期：2024-08-10 题目主题：CS-计算机体系结构-缓存存储器

解题思路

这个问题涉及缓存存储器的设计和性能分析。我们需要：

1. 计算不同缓存映射方案下的标记、索引和偏移的位长。
2. 模拟不同缓存映射方案下的缓存命中情况，并展示缓存表项的变化。

关键点包括：

• 理解全相联、二路组相联和直接映射的缓存组织方式
• 计算标记、索引和偏移的位长
• 模拟 LRU 替换算法
• 注意 4 字节读操作的影响

Solution

1. Bit length calculation for different cache mapping schemes

Given:

• 32-bit memory addressing
• Cache capacity: $2^{15}$ bytes = 32 KB
• Block size: 64 bytes

a) Fully Associative Cache

In a fully associative cache, there is no index, only tag and offset.

• Offset: ${\log }_2(64)=6$ bits
• Tag: $32-6=26$ bits
• Index: 0 bits

b) Two-way Set-associative Cache

• Offset: ${\log }_2(64)=6$ bits
• Number of sets: $\frac{32\text{ KB}}{64\text{ bytes}\times 2}=256$ sets
• Index: ${\log }_2(256)=8$ bits
• Tag: $32-8-6=18$ bits

c) Direct Mapping Cache

• Offset: ${\log }_2(64)=6$ bits
• Number of blocks: $\frac{32\text{ KB}}{64\text{ bytes}}=512$ blocks
• Index: ${\log }_2(512)=9$ bits
• Tag: $32-9-6=17$ bits

Summary of bit lengths for each scheme

Mapping Scheme	Tag Bits	Index Bits	Offset Bits
Full Associative	26	0	6
Two-Way Set-Associative	18	8	6
Direct Mapping	17	9	6

2. Cache hit analysis for different mapping schemes

Given:

• Cache capacity: 64 bytes
• Block size: 8 bytes
• Cache lines: 8
• 4-byte read operations
• LRU replacement policy

Memory access sequence (in hexadecimal):

0x20, 0x48, 0x40, 0x4C, 0x58, 0x80, 0xB8, 0xC8, 0x40, 0x44, 0x48, 0x4C, 0x50, 0x54, 0x58, 0x30, 0x28

Now, let’s analyze each mapping scheme:

a) Fully Associative Cache

• Offset: 3 bits
• Tag: $32-3=29$ bits, or the first 5 bits of the address

Since 4-byte read operations are used, we need to consider the possibility of a read operation spanning two blocks.

The cache state after each access (LRU order from left to right):

Read Address (Hex)	Read Address (Binary)	Tag (Hex)	Cache State (Tag) (8 lines, LRU)	Evict?	Cache Hit/Miss
0x20	0010 0000	0x4	0x4	None	Miss
0x48	0100 1000	0x9	0x4, 0x9	None	Miss
0x40	0100 0000	0x8	0x4, 0x9, 0x8	None	Miss
0x4C	0100 1100	0x9	0x4, 0x8, 0x9	None	Hit
0x58	0101 1000	0xB	0x4, 0x8, 0x9, 0xB	None	Miss
0x80	1000 0000	0x10	0x4, 0x8, 0x9, 0xB, 0x10	None	Miss
0xB8	1011 1000	0x16	0x4, 0x8, 0x9, 0xB, 0x10, 0x16	None	Miss
0xC8	1100 1000	0x19	0x4, 0x8, 0x9, 0xB, 0x10, 0x16, 0x19	None	Miss
0x40	0100 0000	0x8	0x4, 0x9, 0xB, 0x10, 0x16, 0x19, 0x8	None	Hit
0x44	0100 0100	0x8	0x4, 0x9, 0xB, 0x10, 0x16, 0x19, 0x8	None	Hit
0x48	0100 1000	0x9	0x4, 0xB, 0x10, 0x16, 0x19, 0x8, 0x9	None	Hit
0x4C	0100 1100	0x9	0x4, 0xB, 0x10, 0x16, 0x19, 0x8, 0x9	None	Hit
0x50	0101 0000	0xA	0x4, 0xB, 0x10, 0x16, 0x19, 0x8, 0x9, 0xA	None	Miss
0x54	0101 0100	0xA	0x4, 0xB, 0x10, 0x16, 0x19, 0x8, 0x9, 0xA	None	Hit
0x58	0101 1000	0xB	0x4, 0x10, 0x16, 0x19, 0x8, 0x9, 0xA, 0xB	None	Hit
0x30	0011 0000	0x6	0x10, 0x16, 0x19, 0x8, 0x9, 0xA, 0xB, 0x6	0x4	Miss
0x28	0010 1000	0x5	0x16, 0x19, 0x8, 0x9, 0xA, 0xB, 0x6, 0x5	0x10	Miss

Number of cache hits: 7 (Address 0x4C, 0x40, 0x44, 0x48, 0x4C, 0x54, 0x58)

b) Two-way Set-associative Cache

• Offset: 3 bits
• Index: ${\log }_2(8\text{ lines}/2\text{ ways})=2$ bits
• Tag: $32-2-3=27$ bits, or the first 3 bits of the address

The cache state after each access (LRU order from left to right):

Read Address (Hex)	Read Address (Binary)	Tag (Hex)	Index	Set 00	Set 01	Set 10	Set 11	Evict?	Cache Hit/Miss
0x20	001 00 000	0x1	00	0x1				None	Miss
0x48	010 01 000	0x2	01	0x1	0x2			None	Miss
0x40	010 00 000	0x2	00	0x1, 0x2	0x2			None	Miss
0x4C	010 01 100	0x2	01	0x1, 0x2	0x2			None	Hit
0x58	010 11 000	0x2	11	0x1, 0x2	0x2		0x2	None	Miss
0x80	100 00 000	0x4	00	0x2, 0x4	0x2		0x2	100 00	Miss
0xB8	101 11 000	0x5	11	0x2, 0x4	0x2		0x2, 0x5	None	Miss
0xC8	110 01 000	0x6	01	0x2, 0x4	0x2, 0x6		0x2, 0x5	None	Miss
0x40	010 00 000	0x2	00	0x4, 0x2	0x2, 0x6		0x2, 0x5	None	Hit
0x44	010 00 100	0x2	00	0x4, 0x2	0x2, 0x6		0x2, 0x5	None	Hit
0x48	010 01 000	0x2	01	0x4, 0x2	0x6, 0x2		0x2, 0x5	None	Hit
0x4C	010 01 100	0x2	01	0x4, 0x2	0x6, 0x2		0x2, 0x5	None	Hit
0x50	010 10 000	0x2	10	0x4, 0x2	0x6, 0x2	0x2	0x2, 0x5	None	Miss
0x54	010 10 100	0x2	10	0x4, 0x2	0x6, 0x2	0x2	0x2, 0x5	None	Hit
0x58	010 11 000	0x2	11	0x4, 0x2	0x6, 0x2	0x2	0x5, 0x2	None	Hit
0x30	001 10 000	0x1	10	0x4, 0x2	0x6, 0x2	0x2, 0x1	0x5, 0x2	None	Miss
0x28	001 01 000	0x1	01	0x2, 0x1	0x6, 0x2	0x2, 0x1	0x5, 0x2	100 00	Miss

Number of cache hits: 6 (Address 0x4C, 0x40, 0x44, 0x48, 0x4C, 0x54)

c) Direct Mapping Cache

• Offset: 3 bits
• Index: ${\log }_2(8\text{ lines})=3$ bits
• Tag: $32-3-3=26$ bits, or the first 2 bits of the address

Cache state after each access:

Read Address (Hex)	Read Address (Binary)	Tag (Hex)	Index	000	001	010	011	100	101	110	111	Evict?	Cache Hit/Miss
0x20	00 100 000	0x0	100					0				None	Miss
0x48	01 001 000	0x1	001		1			0				None	Miss
0x40	01 000 000	0x1	000	1	1			0				None	Miss
0x4C	01 001 100	0x1	001	1	1			0				None	Hit
0x58	01 011 000	0x1	011	1	1		1	0				None	Miss
0x80	10 000 000	0x2	000	2	1		1	0				01 000	Miss
0xB8	10 111 000	0x2	111	2	1		1	0			2	None	Miss
0xC8	11 001 000	0x3	001	2	3		1	0			2	01 001	Miss
0x40	01 000 000	0x1	000	1	3		1	0			2	10 000	Miss
0x44	01 000 100	0x1	000	1	3		1	0			2	None	Hit
0x48	01 001 000	0x1	001	1	1		1	0			2	11 001	Miss
0x4C	01 001 100	0x1	001	1	1		1	0			2	None	Hit
0x50	01 010 000	0x1	010	1	1	1	1	0			2	None	Miss
0x54	01 010 100	0x1	010	1	1	1	1	0			2	None	Hit
0x58	01 011 000	0x1	011	1	1	1	1	0			2	None	Hit
0x30	00 110 000	0x0	110	1	1	1	1	0		0	2	None	Miss
0x28	00 101 000	0x0	101	1	1	1	1	0	0	0	2	None	Miss

Number of cache hits: 6 (Address 0x4C, 0x44, 0x4C, 0x54, 0x58)

知识点

缓存存储器缓存映射缓存替换算法计算机体系结构CacheLRU

难点思路

1. 理解不同缓存映射方案的特点和区别。
2. 正确计算标记、索引和偏移的位长。
3. 模拟 LRU 替换算法的过程，特别是在二路组相联缓存中。
4. 注意 4 字节读操作可能跨越缓存块边界的情况。

解题技巧和信息

1. 缓存映射方案的特点：

   • 全相联：灵活性最高，但硬件复杂度高
   • 直接映射：硬件简单，但冲突概率高
   • 组相联：平衡了灵活性和硬件复杂度

2. 位长计算：

   • 偏移位 = ${\log }_2$(块大小)
   • 索引位 = ${\log }_2$(组数)
   • 标记位 = 地址总位数 - 索引位 - 偏移位

3. LRU 替换算法：

   • 记录每个缓存块的使用时间
   • 替换最长时间未使用的块

4. 缓存命中判断：

   • 检查标记是否匹配
   • 考虑 4 字节读操作可能跨越的块

5. 性能分析：

   • 缓存命中率 = 缓存命中次数 / 总访问次数

重点词汇

cache memory 缓存存储器

fully associative 全相联

set-associative 组相联

direct mapping 直接映射

tag 标记

index 索引

offset 偏移

LRU (Least Recently Used) 最近最少使用

cache hit 缓存命中

cache miss 缓存缺失

replacement policy 替换策略

参考资料

1. Patterson, D. A., & Hennessy, J. L. (2011). Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufmann. Chapter 5: Memory Hierarchy Design.
2. Stallings, W. (2015). Computer Organization and Architecture: Designing for Performance. Pearson. Chapter 4: Cache Memory.

请参考这份解析。这份解析不一定对，请小心