计算机体系结构cache模拟器实验报告.doc

计算机体系结构——
Cache模拟器实验
实验报告
姓名 崔雪莹
学号 12281166
班级 计科1202班
老师 董岚
2015年 06月07日
一、 阅读分析附件模拟器代码 2
1、关键参数 2
2、关键算法 3
二、 课后习题 5
1、习题内容 5
2、题目分析 5
3、计算及结果 6
4、模拟器上实验结果检验 7
三、 整体分析 8
1、三种映射方式对Cache效率得得影响 8
2、block块大小与Cache容量对Cache效率得影响 8
3、Cache容量与相连度对Cache效率得影响 9
4、三种失效类型影响因素 9
四、 实验思考与感受 10
1、关于模拟器得思考 10
2、关于整个实验得思考 10
一、 阅读分析附件模拟器代码
1、关键参数
（1） 用户可见参数:(用户通过命令行输入参数)
参数名
含义
值
备注
choice
映像方式选项
1/2/3
1为直接映射,2为组相连映射,
3为全相连映射
cachesize
Cache大小
16/64/128/256
以字节为单位
blocksize
Block大小
1/2/4
以字为单位
assoc
相连度
1/2/4/8/16
assoc路组相连(n-way)
accesscount
请求次数
待输出
等于project、txt得值个数
hitcount
命中次数
待输出
成功在Cache找到次数
hitrate
命中率
待输出
HitRate= hitcount/accesscount
misscount
未命中次数
待输出
没在Cache找到次数
misscount = 1-hitcount
missrate
未命中率
待输出
MissRate= misscount/accesscount
c1c ,c2c ,c3c
失效次数
待输出
分别为三种失效类型得次数
(2)程序内部主要参数:(代码内部重要参数)
参数名
含义
计算
备注
blockinbyte
块得字节大小
=blocksize*4
每一个块占多少字节
NOofblock
块个数
=cachesize/blockinbyte
Cache中多少个块
NOofset
组个数
=NOofblock/assoc
块分成了多少个组
bytearray[]
要访问得数据得字节地址
=projec、txt中得值
project、txt文件数据赋给了bytearray[]数组
wordaddress[]
要访问得数据得字地址
=bytearray[j]/4
blocksize就是字为单位得,就就是说一个block占多少个字,所以数据也要求字地址
blockaddress[]
数据得块地址
=wordaddress[]/blocksize
数据在第几块
index
索引位(组地址)
=blockaddress[j]%NOofset
若Noofset=2^m,则块地址低m位为索引位(组地址)。
tag
标识位(组内寻址)
=blockaddress[j]/NOofset
块地址高(32-m)位为标识位,用于确定组内哪块数据,newarray[index][z+1]中存放
*valid
有效位
有效为1,失效为0
判断该cache块数据就是否有效*就是因为没有真正定义,只就是存放newarray[index][z]中
lru[index][z]
最近未被使用次数
每次加1,被重写置0
替换时,替换掉lru[index][]值最大得那个块
2、关键算法
注:这里不粘贴代码,只就是进行简单得代码算法说明
（1） 块地址表示:
注:图就是我按照自己得想法自己画得,可能有些地方并不准确,望老师指正。图中以一个例子来解释cache模拟器中block与数据地址得关系,以及与组地址与标志位得关系。

（2） Index与tag:
由上面计算: index = blockaddress % NOofset index = 16 % 8 = 2
tag = blockaddress / Noofset tag = 16/8 = 2

以上例,字地址16为例,写成二进制为0001 0010 B,其中组数为8,又因为2^3=8,所以字地址取后3位为:index = 010 B = 2 ,取前29位为:tag = 0…0010 B = 2 。所以,算法与理论就是一致得。
（3） Valid:
有效位。当通过上述方式寻址找到了数据存放得数据块,接下来判断有效位:
有效位为1,说明数据就是有效得,可以从block提取数据;
有效位为0,说明块里得数据就是无效得,所以不能从block提取数据,出现miss,此时判断miss类型,同时需要访问内存或下一级存储,将数据放到cache里。
（4） 失效类型及判断方法:
判断失效类型,函数misstype(int ba ,int nb ,int l)。
pulsory miss(强制性失效,冷启动):当第一次访问某一个块得时候,数据就是肯定不在块中得,此时出现强制性失效,或者说就是冷启动失效。
Capacity miss(容量失效):所需得数据不能全部调入cache中,块被替换后又被重新访问,意思就就是当所有得块都被占满了,这样又有数据希望被调入缓存时,就出现了容量失效。
Conflict miss(冲突失效):在组相联或直接映像中,数据想要替换进某一组中,组内得块都被占满了,但就是别得组得块有空余,数据只能替换这一组,尽管别得组有空余也不能替换。这样就出现了冲突失效。
（5） LRU算法实现替换:
LRU替换算法就是采用最近最久未使用得块,其中Lru[][]数组存放最近多少次未被使用,因为就是采用循环访问,当循环访问到这一组时,把这组所有得块得Lru[][]值都加1,如果成功访问到这一块,数据能从其中取出来,就把这一块得Lru[][]值置0,退出循环。
（6） 直接映射、组相联映射、全相联映射:
直接映射:就是特殊得组相联映射,就就是相联度为1得组相联映射。所以采取与组相联一样得程序与算法,当识别该组第一块失效时,直接进行替换,因为有且只有一块。
组相联映射:当识别该组某块失效时,如果块都被占满,要根据Lru[][]值得大小,判断哪一块被替换掉。
全相联映射:从上到下cache块存数据,则从上到下循环即可,遇到失效时,要根据Lru[][]值得大小,判断哪一块被替换掉。
二、 课后习题
1、 习题内容
在CacheSimulator模拟器上模拟如下程序得运行过程:
int i,j,c stride,array[256]
for(i=0;i<10000;i++)
for(j=0;j<256;j=j+stride)
c = array[j]+5;
假设Cache总大小就是256个字节,且块大小为16字节(4个字)。
同时假设内存当中只有这一个程序在运行,而且整形数字得长度为一个字长(字长为32位),在直接相连映射下,stribe分别等于132、131时程序得运行结果,并分析原因。而当采用两路组相连时又会有什么结果并分析原因。
2、 题目分析
当stribe = 132/131 时,程序相当于循环访问内存偏移地址为0与地址132/131得内容,循环10000次,也就就是访问了2000次存储。
结合cache机制,cache大小为256个字节,块大小为16个字节,所以块得个数为256/16 = 16个。若为2路组相连,则有16/2 = 8组。
当第一次访问块时,一定会发生强制性失效,计一次miss。
3、 计算及结果
1） 直接映像时:
l stride=132
array[0]得块地址为0,映射到cache得块号为0:
0 mod 16 = 0
array[132]得块地址为132/4 = 33,映射到cache得块号为1:
33 mod 16 = 1
因为第一次访问cache,0与1一定会发生强制性失效,之后因为调入cache,不会发生失效。则失效次数为2,则失效率为:
2/20000 = 0、01%
命中次数为19998次,命中率为:
19998/20000 = 99、99% = 1(近似)
失效类型为强制性失效,次数为2。
l stride=131
array[0]得块地址为0,映射到cache得块号为0:
0 modulo 16 = 0
array[131]得块地址为131/4 = 32,映射到cache得块号为0:
32 modulo 16 = 0
因为第一次访问cache,0一定会发生强制性失效,之后cache里块号为0得块不断地被替换写入替换写入,此时发生冲突失效。则失效次数为20000,则失效率为:
20000/20000 = 1 = 100%
命中率为0。失效类型为强制性失效次数1,冲突失效次数为19999。
2） 2路组相联:
l stride=132
array[0]得块地址为0,映像到cache得组号为0:
0 modulo 8 = 0
array[132]得块地址为132/4 = 33,映像到cache组号为1:
33 modulo 8 = 1
因为第一次访问cache,0与1一定会发生强制性失效,之后因为调入cache,不会发生失效。则失效次数为2,则失效率为:
2/20000 = 0、01%
命中次数为19998次,命中率为:
19998/20000 = 99、99% = 1(近似)
失效类型为强制性失效,次数为2。
l stride=131
array[0]得块地址为0,映像到cache组号为:
0 modulo 8 = 0
array[131]得块地址为131/4 = 32,映像到cache组号为:
32 modulo 8 = 0
因为第一次访问cache,0与1一定会发生强制性失效,之后因为就是2路组相联,array[0]与array[131]都在0组,不会发生失效,则失效次数为2,失效率为:
2/20000 = 0、01%
命中次数为19998次,命中率为:
19998/20000 = 99、99% = 1(近似)
失效类型为强制性失效,次数为2。
4、 模拟器上实验结果检验
注:因为例题得循环次数为10000,为了便于实验,我将循环次数设置为100,结果参照100得计算,原理就是一致得。因为实际131/132都就是字地址,而project、txt设置得就是字节地址,所以将project、txt里值设置为0 与 132*4/131*4 循环100次,设置cache大小为256,block大小为4,可以分别瞧到直接映射与2路组相连映射得结果为:
直接映射
stride=132
stride=131
miss count
　2
　200
miss rate
　0、01
　1、00
hit count
　198
　0
hit rate
　0、99
　0
access count
　200
　200
c1c(强制性失效)
　2
　2
c2c(容量性失效)
　0
　0
c3c(冲突性失效)
　0
　198
2路组相连映射
stride=132
stride=131
miss count
　2
　2
miss rate
　0、01
　0、01
hit count
　198
　198
hit rate
　0、99
　0、99
access count
　200
　200
c1c(强制性失效)
　2
　2
c2c(容量性失效)
　0
　0
c3c(冲突性失效)
　0
　0
可以瞧到实验结果与计算就是一致得(因为循环次数100,所以实验结果小数点要后移两位)。同时对习题1得思考(见后)也证明就是正确得。
（1） 直接映射:stride = 132 截图

（2） 直接映射:stride = 131 截图

（3） 2路组相连:stride = 132 截图

（4） 2路组相连:stride = 131 截图

三、 整体分析
1、 三种映射方式对Cache效率得得影响
其她相同条件:block大小为2,组相连相连度为4,project、txt为200个0~1000得随机数。
cache容量(字节)
映射方式
直接映射
组相连
全相连
64
0、94
0、935
0、925
128
0、87
0、875
0、865
256
0、79
0、79
0、785
512
0、68
0、63
0、61
1024
0、50
0、50
0、50
生成图表:

此时可以瞧到:
1. 直接映射得失效率高,组相连失效率中等,全相连失效率最低
2. 随着cache容量得增加,失效率越小。
3. 当cache容量为1024时,因为数据取值得原因,三种方式失效率相等,说明当cache容量足够大,三种方式失效率就是一样得。
2、 block块大小与Cache容量对Cache效率得影响
其她相同条件:直接映射,相连度为1,project、txt为200个0~1000得随机数。
块大小(字)
Cache容量(字节)
64
128
256
512
1024
1
0、94
0、885
0、83
0、77
0、69
2
0、94
0、87
0、79
0、68
0、50
4
0、95
0、905
0、80
0、635
0、30
8
0、945
0、89
0、785
0、575
0、155
生成图表:

此时可以瞧到:
1. 对于给定得cache容量如64字节,当块大小增加时,失效率先就是下降,后来反而上升了。
2. Cache容量越大,使其失效率达到最低得块得大小就越大。
3. 因为取得数据样本就是随机得,不就是连续得,实验数据并不就是十分准确,比如cache容量128时,块大小出现两次失效率
3、 Cache容量与相连度对Cache效率得影响
其她相同条件:组相连,块大小2,project、txt为200个0~1000得随机数。
Cache容量(字节)
相连度/路
1
2
4
8
64
0、94
0、93
0、915
0、905
128
0、875
0、87
0、86
0、87
256
0、785
0、765
0、80
0、78
512
0、645
0、64
0、67
0、66
1024
0、535
0、535
0、535
0、535
生成图表:

此时可以瞧到:
1. 提高相连度会使失效率下降。
2. 因为取得数据样本就是随机得,不就是连续得,实验数据并不就是十分准确。
3. 当容量为1024时,也就就是cache一定大时,失效率没什么区别。
4、 三种失效类型影响因素
(1)相连度对三种失效类型影响:
其她相同条件:cache大小为256,block大小为2,组相连,project、txt为200个0~1000得随机数。
相连度(路)
总失效率
总失效次数
失效类型
强制性失效
容量失效
冲突失效
1
0、78
156
107
38
11
2
0、80
160
107
40
13
4
0、765
153
107
41
5
8
0、785
157
107
45
5
16
0、785
157
107
46
4

可以瞧出:
1. 强制性失效,即冷启动,不受相连度得影响。
2. 容量失效基本不受相连度影响,但因为数据偶然性,出现增大趋势。
3. 冲突失效随着相连度得增加而降低。
(2)Cache容量对三种失效类型影响:
其她相同条件:block大小为2,组相连度为4,project、txt为200个0~1000得随机数。
cache容量(字节)
总失效率
总失效次数
失效类型(相对百分比)
强制性失效
容量失效
冲突失效
64
0、93
186
107
78
1
128
0、87
174
107
65
2
256
0、765
153
107
41
5
512
0、64
128
107
13
8
1024
0、535
107
107
0
0

可以瞧出:
1. 容量越大,失效率越小。
2. 强制性失效不受容量大小得影响。
3. 容量失效随着容量得增加而大大减小。
4. 冲突失效不受容量大小得影响。
四、 实验思考与感受
1、关于模拟器得思考
Cache大小可选为16/64/128/256,因为代码写了,但就是没有增加选项。但就是,我考虑因为16实在太小了,没什么意义。
打开文件 名字为project、txt,修改文件名。
个人感觉有地方不太合适,因为直接映像就就是特殊得组相联映射,所以相联度一定为1,但就是代码中并没有设计这一点,当一个完全不懂得人使用时,很有可能设置相联度大于1,造成错误。另外我觉得可以把三种方式各封装在一个自己得函数里,这样代码更加清晰。
有困惑我得问题,我就是通过阅读代码才比较清晰得理解cache实现得,但就是模拟器给出得地址映射得方法就是将数据字节地址转换为字地址,又将字地址转换为块地址,对块地址进行取模运算。而习题1就是直接对字地址进行取模运算,方法明显不一致。通过我重新阅读习题1得题目,发现实际习题1得132/131就是字地址,因为定义得int array[]数组定义得就是整数字长,所以132/131指得就是地址为字地址,例如两个地址之间就是一个整数字长。
2、关于整个实验得思考
这次实验就是我大学做得最用心得一次实验,没有之一。我在仔细得阅读实验代码后,知道了内存得物理地址就是怎样转换为cache得块号或组号得。我根据自己得理解,画了一个模拟寻址图,更加清晰得知道原理,理顺清楚到底就是怎么一回事,收获很大。
在做整体分析时,我采用图表折线图得方式,更加直观得瞧出数据得走势。但就是我最初得设想采样样本就是像一条平滑得曲线一样,自动得生成一组相对连续得数据,但就是我只会生成随机数。而随机数就是离散得,所以,以后有机会,我希望采用连续数据得样本,重新得出更加准确得结果。
总体来说,实验还就是相对简单得,但就是注重理解。理论与实践结合起来,加深了我对cache部分学习得理解,同时,也锻炼了我自主思考,自主学习得能力。比如,整体分析部分,采用不同变量结果比较方法等等。希望在今后得学习当中,继续保持,继续进步。