《第五章 并行存储器与存储系统的组织》由会员分享，可在线阅读，更多相关《第五章 并行存储器与存储系统的组织（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（b）
5、所示。,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，体内地j = A m
9、od 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。因此，采用交叉编址存储器提高带宽的工作方式实际是多个存储体流水线作业的并行存储器系统，,四、多体多字存储器的无访问冲突 在单处理机系统中，一个由n个存储体组成的低位
11、交叉存储器的带宽并不能提高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、存储周期TM和频宽Bm等
16、3个参数来描述。访问时间是指启动一次存储器操作（读或写）到完成该操作所需要的全部时间，存储周期是指存储进行连续两次独立的存储器操作（如连续两次读操作）所需的最小间隔时间，频宽是指单位时间内传输二进制位数。单体存储器最大频宽Bm=W/TM，n个存储体并行工作的最大频宽Bm=nW/TM。存储器的价格包含存储体及其相应的外围电路，可用总价格C和每位价格c来表示，且有c=C/SM。,2. 什么是存储系统 两个或两个以上速度、容量和价格各不相同的存储器用硬件或软件或硬件与软件相结合的方法有机地连接起来的一个集合，其对应用程序员是一个透明的存储器，并具有速度高、容量大、价格低的特性，该存储器集合就称为存储
17、系统。,二、存储系统组织的基本思想 1. 存储访问的特点 程序对存储空间的访问具有所谓程序访问局部性的特点。程序访问局部性包括时间局部性和空间局部性两方面。 一是时间局部性，它是指程序在最近的未来要用到的信息很可能是现在正在使用的信息，最典型的例子是循环程序要被多次重复地执行。 二是空间局部性，它是指程序在最近的未来要用到的信息与现在正在使用的信息很可能在程序空间上是相邻或相近的，这主要是由于指令通常是顺序执行和数据不是随机分散地存储所致。数据一般是以向量、阵列、树形和表格等形式存放，其中每类数据都是簇聚地存储。因此，程序执行时访问存储器的地址的分布不会是随机的、均匀的，而是簇聚成自然的块或页面。,
