第五章 并行存储器与存储系统的组织课件.ppt
《第五章 并行存储器与存储系统的组织课件.ppt》由会员分享,可在线阅读,更多相关《第五章 并行存储器与存储系统的组织课件.ppt(141页珍藏版)》请在三一办公上搜索。
1、第五章 并行存储器与存储系统的组织,存储器是现代计算机系统的核心。本章从计算机系统对存储器的要求出发,根据程序访问局部性的特点,分析具有层次结构的存储系统、并行存储器的概念及其组织实现,讨论高速缓冲存储器、虚拟存储器实现的映像管理规则、替换算法及其相关技术,介绍提高Cache存储系统和虚拟存储器性能的方法。第一节 并行存储器与相联存储器 第二节 存储系统的组织原理 第三节 Cache存储系统的组织基础 第四节 提高Cache存储系统性能的方法,一、什么是并行存储器 二、单体多字存储器 三、多体多字交叉编址存储器 四、多体多字存储器的无访问冲突 五、相联存储器,第一节 并行存储器与相联存储器,一
2、、什么是并行存储器 1. 存储器频带平衡及其实现的基本途径 现代计算机是以主存储器为中心工作的,主存储器要完成取指令、取操作数、写运算结果以及与外围设备进行数据交换等输入输出的操作。 衡量主存储器的速度的参数主要有延迟和带宽(或频带):延迟是指完成一次存储访问所需要的时间;带宽是指单位时间内可传输的二进制位数,主存储器是所有访问源的带宽之和。带宽又有最大带宽与实际带宽之分,最大频宽是指连续访问存储器时能提供的频宽,即指单位时间内可传输的最大二进制位数。由于存储器一般不可能满负荷工作,所以实际频宽要小于最大频宽。存储器频带平衡是指存储器的带宽应与计算机系统需求的带宽相适应。一般说来,对于主存储器
3、解决频带平衡问题有3条途径:(1)设置各种缓冲寄存器,如各种先行缓冲栈。(2)采用并行存储器,让多个存储器并行工作。(3)采用存储系统,特别是Cache存储系统,往往会采用多级Cache存储系统。,2. 并行存储器及其种类 并行存储器能够提高存储器的频宽,从而能够提高存储器的访问效率。所谓并行存储器是指通过设置多个存储器或存储体,使它们并行工作,在一个存储周期内可以访问到多个存储字。并行存储器有单体多字存储器、多体多字交叉编址存储器两种。,二、单体多字存储器 1. 单体多字存储器的结构模型 一般的单体单字存储器的一个存储单元存放一个存储字,每个存储周期只能访问到一个存储字的位,如图5-1(a)
4、所示,存储容量为m位(m为存储单元数)。其最大频宽为Bm=/TM。其中设存储字长与访问字长相同为位,TM为访问周期,在对存储器连续不间断的情况下,访问源(一般是CPU)的获得数据信息的速率也可达/TM。,1. 单体多字存储器的结构模型 要提高存储器的最大频宽,在相同的条件(存储器件相同,访问周期仍为TM;存储容量不变,仍为m位)下,只有提高存储器的字长。单体多字存储器是把存储器的存储字字长增加n倍为n位,存储单元数变为m/n。每个存储单元可存放n个指令字或数据字,从而在一个存储周期内能访问到n个指令字或数据字,相当于访问源获得数据信息的速率提高了n倍,即存储器最大频宽Bm=n/TM如图5-1(
5、b)所示。,1. 单体多字存储器的结构模型 要提高存储器的最大频宽,在相同的条件(存储器件相同,访问周期仍为TM;存储容量不变,仍为m位)下,只有提高存储器的字长。单体多字存储器是把存储器的存储字字长增加n倍为n位,存储单元数变为m/n。每个存储单元可存放n个指令字或数据字,从而在一个存储周期内能访问到n个指令字或数据字,相当于访问源获得数据信息的速率提高了n倍,即存储器最大频宽Bm=n/TM如图5-1(b)所示。,1. 单体多字存储器的结构模型 在保证存储容量m不变的情况下,可以把存储器的地址数相应减少n倍,则地址数为m/n个。这时可把地址信息分成两部分,其中高部分仍作为存储器的地址去访问存
6、储器(因为存储器的字数减少,访问存储器的地址码可以缩短),低部分则去控制一个多路选择器,从同时读出的n个数据中选择一个数输出。,2. 单体多字存储器的访问冲突 单体多字并行存储器的优点是实现简单,缺点是访问冲突概率大。访问冲突主要来自以下几个方面: (1)取指令冲突。 (2)读操作数冲突。 (3)写数据冲突。 (4)读写冲突。 前两种冲突容易解决,后两种冲突的解决比较困难。从存储器本身看,访问冲突产生的原因是地址寄存器和控制逻辑只有一套,如果在图5-1(b)中有n个独立的数据寄存器和n套读写控制逻辑,后两种冲突就自然解决了,前两种冲突也有所缓解。,三、多体多字交叉编址存储器 1. 多体多字交叉
7、编址存储器及其种类 一个存储器通常是由多个存储体(存储模块)组成,假设一个主存储器包含n=2a个存储模块,每个存储模块有m=2b个存储单元(字),则存储器的容量为nm=2a+b个字,存储单元字地址的二进制位数(地址码位数)为a+b。存储器对存储单元的编址是顺序的,当由多个存储体(存储模块)组成一个更大容量的主存储器时,对存储器中的多个存储体的存储单元采用交叉编址方式。根据用地址码的高位还是低位来选择存储模块,交叉编址方式可分为地址码高位交叉编址和地址码的低位交叉编址。地址码高位交叉编址目前使用很普遍,该编址方式能很方便地扩展常规主存储器的容量,例如用16MB8的存储模块可构成64MB8的存储器
8、。但只有低位交叉编址存储器才能有效地解决并行访问冲突问题,才能作为并存存储器的一种工作方式。,2. 高位交叉编址的存储器 高位交叉编址的存储器结构如图5-2所示,各个存储模块都有一套独立的地址寄存器和控制逻辑等。地址码的高a位用来区分存储体的存储模块地址,地址码的低b位是存储模块的体内地址。若高位交叉存储器由n个存储模块组成,每个存储模块的容量均m个字,则存储器的存储单元地址的高a=log2 n位称为存储模块的体号k=0,1,2,n-1,低b= log2 m位称为体内地址j=0,1,2,m-1。存储单元的地址A的计算公式为:A=mk+j。若已知地址A,可以计算出:对应的体号k =A/m,体内地
9、j = A mod m。,3. 低位交叉编址的存储器 低位交叉编址的存储器的结构如图5-3所示,各个存储模块都有一套独立的地址寄存器和控制逻辑等。地址码的低a位用来区分存储体的存储模块地址,地址码的高b位是存储模块的体内地址。若高位交叉存储器由n个存储模块组成,每个存储模块的容量均m个字,则存储器的存储单元地址的低a= n位称为存储模块的体号k=0,1,2,n-1,高b= m位称为体内地址j=0,1,2,m-1。存储单元的地址A的计算公式为: A=nj+k。若已知地址A,可计算出: 对应的体号k=A mod n, 体内地址 j=A/n。 当按地址A访问存储器时,用地址码的低 n位作为一个译码器
10、的输入,由译码器选中一个存储体,然后按地址码的高 m位给出的体内地址对选中的存储体内的一个存储单元进行读写操作。,4. 交叉编址存储器的带宽 为了提高主存储器的带宽,需要多个或所有的存储器能并行工作。由于程序执行过程中,CPU所访问的指令或数据的地址是按顺序连续的,所以在单处理机系统中,必须采用低位交叉编址存储器,并在一个存储周期内分时启动n个存储体,如图5-4所示(其中W表示存储字)。如果每个存储体的访问周期为TM,则各存储体的启动间隔t为:t=TM/n。 因此,采用交叉编址存储器提高带宽的工作方式实际是多个存储体流水线作业的并行存储器系统,,四、多体多字存储器的无访问冲突 在单处理机系统中
11、,一个由n个存储体组成的低位交叉存储器的带宽并不能提高n倍,其根本原因是存在访问存储的冲突。产生访问冲突的根源主要有两个,一是程序中的转移指令,二是数据被访问的随机性,后者的影响更为严重。以一维数组和二维数组为例,介绍一种多维数组的无冲突访问的交叉编址存储器。 1. 一维数组的无冲突访问,2. 二维数组的无冲突访问,(a)按列访问有冲突的存储方案 (b)按对角线访问有冲突的存储方案,P.Budnik和D.J.Kuch提出了一种能够对交叉编址存储器存放mm二维数组实现上述要求的无冲突存储方案。方案要求交叉编址存储体的个数nm,并且n取质数,同时还要在行、列方向上错开一定的距离存储数组元素。设同一
12、列相邻元素在交叉编址存储器中错开d1个存储体存放,同一行相邻元素在交叉编址存储器中错开d2个存储体存放。当n=22p+1(p为任意自然数)时,能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是:d1=2p,d2=1。,mm二维数组中的任意元素aij在无冲突交叉编址存储器中的体号和体内地址可以通过如下的一般公式来计算:体号=(2pi+j+k)mod n体内地址= i其中:0im-1,0jm-1,k是数组的第一个元素a00所在存储体的体号,一般取k=0;存储体的个数n是大于等于m的质数;p是满足n=22p+1的任意自然数。在这种错位存储方案中,有1/(m+1)的存储单元是空闲的,实
13、际上浪费了一个存储体的空间。如果不要求同一行中的数组元素按地址顺序存储,则mm的二维数组实际上只需要m个存储体就能实现按行、列、对角线和反对角线的无冲突访问。这时存储器的存储空间无浪费,利用率最高。,五、相联存储器 1. 相联存储器与相联处理机相联存储器是指可以按所给信息内容的部分或全部特征作为检索项(即关键字项)来检索存放在存储器中的数据信息,将与特征相符的所有存储单元一次性找出。简单来讲,所谓相联存储器是指按存储字的全部或部分内容寻址的存储器。而以相联存储器为核心,配上必要的中央处理部件、指令存储器、控制部件和I/O接口等,就构成一台以存储器并行操作为特征的相联处理机。相联处理机的中央处理
14、部件也应具有并行操作的能力,以便与相联存储器配合,因此相联处理机实质是单指令多数据流(SIMD)处理机。,2. 相联存储器的结构原理 相联存储器的结构模型如图5-10所示,该存储器有W个字,字长为m位,它主要包括存储体、运算操作器、控制电路和若干共用的数据寄存器等。,3. 相联检索的基本算法从相联存储器的结构可以看出,其实现的只是一种全等比较操作,实际上还可以有多种比较查找操作,基本的检索算法有以下几个:全等查找算法:所谓全等查找是指找出与CR未屏蔽的那部分内容完全相同的全部存储单元。最大值查找算法:所谓最大值查找是指要找出存储器中所存的最大数及存放此最大数的所有单元,相同的最大值可能有多个。
15、幅值比较查找算法:幅值比较查找是指在给定某比较数后,要分别找出存储器中内容大于、等于、小于该比较数的存储单元位置,也就是将存储器的存储单元按给定幅值进行比较,将其分成3类。其他算法,一、存储系统的基本概念 二、存储系统组织的基本思想 三、存储的基本层次和三级存储系统 四、三级存储系统的组织方式 五、存储系统的性能指标,第二节 存储系统的组织原理,一、存储系统的基本概念 1. 存储系统的提出 衡量一个存储器性能的基本指标通常有三个:速度、容量、价格。 存储器容量SM=WLn。其中W为存储模块的字长(位或字节),L为每个存储模块的字数,n为并行工作的存储模块数。存储器速度可用访问时间TA、存储周期
16、TM和频宽Bm等3个参数来描述。访问时间是指启动一次存储器操作(读或写)到完成该操作所需要的全部时间,存储周期是指存储进行连续两次独立的存储器操作(如连续两次读操作)所需的最小间隔时间,频宽是指单位时间内传输二进制位数。单体存储器最大频宽Bm=W/TM,n个存储体并行工作的最大频宽Bm=nW/TM。 存储器的价格包含存储体及其相应的外围电路,可用总价格C和每位价格c来表示,且有c=C/SM。,2. 什么是存储系统 两个或两个以上速度、容量和价格各不相同的存储器用硬件或软件或硬件与软件相结合的方法有机地连接起来的一个集合,其对应用程序员是一个透明的存储器,并具有速度高、容量大、价格低的特性,该存
17、储器集合就称为存储系统。,二、存储系统组织的基本思想 1. 存储访问的特点 程序对存储空间的访问具有所谓程序访问局部性的特点。程序访问局部性包括时间局部性和空间局部性两方面。一是时间局部性,它是指程序在最近的未来要用到的信息很可能是现在正在使用的信息,最典型的例子是循环程序要被多次重复地执行。二是空间局部性,它是指程序在最近的未来要用到的信息与现在正在使用的信息很可能在程序空间上是相邻或相近的,这主要是由于指令通常是顺序执行和数据不是随机分散地存储所致。数据一般是以向量、阵列、树形和表格等形式存放,其中每类数据都是簇聚地存储。因此,程序执行时访问存储器的地址的分布不会是随机的、均匀的,而是簇聚
18、成自然的块或页面。,2.存储系统的层次结构 根据程序访问局部性和存储器性能特点,可将存储系统的结构设计成由多级存储器组成的层次结构,而且在速度、容量和价格等性能指标方面的综合水平优于任何的单级存储器,以计算机系统实现对存储器的性能要求。程序访问局部性不仅使层次结构的存储系统在速度、容量和价格等性能指标方面的综合水平较高,而且可对存储空间采用分块或分页的管理方式来获得对Mi较高的命中率。,3.存储层次组织的基本操作 采用层次结构的方法将不同类型、性能各异的存储器组织在建立起来的存储系统,存储层次间有许多问题需要解决,这些问题应由存储系统的组织设计人员通过硬件或软件或硬件与软件相结合的方法来自动实
19、现,从而保证对程序员是透明的。综合起来主要有以下四个操作。(1)存储层次间的数据信息的交换。(2)存储层次间的地址变换。(3)存储空间的替换。(4)存储层次间的数据信息一致性的维护。,三、存储的基本层次和三级存储系统 1.存储的基本层次。,2. 三级存储系统 从存储基本层次的存储层次组织的基本操作来看,高速缓冲存储器以下各存储层次的基本操作是由CPU来自动实现,即由CPU的组织设计者完成;联机外部存储器与脱机外部存储器存储层次的基本操作是用户借助操作系统非自动实现;只有高速缓冲存储器(Cache)、主存储器和磁盘存储器(辅存)等三个存储层次的基本操作是由存储系统来自动实现,即由存储系统的组织设
20、计者完成。因此,由高速缓冲存储器(片外Cache)、主存储器和磁盘存储器(辅存)构成一个三级存储层次的存储系统,其结构模型如图5-14所示。,四、三级存储系统的组织方式 三级存储系统虽然包含了高速缓冲存储器、主存储器和磁盘存储器,但从程序员来看,不管存储系统的组织多么复杂,都只看到一个存储器。这个存储器采用与主存储器相同的按地址随机访问的方式工作,它的等效访问速度接近于Cache的访问速度,等效存储容量是虚拟地址空间的容量。Cache、主存储器、磁盘这三个物理存储器组成一个三级存储系统的组织方式有三种,一是将三级存储器建构成“Cache主存”和“主存磁盘”两个二级存储系统,二是将三级存储器建构
21、成“Cache主存磁盘”一个存储系统,三是将三级存储器建构成一个“Cache磁盘”存储系统,即所谓全Cache存储系统。其中两个存储系统使用最为普遍,全Cache存储系统的使用要求很高,一个存储系统的使用有限制条件。,1、两个存储系统的组织方式 两个存储系统的组织方式就是将Cache、主存、磁盘三级存储器组织成两个相对独立的两级存储层次的存储系统,一个是由Cache和主存组成的“Cache主存”存储系统,或称为Cache存储器(系统),另一个是由主存和磁盘存储器组成的“主存辅存”存储器(系统),因为采用虚拟存储技术,又称为虚拟存储器(系统)。两个存储系统的结构模型如图5-14所示,组织模型如图
22、5-15所示。,Cache存储系统与虚拟存储系统都是二级存储系统,在地址转换、替换算法和性能评价等方面有许多相似之处,但也有六个不同点:(1)一次性交换数据的数据量不同。(2)二级存储器之间的速度比不同。(3)访问不命中时CPU访问的通路不同。(4)设置的目标不同。(5)实现的方式不同。(6)透明性不同。,2、一个存储系统的组织方式 一个存储系统的组织方式就是把Cache、主存和磁盘3个存储器组织成一个“Cache主存磁盘”存储系统,一个存储系统的结构模型如图5-14所示,组织模型如图5-16所示。当CPU要访问存储器时,把虚拟地址直接送往存储管理部件MMU和Cache。Cache能够直接将虚
23、拟地址转换为Cache的物理地址,再访问Cache,找出CPU所需要的数据或指令。如果Cache发生块失效,则用经过MMU变换得到的主存物理地址访问主存,把读出的一块数据或指令装入到Cache中,同时也把CPU所需要的数据或指令送入CPU。,3、全Cache存储系统的组织方式 全Cache存储系统的组织方式,没有设置主存储器,只用Cache和磁盘两种存储器构成 “Cache磁盘”存储系统。全Cache存储系统的等效访问周期与Cache的访问周期很接近,等效存储容量就是虚拟地址空间的容量。在多处理机系统中,一种全Cache存储系统的结构模型如图5-17所示。,五、存储系统的性能指标存储系统的性能
24、指标一般包括的存储容量、单位容量的平均价格、命中率、访问周期和访问效率等五个。对于如图5-11所示的由M1、M2、Mnn个存储器组成的n级存储系统,假设各存储器的访问周期分别为T1、T2、Tn,容量分别为S1、S2、Sn,单位容量价格分别为C1、C2、Cn,T1T2 Tn,S1S2Sn,C1C2Cn,则存储系统的性能指标讨论如下。,1、存储容量 存储系统应对计算机的使用者提供尽可能大的地址空间,而且可对这个地址空间进行随机访问。根据存储系统的组织原理,最高层存储器Mn的存储容量Sn最大,则用户可使用Mn作为地址空间进行随机访问,存储系统的存储容量S就是高层存储器Mn的存储容量,即有:S = S
25、n,2、单位容量的平均价格 n级存储系统的单位容量平均价格C为:若希望存储系统的单位容量平均价格能接近于Cn,就应使S1S2Sn-1Sn。但如果S1、S2、Sn-1与Sn相差太大,则会使得CPU对M1、M2、Mn-1访问的命中率很低。同时,上式没有把由于采用存储系统所必须增加的辅助软硬件价格计算在内,所以要使C接近于Cn,还应使增加的辅助软硬件价格只占价格中很小的比例,否则存储系统的性能价格比将会显著降低。,3、命中率 命中率可简单地定义为由CPU产生的逻辑地址在存储器M1、M2、Mn-1中访问到指定信息的概率。命中率可用实验或模拟方法来获得,即执行或模拟一段有代表性的程序,若逻辑地址流指定的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五章 并行存储器与存储系统的组织课件 第五 并行 存储器 存储系统 组织 课件
链接地址:https://www.31ppt.com/p-1856768.html