层次化存储的根据:局部性原理
由时间局部性和空间局部性
层次化存储
这意味着所有的上层次的数据都是下层次数据的子集:只有数据先在第i+1层出现,才会在第i层出现.
SRAM与DRAM的价格差主要体现
S和D的实现面积有很大差别,在相同面积的硅上D能实现更多的存储容量,S的每比特占用面积要大很多.
S的每比特需要6到8个晶体管,过去是使用S芯片来作为一级或二级高速缓存
由于摩尔定律,现在所有的S高速缓存都集成在处理器芯片上.
同时呢,
S不需要刷新电路,使其访问时间接近处理器时钟周期.
D的特点
每比特采用单个晶体管,密度比S高.使用电容保存电荷,必须进行周期性的刷新.(动态的来源)
而S需要一直接通电源才可以保存数据.
层次化存储的各个媒介的技术研究方向
在SRAM和DRAM技术中,有很多细小的实现技术,是值得去研究的,而且这个存储技术也是影响计算机性能的重要因素.
cache的实现问题
将下一层的数据放入cache中,便于我们对于访问数据进行加速.
为了加速,我们需要知道访问地址的数据是否在cache中?我们如何快速定位cache中的目标数据?
这两个问题如果不好解决,就无从带来访问加速.
一定是地址相关性的
我们已经知道了目标数据的地址,但是我们可以利用该地址来进行映射cache.
最简单的映射就是直接映射,使用模运算来映射每一个地址.
根据逻辑推理,如果想要快速在cache中定位数据应该存在的位置并且判断其是否存在和是否有效,必须依赖于关于数据地址的一个函数.
如果使用的是直接映射方案(模函数),那么我们的cache就是由数据块,标签,有效位组成.
在索引cache的数据项时,我们是由经过数据块大小(对齐标准)的计算,过滤出块地址,然后由块地址来执行模运算.
cache的数据块容量的权衡问题
扩大数据块的大小,是在挖掘程序的空间局部性,所以扩大数据块的大小确实可以增加cache的命中率.
但是当数据块的大小占据了整个cache的一定比例,命中率就会下降,这很简单,因为数据块的数量下降了.
这导致,需要频繁置换数据块.
这还导致了另一个问题,数据块越大,失效损失就越大.因为失效损失由访问命中时间和数据传输时间组成.数据块越大,数据传输的时间就越长.
所以这中间需要达到一种平衡.
但是也可以通过设计出能支持大数据传输的技术,来减小失效损失,也是可以增加性能.
大数据块导致的失效损失长延迟问题–提早重启技术和请求字先行技术
当遇见失效时,我们所需要的数据在下一层的某个数据块中,在传输这个数据块时,如果所需数据被传输进cache中时,就继续执行,无需等待剩下的数据被传输进来.
最早采用该思想的技术称为"提早重启"(early restart).
1 | 在访问指令cache时,往往这种技术会得到很好的性能提升,这是因为指令是顺序执行,顺序存储的.但是在访问数据cache,效果不好.因为所需数据的访问顺序很难预测,在数据传输完成之前,下一个所需数据来自另一个数据块的概率比较大. |
解析:我们遇见的失效,只专注目前的失效损失,即使在访问数据cache时,出现失效,哪怕下一个数据是来自另外一个数据块,但是在这次的失效处理中,我们依然提升了数据传输到被利用的速度.
如果由于当前数据传输未完成导致处理器不能继续访问数据cache,那么流水线就必须停顿.
另一种更加复杂的技术,其原理与"提早重启"一致
具体的不同就是:在失效处理时,直接将所需数据传输过来,然后从所需数据的地址之后继续传输.该技术称为"请求字先行"(requested word first)或者关键字先行(critical word first)
关于存储设备的技术有很大的研究价值和学术方向选择价值,但是在这里不加描述
cache的基本原理
直接对主存访问,是非常消耗时间的,我们加一个cache,利于提高访问时间.
之前讨论过,cache对应于主存的映射,归根结底是跟地址有关.是跟地址的计算方式有关.
从cache角度来解释为何程序要指令/数据存储要以2的幂次对齐具有更高的效率
对于指令/数据存储在内存中,他们在被处理器访问时,都是被提早到cache中,cache对于内存的映射,是根据几位不同的二进制字段来执行的,最右边开始:字内索引->数据块内索引->数据块索引->标签
一个字是4Byte,所以在RISC-V中,指令/数据都是4字节对齐的.
非对齐存储的映射猜想
去掉字内索引+数据块内索引,剩下的数据块索引+标签组成了块地址.
如果我们在从真实地址获得块地址时,做了2的幂有关的除法,这会对小数取整,我们应该以向下取整来尽可能的包含所需的数据地址.
关于cache失效率,cache容量,数据块容量,失效损失的关系
cache容量大小与命中率问题–时钟周期长度与命中率需要一个平衡
cache容量大,会增加数据块大小和数据块的容量.
向从cache容量开始,cache是为了减少内存的访问时间,内存的访问时间长有两个原因:工业技术+索引时间.
工业技术越好,价格越贵,我们倾向于用来做cache或者寄存器,对于内存这种大容量,我们并不这样做,所以这个不用过多讨论.
对于索引时间,这个很好理解,空间越大,越难查找,这是不容辩解的.
如果cache的容量做大,那么处理器的命中时间就会增大,这个后果就是可能将处理器的时钟周期增大.
所以这里出现第一个辩证关系:cache容量越大,处理器时钟周期越长,如果不想时钟周期增长,就需要适当减少cache的容量.
cache的容量分配问题
cache容量确定下来,就需要确定单位数据块的大小和数量.
cache容量 = 单位数据块大小 * 单位数据块数量
如果我们的数据块增大,我们的命中率也是跟着增大的,因为这是挖掘程序的空间局部性.
数据块增大,导致单位数据块的数量减少,这会导致我们某些数据在被访问前,就被替换下去.
这是问题之一.
数据块增大,在访存失效时,由于传输的数据块较大,那传输时间也会增长,导致我们的失效损失增大.
这是问题之二
失效率与失效损失辨证–数据块大小需要一个平衡
如果我们的失效率很小,似乎这个失效损失很大的问题可以被淡化?
失效率跟cache的数据块容量有关,数据块容量增大,失效率减低,失效损失增大.
所以失效率减低,失效次数减少,导致失效损失即使代价增加,但是总代价是可以忍受的.
这中间需要一个平衡.
cache性能衡量不只是失效率的问题
综上所述,即使失效率低,但是失效损失很大,也是于事无补.
同时,跳脱出失效与否与代价的角度,现代cache设计为了提高cache带宽,是将混合cache分成了数据cache和指令cache.
这是为了能够在同一个周期中,指令cache和数据cache能够同时被访问,这是与现代流水线停顿所相投的.即使这样做会导致整体的cache失效率增加.
使用多路组相联策略减低失效率
直接映射对应的就是全相联,内存地址的数据可能出现在cache的任何一个位置.
当在cache中寻找时,我们就需要比对表项中的每一项来保证所需数据是否在cache中.
当然,我们仍然可以在比对表项这里做硬件加速:并行的比较.
这导致的后果就是硬件开销过大,所以这个方案不适合量大的cache.
优秀的设计来源于适当的折中.这句话在cache领域依然发挥着作用.
我们使用多路组相联策略,就是将cache分成m个组,每个组内可以存放n个数据块,内存映射通过直接映射策略来映射到对应的组中,在组内,数据是可以任意存放的,我们在组内查询数据的时候,应用全相联的方案,进行并行比对来查找.
提高相联度,我们确实下降了失效率,同时,在考虑cache性能时,容量和相联度并不是独立的,需要综合考量.
相联度越高,并不总是好的,首先是上述提高的硬件开销增加,其次就是相联度越高,组数下降,索引时间增加,导致命中时间增加,这可能导致处理器时钟周期增加
多路组相联cache组内选择数据块策略
增加硬件,并行的进行比较,这样可以避免增加命中时间.
4路组相联的cache中,需要4个比较器,用于比较标签值,同时比较结果通过一个4个与门(确定有效位有效),然后通过一个4to1选择器,输出对应的数据.
同时将四个与门通过一个或门,用于输出hit信号
减少失效率
选择LRU策略来替换cache中的数据块,增加其他的cache数据块的空间局部性和时间局部原理.
较少失效代价
使用多级cache来减少失效代价是一个好的选择
标准的算法分析通常都会忽略存储层次的影响.理解层次化存储的行为对于理解当今处理器的程序性能至关重要.
If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. All the images used in the blog are my original works or AI works, if you want to take it,don't hesitate. Thank you !