分布式与并行计算报告.doc

并行计算技术及其应用简介
XX
（XXX， XX，XXX）
摘 要： 并行计算是实现高性能计算重要技术手段。在本文中从并行计算发展历程开始简介，总结了并行计算在发展过程中所面临问题以及其发展历程中浮现重要技术。通过度析在当前比较惯用实现并行计算框架和技术，来对并行计算现状进行阐述。惯用并行架构分为SMP（多解决系统）、NUMA（非统一内存存储）、MPP（巨型并行解决）以及集群。涉及并行计算编程模型有MPI、PVM、OpenMP、TBB及Cilk++等。并结合当前研究比较多云计算和大数据来探讨并行计算应用。最后通过MPI编程模型，进行了并行编程简朴实验。
核心词： 并行计算；框架；编写模型；应用；实验
A Succinct Survey about Parallel Computing Technology and It’s Application
Abstract： Parallel computing is the main technology to implement high performance computing. This paper starts from the history of the development of Parallel Computing. It summarizes the problems faced in the development of parallel computing and the important technologies in the course of its development. Through the analysis of framework and technology commonly used in parallel computing currently,to explain the current situation of parallel computing.Framework commonly used in parallel are SMP(multi processing system),NUMA(non uniform memory storage),MPP(massively parallel processing) and cluster.The programming models of parallel computing are MPI，PVM，OpenMP，TBB and Cilk++，etc.Explored the application of parallel computing combined with cloud computing and big data which are very popular in current research.Finally ,through the MPI programming model,a simple experiment of parallel programming is carried out.
Key words： parallel computing；framework；programming model；application；experiment
1引言
近年来多核解决器迅速发展，使得当前软件技术面临巨大挑战。单纯提高单机性能，已经不能满足软件发展需求，特别是在解决某些大计算问题上，单机性能越发显得局限性。在近来AlphaGo与李世石围棋大战中，AlphaGo就使用了分布式并行计算技术，才干获得强大搜索计算能力。并行计算正是在这种背景下，应运而生。并行计算或称平行计算时相对于串行计算来说。它是一种一次可执行各种指令算法，目是提高计算速度，及通过扩大问题求解规模，解决大型而复杂计算问题。可分为时间上并行和空间上并行。时间上并行就是指流水线技术，而空间上并行则是指用各种解决器并发执行计算。其中空间上并行，也是本文重要关注点。
并行计算（Parallel Computing）是指同步使用各种计算资源解决计算问题过程，是提高计算机系记录算速度和解决能力一种有效手段。它基本思想是用各种解决器来协同求解同一问题，即将被求解问题分解成若干个某些，各某些均由一种独立解决机来并行计算。并行计算系统既可以是专门设计，具有各种解决器超级计算机，也可以是以某种方式互联若干台独立计算机构成集群。通过并行计算集群完毕数据解决，再将解决成果返回给顾客。
当前惯用并行计算技术中，有调用系统函数启动多线程以及运用各种并行编程语言开发并行程序，惯用并行模型有MPI、PVM、OpenMP、TBB、Cilk++等。运用这些并行技术可以充分运用多核资源适应当前迅速发展社会需求。并行技术不但要提高并行效率，也要在一定限度上减轻软件开发人员承担，如近年来TBB、Cilk++并行模型就在一定限度上减少了开发难度，提高了开发效率，使得并行软件开发人员把更多精力专注于如何提高算法自身效率，而非把时间和精力放在如何去并行一种算法。
文献[1]回顾了并行计算技术六十近年发展历史，并分析了其发展将来趋势和所面临可拓展性“墙”。文献[2]对大规模MPI计算中，当前惯用容错机制和多模冗余带来开销进行了分析，提出了一种可拓展三模冗余容错机制。文献[3]则阐述了并行计算和云计算之间关系，并简介了并行计算在云计算中运用某些指引原则。文献[4]分析了在大数据时代，并行计算面临挑战和基于，综述了面向批解决、面向流解决、面向图数据以及面向内存等几类并行计算模型有关研究。文献[5]对并行计算模型进行了概述，简介了抱负计算模型特性，讨论了某些典型计算模型，综述了当前并行计算模型在异构计算环境发展状况。文献[6]针对老式单一并行计算模型变得越来越复杂，对并行计算个阶段针对性不强，提出了一种分层并行计算模型思想。文献[7]针对在专业集群中进行并行计算解决，存在费用高、管理困难和操作复杂等问题，运用PC和以太网相连实验环境，采用集群工作框架和并行计算核心技术，提出基于Linux集群并行计算系统环境，并在该环境上对系统性能进行了测试。文献[8]在CPU/GPU协同并行计算这一新兴领域，对当前研究工作进行了综述。依照所用计算资源规模将CPU/GPU协同并行计算研究划分为三类，尔后从立项根据、研究内容和研究办法等方面重点简介了几种混共计算项目，并指出了可进一步研究方向，以期为领域科学家进行协同并行计算研究提供一定参照。文献[9]中对图形解决器中有关问题进行研究。提出了统一计算架构（CUDA）为实现GPU通用计算提供了高效、简便办法．因而，建立了基于GPU通用计算平台中心差分格式显式有限元并行计算办法．该办法针对GPU计算特点，对串行算法流程进行了优化和调节，通过采用线程与单元或节点一一映射方略，实现了迭代过程完全并行化。
2并行计算发展三个重要阶段
并行计算是实现超高计算性能重要技术手段，回顾其发展历史进程，可以看出并行计算发展从整体上跨越了三个阶段。
2．1 Amdahl公式与适度并行
早在二十世纪四十年代中后期，当代电子计算机鼻祖冯·诺依曼就提出了用并行计算提高计算机性能技术途径。所谓并行计算，就是采用各种运算部件或多台计算机共同开展计算任务。理论上，并行多少台计算机就可以获得多少倍运算速度，但实际加速能力往往和应用特性密切有关。1967年，Amdahl提出了知名计算性能加速比公式（也称Amdahl定律）：
（1）
公式（1）中表达应用串行版本程序执行时间，f表达应用中不能被并行化某些工作量占整个程序工作量比率，n表达并行系统解决器数目。表达应用并行版本程序和n个解决器上执行时间。这些概念和理论方面基本研究极大地推动了适度并行计算技术实用化。
2．2 Gustafson公式与大规模并行
80年代后期学术界展开了一次很大讨论，人们对并行与否有前程众说纷坛，问题焦点是-------能不能通过并行规模增大来持续提高计算机性能。
1988年，美国科学家Gustafson在大量实际物理问题并行计算过程中总结了一种知名公式，刊登在《Communication of ACM》上。这篇论文只有两页，但它揭示了一种规律，即Gustafson通过她应用实践发现，诸多程序随着应用规模扩大，程序中不能被并行化某些工作量绝对量基本保持不变。而不能被并行化某些工作量占总工作量相对比例f会相应减小。基于这个规律，她提出了知名Gustafson加速比公式：
（2）
从公式可以得出，当f随着计算规模扩大而不断缩小时，解决器数如果增多，一种程序加速比还是可以随着解决器增多而提高。这个公式不是一种精细性能评估公式，而是一种思想性公式，它揭示了大规模并行要旨：并行计算机实际性能和它所运营并行程序特性密切有关。在大规模并行计算机上要获得高实用计算性能，在其上运营并行程序必要具备串行计算负载保持不变，并行计算负载随着计算机规模扩大而扩大特点，这样程序普通成为可扩展并行程序。在提高大规模并行计算使用效率过程中，能否设计出可扩展并行算法和可扩展并行程序，与大规模并行计算机系统研制同等重要。
2．3 效能评价模型与高效能并行
高性能计算机应当向什么方向发展，美国国防部（DARPA）提出“高效能计算系统（HPCS）”筹划，着眼于高性能向高效能转变，以为高效能计算机系统不但要关注很高计算性能，还要关注系统实用性能、可编程性、可移植性、系统鲁棒性和经济可行性。于是基于经济学中产生率概念和效用理论逐渐取代了以往单一计算性能评价模型。效能模型框架如下：
（3）
其中，T为问题P解决时间（Time-to-solution），M是并行计算机系统，U为效用函数，C为在系统M上T时间内解决问题P所投入最小成本函数。该效能度量模型综合考虑了并行系统开发（Development）和运营（Execution）两种状态，将开发时间和系统运营时间统一到问题解决时间T中。虽然，环绕这一公式标志着高性能计算机学术界、产业界对大规模并行计算机发展趋势产生了新结识。
3 并行编程模型
并行编程可以调用系统函数启动多线程，也可以运用并行编程模型，如惯用并行模型有MPI、PVM、OpenMP、TBB及Cilk++等。
3.1 MPI简介
MPI（Message Passing Interface）是基于消息传递并行编程模型。消息传递指是并行执行各个进程具备自己独立堆栈和代码段，作为互补有关各种程序独立执行，进程之间通信通过显式地调用通信函数来完毕。
（1）MPI程序基本函数
①MPI_Init用来初始化MPI执行环境，建立各种MPI进程之间联系，为后续通信做准备。MPI_Finalize则是结束MPI执行环境。这两个函数之间定义MPI程序并行区域。
②MPI_Comm_rank 来表达各个MPI进程。
③MPI_Comn_size 用来表达进程组中有多少个进程，返回整型错误值，同步有两个函数参数，MPI_Comn 类型通信域，标记参加计算MPI进程组，如MPI_COMM_WORLD;整数指标，返回相应进程组中进程数。
（2） MPI性能分析与优化举例
MPI消息传递开销由两某些构成：一某些是通信固有延迟；另一某些是消息传递开销，与消息数据量和网络带宽关于。时间消耗可以用下面式子表达：
（4）
其中，、、分别表达程序总用时、通信用时和串行某些用时。而通信用时普通可作如下分解：
（5）
其中，n为点对点通信次数，m为集群通信次数，为通信固定延迟，为第i次通信容量，w为网络带环，为负载不平衡导致时间消耗，集群通信耗时。
（3） 解决负载均衡问题
在并行计算中，若各个解决器上执行时间不同，因同步会使先完毕解决器等待未完毕解决器，此时应当考虑负载均衡问题，是资源得到合理运用。负载均衡分为：静态负载均衡及动态负载均衡。静态负载均衡使用与计算前可以精确估算总负载，且这些负载容易平均划分给各个进程状况。对于实现不懂得负载总数，或者总负载不易平均划分状况，需要动态负载均衡方略来解决。
3.2 PVM简介
PVM是一种在网络上虚拟并行机系统软件包，它容许将网络上基于UNIX操作系统并行机和单解决机集合当成一台单一并行虚拟机来使用。PVM支持顾客采用消息传递方式编写并行程序。计算以任务为单位，一种任务就是一种UNIX进程，每个任务均有一种taskid来标记（不同于进程号）。
PVM支持在虚拟机中自动加载任务运营，任务间可以互相通讯以及同步，在PVM系统中，一种任务呗加载到哪个节点上去运营，PVM就容许顾客指定任务被加载节点，这样就以便了顾客编写并行程序。
3.3 OpenMP简介
OpenMp是一种面向共享内存及分布式共享内存多解决器多线程并行编程语言，它也是一种可以用于显示指引多线程、共享内存并行应用程序编程接口。OpenMP 编程模型以线程为基本，通过编译指引语句来显示地指引并行化，为编程人员提供了并行化完整控制。OpenMP 执行模型采用Fork － Join 形式，Fork － Join 执行模式在开始执行时候，只有一种主线程存在。主线程在运营过程，当遇到需要进行并行计算时候，派生出子线程来执行并行任务。在并行执行时候，主线程和派生线程共同工作。在并行代码结束执行后，派生线程退出或者挂起，不再工作，控制流程回到单独主线程中。
3.4 Intel TBB（Threading Building Block）简介
Intel TBB 是一种用来支撑可扩展编程库，TBB 工作层次要高于裸线程，它为C + + 程序提供了丰富而完备办法来表达并行语义。TBB 指定是任务而不是线程，普通线程软件包都规定创立、汇合及管理线程。TBB 运用自己调度算法把任务分派到各个线程，高效合理地运用解决器资源。TBB 目的是通过线程来提高性能，将密集计算任务并行化，提供更高层次和更简朴解决方案，TBB 依赖泛型编程。TBB 中还支持算法模板，如基于递归区间面向循环算法，依照需求来递归地划分问题，从而获得并行任务对的层次。相比静态划分问题，递归划分问题方式更占优势。线程构建模块函数都定义在空间tbb 中，TBB 提供parallel_for 与parallel_reduce 泛型并行算法，可以负载均衡地对固定数目独立循环迭代体进行并行执行。
3.5 Cilk++简介
Cilk ++ 语言扩展了C ++ 语言来编写并行应用程序，有效地运用多解决器。Cilk + + 语言特别适合但不限于分而治之算法，把任务分解成子问题( 任务) ，可以独立地加以解决。递归函数通惯用于分而治之算法。这些任务会在不同循环迭代。Cilk ++ 核心字辨认函数调用和循环，可以并行运营。Cilk ++ 语言比较适合“二分法”算法，将问题分解成若干独立子问题，再将这些执行成果合并起来。任务既可以在不同函数里实现，也可以在一种迭代循环中完毕。Cilk ++ 核心词能有效地标记可并行执行函数调用和循环，Cilk ++ 运营环境能有效地将这些任务调度到空闲解决器上运营。
4几种应用背景下并行计算
4.1 云计算与并行计算
云计算是分布式解决、并行解决和网格计算进一步发展，是一种新兴共享基本架构技术，它可以将巨大系统池连接在一起以提供各种IT 服务。连接设备、实时数据流、SOA 采用以及搜索、开放协作、社会网络和移动商务等都是推动云计算技术发展推动因素。
云计算与并行计算相比，在应用广泛性方面，并行计算是为满足某科学领域专业需求，规定开发者具备较强技术水平，不具备较强广泛性，但云计算可以运用在较多领域，并且具备好效果。在性能方面，并行计算重要追求较高加速比，而云计算则单机计算能力规定较低，此系统通过将分散结点统一，依照相应调度算法合理调度，从而获得巨大计算能力，并且还能依照客户需求变化进行调节。
并行计算和虚拟化一起构成了云计算技术骨干。对于大型应用系统实行云计算重要内容就是实行并行计算。并行计算技术除了当前炙手可热MapReduce 以外，值得推荐尚有OpenMP、MPI 和Erlang。这3 个技术重要应用于并行程序开发， 和其她并行方略（如SOA）一起，用于从主线上实现应用并行化。中华人民共和国电信在支撑云研究、建设中，筹划在各种层面实行并行计算，以提高应用运营效率和可靠性，减少采购和运营成本。对于条件成熟应用，拟从业务并行开始，在开发层面即实现并行计算。当前，通过研究分析和测试，针对不同应用，初步制定出不同并行化解决方案，采用适当并行计算技术实现不同层次并行计算。
4.2 大图数据背景下并行计算模型及其优化技术
大数据时代背景下，数十亿顶点级别大规模图不断涌现以及云计算基本设施持续完善，推动着图数据解决研究重心由单机图算法高度优化逐渐转向分布式并行大图解决优化。当前，大图数据解决存在两种典型模式：一是采用通用海量数据分布式并行计算框架MapReduce进行解决；二是采用完全面向图构造设计专用大图计算框架。由于Mapreduce在应用定位与设计目的上重要是针对模式自由（schema-free）数据对象实现高吞吐批量解决，因而其缺少有效解决大图内部机制。相比之下，专用大图并行计算模型有针对性地考虑了图计算基本特性，因而从框架内部就已经提供了对大图解决支持，能获得较好性能。其明显特性是提供了对图计算中最常用迭代操作支持和实现了直观易用以顶点为中心编程抽象。
从存储架构上可以将大图并行计算模型分为：面向分布内存架构以及面向单机多核共享内存架构两类。在分布内存架构下，当前具备代表性大图并行计算模型有Pregel、HAMA、Giraph、Distributed GraphLab以及Trinity等。由于图构造高耦合性，分布式环境下图计算网络通信代价很高，图划分是优化分布式大图计算通信开销有效手段。某些大图解决系统采用典型划分办法，如ParMetis，也有其她某些系统摸索了新划分办法，如GraphX和PowerGraph均采用vertex-cut划分办法缓和自然图中高度数（high-degree）顶点通信集中问题；Trinity采用多层标签传递划分办法，借助图语义有效支持了十亿顶点级别大图划分；而GPS和Mizan都运用动态划分办法缓和了大图计算过程中负载失衡时顶点重分派问题。除了最棘手图划分问题外，分布式内存架构依然面临诸多困难，如需要开发者具备专门分布式编程知识在集群环境中进行复杂调试与优化工作。鉴于此，某些研究工作面向单机环境提出了有针对性优化技术，如序列化随机访问、运用多核以及新型存储高并发能力、引入异步机制等，并设计了相应大图计算模型。上述研究运用外存某些访问特性，通过有针对性优化提高解决效率，缓和大图对内存压力。此外，尚有某些基于单机图计算系统，依然假设以全内存方式进行图数据解决。虽然这些研究侧重点不在存储模式，但是在大图环境下这些研究成果实行效果也许会受到一定影响。
4.3 集群背景下并行计算
集群(Cluster)是一组互相独立服务器在网络中体现为单一系统，并以单一系统模式加以管理，以此单一系统为客户提供高可靠性服务。
在大多数模式下，集群中所有计算机拥有一种共同名称，集群内任一系统上运营服务可被所有网络客户所使用。Cluster必要可以协调管理各分离组件错误和失败，并可透明地向Cluster 中加入组件。一种Cluster 包括多台(至少2 台)拥有共享数据存储空间服务器。任何一台服务器运营一种应用时，应用数据被存储在共享数据空间内。每台服务器操作系统和应用程序文献存储在其各自本地储存空间上。Cluster 内各节点服务器通过一种内部局域网互相通信。当一台节点服务器发生故障时，这台服务器上所运营应用程序将在另一台节点服务器上被自动接管，Cluster 构造如图1 所示。

图1 Cluster体系构造
采用 Cluster 体系构造系统，具备可自由伸缩、高度可管理、高可用、高性能价格比等诸多长处，解决了跨平台管理、跨操作系统管理、系统软硬件运营状态监控等混合平台应用等技术难题，是担当大规模科学工程计算(如并行计算)坚实且抱负系统平台。
集群可以分为 3 类：高可用性集群，负载均衡集群，超级计算集群。高可用性集群重要功能是提供24 h 不间断服务；普通是由各种节点构成，当单个节点浮现故障时，系统其她节点接替服务，整个系统仍能继续正常对外提供服务。负载均衡集群将系统整体负载合理地分派到各个节点上，使得每个节点都不会由于超负荷工作而崩溃；并且系统整体负载需求不不大于系统整体负载能力时，可以通过增长系统节点，平滑地拓展系统负荷能力。超级计算集群是通过将多台机器连接起来同步解决复杂计算问题计算机群。
5关于并行计算两个简朴实验
5.1基于MPIhello word程序测试
本实验旨在测试在单机环境下基于MPI并行程序实验环境。采用是编程环境是：VC6.0和MPICH2。程序采用C++语言编写。程序源代码，见附录源代码一。
运营过程：在命令行窗口中输入：mpiexec -n 200 mpitest.exe 。 mpiexec是MPI运营库命令,-n 200表达启动200个mpitest.exe ；运营截图如下。通过观测任务管理器，发既有诸各种mpitest.exe进程。由于没有联网其她节点存在，因此200个都在本机上运营了。

图2 hello world程序运营成果图

图3 hello world程序成果局部放大图
键入命令“mpiexec -n 200 mpitest.exe ”后 ， MPI运营库接受到要并行运营200个mpitest.exe，查找临近节点，调度临近节点上mpitest.exe，（在这里测试上由于只有一种节点，因此所有一起执行了）。
5.2 数字字符串解决问题
在这一节进行是一种通过MPI和C语言编写并行程序实验，一方面对问题进行描述如下：对于任意一种给定合法数字字符串，将其各位累加求和，然后对求和得到数值进行判断，如果为一位数，则停止，如果为多位数，迭代执行上述过程，直到得到一位数为止。
实验环境：通过在VC6.0平台上配备MPICH2，然后通过C语言编写并行程序。源程序见附录源程序二。运营过程中输入输出成果如下图所示，输入数据采用txt文本输入，通过程序读入到内存。

图4 字符串解决问题输入数据文献截图

图5 字符串解决问题输出成果图
图5显示了以不同模仿解决器个数运营程序成果。在写这个并行程序时，我总结最大问题就是master processor和worker processor通信，master processor怎么将任务分派给各个worker processor，不但要注意MPI_Send和MPI_Recv数目严格匹配，还要注意MPI_Send和MPI_Recv里面参数也要严格匹配。
4总结
在当前计算机行业中，并行计算技术具备很重要地位，特别是近年来，硬件发展速度逐渐不再符合摩尔定律，其发展速度跟不上软件需求速度。因而并行计算技术无论是运用在单机还是多机，以及集群上，都具备很重要意义。近年比较热门方向，云计算和大数据，都依赖于并行计算技术实行。此外分布式计算普通与并行计算是具备紧密关联。在该课程上，我理解并学习了分布式并行计算领域有关知识，虽然自己研究方向不是课程方向，但是自己兴趣编程和算法，可以在实验中，进行并行计算方面简朴实验，我觉得自己收获很大。
道谢 感谢刘教师辛勤教学，以及同窗们给我在学习和报告中参照意见.

参照文献
[1] 杨学军. 并行计算六十年[J]. 计算机工程与科学，，34(8):1-10.
[2] 王之元，杨学军，周云，等. 大规模MPI并行计算可拓展三模冗余容错机制[J]软件学报，，4,23(4):1023-1035.
[3] 郑文武，李光绪，黄执勤. 云计算中并行计算技术分析[J]. 电信科学. ,12:31-37.
[4] 潘巍，李战怀. 大数据环境下并行计算模型研究进展[J]. 华东师范大学学报（自然科学版），201. 9,5:44-49.
[5] 王庆先，孙世新，尚明生，刘彦兵. 并行计算模型研究[J]. 计算机科学,. 31（9）：128-130.
[6] 陈国良，苗乾坤，孙广中，徐云，郑启龙. 分层并行计算模型[J]. 中华人民共和国科学技术大学学报，，38（7）:841-846.
[7] 王海涛. 刘淑芬. 基于Linux集群并行计算[J]. 计算机工程. ,36(1):64-66.
[8] 卢风顺，宋君强，银福康，张理论 ，CPU/GPU协同并行计算研究综述，,3,38(3)：5-9.
[9] 蔡勇，李光耀，王琥，GPU通用计算平台上中心差分格式显式有限元并行计算[J]. 计算机研究与发展，,50(2)：413-418.
[10] zhaolong Ning，Qingyang Song，Yejun Liu，Fanzhao Wang，Xinyu Wu.. Markov-based vertical handoff decision algorithms in heterogeneous wireless networks[J]. Computers and Electrical Engineering，,40:456-472.
[11] Jin Zhu,Limin Xu，Lin Yang，Wangqing Xie. An Optimal Vertical Handoff Decision Algorithm for Multiple Services with Different Priorities in Heterogeneous Wireless Networks[J]. Wireless Pers Commun，,83:530-534.
[12] Rong Chai，Huili Zhang，Xiaoyu Dong，Qianbin Chen，Tommy Svensson. Optimal joint utility based load balancing algorithm for heterogeneous wireless networks[J]. Wireless Netw，.1.31.