本文共 5526 字,大约阅读时间需要 18 分钟。
Cache
中,从而提高程序执行速度。//程序A:int sumarrayrows(int a[10][10]){ int x, y, sum=0; for( x=0; x<10; x++) for( y=0; y<10; y++) sum += a[x][y]; return sum;}//程序B:int sumarraycols(int a[10][10]){ int x, y, sum=0; for( y=0; y<10; y++) for( x=0; x<10; x++) sum += a[x][y]; return sum;}
A
访问数组时是按照数组的存放顺序访问的,空间局部性好;而程序 B
则每次都要跳过 10 个数组元素,当主存与 Cache
的交换单位小于这 10 个元素的大小时,则每次访问一个元素都需要装入一个主存块到 Cache
中,没有空间局部性。 由此,也应该认识到,平时遍历数组时,在无特殊要求的情况下,数组的访问顺序应该和数组的存放顺序一样。Cache
通常用 SRAM
制造,基本结构如上。Cache
和主存划分成等大的块,Cache 块称作 Cache 行
,由若干字节组成,块的长度称为块长或Cache 行长
,由于空间有限 Cache 块远少于主存的,因此仅保存主存中最活跃的若干块的副本。Cache 的数据读写操作一般如下步骤:
CPU 发出读请求
,若访存地址在 Cache 中命中
,直接将地址转换为 Cache 地址并从 Cache 中进行读操作
,无需访问主存;若 Cache 不命中,则访问主存并将数据对应的主存块放入 Cache
,主存块调入 Cache 中又分为两种情况:未满,直接调入
;已满,使用某种替换算法
,用调入的块替换 Cache 中原有的某块。CPU 与 Cache 之间以字为单位交换数据,Cache 与主存之间以 Cache 块为单位交换数据。
某些计算机采用 Cache 和主存同时访问的方式,当 Cache 命中则主存的访问停止,否则继续访问主存并将数据调入 Cache。
CPU
欲访问的信息已在 Cache 中的比率称之为命中率。在一个程序执行期间,Cache
的总命中次数为 Nc
,访问主存的次数为 Nm
,则命中率 H 为:
H = Nc / (Nc + Nm)
H 越接近 1 越好。设 Tc 为命中时 Cache 访问时间,Tm 为未命中时的访问时间,1-H 表示未命中率,则 Cache-主存系统的平均访问时间 Ta 为:
Ta = HTc + ( 1 - H)Tm
。 例题:
设有 Cache 是主存速度的 5 倍,Cache 命中率为 95%
,则采用 Cache 比没用 Cache,存储器的性能提高多少?
解:
Ta = 0.95*t + 0.05*5t = 1.2t
副本
,所以,通常 Cache 块中都有一个用于指明当前块是主存中哪一块的副本的标记
,同时也有一个用于确定当前 Cache 是否有效的有效位
。地址映射是指把主存地址空间映射到 Cache 地址空间
,这和地址变换(指 CPU 访存时,将主存地址按映射规则换算成 Cache 地址的过程)不同,常用的地址映射方法有:直接映射、全相联映射和组相联映射
。主存块只能装入 Cache 中的唯一位置
,若位置上已有内容,则块冲突那么直接将原有信息无条件替换
出去。j = i mod 2^c
t = m - c
的标记 tag,当主存某块调入 Cache 后,就将其块号的高 t 位设置在对应 Cache 行的标记中。 若相等且有效位为 1,则访问 Cache “命中”
,此时根据主存地址中低位的块内地址在对应 Cache 行读取信息;若不相等或有效位为 0,则“不命中”
,此时 CPU 从主存读出该地址所在的一块信息并调入对应的 Cache 行中,将有效位置 1,并将标记设置为地址的高 t 位
,同时将该地址中的内容送入 CPU。主存中地每一块可以装入 Cache 中地任何位置,每行地标记用于指出该行取自主存地哪一块,所以 CPU 访存时需要与所有 Cache 行标记进行比较
。将 Cache 空间分成大小相同地组,主存地一个数据块可以装入一组内地任何一个位置,即组间采取直接映射,组内用全相联映射
: j=i mod Q
组号找到对应 Cache 组
,再在组内对所有 Cache 行进行高位标记比较
,若有一个相等且有效位为 1,则命中
,再根据主存地址中的块内地址
,在对应 Cache 行读取信息;若不想等或相等但有效位为 0,则不命中
,此时访问主存块并将主存块的信息调入对应 Cache 组的任意一个 Cache 空闲行,将有效位置 1
,同时将信息送往 CPU。28 - 6 - 3 = 19
位就是标记位
,所以 Cache 总容量 8*(1 + 19 + 512) = 4,256 位
。3200B / 64B = 50
;Cache 有 8 行,50 mod 8 = 2
,因此对应的 Cache 行号为 2
.两个 Cache 行合并,组内全相联映射,组间直接映射
,所以 50 mod 4 = 2
, 对应的组号为 2,即对应的 Cache 行号为 4 或 6.直接映射的命中率最低,全相联映射的命中率最高
;直接映射的判断开销最小、所需时间最短,全相联映射的判断开销最大、所需时间最长
;直接映射标记所占的额外空间最小,全相联映射标记所占的额外空间开销最大
全相联映射和组相联映射
方法中,信息从主存调入 Cache 中时都要用到 Cache 块替换算法
,常用的 Cahce 块替换算法有:随机(RAND
)算法、先进先出(FIFO
)算法、近期最少使用(LRU
)算法和最不经常使用(LFU
)算法。计数器
,计数值表示主存块的使用情况,根据计数值决定淘汰哪一块
,计数值的位数与 Cache 组大小有关
,两路一位 LRU 位,四路两位 LRU 位,N 路 log(N) 位 LRU 位。命中时,所命中的行的计数器清零,比其低的计数器加 1,其余不变;
未命中且还有空闲行时,新装入的行的计数器置零,其余全部加 1;
未命中且无空闲行时,计数值为 Cache 行总数-1 的行的信息块被淘汰,新装行的块计数器置零,其余全部加 1。 使用 LRU 算法,有时可能出现一种叫做抖动的现象,具体就是集中访问的存储区超过 Cache 组的大小,命中率变得很低。
一段时间内访问次数最少
的存储行换出,同样的,每行设置一个计数器,新行
建立后从 0 开始计数
,每访问一次
被访问
的行计数器加 1
,需要替换
时,只需找到计数值最小
的行换出
。副本
,当对 Cache 中的内容进行更新
时,需要用写操作策略
来使 Cache 内容
和主存内容保持一致
,写策略针对命中和未命中两种情况分别提供了全写法、写回法和写分配法、非写分配法
。命中
,必须把数据同时
写入 Cache 和主存;当某一块需要替换时,不必把这一块写回主存,用新调入的块直接覆盖即可。写缓冲(Write Buffer)
,CPU 同时写数据到 Cache 和写缓冲中,写缓冲在控制将内容写入主存;写缓冲是一个FIFO 队列
,写缓冲解决速度匹配问题,但是若频繁写时,可能出现写缓冲饱和和溢出。 标志位(脏位)
,用于反映该块是否被修改过。转载地址:http://glqgn.baihongyu.com/