[计算机]第七章_存储系统.ppt

第七章 存储体系,(2),7.3.3 替换策略及更新主存策略(1),Cache从主存读取数据块时有三种方式：需要时读取、预读取和选择读取。这三种方式各有优缺点，请注意比较。课本中提到“共享的数据放在主存中比放在Cache中合适，特别是在多处理机系统中“,因为共享的数据经常由别的处理过程改写，若放到cache中，则经常涉及到数据的一致性问题，因此放在主存中可保证其单一性，不致发生数据一致性错误的问题。 在层次式的存储体系中，访问某层存储器的内容时将从该层取数据块层层复制到上层存储器中，而上层的存储器容量总比下层的少，则在复制到上层时，就会发生替换掉原有数据块的问题。若被替换的块中有新写入的数据(如计算结果)则这些数据还得先写到下层存储器的相应块中，这就涉及更新策略。,7.3.3 替换策略及更新主存策略(2),在直接映象方式下，不存在块替换的算法，因为每一块的位置映象是固定的，需要哪一块数据就可直接确定地将该块数据调入上层确定位置。而其他两种映象就存在替换策略的问题，就是要选择替换到哪一个Cache块。即替换算法。,7.3.3 替换策略及更新主存策略(2),在直接映象方式下，不存在块替换的算法，因为每一块的位置映象是固定的，需要哪一块数据就可直接确定地将该块数据调入上层确定位置。而其他两种映象就存在替换策略的问题，就是要选择替换到哪一个Cache块。即替换算法。,FIFO替换方式的块分配操作示意图 一个容量为4个块的全相联Cache，假定访问的地址块号序列为：2，11，2，9，7，6，4，3，在先进先出替换方式下，队列中的变化情况如下：,访问顺序: 地址块号: 操作状态：,LRU替换方式的块分配操作 一个容量为4个块的全相联Cache，假定访问的地址块号序列为：2，11，2，9，7，6，4，3，在最久未使用替换方式下，队列中的变化情况如下：,访问顺序: 地址块号: 操作状态：,FIFO块替换中出现的颠簸现象 同样对于上述的4个块的全相联Cache，假定访问的地迁块号字列为：2，11，9，7，6，2，11，9，在先进先出替换方式下，队列中的变化情况如下：,访问顺序: 地址块号: 操作状态：,LUR算法的实现过程（1）,计数器法： 每个块一个计数器，定时时间间隔计数一次，块数据被访问时计数器清零。 计数值表示上一次访问后经过的时间，替换选择计数值最大的块替换出去。 由于计数器存在最大长度，计数满后溢出，造成时间最小。因此，改进方法就是采用相对计数值。 例如，当Cache命中时，其他非命中的块的计数值如果小于命中块的计数值就加1，计数值较大的不变。命中块的计数值清零。,LUR算法的实现过程（2）,寄存器栈法： 一套寄存器，存放每个块的记录。最近使用过的块始终保持在栈的顶部，最久未使用过的块放在栈的底部。 块访问时，从栈顶向栈底顺序查找该块的寄存器内的标识，如果找到，将该寄存器抽出来放在栈顶，如果没有找到，栈顶压入该标识的寄存器，栈底的标识出栈。,寄存器栈法示意图 11，6 访问时：,11,找到,6,没找到,Cache的更新策略,对Cache的写操作，情况比读操作要复杂一些。由于写入Cache时，并没有写入主存，因此就出现Cache和主存数据不一致的情况。 如何处理Cache和主存不一致的方法就称为更新策略。,一般的更新策略有两种：,7.3.3 替换策略及更新主存策略(3),另外，当写不命中时(也就是写Cache块时，这块早被人替换出去而在Cache中找不到时)是不是要把这块再取回Cache中，有两个解决方法： 不按写分配法，就是直接写到主存里，不再把该地址对应的块调回Cache中。 按写分配法，就是写到主存，而且把这一块从主存中调入到Cache。 一般写回法用按写分配法，全写法则采用不按写分配。,7.3.3 替换策略及更新主存策略(4),写回法中，处理器写操作的速度就是写Cache的速度，处理器多次写等于多次写Cache，只有发生块替换时才写主存，因此，总的写主存次数较少。 但Cache的操作变得复杂了，由于数据快替换发生在Cache操作失效时（不论读或写），因此，很多读操作也将引起数据块的写回操作。 简单回写法：块替换时不论是否更新过，都回写； 标志回写法：根据块更新标志决定是否回写。 写回法中可以设置写缓存，将暂时不会引起快失效，Cache可继续访问。块失效时，更新数据写入主存时，可以和处理器并行进行。但在处理器又要使用刚刚写入的数据时，就不能避免处理器的写停顿。,7.3.3 替换策略及更新主存策略(4),全写法中，读 Cache失效不涉及主存的写操作，实现比较容易，而且主存的数据和Cache数据保持一致。 如果写操作比较少，全写法对系统的性能影响就比较小。 据统计，访存操作中，534是写操作，平均概率是16%。 全写法的Cache可以采用写缓存，写操作先写入一个高速缓存，此时， Cache可以继续访问，然后在将缓存中数据写入Cache。这样可以提高系统性能，但增加复杂性。,Cache和主存数据不一致带来的问题,CPU和I/O部件共享主存： 访问主存的部件除了CPU，还有I/O控制器、I/O处理机等。如果CPU写入Cache的数据，而主存存的确是原来的数据，I/O部件读主存得到的数据就是错误的。 如果I/O部件写入主存的数据，而Cache 中存的确是原来的数据，CPU读Cache得到的数据就是错误的。,Cache和主存数据不一致带来的问题,多处理机系统共享主存： 每个处理机一个 Cache，处理机之间通过Cache共享主存，就会有Cache之间的数据一致性问题。 全写法并不能保证多个Cache之间的数据一致性。,其他应用Cache的场合,磁盘Cache： 就是磁盘和主存之间的Cache，可以放在磁盘上，也可以放在计算机系统内部。 磁盘Cache容量比较大，采用的技术类似，管理算法也用软件实现。数据传输单位一般是磁盘的存储单位，为一个扇区、或多个扇区。更新策略采用全写法以提高出错恢复能力。,7.3.4 数据Cache、指令Cache和一体化Cache(1),将Cache分别用来存放数据和指令，则可分成上面两种Cache，一体化Cache则既存放数据又存放指令。一般来说，分离后的Cache命中率有所提高。 对数据的访问和对程序指令的访问有不同的特征，区别这两种cache有助于根据其特征分别进行优化设计。对数据的访问有读操作和写操作，对程序指令的访问则仅仅是读操作。因此，数据Cache需要进行写操作，而指令Cache则不需要进行写操作，读入指令Cache的指令 在块替换出去时不需要将Cache中的指令写回主存。,指令Cache、数据Cache 和一体化Cache的不命中率比较,7.3.5 Cache的性能分析 (1),Cache的命中率对计算机速度的影响很大。实践证明，Cache的尺寸越小，地址映象方法和替换策略对命中率的影响越大。 在组的大小一定情况下，Cache的容量越大则命中率越高。 当Cache的大小确定时，组的大小或块的大小将影响不命中率，由于块的内部是全相联的，因此块越大则命中率越高。,LUR算法的实现过程（2）,寄存器栈法： 每个块一个计数器，定时时间间隔计数一次，块数据被访问时计数器清零。 计数值表示上一次访问后经过的时间，替换选择计数值最大的块替换出去。 由于计数器存在最大长度，计数满后溢出，造成时间最小。因此，改进方法就是采用相对计数值。 例如，当Cache命中时，其他非命中的块的计数值如果小于命中块的计数值就加1，计数值较大的不变。命中块的计数值清零。,7.3.5 Cache的性能分析 (2),我们知道，衡量存储系统的速度性能要以平均访存时间为指标，计算平均读访存时间的公式为： Ta=HcTc+(1-Hc)Tm 其中Hc是指命中率，Tc是命中时访问时间，Tm为访主存时间。若是多层Cache也可按此公式推出计算方法。即上层的存储器命中时间加上不命中时访问下层存储器的时间。,7.3.5 Cache的性能分析 (3),采用Cache后读访存速度的提高倍数为: =Tm/Ta=Tm/(HcTc+(1-Hc)Tm)=1(1-(1-Tc/Tm)Hc) 当HC=1时, =Tm/Ta 当Hc=0时, =1,max=tm/tc,Hc,的期望值,8 6 4 2,7.3.5 Cache的性能分析 (4),对于Cache的更新策略可作如下分析。设Tb是块写操作时数据块的传输时间，w是写操作的概率，在全写法按写分配（直达，不命中调入Cache）的情况下，平均访问时间为： Ta=Tc+(1-Hc)Ta+W(Tm-Tc) =(1-W)Tc+(1-Hc)Tb+WTm 式中(Tm-Tc)是主存储器写的附加时间，这里假定Cache写和主存写同时启动并且在主存写完成后才能进行下一次Cache的访问。,7.3.5 Cache的性能分析 (5),采用不按写分配的全写法(直达，不命中，不调入Cache)的Cache的平均访问时间为： Ta=Tc+(1-W)(1-Hc)Tb+W(Tm-Tc) =(1-W)(Tc+(1-Hc)Tb)+WTm 采用简单写回法的Cache，平均访问时间是Cache访问时间加上不命中时一次被替换的块写入主存的时间和新数据写入的时间为： Ta=Tc+(1-Hc)Tb+(1-Hc)Tb =Tc+2(1-Hc)Tb,7.3.5 Cache的性能分析 (6),采用标志位写回法，Cache的平均访问时间为： Ta=Tc+(1-Hc)Tb+Wb(1-Hc)Tb =Tc+(1-Hc)(1+Wb)Tb 其中，Wb是块更新的概率，这个概率最高可以达到写操作的概率W，但一般要小得多。它的命中率和简单写回法和全写法一样。它的平均访问时间比简单写回法下降了(1-Hc)(1-Wb)Tb，而增加的硬件并不多。,7.4 主存储器及带宽拓宽方法,实现主存储器的器件主要是动态存储器芯片，这种芯片的集成度较高，每位的价格约是静态存储器的十六分之一。而存取时间约为静态存储器芯片的8倍左右。 早期计算机的CPU速度都不高，动态存储器的速度基本上能满足要求。近年来，CPU的速度提高很快，而存储器芯片速度的提高则远远跟不上。采用Cache的方法可、缓窄一些速度上的不平衡，但它不能提高主存的带宽。而输入输出设备和Cache与主存的数据交换都要求主存有较大的带宽。因此，从结构上改进主存储器的设计，使其适合处理器的要求已显得越来越重要了。,7.4.1 提高主存性能方法 (1),如前所述，存储器的主要性能指标是容量、速度和价格。存储器的速度指标包括访问时间、访存周期时间和带宽。访问时间是指从地址到达至存储器数据输出所需的时间；周期时间是指两次访存的最小时间间隔；带宽为存储器在连续访问时的数据吞吐速率。 带宽的单位通常是每秒钟传送的位数或字节数，设计者很难提高存储器芯片的存取速度，但是可以从采用新的结构上提高主存的带宽。,7.4.2 多体交叉存储器,存储器的多体交叉是提高其数据带宽的有效方法。它采用模m交叉编址，多体并行进存取操作，每个体的宽度一般是一个字的宽度。,双向数据选择器,访问数据线,访问地址线,7.4.2.1 高位交叉存储器,如果主存的空间是N=2n字，那么该存储器的地址就由n位构成。高位交叉存储器使地址的高位段分别指向不同的存储体，低位地址用于选择一个存储体内的不同存储单元。如果M=2m个存储体，那么选择存储体的地址位段是高m位，体内地址是低n-m位。在高位交叉的存储器中，相邻地址的存储单元分布在相同的存储体中。当访问两个相邻或相近的存储单时，由于这两个存储单元在同一个体中，因此不能并行操作。这种现象称为存储器的分体冲突。 高位交叉存储器一般适合于共享存储器的多机系统。在这种系统中，各处理机通常访问所需的数据对象，当这些数据对象存放在不同的体中时，存取操作即可并行进行。 一个模m的多体交叉存储器在不发生分体冲突时的带宽是单体带宽的m倍。,7.4.2.2 低位交叉存储器,低位交叉存储器使地址的低位段分别指向不同的存储体，而高位地址用于选择一个存体内的不同存储单元。如果有M=2m个体，那么选择存储体的地址位段是低m位，体内地址是高n-m位。在低位交叉的存储器中，相邻地址的存储单元分布在不同的存储体中。在访问地址相邻的数据对象（如数值元素）时，低位交叉的存储器各体可并行进行存取操作。对于顺序访存的地址流，m个体的低位交叉存储器的带宽可以达到单体带宽的m倍，因此，低位交叉存储器比较适于单处理机内的高速数据存取以及带Cache的主存。,一维数组（向量）的无冲突访问存储器,在低位交叉访问的存储器中，影响其性能提高的因素有二点： 一是转移指令的出现； 二是数据访问时同体产生冲突。 两者比较起来，后者的影响更为严重。如何才能减少这种冲突呢？下面以一维数组和二维数组为例，说明解决冲突的方法。,一个一维数组的例子。如果采用低位交叉访问方式的并行存储器有4个存储体，交叉存放一维数组a0，a1，a2，如图所示。,一维数组（向量）的无冲突访问存储器,如果每次都按连续地址访问，就没有冲突问题。一个存储周期可以读出4个操作数，若一个存储周期需要读出更多的操作数，只要增加存储体的个数就可以了。 如果要求按位移量为2的变址方式访问并行存储器（读下标为奇数或偶数的操作数），则存储器的频带宽度就要降低一半，即可能有一半地址是冲突的。 在并行递归算法中，典型的访问模式是向量子集的各个元素逐次按2的整数幂相间访问。 例如，先按地址连续访问，然后按位移量为2的变址方式访问，再按位移量为4的变址方式访问等。对于这类算法，一般的低位交叉访问存储器就显得不能适应了。,一维数组（向量）的无冲突访问存储器,只要认真分析造成访问冲突的原因，不难发现传统的低位交叉访问存储器的存储体个数n为2的整数幂，因此变址位移量正好是n的约数。解决这一问题的方法很简单，只要把存储体的个数n选为质数，变址位移量就必然与n互质，一维数组的访问冲突自然也就不存在了。 许多以向量计算为主要任务的大型计算机系统，其主存储器的存储体个数一般都是质数。例如，美国Burroughs公司研制的巨型科学处理机BSP，它的存储体个数为17，我国研制的银河巨型计算机，存储体的个数为31。,多维数组（向量）的无冲突访问存储器,对于多维数组，需要考虑的问题就复杂得多，为简单起见，下面仅讨论二维数组。讨论过程中所得出得的结论也可以推广到多维数组中。 假设一个nn的二维数组存储在一个并行存储器中。现在要求对这个二维数组实现按行、按列、按对角线和按反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。,多维数组（向量）的无冲突访问存储器,下面以44的二维数组为例来讨论这个问题。如果按照地址顺序存储，一个44二维数组存储在4个并行存储体中的情况如图所示。显而易见，对于按行、按对角线访问能做到不发生冲突。但是，若按列访问，由于4个元素都放在同一个存储体内，只能分4个存储周期顺序读取它们。,多维数组（向量）的无冲突访问存储器,为了实现按行和按列都能无冲突访问，有一种存储方案是将数组的各个元素在4个并行存储体中错位存放，如图所示。但是，这种存储方案造成按对角线访问时又发生冲突了。,二维数组（向量）的无冲突访问存储器,参照一维数组的情况，不难证明，如果二维数组的各个元素采用按地址顺序存储的方案，当并行存储体的个数是偶数时，对于nn二维数组就不可能实现按行、按列、按对角线和反对角线的无冲突访问。当然，也可以针对不同的数组采取各种变通的措施，例如，采用不同的错位存储方案等。但是，这会给编译程序增加很大的麻烦，硬件实现的代价也很高。因此，希望寻找到一种对用户来说最为方便的均匀无冲突存储方案，能够实现二维数组的按行、按列、按对角线和反对角线的变址无冲突访问，而且，硬件实现比较简单，代价不要太高。,二维数组（向量）的无冲突访问存储器,对于nn的二维数组，PBudnik和DJKuck提出了一种能够实现上述要求的无冲突存储方案。这种方案要求并行存储体的个数mn，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。设同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元素在并行存储器中错开d2个存储体存放。 当 m=22p+1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是： d1=2p d2=1,二维数组（向量）的无冲突访问存储器,以44的二维数组为例，取大于4的最小质数m5作为并行存储体的个数，并把m代入关系式 ，解得到p1，从而计