哈尔滨工业大学计算机科学与技术学院 1
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院 2
第一章 并行计算机模型
? ?1 计算技术的现状
? ?2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
? ?4 并行计算机的抽象模型
??5 可扩展的范围和设计
哈尔滨工业大学计算机科学与技术学院 3
?5 可扩展的范围和设计
一、可扩展性范围
二、可扩展设计原理
哈尔滨工业大学计算机科学与技术学院 4
一,可扩展性范围
?说明,
? 系统伸缩：增加或减少系统资源。
?这里假定并行处理计算机的体系中的
结点均为单一处理器结点
? 可扩展性范围包括,
? 资源可扩展性
? 应用可扩展性
? 技术可扩展性
哈尔滨工业大学计算机科学与技术学院 5
?1,资源可扩展性
? 资源可扩展性是指通过增加处理器数、
更多的存储部件 (高速缓存，存，磁
盘 )以及增加软件等方法，使系统具
有更高性能或功能。涉及三方面,
?规模可伸缩性
?资源扩展
?软件可扩展性
哈尔滨工业大学计算机科学与技术学院 6
? （ 1）规模可伸缩性,
? 规模可伸缩性与处理器数相关联。
? 扩展一个计算机系统 ---增加机器规模
（处理器数）。
? 不同并行计算机规模可扩展能力不同。
? 限制并行系统可扩展性的两个主要因
素是,
?程序设计及通信。
哈尔滨工业大学计算机科学与技术学院 7
? 示例,
? 在 1997年时,
? 一个对称多处理机 (SMP)系统最多能扩展
到大约 64个处理器；
? 一个 IBM SP2并行机能扩展到最多具有 512
个处理器。
哈尔滨工业大学计算机科学与技术学院 8
? 当前的并行计算机规模的扩展,
? 加入更多处理器；
? 增加互连网络、接口以及通信软件在内
的子系统。
? 有效地利用更大并行性，即如何为扩大
的系统进行编程。
哈尔滨工业大学计算机科学与技术学院 9
?（ 2）资源扩展
? 增加处理器数不是唯一方式。
? 保持处理器数不变；
? 通过增加更多存储容量、更大的芯
片外高速缓存以及更大容量磁盘等
方法来扩展系统。
哈尔滨工业大学计算机科学与技术学院 10
? 例题,IBM SP2中的存储器需求
? 当 Maui高性能计算中心 (MHPCC)决定升
级它的具有 400个结点的 SP2系统时，
它选择了增加存储器和磁盘容量方法，
而不是增加更多结点数方法。
? 下表概述了所扩展的存储容量。
哈尔滨工业大学计算机科学与技术学院 11
哈尔滨工业大学计算机科学与技术学院 12
? 要求,
? 系统必须设计成能允许扩展这么多
的容量。
? 实际系统总有一个最大存储器容量
的上限。例如,
?IBM SP2中的每个结点最多可容纳 2GB
存储器；
?CrayT3D为 64MB。
哈尔滨工业大学计算机科学与技术学院 13
? （ 3）软件可扩展性
? 包括,
? 操作系统的一个新版本，它具有更多功
能性，如多线程，从而可支持更多的用
户进程，更大的地址空间以及更高效的
内核功能等。
? 具有更有效优化的编译器。
? 更有效的数学和工程库。
? 更有效和易于使用的应用软件。
? 对用户更友好的编程环境。
哈尔滨工业大学计算机科学与技术学院 14
?2、应用可扩展性
相同程序在一个可扩展系统上运行
时，其性能随规模扩大成比例地改进。
两个度量,
?机器规模可扩展性。
?问题规模的可扩展性。
? （ 1）机器规模可扩展性
? 随着附加处理器的增多，系统性能会
有多大改进。
哈尔滨工业大学计算机科学与技术学院 15
? 例如，假定一个有 n个处理器的系统，
作数据库服务器用
? 它拥有美国人口数据库，通常有 100位
美国科学家查询，其性能为每秒 1000个
事务处理 (TPS)。
? 现在如果我们将处理器数加倍成 2n，能
期望速度有多少改进?期望是多少？
? 所增加的资源中，处理器最为常见；
? 也可能是存储器容量和 I／ O容量。
哈尔滨工业大学计算机科学与技术学院 16
（ 2）问题规模可扩展性
? 是指系统在处理更大数据量和工作负载的
更大求解问题时其性能如何。
? 例如,
? 仍以上述的数据库服务器为例，如果该服
务器上装有中国人口的数据库，则此服务
器的服务质量将会如何?
? 注意到此数据库的大小已增至原来的 5
倍。
? 如果用户数增至 200(100个美国和 100中
国科学家联合参与研究 )，将会发生什
么情况?
哈尔滨工业大学计算机科学与技术学院 17
? 在研究应用可扩展性时，有以下 3点
值得注意,
? 许多实际的并行应用问题对于机器和问
题规模已有内在限制
? 应将, 应用／机器, 一起视为一个系
统
? 它也依赖于资源规模。
哈尔滨工业大学计算机科学与技术学院 18
?3、技术可扩展性
是指该系统能适应技术的改变。
? 它可进一步分为 3类,
? 代可扩展性,
? 空间可扩展性,
? 异构可扩展性。
哈尔滨工业大学计算机科学与技术学院 19
? （ 1） 代 (时间 )可扩展性
?一个系统扩展可以通过使用,
?下一代的硬件部件；
? 更快的处理器
? 更快存储器
?新版本的操作系统；
?更强功能的编译器。
哈尔滨工业大学计算机科学与技术学院 20
? 计算机系统中发展最快的部件是处
理器；
? 进展最慢的部分是程序设计语言
(Fortran 77仍被广泛使用 ) ；
? 单计算机每两年可以将处理器升级
一次
? 并以慢得多的速度更新其他部件。
? 并行计算机中这种更新不活跃 。
哈尔滨工业大学计算机科学与技术学院 21
? 例题,IBM个人计算机的代可扩展性
? 最具有代可扩展的计算机是 IBM PC机。
? PC系统 (从处理器到母板,I／ O卡和软件 )
是设计成代可扩展的。
?
? 现有系统中的二进制代码和应用程序
(DOS,Windows、数据库、电子表格及字
处理软件等 )不用作任何修改，就可在升
级的系统中运行得更快。
哈尔滨工业大学计算机科学与技术学院 22
? （ 2）空间可扩展性
? 这一用语是由 Gorden Bell发明的，用
来表示一个系统可从一个盒子、一间房
间或一幢大楼中的多处理器扩展到多幢
大楼和地理范围 (远距离范围 )中的多处
理器的能力。
?SMP和 MMP只具有有限的空间可扩
展性
?因特网则具有最好的空间可扩展
性
哈尔滨工业大学计算机科学与技术学院 23
?（ 3）异构可扩展性
? 一个系统扩展不同设计者和厂商所
提供的硬件和软件部分的能力。
? 系统应使用具有标准、开放系统结
构和接口的部件。
哈尔滨工业大学计算机科学与技术学院 24
? 例题 1：可扩展并行计算机的软件可
移植性
?IBM并行操作环境 (POE)在任何规模的
RS 6000 系统上具有可扩展性。
哈尔滨工业大学计算机科学与技术学院 25
?POE特点,
? 支持一个并行程序无需任何修改就能在
由 RS6000结点机构成的任何网络中运行
? 结点可以是一个低端 PowerPC工作站，可
以是一个高端 SP2宽结点。
? 这些结点能由任何普通互联网络，从慢
速以太网到 SP2的高性能开关 (HPS)，加
以连接。
? 结点只见的距离不限。
哈尔滨工业大学计算机科学与技术学院 26
? 例题 2：并行虚拟机 (PVM)，它也是异
构可扩展的,
?它允许一个并行程序运行在来自不
同厂商的结点机所构成的网络上。
哈尔滨工业大学计算机科学与技术学院 27
二、可扩展设计原理
?包括,
?独立原理
?平衡设计原理
?可扩展性设计原理
?时延隐藏原理
哈尔滨工业大学计算机科学与技术学院 28
?1,独立原理
? 应努力使系统中的各个组成部分
（硬、软件）相互独立。
? 如果无法达到完全独立，则应尽力
使相关程度减至最小并使相关性尽
量清晰。
哈尔滨工业大学计算机科学与技术学院 29
?采用独立原理的好处,
?使独立扩展成为可能；
?使异构可扩展性成为可能。
? 要求部件不受制于一个特别的体系结构
或系统。
哈尔滨工业大学计算机科学与技术学院 30
? 其特点,
? 它有一个开放的体系结构以及与系统其他
部分衔接的标准接口。
? 它是市售产品，若它不具有版权则更好。
? 它有多家供应商，在公开市场大批量供应。
? 它相对成熟，已为许多人使用相当长时间，
且已完成必要的排错。
哈尔滨工业大学计算机科学与技术学院 31
?独立原理涉及,
? 算法应独立于体系结构。
? 应用应独立于平台。
? 程序设计语言应独立于机器。
? 语言应模块化且具有独立性。
? 结点应独立于网络，而网络接口应独
立于网络拓扑。
哈尔滨工业大学计算机科学与技术学院 32
? 例题，开发 Internet和 IBMSP2中所体
现的独立精神
?Internet的成功是表现独立原理优点
的完美例子。 Internet独立于主机、
互连硬件和应用软件。由不同供应商
提供的，从 PC机到超级计算机的不同
类型主机相互连接起来。
? 互连硬件可以是以太网,FDDI等。
? 用户能用不同软件浏览 Web万维网 。
哈尔滨工业大学计算机科学与技术学院 33
?IBM SP2设计结合了独立原理
? 所设计的结点体系结构允许使用不同
的通信体系结构 (例如以太网或 HPS)。
? 通信协议独立于通信硬件：如以太网
或 HPS，都允许使用标准 IP协议或 IBM
专用用户空间协议 。
哈尔滨工业大学计算机科学与技术学院 34
? 例题,MPI及超立方体计算机
? 消息传递接口 (MPl)是使用少量独立 (正交 )语
言特征的佳例。
? MPI基于 4个相互正交的主要概念,
? 数据类型
? 通信操作
? 通信子
? 虚拟拓扑
? 4者的任何组合均是有效的。
哈尔滨工业大学计算机科学与技术学院 35
? 完全的独立起到了事半功倍效果,
? 少数简单概念，组合在一起时能提供许
多功能。
? 为较早期的超立方体计算机而开发的许
多并行算法显式地使用超立方体的互连
拓扑，但在网络连接系统中，它们并不
适用。
? 吸取这一教训，现在的 MPP使用独立于互
连拓扑的通信算法。 IBM SP系统中的集
合通信库便是一个很好的例子。
哈尔滨工业大学计算机科学与技术学院 36
?两种公共技术用来实现独立原理,
?将体系结构和实现分开
?使用标准组件。
哈尔滨工业大学计算机科学与技术学院 37
?（ 1）体系结构和实现的分开
? 体系结构是计算机系统系列或系统组件
的公共行为或功能性精确模型 (或说明 )。
? 而实现是对模型的具体实施。
? 用户和设计者均可使用体系结构模型。
? 一个体系结构可有许多不同实现，它们
会有不同性能，但实现相同功能。
哈尔滨工业大学计算机科学与技术学院 38
? 体系结构的改进是开放体系结构 (或
开放系统 ),
? 体系结构的拥有者 (通常是供应商 )允许
用户或第 3方了解体系结构；
? 用户可自己制造与体系结构兼容的组件，
甚至修改或重新加以设计；
? IBM PC机证实了这的确是一个技术上有
影响的、商业上可行的。
哈尔滨工业大学计算机科学与技术学院 39
?（ 2）使用标准组件
? 有两种标准类型,
? 第一种是工业标准 (也称为事实标准 )，
它通常为某公司所倡导，然后被最终用
户广泛使用并为工业界的大多数所接受。
? 第二种标准类型是由国家或国际标准机
构所设立的，如国际标准组织 (ISO)，美
国国家标准机构 (ANSl)以及 IEEE标准委
员会。
哈尔滨工业大学计算机科学与技术学院 40
? 在使用独立原理时应注意,
? 并行计算机中通常有某种关键组件和技
术是先进的，但往往还不是标准。
? 不可能靠简单地单纯扩展一个或少数几
个组件建成一个有效的系统。
? 必须在所有子系统间设计之间达到一个
平衡系统。
哈尔滨工业大学计算机科学与技术学院 41
?2.平衡设计原理
? 应努力最小化任何性能瓶颈。
? 应避免不平衡系统的设计，在这种系统
中，一个慢速的部件将降低整个系统性
能，即使其他部件都是快速的也无济于
事。
? 应避免单点失效，即一个部件失效将使
整个系统崩溃。
哈尔滨工业大学计算机科学与技术学院 42
?（ 1） Amdahl定律,
? 假定一个应用程序可分为两类计算结构：
X部分和 Y部分。两部分各自所占的总执
行时间分别为,
? X％和 Y％,
哈尔滨工业大学计算机科学与技术学院 43
? 如果对 X％作了某种改进后能以原来 n倍
速度运行，则加速比 S定义如下,
哈尔滨工业大学计算机科学与技术学院 44
? 此方程被称为 Amdahl定律，含义,
? 应优化较大部分 X，加速普通部分。
? 最好加速比的上限值为 1／ Y。
? 慢速部分 Y称为瓶颈，应使 Y尽可能
小。
哈尔滨工业大学计算机科学与技术学院 45
?Amdahl法则,
? 处理速度应与存储器容量和 I／ O速度相
平衡。
? 实现,
? 粗略地估计每秒一百万指令 (MIPS)的
计算速度，应与 1MB存储器容量和 1Mb
／ s的 I／ O速率相平衡。
? Amdahl法则在近来的系统中逐渐适用
哈尔滨工业大学计算机科学与技术学院 46
? 例,PetaFLOPS科研项目
? 来自 PetaFLOPS科研项目的近期预测表明，
在科学／工程模拟求解很宽的问题范围内,
对存储器需求 (以 GB计 )和速度要求 (以
Gflop／ s计 )有如下关系,
? 存储器 ----速度 3/4
? 这样 30TB容量的存储器对一个 Pflop／ s机
器是适合的。这里的,
? 1Pflop／ s=1,000,000Gflop／ s。
哈尔滨工业大学计算机科学与技术学院 47
?例 I／ O和检查点问题
? 为了解 I／ O速度需求，应考虑检查点
问题,
? 该系统需要周期地转存存储器内容到
磁盘，万一系统崩溃时，用户能从最
近检查点重新开始他们的工作，而不
必重头开始。
哈尔滨工业大学计算机科学与技术学院 48
? 假设要求转存在 90秒内完成，那么对
1MB存储器来讲，我们需要的磁盘带宽
为 1／ 90 （ Mb／ s） =0,01Mb／ s，不
接近 Amdahl法则。
? 对于更大系统，则检查点时间就会更
长。假设转存时间为 900秒，那么对于
有 1GB存储器的机器，需要的磁盘带宽
为 1000／ 900MB／ s=1,1MB／ s。
? 对于 100GB存储器，对磁盘 I/O需求就
将增至大于 100MB／ s。
哈尔滨工业大学计算机科学与技术学院 49
? （ 2） 50％法则
? 并行程序性能由于负载不平衡、并行化
开销、通信启动开销以及每字节通信开
销，会发生衰减。
? 50％法则是,4个开销因素的每一个使性
能衰减都不大于 50％的话，那么就认为
此并行系统是平衡的。
? 使用这一规则，就能估计对种种开销因
素的期望界限值。
哈尔滨工业大学计算机科学与技术学院 50
? 下表列出了在不同颗粒度和速度条件
下，对通信启动开销 t0的期望值。
? 包括,
? 启动开销大的机器；
? 启动开销快的机器。
哈尔滨工业大学计算机科学与技术学院 51
哈尔滨工业大学计算机科学与技术学院 52
? 当消息大小 α ·ω 或颗粒度 ω 很大时,
? 带宽 r∞ =1／ tc变为最重要因素。
? 其中, α 是 通讯与计算的比
? 下表列出了在不同的速度 P1和 α （ 通讯与
计算的比）的一些情况下，所期望的带宽
r∞ 值。
哈尔滨工业大学计算机科学与技术学院 53
哈尔滨工业大学计算机科学与技术学院 54
? 例题,PDE求解方法中的栅格点阵二维 (2D)
问题中的许多数值并行偏微分方程 (PDE)
求解方法
? 使用的方案,
? 数据域是一个有 N× N个数据点的 2D栅格。
每个数据点需要 X个字节的存储器，那么
总的存储器需求为 N2X字节。该算法完成
许多 (例如 10 000)时间步。每一步中，一
个栅格点需要完成 Y-flop
哈尔滨工业大学计算机科学与技术学院 55
?计算并访问它的 4个邻点。当用单
处理器执行时所需时间为,
哈尔滨工业大学计算机科学与技术学院 56
?用 n个处理器的 MPP处理
?数据域可分解成 n个方块区域,
?每个区域是一个 (N／ n1/2)x(N／
n1/2)子域
?共有 N2／ n栅格点。
哈尔滨工业大学计算机科学与技术学院 57
? 在每个时间步，每个处理器的计算工
作负载是 YN2/n。
? 每个处理器需要从 4个邻点的每一点中
获取 XN／ n1/2字节,
? 这样在一个有 n个处理器的机器上，所
需的执行时间大约为,
哈尔滨工业大学计算机科学与技术学院 58
? 常数因素 8是这样得到的，即每个处理
器需要对 4个邻点中的每一个发送一个
消息并从那里接收一个消息。它的加
速比因子为,
哈尔滨工业大学计算机科学与技术学院 59
? 对于 4种并行计算机，它们的加速比曲线如
图所示,
哈尔滨工业大学计算机科学与技术学院 60
? (1)第 1个系统的处理器速度为
? 50Mflop／ s，它们用 t0=550Bs以及
r∞ =1MB／ s的慢速通信网互连。此网
络速度与以太网的点对点通信相近。
? 当问题规模 N=1024时，系统 A的加速比
很差 (在图中的下方用正方块曲线表
示 ),128个处理器的加速比小于 10。
哈尔滨工业大学计算机科学与技术学院 61
? 当问题规模增至 8倍为 8K时 (图中用菱
形曲线表示 )，加速比有很大改进。
? 因为此时颗粒度 W增大了，通信 -计算
比 α 减小了。
哈尔滨工业大学计算机科学与技术学院 62
? (2)第 2个系统 (上图中用三角曲
线表示 )的处理器速度为,
?100Mflop／ s（比第一个系统快
一倍 )，它们用同样的慢速网互
连。由于这是不平衡设计，在问
题规模 N=8192时，加速比下跌。
哈尔滨工业大学计算机科学与技术学院 63
?(3)第 3个系统 (在上图中的顶部,
用圆圈曲线表示 )比系统 B更为平衡，
它的 100Mflop／ s处理器用类似于
IBM SP2的快速网互连,t0=46μ s,
r∞ =35MB／ s。它的平衡设计使得它
在 3台机器中具有最好的性能 。
哈尔滨工业大学计算机科学与技术学院 64
?3、可扩展性设计
? 该设计原理说明，在设计一个可扩展的
系统时，应该从一开始就将可扩展性作
为主要目标，而不是设计完成后再来考
虑这一问题。
? 必须为系统将来可能扩展以提供更高性
能或缩小以使价格降低或是有更大的成
本有效性作好准备。
? 可扩展性设计的两种流行方法是过度设
计和向后兼容性。
哈尔滨工业大学计算机科学与技术学院 65
? （ 1）过度设计
? 使用过度设计技术是指系统在设计时
不单纯地只是为了满足目前系统的最
低需要。
? 设计必须包括一些附加特性，以期在
未来的扩展系统中性能得到改进。这
些特性在目前系统中可能是浪费的，
但它们将会使目前系统向未来改进的
系统过渡时变得顺畅。
哈尔滨工业大学计算机科学与技术学院 66
? 例：现代处理器设计中的地址空间
? 在设计处理器时要考虑的最重要的
问题之一是它的地址空间大小，即处
理器能直接访问的字节单元数。引用
Gordon Bell的说法,
? 在体系结构设计的错误中，唯一在以
后不易改正的错误是采用小的地址空
间。
哈尔滨工业大学计算机科学与技术学院 67
?现代的处理器支持 64位地址空间，
或 2６４ =11,8x 1019B。这一巨大
的地址空间，对于仅支持 32位
(4GB)的 Unix来讲可能未被充分利
用。
?但地址空间的过度设计为操作系
统扩展为 64位 Unix时的方便过渡
创造了条件。
哈尔滨工业大学计算机科学与技术学院 68
? 示例,
? 在最初的 IBM PC中使用的处理器 —
Intel 8086／ 8088微处理器中，它
的 地址空间被限制为 20位或 1MB。
?DOS对内核和用户软件限制使用
640KB地址空间。这个 340KB的限制
给编译程序的编写人员以及应用软
件开发者带来许多烦恼。
哈尔滨工业大学计算机科学与技术学院 69
? 因为 DOS程序 (包括 Windows)不能超
过 640KB限制，软件设计者不得不创
造一些复杂技术
?(例如高位存储器、扩充存储器和扩展
存储器 )
? 以使后几代的处理器 (Intel286、
386,486,Pentium以及 PentiumPro)
能使用更大的地址空间。
哈尔滨工业大学计算机科学与技术学院 70
? 例题 IBM RS6000SMP服务器中的过度设
计
? 考虑到代的可扩展性,IBM RS6000 SMP
作了过度设计。
? 第一代的 SMP基于 PowerPC 601处理器。
? 系统的其他部分，从存储器,I/O、电源、
凤扇直到时钟电路，都设计成可容纳后
两代的处理器 PowerPC604以及 620。
哈尔滨工业大学计算机科学与技术学院 71
? 每个处理器的开关口的带宽为 600MB
／ S，大于 PC601的需要。
? 这些过度设计的特性使得在扩展为
未来一代 SMP系统时非常容易；
? 只要简单地升级处理器就可实现。
哈尔滨工业大学计算机科学与技术学院 72
?（ 2）向后兼容性
? 是说在设计硬件或软件部分时，必须兼
顾缩减系统的需求。
哈尔滨工业大学计算机科学与技术学院 73
? 例如,
? 新处理器应能执行老处理器的二进
制代码。
? 为在 n个结点上运行而设计的并行程
序，应能在单结点 (n=1)上运行，此
时可能只要求缩减的输入数据集。
哈尔滨工业大学计算机科学与技术学院 74
? 超级计算机程序应能在工作站上运
行。此外，输入数据集必须适应工
作站的有限主存容量。
? 操作系统的新版本应保留所有原来
的功能，除了那些过时的不再使用，
对此必须用文档清楚地加以说明 。
哈尔滨工业大学计算机科学与技术学院 75
?例：处理器中数据总线宽度的向
后兼容性
?现代处理器的 CPU，总线有一条
64位数据总线。某些处理器支持
向后兼容性，它们允许 64位处理
器用在含有较小数据总线宽度
(32,16或 8位 )的母板上。
哈尔滨工业大学计算机科学与技术学院 76
? 这只需对该处理器的少数控制引脚
进行设置就可做到这一点。
? 假定处理器需要两个总线周期完成
存储器的读操作 (一个周期送地址，
另一个周期从存储器读出 64位数据 )。
? 则当在一个 8位母板上进行读操作时，
处理器的设置将自动地在 9个总线周
期内从存储器读出 64位数据。
哈尔滨工业大学计算机科学与技术学院 77
? 例 IBM SP系统中的并行操作环境
? IBM并行操作环境 (POE)最初是为 IBM
可扩展并行计算机 (SPl和 SP2)设计的。
? 环境中，用户的应用程序在多个 SP结
点上执行。 POE支持的向后兼容性如
下,
? POE完全可在一个结点上执行，因此它
允许多个用户任务在一个结点上运行。
? 该结点不必非是一个 SP结点，它可以是
任何 RS6000工作站。
? POE是在 IBMUnix(AIX)上实现的，因此
已有的 Unix程序可在 POE中运行。
哈尔滨工业大学计算机科学与技术学院 78
? 说明,
? 向后兼容性并不表示一个旧系统的所
有特性都应保留。
? 应该剔除陈旧的特性。
? 在应用过度设计技术时，应考虑成本
问题且不应对未来期待过多，虽然有
时过度设计确实能减少总的开发和生
产成本。
哈尔滨工业大学计算机科学与技术学院 79
? 例题,Intel 486DX和 486SX
? 当 Intel推出 80486微处理器芯片时，
共有两种模型,
? 486DX和 486SX。
? 两种芯片在内部是完全一样的。两者
唯一差别是,
? 在 SX芯片上，浮点部件 (FPU)不能用；
? DX芯片有浮点部件 (FPU) 。
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院 2
第一章 并行计算机模型
? ?1 计算技术的现状
? ?2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
? ?4 并行计算机的抽象模型
??5 可扩展的范围和设计
哈尔滨工业大学计算机科学与技术学院 3
?5 可扩展的范围和设计
一、可扩展性范围
二、可扩展设计原理
哈尔滨工业大学计算机科学与技术学院 4
一,可扩展性范围
?说明,
? 系统伸缩：增加或减少系统资源。
?这里假定并行处理计算机的体系中的
结点均为单一处理器结点
? 可扩展性范围包括,
? 资源可扩展性
? 应用可扩展性
? 技术可扩展性
哈尔滨工业大学计算机科学与技术学院 5
?1,资源可扩展性
? 资源可扩展性是指通过增加处理器数、
更多的存储部件 (高速缓存，存，磁
盘 )以及增加软件等方法，使系统具
有更高性能或功能。涉及三方面,
?规模可伸缩性
?资源扩展
?软件可扩展性
哈尔滨工业大学计算机科学与技术学院 6
? （ 1）规模可伸缩性,
? 规模可伸缩性与处理器数相关联。
? 扩展一个计算机系统 ---增加机器规模
（处理器数）。
? 不同并行计算机规模可扩展能力不同。
? 限制并行系统可扩展性的两个主要因
素是,
?程序设计及通信。
哈尔滨工业大学计算机科学与技术学院 7
? 示例,
? 在 1997年时,
? 一个对称多处理机 (SMP)系统最多能扩展
到大约 64个处理器；
? 一个 IBM SP2并行机能扩展到最多具有 512
个处理器。
哈尔滨工业大学计算机科学与技术学院 8
? 当前的并行计算机规模的扩展,
? 加入更多处理器；
? 增加互连网络、接口以及通信软件在内
的子系统。
? 有效地利用更大并行性，即如何为扩大
的系统进行编程。
哈尔滨工业大学计算机科学与技术学院 9
?（ 2）资源扩展
? 增加处理器数不是唯一方式。
? 保持处理器数不变；
? 通过增加更多存储容量、更大的芯
片外高速缓存以及更大容量磁盘等
方法来扩展系统。
哈尔滨工业大学计算机科学与技术学院 10
? 例题,IBM SP2中的存储器需求
? 当 Maui高性能计算中心 (MHPCC)决定升
级它的具有 400个结点的 SP2系统时，
它选择了增加存储器和磁盘容量方法，
而不是增加更多结点数方法。
? 下表概述了所扩展的存储容量。
哈尔滨工业大学计算机科学与技术学院 11
哈尔滨工业大学计算机科学与技术学院 12
? 要求,
? 系统必须设计成能允许扩展这么多
的容量。
? 实际系统总有一个最大存储器容量
的上限。例如,
?IBM SP2中的每个结点最多可容纳 2GB
存储器；
?CrayT3D为 64MB。
哈尔滨工业大学计算机科学与技术学院 13
? （ 3）软件可扩展性
? 包括,
? 操作系统的一个新版本，它具有更多功
能性，如多线程，从而可支持更多的用
户进程，更大的地址空间以及更高效的
内核功能等。
? 具有更有效优化的编译器。
? 更有效的数学和工程库。
? 更有效和易于使用的应用软件。
? 对用户更友好的编程环境。
哈尔滨工业大学计算机科学与技术学院 14
?2、应用可扩展性
相同程序在一个可扩展系统上运行
时，其性能随规模扩大成比例地改进。
两个度量,
?机器规模可扩展性。
?问题规模的可扩展性。
? （ 1）机器规模可扩展性
? 随着附加处理器的增多，系统性能会
有多大改进。
哈尔滨工业大学计算机科学与技术学院 15
? 例如，假定一个有 n个处理器的系统，
作数据库服务器用
? 它拥有美国人口数据库，通常有 100位
美国科学家查询，其性能为每秒 1000个
事务处理 (TPS)。
? 现在如果我们将处理器数加倍成 2n，能
期望速度有多少改进?期望是多少？
? 所增加的资源中，处理器最为常见；
? 也可能是存储器容量和 I／ O容量。
哈尔滨工业大学计算机科学与技术学院 16
（ 2）问题规模可扩展性
? 是指系统在处理更大数据量和工作负载的
更大求解问题时其性能如何。
? 例如,
? 仍以上述的数据库服务器为例，如果该服
务器上装有中国人口的数据库，则此服务
器的服务质量将会如何?
? 注意到此数据库的大小已增至原来的 5
倍。
? 如果用户数增至 200(100个美国和 100中
国科学家联合参与研究 )，将会发生什
么情况?
哈尔滨工业大学计算机科学与技术学院 17
? 在研究应用可扩展性时，有以下 3点
值得注意,
? 许多实际的并行应用问题对于机器和问
题规模已有内在限制
? 应将, 应用／机器, 一起视为一个系
统
? 它也依赖于资源规模。
哈尔滨工业大学计算机科学与技术学院 18
?3、技术可扩展性
是指该系统能适应技术的改变。
? 它可进一步分为 3类,
? 代可扩展性,
? 空间可扩展性,
? 异构可扩展性。
哈尔滨工业大学计算机科学与技术学院 19
? （ 1） 代 (时间 )可扩展性
?一个系统扩展可以通过使用,
?下一代的硬件部件；
? 更快的处理器
? 更快存储器
?新版本的操作系统；
?更强功能的编译器。
哈尔滨工业大学计算机科学与技术学院 20
? 计算机系统中发展最快的部件是处
理器；
? 进展最慢的部分是程序设计语言
(Fortran 77仍被广泛使用 ) ；
? 单计算机每两年可以将处理器升级
一次
? 并以慢得多的速度更新其他部件。
? 并行计算机中这种更新不活跃 。
哈尔滨工业大学计算机科学与技术学院 21
? 例题,IBM个人计算机的代可扩展性
? 最具有代可扩展的计算机是 IBM PC机。
? PC系统 (从处理器到母板,I／ O卡和软件 )
是设计成代可扩展的。
?
? 现有系统中的二进制代码和应用程序
(DOS,Windows、数据库、电子表格及字
处理软件等 )不用作任何修改，就可在升
级的系统中运行得更快。
哈尔滨工业大学计算机科学与技术学院 22
? （ 2）空间可扩展性
? 这一用语是由 Gorden Bell发明的，用
来表示一个系统可从一个盒子、一间房
间或一幢大楼中的多处理器扩展到多幢
大楼和地理范围 (远距离范围 )中的多处
理器的能力。
?SMP和 MMP只具有有限的空间可扩
展性
?因特网则具有最好的空间可扩展
性
哈尔滨工业大学计算机科学与技术学院 23
?（ 3）异构可扩展性
? 一个系统扩展不同设计者和厂商所
提供的硬件和软件部分的能力。
? 系统应使用具有标准、开放系统结
构和接口的部件。
哈尔滨工业大学计算机科学与技术学院 24
? 例题 1：可扩展并行计算机的软件可
移植性
?IBM并行操作环境 (POE)在任何规模的
RS 6000 系统上具有可扩展性。
哈尔滨工业大学计算机科学与技术学院 25
?POE特点,
? 支持一个并行程序无需任何修改就能在
由 RS6000结点机构成的任何网络中运行
? 结点可以是一个低端 PowerPC工作站，可
以是一个高端 SP2宽结点。
? 这些结点能由任何普通互联网络，从慢
速以太网到 SP2的高性能开关 (HPS)，加
以连接。
? 结点只见的距离不限。
哈尔滨工业大学计算机科学与技术学院 26
? 例题 2：并行虚拟机 (PVM)，它也是异
构可扩展的,
?它允许一个并行程序运行在来自不
同厂商的结点机所构成的网络上。
哈尔滨工业大学计算机科学与技术学院 27
二、可扩展设计原理
?包括,
?独立原理
?平衡设计原理
?可扩展性设计原理
?时延隐藏原理
哈尔滨工业大学计算机科学与技术学院 28
?1,独立原理
? 应努力使系统中的各个组成部分
（硬、软件）相互独立。
? 如果无法达到完全独立，则应尽力
使相关程度减至最小并使相关性尽
量清晰。
哈尔滨工业大学计算机科学与技术学院 29
?采用独立原理的好处,
?使独立扩展成为可能；
?使异构可扩展性成为可能。
? 要求部件不受制于一个特别的体系结构
或系统。
哈尔滨工业大学计算机科学与技术学院 30
? 其特点,
? 它有一个开放的体系结构以及与系统其他
部分衔接的标准接口。
? 它是市售产品，若它不具有版权则更好。
? 它有多家供应商，在公开市场大批量供应。
? 它相对成熟，已为许多人使用相当长时间，
且已完成必要的排错。
哈尔滨工业大学计算机科学与技术学院 31
?独立原理涉及,
? 算法应独立于体系结构。
? 应用应独立于平台。
? 程序设计语言应独立于机器。
? 语言应模块化且具有独立性。
? 结点应独立于网络，而网络接口应独
立于网络拓扑。
哈尔滨工业大学计算机科学与技术学院 32
? 例题，开发 Internet和 IBMSP2中所体
现的独立精神
?Internet的成功是表现独立原理优点
的完美例子。 Internet独立于主机、
互连硬件和应用软件。由不同供应商
提供的，从 PC机到超级计算机的不同
类型主机相互连接起来。
? 互连硬件可以是以太网,FDDI等。
? 用户能用不同软件浏览 Web万维网 。
哈尔滨工业大学计算机科学与技术学院 33
?IBM SP2设计结合了独立原理
? 所设计的结点体系结构允许使用不同
的通信体系结构 (例如以太网或 HPS)。
? 通信协议独立于通信硬件：如以太网
或 HPS，都允许使用标准 IP协议或 IBM
专用用户空间协议 。
哈尔滨工业大学计算机科学与技术学院 34
? 例题,MPI及超立方体计算机
? 消息传递接口 (MPl)是使用少量独立 (正交 )语
言特征的佳例。
? MPI基于 4个相互正交的主要概念,
? 数据类型
? 通信操作
? 通信子
? 虚拟拓扑
? 4者的任何组合均是有效的。
哈尔滨工业大学计算机科学与技术学院 35
? 完全的独立起到了事半功倍效果,
? 少数简单概念，组合在一起时能提供许
多功能。
? 为较早期的超立方体计算机而开发的许
多并行算法显式地使用超立方体的互连
拓扑，但在网络连接系统中，它们并不
适用。
? 吸取这一教训，现在的 MPP使用独立于互
连拓扑的通信算法。 IBM SP系统中的集
合通信库便是一个很好的例子。
哈尔滨工业大学计算机科学与技术学院 36
?两种公共技术用来实现独立原理,
?将体系结构和实现分开
?使用标准组件。
哈尔滨工业大学计算机科学与技术学院 37
?（ 1）体系结构和实现的分开
? 体系结构是计算机系统系列或系统组件
的公共行为或功能性精确模型 (或说明 )。
? 而实现是对模型的具体实施。
? 用户和设计者均可使用体系结构模型。
? 一个体系结构可有许多不同实现，它们
会有不同性能，但实现相同功能。
哈尔滨工业大学计算机科学与技术学院 38
? 体系结构的改进是开放体系结构 (或
开放系统 ),
? 体系结构的拥有者 (通常是供应商 )允许
用户或第 3方了解体系结构；
? 用户可自己制造与体系结构兼容的组件，
甚至修改或重新加以设计；
? IBM PC机证实了这的确是一个技术上有
影响的、商业上可行的。
哈尔滨工业大学计算机科学与技术学院 39
?（ 2）使用标准组件
? 有两种标准类型,
? 第一种是工业标准 (也称为事实标准 )，
它通常为某公司所倡导，然后被最终用
户广泛使用并为工业界的大多数所接受。
? 第二种标准类型是由国家或国际标准机
构所设立的，如国际标准组织 (ISO)，美
国国家标准机构 (ANSl)以及 IEEE标准委
员会。
哈尔滨工业大学计算机科学与技术学院 40
? 在使用独立原理时应注意,
? 并行计算机中通常有某种关键组件和技
术是先进的，但往往还不是标准。
? 不可能靠简单地单纯扩展一个或少数几
个组件建成一个有效的系统。
? 必须在所有子系统间设计之间达到一个
平衡系统。
哈尔滨工业大学计算机科学与技术学院 41
?2.平衡设计原理
? 应努力最小化任何性能瓶颈。
? 应避免不平衡系统的设计，在这种系统
中，一个慢速的部件将降低整个系统性
能，即使其他部件都是快速的也无济于
事。
? 应避免单点失效，即一个部件失效将使
整个系统崩溃。
哈尔滨工业大学计算机科学与技术学院 42
?（ 1） Amdahl定律,
? 假定一个应用程序可分为两类计算结构：
X部分和 Y部分。两部分各自所占的总执
行时间分别为,
? X％和 Y％,
哈尔滨工业大学计算机科学与技术学院 43
? 如果对 X％作了某种改进后能以原来 n倍
速度运行，则加速比 S定义如下,
哈尔滨工业大学计算机科学与技术学院 44
? 此方程被称为 Amdahl定律，含义,
? 应优化较大部分 X，加速普通部分。
? 最好加速比的上限值为 1／ Y。
? 慢速部分 Y称为瓶颈，应使 Y尽可能
小。
哈尔滨工业大学计算机科学与技术学院 45
?Amdahl法则,
? 处理速度应与存储器容量和 I／ O速度相
平衡。
? 实现,
? 粗略地估计每秒一百万指令 (MIPS)的
计算速度，应与 1MB存储器容量和 1Mb
／ s的 I／ O速率相平衡。
? Amdahl法则在近来的系统中逐渐适用
哈尔滨工业大学计算机科学与技术学院 46
? 例,PetaFLOPS科研项目
? 来自 PetaFLOPS科研项目的近期预测表明，
在科学／工程模拟求解很宽的问题范围内,
对存储器需求 (以 GB计 )和速度要求 (以
Gflop／ s计 )有如下关系,
? 存储器 ----速度 3/4
? 这样 30TB容量的存储器对一个 Pflop／ s机
器是适合的。这里的,
? 1Pflop／ s=1,000,000Gflop／ s。
哈尔滨工业大学计算机科学与技术学院 47
?例 I／ O和检查点问题
? 为了解 I／ O速度需求，应考虑检查点
问题,
? 该系统需要周期地转存存储器内容到
磁盘，万一系统崩溃时，用户能从最
近检查点重新开始他们的工作，而不
必重头开始。
哈尔滨工业大学计算机科学与技术学院 48
? 假设要求转存在 90秒内完成，那么对
1MB存储器来讲，我们需要的磁盘带宽
为 1／ 90 （ Mb／ s） =0,01Mb／ s，不
接近 Amdahl法则。
? 对于更大系统，则检查点时间就会更
长。假设转存时间为 900秒，那么对于
有 1GB存储器的机器，需要的磁盘带宽
为 1000／ 900MB／ s=1,1MB／ s。
? 对于 100GB存储器，对磁盘 I/O需求就
将增至大于 100MB／ s。
哈尔滨工业大学计算机科学与技术学院 49
? （ 2） 50％法则
? 并行程序性能由于负载不平衡、并行化
开销、通信启动开销以及每字节通信开
销，会发生衰减。
? 50％法则是,4个开销因素的每一个使性
能衰减都不大于 50％的话，那么就认为
此并行系统是平衡的。
? 使用这一规则，就能估计对种种开销因
素的期望界限值。
哈尔滨工业大学计算机科学与技术学院 50
? 下表列出了在不同颗粒度和速度条件
下，对通信启动开销 t0的期望值。
? 包括,
? 启动开销大的机器；
? 启动开销快的机器。
哈尔滨工业大学计算机科学与技术学院 51
哈尔滨工业大学计算机科学与技术学院 52
? 当消息大小 α ·ω 或颗粒度 ω 很大时,
? 带宽 r∞ =1／ tc变为最重要因素。
? 其中, α 是 通讯与计算的比
? 下表列出了在不同的速度 P1和 α （ 通讯与
计算的比）的一些情况下，所期望的带宽
r∞ 值。
哈尔滨工业大学计算机科学与技术学院 53
哈尔滨工业大学计算机科学与技术学院 54
? 例题,PDE求解方法中的栅格点阵二维 (2D)
问题中的许多数值并行偏微分方程 (PDE)
求解方法
? 使用的方案,
? 数据域是一个有 N× N个数据点的 2D栅格。
每个数据点需要 X个字节的存储器，那么
总的存储器需求为 N2X字节。该算法完成
许多 (例如 10 000)时间步。每一步中，一
个栅格点需要完成 Y-flop
哈尔滨工业大学计算机科学与技术学院 55
?计算并访问它的 4个邻点。当用单
处理器执行时所需时间为,
哈尔滨工业大学计算机科学与技术学院 56
?用 n个处理器的 MPP处理
?数据域可分解成 n个方块区域,
?每个区域是一个 (N／ n1/2)x(N／
n1/2)子域
?共有 N2／ n栅格点。
哈尔滨工业大学计算机科学与技术学院 57
? 在每个时间步，每个处理器的计算工
作负载是 YN2/n。
? 每个处理器需要从 4个邻点的每一点中
获取 XN／ n1/2字节,
? 这样在一个有 n个处理器的机器上，所
需的执行时间大约为,
哈尔滨工业大学计算机科学与技术学院 58
? 常数因素 8是这样得到的，即每个处理
器需要对 4个邻点中的每一个发送一个
消息并从那里接收一个消息。它的加
速比因子为,
哈尔滨工业大学计算机科学与技术学院 59
? 对于 4种并行计算机，它们的加速比曲线如
图所示,
哈尔滨工业大学计算机科学与技术学院 60
? (1)第 1个系统的处理器速度为
? 50Mflop／ s，它们用 t0=550Bs以及
r∞ =1MB／ s的慢速通信网互连。此网
络速度与以太网的点对点通信相近。
? 当问题规模 N=1024时，系统 A的加速比
很差 (在图中的下方用正方块曲线表
示 ),128个处理器的加速比小于 10。
哈尔滨工业大学计算机科学与技术学院 61
? 当问题规模增至 8倍为 8K时 (图中用菱
形曲线表示 )，加速比有很大改进。
? 因为此时颗粒度 W增大了，通信 -计算
比 α 减小了。
哈尔滨工业大学计算机科学与技术学院 62
? (2)第 2个系统 (上图中用三角曲
线表示 )的处理器速度为,
?100Mflop／ s（比第一个系统快
一倍 )，它们用同样的慢速网互
连。由于这是不平衡设计，在问
题规模 N=8192时，加速比下跌。
哈尔滨工业大学计算机科学与技术学院 63
?(3)第 3个系统 (在上图中的顶部,
用圆圈曲线表示 )比系统 B更为平衡，
它的 100Mflop／ s处理器用类似于
IBM SP2的快速网互连,t0=46μ s,
r∞ =35MB／ s。它的平衡设计使得它
在 3台机器中具有最好的性能 。
哈尔滨工业大学计算机科学与技术学院 64
?3、可扩展性设计
? 该设计原理说明，在设计一个可扩展的
系统时，应该从一开始就将可扩展性作
为主要目标，而不是设计完成后再来考
虑这一问题。
? 必须为系统将来可能扩展以提供更高性
能或缩小以使价格降低或是有更大的成
本有效性作好准备。
? 可扩展性设计的两种流行方法是过度设
计和向后兼容性。
哈尔滨工业大学计算机科学与技术学院 65
? （ 1）过度设计
? 使用过度设计技术是指系统在设计时
不单纯地只是为了满足目前系统的最
低需要。
? 设计必须包括一些附加特性，以期在
未来的扩展系统中性能得到改进。这
些特性在目前系统中可能是浪费的，
但它们将会使目前系统向未来改进的
系统过渡时变得顺畅。
哈尔滨工业大学计算机科学与技术学院 66
? 例：现代处理器设计中的地址空间
? 在设计处理器时要考虑的最重要的
问题之一是它的地址空间大小，即处
理器能直接访问的字节单元数。引用
Gordon Bell的说法,
? 在体系结构设计的错误中，唯一在以
后不易改正的错误是采用小的地址空
间。
哈尔滨工业大学计算机科学与技术学院 67
?现代的处理器支持 64位地址空间，
或 2６４ =11,8x 1019B。这一巨大
的地址空间，对于仅支持 32位
(4GB)的 Unix来讲可能未被充分利
用。
?但地址空间的过度设计为操作系
统扩展为 64位 Unix时的方便过渡
创造了条件。
哈尔滨工业大学计算机科学与技术学院 68
? 示例,
? 在最初的 IBM PC中使用的处理器 —
Intel 8086／ 8088微处理器中，它
的 地址空间被限制为 20位或 1MB。
?DOS对内核和用户软件限制使用
640KB地址空间。这个 340KB的限制
给编译程序的编写人员以及应用软
件开发者带来许多烦恼。
哈尔滨工业大学计算机科学与技术学院 69
? 因为 DOS程序 (包括 Windows)不能超
过 640KB限制，软件设计者不得不创
造一些复杂技术
?(例如高位存储器、扩充存储器和扩展
存储器 )
? 以使后几代的处理器 (Intel286、
386,486,Pentium以及 PentiumPro)
能使用更大的地址空间。
哈尔滨工业大学计算机科学与技术学院 70
? 例题 IBM RS6000SMP服务器中的过度设
计
? 考虑到代的可扩展性,IBM RS6000 SMP
作了过度设计。
? 第一代的 SMP基于 PowerPC 601处理器。
? 系统的其他部分，从存储器,I/O、电源、
凤扇直到时钟电路，都设计成可容纳后
两代的处理器 PowerPC604以及 620。
哈尔滨工业大学计算机科学与技术学院 71
? 每个处理器的开关口的带宽为 600MB
／ S，大于 PC601的需要。
? 这些过度设计的特性使得在扩展为
未来一代 SMP系统时非常容易；
? 只要简单地升级处理器就可实现。
哈尔滨工业大学计算机科学与技术学院 72
?（ 2）向后兼容性
? 是说在设计硬件或软件部分时，必须兼
顾缩减系统的需求。
哈尔滨工业大学计算机科学与技术学院 73
? 例如,
? 新处理器应能执行老处理器的二进
制代码。
? 为在 n个结点上运行而设计的并行程
序，应能在单结点 (n=1)上运行，此
时可能只要求缩减的输入数据集。
哈尔滨工业大学计算机科学与技术学院 74
? 超级计算机程序应能在工作站上运
行。此外，输入数据集必须适应工
作站的有限主存容量。
? 操作系统的新版本应保留所有原来
的功能，除了那些过时的不再使用，
对此必须用文档清楚地加以说明 。
哈尔滨工业大学计算机科学与技术学院 75
?例：处理器中数据总线宽度的向
后兼容性
?现代处理器的 CPU，总线有一条
64位数据总线。某些处理器支持
向后兼容性，它们允许 64位处理
器用在含有较小数据总线宽度
(32,16或 8位 )的母板上。
哈尔滨工业大学计算机科学与技术学院 76
? 这只需对该处理器的少数控制引脚
进行设置就可做到这一点。
? 假定处理器需要两个总线周期完成
存储器的读操作 (一个周期送地址，
另一个周期从存储器读出 64位数据 )。
? 则当在一个 8位母板上进行读操作时，
处理器的设置将自动地在 9个总线周
期内从存储器读出 64位数据。
哈尔滨工业大学计算机科学与技术学院 77
? 例 IBM SP系统中的并行操作环境
? IBM并行操作环境 (POE)最初是为 IBM
可扩展并行计算机 (SPl和 SP2)设计的。
? 环境中，用户的应用程序在多个 SP结
点上执行。 POE支持的向后兼容性如
下,
? POE完全可在一个结点上执行，因此它
允许多个用户任务在一个结点上运行。
? 该结点不必非是一个 SP结点，它可以是
任何 RS6000工作站。
? POE是在 IBMUnix(AIX)上实现的，因此
已有的 Unix程序可在 POE中运行。
哈尔滨工业大学计算机科学与技术学院 78
? 说明,
? 向后兼容性并不表示一个旧系统的所
有特性都应保留。
? 应该剔除陈旧的特性。
? 在应用过度设计技术时，应考虑成本
问题且不应对未来期待过多，虽然有
时过度设计确实能减少总的开发和生
产成本。
哈尔滨工业大学计算机科学与技术学院 79
? 例题,Intel 486DX和 486SX
? 当 Intel推出 80486微处理器芯片时，
共有两种模型,
? 486DX和 486SX。
? 两种芯片在内部是完全一样的。两者
唯一差别是,
? 在 SX芯片上，浮点部件 (FPU)不能用；
? DX芯片有浮点部件 (FPU) 。
