计算机组成原理4-3

1、1、基本原理基本原理 （1）功能：）功能：解决解决CPU和主存之间的速度不匹配问题和主存之间的速度不匹配问题 一般采用高速的一般采用高速的SRAM构成。构成。 CPU和主存之间的速度差别很大采用两级或和主存之间的速度差别很大采用两级或 多级多级Cache系统系统 早期的一级早期的一级Cache在在CPU内，二级在主板上内，二级在主板上 PentiumPentium以后的以后的CPUCPU则将则将L2 CacheL2 Cache与与CPUCPU内内 核一起封装在一个金属盒内，或者直接把核一起封装在一个金属盒内，或者直接把L2 L2 CacheCache也集成到也集成到CPUCPU芯片内，以进一步

2、提高速芯片内，以进一步提高速 度。这样，主板上的度。这样，主板上的CacheCache就称为三级就称为三级 Cache(L3 Cache)Cache(L3 Cache)。 4.3 高速缓冲存储器 (2) cache基本原理小结：基本原理小结： cache是介于是介于CPU和主存和主存M2之间的小之间的小 容量存储器，但存取速度比主存快。主容量存储器，但存取速度比主存快。主 存容量配置几百存容量配置几百MB的情况下，的情况下，cache 的典型值是几百的典型值是几百KB。cache能高速地向能高速地向 CPU提供指令和数据，从而加快了程序提供指令和数据，从而加快了程序 的执行速度。从功能上看，它

3、是主存的的执行速度。从功能上看，它是主存的 缓冲存储器，由高速的缓冲存储器，由高速的SRAM组成。为组成。为 追求高速，包括管理在内的全部功能由追求高速，包括管理在内的全部功能由 硬件实现，因而对程序员是透明的。硬件实现，因而对程序员是透明的。 Cache的设计依据的设计依据:CPU这次访问过的数据，这次访问过的数据， 下次有很大的可能也是访问附近的数据。下次有很大的可能也是访问附近的数据。 CPU与与Cache之间的数据传送是以字为单位之间的数据传送是以字为单位 主存与主存与Cache之间的数据传送是以块为单位之间的数据传送是以块为单位 CPU读主存时，便把地址同时送给读主存时，便把地址同时

4、送给Cache和和 主存，主存，Cache控制逻辑依据地址判断此字是控制逻辑依据地址判断此字是 否在否在Cache中，若在此字立即传送给中，若在此字立即传送给CPU ， 否则，则用主存读周期把此字从主存读出送否则，则用主存读周期把此字从主存读出送 到到CPU，与此同时，把含有这个字的整个数，与此同时，把含有这个字的整个数 据块从主存读出送到据块从主存读出送到cache中。中。 （3） Cache的命中率的命中率 从从CPU来看，增加一个来看，增加一个cache的目的目 的，就是在性能上使主存的平均读出时的，就是在性能上使主存的平均读出时 间尽可能接近间尽可能接近cache的读出时间。为了的读出

5、时间。为了 达到这个目的，在所有的存储器访问中达到这个目的，在所有的存储器访问中 由由cache满足满足CPU需要的部分应占很高需要的部分应占很高 的比例，即的比例，即cache的命中率应接近于的命中率应接近于1。 由于程序访问的局部性，实现这个目标由于程序访问的局部性，实现这个目标 是可能的。是可能的。 n在一个程序执行期间，设在一个程序执行期间，设Nc表示表示cache完成存取的总完成存取的总 次数，次数，Nm表示主存完成存取的总次数，表示主存完成存取的总次数，h定义为命中定义为命中 率，则有率，则有 h=Nc/（Nc+Nm) n若若tc表示命中时的表示命中时的cache访问时间，访问时间

6、，tm表示未命中时表示未命中时 的主存访问时间，的主存访问时间，1-h表示未命中率，则表示未命中率，则cache/主存主存 系统的平均访问时间系统的平均访问时间ta为：为： ta=h*tc+（1-h)tm n我们追求的目标是，以较小的硬件代价使我们追求的目标是，以较小的硬件代价使cache/主存主存 系统的平均访问时间系统的平均访问时间ta越接近越接近tc越好。越好。 n设设r=tm/tc表示主存慢于表示主存慢于cache的倍率，的倍率，e表示访问效表示访问效 率，则有率，则有 e=tc/ta=tc/（h*tc+（1-h）*tm =1/（h+（1-h）*r=1/（r+（1-r)*h n由表达式

7、看出，为提高访问效率，命中率由表达式看出，为提高访问效率，命中率h越接近越接近1越越 好，好，r值以值以510为宜，不宜太大。为宜，不宜太大。 n命中率命中率h与程序的行为、与程序的行为、cache的容量、组织方式、块的容量、组织方式、块 的大小有关。的大小有关。 例例6 CPU执行一段程序时，执行一段程序时，cache完成存取的次数为完成存取的次数为 1900次，主存完成存取的次数为次，主存完成存取的次数为100次，已知次，已知cache存取存取 周期为周期为50ns，主存存取周期为，主存存取周期为250ns，求，求cache/主存系统主存系统 的效率和平均访问时间。的效率和平均访问时间。

8、n公式 cm c a mca me e ttr hrrt t e thhtt NN N h / )1 ( 1 )1 ( 命中率命中率 Cache/主存系统的主存系统的 平均访问时间平均访问时间 访问效率访问效率 Cache与内存的速与内存的速 度比度比 例6解： nh=Nc/（Nc+Nm） =1900/(1900+100)=0.95 nr=tm/tc=250ns/50ns=5 ne=1/(r+(1-r)h)=1/(5+(1-5)0.95=83.3% nta=tc/e=50ns/0.833=60ns 2. 主存与主存与CacheCache的地址映射的地址映射 来自cpu的主存地址 Cache地址

9、 装入时，地 址映像 执行程序时， 地址变换 地址映射方式有全相联方式，直接方式地址映射方式有全相联方式，直接方式 和组相联方式三种和组相联方式三种 为了把主存块放到为了把主存块放到cache中，必须应用某种方法把主存中，必须应用某种方法把主存 地址定位到地址定位到cache中，称做地址映射。中，称做地址映射。 假设某机假设某机 主存容量主存容量1 1MB=2MB=220 20，被分为 ，被分为2048=22048=211 11块，每块 块，每块512=2512=29 9B B； CacheCache容量为容量为8 8KB=2KB=213 13B B，被分为 ，被分为1616=2=24 4块，

10、每块也是块，每块也是512512B B。 (1) 直接映射：直接映射：i=j mod 2i=j mod 2c c i是是Cache的字块号、的字块号、j是主存的字块号、是主存的字块号、c为为Cache二二 进制字块号的位数进制字块号的位数(该例该例c=4)。 地址映射关系如下：地址映射关系如下： 0块 1块 15块 标记 标记 标记 0块 1块 15块 16块 17块 31块 2032块 2033块 2047块 0组 1组 255组 7位Cache主存储器 主存地址主存标记Cache块号块内地址 7位4位9位 t c Cache块号块内地址 4位9位 主存块号 Cache地址 图 直接映像63

11、4 Cache 主存的第0块、第16块第 2032块等，映象到Cache的第0 块(mod 16=0)；究竟存入的是 第几块写入标记，如第0块写0， 第16块写1（主存）标记的 位数211块/24块=27 在访存时，比较主存地址中高7位 的标记段与对应Cache块的7位 （主存）标记，两者相同 则命中。 例：Cache第0块中复制的是主存 中第16块的内容，则其标记段为1， 标志它现在与主存的第1组相对应 具体过程见下页 127 主存地址： 0000000 0000 000000000 第0块 0000000 0000 111111111 0000000 0001 000000000 第1块

12、0000000 0001 111111111 0000000 0010 000000000 第2块 0000000 0010 111111111 0000000 1111 000000000 第15块 0000000 1111 111111111 0000001 0000 000000000 第16块 （第0块） 0000001 0000 111111111 0000001 0001 000000000 第17块 （第1块） 1111111 1111 111111111 第0组 第1组 Cache地址： 0000 000000000 第0块 0000 111111111 0001 000000

13、000 第1块 0001 111111111 为了表明究竟 是主存的哪一 块放在cache的 第X块，另外用 专门的存储单 元存放主存 （组）标记即 主存的组号 cpu给出主存地址后的访问过程：给出主存地址后的访问过程： 直接映射的优缺点：直接映射的优缺点： 优点：优点：硬件实现简单，成本低。只需利用主存地址的某些硬件实现简单，成本低。只需利用主存地址的某些 位直接判断，即可确定所需字块是否在缓存中。位直接判断，即可确定所需字块是否在缓存中。 缺点：缺点：不灵活，存在不灵活，存在Cache有空行而不能存数据块的问题，有空行而不能存数据块的问题， 即造成替换频繁，效率下降。即造成替换频繁，效率下

14、降。 适合需要大容量适合需要大容量Cache的场合（更多的行数可以减少冲突的场合（更多的行数可以减少冲突 的机会）。的机会）。 (2) 全相联映射 0块 1块 15块 标记 标记 标记 11位 Cache 0块 1块 15块 2047块 主存储器 主存地址主存标记块内地址 11位9位 Cache块号块内地址 4位9位 Cache地址 t+c 图 全相联映像635 Cache 1）查询相等，现在所映射的 主存块号(2048个字块中之一) 主存的各字块可映象到主存的各字块可映象到Cache的任一个字块的任一个字块 访问访问Cache时，需要和时，需要和Cache的全部标记进行的全部标记进行“比较比

15、较” 后才能判断出所访主存地址单元的内容是否已在后才能判断出所访主存地址单元的内容是否已在 Cache中中 。 2）拼装出cache地址 0块 1块 15块 标记 标记 标记 11位 Cache 0块 1块 15块 2047块 主存储器 主存地址主存标记块内地址 11位9位 Cache块号块内地址 4位9位 Cache地址 t+c 图 全相联映像635 Cache 主存地址：主存地址： 0000000 0000 000000000 第第0块块 0000000 0000 111111111 0000000 0001 000000000 第第1块块 0000000 0001 111111111 0

16、000000 0010 000000000 第第2块块 0000000 0010 111111111 0000000 1111 000000000 第第15块块 0000000 1111 111111111 0000001 0000 000000000 第第16块块 0000001 0000 111111111 0000001 0001 000000000 第第17块块 Cache地址：地址： 0000 000000000 第第0块块 0000 111111111 0001 000000000 第第1块块 0001 111111111 为了表明究竟 是主存的哪一 块放在cache的 第X块，另

17、外用 专门的存储单 元存放主存标 记即主存的块 号 任 意 映 射 全相联全相联CacheCache的检索过程的检索过程 全相联存储器的优缺点：全相联存储器的优缺点： 优点：优点：灵活，灵活，Cache的命中率高。的命中率高。 缺点：与直接映射相比，缺点：与直接映射相比，Cache标记的位数增多、标记的位数增多、 比较的次数也增多。比较的次数也增多。速度较慢，成本较高（比速度较慢，成本较高（比 较器电路难以设计和实现）。较器电路难以设计和实现）。 适用于小容量的适用于小容量的Cache。 (3) 组相联映射组相联映射 主存和Cache都分组，主存中一个组内的块数与Cache中的分组数相同。 组

18、间采用直接映射，组内采用全相联映射。 例 ： 主 存 分 为256组，每 组 8 块 ； Cache分为8 组，每组2块。 主存中的各 块与Cache的 组号间有固 定的映象关 系 但可自由映 象到对应的 Cache组中的 任一块。 如主存中的 第0块、第8 块均映象 于Cache的第 0组，但可映 象于Cache的 第0块或第1 块。 高8位为主存组标记 Cache组号共3位， 可选择8组之一，低 9位为块内地址。 访存时，根据主存 地址，在Cache组号 对应组中查找，比 较该组所有标记， 确定是否命中。 Cache地址仍为查询 后拼接。 主存地址：主存地址： 0000000 0 000

19、000000000 第第0块块 0000000 0 000 111111111 0000000 0 001 000000000 第第1块块 0000000 0 001 111111111 0000000 0 010 000000000 第第2块块 0000000 0 010 111111111 0000000 0 111 000000000 第第7块块 0000000 0 111 111111111 0000000 1 000 000000000 第第8块块 0000000 1 000 111111111 （第（第0块）块） 0000000 1 111 000000000 第第15块块 000

20、0000 1 111 111111111 （第（第7块）块） 0000001 0 000 000000000 第第16块块 0000001 0 000 111111111 0000001 0 001 000000000 第第17块块 Cache地址：地址： 000 0 000000000 第第0块块 000 0 111111111 000 1 000000000 第第1块块 000 1 111111111 001 0 000000000 第第2块块 001 0 111111111（第（第0块）块） 001 1 000000000 第第3块块 001 1 111111111 （第（第1块）块）

21、为了表明究竟是 主存的哪一块放 在cache的第X块， 另外用专门的存 储单元存放主存 组标记即本例的 高8位（主存组 号） 第0组 第1组 第2组 第0组 第1组 组相联映射的检索过程组相联映射的检索过程 组相联映射的特点组相联映射的特点 具有块在组中存放的灵活性具有块在组中存放的灵活性冲突少；冲突少； 比较器电路不太复杂。比较器电路不太复杂。 主 存 替 换 算 法 比 较 器 不 命 中 Cache满 Cache 数 据 Cache 标 记 标 记块 号块 内 地 址 块 号块 内 地 址 块 （ 多 字 ） 直 接 通 路 去CPU 或 来 自CPU 来 自CPU 主 存 地 址 修

22、改 标 记 访 标 记 Cache地 址 命 中 单 字 图 的 基 本 结 构633 Cache 本图是直接映像：用主存地址的块号字段访问Cache标记 将取出的cache标记和主存地址的标记字段相比较。 若相等，说明访问Cache有效，称Cache命中（即要访问的 在cache中） 若不相等，说明访问Cache无效，称Cache不命中或失效 3. Cache的基本结构的基本结构 4. Cache4. Cache的读的读/ /写操作写操作 (1) (1) CacheCache的读操作的读操作 主 存 替换算法 比较器 不命中 Cache满 Cache 数据 Cache 标记 标记 块号块内地

23、址 块号块内地址 块 （多字） 直接通路 去CPU 或来自CPU 来自CPU 主存地址 修改标记 访标记 Cache地址 命 中 单字 图 的基本结构633 Cache 1.CPU发出读请求 2.Cache命中，直接 对Cache进行读操 作，与主存无关 3.不命中，仍需访 问主存，并把相应 块的信息一次从主 存调入Cache内。 若此时Cache已满， 则需根据某种替换 算法，用这个块替 换掉Cache中原来 的某块信息。 (2) (2) CacheCache的写操作的写操作 主 存 替换算法 比较器 不命中 Cache满 Cache 数据 Cache 标记 标记 块号块内地址 块号块内地址

24、 块 （多字） 直接通路 去CPU 或来自CPU 来自CPU 主存地址 修改标记 访标记 Cache地址 命 中 单字 图 的基本结构633 Cache 1.CPU发出写请求 2.如果Cache命中，保 持Cache与主存中的内 容相一致的问题: 写直达法:同时写入 Cache和主存。 写回法:信息暂时只 写入Cache，并用标记 将该块加以注明，直 到该块从Cache中替换 出来时才一次写入主 存，有可能出错。 3.不命中，就直接 把信息写入主存， 而与Cache无关。 5. 5. 替换算法替换算法 当新的主存字块需要调入当新的主存字块需要调入Cache存储器而存储器而 Cache中的可用位

25、置又被占满时，就产生替中的可用位置又被占满时，就产生替 换算法问题。换算法问题。 FIFO算法：算法： 把一组中最先调入把一组中最先调入Cache的字块替换出去，的字块替换出去， 这种算法实现起来比较方便，但不能正确反这种算法实现起来比较方便，但不能正确反 映程序的局部性。因为最先进入的字块也可映程序的局部性。因为最先进入的字块也可 能是目前经常要用的字块，因此，采用这种能是目前经常要用的字块，因此，采用这种 算法，有可能产生较大的失效率。算法，有可能产生较大的失效率。 访问顺序 1 2 3 4 5 6 7 8 块地址 22 26 22 26 16 4 16 18 块分配情况 操作状态 调进

26、调进 命中 命中 调进 调进 命中 替换 - - - - - - 22 - - - 26 - - - 22 - - - 26 - - - 22 - - - 26 - - - 22 - 16 - 26 - - - 22 - 16 - 26 - 4 - 22 - 16 - 26 - 4 - 22 - 16 - 18 - 4 - 22 - 直接映射直接映射 FIFO替换算法 访问顺序 1 2 3 4 5 6 7 8 地址块号 2 11 2 9 7 6 4 3 块分配情况 操作状态 调进 调进 命中 调进 调进 替换 替换 替换 2 - - - 2 11 - - 2 11 - - 2 11 9 - 2

27、 11 9 7 6 11 9 7 6 4 9 7 6 4 3 7 LRU算法：算法： 把把Cache组中各字块的使用情况记录组中各字块的使用情况记录 在一张表上。并把最近使用过的字块放在一张表上。并把最近使用过的字块放 在表的最上面。在表的最上面。 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 原 始 状 态替 换 7访 问 5访 问 1替 换 6 图算 法 替 换 登 记 表63 9 L R U 设组内有设组内有8个字块，其地址编号为个字块，其地址编号为0，1，7。从图中可。从图

28、中可 以看到，以看到，7号字块在最下面，所以当要求替换时，首先更新号字块在最下面，所以当要求替换时，首先更新7号号 字块内容；如要访问字块内容；如要访问7号字块，则将号字块，则将7号写到表的顶部，其它号号写到表的顶部，其它号 向下顺移。接着访问向下顺移。接着访问5号字块，如果此时命中，不需要替换，但号字块，如果此时命中，不需要替换，但 也要将也要将5号移到表的顶部，其它号向下顺移。号移到表的顶部，其它号向下顺移。6号块是以后要首号块是以后要首 先被替换的，先被替换的，。 近期最少使用算法 访问顺序 1 2 3 4 5 6 7 8 地址块号 2 11 2 9 7 6 4 3 块分配情况 操作状态 调进 调进 命中 调进 调进 替换 替换 替换 2* - - - 2* 11 - - 2 11* - - 2 11* 9 - 2 11* 9 7 2* 6 9 7 4 6 9* 7 4 6 3 7 例：选最近例：选最近4 4次访问期间最少使用次访问期间最少使用CacheCache块作为被替换的块。块作为被替换的块。 例例6.6 6.6 一个组相联映象一个组相联映象CacheCache