计算机组成——Cache
目录
为什么引入高速缓存？
数据查找方案：
命中率与缺失率
Cache和主存的映射方式
1.全相联映射
经典考法
覆盖问题
访存
2.组相联映射
3.直接映射（和组相联类似）
覆盖问题
替换算法
1.随机算法（RAND）
2.先进先出算法（FIFO）
3.最近最少使用原则
4.最近不经常使用算法
为什么引入高速缓存？
数据查找方案：
命中率与缺失率
Cache和主存的映射方式
1.全相联映射
经典考法
2.组相联映射
3.直接映射（和组相联类似）
替换算法
1.随机算法（RAND）
2.先进先出算法（FIFO）
3.最近最少使用原则
4.最近不经常使用算法
为什么引入高速缓存？
CPU的速度为0.2ns，内存的速度为20ns，为了弥补他们之间速度差，我们在CPU内引入高速缓存
数据查找方案：
方案一：先访问Cache未命中再访问内存
此时，查找数据的时间为 t=Htc+(1-H)(tc+tm)
方案二：CPU同时去Cache和内存当中查找数据
此时，查找数据的时间为 t=Htc+(1-H)tm
命中率与缺失率
设tc为访问一次Cache所需要的时间，tm为访问一次内存所需要的时间。
命中率H：CPU欲访问的信息已经在Cache中的比率
缺失率：M=1-H。
下面是一个例题—性能对比
Cache和主存的映射方式
1.全相联映射
全相联映射就是主存块可以放在Cache的任意位置
经典考法
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据Cache行，行长为64B.
按字节编址：256MB=2^28B——需要28位来储存块号
现在一个主存块的大小：64B=2^6B——需要更新块号分配
——此时，更新为22位用于块号寻址，6位用于块内寻址
下面进行全相联映射
首先我们一定需要有一个有效位，刚开始整个Cache都是空的，所以把他的有效位都标记为0
标记的大小也为22位（同块号）
注意Cache块本身也有3位地址（以下图为例子），一个cache块内部也有6位的地址（cache块的大小同主存块相同都为64B），所以这是大小给你的可能是（1+22+3+6）要区分清楚
覆盖问题
当Cache满了，我们在这里涉及到淘汰策略
访存
现在全相联映射结束之后，CPU要访问某一个字节1...10110010101010010，怎么办？
给地址分段，区分出来哪是有效位、标记、Cache块号、块内地址
2.组相联映射
组相联映射：每一个主存块可以被放到特定分组当中的任意一个位置，具体放到哪个分组，可以用主存块号对总的分组数进行一个取余操作
3.直接映射（和组相联类似）
直接映射主存块在Cache中的位置=主存块号%Cache总块数
覆盖问题
如果采用直接映射的方式，他有一个显而易见的缺点，就是虽然这Cache里面还有很多空闲的Cache块，但是不能用，我们只能把这些主存块放到固定的位置。
和全相联比灵活性差一些，空间利用率也不充分
思考：我们用22位的标记（即把主存号全部保存下来），这个方式是否可以进行优化？
如下图，每个主存块号的末尾是三位正好对应着Cache块号，所以在这个例子当中我们只需要记录内存号前边的19位即可。（这取决于Cache块的大小）
因此，如果采用直接映射，原本的主存块号可以再细分为两个部分。前面的19位作为标记，后面三位反应每一个主存块号在哪一个Cache行中
访存
1+19+3+6=29 通过29位地址即可实现访存
替换算法
替换算法是针对于全相联映射和组相联映射
1.随机算法（RAND）
如果Cache块满了，我们随机选择一块进行替换，非常自由
2.先进先出算法（FIFO）
我们会优先替换掉最先进入Cache的块
出现抖动现象——刚换出的块，很快又被访问
3.最近最少使用原则
添加一列计数器，用于记录cache块里存放的主存块多久没有被放问过，一旦被访问到计数器清零。最终我们会替换计数器最大的一个cache块
注意！！
这里不变了——因为Cache块的总数是2，则计数器需要n位，且Cache块装满后所有计数器的值一定不重复。
如果我们频繁访问到的主存块的数量大于cache行数，就会发生抖动现象。
4.最近不经常使用算法
与最近最少使用不同，该计数器记录被访问的次数，每次替换计数器最小的块
为什么引入高速缓存？
CPU的速度为0.2ns，内存的速度为20ns，为了弥补他们之间速度差，我们在CPU内引入高速缓存
数据查找方案：
方案一：先访问Cache未命中再访问内存
此时，查找数据的时间为 t=Htc+(1-H)(tc+tm)
方案二：CPU同时去Cache和内存当中查找数据
此时，查找数据的时间为 t=Htc+(1-H)tm
命中率与缺失率
设tc为访问一次Cache所需要的时间，tm为访问一次内存所需要的时间。
命中率H：CPU欲访问的信息已经在Cache中的比率
缺失率：M=1-H。
下面是一个例题—性能对比
Cache和主存的映射方式
1.全相联映射
全相联映射就是主存块可以放在Cache的任意位置
经典考法
假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据Cache行，行长为64B.
按字节编址：256MB=2^28B——需要28位来储存块号
现在一个主存块的大小：64B=2^6B——需要更新块号分配
——此时，更新为22位用于块号寻址，6位用于块内寻址
下面进行全相联映射
首先我们一定需要有一个有效位，刚开始整个Cache都是空的，所以把他的有效位都标记为0
标记的大小也为22位（同块号）
注意Cache块本身也有3位地址（以下图为例子），一个cache块内部也有6位的地址（cache块的大小同主存块相同都为64B），所以这是大小给你的可能是（1 22 3 6）要区分清楚
覆盖问题
当Cache满了，我们在这里涉及到淘汰策略
访存
现在全相联映射结束之后，CPU要访问某一个字节1...10110010101010010，怎么办？
给地址分段，区分出来哪是有效位、标记、Cache块号、块内地址
2.组相联映射
组相联映射：每一个主存块可以被放到特定分组当中的任意一个位置，具体放到哪个分组，可以用主存块号对总的分组数进行一个取余操作
3.直接映射（和组相联类似）
直接映射主存块在Cache中的位置=主存块号%Cache总块数
覆盖问题
如果采用直接映射的方式，他有一个显而易见的缺点，就是虽然这Cache里面还有很多空闲的Cache块，但是不能用，我们只能把这些主存块放到固定的位置。
和全相联比灵活性差一些，空间利用率也不充分
思考：我们用22位的标记（即把主存号全部保存下来），这个方式是否可以进行优化？
如下图，每个主存块号的末尾是三位正好对应着Cache块号，所以在这个例子当中我们只需要记录内存号前边的19位即可。（这取决于Cache块的大小）
因此，如果采用直接映射，原本的主存块号可以再细分为两个部分。前面的19位作为标记，后面三位反应每一个主存块号在哪一个Cache行中
访存
1+19+3+6=29 通过29位地址即可实现访存
替换算法
替换算法是针对于全相联映射和组相联映射
1.随机算法（RAND）
如果Cache块满了，我们随机选择一块进行替换，非常自由
2.先进先出算法（FIFO）
我们会优先替换掉最先进入Cache的块
出现抖动现象——刚换出的块，很快又被访问
3.最近最少使用原则
添加一列计数器，用于记录cache块里存放的主存块多久没有被放问过，一旦被访问到计数器清零。最终我们会替换计数器最大的一个cache块
注意！！
这里不变了——因为Cache块的总数是2，则计数器需要n位，且Cache块装满后所有计数器的值一定不重复。
如果我们频繁访问到的主存块的数量大于cache行数，就会发生抖动现象。
4.最近不经常使用算法
与最近最少使用不同，该计数器记录被访问的次数，每次替换计数器最小的块
若有多个计数器最小的行可按照行号递增或FIFO算法淘汰
注意！！
这个计数器并没有上限，这就意味着我们需要更多的bit位存储
若有多个计数器最小的行可按照行号递增或FIFO算法淘汰