计算机组织结构 期中复习

优点：防止抖动，

缺点：复杂而且浪费资源。 三．组关联映射（折衷）

策略：Cache被分为多个组，假设j为主存中的块数，S是Cache中的组数，那么相应的块对应在

Cache中的组号s=S mod j

K路组：k=C/S,每组的行数 组内采用关联映射

例：假设Cache中有4行且被分成2组，每行8个字，主存中含有128个字节，所以7位地址。 三位表示字长，因为组数=2，中间一位用来表示位于哪一组，最高3位用作Tag. 即M=16，S=2 所以n=4-1=3.

比较:

K=1

直接映射

K=C

关联映射

关联度(Correlation 每块对应寄存器中行的可能数): 直接映射1

3.替换机制

LRU Least Recently Used 最近最少用 FIFO First In First Out 先进先出 LFU Least Frequently Used 最不常用

关联映射C 组关联映射K

相关度越小，命中率越低，check时间更少，Tag长度越短

4.写操作策略

一．写入

为保证Cache与主存的一致性，往Cache写入时同时也要往主存写入 但降低写入速度，容易产生瓶颈

二．写回

在Cache中增加一位（脏位）表示是否被修改过，若“脏”，则替换整个块时前将其写回 减少写入操作，但会有不必要的麻烦（如输出时会取得主存中未修改的数据） 策略：输出时候强制修改主存

5.行的大小即每个块的容量

行变大，提高命中率。

行再变大，也可能降低命中率（原因: Cache总大小不变时，行变大，减少了行数，使得替换频繁） 6.Cache的个数

单个：方便集成到处理器，简化电路设计 层次式：L1 L2

设计复杂：要保证3个之间数据的一致性 L2 可以使用另外一条路，也可以放在处理器上

注意：L1与L2的关系可以类比于单个Cache时候Cache与主存的关系

7.数据与指令是否分开

例题分析：

关于Cache的映射关系

1.假设Cache有4K字，每行32字。对十六进制主存地址：111111、666666、BBBBBB，请 用十六进制格式表示如下信息：

(1)直接映射Cache的地址格式，(2)全关联映射Cache的地址格式，(3)两路组关联Cache的地址格式。（提示：每个映射方式下，需要将标记、 块内地址等分开表示。）

解： Cache字数：4K=4*2^10=2^12 总共12位地址 块的大小32=2^5 5位字长 行数2^7 用7位表示 主存地址为6位16进制即24位二进制，其中5位表示字长. 一．直接映射：

标记位：19-7=12 行数: 7 块内地址：5

二．全关联映射

标记为 19 块内地址 5

三．两路组关联映射

组数 2^6 6位表示组数 标记为 19-6=13 块内地址 5位

以BBBBBB为例 化为二进制位1011 1011 1011 1011 1011 1011 直接映射 101110111011 1011101 11011

BBB

5D 1B

全关联映射 101 1101 1101 1101 1101 11011

5DDDD 1B

两路组关联映射 1 0111 0111 0111 01 1101 11011

1777 1D 1B

对命中的判断以及LRU算法的应用

2. 计算机系统包含容量为32K×16位的主存，按字编址，每字16位。Cache采用4路组关 联的映射方式，数据区大小为4K字，主存块大小为64字。假设Cache初始时是空的， 处理器顺序地从存储单元（每个存储单元中包含1个字）0,1,…,4351中取数，然后再 重复这一顺序9次，并且Cache的速度是主存的10倍，同时假设块替换用LRU算法。 请说明使用Cache后的改进。

主存共32K=2^15个字，每块2^6=64个字，所以一共2^9块. Cache 共2^12 字 所以一共 2^6=64 行 采用4路组关联 组数=2^4=16 所以标记位为9-4=5 组： 4

设Cache的速度为t，则主存的速度为10t 采用cache:

第一次： 0 miss 11t

1-63 hit 1t*15 64 miss 11t 64-127 hit 1t*15

4351/64 = 68 所以一共有68次miss.

第二次： 因为第一次中 0 1 2 3 行中的内容被替换成了 64 65 66 67 块.

根据LRU原则 0 1 2 3 换下的是 16 17 18 19 那一路，以此类推、 0123 16171819 32333435 48495051 64656667永远miss

所以综上p= ( 4352*10-68-20*9)/43520 = 99.43%

时间10V/(V+10*（1-0.9943))=9.5倍

LRU算法与FIFO算法的应用与比较