[4] 并行存储器系统

1、北京科技大学计算机系李建江参考课件：清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授第四章 并行存储器系统4.1 存储器系统的层次结构4.2 包含性、一致性和局部性4.3 存储器容量的规划4.4 虚拟存储器技术4.5 交叉访问的存储器4.1 存储器系统的层次结构存储器系统的层次结构如下图所示：CPU内的寄存器高速缓存主存储器磁盘存储器磁带机层0：M0层1：M1层2：M2层3：M3层4：M4容量和存取时间增加每位成本增加五个参数：存取时间ti：从CPU到第i层存储器的往返时间存储器容量Si：第i层的字节的数量每字节成本Ci：第i层存储器的成本为CiSi传输带宽bi：相邻层之间传送信息的速

2、率传输单位Xi：i和i+1层之间数据传送的粒度 对存储器系统中各层次存储器的特性，某统计数据如下表：存储器层次特性第0层CPU寄存器第1层高速缓存第2层主存储器第3层磁盘存储器第4层磁带存储器设备工艺存取时间容量(字节)成本(美分/KB)带宽(MB/S)传送单位分配管理ECLSRAMDRAM磁盘机磁带机10ns25-40ns60-100ns10-20ms2-20min512B128KB512MB60-228GB512G-2TB18000725.60.230.01400-800250-40080-1333-50.18-0.23字:4-8B块:32B页:0.5-1KB文件:5-512KB后援存储器

3、编译器分配 硬件控制 操作系统操作系统/用户操作系统/用户第四章 并行存储器系统4.1 存储器系统的层次结构4.2 包含性、一致性和局部性4.2.1 包含性4.2.2 一致性4.2.3 局部性4.3 存储器容量的规划4.4 虚拟存储器技术4.5 交叉访问的存储器4.2 包含性、一致性和局部性4.2.1 包含性（inclusion）1. 包含性的定义M0 M1 M2 Mn 所有信息项最初存放在最外层Mn，在处理过程中，它的子集复制到Mn-1，同样， Mn-1的子集复制到Mn-2， 如果在Mi中找到一个信息字，那么同一个字的复制品在所有的高层Mi+1，Mi+2，Mn中都一定可以找到。2. 相邻层之

4、间的数据传送单位CPU高速缓存：字字高速缓存主存储器：块块（每块32个字节（8个字）主存磁盘：页面页面（比如每页4K字节，包含128块）磁盘磁带：段段包含性可以用下面的图来说明：CPU寄存器baM1:高速缓存a,b为高速缓存块，32个字节页面AaM2:主存储器页面Bb页面AaM3:磁盘存储器页面Bb段F段G页面AaM4:磁带机后援存储器页面Bb段F段G字单位块单位页单位段单位4.2.2 一致性（coherence）1.一致性定义同一个信息项与后继存储器层次的副本是一致的。如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改 。2.维护一致性的两种策略（1）写直

5、达（write-through,WT），即如果在Mi（i=1，2，n-1）中修改了一个字，则在Mi+1中需要立即修改。 （2）写回（write-back,WB），即如果在Mi+1 中的修改延迟到Mi中正在修改的字被替换时才进行。4.2.3 局部性（locality）Hennessy和Patterson（1990年）提出了一条90-10规则：典型程序在10%的代码上可能要耗费其执行时间的90%（例如嵌套循环操作的最内层循环）。时间局部性（temporal locality）：最近的访问项（指令或数据）很可能在不久的将来再次被访问。即对最近使用区域的集中访问。空间局部性（spatial local

6、ity）：一个进程访问的各项的地址彼此很近，例如，表操作或数组操作含对地址空间中某一区域的集中访问。顺序局部性（sequential locality）：在典型程序中，除非转移指令产生不按次序的转移外，指令都是顺序执行的。局部性原理指导我们去设计高速缓存、主存储器以及虚拟存储器组织。第四章 并行存储器系统4.1 存储器系统的层次结构4.2 包含性、一致性和局部性4.3 存储器容量的规划5.3.1 命中率5.3.2 有效存取时间4.4 虚拟存储器技术4.5 交叉访问的存储器4.3 存储器容量的规划存储器层次结构的性能是由层次结构的有效存取时间Teff决定的，它依赖于相继层次的命中率和访问频率。4

7、.3.1 命中率在Mi中找到一个信息项时，称之为命中，反之称为缺失。假定在层次结构中的存储器层次为Mi和Mi-1，其中i=1，2，n。 在Mi层的命中率hi则是信息项可在Mi中找到的概率。它是表示两个相邻层Mi-1和Mi特性的函数。 在Mi中的缺失率定义为1-hi。相继层的命中率是存储器容量、管理策略和程序行为的函数，它是独立的随机变量，其值在0到1之间。我们，这意味着CPU总是先访问M1，并且访问到最外层Mn时总是命中的。对Mi的访问频率为：iiihhhhf)1()1)(1(121是指在较低层次有i-1次缺失而在Mi有一次命中时访问Mi成功的概率。111,1hffniiiiihhhhf)1(

8、)1)(1(121niif11111111)1()1(njjnijijihfhhfhfCPU总是先访问M1访问到最外层Mn时总是命中的nfff21通常情况下，有：这说明，访问内存比访问外存要多。4.3.2 有效存取时间每当发生缺失时，就要付出代价付出代价去访问较高层次的存储器。这种缺失在Cache中称为块缺失。在主存储器中称为缺页错（page fault），因为块和页面是这些层次之间传送信息的单位。nnnniiieffthhhhthhthtfT)1()1)(1()1(121122111访问到最外层Mn时总是命中的4.3.3 层次结构的优化目标： 使Teff接近于M1的t1， 总成本接近于Mn的

9、CnSn 。优化过程可以表达为：对一个线性规划求最小值问题:减到最小值。要将有效存取时间总价格的上限）时，对于niiieffniiitotaliitfTCSCCSnitS101(,2, 1,0,0例子：存储器层次结构设计存储器层次存取时间容量价格/K字节高速缓存主存储器磁盘阵列t1 = 25nst2 = 未知t3 = 4mss1=512K字节s2=32M字节s3 = 未知c1=1.25美元c2=0.2美元c3=0.0002美元要达到有效存取时间Teff=10.04s,高速缓存命中率为h1=0.98，主存储器命中率h2=0.9，总成本上限为15000美元。解：ustthhhthhthTGByte

10、SSCSCSCCSeff972.11104.10)1)(1()1(8.391500023321221113332211代入可得代入有：如果在同样的预算限制条件下，要把主存储器容量提高64M字节，那么只好以减少磁盘容量为代价，但是这一变化并不影响高速缓存的命中率。如果使用合适的页面替换算法(主存与磁盘)，可能会增加主存储器的命中率，Teff有所降低。层次化存储器系统必须解决的问题：（1）数据块在较高层存储器中存放在哪个位置？即块和页的。如果一个块存放在某一上层存储器中，怎样确定并找到该块，即块的。（2）不命中的将从下层存储器中访问，并将该块调入上层存储器中，但是如果上层存储器中已无空闲空间，则势

11、必将上层存储器中的某一块调出，但应调出那一块，即。（3）在写访问时，写入上层存储器中的数据必须在适当的时候写入下层存储器，何时写？即第四章 并行存储器系统4.1 存储器系统的层次结构4.2 包含性、一致性和局部性4.3 存储器容量的规划4.4 虚拟存储器技术4.3.1 共享存储和分布存储4.3.2 DSM与SVM4.3.3 虚拟存储器的主要技术4.5 交叉访问的存储器4.4 虚拟存储器技术提要：虚拟存储器提供了的存储器工作空间。虚拟地址在编译时产生。虚拟地址到物理地址的转换在运行时进行，需要使用转换表和映象系统。4.4.1 共享存储和分布存储MIMD系统可以分为两种：(1)tightly co

12、upled shared-Memory multiprocessors(2)loosely coupled distributed-Memory multiprocessors它们可以用图表示如下：P1P2PnICN (Interconnection Network)SM1SMmshare-MemorymultiprocessorsPICNdistribued-MemorymultiprocessorsLMPLMPLM共享存储和分布存储的优缺点：共享存储器：易于编程，是单机的自然延伸；程序员没有数据划分的负担；多进程并发的开销小，效率高，易于进程迁移，任务动态分配简单；由于每个处理器都通过总线

13、通过总线访问存储器，因而限制了处理器的个数，可扩展性差。分布存储器：系统结构灵活，可扩展性好；处理机数目可达成百上千，处理速度有巨大的发展潜力；算法设计、编程以及任务动态分配比较困难；很难在处理机之间传递复杂的数据结构，难于进程迁移；不能支持需要存储空间的大规模数据处理要求。分布存储的两种编程方法：（1）message-passing，用send，receive原语实现通信，要求程序员在进程的整个运行期间对数据的移动都很清楚；（2）romote procedure call，语言一级传送控制与数据，可以看作是本地调用，但透明度有限。缺点：这两种方法都是用来解决不同地址空间的问题，在结点间传递复

14、杂数据结构时都比较困难，需要打包。由于每个处理机拥有不同的地址空间，使得进程迁移时，该进程所分配到的操作系统资源也得一起移动（打开的文件、文件存取控制块等），这很费时。4.4.2 DSM与SVM1.DSM和SVM的提出 如何把共享和分布的优点结合起来，取长补短？共享分布存储器（Distributed shared Memory，DSM）虚拟共享存储器（Shared Virtual Memory，SVM）基于分布存储器的多处理机上，实现物理上分布但逻辑上共享的存储器系统。虚拟共享存储器的逻辑结构：CPU1虚拟共享存储器LM1CPU2LM2CPUnLMn地址映射部件地址映射部件地址映射部件MIMD

15、机器存储系统的发展方向：共享存储器分布存储器共享分布存储器2.DSM系统的特点 在DSM系统中，每一台处理机都可以访问全局存储器的任一位置，用户可以把它当成全局共享存储器系统。 优点：编程容易系统结构灵活可扩展性好系统价格低有较好的软件移植性 DSM系统编制的程序比用消息传递方式编制的程序效率高：（1）在DSM系统中，数据都是以块的方式进行传送，如果一个程序具有较高的，则当把一个数据块传送到一个结点后，该结点对它的访问就成为本地访问，而消息传递方式的每次访问都需要。（2）许多并行应用程序都是分阶段执行的，每次执行前，都有一个数据交换阶段，其时间受通信限制。在DSM系统中，数据只有用到的时候才传

16、送，取消了数据交换阶段，把通信时间加以分散，提高了并行性。（3）DSM提供的虚存空间比单个结点的存储空间大得多，减少了换页操作。3.实现DSM的途径 主要有三种：（1）硬件实现：将传统的cache技术扩展应用到松耦合分布式存储多处理机。要增加专用部件以取得高效的实现。（2）操作系统和库实现：利用虚拟存储管理机制取得共享（sharing）和一致（coherence）。（3）编译实现：自动将共享访问转换成同步和一致原语。用户需要显式控制全局数据，当传递大量数据时或试图进行进程迁移时极其复杂。4.主要技术结构（structure）粒度（granularity）数据访问与一致性（access and

17、cosistency）一致性语义（coherence semantics）可扩展性（scalability）异构性（heterogeneity）结构指共享数据在存储器中的框架（如对象和语言的类型）；粒度指基本共享单位长度（如字节、字、页或复杂数据结构）。第四章 并行存储器系统4.1 存储器系统的层次结构4.2 包含性、一致性和局部性4.3 存储器容量的规划4.4 虚拟存储器技术4.5 交叉访问的存储器4.5.1 两种组织方式4.5.2 两种方式的比较4.3.3 容错4.5 交叉访问的存储器主存储器。假设主存储器包含m=2a个存储器模块，每个模块包含w=2b个存储单元（字），则总存储容量为个字b

18、awm24.5.1 两种组织方式交叉访问的存储器可以分为两种：(1)低位交叉方式(2)高位交叉方式1.低位交叉方式存储器地址的低a位用来指明存储器模块，高b位是每个模块内的字地址。低位m路交叉存取如下图：地址译码器MAB0mm(w-1)MDBM0MAB1m+1mw-m+1MDBM1MABm-12m-1mw-1MDBMm-1MDB字模块地址ab数据总线存储器数据缓冲器模块地址缓冲器字地址缓冲器每个模块每个模块包含包含w=2w=2b b个存储单个存储单元（字）元（字）包含包含m=2m=2a a个个存储器模块存储器模块行优先！行优先！2.高位交叉方式存储器地址的高a位作为存储器模块地址，邻接的存储器单元被分配在同一个存储器模块中，在每个存储器周期内，只能对各模块存取一个字。所以不支持邻接单元的成块存取。高位m路交叉存取如下图：地址译码器MAB01w-1MDBM0MABww+12w-1MDBM1MAB(m-1)wmw-w-1mw-1MDBMm-1MDB字模块地址ab数据总线存储器数据缓冲器模块地址缓冲器字地址缓冲器列优先！列优先！4.5.2 两种方式的比较 （1）低位交叉以流水线方式支持成块存取行优先！行优先！0856存储器地址寄存器(6位)M01957M121058M231159M341