本文主要是介绍二 cahce 一致性-替换算法-多级cahce-并行主存系统,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一.cache的一致性问题:
1.cache的一致性问题指的是什么?
cache中的内容是主存的副本。
情况1:cache中的内容进行更新时,而没有改变主存中的相应内容时,cache和主存之间产生了不一致性。
情况2:当多个设备都允许访问主存时
例:I/O设备可通过DMA 方式直接读写主存时,如果Cache中的内容被修改,则I/O设备读出的对应主存单元的内容无效;若I/O设备修改了主存单元的内容,则对应Cache行中的内容无效。
情况3:当多个CPU都有各自私有的Cache并且共享主存时
例:某个CPU修改了自身Cache中的内容,则对应的主存单元和其他CPU中对应的Cache行的内容都要变为无效。
私有Cache中的变量u被更新后,各处理器读到的是不同的u值.
处理器私有Cache引入的问题
• 同一变量拷贝可能出现在多个处理器私有Cache中
•某处理器写操作可能对其它处理器是不可见的
2.如何保持Cache一致性呢?只有写操作能修改cache和主存ddr中的内容
当CPU写存储地址命中Cache时:
Write Through (写直达、写通过、直写)
Write Back (写回、一次性写、回写 )
Cache的写机制:Write Through (写直达、写通过、直写)
当一个写操作产生时,新值同时写到Cache和主存的块中
写直达会带来什么影响?
Memory is too slow(>100Cycles)
10%的存数指令会使CPI增加到:1.0+100×10%=11
在Cache和主存之间使用写缓冲(Write Buffer)
• 当一个数据等待被写入主存时,先将其存入写缓冲;
• 在把数据写入Cache和写缓冲后,处理器继续执行命令;
• 当写主存操作结束后,写缓冲里的数据释放
Cache的写机制:Write Back (写回、一次性写、回写)
当一个写操作产生时,新值仅被写到Cache中,而不被写入主存
写回方式会带来什么影响?
• 大大降低主存带宽需求,提高系统性能,控制可能很复杂
• 每个Cache行都设置一个修改位 (“ dirty bit-脏位”) ,如果对应Cache行中的主存块被修改,就同时置修改位为“1“ ,如果修改位为“0“ ,则说明对应主存块没有被修改过
• 只有当修改位为“1“的块从cache中替换出去时,才把它写回主存
写命中(Write Hit)要写的单元已经在Cache中
Write Through(写通过、写直达、直写)
Write Back(一次性写、写回、回写)
写不命中(Write Miss)要写的单元不在Cache中
Allocate-on-miss (写分配)
No-allocate-on-write (写不分配)
写不命中时如何处理?
Allocate-on-miss (写分配)
将该主存块装入Cache,然后更新Cache行中的相应单元;试图利用空间局部性,但增加了从主存读入一个块的开销
No-allocate-on-write (写不分配)
直接写主存,不把被写数据放入Cache;减少了从主存读一个块的开销,但没有利用空间局部性
2.cache的替换算法:
1.什么时候需要进行Cache替换?
Cache行数<<主存块数;
• 主存块和Cache行:多对1;
• 当一个新的主存块需要复制到Cache中时,如果Cache中的对应行已经全部被占满,怎么办?选择淘汰掉一个Cache行中的块
直接映射(Direct Mapped)Cache
• 映射唯一,无条件用新信息替换老信息
N路组相联(N-way Set Associative)Cache
• 每个主存数据有N个Cache行可选择,需考虑替换哪一行
全相联(Fully Associative)Cache
• 每个主存数据可存放到Cache任意行中,需考虑替换哪一行
2.常用替换算法:
先进先出FIFO、最近最少用LRU、最不经常使用LFU、随机替换
先进先出(First In First Out,FIFO)算法
基本思想:总是把最先进入的那一块替换掉
最近最少使用(Least Recently Used,LRU)算法
基本思想:总是把最近最少用的那一块淘汰掉,利用时间局部性
LRU算法的命中率随组中行数的增大而提高
LRU算法具体实现:通过给每个Cache行设定一个计数器,根据计数值来记录这些主存块的使用情况。这个计数值称为LRU位
计数器变化规则
•每组4行时,计数器设2位。计数值越小,则说明越被常用
•命中时,被访问行的计数器置0,其他行计数器加1,其余不变
•未命中且该组未满时,新行计数器置为0,其余全加1
•未命中且该组已满时,计数值最大的那一行中的主存块被淘汰,新行计数器置为0,其余加1
随机(Random)替换算法
基本思想:随机地从候选的槽中选取一个淘汰,与使用情况无关
模拟试验表明,随机替换算法在性能上只稍逊于LRU算法,而且代价低!
3.多级cache
多级Cache系统成为主流:在Cache-Memory系统中使用更多的层次结构,以掩盖CPU访存延迟,提高处理器的执行效率.
多Cache系统设计的主要考虑因素:
(1) 单级/多级
• 片内(On-chip)Cache:将Cache和CPU作在一个芯片上
• 外部(Off-chip)Cache:不做在CPU内而是独立设置一个Cache
• 单级Cache:只用一个片内Cache
• 多级Cache:同时使用L1 、L2 Cache,有些系统还有L3 Cache
L1 Cache更靠近CPU,其速度比L2快,其容量比L2小
(2) 联合/分立
分立:数据和指令分开存放在各自的数据和指令Cache中
联合:数据和指令都放在一个Cache中
一般L1 Cache都是分立Cache,为什么?
L1 Cache的命中时间比命中率更重要!减少命中时间以获得较短的时钟周期
一般L2 Cache都是联合Cache,为什么?
L2 Cache的命中率比命中时间更重要!降低缺失率以减少访问主存缺失损失
两级Cache 系统的缺失损失(Miss Penalty)分析:
(1) 单级/多级
• 若L2 Cache包含所请求信息,则缺失损失为L2 Cache的访问时间
• 否则要访问主存,并同时取到L1 Cache和L2 Cache(缺失损失更大)
4.并行主存系统
解决内存访问速度慢的措施:
•提高主存芯片本身的速度
•在主存和CPU之间加入Cache
•采用并行结构技术
主存性能一直是计算机的重要性能指标之一,决定着计算机系统的整体性能
计算机系统期望主存:速度快、容量大、可靠性高、成本低
但从计算机实现技术来看,存在两个现实:
• 主存速度的提高总是远远落后于CPU速度的增长
• 主存容量的扩大总是远远满足不了软件的日益膨胀
结论:单从存储技术本身提高主存速度和容量,已经很难满足计算机系统的实际需求
从存储系统结构上想办法?
1、层次式存储系统
Cache —— 主存层次
主存 —— 辅存层次(虚拟存储技术,扩大用户编程的逻辑空间)
2、多体(多模块)并行交叉编址的主存储器
多体存储器
由若干个小存储体组成,共用MAR和MDR,同一套读/写控制电路、地址缓存、地址译码,不能提高数据访问速度
多体存储器
一个存储器中提供两套独立工作的读/写控制 电路 地址缓存 地址译 码 两个读写端口
根据地址线和数据线能同时进行两个数据的读/写.
通常作为双口RAM或指令预取部件
多模块存储器(多体交叉)
包含多个小存储体/模块,每个体有自己的MAR、MDR和读写电路
多个存储模块可独立并行工作
能够提高数据访问速度
编址方式
连续编址(高位交叉访问)
交叉编址(低位交叉访问)
连续编址方式 —— 高位交叉访问存储器
实现方法:用主存地址码的高位区分存储体号,低位表示模块内的地址
扩大了存储器容量连续字在一个模块中;各个体并行工作
存储地址连续的数据落在同一存储体内,容易发生访存冲突,并行存取的可能性很小
访存冲突,就是同时有两个或两个以上访存地址指向同一存储体,不能同时进行访存
用于非共享主存(即每个处理机仅享用统一编址主存的部分连续地址空间)和专用Cache的多处理机系统中
交叉编址方式 —— 低位交叉访问存储器
实现方法:用主存地址码的低位区分存储体号,高位表示模块内的地址
连续字分布在多个体中;各个体轮流编址、并行工作提高存储器访问速度
存储地址在同一存储体中不连续,以存储体个数(如:m)为模交叉编址
连续的程序或数据将交叉存放在m个存储体中,可实现以m为模的交叉并行存取,访存冲突的概率很小,为充分发挥并行性,多数计算机都采用低位交叉编址方式
什么条件下,多体低位交叉编址可增加存储带宽?
CPU访问主存的存储单元地址分布在不同存储体内
避免存储体访问冲突
软件通过编译程序做循环变换,可避免访问相同的存储体
硬件采用质数个存储体的低位交叉并行主存系统:一种无访问冲突的并行主存结构(实际带宽接近于最大带宽)
• 余数定律证明
• YH-1巨型机采用的是31个存储体构成的无冲突并行主存结构
指令执行时发生Cache失效/缺失/失靶,需到主存取数据或指令在主存和Cache之间传输的单位是块(Block)
问题:何种存储器使Block传输最快(miss penalty最小)?
存储器访问过程:
•发送地址到主存储器:1个总线时钟
•访问主存的时间:15个总线时钟
•从总线上传送一个字:1个总线时钟
并行计算机的访存模型
1、UMA模型(Uniform Memory Access):均匀存储访问模型
特点
• 物理存储器被所有处理器均匀共享(SM:Shared Memory)
• 访问任何存储字的时间相同
• 每台处理器可带私有高速缓冲
• 外围设备可以某种形式共享
2、NUMA模型(Non-Uniform Memory Access):非均匀存储访
特点
• 被共享的存储器在物理上分布于各个处理器
• 处理器访问不同存储器的时间不一样
• 每台处理器带私有高速缓冲
• 外围设备可以某种形式共享
多处理机的Cache一致性
多核处理器:在单芯片上的多个处理器,可能会共享主存中的一个公共的物理地址空间
Cache提供共享数据的迁移(migration)和复制(replication)
• 迁移:数据项可以移入本地cache并以透明的方式使用。迁移减少访问
远程共享数据项的延迟和对共享存储器带宽的需求
• 复制:当共享数据被同时读取时,Cache在本地对数据项做了备份。
复制减少了访问延迟和读取共享数据时的竞争现象
Cache共享数据带来新的问题 —— Cache一致性问题
• 两个不同处理器所保存的存储器视图是通过各自的cache得到(采用写直达cache)
• 两个处理器可能分别得到两个不同的值
软件方法:借助编译程序进行分析,使共享数据只存放在主存中,不允许放入高速缓存中
硬件方法:硬件协议维护,关键在于跟踪所有共享数据块的状态
• 侦听协议(snooping)
• 目录协议
侦听协议
基于总线连接的多处理机系统中,每个处理器的高速缓存设置1个侦听部件,侦听总线上的事务活动
若侦听到主存中有1个单元被其它处理器修改,而在自己Cache中有该单元的副本时,则将自己Cache中的副本置为无效,或把该副本更新,保持与主存中相应单元的内容一致
目录协议(Directory Protocol)
在主存中设置一个目录表,表中每一项记录共享数据的所有高速缓存行(数据块)的位置和状态,包括几个指示器(指示数据块的副本放在哪些处理器的高速缓存中)和指示位(指示是否已有高速缓存更新过此数据块的内容)
当一个处理器写入自己的高速缓存时,基于目录表,只需有选择地通知存有该数据块的处理器中的高速缓存,使相应副本被废弃或被更新
这篇关于二 cahce 一致性-替换算法-多级cahce-并行主存系统的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!