《深入理解大数据：大数据处理与编程实践》一一1.1 并行计算技术简介
本节书摘来自华章计算机《深入理解大数据：大数据处理与编程实践》一书中的第1章，第1.1节,作者 主 编：黄宜华（南京大学）副主编：苗凯翔（英特尔公司），更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1.1 并行计算技术简介
1.1.1 并行计算的基本概念
随着信息技术的快速发展，人们对计算系统的计算能力和数据处理能力的要求日益提高。随着计算问题规模和数据量的不断增大，人们发现，以传统的串行计算方式越来越难以满足实际应用问题对计算能力和计算速度的需求，为此出现了并行计算技术。
并行计算（Parallel Computing）是指同时对多条指令、多个任务或多个数据进行处理的一种计算技术。实现这种计算方式的计算系统称为并行计算系统，它由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以并行化的方式共同完成复杂的计算任务。实现并行计算的主要目的是，以并行化的计算方法，实现计算速度和计算能力的大幅提升，以解决传统的串行计算所难以完成的计算任务。
现代计算机的发展历程可分为两个明显不同的发展时代：串行计算时代和并行计算时代。并行计算技术是在单处理器计算能力面临发展瓶颈、无法继续取得突破后，才开始走上了快速发展的通道。并行计算时代的到来，使得计算技术获得了突破性的发展，大大提升了计算能力和计算规模。
1.?单处理器计算性能提升达到极限
纵观计算机的发展历史，日益提升计算性能是计算技术不断追求的目标和计算技术发展的主要特征之一。自计算机出现以来，提升单处理器计算机系统计算速度的常用技术手段有以下几个方面。
图1-1 摩尔定律
1）提升计算机处理器字长。随着计算机技术的发展，单处理器字长也在不断提升，从最初的4位发展到如今的64位。处理器字长提升的每个发展阶段均有代表性的处理器产品，如20世纪70年代出现的最早的4位Intel微处理器4004，到同时代以Intel 8008为代表的8位处理器，以及20世纪80年代Intel推出的16位字长80286处理器，以及后期发展出的Intel 80386/486/Pentium系列为主的32位处理器等。2000年以后发展至今，出现了64位字长的处理器。目前，32位和64位处理器是市场上主流的处理器。计算机处理器字长的发展大幅提升了处理器性能，推动了单处理器计算机的发展。
2）提高处理器芯片集成度。1965年，戈登·摩尔（Gordon Moore）发现了这样一条规律：半导体厂商能够集成在芯片中的晶体管数量大约每18～24个月翻一番，其计算性能也随着翻一番，这就是众所周知的摩尔定律。在计算技术发展的几十年中，摩尔定律一直引导着计算机产业的发展。
3）提升处理器的主频。计算机的主频越高，指令执行的时间则越短，计算性能自然会相应提高。因此，在2004年以前，处理器设计者一直追求不断提升处理器的主频。计算机主频从Pentium开始的60MHz，曾经最高可达到4GHz～5GHz。
4）改进处理器微架构。计算机微处理器架构的改进对于计算性能的提升具有重大的作用。例如，为了使处理器资源得到最充分利用，计算机体系结构设计师引入了指令集并行技术（Instruction-level Parallelism，ILP），这是单处理器并行计算的杰出设计思想之一。实现指令级并行最主要的体系结构技术就是流水线技术（Pipeline）。
在2004年以前，以上这些技术极大地提高了微处理器的计算性能，但此后处理器的性能不再像人们预期的那样能够继续提高。人们发现，随着集成度的不断提高以及处理器频率的不断提升，单核处理器的性能提升开始接近极限。首先，芯片的集成度会受到半导体器件制造工艺的限制。目前集成电路已经达到十多个纳米的极小尺度，因此，芯片集成度不可能无限制提高。与此同时，根据芯片的功耗公式P=CV2f（其中，P是功耗；C是时钟跳变时门电路电容，与集成度成正比；V是电压，f是主频），芯片的功耗与集成度和主频成正比，芯片集成度和主频的大幅提高导致了功耗的快速增大，进一步导致了难以克服的处理器散热问题。而流水线体系结构技术也已经发展到了极致，2001年推出的Pentium4（CISC结构）已采用了20级复杂流水线技术，因此，流水线为主的微体系结构技术也难以有更大提升的空间。
由图1-2可以看出，从2004年以后，微处理器的主频和计算性能变化逐步趋于平缓，不再随着集成度的提高而提高。如图1-3a所示，在2005年以前，人们预期可以一直提升处理器主频。但2004年5月Intel处理器Tejas和Jayhawk（4GHz）因无法解决散热问题最终放弃，标志着升频技术时代的终结。因此，随后人们修改了2005年后微处理器主频提升路线图，基本上以较小的幅度提升处理器主频，而代之以多核实现性能提升，如图1-3b所示。
2.?多核计算技术成为必然发展趋势
2005年，Intel公司宣布了微处理器技术的重大战略调整，即从2005年开始，放弃过去不断追求单处理器计算性能提升的战略，转向以多核微处理器架构实现计算性能提升。自此Intel推出了多核/众核构架，微处理器全面转入了多核计算技术时代。多校计算技术的基本思路是：简化单处理器的复杂设计，代之以在单个芯片上设计多个简化的处理器核，以多核/众核并行计算提升计算性能。
图1-3 2005年前后人们预期的主频提升路线图
（注：插图引自Edward L. Bosworth，The Power Wall，2010）
自Intel在2006年推出双核的Pentium D处理器以来，已经出现了很多从4核到12核的多核处理器产品，如2007年Intel推出的主要用于个人电脑的4核Core 2 Quad系列以及2008～2010年推出的Core i5和i7系列。而Intel服务器处理器也陆续推出了Xeon E5系列4-12核的处理器，以及Xeon E7系列6-10核处理器。
除了多核处理器产品外，众核处理器也逐步出现。NVIDIA GPU是一种主要面向图形处理加速的众核处理器，在图形处理领域得到广泛应用。2012年年底Intel公司发布了基于集成众核架构（Intel? MIC Architecture，Intel? Many Integrated Core Architecture）的Xeon Phi协处理器，这是一款真正意义上通用性的商用级众核处理器，可支持使用与主机完全一样的通用的C/C++编程方式，用OpenMP和MPI等并行编程接口完成并行化程序的编写，完成的程序既可在多核主机上运行，也可在众核协处理器上运行。众核计算具有体积小、功耗低、核数多、并行处理能力强等技术特点和优势，将在并行计算领域发挥重要作用。众核处理器的出现进一步推进了并行计算技术的发展，从而使并行计算的性能发挥到极致，更加明确地体现了并行计算技术的发展趋势。
3.?大数据时代日益增大的数据规模迫切需要使用并行计算技术
随着计算机和信息技术的不断普及应用，行业应用领域计算系统的规模日益增大，数据规模也急剧增大。
全球著名的互联网企业的数据规模动辄达到数百至数千PB量级，而其他的诸如电信、电力、金融、科学计算等典型应用行业和领域，其数据量也高达数百TB至数十PB的规模。如此巨大的数据量使得传统的计算技术和系统已经无法应对和满足计算需求。巨大的数据量会导致巨大的计算时间开销，使得很多在小规模数据时可以完成的计算任务难以在可接受的时间内完成大规模数据的处理。超大的数据量或计算量，给原有的单处理器和串行计算技术带来巨大挑战，因而迫切需要出现新的技术和手段以应对急剧增长的行业应用需求。
**
1.1.2 并行计算技术的分类**
并行计算技术发展至今，出现了各种不同的技术方法，同时也出现了不同的分类方法，包括按指令和数据处理方式的Flynn分类、按存储访问结构的分类、按系统类型的分类、按应用的计算特征的分类、按并行程序设计方式的分类。
1.?Flynn分类法
1966年，斯坦福大学教授Michael J. Flynn提出了经典的计算机结构分类方法，从最抽象的指令和数据处理方式进行分类，通常称为Flynn分类。Flynn分类法是从两种角度进行分类，一是依据计算机在单个时间点能够处理的指令流的数量；二是依据计算机在单个时间点能够处理的数据流的数量。任何给定的计算机系统均可以依据处理指令和数据的方式进行分类。图1-4所示为Flynn分类下的几种不同的计算模式。
图1-4 Flynn分类法
1）单指令流单数据流（Single Instruction stream and Single Data stream，SISD）：SISD是传统串行计算机的处理方式，硬件不支持任何并行方式，所有指令串行执行。在一个时钟周期内，处理器只能处理一个数据流。很多早期计算机均采用这种处理方式，例如最初的IBM PC机。
2）单指令流多数据流（Single Instruction stream and Multiple Data stream，SIMD）：SIMD采用一个指令流同时处理多个数据流。最初的阵列处理机或者向量处理机都具备这种处理能力。计算机发展至今，几乎所有计算机都以各种指令集形式实现SIMD。较为常用的有，Intel处理器中实现的MMXTM、SSE（Streaming SIMD Extensions）、SSE2、SSE3、SSE4以及AVX（Advanced Vector Extensions）等向量指令集。这些指令集都能够在单个时钟周期内处理多个存储在寄存器中的数据单元。SIMD在数字信号处理、图像处理、多媒体信息处理以及各种科学计算领域有较多的应用。
3）多指令流单数据流（Multiple Instruction stream and Single Data stream，MISD）：MISD采用多个指令流处理单个数据流。这种方式实际很少出现，一般只作为一种理论模型，并没有投入到实际生产和应用中。
4）多指令流多数据流（Multiple Instruction Stream and Multiple Data Stream，MIMD）：MIMD能够同时执行多个指令流，这些指令流分别对不同数据流进行处理。这是目前最流行的并行计算处理方式。目前较常用的多核处理器以及Intel最新推出的众核处理器都属于MIMD的并行计算模式。
2.按存储访问结构分类
按存储访问结构，可将并行计算分为以下几类：
1）共享内存访问结构（Shared Memory Access）：即所有处理器通过总线共享内存的多核处理器，也称为UMA结构（Uniform Memory Access，一致性内存访问结构）。SMP（Symmetric Multi-Processing，对称多处理器系统）即为典型的内存共享式的多核处理器构架。图1-5即为共享内存访问结构示意图。
2）分布式内存访问结构（Distributed Memory Access）：图1-6所示为分布式内存访问结构的示意图，其中，各个分布式处理器使用本地独立的存储器。
图1-5 共享内存访问结构 图1-6 分布式内存访问结构
3）分布共享式内存访问结构（Distributed and Shared Memory Access）：是一种混合式的内存访问结构。
如图1-7所示，各个处理器分别拥有独立的本地存储器，同时，再共享访问一个全局的存储器。
分布式内存访问结构和分布共享式内存访问结构也称为NUMA结构（Non-Uniform Memory Access，非一致内存访问结构）。在多核情况下，这种内存访问架构可以充分扩展内存带宽，减少内存冲突开销，提高系统扩展性和计算性能。
3.?按系统类型分类
按并行计算系统类型，可将并行计算分为以下类型：
1）多核/众核并行计算系统（Multi-Core/Many-Core）或芯片级多处理系统（Chip-level
Multiprocessing，CMP）。
2）对称多处理系统（Symmetric Multi Processing，SMP），即多个相同类型处理器通过总线连接、并共享存储器构成的一种并行计算系统。
3）大规模并行处理系统（Massive Parallel Processing，MPP），以专用内联网连接一组处理器形成的一种并行计算系统。
4）集群（Cluster），以网络连接的一组普通商用计算机构成的并行计算系统。
5）网格（Grid），用网络连接远距离分布的一组异构计算机构成的并行计算系统。
4.?按应用的计算特征分类
按应用的计算特征，可将并行计算分为以下类型：
1）数据密集型并行计算（Data-Intensive Parallel Computing），即数据量极大、但计算相对简单的并行计算。
2）计算密集型并行计算（Computation-Intensive Parallel Computing），即数据量相对不大、但计算较为复杂的并行处理。较为传统的高性能计算领域大部分都是这一类型，例如三维建模与渲染、气象预报、生命科学等科学计算。
3）数据密集与计算密集混合型并行计算，具备数据密集和计算密集双重特征的并行计算，如3D电影渲染等。
5.?按并行程序设计方式分类
按并行程序设计方式，可将并行计算分为以下几类：
1）共享存储变量方式（Shared Memory Variables）：这种方式通常被称为多线程并行程序设计。多线程并行方式发展至今，应用非常广泛，同时也出现了很多代表性的并行编程接口，包括开源的和一些商业版本的并行编程接口，例如最常用的有pthread，OpenMP，Intel TBB等。其中，pthread是较为低层的多线程编程接口；而OpenMP采用了语言扩充的方法，简单易用，不需要修改代码，仅需添加指导性语句，应用较为广泛；而Intel TBB是一种很适合用C++代码编程的并行程序设计方法，提供了很多方便易用的并行编程接口。本书的附录A将较为详细地介绍OpenMP的技术特点和编程方法。共享存储变量方式可能引起数据的不一致性，从而导致数据和资源访问冲突，因此一般都需要引入同步控制机制。
2）消息传递方式（Message Passing）：从广义上来讲，对于分布式内存访问结构的系统，为了分发数据实现并行计算、随后收集计算结果，需要在各个计算节点或者计算任务间进行数据通信。这种编程方式有时候可狭义地理解为多进程处理方式。最常用的消息传递方式是MPI（Message Passing Interface，消息传递并行编程接口标准）。MPI广泛应用于科学计算的各个领域，并体现了其高度的可扩展性，能充分利用并行计算系统的硬件资源，发挥其计算性能。具体有关MPI技术的介绍，请阅读本书的附录B：MPI并行程序设计简介。
3）MapReduce并行程序设计方式：Google公司提出的MapReduce并行程序设计模型，是目前主流的大数据处理并行程序设计方法，可广泛应用于各个领域的大数据处理，尤其是搜索引擎等互联网行业的大规模数据处理。本书后续重点探讨的数据处理技术正是基于这种方式的并行程序设计技术。
4）其他新型并行计算和编程方式：由于MapReduce设计之初主要致力于大数据的线下批处理，因而其难以满足高实时性和高数据相关性的大数据处理需求。为此，近年来，逐步出现了多种其他类型的大数据计算模式和方法。这些新型计算模式和方法包括：实时流式计算、迭代计算、图计算以及基于内存的计算等。
1.1.3 并行计算的主要技术问题
依赖于所采用的并行计算体系结构，不同类型的并行计算系统在硬件构架、软件构架和并行算法方面会涉及到不同的技术问题，但概括起来，主要包括以下技术问题。
1.?多处理器/多节点网络互连技术
对于大型的并行处理系统，网络互连技术对处理器能力影响很大。典型的网络互连结构包括共享总线连接、交叉开关矩阵、环形结构、Mesh网络结构、互联网络结构等。
2.?存储访问体系结构
存储访问体系结构主要研究不同的存储结构以及在不同存储结构下的特定技术问题，包括共享数据访问与同步控制、数据通信控制和节点计算同步控制、Cache的一致性、数据访问/通信的时间延迟等技术问题。
3.?分布式数据与文件管理
并行计算的一个重要问题是，在大规模集群环境下，如何解决大规模数据的存储和访问管理问题。在大规模集群环境下，解决大数据分布存储管理和访问问题非常关键，尤其是数据密集型并行计算，数据的存储访问对并行计算的性能至关重要。目前比较理想的解决方法是提供分布式数据和文件管理系统，代表性的系统有Google GFS（Google File System）、Lustre、HDFS（Hadoop Distributed File System）等。这些分布式文件系统各有特色，适用于不同领域。
4.?并行计算的任务划分和算法设计
并行计算的任务分解和算法设计需要考虑的是如何将大的计算任务分解成子任务，继而分配给各节点或处理器并行处理，最终收集局部结果进行整合。一般有算法分解和数据划分两种并行计算形式，尤其是算法分解，可有多种不同的实现方式。
5.?并行程序设计模型和语言
根据不同的硬件构架，不同的并行计算系统可能需要不同的并行程序设计模型、方法和语言。目前主要的并行程序设计语言和方法包括共享内存式并行程序设计、消息传递式并行程序设计、MapReduce并行程序设计以及近年来出现的满足不同大数据处理需求的其他并行计算和程序设计方法。而并行程序设计语言通常可以有不同的实现方式，包括：语言级扩充（即使用编译指令在普通的程序设计语言中增加一些并行化编译指令，如OpenMP提供C、C++、Fortran语言扩充）、并行计算库函数与编程接口（使用函数库提供并行计算编程接口，如MPI、CUDA等）以及能提供诸多自动化处理能力的并行计算软件框架（如Hadoop MapReduce并行计算框架等）。
6.?并行计算软件框架设计和实现
现有的OpenMP、MPI、CUDA等并行程序设计方法需要程序员考虑数据存储管理、数据和任务划分、任务的调度执行、数据同步和通信、结果收集、出错恢复处理等几乎所有技术细节，非常繁琐。为了进一步提升并行计算程序的自动化并行处理能力，编程时应该尽量减少程序员对很多系统底层技术细节的考虑，使得编程人员能从底层细节中解放出来，更专注于应用问题本身的计算和算法实现。目前已发展出多种具有自动化并行处理能力的计算软件框架，如Google MapReduce和Hadoop MapReduce并行计算软件框架，以及近年来出现的以内存计算为基础、能提供多种大数据计算模式的Spark系统等。
7.?数据访问和通信控制
并行计算目前存在多种存储访问体系结构，包括共享存储访问结构、分布式存储访问结构以及分布共享式存储访问结构。不同存储访问结构下需要考虑不同的数据访问、节点通信以及同步控制等问题。例如，在共享存储访问结构系统中，多个处理器访问共享存储区，可能导致数据访问的不确定性，从而需要引入互斥信号、条件变量等同步机制，保证共享数据访问的正确性，同时需解决可能引起的死锁问题。而对于分布式存储访问结构系统，数据可能需要通过主节点传输到其他计算节点，由于节点间的计算速度不同，为了保证计算的同步，需要考虑计算的同步问题。
8.?可靠性与容错性技术
对于大型的并行计算系统，经常发生节点出错或失效。因此，需要考虑和预防由于一个节点失效可能导致的数据丢失、程序终止甚至系统崩溃的问题。这就要求系统考虑良好的可靠性设计和失效检测恢复技术。通常可从两方面进行可靠性设计：一是数据失效恢复，可使用数据备份和恢复机制，当某个磁盘出错或数据损毁时，保证数据不丢失以及数据的正确性；二是系统和任务失效恢复，当某个节点失效时，需要提供良好的失效检测和隔离技术，以保证并行计算任务正常进行。
9.?并行计算性能分析与评估
并行计算的性能评估较为常用的方式是通过加速比来体现性能提升。加速比指的是并行程序的并行执行速度相对于其串行程序执行加速了多少倍。这个指标贯穿于整个并行计算技术，是并行计算技术的核心。从应用角度出发，不论是开发还是使用，都希望一个并行计算程序能达到理想的加速比，即随着处理能力的提升，并行计算程序的执行速度也需要有相应的提升。并行计算性能的度量有以下两个著名的定律：
1）Amdal定律：在一定的程序可并行化比例下，加速比不能随着处理器数目的增加而无限上升，而是受限于程序的串行化部分的比例，加速比极限是串行比例的倒数，反映了固定负载的加速情况。Amdal定律的公式是：
其中，S是加速比，P是程序可并行部分的比例，N是处理器数量。图1-8所示是在程序不同的可并行化比例下、在不同处理器数量下的加速比，由图示结果可见，在固定的程序可并行化比例下，加速比提升会有一个上限，处理器数量的增加并不能无限制地带来性能提升。
图1-8 Amdal定律在程序不同的可并行化比例和不同处理器数量下的加速比
2）Gustafson定律：在放大系统规模的情况下，加速比可与处理器数量成比例地线性增长，串行比例不再是加速比的瓶颈。这反映了对于增大的计算负载，当系统性能未达到期望值时，可通过增加处理器数量的方法应对（如图1-9和1-10所示）。