组路相联Cache

存储之CacheCache存在的意义：根据局部性原理，对于当前访问的存储位置，接下来，它很可能会被多次访问（时间局部性），它的相邻位置也可能会被访问（空间局部性）。

由于访问内存的速度远⼤于访问寄存器，所以在⼆者之间设置cache，来暂存⼀部分指令或数据。

内存：假设每个内存地址有m位，那么共有M=2m个不同的地址，即内存容量为M字节。

如下图所⽰，m位地址划分为t位标记、s位组索引和b位块偏移，⽤于描述该地址所存数据(⼤⼩为byte)的副本在cache中的位置。

Cache：使⽤元组(S,E,B,m)来描述，具体为：S=2s表⽰Cache共有S个⾼速缓存组(cache set)E表⽰每组均有E个⾼速缓存⾏(cache line)B=2b表⽰每⾏均包含⼤⼩为B个字节的⾼速缓存块(block)总容量为C=S∗E∗B个字节特别注意：每个cache line包含两部分，有效位/标记位+⾼速缓存块；通常说line size是指⾼速缓存块的⼤⼩，即B假设指令指⽰CPU从地址A读取⼀个数据，CPU将地址A发送到Cache，如果Cache含有该数据的副本，它将⽴即返回数据给CPU；那么Cache如何找到该数据的呢？组选择，Cache根据地址A中的s位组索引定位到组⾏匹配，Cache根据地址A中的t位标记位定位到⾏（注意：当且仅当该⾏设置了有效位，并且该⾏的t位标记位与地址A的t位标记位完全相同时，该⾏才包含所需数据副本）取数据，Cache根据地址A中的b位块偏移定位到该数据在block中的位置Cache与内存的映射关系⾸先要明确，cache有多个组，每个组有⼀个或多个⾏；内存有多个块，每个块的⼤⼩为B（即line size），块的数量为2m/B；映射关系是内存块与cache line的映射⼀、直接映射⾼速缓存E=1，即cache中每组只有⼀⾏（即查取数据时没有⾏匹配过程）。

⽐如(S,E,B,m)=(4,1,2,4)，即cache有4组/4⾏，内存有8块，则映射关系如下：⼆、全相联⾼速缓存S=1，即只有⼀个组；所以，查取数据时没有组选择过程，定位数据副本过程如下：三、组相联⾼速缓存Cache包含多个组，每组⼜有多个⾏，所以查取数据时组选择、⾏匹配都不会少，过程如下：理解关键：以上就是CSAPP对cache的主要描述，此时我们对cache的实现原理已经⽐较清楚了，但是有个很关键且令⼈困惑的问题：⼀直在说查取数据，cache与内存的三种映射关系并没有体现出来！我们在各种资料上常见的三张映射关系图，如何与上述知识对接呢？关键就在于t位的标记位！⾸先，t=m−s−b，它的含义是每⾏(或者说每个cache line)可以与2t=MS⋅B种不同的内存块产⽣映射关系(注意，是种，不是个)。

5.1 解释下列术语多级存储层次：由若干个采用不同实现技术的存储器构成的存储器系统，各存储器处在离CPU不同距离的层次上。

使得靠近CPU的存储器速度较快，容量较小。

整个存储系统的速度接近与离CPU最近的存储器的速度，而容量和每位价格接近于最低层次的容量和价格。

全相联映像：指主存中的任一块可以被放置到Cache中的任意一个位置。

直接映像：指主存中的每一块只能被放置到Cache中唯一的一个位置。

组相联映像：指主存中的每一块可以被放置到Cache中固定的一个组中的任意位置。

替换算法：由于主存中的块比Cache中的块多，所以当要从主存中调入一个块到Cache中时，会出现该块所映像的Cache块位置已经被占用的情况。

替换算法即解决如何选择替换块的问题。

LRU：最近最少使用法。

选择近期最少被访问的块作为被替换的块。

写直达法：在执行“写”操作时，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。

写回法：只把信息写入Cache中相应的块，该块只有在被替换时才被写回主存。

按写分配法：在写失效时，先把所写单元所在的块从主存调入Cache，然后再进行写入。

不按写分配法：写失效时，直接写入下一级存储器而不将相应的块调入Cache。

命中时间：CPU所要访问的块在Cache中，确认并取走所花费的时间开销。

失效率：CPU一次访存不命中的概率。

失效开销：CPU一次访存不命中，而额外增加的访存开销。

强制性失效：当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache。

容量失效：如果程序执行执行时所需的块不能全部调入Cache中，则当某些快被替换后，若又重新被访问，就会发生失效。

冲突失效：在组相联或直接映像Cache中，若不多的块映像到同一组中，则会出现该组中某个块被别的块替换，然后又重新被访问的情况。

2：1 Cache经验规则：大小为N的直接映像Cache的失效率约等于大小为N/2的2路组相联Cache的失效率。

计算机科学与技术考试：2022计算机系统结构真题模拟及答案(2)共126道题1、冯·诺依曼计算机的特点是（）。

Ⅰ．采用二进制Ⅱ．存储程序Ⅲ．控制流驱动方式Ⅳ．数据流驱动方式（单选题）A. 仅Ⅰ、ⅡB. 仅Ⅰ、Ⅱ、ⅢC. 仅Ⅰ、Ⅱ、ⅣD. Ⅰ、Ⅱ、Ⅲ、Ⅳ试题答案：A2、一个八路组相联Cache共有64块，主存共有8192块，每块64个字节，那么主存地址的标记x，组号y和块内地址z分别是（）。

（单选题）A. x＝4，y＝3，z＝6B. x＝1，y＝6，z＝6C. x＝10，y＝3，z＝6D. x＝7，y＝6，z＝6试题答案：C3、假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache 的总容量的位数至少是（）。

（单选题）A. 146KB. 147KC. 148KD. 158K试题答案：C4、CPU中，除了内部总线和必要的寄存器外，主要的两大部件分别是运算器和（）。

（单选题）A. 控制器B. 存储器C. CacheD. 编辑器试题答案：A5、下列关于RISC的叙述中，错误的是（）。

（单选题）A. RISC普遍采用微程序控制器B. RISC大多数指令在一个时钟周期内完成C. RISC的内部通用寄存器数量相对CISC多D. RISC的指令数、寻址方式和指令格式种类相对CISC少试题答案：A6、某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。

每个主存块大小为32字节，按字节编址。

主存129号单元所在主存块应装入到的Cache组号是（）。

（单选题）A. 0B. 1C. 4D. 6试题答案：C7、假设某计算机的存储系统由Cache和主存组成。

某程序执行过程中访存1000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是（）。

（单选题）A. 5%C. 50%D. 95%试题答案：D8、度量处理器CPU时钟频率的单位是（）。

计算机组成原理——主存储器考研题（2009）14.某计算机的Cache共有16块，采⽤2路组相联映射⽅式（即每组2块）。

每个主存块⼤⼩为32字节，按字节编制。

主存129号单元所在主存块应装⼊到的Cache组号是A.0B. 2C. 4D.6答案：C考点：Cache组相联映射⽅式主存按字节变址，第129号单元代表第129个字节。

主存129单元，所在的块号为129/32=4(从0开始编号)；由于Cache共有16块，采⽤2路组相联，因此共有8组，0，1，2， (7)主存的某⼀字块按模8映像到Cache某组的任⼀字块中，即主存的第0，8，16…字块可以映像到Cache第0组2个字块的任⼀字块中，⽽129号单元是位于第4块主存块中，因此将映射到Cache第4组2个字块的任⼀字块中。

21.假设某计算机的存储系统由 Cache 和主存组成，某程序执⾏过程中访存 1000 次，其中访问 Cache 缺失（未命中）50 次，则 Cache 的命中率是A 5% B.9.5%C. 50%D.95%答案：D考点：Cache命中率的计算（2010）17.下列命令组合情况，⼀次访存过程中，不可能发⽣的是( )A.TLB未命中，Cache未命中，Page未命中B.TLB未命中，Cache命中，Page命中C.TLB命中，Cache未命中，Page命中D.TLB命中，Cache命中，Page未命中答案：D考点：TLB，Cache，Page的含义。

TLB即为快表，快表只是慢表(Page)的⼩⼩副本，因此TLB命中，必然Page也命中，⽽当Page命中，TLB则未必命中，故D不可能发⽣；⽽Cache的命中与否与TLB、Page的命中与否并⽆必然联系。

（2012）17．假设某计算机按字编址，Cache 有 4 个⾏，Cache 和主存之间交换的块为 1 个字。

若 Cache 的内容初始为空，采⽤ 2 路组相联映射⽅式和 LRU 替换算法。

5.10 假设对指令Cache 的访问占全部访问的75%；而对数据Cache 的访问占全部访问的25%。

Cache 的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache 中一次load 或store 操作访问Cache 的命中时间都要增加一个时钟周期，32KB 的指令Cache 的失效率为0.39%，32KB 的数据Cache 的失效率为4.82%，64KB 的混合Cache 的失效率为1.35%。

又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。

试问指令Cache 和数据Cache 容量均为32KB 的分离Cache 和容量为64KB 的混合Cache 相比，哪种Cache 的失效率更低？两种情况下平均访存时间各是多少？解：（1）根据题意，约75%的访存为取指令。

因此，分离Cache 的总体失效率为：（75%×0.15%）＋（25%×3.77%）＝1.055%；容量为128KB 的混合Cache 的失效率略低一些，只有0.95%。

（2）平均访存时间公式可以分为指令访问和数据访问两部分：平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋ 数据所占的百分比×（数据命中时间＋数据失效率×失效开销）所以，两种结构的平均访存时间分别为：分离Cache 的平均访存时间＝75%×（1＋0.15%×50）＋25%×（1＋3.77%×50）＝（75%×1.075）＋（25%×2.885）＝1.5275混合Cache 的平均访存时间＝75%×（1＋0.95%×50）＋25%×（1＋1＋0.95%×50）＝（75%×1.475）＋（25%×2.475）＝1.725因此，尽管分离Cache 的实际失效率比混合Cache 的高，但其平均访存时间反而较低。

习题1：设主存容量1MB，Cache容量16KB，块的大小为0.5KB。

要求：写出主存地址格式；Cache地址格式；画出直接地址映像及变换图。

解题：主存地址格式：Cache地址格式：习题2：设主存容量1MB，字长32位，直接映像的Cache容量是512字。

Cache块长为8字。

请写出主存地址格式。

解题：Cache块长是8字，由于字长是32位，所以有32个字节，字地址有5位。

Cache容量是512字（题目给出）=512Χ32=211B，Cache地址格式是：主存地址格式：习题3：一个Cache的容量是2K字，每块为16字。

问：该Cache可容纳多少块；如果主存容量有256K字，有多少块；主存地址有多少位；Cache地址有多少位；在直接映射方式下，主存的第i块映射到Cache 中的第几块？解题：该Cache可容纳2K字/16字=128块；主存有256K字/16字=16384块；主存地址是18位（由于256K字=218）；Cache地址位11位（Cache容量是2K=211）；在直接映射方式下，主存的第i块映射到Cache中的第imod 128个块中。

习题4：一个采取4路组相联映像的Cache，其容量是16KB，主存容量是2MB，每个字块有8个字，每个字有32位。

请写出：（1）主存地址多少位（按字节编址），各字段如何划分？（2）设Cache起始为空，CPU从主存单元0，1……………101。

依次读出101字（主存一次读出一个字），并重复按此次序数读11次，问命中率为多少？（3）若Cache速度是主存的5倍，问采用Cache与不采用Cache速度提高多少倍？习题5：某计算机的组相联映像Cache由64个块组成，每组由4个块组成，主存块数4096，每块为128字，（1）写出Cache地址格式及位数。

（2）写出主存地址格式和位数。

（3）画出组相联映像方式变换示意图。

解题：（1）Cache由64块组成，而每组4块，因此Cache共有16组。

一．名词解释2:1Cache经验规则：大小为N的直接印象Cache的失效率约等于大小为N/2的两路组相联Cache的失效率。

通道处理机：通道的专用处理机，来专门负责整个计算机体系的输入/输出工作。

通道处理机只能执行有限的一组输入/输出指令。

透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。

向量处理机：设置了向量数据表示和相应的向量指令的流水线处理机称为向量处理机。

虚拟Cache：直接用虚拟地址进行访问的Cache计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。

系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。

同构型多处理机系统：由多个同类型或至少担负同等功能的处理机组成，它们同时处理同一作业中能并行执行的多个任务。

堆栈型机器：CPU 中存储操作数的单元是堆栈的机器。

累加器型机器：CPU 中存储操作数的单元是累加器的机器。

通用寄存器型机器：CPU 中存储操作数的单元是通用寄存器的机器。

数据相关：考虑两条指令i和j，i在j的前面，如果下述条件之一成立，则称指令j与指令i数据相关：（1）指令j使用指令i产生的结果；（2）指令j与指令k数据相关，而指令k又与指令i数据相关。

定向：用来解决写后读冲突的。

在发生写后读相关的情况下，在计算结果尚未出来之前，后面等待使用该结果的指令并不见得是马上就要用该结果。

如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。

指令级并行：简称ILP。

是指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。

指令的动态调度：是指在保持数据流和异常行为的情况下，通过硬件对指令执行顺序进行重新安排，以提高流水线的利用率且减少停顿现象。

是由硬件在程序实际运行时实施的。

指令的静态调度：是指依靠编译器对代码进行静态调度，以减少相关和冲突。

4路组相联cache设计实验报告实验报告一、实验目的本实验旨在实现4路组相联cache的设计，并用科学方法评价其性能。

二、实验内容（一）实现4路组相联cache实现4路组相联cache的功能，具体内容如下：1. 设计cache结构：设计4路组相联cache的数据结构；2. 编写读取程序：编写程序从cache中读取数据；3. 代码实现：利用设计的结构，实现cache的功能程序；4. 性能评估：采用科学可靠的方法评估程序的性能。

（二）运行实验1. 选择测试数据：采用规范的测试数据集，以便对结果进行科学评价；2. 调参：根据不同特征的数据集，调动cache结构上的参数，以获取最优性能；3. 性能评估：运行不同参数设定，定量评估4路组相联cache性能；4. 绘制图表：根据实验结果，绘制折线图，可视化实验结果。

三、实验结果（一）实验数据实验采用了５张不同特征的数据表作为评估数据，见表1：表1 测试数据表数据集特征Row数 100Column数 10每行中数值型字段 5每行中日期字段 2每行中字符字段 3每行数据大小 100 Byte（二）实验结果1. cache结构改进：依据不同测试数据表，改进cache结构，并增加数据对应的查找时间；2. 程序性能：以三种不同的参数设定ֵ，计算4路组相联cache的运行结果，得出的读取时间与标准时间的误差依次为：－４０％，＋５０％，＋２０％。

3. 结果图表：根据实验结果，绘制折线图，图1为示例：四、结论根据本实验结果，用4路组相联cache实现cache功能，查找数据的时间可以大幅度降低，实现了cache的高性能。

高速缓冲存储器cache程序的访问局部性程序的访问局部性定义在较短时间间隔内，程序产生的地址往往聚集在很小的一段地址空间内。

具体体现有两方面：时间局部性：被访问的某一存储单元，在一个较短的时间间隔内可能被再次访问；空间局部性：被访问的存储单元的邻近单元在一个较短的时间间隔内，可能也会被访问。

产生访问局部性的原因程序是由指令和数据组成的。

指令在主存中是按序存放的，存储单元是连续的，地址也是连续的，循环结构程序段或函数等子程序段再较短时间间隔内可能被重复执行，因此，指令的访问具有明显的局部化特性；数据在主存中的也是按序连续存放的，尤其是数组元素，常常被按序重复访问，因此，数据的访问也具有明显的局部化特性。

命中(Hit)：若CPU访问单元所在的块在cache中，则称为命中。

命中的概率称为命中率(Hit Rate)，是命中次数与访问总次数之比。

命中时，CPU在cache直接存取信息，所用的时间开销为cache的访问时间，称为命中时间(Hit Time)。

缺失(Miss)：若CPU访问单元所在的块不在cache中，则称为不命中或缺失，缺失的概率称为缺失率(Miss Rate)，是缺失次数与访问总次数之比。

缺失时，需要从主存读取一个主存块送cache，同时将所需信息送CPU，所用的时间开销为主存访问时间和cache访问时间之和。

通常将从主存读入一个主存块到cache的时间称为缺失损失(Miss Penalty)。

CPU在cache—主存层次的平均访问时间为。

由于程序访问的局部性特定，cache的命中率可以达到很高，接近于1，因此，即使Miss Penalty 远远大于Hit Time，但最终的平均访问时间仍可接近cache的访问时间。

cache工作流程程序执行中过程中，需要从主存取指令或读数据时，先检查cache是否命中，若命中，则直接从cache中读取信息送CPU进行运算，而不用访问主存储器；若缺失，则将访问地址内的数据送CPU进行运算，同时将当前访问的主存块复制到cache中。