《计算机系统结构》PPT课件.ppt

《《计算机系统结构》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《计算机系统结构》PPT课件.ppt（111页珍藏版）》请在三一办公上搜索。

1、计算机系统结构,主讲 蔡启先,第8章 多处理器系统,8.1 指令级并行性的限制和超线程技术,8.2 多处理器构成的系统结构,第8 章 多处理器系统,8.3 多处理器的Cache一致性,8.5 集群系统,8.4 多处理器系统的同步机制,8.6 多处理器系统的程序并行性,8.7 曙光5000超级计算机,第8章 多处理机系统Chapter 8 Multiprocessers,8.1 指令级并行性的限制和超线程技术 8.2 多处理器构成的系统结构 8.3 多处理器的Cache一致性8.4 多处理器系统的同步机制 8.5 集群系统 8.6 多处理器系统的程序并行性 8.7 曙光5000超级计算机本章小结

2、,8.1指令级并行性的限制和超线程技术,指令级并行性的限制 超线程技术 限制单处理器发展的其它主要因素,8.1.1 指令级并行性的限制,1.理想处理器 2.理想处理器难以接近（1）转移预测、重命名和相关性分析上依靠静态的编译分析是不可能完美的，动态分析受窗口局限（2）错误的预测限制了指令的并行度（3）寄存器的数目有限（4）此外，每时钟周期发射指令数量、功能单元及单元延迟、寄存器文件端口、功能单元队列、对转移发射的限制、对存储器并行访问的限制以及对指令提交的限制等都是影响指令级并行的因素。,8.1.2 超线程（Hyper-Threading）技术,超线程技术是指在单处理器中采用的线程级并行技术，

3、又称简单多线程技术。超线程有两种主要方法：细粒度超线程和粗粒度超线程。同时多线程（SMT）是超线程的一个改进版本，它使用多发射和动态调度机制在开发线程级并行的同时开发指令级并行。,8.1.3 限制单处理器发展的其它主要因素,尽管单处理器在提高指令集并行及采用超线程并行技术方面做出了很大努力，但在如下几个方面受到局限：（1）指令级并行约束及超线程技术的限制已经不太可能提高更多的并行性。（2）仅靠提高频率的办法，难以实现性能的突破。反而带来功耗和内存、I/O速度平衡的问题。（3）不断增加的单核芯片面积提高了生产成本，并且使得设计和验证所花费的时间变得更长。（4）功耗与性能比问题日渐突出。,多核处理

4、器结构 多处理器结构 多处理器并行处理定量分析和所遇到的问题,8.2 多处理器构成的系统结构,多核处理器是指在一个芯片上集成多个处理器核心，即CMP(Chip Multiprocessor，CMP单芯片多处理器)。这多个核心间联系非常紧密，甚至共享L1、L2和L3 Cache等。CMP通常可分为同构CMP和异构CMP 在存储层次上，CMP结构的互连采用共享二级或三级Cache的CMP结构，每个处理器核心拥有私有的一级或二级Cache，且所有处理器核心共享下一级 Cache。核间通信机制目前有两种，一种基于总线共享的Cache结构，一种基于片上的互连结构。,8.2.1 多核处理器结构,CMP在实

5、际使用中具有如下优点：（1）微处理器厂商一般采用现有的成熟单核处理器作为处理器核心，从而可缩短设计和验证周期，节省研发成本。（2）控制逻辑简单,扩展性好,易于实现。（3）通过动态调节电压/频率、负载优化分布等，可有效降低CMP功耗。（4）CMP采用共享Cache或者内存的方式，多线程的通信延迟较低。,8.2.1 多核处理器结构,这种结构的特性是：（1）结构中的每个处理器取自己的指令并对自己的数据进行操作，即每个处理器执行自己的指令流，很容易实现多线程并行机制。（2）MIMD灵活性强；（3）MIMD结构中的众多处理器可以由同一种处理器来组成,8.2.2 多处理器结构,8.2.2.1 MIMD计算

6、机概述,按照多处理器组成的规模，多处理器大致可分为4个层次。（1）多核处理器（2）中小规模多处理器（3）大规模多处理器（4）集群 商业集群和客户集群,8.2.2.1 MIMD计算机概述,两种典型的结构：集中式共享存储器系统结构和分布式存储器系统结构。1集中式共享存储器系统,8.2.2.2 MIMD计算机的基本结构,集中式共享存储器多处理器系统的优点是：（1）可以与传统的单处理器系统软件兼容。（2）程序设计容易。（3）通信开销小。集中式共享存储器的结构组成的处理器不能太多，主要受到访存冲突和互联网络的带宽和复杂性的限制,2分布式存储器多处理器系统,分布式存储器的主要优点是：如果大部分访存是对节点

7、内的本地存储器进行的，这样做是增大存储器带宽的比较经济的方法；缩短了本地存储器访问的时延。具有较好的扩展性。主要缺点是由于处理器不再共享单一集中存储器，处理器间的数据通信在某种程度上变得更加复杂，且时延也更大。,分布式存储器有两种进行处理器之间通信的方式。一种是分布式共享存储器（Distributed Shared-Memory，简称DSM）系统，它将物理上分开的存储器在逻辑上统一为一个地址空间，通过load和store操作在统一的地址空间上隐式地传递数据。另一种是各个处理器都有自己的私有地址空间，它们在逻辑上分散，相互独立。数据通信往往通过显式地在处理器之间传递消息来完成。,Gustafso

8、n定律:扩展加速比=N+(1-N)*S其中，N表示处理器的数量，S表示程序中串行部分的比例。虽然多处理器有利于程序级、进程级乃至线程级的并行处理，但存在着两个问题是并行开发所要面对的。一是程序可获得的并行度是有限的。二是执行模块之间的通信开销。这限制了多处理器系统的性价比的提高。要解决这两个问题，一是在软件中采用更好的并行算法来提高并行度。二是改进系统结构，如在硬件上缓存共享数据，在确保存储器一致性的前提下，如何使用Cache来减少远程访问频率。三是在软件上重新构造数据来尽可能增加本地访问。此外，还可以使用多线程或预取技术来减少时延的影响。,8.2.3 多处理器并行处理定量分析和所遇到的问题,

9、8.3 多处理器的Cache一致性,对称式共享存储器系统和多处理器的Cache一致性 分布式共享存储器系统和基于目录的Cache一致性,8.3.1 对称式共享存储器系统和多处理器的Cache一致性,对称式共享存储器系统 多处理器的Cache一致性 监听式协议实现多处理器的Cache一致性,8.3.1.1 对称式共享存储器系统,8.3.1.1 对称式共享存储器系统,对称式共享存储器系统支持共享和私有数据的缓存，私有数据被单个处理器使用，而共享数据则被多个处理器使用，基本上是通过读写共享数据完成处理器之间的通信。把一个私有数据缓存之后，支该数据的访问就可以在Cache中形成副本，这样做除了会减少访

10、问时延和降低对存储器带宽的要求外，还能减少多个处理器同时读取共享数据时的竞争现象。然而，把共享数据放入Cache又出现了一个新的问题：Cache一致性。,8.3.1.2 多处理器的Cache一致性,所谓多处理器的Cache一致性问题，是指由于缓存共享数据，两个不同的处理器所保存的存储器视图可能是通过各自的Cache得到的。因此，如果没有其它的防范措施，则会导致两个处理器分别得到两个不同的值。解决多处理器的Cache一致性问题的方法有软件方法、总线监听法和目录表法。,8.3.1.2 多处理器的Cache一致性,软件方法主要依靠编译程序进行分析，同时需要硬件机制的配合，使共享信息安排在主存中，而避

11、免将它们存放到Cache中。这需要一种机制，使软件能够对数据进行标记，并按时序进行调度。另外对于具有良好结构的循环级并行程序，且在循环中需要显式地复制数据，使用软件方法有可能大大降低访存开销。软件方法的优点是不需要硬件提供很多支持，减少了硬件的复杂性，降低了对互连网络通信量的要求。其局限性在于编译器进行一致性处理的能力是很有限的，并且只能用于共享存储器的系统。,8.3.1.3 监听式协议实现多处理器的Cache一致性,监听式协议对于采用总线互连共享主存的多处理器系统，可利用总线的播送来实现。它让各个处理器上的Cache控制器对总线进行监视或监听，来确定它们是否含有总线或交换机上请求的数据块的副

12、本，从而跟踪共享数据，以保证Cache一致性。监听式协议使用硬件解决办法。有两种方法可以实现监听式协议：写无效协议和写更新或写广播协议。,8.3.2 分布式共享存储器系统和基于目录的Cache一致性,各个节点带有目录的分布式存储器多处理器系统所谓目录式协议，是指把物理存储器的共享状态存放在一个地点，称之为目录。目录表中每项保存了每个Cache数据块的使用情况。为了防止访问目录表成为瓶颈，需要使目录随存储器分布。,各个节点带有目录的分布式存储器多处理器系统,一般目录表中记录的Cache数据块的状态主要有：共享：该Cache数据块具有正确的副本。未缓存：没有任何一个处理器含有该数据块的副本。修改：

13、只有一个处理器拥有该Cache数据块的正确副本并且对该块执行过写操作，因此其它存储器中与之对应的副本是无效的。这个处理器成为该块的所有者。无效：由于某个处理器执行写操作，使得本处理器含有该数据块的副本被标记为无效状态。,目录表的具体作法可分为3种。（1）全映象目录表法。（2）有限目录表法。（3）链式目录表法。目录式协议的实现要占据一些存储空间，比监听式协议的开销略微偏高，但是可以用来扩展更多的处理器，很适合于分布式共享存储器系统。监听式协议要求处理器在修改数据块时向所有处理器广播Cache缺失的信息，这种方法实现简单，但也限制了其扩展性。,8.4 多处理器系统的同步机制,基本硬件原语8.4.2

14、 同步机制的实现 多线程同步机制带来的问题,8.4.1 基本硬件原语,实现多处理器系统同步的关键是要有一个能够以原子方式对存储器执行读写操作的硬件原语集合。硬件原语可有多种不同的形式，但都必须支持原子方式的读写操作，并能够返回操作是否成功的信息。这些硬件原语是构造多种不同的用户层同步操作的基本构件，比如锁和屏障等。一般来说，硬件原语对应用程序员是透明的，而是由系统程序员用这些硬件原语构建一个同步库来支持线程的同步机制。,基本的硬件原语,（1）原子互换。典型的构建同步原语的操作，它将一个寄存器中的值与一个存储器中的值进行互换。用这种原语可建立基本的同步机制。例如可建立一个简单的锁（一个共享的变量

15、），其中0表示锁是打开的，1表示锁是关闭的。如果某个处理器要访问存储器，可通过将寄存器中的1与存储器中的锁的值交换，若返回值为1，表明有其它处理器占用了该锁，不能访问；若返回值为0，表明无其它处理器占用，并已被该处理器占用，且此时存储器锁值为1，在这个处理器将锁释放之前，其它处理器无法占用。如果有两个处理器试图同时进行这种互换，这就发生了竞争。此时，只能有一个处理器首先执行互换并得到返回值0，而另一个处理器执行互换时得到返回值1。应用互换原语实现同步的关键是这种操作具有原子性：互换是不可分割的，两个同时进行的互换操作将被排序进行，不可能进行这种互换时都返回0值。,基本的硬件原语,（2）测试并置

16、位（test-and-set）。这是许多早期的多处理器系统采用的同步操作。它先对一个数值进行测试，若该数值通过了检测则执行设置。例如在测试数值为0时将其设置为1，这与前述原子互换类似。（3）读取并加1（fetch-and-increment）。它返回存储器中的值并以原子操作的方式使存储器中的值加1。若用0表示同步变量未被占用，则可以像使用原子互换一样得到类似的结果。当然，这类操作还有其它用途。,基本的硬件原语,（4）读取并更新（fetch-and-update）。这是一种新型的同步原子操作，可以包含上述同步原语的功能。这一对指令包括一条专门的装载指令，称为链接装载（load linked）或上

17、锁装载（load locked）即LL指令；还包括一条称为条件存储（store condition）即SC指令。LL指令和SC指令按顺序执行。如果LL指令指定的存储单元的地址值在对应的SC指令执行之前被改变了，则条件存储失败。如果处理器在这两条指令之间作了线程切换，则条件存储也失败。SC指令返回一个数值，成功返回1，失败返回0。这是一种非阻塞机制，它不采用锁的操作，不会导致其它线程的阻塞，可以避免死锁的发生。,8.4.2 同步机制的实现,用一致性机制实现锁 屏障同步的实现 事务存储器,8.4.2.1 用一致性机制实现锁,基于原子操作，就可以利用多处理器的一致性来实现自旋锁（spin lock）

18、。自旋锁是指处理器通过循环的方法来不断尝试取得的锁。自旋锁适用于对锁的占用时间很短并且上锁时间很快的情况。下面的代码实现原子互换来锁定R1指定的自旋锁：ADDIR2,R0,#1;让R2=0lockit:EXCHR2,0(R1);互换，将0写 入锁变量 BNEZR2,lockit;若未锁定继续尝试,虽然自旋锁的方案简单，但互斥的锁操作会带来较大的通信流量，对拥有较多数目的处理器系统来说会带来困难。一种解决办法是将锁的竞争分散到多个锁上，避免频繁进行Cache块的更新。还有采用链接装载和条件存储机制来实现非阻塞自旋锁等。,8.4.2.2 屏障同步的实现,屏障（Barrier）是一种同步操作，它要求

19、各线程等待，直到所有线程都到达屏障。屏障同步函数需要对到达的线程数量进行计数，线程计数器是一个共享变量。下面程序可实现屏障同步函数：lock(counterlock);/上锁，计数器锁的更新保护是原子的if(count=0)release=0;/首次到达的线程复位release标志count=count+1;/对到达的线程计数unlock(counterlock);/解锁if(count=total)/若计数值达到必须到达屏障同步函数的线程数count=0;/则复位计数器release=1;/release为1表示所有线程已到达屏障elsespin(release=1);/否则继续等待，直到所

20、有线程到达屏障,8.4.2.2 屏障同步的实现,在大量处理器构成的系统中，可使用组合树的数据结构来实现屏障同步机制。这种方式将锁资源的竞争分解成层次化的树型结构的竞争。,8.4.2.3 事务存储器,事务存储器（transaction memory）是一种解决多线程同步和互斥问题、协调多线程对同一个存储器的访问方式的硬件技术，是一种非互锁的机制，能使系统并行地执行原子操作。这里事务被定义为锁的作用范围。每个事物由一个线程试探性地执行而不请求锁。如果事务执行顺利，它将提交无需其它动作；如果事务执行中检测到冲突，该事物则整体放弃，方法是进行事物的回滚（roll back）并重新开始，直至事务成功提交

21、。在事务没有成功提交之前，其操作结果不会对其它线程产生影响。事务执行由线程中的一组指令构成，它具有串行性、分离性、原子性和一致性。事务存储器必须实现存储器的分离机制、冲突检测机制、原子提交机制和回滚机制。,8.4.2.3 事务存储器,硬件事务存储器实际上将事务的访存限制在本地Cache中，所修改的数据在提交时才被写回共享存储器，在提交之前不会影响其它线程。其它线程如果对本事务修改的数据项进行访问将导致线程放弃。基于软件的事务存储器使用软件来管理事务，它可以建立在Cache一致性机制和前述同步机制的基础上。与软件的互斥和锁机制相比，事务存储器由于可以消除共享存储器中锁变量竞争引起的大量访存操作，

22、并消除了死锁操作，因而具有更高的性能。,8.4.3 多线程同步机制带来的问题,（1）数据竞争数据竞争是由于各线程对共享数据读-写访问和写-写访问顺序的不确定性引起的。（2）同步同步是解决数据竞争的措施，目的是使数据访问按一定的顺序进行，但是同步机制会带来许多复杂性和一定的开销。（3）线程停顿线程停顿是同步操作带来的后果。在采用互斥量对共享资源进行锁定时，如果某个互斥量没有被解锁，则会使等待这个锁的线程停顿。,8.4.3 多线程同步机制带来的问题,（4）死锁死锁是线程无限期的停顿现象。它通常出现在对资源的占有和对其它资源的等待出现环形依赖关系的时候。（5）伪共享伪共享是线程之间的非真正的数据共享

23、引起的相关性。常见的有Cache数据块的伪共享现象。本来两个线程并没有真正共享同一个数据变量，但由于两个线程的访问数据都在同一个Cache块中，从而导致对该数据块的争用。这种现象会使系统的性能下降。,8.5 集群系统,集群系统及其特点 概述 集群系统的分类 集群系统的特点 集群系统的关键技术,集群系统及其特点,多处理器系统可以在不同的层次上实现，根据硬件实现的方式有芯片级、板卡级、机柜级等。集群（cluster）系统是以板卡级或机柜级多处理器系统为节点，通过标准局域网络构成的并行计算机系统，又称机群系统。集群系统中的每一个节点都是完整的能独立工作的计算机系统，这些计算机系统可以是同构的，也可能

24、是异构的，它们通过高速通信网络，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效协同并行完成特定的任务。,8.5.1.1 概述,集群系统的发展简介,集群系统的研究与开发工作是从二十世纪八十年代开始的，它起源于集群系统的良好的性能可扩展性(scalability)。尽管通过增加CPU个数和内存容量等方法来提高性能，由此出现了向量机、对称多处理机(SMP)等，但是当CPU的个数超过某一阈值，象SMP多处理机系统的可扩展性就变得极差。主要瓶颈在于CPU访问内存的带宽并不能随着CPU个数的增加而有效增长。与SMP相反，集群系统的性能随着CPU个数的增加几乎是线性变化的

25、。,集群系统的发展简介,1980年中后期10M以太网问世和1990年PVM（Parallel Virtual Machine）的发布，使集群系统有了可移植的并行编程环境；1991年开放源码的Linux操作系统的发布为集群系统的研究注入了新的活力，1993年Berkeley COW引起了巨大的反响。从此集群计算技术被广为关注，并迅速发展。从互联网中心服务器的变化来看，可以清晰地观察到集群结构是中心服务器的发展趋势。,90年代以前，中心服务器一般都用大型机（Mainframe）。大型机可以完成一切的应用和服务，用户从终端通过网络完成应用。这种应用模式带来许多的好处：应用集中、比较好部署、系统监控、

26、管理方便等。但大型机的缺点也是非常明显的，主要是设备昂贵，很难实现高可用解决方案；非高可用系统在出现故障时，全部应用都受到影响；操作系统、设备和部件比较专用，用户本身维护困难；可扩展性不强等。这些缺点中的任何一个都是用户难以接受的。,随着PC及其操作系统的普及和CPU的性能和稳定性的不断提高，人们逐渐用PC服务器构成的分布式系统（DistributedSystem）去代替大型机。分布式系统解决了大型机上面提到的多个缺点，却丢弃了大型机应用的优点，服务器多且杂，不好监控、管理，不好部署。因此综合大型机和分布式系统优势的服务器必将成为趋势，集群系统就是这样的服务器。目前，在世界前500强超级计算机

27、中，基于集群架构的超级计算机已占了绝大多数比例，大规模并行处理MPP（Massively Parallel Processing）系统的定义也趋向集群系统。,8.5.1.2 集群系统的分类,（1）按照应用目的可以分为高性能集群和高可用性集群；高性能集群通过将多台机器连接起来同时处理复杂的计算问题。高可用性集群的主要功能就是提供不间断的服务。（2）按照组成集群的计算机类型可以分为PC集群(COP：Cluster 0f PCs)、工作站集群(COW：Cluster of Workstations)、服务器集群(COS：Cluster of Servers)、SMP(对称多处理器)集群(CLUMP：

28、Cluster of SMP)等。（3）按照集群节点的操作系统分为Linux集群、Solaris集群，HP-UX集群、AIX集群NT集群、VMS(虚拟存储机)集群、微软Wolfpack集群等。,8.5.1.3 集群系统的特点,（1）高扩展性如果能够通过增加系统资源以满足不断增长的对性能和功能的要求，或者能够通过减少系统资源以降低成本，则称这样的计算机系统是可扩展的。一个系统的可扩展性包含性能和功能、成本伸缩、可兼容性等几个方面。集群系统具有很好的资源可扩展性，通过增加系统规模(即处理器数)、投入更多存储部件(高速缓存、主存、磁盘)以及增加软件等方法，能使系统具有更高性能或更多功能。在应用上，集

29、群系统也有很好的可扩展性。借助并行操作系统和并行计算工具的支持，应用程序的性能也能够随系统规模扩大而成比例地得到改进。集群系统还具有很好的技术可扩展性，包括代可扩展性、空间可扩展性以及异构可扩展性。,（2）高可用性计算机系统的可用性(availability)是通过系统的可靠性(reliability)和可维护性(maintainability)来度量的。工程上通常用平均无故障时间(MTTF)来度量系统的可靠性，即在系统或其部件发生故障前正常运行的平均时间。用平均维修时间(MTTR)来度量系统的可维护性，即用于修复系统和在修复后恢复正常工作状态所用的平均时间。系统的可用性被定义为：可用性=MT

30、TF/(MTTF+MTTR)*100%一般常规系统(Conventional)的年停机时间不多于3.7天，可用系统(Available)的年停机时间不多于8.8小时，而高可用系统(Highly Available)的年停机时间不能多于52.6分钟，可用比例达到99.99%。对于关键业务，停机通常是灾难性的。随着企业越来越依赖于信息技术，由于系统停机而带来的损失也将越拉越大。,采用集群技术有可能实现计算机系统的高可用性。因为集群中的一个节点失效，它的任务可以传递给其它节点，从而有效防止单点失效。高可用集群具有高可靠性的容错机制。通常是主从节点方式。次节点通常是主节点的镜像，并在工作中检测主节点的

31、状态（俗称心跳信号）。一旦从节点检测到主节点发生了故障（心跳消失），那么从节点就能够以热切换的方式在主节点故障时间内代替主节点提供服务。而对用户而言，整个系统环境是一致的。这种替换不仅是计算资源的冗余，也是存储资源乃至I/O资源的冗余，以保证整个系统的高可用性。集群中的存储资源一般由磁盘阵列和SAN构成，能够适应系统的高可用性。,（3）高性能集群系统的高性能是通过多节点、并行计算和负载均衡来保证的。通常，集群内部由十至数万个独立处理器组成，通过高速通信来连接。复杂问题涉及为集群开发并行编程应用程序，尽可能利用计算资源、存储资源和I/O资源的并行性。负载平衡集群允许系统同时接入更多的用户。系统负

32、载包括需要均衡的应用程序处理负载或网络流量负载。负载均衡指系统使负载在集群的各个节点中尽可能平均地分摊处理。集群中所有的节点都处于活动状态，它们分摊系统的工作负载，并且可以在节点之间动态分配负载，以实现平衡。对于网络流量也是如此。通常，网络服务器应用程序接受了太多入网流量，以致无法迅速处理，这就需要将流量发送给在其它节点上运行的网络服务器应用。还可以根据每个节点上不同的可用资源或网络的特殊环境来进行优化。这样，通过负载均衡，整个系统可以实现更高的应用饱和性能。,（4）高性价比集群系统中的各个节点可采用现成的独立的计算机系统，系统开发主要集中在节点通信、并行计算和负载均衡上，因此系统开发周期短，

33、用户投资风险小。集群系统可以采用廉价的符合工业标准的硬件通过并行计算构造高性能的系统，例如，将一定数量的高档PC机通过快速以太网进行互连，并辅之以某些相关的免费自由软件，如Linux，PVM，MPI等，即可得到一个性价比很不错的并行计算环境。因此集群系统价格可以做得很低，而且利用了现有设备，节约了系统资源。,8.5.2 集群系统的关键技术,通信子系统是集群系统的重要组成部分，它是连接集群系统底层的互连网络，完成系统中各节点之间的数据传递功能。集群网络按所采用的技术可分成两类：共享介质类型和基于开关类型。其中共享介质类型的高速网络，主要有快速以太网，如万兆以太网，包括10GBASEX、10GBA

34、SER和10GBASEW等3种类型。快速以太网是小规模、低成本集群的主要网络互连方式基于开关的高速网络主要有ATM 和Myrinet。Myrinet、Quadries、SCI和InfiniBand是商业化高性能集群通信网络，具有更高的带宽和更小的传输延时。另外，针对传统TCPIP协议的多层次结构使得复杂的缓冲管理带来很大的网络延迟和操作系统的额外开销问题，可以在用户空间实现通信协议、精简通信协议，采用新的通信机制，如用ActiveMessage通信机制等措施来解决。,1高效的通信系统,开发并行应用程序要比串行程序困难得多，它要涉及多个处理器之间的数据交换与同步，要解决数据划分、任务分配、程序调

35、试和性能评测等问题，需要相应支持工具，比如并行调试器、性能评测工具、并行化辅助工具等。广义地说，并行程序设计环境应包括硬件平台、操作系统和并行程序语言、编程、编译、调试及性能分析工具等，狭义的并行程序设计环境则仅指系统核心之上的工具软件部分。作为一个并行程序的支撑环境，至少应包括：并行语言支持或并行操作库函数支持；一种或多种并行编程模式。,2并行程序设计环境,常用的并行编程模式有消息传递编程模式和共享存储编程模式2种。目前集群系统上广泛使用的并行程序设计环境有PVM（Parallel Virtual Machine）、MPI（Message Passing Interface）、Express

36、、Linda等，能提供统一的虚拟机、定义和描述通信原理、管理系统资源、提供可移植的用户编程接口和多种编程语言支持。它们都是基于消息传递方式的，其中PVM 和MPI应用得最多。PVM是美国橡树岭国家实验室和美国几所大学联合开发的并行计算工具软件，支持C、C+和Fortran。MPI是一个消息传递标准，详见介绍。PVM和MPI都是免费软件，它们都可以方便地进行再开发。对于具有共享存储器的集群系统，则应采用共享变量模型来进行并行编程。需要注意的是，在前一种集群系统上也可以采用共享变量的并行编程模型，这时需要使用一种称为虚拟共享存储器的技术，利用它在基于分布存储器的集群系统中，实现物理上分布但逻辑上共

37、享的存储系统。相应的支撑软件有ThreadMarksDSM，MidwayDSM等。,3全局资源的管理与利用,如何有效地管理系统中的所有资源是集群系统的一个非常重要的方面，常用的并行编程环境PVM、MPI等对这方面的支持都比较弱，仅提供统一的虚拟机。主要原因是节点的操作系统是单机系统，并不提供全局服务支持，同时也缺少有效的全局共享方法。因此，就有必要在节点操作系统和并行编程环境之间加入一些中间件，即所谓的集群操作系统，来解决对系统中所有资源的调度，其中包括组调度、资源分配和并行文件系统等，实现一个单一系统映像的高层抽象，即一个虚拟的单一超级服务器，使得系统中的多台计算机像单一主机一样使用。,在并

38、行计算中，一个大任务往往由多个子任务组成。从应用的角度看，任何并行环境要提高并行应用的有效性，负载平衡策略是必不可少的。集群系统平台上的并行计算，因其异构性、特殊的网络结构，以及交互用户的介入，后台进程的运行等导致节点性能动态变化，其负载平衡问题显得尤其重要。当整个系统任务较多时，各节点的负载可能产生不均衡现象，从而会降低整个系统的利用率。负载平衡技术的核心是调度算法，即将各个任务比较均衡地分布到不同的处理节点进行并行处理以使各节点的利用率达到最大。除此之外，在设计负载平衡系统时，还需要考虑诸如决策时机、调度系统模式、负载指标的设计与收集、负载调度策略等问题。比较成熟的负载平衡系统有美国Wis

39、consin-Madison大学的Condor系统和加拿大Platform公司的LSF系统。它们的特点是只需对原有系统稍加改动，即可使之与并行程序设计环境结合起来，提供负载平衡功能。,4可扩展性技术,设计可扩展高性能计算机大致包括4个设计原理：(1)独立原理。该原理要求系统中的各个组成部分相互独立。如果无法达到要求，则应尽量使相关程度减至最小并使相关性尽量清晰。这里的组成部分包括硬、软件两方面。采用独立原理的一个好处是使独立扩展(增量扩展)成为可能；另一好处是使异构可扩展性成为可能。(2)平衡设计原理。该原理要求最小化任何性能瓶颈。应避免不平衡系统的设计，因为在这种系统中，一个慢速的部件将会导

40、致整个系统性能下降，即使其它部件的速度再高也无济于事。此外，还应避免单点失效，即一个部件的失效将会引起整个系统崩溃。,(3)可扩展性设计原理。即在设计一个可扩展系统时，应该从一开始就将可扩展性作为主要目标，而不是设计完成后再来考虑它。可扩展性设计的两种流行方法是过渡设计和向后兼容性设计。(4)时延隐藏原理。是指利用计算来隐藏通信时延，也就是说，能够保证即使是在长时延不可避免的情况下系统也能达到高性能。其基本思想之一是使计算和通信在时间上重叠。可以通过4种互补的方法进行时延隐藏：预取技术、分布式一致性高速缓存、非严格的存储器一致性模型、多线程处理器。,(1)相互独立的冗余设备。改善任何系统可用性

41、的一个重要技术是使用冗余部件。当一个主要部件发生故障时，由另一个备用部件继续提供服务。此外主要部件和备用部件之间必须相互隔离，使得它们不会因为同一个原因而发生故障。(2)故障接管。对于现在的商用集群来说，故障接管可能是最重要的性能需求。一个部件发生故障时，该技术允许系统的余留部分能继续提供原来由故障部件提供的服务。,5可用性技术,(3)恢复技术。指为了接管一个已发生故障部件的工作负载所要做的动作。有后向和前向两种恢复技术。对前者，周期地为运行在集群中的进程在稳定存储设备中保存它的一个一致状态(即检查点)。发生故障后，系统重组以与故障部件相隔离，恢复前一个检查点，然后继续正常的操作，整个过程称为

42、卷回。在独立于应用程序的可移植方式下后向恢复较容易实现，并已被广泛运用。然而，卷回过程要有较大的时间开销，这在实时系统中是不能容忍的，这时就要考虑使用前向恢复技术。这种技术要求系统不是卷回到故障前的某个检查点而是利用故障诊断信息去重构一个有效的系统状态，并继续执行下去。前向恢复将依赖于应用程序并且可能还需要额外的硬件设备支持。,集群系统作为当前世界上并行处理的热点和主流，具有许多其它系统不可替代的优势：性价比高、可扩展性好、高可用性和高能用性。尤其是PC并行集群系统以系统开发周期短、用户投资风险小、节约系统资源、用户编程方便等优点，非常适合我国国情。,8.6 多处理器系统的程序并行性,程序的并

43、行性挖掘 多处理器系统并行程序的设计思路 多线程并行的程序设计思路 支持并行程序的软件工具 OpenMP MPI,8.6.1 程序的并行性挖掘,8.6.1.1 多处理器系统并行程序的设计思路例如，求多项式E=ax3+bx2+cx+d采用秦九韶算法，可得到：E1=d+x(c+x(b+x(a),8.6.1 程序的并行性挖掘,图8-11 用树型流程图描述不同算法,(b),(a),为了评价并行算法的性能效率，用P表示可并行处理的处理器数目；用加速比Sp表示单处理器顺序运算的级数T1与P个处理器运算的级数Tp之比；用Ep表示P个处理器的设备利用率即效率，Ep=Sp/P。当Sp1时，必有Ep1，即运算的加

44、速总是导致效率的降低。由图8-11（b）可知：P=3，Tp=4，Sp=T1/Tp=6/4=1.5，Ep=Sp/P=1.5/3=0.5显然尽可能增大树中每一层的节点数，使各处理器可并行的运算尽可能多，就会使树的层次越少，从而增加运算的并行性。反复利用交换律、结合律、分配律有可能逐步增大树的广度，降低树的高度。,表达式运算并行性的识别，除了依靠算法以外，还可以依靠编译程序。有一些编译算法可以经过或不经过逆波兰后缀表达式直接从给定的算术表达式产生能并行执行的机器指令。,下面的例子是对64000个数据进行累加，分别在共享存储器和分布存储器多处理器系统进行并行运算。在共享存储器系统中，假定有8个处理器以

45、单总线方式连接。求和时，数据A存放在集中共享的存储器中，每个处理器对共享数据分成不同子集进行访问和累加。设p为处理器数(p=0,1,7)，所有处理器通过分别运行下面的程序，对子集中的数据进行部分和计算：sump=0;for(i=8000*p;i8000*(p+1);i=i+1)sump=sump+Ai;/累加子集中的数据程序将数据A分为8个子集，每个子集通过上面的循环得到部分和，分别存放在共享存储器内的sump中，再用递归折叠（recursive doubling）方法求得总和。由于部分和的数据都在共享存储器中，无需处理器之间的通信开销，每个处理器都可直接获得。但是，求总和的程序段必须在各个处

46、理器的部分和都计算出来之后才开始进行，因此需要一种同步机制来协调程序的执行时间。,下面是求总和的程序段：half=8;/8个处理器dosynch();/等待部分和的完成half=half/2;/分两半求和if(p1);其中，synch()函数是一个屏障同步函数，它使所有处理器中有关线程都执行到这一点时才继续执行以后的指令。先到达同步点的线程必须等待，只有当所有的线程都调用了这个函数时，该函数才返回。每一次循环，参与运算的处理器数目减半，在1/2的sump中得到两个部分和之和。退出循环后，half=1，sum0中得到总和。,在分布存储器多处理器系统中，假设有64个处理器（编号p=0,1,2,63

47、），通过某种互联网络相互连接，采用消息传递信息。上述求和运算的第一步是将64000个数据划分成64个数据子集发送到各个局部存储器中，称为数组A1。第二步是计算部分和与总和，程序为：sum=0;for(i=0;i=half/循环结束时，总和在sum中,该程序的前3行计算部分和，由各个处理器各自累加传递到本地的数据子集中的数据。后10行对部分和求和。所有参与运算的处理器分为两半，编号在上半部分的处理器是发送方，编号在下上半部分的处理器是接收方，接收方收到发送来的部分和，并和本地的部分和累加。其中，send函数指定传送的目的处理器号（由源处理器号p%half）及要传送的源处理器计算的部分和sum，由

48、接收方发出；receive函数接受消息即源处理器计算的部分和，接收方在未收到发送来的数据之前一直等待。虽然发送和接收操作之间不需要另加同步操作，但在一般情况下，仍然需要一种机制来保证发出的消息能够被及时接收到。,实现并行程序设计的方法主要有3种：（1）库函数在现有串行程序标准函数库的基础上扩充支持并行操作的函数。如MPI的消息传递库、POSIX的Pthread多线程库。库函数提供了在并行操作中的同步和互斥的函数。库函数方法较容易实现，不需要改变编译程序，但是程序中的并行性问题没有经过编译程序的检查、分析和优化。程序设计的难度较大，容易出现错误。（2）构造新的语言针对并行操作，在原有的程序设计语

49、言中增加新的构造语句。如Fortran 90在原有的Fortran中新增了向量运算语句。编译程序可以根据这些并行构造的语义生成适合并行运算的程序。在对并行构造语句进行分析的时候，编译程序通过检查、分析，发现并行运算中存在的问题和错误。这种方法需要采用新的编译程序，并且增加了编译程序的复杂性。,（3）增加编译指导语句在串行程序中嵌入一些表达并行运算的编译指导语句，或称伪语句。这些编译指导语句能被并行编译程序识别，但串行程序将其视为注视语句而忽略。因此程序既能在串行平台上进行编译和执行，也能适合并行平台。并行编译程序根据这些指导语句将相关代码转换成适合并行运算的代码，OpenMP就用到了这种方法。

50、该方法的特点介于上述两种方法之间。编译程序的复杂性不是太高，而且可以对程序进行分析和优化。程序员也可以在编译指导中对并行代码的生成进行控制。,8.6.1.2 多线程并行的程序设计思路,多线程的并行运行可以在单个处理器上运行，形成软件多线程共享同一个处理器资源，由操作系统通过动态改变线程的运行优先级来调度线程，实现多个线程都能在同一个处理器上运行。此时，多个线程通过共享Cache进行数据交换。这种方式是基于软件的多线程并行，开销较小。多线程在多处理器核或多个处理器芯片上的运行，主要是基于硬件的多线程并行。多个逻辑处理器上的多线程具有不同的硬件资源，线程之间的通信开销是硬件的通信开销，从而构成真正