第5章 并行计算与集群技术

并行计算（Parallel Computing) 也叫高性能计算（High Performance Computing) 、高端计算（High-end Parallel Computing) 或超级计算（Super Computing) .它的快速发展为其他技术、的发展提供了重要的支撑。云计算关注的两个要点是计算力和存储力，而计算力依赖的技术就
是并行计算，因此学习云计算需要了解并行计算的概念和分类。集群技术是并行计算的基础，也是云计算的基础，所以需要了解集群技术。本章就将介绍并行计算的基本概念及分类，云计算的基础架构－集群，以及并行程序设计－MPI编程。

5. 1 并行计算概述

并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效方法。它的基本思想是，利用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。在计算机术语中，并行性指的是把一个复杂问题分解成多个能同时处理子问题的能力。
并行计算是指同时使用多种计算资源解决计算问题的过程，是旨在提高计算机系统计算速度和处理能力的一种有效手段。它是由运行在多个部件上的小任务合作来求解一个规模很大的计算问题的一种方法。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题拆分成若干个部分，各部分均由一个独立的处理机来进行计算。并行计算系统实际上是一种由多个计算单元组成，运算速度快、存储容量大、可靠性高的计算机系统。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群，通过并行计算集群完成数据的处理，再将处理的结果返回给用户。并行计算的内涵包括了并行计算机体系结构、编译系统、并行算法、并行编程、并行软件技术、并行性能优化与评价、并行应用等。此外，并行计算可以定位为连接并行计算机系统和实际应用问题之间的桥梁。它辅助科学、工程及商业应用领域的专家，为在并行计算机上求解本领域问题提供了关键支撑。
因此，为了成功实施并行计算，须具备3个基本条件：

1. 并行计算机。并行计算机至少包含两台或两台以上的处理机，并且这些处理机通过网络能相互连接、相互通信。
2. 应用具有并行度。应用可以分解为多个子任务，这些子任务可以并行执行。将一个应用分解为多个子任务的过程，便称为并行算法的设计。
3. 并行编程。在并行计算机提供的并行编程环境上，具体实现并行算法，编制并行程序并运行该程序，从而达到并行求解应用问题的目的。
   并行计算之所以可行，主要在于并发性是物质世界的一种普遍属性，具有实际应用背景的计算问题在多数情况下都可以拆分为能并行计算的多个子任务。

5. 1.1并行计算机的发展

并行计算机的出现是并行计算得以应用的重要前提。并行计算机的产生和发展就是为了满足日益增长的大规模科学和工程计算、事务处理和商业计算的需求。问题求解的最大规模是并行计算机最重要的指标之一。
大规模科学与工程计算应用对并行计算的需求是推动并行计算机快速发展的主要动力，它们对并行计算能力的需求是永无止境的，这加快推动了并行计算的产生。市场需求也是推动并行计算产生的另一巨大动力，许多的应用领域，如天气预报、核科学、石油勘探、地震数据处理、飞行器数值模拟等，都需要具有每秒执行万亿次甚至是百万亿次浮点运算能力的计算机，并行计算是满足它们实际需求的可行途径，进一步催生了并行计算机的产生。除了大规模科学与工程计算应用外，微电子技术与大规模集成电路的迅猛发展亦是推进并行计算机产生的另一动力。

1. 按时间看并行计算机的发展
   20世纪70年代，第一台并行计算机于1972年产生（ILLIAC IV, 伊利诺依大学）， 由64个处理器组成，可扩展性好，但可编程性差。1976年向量机 Cray-1投入运行，以Cray-1为代表的向量机称雄超级计算机界十余年。Cray-1 编程方便，但可扩展性较差。
   20世纪80年代，并行计算机的发展进入百家争鸣的阶段，早期以多指令多数据流 MIMD （Multiple Instruction stream Multiple Data stream) 并行计算机为主；中期出现了具备对称式多处理器（Symmetrical Multi-Processor, SMP) 的共享存储多处理机（Shared-Memory Multi-Processors) , 这种处理机在一台计算机上汇集了一组处理器，即多个CPU, 各CPU 之间共享内存子系统以及总线结构，这是一种相对非对称多处理技术而言的、应用十分广泛的并行技术，其思路是各处理器对称共享内存及计算机的其他资源，由单一操作系统管理，极大地提高了整个系统的数据
   处理能力，但扩展性、可靠性较差，容易出现内存访问瓶颈：后期出现了具有强大计算能力的开行计算机，如通过二维 Mesh 连接的Meiko (Sun) 系统，超立方体连接的 MIMD 并行计算机，共享存储向量多处理机 Cray Y-MP等，种类繁多。
   20 世纪90年代，并行计算体系结构框架趋于统一，以分布式共享存储 DSM (Distributed Shared Memory) 、大规模并行处理结构 MPP (Massively Parallel Processing) 、工作站集群 COW （Cluster of Workstations) 为代表。这期间，并行计算机的发展思路是让每个结点越来越独立，最后达到每个结点都是一个完整的工作站，有独立的硬盘与 UNIX 系统；结点间通过低成本的网络（如千兆以太网）连接。COW的典型代表是 Beowulf cluster 集群，COW与MPP之间的界线越来越模糊。
   2000年至今，并行计算得到了前所未有的大踏步发展。并行计算机以COW 为原型的由大规模商用普通 PC 机构成的集群为主，如Cluster 集群、Constellation 星群和 MPP 都是以集群为基本架构。Cluster 集群中每个结点包含多个商用处理器，结点内部共享存储；采用商用集群交换机通过前端总线连接结点，结点分布存储：各个结点采用 Linux 操作系统、GNU 编
   译系统和作业管理系统。Constellation 星群中每个结点都是一台子并行计算机，采用商用集群交换机通过前端总线连接结点，结点采用分布存储，各个结点运行专用的操作系统、编译系统和作业管理系统。并行计算机各个年代的发展如图5-5所示。

5. 1. 2 并行计算与分布式计算

并行计算、分布式计算都属于高性能计算（High Performance Computing, HPC) 范畴，主要目的都是对大数据进行分析和处理，都是利用并行来获得更高性能的计算－把大任务分为n个小任务。这也使得很多人一直分不清两者之间的关系，但二者之间存在很多差异，我们需要了解两者的原理、特点和运用的场合，这对于云计算的理解大有裨益。
这里首先简要介绍一下分布式计算的概念。分布式计算主要研究分散系统（Distributed System) 如何进行计算。分散系统是一组计算机通过计算机网络互连后形成的系统。分布式计算可以把程序放在最适合运行它的计算机上运行，实现共享稀有资源和平衡负载，这也是分布式计算的核心思想之一。
并行计算是相对于串行计算来说的，并行计算主要目的是加速求解问题的速度和提高求解问题的规模。并行计算强调时效性和海量数据处理，各任务之间的独立性弱，而且关系密切，每个结点之间的任务时间要同步。即并行程序并行处理的任务包之间有很大的联系，并且并行计算的每一个任务块都是必要的，没有浪费的、分割的，就是每个任务包都要处理，而且计算结果相互影响，这就要求每个计算结果要绝对正确。
分布式计算是相对于集中式计算来说的，分布式计算的任务包相互之间有独立性，上一个任务包的结果未返回或者是结果处理错误、对下一个任务包的处理几乎没有什么影响。分布式计算的实时性要求不高，并且允许存在计算错误（因为每个计算任务给好几个参与者计算，上传结果到服务器后要比较结果，然后对结果差异大的进行验证。也就是说，分布式计算不强调时效性，各任务之间相互独立，所以结点节可以没有通讯，即无网络信息传输。每个结点之间的任务执行时间没有限制。
典型的分布式计算，如分析计算蛋白质的内部结构和相关药物的 Folding@home 项目，该项目结构庞大，需要惊人的计算量，由一台计算机计算是不可能完成的。因此，该项目通过分布式计算技术把需要进行大量计算的工程数据分区成小块，分配给多台计算机分别计算，在各台计算机上传运算结果后，将结果统一合并得出数据结论。因此，有人认为分布式计算是开行计算的一种特例。
分布式计算中，很多任务块可以根本不处理，即有大量的无用数据块。因此，分布式计算的速度尽管很快，但真正的“效率”是低之又低的。分布式要处理的问题一般是基于“寻找”模式的。所谓的“寻找”， 就相当于穷举法。为了尝试到每一个可能存在的结果，一般从0~n (某一数值）被一个一个的测试，直到找到所要求的结果。事实上，为了易于一次性探测到正确的结果，可以假设结果是以某个特殊形式开始的。在这种类型的搜索里，也许一开始就找到答案，也许到最后才找到答案，即分布式计算中可能一直在寻找答案，但有可能永远都找不到，也可能一开始就找到了。而并行计算的任务包个数相对有限，在一个有限的时间应该是可能完成的。
分布式计算程序的编写一般用是 C++或 Java, 基本不用 MPI接口。并行计算编程采用用MPI或者OpenMP.

5. 1. 3 并行计算与云计算

云行在天，云计算的横空出世少不了其他技术的支持，云计算是并行计算技术、大数据技术和网络技术发展的必然结果。
云计算需要解决：计算资源的透明虚拟化和弹性化、内存储资源的透明虚拟化和弹性化、外存储资源的透明虚拟化和弹性化、数据安全的保障、向开发者提供完善的 API 并实现终端用户向云计算的平滑过渡。云计算将一切隐在云端，普通用户不再关心数据存在哪里，不再关心数据的安全，不再关心应用程序是否需要升级，不再关心计算机病毒的危害，这一切的
工作都由云计算负责解决，普通用户要做的就是选择自己喜爱的云计算服务商购买自己需要的服务，并为之付费。云计算使普通用户有了享受高性能计算的机会，因为云计算中心几乎可以提供无限制的计算能力，计算的弹性化和存储的弹性化是云计算的重要特征。
云计算的计算能力的实现是从计算机的并行化开始的，即把多个计算机并联起来，从而获得更快的计算速度，这是一种很简单也很朴素的实现高速计算的方法，也被证明是相当成功的方法。
大规模并行计算机出现后，以其为基础的云计算服务器集群的服务器数量是以万、十万甚至更高的单位计数，在这样巨大的集群规模下，云计算面临两个重要问题：昂贵的系统部署费用和不可忽视的结点失效问题。在云计算环境中，云计算的计算力和存储力可随着需求改变，即云计算是按需使用的。这种理念同时也适用于云计算对服务器的要求，在云计算时代人们不再追求服务器的高性能、全配置，“能用就行＂成了云计算时代的对服务器的要求。因此云计算的基础架构采用了以COW (Cluster Of Workstations, 工作站集群）为原型的由大规模商用普通PC机（大大降低了服务器的硬件成本）构成的集群为主的体系架构，这一体系架构正是并行计算机2000年后最基本的结构模型。
由于服务器的大量集中，服务器的失效成为经常的事情，传统的架构对于单点失效是很敏感的，而在云计算架构下单点失效成为系统认可的常态，任何的单点失效都不会影响系统对外提供服务。即云计算在构建系统架构时就将系统结点的失效考虑了进去，实现了基于不可信服务器结点的云计算基础架构。将服务器失效作为云计算系统的服务器集群模型是符合实际情况的，这种情况下单个服务器可以看作是不可信的结点，在系统设计时必须要将不可信服务器结点的失效屏蔽在系统之内，不向开发者和普通用户传递。在将服务器失效作为常态的服务器集群模型下，数据的安全性通过副本策略得到了保证。

5. 2 云计算基础架构－集群技术

集群架构是当前高性能计算的主流架构，也是大数据领域的主流架构，集群技术是支撑云计算与大数据系统的重要技术。

5. 2. 1 集群的基本概念

集群是一组独立的计算机（结点）的集合体，结点间通过高性能的网络相连接，各结点除了作为一个单一的计算资源供用户使用外，还可以协同工作，并表示为一个单一的、集中的计算资源，供并行计算任务使用。集群是一种造价低廉、易于构建并且具有较好可扩展性的体系结构。集群具有以下重要特征：

1. 集群中的各个结点都是一个完整的计算机系统，结点可以是工作站，也可以是PC或对称多处理器SMP.
2. 网络连接上通常使用如以太网、FDDI、光纤等商用网络设备，部分商用集群也采用专用网络互联。
3. 网络接口与结点的I/O总线松耦合相连。
4. 各结点具有本地磁盘。
5. 各结点有自己的独立的操作系统。
   集群系统的设计中要考虑5个关键问题。
6. 可用性：集群系统有一个提供可用性的中间层，它使集群系统可以提供检查点、故障接管、错误恢复以及所有结点上的容错支持等服务。从而可以充分利用集群系统中的冗余资源，使系统在尽可能长的时间内为用户服务。
7. 单一系统映像 SSI (Single System Image) : 集群系统与一组互联工作站的区别在于，集群系统可以表示为一个单一系统。集群系统中也有一个单一系统映像的中间层，它通过组合各结点上的操作系统提供对系统资源的统一访问。
8. 作业管理（Job Management) : 因为集群系统需要获得较高的系统使用率，集群系统上的作业管理软件需要提供批处理、负载平衡、并行处理等功能。
9. 并行文件系统PFS: 由于集群系统上的许多并行应用要处理大量数据，需进行大量的I/0操作，而这些应用要获得高性能，就必须要有一个高性能的并行文件系统。
10. 高效通信（Efficient Communication) .集群系统比MPP机器需要一个更高效的通信子系统，因为集群系统的结点复杂度高，结占间的连接线路比较长，带来了较高的通信延迟，同时也带来了可靠性、时钟扭斜（Clock Shew) 和串道（Cross-Talking) 等问题。

5. 2. 2 集群系统的分类

一个理想的集群系统从来不会让用户意识到它的底层存在众多的结点。在用户看来，集群就是一个单独的计算机系统，而非由多个计算机系统构成。并且集群系统的管理员可以随意增加和删改集群系统的结点而用户并无感知。
集群系统按功能和结构可以分为如下四类。
（1) 高可用性集群系统
高可用性集群系统通常通过备份结点的使用来实现整个集群系统的高可用性，活动结点失效后备份结点自动接替失效结点的工作。高可用性集群系统就是通过结点冗余来实现的，一般这类集群系统主要用于支撑关键性业务，保证关键性业务的不间断服务。
（2) 负载均衡集群系统
负载均衡集群系统中所有结点都参与工作，系统通过管理结点（利用轮询算法、最小负载优先算法等调度算法）或利用类似一致性哈希等负载均衡算法实现整个集群系统内负载的均衡分配。
（3) 高性能集群系统
高性能集群系统主要是追求整个集群系统强大的计算能力，其目的是完成复杂的计算任
务，在科学计算中常用的集群系统就是高性能集群系统，目前物理、生物、化学等领域有大量
的高性能集群系统提供服务。
（4) 虚拟化集群系统
在虚拟化技术得到广泛使用后，人们为了实现服务器资源的充分利用和切分，将一台服务器利用虚拟化技术分割为多台独立的虚拟机使用，并通过管理软件实现虚拟资源的分配和管理。这类集群系统称为虚拟集群系统，其计算资源和存储资源通常是在一台物理机上。利用虚拟化集群系统可以实现虚拟桌面技术等云计算的典型应用。
目前基于集群系统结构的云计算系统和大数据系统往往是几类集群系统的综合，它既需要满足高可用性的要求又尽可能地在结点间实现负载均衡，同时也需要满足大量数据的处理任务。Hadoop、HPCC (HighPerformance Computing Cluster, 高性能计算集群）这类大数据系统中，前三类集群系统的机制都存在，而在基于虚拟化技术的云计算系统中采用的往往是虚拟化集群系统。