哈尔滨工业大学计算机科学与技术学院 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
二、可扩展设计原理
?包括,
?独立原理
?平衡设计原理
?可扩展性设计原理
?时延隐藏原理 (第 5章介绍）
哈尔滨工业大学计算机科学与技术学院 28
1,独立原理
（ 1）定义,
? 应努力使系统中的各个组成部分（硬、
软件）相互独立。
? 如果无法达到完全独立，则应尽力使
相关程度 减至最小并使相关性尽量清
晰。
哈尔滨工业大学计算机科学与技术学院 29
（ 2）采用独立原理的优点,
? 使独立扩展成为可能；
? 使异构可扩展性成为可能；
? 要求部件不受制于一个特别的体系结
构或系统。
哈尔滨工业大学计算机科学与技术学院 30
（ 3）独立系统的特点,
?有一个开放的体系结构，有一个与
系统其他部分衔接的标准接口；
?是市售产品，若不具有版权则更好；
?有多家供应商，在公开市场大批量
供应；
?相对成熟，已为许多人使用相当长
时间，且已完成必要的排错。
哈尔滨工业大学计算机科学与技术学院 31
（ 4）独立原理涉及的范围,
?算法应独立于体系结构。
?应用应独立于平台。
?程序设计语言应独立于机器。
?语言应模块化且具有独立性。
?结点应独立于网络，而网络接口应
独立于网络拓扑。
哈尔滨工业大学计算机科学与技术学院 32
? 例题 1，开发 Internet和 IBMSP2中所
体现的独立精神
?Internet的成功是表现独立原理优点
的完美例子。 Internet独立于主机、
互连硬件和应用软件。由不同供应商
提供的，从 PC机到超级计算机的不同
类型主机相互连接起来。
? 互连硬件可以是以太网,FDDI等。
? 用户能用不同软件浏览 Web万维网 。
哈尔滨工业大学计算机科学与技术学院 33
? 例题 2,IBM SP2设计结合了独立原理
? 设计的结点体系结构允许使用不同的
通信体系结构 (例如以太网或 HPS)。
? 通信协议独立于通信硬件：如以太网
或 HPS，都允许使用标准 IP协议或 IBM
专用用户空间协议。
哈尔滨工业大学计算机科学与技术学院 34
? 例题 3,MPI及超立方体计算机
? 消息传递接口 (MPl)是使用少量独立
(正交 )语言特征的成功范例。
?MPI基于 4个相互正交的主要概念,
?数据类型
?通信操作
?通信子
?虚拟拓扑
? 4者的任何组合均是有效的。
哈尔滨工业大学计算机科学与技术学院 35
? 为较早期的超立方体计算机而开发的
许多并行算法显式地使用超立方体的
互连拓扑，但在网络连接系统中，它
们并不适用。
? 现在的 MPP使用独立于互连拓扑的通
信算法。
?IBM SP系统中的集合通信库便是一个
很好的例子。
哈尔滨工业大学计算机科学与技术学院 36
（ 5 ）实现独立原理的两种通用技术,
?将体系结构和实现分开
?使用标准组件
哈尔滨工业大学计算机科学与技术学院 37
?体系结构和实现的分开
?体系结构是系统组件的公共行为
或是功能性精确模型；
?实现是对模型的具体实施；
?用户和设计者均可使用体系结构
模型。
?一个体系结构可有许多不同实现，
它们会有不同性能，但实现相同
功能。
哈尔滨工业大学计算机科学与技术学院 38
?开放体系结构,
?体系结构的拥有者允许用户或第 3
方了解体系结构；
?用户可自己制造与体系结构兼容的
组件，甚至修改或重新加以设计；
?IBM PC机证实了这的确是一个技术
上有影响的、商业上可行的。
哈尔滨工业大学计算机科学与技术学院 39
?使用标准组件
?有两种标准类型,
?工业标准 (也称为事实标准 )，它通
常为某公司所倡导，然后被最终用
户广泛使用并为工业界的大多数所
接受。
?由国家或国际标准机构所设立的标
准，如国际标准组织 (ISO)，美国国
家标准机构 (ANSl)以及 IEEE标准委
员会。
哈尔滨工业大学计算机科学与技术学院 40
（ 6）在使用独立原理时应注意,
?并行计算机中通常有某种关键组件
和技术 是先进的,但往往还 不是标
准 。
?不可能靠简单地单纯扩展一个或少
数几个组件建成一个有效的系统。
?必须在所有 独立的 子系统设计之间
达到 平衡 。
哈尔滨工业大学计算机科学与技术学院 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
?它的加速比因子为,
哈尔滨工业大学计算机科学与技术学院 59
? 对于 4种并行计算机，它们的加速比曲线如
图所示,
哈尔滨工业大学计算机科学与技术学院 60
? 第 1个系统的处理器速度为,
? 50Mflop／ s，它们用 t0=550Bs以及
r∞ =1MB／ s的慢速通信网互连。此网
络速度与以太网的点对点通信相近。
? 当问题规模 N=1024时，系统 A的加速比
很差 (在图中的下方用正方块曲线表
示 ),128个处理器的加速比小于 10。
哈尔滨工业大学计算机科学与技术学院 61
? 当问题规模增至 8倍为 8K时 (图中用菱
形曲线表示 )，加速比有很大改进。
? 此时颗粒度 W增大了，通信 -计算比 α
减小了 。
哈尔滨工业大学计算机科学与技术学院 62
?第 2个系统 (上图中用三角曲线表
示 )的处理器速度为,
?100Mflop／ s（比第一个系统快一
倍 )，它们用同样的慢速网互连。由
于这是不平衡设计，在问题规模
N=8192时，加速比下跌。
哈尔滨工业大学计算机科学与技术学院 63
?第 3个系统
? 在图中的顶部，用圆圈曲线表示；
? 比系统 B更为平衡，它的 100Mflop／ s
处理器用类似于 IBM SP2的快速网互
连,t0=46μ s,r∞ =35MB／ s。
? 它的平衡设计使得它在 3台机器中具
有最好的性能。
哈尔滨工业大学计算机科学与技术学院 64
3、可扩展性设计
? 在设计一个可扩展的系统时，应该从
一开始就将可扩展性作为主要目标，
而不是设计完成后再来考虑这一问题。
? 必须为系统将来可能扩展以提供更高
性能或缩小以使价格降低或是有更大
的成本有效性作好准备。
? 可扩展性设计的两种流行方法,
?过度设计；
?向后兼容性。
哈尔滨工业大学计算机科学与技术学院 65
?（ 1）过度设计
? 使用过度设计技术是指系统在设计时
不单纯地只是为了满足目前系统的最
低需要。
? 设计必须包括一些附加特性,以期 在
未来的扩展系统中性能得到改进。
哈尔滨工业大学计算机科学与技术学院 66
? 例 1：现代处理器设计中的地址空间
? 在设计处理器时要考虑的最重要的问
题之一是它的地址空间大小，即处理
器能直接访问的字节单元数。
?引用 Gordon Bell的说法,
?在体系结构设计的错误中，唯一在
以后不易改正的错误是采用小的地
址空间。
哈尔滨工业大学计算机科学与技术学院 67
?现代的处理器支持 64位地址空间，
或 2６４ =11,8x1019B。这一巨大的
地址空间，对于仅支持 32位 (4GB)
Unix来讲可能未被充分利用。
?地址空间的过度设计为操作系统
扩展为 64位 Unix时的方便过渡创
造了条件。
哈尔滨工业大学计算机科学与技术学院 68
? 例题 2,
? 在最初的 IBM PC中使用的处理器 —
Intel 8086／ 8088微处理器中，它
的 地址空间被限制为 20位或 1MB。
?DOS对内核和用户软件限制使用
640KB地址空间。这个限制给编译程
序的编写人员以及应用软件开发者
带来许多烦恼。
哈尔滨工业大学计算机科学与技术学院 69
? 因为 DOS程序 (包括 Windows)不能超
过 640KB限制，软件设计者不得不创
造一些复杂技术
?(例如高位存储器、扩充存储器和扩展
存储器 )
? 以使后几代的处理器 (Intel286、
386,486,Pentium以及 PentiumPro)
能使用更大的地址空间。
哈尔滨工业大学计算机科学与技术学院 70
? 例题 3 IBM RS6000SMP服务器中的过
度设计
? 考虑到代的可扩展性,IBM RS6000 SMP作
了过度设计。
? 第一代的 SMP基于 PowerPC 601处理器。
? 系统的其他部分，从存储器,I/O、电源、
风扇直到时钟电路，都设计成可容纳后两
代的处理器 PowerPC604以及 620。
哈尔滨工业大学计算机科学与技术学院 71
? 每个处理器的开关口的带宽为 600MB
／ S，大于 PC601的需要。
? 这些过度设计的特性使得在扩展为
未来一代 SMP系统时非常容易；
? 只要简单地升级处理器就可实现。
哈尔滨工业大学计算机科学与技术学院 72
?（ 2）向后兼容性
? 在设计硬件或软件部分时，必须兼顾缩
减系统的需求。
哈尔滨工业大学计算机科学与技术学院 73
? 例题 1,
? 新处理器应能执行老处理器的二进
制代码。
? 为在 n个结点上运行而设计的并行程
序，应能在单结点 (n=1)上运行，此
时可能只要求缩减的输入数据集。
哈尔滨工业大学计算机科学与技术学院 74
? 超级计算机程序应能在工作站上运
行。此外，输入数据集必须适应工
作站的有限主存容量。
? 操作系统的新版本应保留所有原来
的功能，除了那些过时的不再使用，
对此必须用文档清楚地加以说明 。
哈尔滨工业大学计算机科学与技术学院 75
?例 题 2：处理器中数据总线宽度
的向后兼容性
? 现代处理器的 CPU，总线有一条 64位
数据总线。某些处理器支持向后兼
容性，它们允许 64位处理器用在含
有较小数据总线宽度 (32,16或 8位 )
的母板上 。
哈尔滨工业大学计算机科学与技术学院 76
? 这只需对该处理器的少数控制引脚
进行设置就可做到这一点。
? 假定处理器需要两个总线周期完成
存储器的读操作 (一个周期送地址，
另一个周期从存储器读出 64位数据 )。
? 则当在一个 8位母板上进行读操作时，
处理器的设置将自动地在 9个总线周
期内从存储器读出 64位数据。
哈尔滨工业大学计算机科学与技术学院 77
? 例题 3,IBM SP系统中的并行操作环境
? IBM并行操作环境 (POE)最初是为 IBM可扩
展并行计算机 (SPl和 SP2)设计的。
? 环境中，用户的应用程序在多个 SP结点上
执行。 POE支持的向后兼容性如下,
? POE完全可在一个结点上执行，因此它允许多
个用户任务在一个结点上运行。
? 该结点不必非是一个 SP结点，它可以是任何
RS6000工作站。
? POE是在 IBMUnix(AIX)上实现的，因此已有的
Unix程序可在 POE中运行。
哈尔滨工业大学计算机科学与技术学院 78
? 说明,
? 向后兼容性并不表示一个旧系统的所
有特性都应保留。
? 应该剔除陈旧的特性。
? 在应用过度设计技术时，应考虑成本
问题且不应对未来期待过多，虽然有
时过度设计确实能减少总的开发和生
产成本。
哈尔滨工业大学计算机科学与技术学院 79
?例题 4,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
二、可扩展设计原理
?包括,
?独立原理
?平衡设计原理
?可扩展性设计原理
?时延隐藏原理 (第 5章介绍）
哈尔滨工业大学计算机科学与技术学院 28
1,独立原理
（ 1）定义,
? 应努力使系统中的各个组成部分（硬、
软件）相互独立。
? 如果无法达到完全独立，则应尽力使
相关程度 减至最小并使相关性尽量清
晰。
哈尔滨工业大学计算机科学与技术学院 29
（ 2）采用独立原理的优点,
? 使独立扩展成为可能；
? 使异构可扩展性成为可能；
? 要求部件不受制于一个特别的体系结
构或系统。
哈尔滨工业大学计算机科学与技术学院 30
（ 3）独立系统的特点,
?有一个开放的体系结构，有一个与
系统其他部分衔接的标准接口；
?是市售产品，若不具有版权则更好；
?有多家供应商，在公开市场大批量
供应；
?相对成熟，已为许多人使用相当长
时间，且已完成必要的排错。
哈尔滨工业大学计算机科学与技术学院 31
（ 4）独立原理涉及的范围,
?算法应独立于体系结构。
?应用应独立于平台。
?程序设计语言应独立于机器。
?语言应模块化且具有独立性。
?结点应独立于网络，而网络接口应
独立于网络拓扑。
哈尔滨工业大学计算机科学与技术学院 32
? 例题 1，开发 Internet和 IBMSP2中所
体现的独立精神
?Internet的成功是表现独立原理优点
的完美例子。 Internet独立于主机、
互连硬件和应用软件。由不同供应商
提供的，从 PC机到超级计算机的不同
类型主机相互连接起来。
? 互连硬件可以是以太网,FDDI等。
? 用户能用不同软件浏览 Web万维网 。
哈尔滨工业大学计算机科学与技术学院 33
? 例题 2,IBM SP2设计结合了独立原理
? 设计的结点体系结构允许使用不同的
通信体系结构 (例如以太网或 HPS)。
? 通信协议独立于通信硬件：如以太网
或 HPS，都允许使用标准 IP协议或 IBM
专用用户空间协议。
哈尔滨工业大学计算机科学与技术学院 34
? 例题 3,MPI及超立方体计算机
? 消息传递接口 (MPl)是使用少量独立
(正交 )语言特征的成功范例。
?MPI基于 4个相互正交的主要概念,
?数据类型
?通信操作
?通信子
?虚拟拓扑
? 4者的任何组合均是有效的。
哈尔滨工业大学计算机科学与技术学院 35
? 为较早期的超立方体计算机而开发的
许多并行算法显式地使用超立方体的
互连拓扑，但在网络连接系统中，它
们并不适用。
? 现在的 MPP使用独立于互连拓扑的通
信算法。
?IBM SP系统中的集合通信库便是一个
很好的例子。
哈尔滨工业大学计算机科学与技术学院 36
（ 5 ）实现独立原理的两种通用技术,
?将体系结构和实现分开
?使用标准组件
哈尔滨工业大学计算机科学与技术学院 37
?体系结构和实现的分开
?体系结构是系统组件的公共行为
或是功能性精确模型；
?实现是对模型的具体实施；
?用户和设计者均可使用体系结构
模型。
?一个体系结构可有许多不同实现，
它们会有不同性能，但实现相同
功能。
哈尔滨工业大学计算机科学与技术学院 38
?开放体系结构,
?体系结构的拥有者允许用户或第 3
方了解体系结构；
?用户可自己制造与体系结构兼容的
组件，甚至修改或重新加以设计；
?IBM PC机证实了这的确是一个技术
上有影响的、商业上可行的。
哈尔滨工业大学计算机科学与技术学院 39
?使用标准组件
?有两种标准类型,
?工业标准 (也称为事实标准 )，它通
常为某公司所倡导，然后被最终用
户广泛使用并为工业界的大多数所
接受。
?由国家或国际标准机构所设立的标
准，如国际标准组织 (ISO)，美国国
家标准机构 (ANSl)以及 IEEE标准委
员会。
哈尔滨工业大学计算机科学与技术学院 40
（ 6）在使用独立原理时应注意,
?并行计算机中通常有某种关键组件
和技术 是先进的,但往往还 不是标
准 。
?不可能靠简单地单纯扩展一个或少
数几个组件建成一个有效的系统。
?必须在所有 独立的 子系统设计之间
达到 平衡 。
哈尔滨工业大学计算机科学与技术学院 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
?它的加速比因子为,
哈尔滨工业大学计算机科学与技术学院 59
? 对于 4种并行计算机，它们的加速比曲线如
图所示,
哈尔滨工业大学计算机科学与技术学院 60
? 第 1个系统的处理器速度为,
? 50Mflop／ s，它们用 t0=550Bs以及
r∞ =1MB／ s的慢速通信网互连。此网
络速度与以太网的点对点通信相近。
? 当问题规模 N=1024时，系统 A的加速比
很差 (在图中的下方用正方块曲线表
示 ),128个处理器的加速比小于 10。
哈尔滨工业大学计算机科学与技术学院 61
? 当问题规模增至 8倍为 8K时 (图中用菱
形曲线表示 )，加速比有很大改进。
? 此时颗粒度 W增大了，通信 -计算比 α
减小了 。
哈尔滨工业大学计算机科学与技术学院 62
?第 2个系统 (上图中用三角曲线表
示 )的处理器速度为,
?100Mflop／ s（比第一个系统快一
倍 )，它们用同样的慢速网互连。由
于这是不平衡设计，在问题规模
N=8192时，加速比下跌。
哈尔滨工业大学计算机科学与技术学院 63
?第 3个系统
? 在图中的顶部，用圆圈曲线表示；
? 比系统 B更为平衡，它的 100Mflop／ s
处理器用类似于 IBM SP2的快速网互
连,t0=46μ s,r∞ =35MB／ s。
? 它的平衡设计使得它在 3台机器中具
有最好的性能。
哈尔滨工业大学计算机科学与技术学院 64
3、可扩展性设计
? 在设计一个可扩展的系统时，应该从
一开始就将可扩展性作为主要目标，
而不是设计完成后再来考虑这一问题。
? 必须为系统将来可能扩展以提供更高
性能或缩小以使价格降低或是有更大
的成本有效性作好准备。
? 可扩展性设计的两种流行方法,
?过度设计；
?向后兼容性。
哈尔滨工业大学计算机科学与技术学院 65
?（ 1）过度设计
? 使用过度设计技术是指系统在设计时
不单纯地只是为了满足目前系统的最
低需要。
? 设计必须包括一些附加特性,以期 在
未来的扩展系统中性能得到改进。
哈尔滨工业大学计算机科学与技术学院 66
? 例 1：现代处理器设计中的地址空间
? 在设计处理器时要考虑的最重要的问
题之一是它的地址空间大小，即处理
器能直接访问的字节单元数。
?引用 Gordon Bell的说法,
?在体系结构设计的错误中，唯一在
以后不易改正的错误是采用小的地
址空间。
哈尔滨工业大学计算机科学与技术学院 67
?现代的处理器支持 64位地址空间，
或 2６４ =11,8x1019B。这一巨大的
地址空间，对于仅支持 32位 (4GB)
Unix来讲可能未被充分利用。
?地址空间的过度设计为操作系统
扩展为 64位 Unix时的方便过渡创
造了条件。
哈尔滨工业大学计算机科学与技术学院 68
? 例题 2,
? 在最初的 IBM PC中使用的处理器 —
Intel 8086／ 8088微处理器中，它
的 地址空间被限制为 20位或 1MB。
?DOS对内核和用户软件限制使用
640KB地址空间。这个限制给编译程
序的编写人员以及应用软件开发者
带来许多烦恼。
哈尔滨工业大学计算机科学与技术学院 69
? 因为 DOS程序 (包括 Windows)不能超
过 640KB限制，软件设计者不得不创
造一些复杂技术
?(例如高位存储器、扩充存储器和扩展
存储器 )
? 以使后几代的处理器 (Intel286、
386,486,Pentium以及 PentiumPro)
能使用更大的地址空间。
哈尔滨工业大学计算机科学与技术学院 70
? 例题 3 IBM RS6000SMP服务器中的过
度设计
? 考虑到代的可扩展性,IBM RS6000 SMP作
了过度设计。
? 第一代的 SMP基于 PowerPC 601处理器。
? 系统的其他部分，从存储器,I/O、电源、
风扇直到时钟电路，都设计成可容纳后两
代的处理器 PowerPC604以及 620。
哈尔滨工业大学计算机科学与技术学院 71
? 每个处理器的开关口的带宽为 600MB
／ S，大于 PC601的需要。
? 这些过度设计的特性使得在扩展为
未来一代 SMP系统时非常容易；
? 只要简单地升级处理器就可实现。
哈尔滨工业大学计算机科学与技术学院 72
?（ 2）向后兼容性
? 在设计硬件或软件部分时，必须兼顾缩
减系统的需求。
哈尔滨工业大学计算机科学与技术学院 73
? 例题 1,
? 新处理器应能执行老处理器的二进
制代码。
? 为在 n个结点上运行而设计的并行程
序，应能在单结点 (n=1)上运行，此
时可能只要求缩减的输入数据集。
哈尔滨工业大学计算机科学与技术学院 74
? 超级计算机程序应能在工作站上运
行。此外，输入数据集必须适应工
作站的有限主存容量。
? 操作系统的新版本应保留所有原来
的功能，除了那些过时的不再使用，
对此必须用文档清楚地加以说明 。
哈尔滨工业大学计算机科学与技术学院 75
?例 题 2：处理器中数据总线宽度
的向后兼容性
? 现代处理器的 CPU，总线有一条 64位
数据总线。某些处理器支持向后兼
容性，它们允许 64位处理器用在含
有较小数据总线宽度 (32,16或 8位 )
的母板上 。
哈尔滨工业大学计算机科学与技术学院 76
? 这只需对该处理器的少数控制引脚
进行设置就可做到这一点。
? 假定处理器需要两个总线周期完成
存储器的读操作 (一个周期送地址，
另一个周期从存储器读出 64位数据 )。
? 则当在一个 8位母板上进行读操作时，
处理器的设置将自动地在 9个总线周
期内从存储器读出 64位数据。
哈尔滨工业大学计算机科学与技术学院 77
? 例题 3,IBM SP系统中的并行操作环境
? IBM并行操作环境 (POE)最初是为 IBM可扩
展并行计算机 (SPl和 SP2)设计的。
? 环境中，用户的应用程序在多个 SP结点上
执行。 POE支持的向后兼容性如下,
? POE完全可在一个结点上执行，因此它允许多
个用户任务在一个结点上运行。
? 该结点不必非是一个 SP结点，它可以是任何
RS6000工作站。
? POE是在 IBMUnix(AIX)上实现的，因此已有的
Unix程序可在 POE中运行。
哈尔滨工业大学计算机科学与技术学院 78
? 说明,
? 向后兼容性并不表示一个旧系统的所
有特性都应保留。
? 应该剔除陈旧的特性。
? 在应用过度设计技术时，应考虑成本
问题且不应对未来期待过多，虽然有
时过度设计确实能减少总的开发和生
产成本。
哈尔滨工业大学计算机科学与技术学院 79
?例题 4,Intel 486DX和 486SX
? 当 Intel推出 80486微处理器芯片时，共
有两种模型,
?486DX和 486SX。
? 两种芯片在内部是完全一样的。两者唯
一差别是,
?在 SX芯片上，浮点部件 (FPU)不能用；
?DX芯片有浮点部件 (FPU) 。
