假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU替换策略。访问的主存地址依次为0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是（）。
-
LRU最近最少使用算法：根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
-
主存到缓存的映射策略
-
直接映射：一个内存地址能被映射到的Cache line是固定的
-
全相联映射：主存中的一个地址可被映射进任意*** line
-
组相联映射：将缓存分组，组内包含多块，组间采用直接映射，组内采用全相联映射
例题帮助理解组相联映射，可跳过直接看解答。
例题：容量为64块的Cache采用组相联方式映像，字块大小为128字节，每4块为一组，若主容量为4096块，且以字编址，那么主存地址为（19）位，主存区号为（6）位。
组相联的地址构成为：区号+组号+块号+块内地址,主存的每个分区/组大小与整个Cache大小相等，故此主存需要分的区数为：4096/64=64，因为2^6＝64，因此需要6位来表示区号。每4块为一组，故共有组数 64/4 = 16 ，因为2^4＝16，因此需要4位表示组号。每组4块，故表示块号需要2位。
块内地址共128字节，2^7＝128，所以块内地需要7位表示。所以：主存地址的位数＝6+4+2+7 ＝ 19
2路组相联映射，即缓存分为两组，又缓存有4行，因而每组内分为2行，根据前面例题的启示，主存与缓存的直接映射关系应当为：组号= 主存地址%4/2（对4求余忽略区号），组内行号采用全相联映射，结合LRU算法，，那么我们可以得到下表：
-
| 组号 | 缓存行号 | 0 | 4 | 8 | 2 | 0 | 6 | 8 | 6 | 4 | 8 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0组 | 0 | 0 | 0 | 8 | 8 | 8 | 8 | 8* | 8* | 8* | 8** |
| 0组 | 1 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 4 | 4 | |
| 1组 | 0（3） | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |||
| 1组 | 1（4） | 6 | 6 | 6* | 6* | 6* | |||||
| 备注 | 0%4/2=0 | 4%4/2=0 | 8%4/2=0，替换0 | 2%4/2=1 | 0%4/2=0，替换4 | 6%4/2=1 | 8命中 | 6命中 | 4%4/2=0，替换0 | 8命中 |
命中3次。
编辑于 2018-10-09 01:45:50
回复(2)
由于 Cache 有 4 行，采用二路组相联，由此可以得出分为 2 组，故组内地址为 1 位。
根据 Cache 和主存之间交换的块大小为 1 个字，并且计算机按字编址，由此可得出块内地址为 1 位。
综合相联地址结构为 标记+组号+块内地址 得出，低第二位为组号。
0：0000 -> 0组
4：0100 -> 0
8：1000 -> 0
2：0010 -> 1
0：0000 -> 0
6：0110 -> 1
8：1000 -> 0
6：0110 -> 1
4：0100 -> 0
8：1000 -> 0
由此可得 Cache 置换过程如下表所示：
| 0 | 4 | 8 | 2 | 0 | 6 | 8 | 6 | 4 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 4 | 4 | 0 | 4 | |||||
| 0 | 8 | 8 | 8 | ||||||
| 2 | 2 | ||||||||
| 6 | |||||||||
| 命中 | 命中 | 命中 |
故 Cache 命中次数为 3 次。
发表于 2023-07-06 21:39:41
回复(0)
直接映射:一个内存地址能被映射到的Cache line是固定的，***有2块，主存有4块，则第一块***对应1和3块主存，第二块***对应2和4块主存。 全相联则是一个***能映射所有主存块，有空位就插。 n路组相联则是直接映射和全相联的结合。 ***分为k组，组内有n块。组内采用全相联，组间采用直接映射。n一般为2的幂
发表于 2019-04-17 21:31:43
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
走向
0
4
8
2
0
6
8
6
4
8
第0组
块0
0
4
4
8
8
0
0
8
4
块1
0
4
8
8
0
0
8*
8
4
8*
第1组
块2
2
2
2
2
2
块3
2
2
6
6
6*
6
6
注：“ ”表示当前访问块，“*”表示本次访问命中。
注意：在不同的《计算机组成原理》教材中，关于组相联映射的介绍并不相同。通常采用（真题2009,14）中的方式，也是唐朔飞教材中的方式，但本题中采用的是蒋本珊教材中的方式。可以推断两次命题的老师应该不是同一老师，也给考生答题带来了困扰。