ch5-第五章并行存储器系统

《ch5-第五章并行存储器系统》由会员分享，可在线阅读，更多相关《ch5-第五章并行存储器系统（57页珍藏版）》请在金锄头文库上搜索。

1、第五章 并行存储器系统,5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.5 交叉访问的存储器,5.1 存储器系统的层次结构,存储器系统的层次结构如下图所示：,CPU内的寄存器,高速缓存,主存储器,磁盘存储器,磁带机,层0：M0,层1：M1,层2：M2,层3：M3,层4：M4,容量和存取时间增加,每位成本增加,五个参数： 存取时间ti：从CPU到第i层存储器的往返时间 存储器容量Si：第i层的字节或字的数量 每字节成本Ci：第i层存储器的成本为CiSi 传输带宽bi：相邻层之间传送信息的速率 传输单位Xi：i和i+1层之间数据传

2、送的粒度 对存储器系统中各层次存储器的特性，1993年的统计数据如下表：,存储器层次,特性,第0层,CPU寄存器,第1层,高速缓存,第2层,主存储器,第3层,磁盘存储器,第4层,磁带存储器,设备工艺,存取时间,容量(字节),成本(美分/KB),带宽(MB/S),传送单位,分配管理,ECL,SRAM,DRAM,磁盘机,磁带机,10ns,25-40ns,60-100ns,10-20ms,2-20min,512B,128KB,512MB,60-228GB,512G-2TB,18000,72,5.6,0.23,0.01,400-800,250-400,80-133,3-5,0.18-0.23,字:4-

3、8B,块:32B,页:0.5-1KB,文件:5-512KB,后援存储器,编译器分配,硬件控制,操作系统,操作系统/用户,操作系统/用户,第五章 并行存储器系统,5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.2.1 包含性 5.2.2 一致性 5.2.3 局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.5 交叉访问的存储器,5.2 包含性、一致性和局部性,5.2.1 包含性（inclusion） 1. 包含性的定义 M0 M1 M2 Mn 所有信息项最初存放在最外层Mn，在处理过程中，它的子集复制到Mn-1，同样， Mn-1的子集复制到Mn-2， 如果在Mi中找

4、到一个信息字，那么同一个字的复制品在所有的高层Mi+1，Mi+2，Mn中都一定可以找到。,2. 相邻层之间的数据传送单位 CPU高速缓存：字 高速缓存主存储器：块（每块32个字节（8个字） 主存磁盘：页面（比如每页4K字节，包含128块） 磁盘磁带：段 包含性可以用下面的图来说明：,CPU寄存器,b,a,M1:高速缓存,a,b为高速缓存 块，32个字节,页面A,a,M2:主存储器,页面B,b,页面A,a,M3:磁盘 存储器,页面B,b,段F,段G,页面A,a,M4:磁带机 后援存储器,页面B,b,段F,段G,字单位,块单位,页单位,段单位,5.2.2 一致性（coherence） 1.一致性定

5、义 同一个信息项与后继存储器层次的副本是一致的。 如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改 。,2.维护一致性的两种策略 （1）写直达（write-through,WT），即如果在Mi（i=1，2，n-1）中修改了一个字，则在Mi+1中需要立即修改。 （2）写回（write-back,WB），即如果在Mi+1 中的修改延迟到Mi中正在修改的字被替换时才进行。,5.2.3 局部性（locality） Hennessy和Patterson（1990年）提出了一条90-10规则：典型程序在10%的代码上可能要耗费其执行时间的90%（例如嵌套循环操作的最内

6、层循环）。 时间局部性（temporal locality）：最近的访问项（指令或数据）很可能在不久的将来再次被访问。即对最近使用区域的集中访问。,空间局部性（spatial locality）：一个进程访问的各项的地址彼此很近，例如，表操作或数组操作含对地址空间中某一区域的集中访问。 顺序局部性（sequential locality）：在典型程序中，除非转移指令产生不按次序的转移外，指令都是顺序执行的。 局部性原理指导我们去设计高速缓存、主存储器以及虚拟存储器组织。,第五章 并行存储器系统,5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.3.1

7、命中率 5.3.2 有效存取时间 5.4 虚拟存储器技术 5.5 交叉访问的存储器,5.3 存储器容量的规划,存储器层次结构的性能是由层次结构的有效存取时间Teff决定的，它依赖于相继层次的命中率和访问频率。,5.3.1 命中率 在Mi中找到一个信息项时，称之为命中，反之称为缺失。 假定在层次结构中的存储器层次为Mi和Mi-1，其中i=1，2，n。在Mi层的命中率hi则是信息项可在Mi中找到的概率。它是表示两个相邻层Mi-1和Mi特性的函数。在Mi中的缺失率定义为1-hi。,相继层的命中率是存储器容量、管理策略和程序行为的函数，它是独立的随机变量，其值在0到1之间。我们假设h0=0和hn=1，

8、这意味着CPU总是先访问M1，并且访问到最外层Mn时总是命中的。 对Mi的访问频率为：,是指在较低层次有i-1次缺失而在Mi有一次命中时访问Mi成功的概率。,通常情况下，有：,这说明，访问内存比访问外存要多。,5.3.2 有效存取时间 每当发生缺失时，就要付出代价去访问较高层次的存储器。这种缺失在Cache中称为块缺失。在主存储器中称为缺页错（page fault），因为块和页面是这些层次之间传送信息的单位。 缺页错付出的时间代价要比块缺失付出的更大：,5.3.3 层次结构的优化 目标： 使Teff接近于M1的t1， 总成本接近于Mn的Cn。 优化过程可以表达为：对一个线性规划求最小值问题:,

9、例子：存储器层次结构设计,存储器层次,存取时间,容量,价格/K字节,高速缓存 主存储器 磁盘阵列,t1 = 25ns t2 = 未知 t3 = 4ms,s1=512K字节 s2=32M字节 s3 = 未知,c1=1.25美元 c2=0.2美元 c3=0.0002美元,要达到有效存取时间Teff=10.04s,高速缓存命中率为h1=0.98，主存储器命中率h2=0.9，总成本上限为15000美元。,解：,如果在同样的预算限制条件下，要吧主存储器容量提高64M字节，那么只好以减少磁盘容量为代价，但是这一变化并不影响高速缓存的命中率。如果使用合适的页面替换算法，可能会增加主存储器的命中率，Teff有

10、所降低。,层次化存储器系统必须解决的问题： （1）数据块在较高层存储器中存放在哪个位置？即块和页的定位问题。如果一个块存放在某一上层存储器中，怎样确定并找到该块，即块的寻址问题。 （2）不命中的将从下层存储器中访问，并将该块调入上层存储器中，但是如果上层存储器中已无空闲空间，则势必将上层存储器中的某一块调出，但应调出那一块，即替换问题。 （3）在写访问时，写入上层存储器中的数据必须在适当的时候写入下层存储器，何时写？,第五章 并行存储器系统,5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.3.1 共享存储和分布存储 5.3.2

11、 DSM与SVM 5.3.3 虚拟存储器的主要技术 5.5 交叉访问的存储器,5.4 虚拟存储器技术,提要： 虚拟存储器提供了几乎没有限制的存储器工作空间。 虚拟地址在编译时产生。 虚拟地址到物理地址的转换在运行时进行，需要使用转换表和映象系统。 替换策略。,5.4.1 共享存储和分布存储 MIMD系统可以分为两种： (1)tightly coupled shared-Memory multiprocessors (2)loosely coupled distributed-Memory multiprocessors 它们可以用图表示如下：,P1,P2,Pn,ICN,SM1,SMm,shar

12、e-Memory multiprocessors,P,ICN,distribued-Memory multiprocessors,LM,P,LM,P,LM,共享存储和分布存储的优缺点： 共享存储器： 易于编程，是单机的自然延伸； 程序员无数据划分的负担； 多进程并发的开销小，效率高，易于进程迁移，任务动态分配简单； 由于每个处理器都通过总线访问存储器，因而限制了处理器的个数，可扩展性差。,分布存储器： 系统结构灵活，可扩展性好； 处理机数目可达成百上千，处理速度有巨大的发展潜力； 算法设计、编程以及任务动态分配比较困难； 很难在处理机之间传递复杂的数据结构，难于进程迁移； 不能支持需要存储空间

13、的大规模数据处理要求。,分布存储的两种编程方法： （1）message-passing，用send，receive原语实现通信，要求程序员在进程的整个运行期间对数据的移动都很清楚； （2）romote procedure call，语言一级传送控制与数据，可以看作是本地调用，但透明度有限。,缺点： 这两种方法都是用来解决不同地址空间的问题，在结点间传递复杂数据结构时都比较困难，需要打包，传递指针也不可能实现。由于个处理机拥有不同的地址空间，使得进程迁移时，该进程所分配到的操作系统资源也得一起移动（打开得文件、文件存取控制块等），这很费时。,5.4.2 DSM与SVM 1.DSM和SVM的提出

14、如何把共享和分布的优点结合起来，取长补短？ 共享分布存储器（Distributed shared Memory，DSM） 虚拟共享存储器（Shared Virtual Memory，SVM） 基于分布存储器的多处理机上，实现物理上分布但逻辑上共享的存储器系统。,虚拟共享存储器的逻辑结构：,CPU1,虚拟共享存储器,LM1,CPU2,LM2,CPUn,LMn,地址映射 部件,地址映射 部件,地址映射 部件,MIMD机器存储系统的发展方向：,共享存储器,分布存储器,共享分布存储器,2.DSM系统的特点 在DSM系统中，每一台处理机都可以访问全局存储器的任一位置，用户可以把它当成全局共享存储器系统。

15、 优点： 编程容易 系统结构灵活 可扩展性好 系统价格低 有较好的软件移植性,DSM系统编制的程序比用消息传递方式编制的程序效率高： （1）在DSM系统中，数据都是以块的方式进行传送，如果一个程序具有较高的局部性，则当把一个数据块传送到一个结点后，该结点对它的访问就成为本地访问，而消息传递方式的每次访问都需要通讯。,（2）许多并行应用程序都是分阶段执行的，每次执行前，都有一个数据交换阶段，其时间受通讯限制。在DSM系统中，数据只有用到的时候才传送，取消了数据交换阶段，把通讯时间加以分散，提高了并行性。 （3）DSM提供的虚存空间比单个结点的存储空间大得多，减少了换页操作。,3.实现DSM的途径

16、 主要有三种： （1）硬件实现：将传统的cache技术扩展应用到松耦合分布式存储多处理机。要增加专用部件以取得高效的实现。 （2）操作系统和库实现：利用虚拟存储管理机制取得共享（sharing）和一致（coherence）。 （3）编译实现：自动将共享访问转换成同步和一致原语。用户需要显式控制全局数据，当传递大量数据时或试图进行进程迁移时极其复杂。,4.主要技术 结构（structure） 粒度（granularity） 数据访问与一致性（access and cosistency） 一致性语义（coherence semantics） 可扩展性（scalability） 异构性（heterogeneity） 结构指共享数据在存储器中的框架（如对象和语言的类型）； 粒度指基本共享单位长度（如字节、字、页或复杂数据结构）。,第五章 并行存储器系统,5.1 存储器系统的层次结构 5.2 包含性、