节讲义月日PPT课件

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