存储系统

存储系统层次结构

  • 速度越快,每位价格就越高
  • 容量越大,每位价格就越低
  • 容量越大,速度越慢

解决方案:采用多种存储器技术,构成多级存储层次结构

程序访问局部性原理

时间局部性:程序马上将要用到的信息很可能就是现在正在使用的信息

空间局部性:程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的

存储层次性能参数

存储容量S

命中率H:CPU访问存储系统时在一级存储中找到所需信息的概率

不命中率F:1-H

平均访问时间:TA=HT1+(1-H)(T1+TM)=T1+(1-H)TM

TM为不命中开销

三级存储系统

“cache—主存”和“主存—辅存”构成的系统

三级存储系统.png

存储层次四个问题

  • 映象规则:当把一个块调入高一层(靠近CPU)存储器时,可以放在哪些位置上
  • 查找算法:当所要访问的块在高一层存储器中时,如何找到该块
  • 替换算法:当发生不命中时,应替换哪一块
  • 写策略:当进行写访问时,应进行哪些操作

cache

cache按块管理,cache主存均被分割成大小相同的块,数据以块为单位调入cache。

基本工作原理图:

cache.png

映象规则

全相联映象

主存中任一块可以被放置到Cache中的任意一个位置

特点:空间利用率最高,冲突概率最低,实现最复杂

直接映象

主存中的每一块只能被放置到Cache中唯一的一个位置(循环分配)

例如对于主存的第i块,若cache共有M块,则映射到cache的第j块其中j=i mod(M)

特点:空间利用率最低,冲突概率最高,实现最简单

组相联映象

主存中的每一块可以被放置到cache中唯一的一个组中的任何一个位置

例如主存第i块映象到cache第k组,则k=i mod(G),G为cache的组数

特点:是直接映象和全相联的一种折衷

n路组相联:每组中有n个块(n=M/G),n称为相联度

n(路数) G(组数)
全相联 M 1
直接映象 1 M
组相联 1<n<M 1<G<M

绝大多数计算机的cache:n≤4

查找方法

查找目录表

目录表结构:标识-索引-块内位移,标识和索引构成块地址,索引指示了主存块在cache的位置

并行查找

相联存储器:目录由2g(G)个相联存储区构成,每个存储区大小为n×(h+log2n)),其中n为路数,h为标识位数

相联存储器.png

根据所查找到的组内块地址,从Cache存储体中读出的多个信息字中选一个,发送给CPU

单体多字存储器+比较器

以4路组相联为例

四路组相联.png

根据索引找对应的组,用标识与组内的四路标识比较从而判断是否命中

不必采用相联存储器,直接用按地址访问的存储器即可

替换算法

直接映象cache中的替换算法很容易,因为只有一个块,别无选择,在组相联和全相联中有多种选择

随机法

随机选取一个块替换,实现简单

先进先出法FIFO

最早进cache的被替换

最近最少使用法LRU

选择近期最少被访问的块作为被替换的块,命中率较高

模拟数据表明,对于容量很大的cache,LRU和随机法的命中率差别不大

LRU算法的硬件实现

  • 堆栈法

    • 一个堆栈,栈底为早被访问的块地址,栈顶是刚刚被访问的块地址。cache命中时,通过用块地址进行相联查找,在堆栈中找到相应的元素出栈并压入栈顶。cache不命中时把本次访问的块地址压栈,若栈满则把栈底弹出再把本次访问的块地址压栈
  • 比较对法

    • 让各块两两组合,构成比较对。每一个比较对用一个触发器的状态来表示它所相关的两个块最近一次被访问的远近次序,再经过门电路就可找到LRU块

      例:假设有A、B、C三个块,组成三对AB、AC、BC,TAB为1表示A比B更近被访问过,则当TAB=1且TBC=1时表示C是最久未被访问的块地址

      当组内块数较多时,可用多级状态位技术减少所需的硬件量。

      例:组内16块,可分为群、对、行3级,分为4群,每群两对,每对两行

      则选LRU群需要6(n×(n-1)/2)个触发器,每个群选LRU对需要 一个触发器,共需4个;每个对选LRU块需要一个触发器,一共8对需要8个,共需18个

写策略

“写”操作必须在确认是命中后才可进行,“写”有可能导致cache和主存内容的不一致

两种策略

  • 写直达法
    • 执行“写”操作时,不仅写入cache,而且也写入下一级存储器
  • 写回法
    • 执行“写”操作时,只写入cache。仅当cache中相应的块被替换时,才写回主存

比较

写回法速度快,使用的存储器带宽较低;写直达法易实现,一致性好

采用写直达法时,若在进行“写”操作的过程中CPU必须等待,直到“写”操作结束,则称CPU写停顿,可以采用写缓冲器来优化

“写”操作时的调块

  • 按写分配(写时取)(写回法采用)
    • 写不命中时,先把所写单元块调入cache再写入
  • 不按写分配(绕写法)(写直达法采用)
    • 写不命中时,直接写入下一级存储器而不调块

cache性能分析

  • 平均访存时间:

    • 平均访存时间 = 命中时间+不命中率 × 不命中开销

      不命中开销=不命中周期数(停顿)× 时钟周期时间

  • 程序执行时间:

    • CPU时间=(CPU执行周期数+存储器停顿周期数)× 时钟周期时间

      ​ =(CPU执行周期数+访存次数×不命中率×不命中开销)× 时钟周期时间

      ​ =IC ×(CPIexe+每条指令平均访存次数×不命中率×不命中开销)× 时钟周期时间

      CPIexe越低,固定周期数的cache不命中开销的相对影响就越大

改进cache性能

降低cache不命中率

三种类型不命中:

  • 强制性不命中:当第一次访问一个块时,该块不在cache中,需从下一级存储器中调入cache,这就是强制性不命中。(冷启动不命中,首次访问不命中)
  • 容量不命中:如果程序执行时所需的块不能全部调入Cache中,则发生容量缺失,随后再被调入。这种不命中称为容量不命中
  • 冲突不命中:在组相联或直接映象cache中,若太多的块映象到同一组(块)中,则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置),然后又被重新访问的情况。这就是发生了冲突不命中。(碰撞不命中,干扰不命中)

有以下结论:

  1. 相联度越高,冲突不命中就越少
  2. 强制性不命中和容量不命中不受相联度的影响
  3. 强制性不命中不受cache容量的影响,但容量不命中却随着容量的增加而减少

根据以上结论,减少三种不命中的方法:

  • 强制性不命中:增加块大小,预取(本身很少)
  • 容量不命中:增加容量(抖动现象:cache同一个组内块被反复地替换)
  • 冲突不命中:提高相联度(理想:全相联)

增加块大小

对于给定的Cache容量,当块大小增加时,不命中率开始是下降,后来反而上升了

由于增加块大小会减少cache中块的数目,所以有可能会增加冲突不命中。cache容量越大,使不命中率达到最低的块大小就越大。增加块大小也会增加不命中的开销

增加cache容量

缺点:增加成本,可能增加命中时间

提高相联度

采用相联度超过8的方案的实际意义不大,提高相联度是以增加命中时间为代价的

2:1 cache经验规则:容量为N的直接映象cache的不命中率和容量为N/2的两路组相联cache的不命中率差不多相同

伪相联cache(列相联cache)

既有直接映象的命中时间小优点,也有组相联的不命中率低的优点

基本思想:在逻辑上把直接映象cache的空间上下平分为两个区。对于任何一次访问,伪相联cache先按直接映象cache的方式去处理(快速命中)。若命中,则其访问过程与直接映象cache的情况一样。若不命中,则再到另一区相应的位置去查找。若找到,则发生了伪命中,否则就只好访问下一级存储器

伪相联.png

出现伪命中时把最近访问过的块放在第一位置

硬件预取

指令和数据都可以预取,可放入cache或外缓冲器,指令预取通常由cache之外的硬件完成。通过指令预取或数据预取或指令加数据预取可以捕获不命中。预取应利用存储器的空闲带宽,不能影响对正常不命中的处理,否则可能会降低性能

编译器控制的预取

在编译时加入预取指令,在数据被用到之前发出预取请求

按预取数据存放位置分

  • 寄存器预取:把数据取到寄存器
  • cache预取:只取数据到cache

按预取处理方式分

  • 故障性预取:在预取时,若出现虚地址故障或违反保护权限,就会发生异常
  • 非故障性预取(非绑定预取):在遇到这种情况时则不会发生异常,因为这时它会放弃预取,转变为空操作

预取数据时,处理器应能继续执行。编译器控制预取的目的是使执行指令和读取数据能重叠执行

循环是预取优化的主要对象

  • 不命中开销小时:循环体展开1~2次
  • 不命中开销大时:循环体展开许多次

注意每次预取需要花费一条指令的开销,要确保这种开销要小于带来的收益。编译器可以通过把重点放在那些可能会导致不命中的访问上,使程序避免不必要的预取,从而较大程度地减少平均访存时间

编译器优化

基本思想:通过对软件进行优化来降低不命中率

  • 程序代码和数据重组

    • 把一个程序中的过程重新排序,就可能会减少冲突不命中,从而降低指令不命中率
    • 如果编译器知道一个分支指令很可能会成功转移,则可以用以下两步来改善空间局部性
      • 将转移目标处的基本块和紧跟着该分支指令后的基本块进行对调
      • 把该分支指令换为操作语义相反的分支指令
  • 数组合并:将本来相互独立的多个数组合并成为一个复合数组,以提高访问它们的局部性

  • 内外循环交换:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //每次循环调入一个大块,可能发生容量不命中和冲突不命中
    for(j=0; j<100; j++){
    for(i=0; i<5000; i++){
    x[i][j] = 2*x[i][j];
    }
    }
    //修改后,可以访问同一块中的各个元素,再访问下一个块
    for(i=0; i<5000; i++){
    for(j=0; j<100; j++){
    x[i][j] = 2*x[i][j];
    }
    }
  • 循环融合:将若干个独立的循环融合为单个的循环。这些循环访问同样的数组,对相同的数据作不同的运算。这样能使得读入cache的数据在被替换出去之前,能得到反复的使用

  • 分块:把对数组的整行或整列访问改为按块进行。有助于寄存器分配,可以把load和store操作的次数变成最小。例如矩阵乘法,若行列较多,可以通过分块计算

“牺牲”cache

一种能减少冲突不命中次数而又不影响时钟频率的方法

基本思想:在cache和它从下一级存储器调数据的通路之间设置一个全相联的小cache,称为“牺牲”Cache(Victim Cache)。用于存放被替换出去的块(称为牺牲者),以备重用

作用:对于减小冲突不命中很有效,特别是对于小容量的直接映象数据Cache,作用尤其明显

减少cache不命中开销

采用两级cache

第一级cache小而快,第二级cache容量大

平均访存时间= 命中时间L1+不命中率L1×不命中开销L1

不命中开销L1= 命中时间L2+不命中率L2×不命中开销L2

  • 局部不命中率:该级Cache的不命中次数/到达该级cache的访问次数
  • 全局不命中率:该级Cache的不命中次数/CPU发出的访存的总次数

每条指令的平均访存停顿时间= 每条指令的平均不命中次数L1×命中时间L2+每条指令的平均不命中次数L2×不命中开销L2

对于第二级cache

  • 在第二级cache比第一级 cache大得多的情况下,两级cache的全局不命中率和容量与第二级cache相同的单级cache的不命中率非常接近
  • 局部不命中率不是衡量第二级cache的一个好指标,因此,在评价第二级cache时,应用全局不命中率这个指标

第二级cache参数

  • 容量:第二级Cache的容量一般比第一级的大许多,意味着第二级cache可能实际上没有容量不命中,只剩下一些强制性不命中和冲突不命中
  • 相联度:第二级Cache可采用较高的相联度或伪相联方法
  • 块大小:
    • 第二级cache可采用较大的块
    • 为减少平均访存时间,可以让容量较小的第一级cache采用较小的块,而让容量较大的第二级cache采用较大的块
    • 多级包容性:第一级cache中的数据是否总是同时存在于第二级cache中

让读不命中优先于写

cache中的写缓冲器导致对存储器访问的复杂化。在读不命中时,所读单元的最新值有可能还在写缓冲器中,尚未写入主存。

解决方法

  • 可推迟对读不命中的处理,直至写缓冲器清空。
  • 在读不命中时检查写缓冲器内容,若没有冲突而且地址可以访问,就可以处理读不命中(让读不命中优先于写)

写缓冲合并

  • 如果写缓冲器为空,就把数据和相应地址写入该缓冲器
  • 如果写缓冲器中已经有了待写入的数据,就要把这次的写入地址与写缓冲器中已有的所有地址进行比较,看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的,就把这次要写入的数据与该项合并。这就叫写缓冲合并
  • 如果写缓冲器满且又没有能进行写合并的项,就必须等待

写缓冲合并.png

待写入数据连续,可以合并

提高了写缓冲器的空间利用率,而且还能减少因写缓冲器满而要进行的等待时间

请求字处理技术

请求字:从下一级存储器调入cache的块中,只有一个字是立即需要的。这个字称为请求字

应尽早把请求字发送给CPU

  • 尽早重启动:调块时,从块的起始位置开始读起。一旦请求字到达,就立即发送给CPU,让CPU继续执行
  • 请求字优先:调块时,从请求字所在的位置读起。这样,第一个读出的字便是请求字。将之立即发送给CPU

cache块小或是下条指令正好访问同一cache块的另一部分情况下效果不大

非阻塞cache技术

非阻塞cache:cache不命中时仍允许CPU进行其它的命中访问。即允许“不命中下命中”

可以同时处理的不命中次数越多,所能带来的性能上的提高就越大,但并不是不命中次数越多越好

减少命中时间

容量小、结构简单的cache

  • 硬件越简单,速度就越快
  • 应使cache足够小,以便可以与CPU一起放在同一块芯片上

虚拟cache

  • 物理cache:使用物理地址进行访问的传统Cache。标识存储器中存放的是物理地址,进行地址检测也是用物理地址。地址转换和访问cache串行进行,访问速度很慢

  • 虚拟cache:可以直接用虚拟地址进行访问的cache。标识存储器中存放的是虚拟地址,进行地址检测用的也是虚拟地址。优点:在命中时不需要地址转换,省去了地址转换的时间。即使不命中,地址转换和访问cache也是并行进行的,其速度比物理cache快很多

  • 虚拟索引+物理标识
    • 虚地址的页内位移作为访问cache的索引(不作虚-实转换),标识是物理的地址

cache访问流水化

对第一级Cache的访问按流水方式组织,访问cache需要多个时钟周期才可以完成

踪迹cache

开发指令级并行性所遇到的一个挑战是当要每个时钟周期流出超过4条指令时,要提供足够多条彼此互不相关的指令是很困难的

一个解决办法:踪迹cache

  • 存放CPU所执行的动态指令序列。包含了由分支预测展开的指令,该分支预测是否正确需要在取到该指令时进行确认

并行主存系统

是在一个访存周期内能并行访问多个存储字的存储器,它能有效地提高存储器的带宽

单体多字存储器

单体多字.png

m=4,一次性读出4个字到寄存器

多体交叉存储器

多体交叉.png

m=4,4个存储体,一次性可以读出4个体同一个体内地址的内容

编址方法有高位交叉编址和低位交叉编址。高位交叉编址体号在高位,低位交叉编址体号在低位。

假设m个体,体内n个存储单元,给定一个地址A

  • 高位交叉编址:体号j=⌊A/n⌋,体内地址i=A mod n
  • 低位交叉编址:体号j=A mod m,体内地址i=⌊A/m⌋

避免存储器冲突

体冲突:是指两个访问请求要访问同一个存储体。在传统的多体交叉结构中,顺序访问被处理得很好,不会发生体冲突。地址相差奇数值的访存也是如此

而地址相差偶数值时,冲突频度增加了,解决问题的一种办法是用更多的体来减少体冲突的次数,但这种方法不会完全避免。

例如:假设有128个存储体,按字交叉方式工作,执行以下程序

1
2
3
4
int x[256][512];
for(j=0;j<512;j=j+1)
for(i=0;i<256;i=i+1)
x[i][j]=2*x[i][j]

512是128的整数倍,同一列内所有元素都在同一体内,会频繁产生cache不命中。可以让程序员或编译器来扩展数组大小使其不是2的幂从而强制使上述地址落在不同的体内

另一种硬件方法

(低位交叉)对于给定地址A,体数m,体内容量n,为了减少体冲突,令m为素数

顺序交叉:体号j=A mod m,体内地址i=⌊A/m⌋

取模交叉:体内地址i=A mod n,体号j=A mod m(用素数取模)

顺序交叉与取模交叉.png

虚拟存储器

基本概念

虚拟存储器分为两类:段式和页式

分页:页式虚拟存储器把空间划分为大小相同的块。页面是对空间的机械划分。信息的物理单位

分段:虚拟存储器则把空间划分为可变长的块。而段则往往是按程序的逻辑意义进行划分的。信息的逻辑单位

现代计算机大多段页式组合,每段被划分为若干个页,保存段作为逻辑单位的优点.又简化了替换的实现,而且段不必作为整体全部—次调入主存,可以以页面为单位部分调入

快速地址转换技术

由页表管理,页表一般很大,是存放在主存中的。—般采用TLB来解决这个问题

TLB(Translation Look-aside Buffer)地址变换高速缓存:

  • —个专用的高速缓冲器,用于存放近期经常使用的页表项(Page Table Entry,PTE页表条目)。根据程序的局部性原理,它所用的页表条目也是聚集的
  • 这样,大多数访存都可以通过TLB快速地完成虚—实地址转换,只有偶尔在ALU不命中时,才需要去访问主存中的页表

TLB中的项由两部分构成:标识和数据

  • 标识:存放的是虚地址的一部分
  • 数据:存放的则是物理页帧号:有效位、存储保护信息、使用位、修改位等

为了使TLB中的内容与页表保持一致,当修改页表的某—项时,操作系统必须保证TLB中没有该页表项的副本。这可以通过作废TLB中的页表项来实现

下图为AMD Opteron的数据TLB的组织结构

TLB.png

进行地址转换时,把虚拟地址送往各个标识,同时进行比较。若存在匹配的标识,则多路选择器把相应TLB项中的物理地址选出