清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年10月

Presentation on theme: "清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年10月"— Presentation transcript:

1 清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年10月
计算机科学与技术系研究生课程 高等计算机系统结构 清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年10月

2 高等计算机系统结构 第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度
第一章 高等计算机的核心技术——并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第五章 并行存储器系统 第六章 Cache Coherence 第七章 Memory Consistency 第八章 指令级并行处理

3 第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.5 交叉访问的存储器

4 5.1 存储器系统的层次结构 存储器系统的层次结构如下图所示： 容量和存取时间增加 每位成本增加 层0：M0 CPU内的寄存器 高速缓存
主存储器 层2：M2 磁盘存储器 层3：M3 磁带机 层4：M4

5 存取时间ti：从CPU到第i层存储器的往返时间
五个参数： 存取时间ti：从CPU到第i层存储器的往返时间 存储器容量Si：第i层的字节或字的数量 每字节成本Ci：第i层存储器的成本为CiSi 传输带宽bi：相邻层之间传送信息的速率 传输单位Xi：i和i+1层之间数据传送的粒度 对存储器系统中各层次存储器的特性，1993年的统计数据如下表：

6 存储器层次 第0层 第1层 第2层 第3层 第4层 特性 CPU寄存器 高速缓存 主存储器 磁盘存储器 磁带存储器 设备工艺 ECL SRAM DRAM 磁盘机 磁带机 存取时间 10ns 25-40ns 60-100ns 10-20ms 2-20min 容量(字节) 512B 128KB 512MB 60-228GB 512G-2TB 成本(美分/KB) 18000 72 5.6 0.23 0.01 带宽(MB/S) 80-133 3-5 传送单位 字:4-8B 块:32B 页:0.5-1KB 文件:5-512KB 后援存储器 分配管理 编译器分配 硬件控制 操作系统 操作系统/用户 操作系统/用户

7 第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.2.1 包含性 5.3 存储器容量的规划
第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.2.1 包含性 5.2.2 一致性 5.2.3 局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.5 交叉访问的存储器

8 5.2 包含性、一致性和局部性 5.2.1 包含性（inclusion） 1. 包含性的定义 M0 M1 M2……  Mn
所有信息项最初存放在最外层Mn，在处理过程中，它的子集复制到Mn-1，同样， Mn-1的子集复制到Mn-2，…… 如果在Mi中找到一个信息字，那么同一个字的复制品在所有的高层Mi+1，Mi+2，……，Mn中都一定可以找到。

9 2. 相邻层之间的数据传送单位 CPU高速缓存：字 高速缓存主存储器：块（每块32个字节（8个字））
主存磁盘：页面（比如每页4K字节，包含128块） 磁盘磁带：段 包含性可以用下面的图来说明：

10 CPU寄存器 字单位 …… b M1:高速缓存 a,b为高速缓存 块，32个字节 a …… 块单位 页面A a 页面B b M2:主存储器 页单位 段F 页面A a 页面B b 段G M3:磁盘 存储器 段单位 段F 页面A a 页面B b M4:磁带机 后援存储器 段G

11 同一个信息项与后继存储器层次的副本是一致的。
5.2.2 一致性（coherence） 1.一致性定义 同一个信息项与后继存储器层次的副本是一致的。 如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改 。

12 2.维护一致性的两种策略 （1）写直达（write-through,WT），即如果在Mi（i=1，2，…，n-1）中修改了一个字，则在Mi+1中需要立即修改。 （2）写回（write-back,WB），即如果在Mi+1 中的修改延迟到Mi中正在修改的字被替换时才进行。

13 5.2.3 局部性（locality） Hennessy和Patterson（1990年）提出了一条90-10规则：典型程序在10%的代码上可能要耗费其执行时间的90%（例如嵌套循环操作的最内层循环）。 时间局部性（temporal locality）：最近的访问项（指令或数据）很可能在不久的将来再次被访问。即对最近使用区域的集中访问。

14 空间局部性（spatial locality）：一个进程访问的各项的地址彼此很近，例如，表操作或数组操作含对地址空间中某一区域的集中访问。
顺序局部性（sequential locality）：在典型程序中，除非转移指令产生不按次序的转移外，指令都是顺序执行的。 局部性原理指导我们去设计高速缓存、主存储器以及虚拟存储器组织。

15 第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.3.1 命中率
第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.3.1 命中率 5.3.2 有效存取时间 5.4 虚拟存储器技术 5.5 交叉访问的存储器

16 5.3 存储器容量的规划 存储器层次结构的性能是由层次结构的有效存取时间Teff决定的，它依赖于相继层次的命中率和访问频率。

17 在Mi中找到一个信息项时，称之为命中，反之称为缺失。
5.3.1 命中率 在Mi中找到一个信息项时，称之为命中，反之称为缺失。 假定在层次结构中的存储器层次为Mi和Mi-1，其中i=1，2，…，n。在Mi层的命中率hi则是信息项可在Mi中找到的概率。它是表示两个相邻层Mi-1和Mi特性的函数。在Mi中的缺失率定义为1-hi。

18 是指在较低层次有i-1次缺失而在Mi有一次命中时访问Mi成功的概率。
相继层的命中率是存储器容量、管理策略和程序行为的函数，它是独立的随机变量，其值在0到1之间。我们假设h0=0和hn=1，这意味着CPU总是先访问M1，并且访问到最外层Mn时总是命中的。 对Mi的访问频率为： 是指在较低层次有i-1次缺失而在Mi有一次命中时访问Mi成功的概率。

19 通常情况下，有： 这说明，访问内存比访问外存要多。

20 5.3.2 有效存取时间 每当发生缺失时，就要付出代价去访问较高层次的存储器。这种缺失在Cache中称为块缺失。在主存储器中称为缺页错（page fault），因为块和页面是这些层次之间传送信息的单位。 缺页错付出的时间代价要比块缺失付出的更大：

21 5.3.3 层次结构的优化 目标： 使Teff接近于M1的t1， 总成本接近于Mn的Cn。 优化过程可以表达为：对一个线性规划求最小值问题:

22 要达到有效存取时间Teff=10.04s,高速缓存命中率为h1=0.98，主存储器命中率h2=0.9，总成本上限为15000美元。
例子：存储器层次结构设计 存储器层次 存取时间 容量 价格/K字节 高速缓存 主存储器 磁盘阵列 t1 = 25ns t2 = 未知 t3 = 4ms s1=512K字节 s2=32M字节 s3 = 未知 c1=1.25美元 c2=0.2美元 c3=0.0002美元 要达到有效存取时间Teff=10.04s,高速缓存命中率为h1=0.98，主存储器命中率h2=0.9，总成本上限为15000美元。

23 解： 如果在同样的预算限制条件下，要吧主存储器容量提高64M字节，那么只好以减少磁盘容量为代价，但是这一变化并不影响高速缓存的命中率。如果使用合适的页面替换算法，可能会增加主存储器的命中率，Teff有所降低。

24 层次化存储器系统必须解决的问题： （1）数据块在较高层存储器中存放在哪个位置？即块和页的定位问题。如果一个块存放在某一上层存储器中，怎样确定并找到该块，即块的寻址问题。 （2）不命中的将从下层存储器中访问，并将该块调入上层存储器中，但是如果上层存储器中已无空闲空间，则势必将上层存储器中的某一块调出，但应调出那一块，即替换问题。 （3）在写访问时，写入上层存储器中的数据必须在适当的时候写入下层存储器，何时写？

25 第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术
第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.3.1 共享存储和分布存储 5.3.2 DSM与SVM 5.3.3 虚拟存储器的主要技术 5.5 交叉访问的存储器

26 5.4 虚拟存储器技术 提要： 虚拟存储器提供了几乎没有限制的存储器工作空间。 虚拟地址在编译时产生。
虚拟地址到物理地址的转换在运行时进行，需要使用转换表和映象系统。 替换策略。

27 5.4.1 共享存储和分布存储 MIMD系统可以分为两种：
(1)tightly coupled shared-Memory multiprocessors (2)loosely coupled distributed-Memory multiprocessors 它们可以用图表示如下：

28 ICN ICN P1 P2 …… Pn share-Memory multiprocessors SM1 …… SMm P LM P LM
distribued-Memory multiprocessors ICN

29 共享存储和分布存储的优缺点： 共享存储器： 易于编程，是单机的自然延伸； 程序员无数据划分的负担；
多进程并发的开销小，效率高，易于进程迁移，任务动态分配简单； 由于每个处理器都通过总线访问存储器，因而限制了处理器的个数，可扩展性差。

30 分布存储器： 系统结构灵活，可扩展性好； 处理机数目可达成百上千，处理速度有巨大的发展潜力； 算法设计、编程以及任务动态分配比较困难； 很难在处理机之间传递复杂的数据结构，难于进程迁移； 不能支持需要存储空间的大规模数据处理要求。

31 分布存储的两种编程方法： （1）message-passing，用send，receive原语实现通信，要求程序员在进程的整个运行期间对数据的移动都很清楚； （2）romote procedure call，语言一级传送控制与数据，可以看作是本地调用，但透明度有限。

32 缺点： 这两种方法都是用来解决不同地址空间的问题，在接点间传递复杂数据结构时都比较困难，需要打包，传递指针也不可能实现。由于个处理机拥有不同的地址空间，使得进程迁移时，该进程所分配到的操作系统资源也得一起移动（打开得文件、文件存取控制块等），这很费时。

33 5.4.2 DSM与SVM 1.DSM和SVM的提出 如何把共享和分布的优点结合起来，取长补短？
共享分布存储器（Distributed shared Memory，DSM） 虚拟共享存储器（Shared Virtual Memory，SVM） ——基于分布存储器的多处理机上，实现物理上分布但逻辑上共享的存储器系统。

34 虚拟共享存储器的逻辑结构： 虚拟共享存储器 CPU1 CPU2 CPUn …… LM1 LM2 LMn 地址映射 部件 地址映射 部件

35 MIMD机器存储系统的发展方向： 共享存储器 分布存储器 共享分布存储器

36 2.DSM系统的特点 在DSM系统中，每一台处理机都可以访问全局存储器的任一位置，用户可以把它当成全局共享存储器系统。 优点： 编程容易
系统结构灵活 可扩展性好 系统价格低 有较好的软件移植性

37 DSM系统编制的程序比用消息传递方式编制的程序效率高：

38 （2）许多并行应用程序都是分阶段执行的，每次执行前，都有一个数据交换阶段，其时间受通讯限制。在DSM系统中，数据只有用到的时候才传送，取消了数据交换阶段，把通讯时间加以分散，提高了并行性。

39 3.实现DSM的途径 主要有三种： （1）硬件实现：将传统的cache技术扩展应用到松耦合分布式存储多处理机。要增加专用部件以取得高效的实现。 （2）操作系统和库实现：利用虚拟存储管理机制取得共享（sharing）和一致（coherence）。 （3）编译实现：自动将共享访问转换成同步和一致原语。用户需要显式控制全局数据，当传递大量数据时或试图进行进程迁移时极其复杂。

40 4.主要技术 结构（structure） 粒度（granularity） 数据访问与一致性（access and cosistency）
一致性语义（coherence semantics） 可扩展性（scalability） 异构性（heterogeneity） 结构——指共享数据在存储器中的框架（如对象和语言的类型）； 粒度——指基本共享单位长度（如字节、字、页或复杂数据结构）。

41 第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术
第五章 并行存储器系统 5.1 存储器系统的层次结构 5.2 包含性、一致性和局部性 5.3 存储器容量的规划 5.4 虚拟存储器技术 5.5 交叉访问的存储器 5.5.1 两种组织方式 5.5.2 两种方式的比较 5.3.3 带宽和容错

42 5.5 交叉访问的存储器 主存储器由多个模块构成。
假设主存储器包含m=2a个存储器模块，每个模块包含w=2b个存储单元（字），则总存储容量为

43 5.5.1 两种组织方式 交叉访问的存储器可以分为两种： (1)低位交叉方式 (2)高位交叉方式

44 存储器地址的低a位用来指明存储器模块，高b位是每个模块内的字地址。
1.低位交叉方式 存储器地址的低a位用来指明存储器模块，高b位是每个模块内的字地址。 低位m路交叉存取如下图：

45 模块地址缓冲器 …… 地址译码器 MAB MAB MAB M0 M1 Mm-1 a 1 m-1 …… m m+1 2m-1 字 模块 …… …… …… 地址 m(w-1) mw-m+1 mw-1 b MDB MDB MDB M D B 存储器数据缓冲器 数据总线 字地址缓冲器

46 2.高位交叉方式 存储器地址的高a位作为存储器模块地址，邻接的存储器单元被分配在同一个存储器模块中，在每个存储器周期内，只能对各模块存取一个字。所以不支持邻接单元的成块存取。 高位m路交叉存取如下图：

47 模块地址缓冲器 …… 地址译码器 MAB MAB MAB M0 M1 Mm-1 w (m-1)w a …… 1 w+1 mw-w-1 模块 字 …… …… …… 地址 w-1 2w-1 mw-1 b MDB MDB MDB M D B 存储器数据缓冲器 数据总线 字地址缓冲器

48 5.5.2 两种方式的比较 （1）低位交叉以流水线方式支持成块存取 8路低位交叉存取如下图：
将存储器周期称为主周期，细分为m个小周期（m称为交叉存取度），如8路交叉，m=8，w=8，a=b=3，设为主周期，为小周期，则 8路低位交叉存取如下图：

49 数据 存储器地址寄存器(6位) M0 M1 M2 M3 M4 M5 M6 M7 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 … … … … … … … … 56 57 58 59 60 61 62 63 数据

50 为主周期，= /m为小周期，m为交叉存取度
低位交叉流水线方式示意图： W7 W6 W5 W4 W3 W2  W1 W0 时间  为主周期，= /m为小周期，m为交叉存取度

51 （2）如果应用问题很少共享地址空间，把一个进程的几页集中在高位交叉存储器的某个给定的存储器模块种，能有效的减少存储器干扰，即每个存储器模块只和一台处理机有关，可以减少存储器冲突。

52 5.5.3 带宽和容错 1.带宽 讨论低位交叉情况。 带宽B的上限为m，下限为1。Hellerman（1967年）推导出来的公式为： 如果使用16个存储器模块，则有效存储器带宽大约是单个存储器的4倍。产生这一悲观估算的原因是：不同长度的块存取与单字存取在用户程序中是随机混合的。

53 所以，交叉存取适合于长向量的流水线存取。
另外一种估算公式：Cragon（1992年） 假设n个分量存放在m路交叉存取存储器系统邻接的存储单元中，存取向量的一个分量所需的平均时间t1可估算为： 所以，交叉存取适合于长向量的流水线存取。

54 2.容错 将高位与低位交叉存取加以组合。 高位交叉时，各存储器模块内的地址是按顺序编排的。
对8个存储模块，将它们分为2个存储器，体内采用4路低位交叉存取。示意图如下：

55 体0 体1 存储器地址寄存器(6位) 模块地址 体地址 字地址 M0 M1 M2 M3 M4 M5 M6 M7 1 2 3 32 33 34
1 2 3 32 33 34 35 4 5 6 7 36 37 38 39 … … … … … … … … 28 29 30 31 60 61 62 63 体0 体1

56 对8个存储模块，将它们分为4个存储器，体内采用2路低位交叉存取。示意图如下：

57 体0 体1 体2 体3 存储器地址寄存器(6位) 模块地址 体地址 字地址 M0 M1 M2 M3 M4 M5 M6 M7 1 16 17
1 16 17 32 33 48 49 2 3 18 19 34 35 50 51 … … … … … … … … 14 15 30 31 46 47 62 63 体0 体1 体2 体3

58 在一个模块发生故障的情况下： 8路交叉存取存储器的最大存储器带宽减少到零； 4路2体交叉存储器的最大带宽减少到每周期4个字（只有一个体被废弃）； 2路4体交叉存储器中，仍有3个体工作，所以最大带宽为6个字。

59 习题： 假定一个由16个存储器模块构成的主存储器系统有下列三种交叉存储器设计方案。每个模块的容量为1M字节，机器按字节寻址。 设计1：用1个存储体16路交叉。 设计2：用2个存储体8路交叉。 设计3：用4个存储体4路交叉。 （a）确定上述存储器组织的地址构成。 （b）在上述每种存储器组织中，假定只有一个存储器模块失效，确定能获得的最大存储器带宽。 （c）比较说明三种交叉存储器组织的优缺点。