第三单元作业

Andy Gao

2023-12-22

homework › computer_orgnization

computer_orgnization, homework

第三单元作业

郭高旭 ggx21@mails.tsinghua.edu.cn 2021010803

B
B
不一定

在LRU的情况下，如果全相联cache行数为N，地址为0-N+1连续的N个，循环访问0-N+1的地址，会导致每次要访问的地址恰好已被替换，缓存命中率为0；

使用组相联时，由于通过index选择了组，可能有些地址一直不被替换。

比如cache共有4行的两路组相联，地址为0-5.如果循环顺序执行，全相联命中率为0，而1，3地址永远不被替换，组相联命中率为2/5
不是

RAID1是通过镜像,将数据完全复制到两个disk上.读取时由于可以同时并行读取两个disk,使得读的效率接近两倍.但是写时由于要同时写到两个disk上（写后同步）,会使得写效率比不使用RAID时略有降低
$$
总共访问时间:(5000-450)\times20ns+450\times100ns=13600ns\
平均访问时间:13600ns/5000=27.2ns
$$
$$

$$

$$
raid0 实际上没有冗余,因此占用大小就是512GB
$$

$$
raid6(4+2):512GB\times \frac{6}{4}=768GB
$$

低八位是VPO,高四位是VPN.高二位是tlb tag,次高二位是tlb index
低八位是PPO,高四位是PPN,低二位是CO，次低2位是CI ,高10位是cache tag
修改处加粗表示
- page table
  
  vpn ppn valid vpn ppn valid
  
  0 1 1 8 - 0
  
  1 E 1 9 5 1
  
  2 5 0 A F 1
  
  3 1 0 B 4 1
  
  4 A 1 C D 1
  
  5 - 0 D 2 1
  
  6 B 0 E 3 1
  
  7 C 1 F B 1
- TLB
  
  index tag ppn valid
  
  0 3© 0 1
  
  0 1(4) A 1
  
  1 0(1) E 1
  
  1 3(D) 2 1
  
  2 3(E) 3 1
  
  2 2(A) F 1
  
  3 2(B) 4 1
  
  3 1(7) F 04
cache

index valid(1位) tag(8位) entry(4B data)

0

0

1

1

2<–cache hit 1 $10101000_2$ 4Bytes

2

3

3

查找过程
1. 首先根据物理地址低2位(2)找到index为2的cache 组
2. 用两个比较器并行比较这一组里两个tag是否和物理地址的高10位相等
3. 判等信号取或,判断是否cache hit;如果hit,通过选择器选择实际hit的cache line
4. 得到cache entry,也就是4B的data
5. 取出cache entry偏移cache offset处字节内容
缺页处理
1. CPU 检测到页面缺失，触发异常。
2. 操作系统中断处理程序执行，确定缺失页面地址。
3. 操作系统从页表获取缺失页框号，确定对应物理地址。
4. 如果在物理内存中找到，更新页表项并重新执行指令。
5. 否则，操作系统将缺失页号发送给磁盘。
6. 磁盘读取缺失页到内存，更新页表，返回 CPU 执行缺失指令。

vpn	ppn	valid	vpn	ppn	valid
0	1	1	8	-	0
1	E	1	9	5	1
2	5	0	A	F	1
3	1	0	B	4	1
4	A	1	C	D	1
5	-	0	D	2	1
6	B	0	E	3	1
7	C	1	F	B	1

index	tag	ppn	valid
0	3©	0	1
0	1(4)	A	1
1	0(1)	E	1
1	3(D)	2	1
2	3(E)	3	1
2	2(A)	F	1
3	2(B)	4	1
3	1(7)	F	04

cacheA:

大小:32KB
路数:8
缓存行大小64B
64组

1

芯片A的组数为
$$
\frac {32KB}{64B\times 8}=64=2^6
$$
因此，索引位为6位。

由于缓存行大小为64B，CO位为6

剩下32-6-6=20位为标记位

综上，地址各部分为

| 31-12 | 11-6 | 5-0 | |
| ------------- | --------------- | ---------------- | ---- |
| Cache Tag, CT | Cache Index, CI | Cache Offset, CO | |

访存地址转换为2进制表示

Decimal	Hexadecimal	Decimal	Hexadecimal	Decimal	Hexadecimal
15	0x000f	32768	0x8000	0	0x0000
8193	0x2001	0	0x0000	4	0x0004
16384	0x4000	129	0x0081	8	0x0008
63	0x003f	1024	0x0400	4096	0x1000
4096	0x1000	3072	0x0c00	64	0x0040
8194	0x2002	8192	0x2000	128	0x0080
64	0x0040	260	0x0104	128	0x0080
16385	0x4001	513	0x0201	64	0x0040

十进制	补齐为16位的二进制
15	0000 0000 0000 1111
8193	0010 0000 0000 0001
16384	0100 0000 0000 0000
63 hit	0000 0000 0011 1111
4096	0001 0000 0000 0000
8194 hit	0010 0000 0000 0010
64	0000 0000 0100 0000
16385 hit	0100 0000 0000 0001

十进制	补齐为16位的二进制
32768	1000 0000 0000 0000
0	0000 0000 0000 0000
129	0000 0000 1000 0001
1024	0000 0100 0000 0000
3072	0000 1100 0000 0000
8192	0010 0000 0000 0000
260	0000 0001 0000 0100
513	0000 0010 0000 0001

十进制	补齐为16位的二进制
0	0000 0000 0000 0000
4	0000 0000 0000 0100
8	0000 0000 0000 1000
4096	0001 0000 0000 0000
64	0000 0000 0100 0000
128	0000 0000 1000 0000
128	0000 0000 1000 0000
64	0000 0000 0100 0000

前八次，只有CO位数为6时才能命中三次，hit标记如上。此时缓存行大小为64B

在此基础上如果路数为1，2.那么 4096，8194，16385 必然冲突（详细证明略），由于中8次8192没有hit（本应该hit8193出缓存），说明发生冲突，容易排除路数为8.

故取路数为4验证：

8194条目被16385，32768，0，3072挤走了，路数为4合理。

如果缓存大小为4KB，后八次访问4096因为fifo而miss。

缓存大小为8KB

综上：

缓存行大小64B
路数为4
缓存大小8KB

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        sum = 0.0;
        for (k = 0; k < n; k++)
            sum += M[i][k] * N[k][j];
        Q[i][j] = sum;
    }
}

C语言的矩阵是行优先的，我们希望尽量按行访问以充分利用缓存

for (i = 0; i < n; i++) {
    for (k = 0; k < n; k++) {
        double Mik = M[i][k]; // 将 Mik在最内层循环不变
        for (j = 0; j < n; j++) {
            Q[i][j] += Mik * N[k][j];
        }
    }
}

这样Q，N，M都是按行访问，可以提高缓存命中率

index	valid(1位)	tag(8位)	entry(4B data)
0
0
1
1
2<–cache hit	1	$10101000_2$	4Bytes
2
3
3

第三单元作业

查找过程