[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层存储器

2、的成本为CiSi 传输带宽bi：相邻层之间传送信息的速率 传输单位Xi：i和i+1层之间数据传送的粒度 对存储器系统中各层次存储器的特性，某统 计数据如下表： 存储器层次 特性 第0层 CPU寄存器 第1层 高速缓存 第2层 主存储器 第3层 磁盘存储器 第4层 磁带存储器 设备工艺 存取时间 容量(字节) 成本(美分/KB) 带宽(MB/S) 传送单位 分配管理 ECLSRAMDRAM磁盘机磁带机 10ns25-40ns60-100ns10-20ms2-20min 512B128KB512MB60-228GB512G-2TB 18000725.60.230.01 400-800250-400

3、80-1333-50.18-0.23 字:4-8B块:32B页:0.5-1KB文件:5- 512KB 后援存储器 编译器分配 硬件控制 操作系统操作系统/ 用户 操作系统/ 用户 第四章 并行存储器系统 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，同样，

4、Mn-1的子集复制到Mn-2， 如果在Mi中找到一个信息字，那么同一个 字的复制品在所有的高层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、 段单位 4.2.2 一致性（coherence） 1.一致性定义 同一个信息项与后继存储器层次的副本是 一致的。 如果在高速缓存中的一个字被修改过，那 么在所有更高层上该字的副本也必须立即或最 后加以修改 。 2.维护一致性的两种策略 （1）写直达（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规

6、则：典型程序在10%的代码上可能要耗 费其执行时间的90%（例如嵌套循环操作的最 内层循环）。 时间局部性（temporal locality）：最近 的访问项（指令或数据）很可能在不久的将来 再次被访问。即对最近使用区域的集中访问。 空间局部性（spatial locality）：一个 进程访问的各项的地址彼此很近，例如，表操 作或数组操作含对地址空间中某一区域的集中 访问。 顺序局部性（sequential locality）：在 典型程序中，除非转移指令产生不按次序的转 移外，指令都是顺序执行的。 局部性原理指导我们去设计高速缓存、主存储器 以及虚拟存储器组织。 第四章 并行存储器系统

7、4.1 存储器系统的层次结构 4.2 包含性、一致性和局部性 4.3 存储器容量的规划 5.3.1 命中率 5.3.2 有效存取时间 4.4 虚拟存储器技术 4.5 交叉访问的存储器 4.3 存储器容量的规划 存储器层次结构的性能是由层次结构的有 效存取时间Teff决定的，它依赖于相继层 次的命中率和访问频率。 4.3.1 命中率 在Mi中找到一个信息项时，称之为命中，反 之称为缺失。 假定在层次结构中的存储器层次为Mi和Mi-1， 其中i=1，2，n。 在Mi层的命中率hi则是信息项可在Mi中找到的 概率。它是表示两个相邻层Mi-1和Mi特性的函数。 在Mi中的缺失率定义为1-hi。 相继层

8、的命中率是存储器容量、管理策略 和程序行为的函数，它是独立的随机变量，其 值在0到1之间。我们，这意味 着CPU总是先访问M1，并且访问到最外层Mn时总 是命中的。 对Mi的访问频率为： iii hhhhf)1()1)(1( 121 是指在较低层次有i-1次缺失而在Mi有一次 命中时访问Mi成功的概率。 11 1 ,1hff n i i iii hhhhf)1()1)(1( 121 n i i f 1 1 1 1 1 1 11 )1( )1( n j jn i j iji hf hhf hf CPU总是先访问M1 访问到最外层Mn时总是命中的 n fff 21 通常情况下，有： 这说明，访问内

9、存比访问外存要多。 4.3.2 有效存取时间 每当发生缺失时，就要付出代价付出代价去访问较高 层次的存储器。这种缺失在Cache中称为块缺失。 在主存储器中称为缺页错（page fault），因为 块和页面是这些层次之间传送信息的单位。 nnn n i iieff thhhh thhthtfT )1()1)(1( )1( 121 1 22111 访问到最外层Mn时总是命中的 4.3.3 层次结构的优化 目标： 使Teff接近于M1的t1， 总成本接近于Mn的CnSn 。 优化过程可以表达为：对一个线性规划求 最小值问题: 减到最小值。要将有效存取时间 总价格的上限）时， 对于 n i iief

10、f n i iitotal ii tfT CSCCS nitS 1 0 1 ( ,2, 1,0,0 例子：存储器层次结构设计 存储器层次存取时间容量价格/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美元。 解： ust thhhthhthT GByteS SCSCSCCS eff 972.111 04.10

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

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

13、可以分为两种： (1)tightly coupled shared-Memory multiprocessors (2)loosely coupled distributed-Memory multiprocessors 它们可以用图表示如下： P1P2Pn ICN (Interconnection Network) SM1SMm share-Memory multiprocessors P ICN distribued-Memory multiprocessors LMPLMPLM 共享存储和分布存储的优缺点： 共享存储器： 易于编程，是单机的自然延伸； 程序员没有数据划分的负担； 多进程并

14、发的开销小，效率高，易于 进程迁移，任务动态分配简单； 由于每个处理器都通过总线通过总线访问存储 器，因而限制了处理器的个数，可扩展性差。 分布存储器： 系统结构灵活，可扩展性好； 处理机数目可达成百上千，处理速度有 巨大的发展潜力； 算法设计、编程以及任务动态分配比较 困难； 很难在处理机之间传递复杂的数据结构， 难于进程迁移； 不能支持需要存储空间的大规模数据处 理要求。 分布存储的两种编程方法： （1）message-passing，用send，receive 原语实现通信，要求程序员在进程的整个运行 期间对数据的移动都很清楚； （2）romote procedure call，语言一级

15、传 送控制与数据，可以看作是本地调用，但透明 度有限。 缺点： 这两种方法都是用来解决不同地址空间的问 题，在结点间传递复杂数据结构时都比较困难， 需要打包。由于每个处理机拥有不同的地址空 间，使得进程迁移时，该进程所分配到的操作 系统资源也得一起移动（打开的文件、文件存 取控制块等），这很费时。 4.4.2 DSM与SVM 1.DSM和SVM的提出 如何把共享和分布的优点结合起来，取长 补短？ 共享分布存储器（Distributed shared Memory，DSM） 虚拟共享存储器（Shared Virtual Memory，SVM） 基于分布存储器的多处理机上，实现物 理上分布但逻辑上

16、共享的存储器系统。 虚拟共享存储器的逻辑结构： CPU1 虚拟共享存储器 LM1 CPU2 LM2 CPUn LMn 地址映射 部件 地址映射 部件 地址映射 部件 MIMD机器存储系统的发展方向： 共享存储器分布存储器共享分布存储器 2.DSM系统的特点 在DSM系统中，每一台处理机都可以访问全 局存储器的任一位置，用户可以把它当成全局共 享存储器系统。 优点： 编程容易 系统结构灵活 可扩展性好 系统价格低 有较好的软件移植性 DSM系统编制的程序比用消息传递方式编制的 程序效率高： （1）在DSM系统中，数据都是以块的方式进行传 送，如果一个程序具有较高的，则当把一 个数据块传送到一个结

17、点后，该结点对它的访问 就成为本地访问，而消息传递方式的每次访问都 需要。 （2）许多并行应用程序都是分阶段执行的，每 次执行前，都有一个数据交换阶段，其时间受通 信限制。在DSM系统中，数据只有用到的时候才 传送，取消了数据交换阶段，把通信时间加以分 散，提高了并行性。 （3）DSM提供的虚存空间比单个结点的存储空间 大得多，减少了换页操作。 3.实现DSM的途径 主要有三种： （1）硬件实现：将传统的cache技术扩展应用 到松耦合分布式存储多处理机。要增加专用部件以 取得高效的实现。 （2）操作系统和库实现：利用虚拟存储管理机 制取得共享（sharing）和一致（coherence）。

18、（3）编译实现：自动将共享访问转换成同步和 一致原语。用户需要显式控制全局数据，当传递大 量数据时或试图进行进程迁移时极其复杂。 4.主要技术 结构（structure） 粒度（granularity） 数据访问与一致性（access and cosistency） 一致性语义（coherence semantics） 可扩展性（scalability） 异构性（heterogeneity） 结构指共享数据在存储器中的框架（如对象 和语言的类型）； 粒度指基本共享单位长度（如字节、字、页 或复杂数据结构）。 第四章 并行存储器系统 4.1 存储器系统的层次结构 4.2 包含性、一致性和局部性

19、4.3 存储器容量的规划 4.4 虚拟存储器技术 4.5 交叉访问的存储器 4.5.1 两种组织方式 4.5.2 两种方式的比较 4.3.3 容错 4.5 交叉访问的存储器 主存储器。 假设主存储器包含m=2a个存储器模块， 每个模块包含w=2b个存储单元（字），则 总存储容量为 个字 ba wm 2 4.5.1 两种组织方式 交叉访问的存储器可以分为两种： (1)低位交叉方式 (2)高位交叉方式 1.低位交叉方式 存储器地址的低a位用来指明存储器模块， 高b位是每个模块内的字地址。 低位m路交叉存取如下图： MAB 0 m m(w-1) MDB M0 MAB 1 m+1 mw-m+1 MDB

20、 M1 MAB m-1 2m-1 mw-1 MDB Mm-1 M D B 字模块 地址 a b 数据总线 存储器数据缓冲器 模块地址缓冲器 字地址缓冲器 每个模块每个模块 包含包含w=2w=2b b 个存储单个存储单 元（字）元（字） 包含包含m=2m=2a a个个 存储器模块存储器模块 行优先！行优先！ 2.高位交叉方式 存储器地址的高a位作为存储器模块地址， 邻接的存储器单元被分配在同一个存储器模块 中，在每个存储器周期内，只能对各模块存取 一个字。所以不支持邻接单元的成块存取。 高位m路交叉存取如下图： MAB 0 1 w-1 MDB M0 MAB w w+1 2w-1 MDB M1 MAB (m-1)w mw-w-1 mw-1 MDB Mm-1 M D B 字模块 地址 a b 数据总线 存储器数据缓冲器 模块地址缓冲器 字地址缓冲器 列优先！列优先！ 4.5.2 两种方式的比较 （1）低位交叉以流水线方式支持成块存取 行优先！行优先！ 0 8 56 存储器地址寄存器(6位) M0 1 9 57 M1 2 10 58 M2 3 11 59 M3 4 12 60 M4 5 13 61 M5 6 14 62 M6 7 15 63 M7 数据 低低3 3位，高位，高3 3位