1、计算机组成原理课外实践报告Cache 的不同映射算法2011 年 12 月 28 日星期三一 实验目的1. 加深掌握 Cache 的三种地址映射方式，即全相联映射、直接映射和组相联映射的映射原理和不同映射方式下主存的逻辑划分。 2 加深理解替换 Cache 原存数据块的四种算法，即先进先出 FIFO(First In First Out) 算法、近期最少使用 LRU(Least Recently Used)算法、最不经常用 LFU(Least Frequently Used)算法和随机替换(Random Replacement)算法的算法原理和算法过程。3 复习 C 语言基本知识，学习并熟悉利
2、用 c 语言编写图形界面的方法，丰富自己的 C 语言技能。二 实验要求1 实现 Cache 与主存的三种地址映射过程，可以自定义主存地址。2 实现四种常用替换算法。3 使用 c 语言实现图形界面人机交互，界面简洁直观。三 实验原理Cache 的工作原理（1）为了便于比较和快速查找，Cache 和主存都被分成大小相等的块，每块包含若干个字，每个字又由多个字节组成，主存和 Cache 都是按字节编址。（2）在不同的映射方式下，主存和 Cache 进行不同的逻辑划分，具体划分如下：全相联映射方式下主存的逻辑划分为：块地址（Tag） 块内地址直接相联映射方式下主存的逻辑划分为：主存区号（Tag） 区内
3、块号(索引) 块内地址组相联映射方式下对主存的逻辑划分为：Cache 的组织方式为： V Tag Cache 行号 行内地址 数据体其中 V 是标志 Cache 快中数据是否有效的标志位，Tag 是与主存 Tag 相对应的标志，也是根据主存地址在 Cache 中查找的数据是否为所需的依据。行内地址是查找具体字节的依据。本次实践假定的主存和 Cache 容量如图 1-1 所示，所以在全相联映射中，如地址值为 1，则二进制地址为：000000000000000000001。若采用全相联映射，则主存地址被划分为：00000000000000 0000001，即前 13 位为 Tag,后七位为块内地址
4、；若采用的是直接映射方式，则主存地址被划分为：0000000000 0000 0000001，前 9 位 0000000000 为主存区号，与 Cache 的 Tag想对应,第 10-13 位 0000 为区内块号，与 Cache 的行号相对应，第 14-20 位0000001 为块内地址；若采用的是二路组相联，则主存地址被划分为：00000000000 000 0000001，前 10 位为主存组号与 Cache 的 Tag 想对应,第 11-13 位是组内块号，3 位表示 8 块与 Cache 的 8 组相对应，组内块号为 000 的主存块将映射到 Cache 行号为 000x 的行。主存
5、组号（Tag） 组内块号(索引) 块内地址图 1-1 假定的主存和 Cache 容量及划分（3）直接映射方式主存块和 Cache 块是一一对应的，所以不需要选择替换算法，换而言之四种替换算法只有在映射方式是全相联映射和二路组相联映射时才起作用。先进先出 FIFO 算法的基本思想是按照数据进入 Cache 的先后决定替换的顺序，即在需要替换的时候，选择最先调入 Cache 的块作为替换块，这种方法要求为Cache 中每块数据记录他们进入 Cache 的先后次序，在程序设计时，使用两个数组Number16、Number182分别记录在全相联映射方式下和二路组联的方式下的数据进入的次序。在全相联映射
6、方式下，Number16数组中元素的值，根据进入Cache 的先后次序分别为 1,2,3,15,16 Cache 被数据填满之后 Numberi为 1 的块被替换掉，新的被替换第 i 行的 Numberi值为 16，其余每个值都减 1，其中0= 全相联映射(1) 进入全相联映射单击主界面左上方的全相联映射和左下方的某一个替换算法，在程序的编辑框内输入地址，地址的范围为 0-1048575（因为主存的容量为 1MB）, 如果各种选项的选择和输入的地址没有错误将运行得到正确的结果如图 1-3 示， 如果没有选择映射方式和替换算法程序将会给出相应的提示，没有选映射方式时程序给出提示如图 1-4，如果
7、选择了全相联映射方式却没有选择替换算法程序会给出相应的提示如图 1-5,如果选中的替换算法超过一个，程序也会给出提示，选中替换算法超过一个时程序给出提示如图 1-6。如果程序没有输入地址会给出提示如图 1-7，若输入的地址值超出返回也会给出相应的提示如图 1-8 所示。如图 1-3 10 进制地址 1234 转化为二进制地址得：0000000001001 10100100000000001001 为块地址对应于 cache 的 Tag,在 Cache 和主存中用相应的颜色表示，由于本次是第一个数据，所以全相联映射与 Cache 的第 1 行，行号为0000， 左侧显示了已被占有的 Cache
8、行，编辑框内的结果如图灰色部分显示，右侧主存显示了第 0-14 块其余的用省略号表示，如图中 1-3 的右下方最后一个矩形内。由于映射方式是全相联映射那么在 Cache 没有被数据块占满的情况下，Cache的映射将会按照顺序来，在图 1-3 的情况下我们在输入一个值 123456 转化为二进制地址值为 0001111001100 1000000，结果如图 1-9 所示，图中主存区显示了以0001111001100 为开始的连续的 14 个快，最上方的矩形中的省略号表示主存中还有更小的地址，最下方一个矩形中的省略号表示，还有更大的地址。图 1-3 全相联方式下正确的选择和填写示例图 1-4 没有
9、选择映射方式就查询时给出的提示示例图 1-5 选择了全相联映射方式没有选择替换算法时的提示示例图 1-6 选择了全相联映射方式并且选择了多个替换算法时的提示示例图 1-7 没有输入地址值就查询时的错误输出提示示例图 1-8 如果选择的地址值超过范围给出的错误提示示例图 1-9 全相联模式下的 Cache 没有满时顺序存储示例(2) 全相联映射方式下替换算法的演示为了方便演示分别输入以下数据 2 次，数据 384 除外：0,128,256,384,512,640,768,896,1024,1152,1280,1408,1536,1664,1792,1920如果是选择了先进先出算法的话，当再次输入
10、一个数据 2500 时，那么数据 0 最先进入 Cache 的第一行，那么第一行将被替换。接着上面的操作，再输入一次2500，则 2500 也命中了两次，改变选择 LFU 如果此时输入数据 3000，则 只有384 所在的第 4 行访问了 1 次，所以是最不经常访问的第四行被替换。然后改变替换算法为 LRU，以上的输入中 128 所在的第二行是近期使用最少的一行，所以输入 4000 以后第 2 行将被替换，然后该选择随机替换算法，输入 6000 第1 行将被替换。当输入 1920 结束后程序结果如图 2-1 所示，由于输入的 16 个数据所在主存快分别为 0-15,所以块号的后 4 位应为 0
11、000-1111,得到的 Cache 的 Tag 后 4 位也应该如此，看图 2-1 中 Tag 确实如此，进一步证明了映射结果的正确性。输入 2500 后结果如图 2-2 所示，第 1 行被替换；如图 2-3 改变替换算法为LFU，输入 3000 后第 4 行被替换；如图 2-4 改替换算法为 LRU，输入 4000 后,第 2 行被替换；如图 2-5 改算法为随机替换后，输入 6000,第 1 行被替换。注意图中提示的该行被替换式指的图中灰色区域，而且灰色区域显示的是替换后的结果，图中显示的结果与事先预料的结果相符，说明四种算法都得到了有效的、正确的使用。图 2-1 输入 16 个数之后 Cache 已满的情况图 2-2 全相联映射先进先出替换算法的演示
