高性能并行计算初步(整理)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
高性能并行计算初步(整理)
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
你可能喜欢关于高性能计算（并行计算）的知识记录汇总（OpenMP、OpenCL、CUDA、tbb）
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
关于高性能计算的知识记录汇总
MPI和openMPI的区别，或者CUDA和OpenCL的区别，这篇文章就是为了总结下高性能计算的相关知识。目前高性能计算有两大趋势，并行计算集群和CPU处理器GPU显卡的异构混合计算。下面做对这些名词进行一个简单的介绍：
MPI-Message Passing
Interface是一个并行计算的API，适合超级电脑，大规模集群。
OpenMPI是一种高性能消息传递库，可以很方便的把串行程序，改为多线程并行程序，适合多核心电脑，可以和MPI搭配使用，对C语言和Fortran高性能计算支持很好。
TBB-Intel Threading Building Blocks
线程构建模块，是Intel公司开发的并行编程开发的工具,能很好的支持C++并行计算编程。
CUDA(Compute Unified Device
Architecture)，显卡厂商NVidia推出的运算平台，使用显卡和处理器进行异构并行计算，是比较高级的并行开发工具，不需要太多硬件知识。
OpenCL&(Open
Computing Language)
是一个为异构平台编写程序的框架，属于API，和OpenGL架构类似，此异构平台可由CPU，GPU或其他类型的处理器组成。
最近花了点时间，对，，MPI（有多种实现，如）等，关于高性能计算的技术，做了一下简单的浏览，我把这次简单浏览所学习到的一点东西记录在此。这些总结和记录都比较半吊子，还需要更深入的学习和研究。
首先，时下越来越热的GPU计算，随着中国天津的大型计算机拿到国际头把运算力交椅，不得不让人重视。现有的技术，从阵营上分，有NVidia的，AMD(ATI)的。还有一个开放标准：。我是比较看好OpenCL的，因为他可以支持同时对不同品牌，不同核心CPU和GPU的优化和加速，特别适合异构环境。他的基本原理就是系统里边内置一个类似编译器，好像llvm,API的东西，软件写完的代码只有到最后的硬件执行的时候进行最终编译，这个编译过程似乎是通过系统里边的硬件驱动Driver，现在都还需要另外安装，，，提供的sdk中都分别包含有自己Driver，得以执行。所以OpenCL的程序主线程，会根据系统中是几个核的多核CPU，那种架构的CPU（arm或者x86），有没有GPU，哪种GPU?
来决定最后生成的工作线程的代码传递给哪个Driver编译执行。系统会自动保存编译后的二进制代码以备后用。这个过程看起来好像是一个动态语言的过程，但是实际上现在OpenCL还主要是底层的，经过扩展的c语言来写。不同硬件的Driver充当了runtime的角色。
intel,nvidia,amd等多家硬件厂商支持OpenCL，但是同时也有自己的小九九，比如nvidia的cuda，就提供了针对自己的更多的功能，而且函数上据说也更为高级。所以说，如果是专门针对特定硬件环境下，比如开发大运算量的科学程序的话，最好使用专门硬件自己的GPU加速sdk开发。只有在要求通用性，比如商业软件上，才使用OpenCL开发。
另外，一贯讨厌开放标准的微软这次又和当年对待OpenGL一样，用他的DirectorX来玩个性了。反正我是能不鸟他，就不鸟他！
其次，OpenMP和MPI，这两个都是已经被广泛使用的并行程序开发库。他们的区别是：OpenMP是针对多核处理器，使用的是共享内存的并行方式，可以说更为线程一些；MPI是针对服务器中，多个对称并行CPU或者集群服务器的情况，内容共享方式是混合的，更为进程一些。
从某种角度上说，OpenCL有代替OpenMP的可能和趋势，里边会包含针对多核心CPU的处理。现在的环境下，还是OpenMP更合适——可以直接发挥多核心处理器的能力，而且不需要图形开发的知识。是一篇关于OpenMP和OpenCL性能的测试。
&&&&现在的并行开发，主要就是MPI+OpenMP，前者负责将运算通过进程分布到不同服务器的不同CPU上去，后者负责通过多线程，有效利用CPU中每个核心的效能。
再次，有文章显示，为了最好的发挥线程的效能，在同样算法条件下，，而且。GPU对某些计算加速效果特别好，效率也不错，但是由于必须通过PCI用CPU进行调度，所以，实际程序设计的时候，要。
最后，现有的几种并行计算技术：
1、系统层面，使用进程迁移技术，从而让所有支持多进程的程序，实现并行，如openmosix，这需要经过patch过的操作系统；
2、硬件层面，也就是OpenCL等GPU加速技术，需要相应的硬件支持；
3、开发语言方面，现在这种动态语言，就提供了对集群环境的支持，他会自动向加入集群的服务器分布运算进程。语言可能也是类似的。
开发方面，OpenCL现在用起来门槛还是很高的，不知道以后会不会提供更高层的抽象库。不过，我发现QT，现在可以支持OpenCL了，虽然还没有放入主枝，需要自己编译开发包，但是文档上说，提供了QT模式的函数。QT在被诺基亚收购之后，改变授权为lgpl，加上技术越来越全面，的确成了一个跨平台开发很好的解决方案了。真眼馋。
里边有OpenCL的新闻。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。计算机并行计算的基本问题及现状
　　工作中，我们总是希望我们自己工作得更有效率，用更少的时间解决更多的问题。在计算机里，这就是并行计算的基本初衷。全世界第一台计算机ENIAC中就己经出现了并行计算的概念。它有20个累加器，可以并发执行多个加减运算，可谓开并行计算的先河。在随后的20世纪五六十年代，由于晶体管和集成电器的发明，出现了更多更快的计算机。IBM是这一时期的主角，同期计算机编程语言的出现，由软件完成处理并行计算的思想进一步深化。但这一时期的计算还是大型机时代，没有几个平民能用得起这些昂贵的东西。计算机和软件技术还锁在研究院和大学校园里。
　　20世纪70年代，随着微电子技术的发展，出现了微型处理器(CPU)接着,1974年，全世界第一台个人电脑&牛郎星顺利出炉。紧随其后，看到市场前景的苹果和IBM推波助澜，计算机开始进入个人时代。个人计算机同时又催生了软件业的高速发展，软件又带动CPU不断升级换代。这为并行计算摆脱高端路线，进入平民化时代打下了基础。
　　1并行计算的基本问题
　　1.1为什么需要并行计算
　　在个人计算机诞生后的几十年里，程序员们编写了大量的应用软件，这些软件决大部分了采用串行计算方法。所谓串行，是指软件在PC上执行，在进入CPU前被分解为一个个指令，指令在CPU中一条条顺序执行。任一时间内，CPU只能够运行一条指令。这种方式很符合我们对现实世界的思考习惯。至于软件的运行速度，则依赖硬件的处理能力，尤其CPU的处理速度。这种思维方式到了2005年遇到了挑战。在那一年，受限于制造CPU的半导体材料限制，左右CPU发展的摩尔定律开始失效了。但芯片业很快找到了一个变通的办法:在一块芯片中植入多个处理核心，通过多核的共同运算，提高运行速度。不幸的是，采用串行方法编写的软件面临着一个尴尬的局面:如果仍采用串行编程方式，运行速度将停滞不前。这样，原来需要CPU完成的提速工作，被迫需要软件自己来完成。在另一个领域:互联网，由于网络数据极速膨胀，数据量己经远远超过一台或者几台大型计算机的处理能力，需要更大数量的计算机协同完成。面对这些问题，主要的解决方案就是:并行计算。
　　1.2并行计算的涵义
　　并行计算目前还是一门发展中的学科。并行计算是相对串行计算而言的，并行计算可以分为时间上的并行计算和空间上的并行计算。
　　时间上的并行计算就是流水线技术，即采用指令预取技术，将每个指令分成多步，各步间叠加操作，当前指令完成前，后一指令准备就绪，缩小指令执行的时钟周期。典型的以时间换空间。
　　空间上的并行计算是指由多个处理单元(不仅是CPU)执行的计算，是以空间换时间。空间上的并行计算分为两类:单指令多数据流(SIMD)和多指令多数据流(MIMD)
　　SIMD是流水技术的扩展，可以在一个时钟周期处理多个指令，我们目前使用的PC大多属于此列，例如AMD 3DNOW和Intel MMX。
　　MIMD大致又分为5类:工作站集群 (COW)。对称多处理机(SMP)。大规模并行处理机(MPP)。分布共享存储处理机(DSM ) ,并行向量机(PVP)。
　　空间并行计算技术包括数据并行计算和任务并行计算。数据并行计算是指将一个大的数据分解为多个小的数据，分散到多个处理单元执行。任务并行是将大的任务分解为小的任务，分散到多个处理单元执行，任务并行同时还要避免任务重复执行，协调数据的上下文关系，避免冲突发生。任务并行计算与实际应用需求紧密相关。所以，任务并行计算要比数据并行计算复杂得多。并行计算与串行计算的最大不同在于，并行计算不仅要考虑计算本身，还要考虑并行处理模型。网络通信。计算协作诸多问题。
　　1.3主要的并行计算体系类型
　　1.3.1工作站集群(COW Cluster of Workstation)
　　工作站集群可以理解为:PC+网络。它可以由少数几台PC扩展到数千个节点的大规模并行系统，既可以是廉价的并行程序调试环境，也可以成为的高性能计算平台。集群由于低成本，动态可扩充的特点，己经成为高性能计算平台的主流。目前Google搜索和云计算业务即采用这一方式。我国的联想深腾XXXX,曙光XXXX系列均属此类。
　　1.3.2多处理系统(SMP Symmetric Multi Processing)
　　它由多个紧耦合多处理器组成，最大特点就是共享全部资源。
　　1.3.3大规模并行处理系统(MPP Massively Parallel Processing)
　　由许多松祸合处理单元(不是处理器)组成的。这种结构与SMP对立，每个单元自成体系，包括CPU。内存。硬盘。操作系统，最大特点是不共享资源。刀片服务器属于此列。
　　1.3.4分布式共享存储多处理(DSM)
　　它可以视为对SMP的可扩充，将共享数据映射到不同的物理位置。数据的同步由硬件或者软件来完成。是目前高性能计算机的主流发展方向之一。
　　1.3.5并行向量机(PVP ,Parallel Vector Processor )
　　PVP使用专用的向量处理器，提供数据共享，通过高速交叉开关实现通信。向量运算是一种较简单的并行计算，适用面很广，机器比较容易实现，使用也方便，因此向量处理机(向量机)在20世纪70年代获得了迅速发展。
　　1.4并行计算的处理模式
　　1.4.1主从模型( MS , Master-slave )
　　即有一个主进程，其他是从进程。主进程负责整个系统的控制(包括任务调度。负载平衡)，从进程负责对数据的处理和计算任务。Google搜索业务目前就是采用的这种编程模型。
　　1.4.2对称处理模型(SPM)
　　这种架构没有主从概念之分，所有进程的地位都是平等的。在并行执行过程中，我们可以任意选择其中一个进程执行输入输出操作，其他进程扮演同样的角色。
　　1.4.3多程序处理模型( MPPM )
　　在计算机集群中，每台计算机节点执行不同的程序和相同的程序。
　　1.5并行计算设计原则
　　(1)适应性。并行算法是并行计算的基础，是为解决实际问题而出现，必须与实际应用相结合。
　　(2)可扩展。并行算法是否能够随计算节点增加或减少而同步的线性变化，是评价一个并行算法是否有效的重要标志之一。
　　(3)粗粒度。通常情况下，粒度越大越好。这是因为在每个处理机中有很多需要计算的工作任务，如此可以充分发挥多处理机的作用。并行加速比对细粒度问题一般情况下是不会很高的，这也是为什么并行计算需要求解大规模问题的原因所在。
　　(4)减少通信。一个高效的并行算法，通信是至关。提高性能的一个关键是减少数据通信量和通信次数。
　　(5)优化性能。评价性能的优缺，主要是看单节点计算的处理能力，和并行执行效率。这与实际采用的技术息息相关。
　　1.6并行计算设计方法
　　1.6.1分片
　　(1)数据分片。数据分片包括两类:数值分片和哈希分片。数值分片适用于己知数据范围的分解，如果Int,Long类型处理。哈希分片适用于未知数据范围的数据分解，包括字符串，字节数组类型。
　　数据分片是把相同的操作作用于不同的数据，达到提到快速求解的目的。数据分片模型是一种较高层次的并行计算模型，编程却相对简单。数据分片的并行计算最早应用于并行向量计算机(PVP))经过长期实践表明，该技术可以高效地求解大部分的科学和工程计算问题。数据并行处理对象是数值，对应非数值类问题，则需要其他并行计算模型来解决。Google的搜索业务是采用数据分片的并行计算模式。
　　(2)任务分片。任务分片的并行计算主要针对非数值类的并行处理。它通常的消息传递机制(目前主流是PMI是各并行计算执行单元之间通过传递消息来交换数据，协调步伐，执行控制操作。消息传递一般是针对分布节点内存，也可以适用于共享内存的并行节点。消息传递模型为程序员提供了更加灵活的控制手段和表现形式。消息传递模型很容易实现，控制变化手段灵活多样，但是需要程序员有丰富的并行编程经验。是一种较低层次，编程相对复杂的模型，适用于业务流程的并行化处理。
　　1.6.2通信
　　协调计算过程中的数据共享。通信工作目前主要由TCP/IP协议完成。
　　1.6.3组织
　　组织各任务并发执行，提高性能。在主线程的控制下，子线程在此承担具体的并发操作任务。
　　1.6.4映射
　　分配任务(分布处理。共享处理)。线程和通信共同完成。1.7并行计算应注意的事项
　　(1)任务分解:这是所有并行计算的核心问题，优秀的任务分解需要保证平均和处理负载的平衡，同时，随着处理器能力的动态伸缩动态调节。
　　(2)通信:并发处理离不开网络通信联系。相较与CPU运算，数据在网络间传递延迟是并发处理的瓶颈之一。光纤网络是目前最好的选择。
　　(3)并行协调:是并行运算过程中控制流程。
　　(4)并行冲突:并行冲突来源主要是任务分解和并行协调。
　　(5)数据归并:这是数据计算完成后，必不可少的一步操作。数据归并需要注意:过滤重复数据，合并相关性数据等。
　　(6)死锁。死锁是在编程过程中，由于人为的原因造成。死锁表示为:对象间在不放弃自己资源下互相调用。请程序员注意。
　　2并行计算的发展现状
　　2.1多核为主流的体系结构
　　多核处理器代表了计算技术的一次创新。由于数字数据和互联网的全球化，商业和消费者开始要求多核处理器带来性能改进，这个重要创新就开始了，因为多核处理器比单核处理器具有性能和效率优势，多核处理器将会成为被广泛采用的计算模型。在驱动PC安全性和虚拟化技术的重大进程过程中，多核处理器扮演着中心作用，这些安全性和虚拟化技术的开发用于为商业计算市场提供更大的安全性。更好的资源利用率。创造更大价值。普通消费者用户也期望得到前所未有的性能，这将极大地扩展其家庭PC和数字媒体计算系统的使用。多核处理器具有不增加功耗而提高性能的好处，实现更大的性能/能耗比。
　　在一个处理器中放入两个或多个功能强大的计算核产生了一个重大的可能性。由于多核处理器能提供比单核处理器更好的性能和效率，下一代的软件应用程序很有可能是基于多核处理器而开发的。不管这些应用是帮助专业的电影公司以更少的投入和更少的时间完成更真实的电影，还是以更彻底的方法使得PC更自然和直观，多核处理器技术将永远改变计算世界。多核处理器表达了AMD了解顾客需求并且开发最能满足客户要求产品的意愿。
　　微软多核计算的主管Dan Reed称，整个世界上很缺乏那些并行计算的研究人员，而一个间接的原因就是学院里对于并行计算的关注度不够，而这些学院正是下一代软件开发人员诞生的地方。越来越高的时钟频率导致应用程序的代码运行得越来越快，而对于当前多核处理器来讲这一规则虽然成立，但却有所不同。而这种不同可以做一个形象的比喻，那就是一部跑车和一辆学校的巴士。当跑车能够以很快的速度飞奔时，巴士虽然比较慢，但它可以载着更多的人前行。问题就是，简单地在计算机CPU上增加多个核并不能增加传统应用程序代码的运行速度，这一结果是根据一项来自于Forrester研究公司的报告得出的。换句话说，复杂的工作需要拆分来填充这辆巴士上的空座位。Forrester的报告还谈到:当前四核处理器会激发更多的多处理器设计的思想，2009年x86的服务器使用64个处理器核，并且2012年台式机也己实现了这一梦想。
　　2.2以数据为中心的云计算
　　云计算可以被解释为虚拟主机的租赁服务，也可以被解释为企业软件的SaaS化，又或者是一个&云机箱&之上跑许多个虚拟桌面。但不管怎么说笔者认为云计算要解决3个实质问题:
　　(1)大规模。这里提到的大规模不仅是超过单台PC服务器的能力，更指的是能够支撑互联网级别的数据和应用，例如个人邮箱。搜索等。
　　(2)低成本。低成本的一个标志在于用系统软件来解决廉价硬件在复杂条件下不可靠的问题。
　　(3)服务运营。这里所指的服务运营是能够通过无差别的存储计算能力来提供公共的基础服务。
　　当各式各样的应用可以共同运行在一个统一平台之上，才能达到真正的大规模，而由此得到的规模效益才能够获得低成本，于是这3个本质的问题是云计算的有机整体。
　　传统的软件以功能为主体，而云计算则彻底推动了&数据为土&。数据将成为一家企业乃至是一个国家极其重要的战略资源。而数据的搜集。存储。分享。处理和应用是需要大量的计算资源的，从这个意义上说，云计算可以称为&以数据为中心的分布式大规模计算&。而一个企业乃至一个国家瞬间能够调用的计算资源则成为了能否利用和发挥好数据这个战略资源的核心竞争力。提供公共计算服务的云计算平台将大大促进企业之间。社会各行业间的数据收集。分享和实时处理，在这基础之上必将孕育出大量的数据运营的新商业模式，数据也将最终成为一切商业行为的决策基础，从而大大提高社会的整体效率，促进人类从大工业化时代走向信息化时代。
　　2.3以普及应用为宗旨的个人高性能计算机
　　作为三大科学研究手段之一的高性能计算机，其发展的根本动力来自于各类科学技术对计算机性能永无止境的需求和生产的实际需要。
　　在1996年的&SuperComputing&96&大会上，美国政府HPCC计划全国协调委员会主席John Toole在题为&危机。创新与机会:HPCC将向何处去&的报告中指出:&高性能计算与通信对美国的国家安全及保持美国在未来的优势至关重要。美国政府将在高端计算机与通信。大规模网络。高可信系统等5个方面制定10~15年的长期计划，保持长期持续性投资。&
　　过去的10年是超级计算机。特别是并行机飞速发展。走向成熟的10年。10年中CPU芯片的性能翻了几番，计算机工作者发明了Wormhole(虫蚀寻径)技术，找到了更符合实际的LogP并行计算模型，创造了成百的不同规模。不同拓扑结构的并行平台。特别是，由于多种软硬件技术的进步，使既具有可扩展性。又具有可编程性的。分布式共享存贮结构的并行机成为可能。并行计算机是当今超级计算机的主流。
　　并行计算机的发展史就是可扩展性与可编程性这一对矛盾相互作用直至统一的历史。可扩展性是并行计算机最大的优势，可简单定义为&在确定的应用背景下，计算机系统的性能要随处理机数的增加而线性增长&(美籍并行处理专家黄恺教授语)。可扩展性包括规模可扩展。时间可扩展和问题可扩展几个方面。规模可扩展的要点是均衡，均衡的目的是防止瓶颈的发生，&三T&表达了当今均衡的指标。时间可扩展也称换代可扩展，主要指体系不受限于芯片。器件。工艺等。问题可扩展指格点增加时，系统能适应问题规模的扩大，而当问题的粒度加大时，效率能相应提高。现有的MPP，如Inetl的Paragon ,IBM的SP/2。国内的曙光1000，一般认为是可以扩展的。
　　可编程性是在并行机发展的过程中，伴随可扩展性而产生的新概念。并行计算机有共享与分布式两种存储结构，所以操作系统进程间的通信(IPC)也有两种不同的机制:共享变量和信息传递。机器结构和操作系统的这些区别又影响到支撑软件和应用软件的编程模式。SMP的程序设计仍以传统的高级语言为基础，系统提供自动并行识别或增加并行语言成分。而MPP必须建立另一种编程环境(如PVM , MPI等)，在程序中显式地写出信息的发送和接收。这不仅导致应用软件编写困难，还给广大用户增加了很多负担。为此，创建了一个新的单词Programmability，用以描述并行计算机的这一重要特点。
　　高性能计算机己走过了整整20年，这是一段可扩展性与可编程性这一对矛盾相互作用直至统一的历史。市场需求是发展的动力，技术进步是发展的条件。有专家估计，从现在起直到21世纪若干年，DSM结构将是超级计算机的主流，将稳固地占领超级计算机的主要市场。
　　3并行计算的发展&机群系统
　　机群系统是利用高速通用网络将一组高性能工作站或高档PC机，按某种结构连接起来，在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。从结构和结点间的通信方式来看，它属于分布存储系统。机群系统中的主机和网络可以是同构的，也可以是异构的。机群系统之所以能够从技术可能发展到实际应用，主要原因是它与传统的并行处理系统相比有以下几个明显的特点:
　　(1)系统开发周期短。由于机群系统大多采用商用工作站和通用LAN网络，节省了大量的研制时间。
　　(2)系统价格低。构成机群的工作站或高档PC机是批量生产的，因而售价较低。
　　(3)用户投资风险小。机群系统不仅是一个并行处理系统，它的每个结点同时也是一台独立的工作站，即使整个系统对某些应用问题并行效率不高，它的结点仍然可以作为单个工作站使用。
　　(4)系统扩展性好。机群系统大多使用通用网络，系统扩展容易。
　　(5)节约系统资源。由于机群系统的结构比较灵活，可以将不同体系结构，不同性能的工作站连在一起，这样就可以充分利用现有设备。
　　(6)用户编程方便。机群系统中，程序的并行化还是在用户熟悉的编程环境C ,C++或Fortran下实现的。
　　总之，随着网络技术的发展和对机群系统研究的深入，特别是高效通信机制的开发，机群系统的通信性能将会接近专用的互联网络，并行编程环境和工具更加完善，有望在机群系统上解决粒度更细的应用问题，使并行处理系统的应用领域更加广泛。
　　4结束语
　　并行计算目前尚不是一门成熟的技术，有待我们继续努力和完善。受到CPU单核处理能力的限制，必须采用并行计算是提高软件运行速度的主要出路。但是由于并行编码的难度远超过串行处理，这是我们面临的巨大挑战。共同努力!
0引言 当前，随着世界经济形势和地缘政治因素的影响，我国而临的战争风险越来越大。由于科学技术水平的显著提升，各国...
电连接器是现代各类电子系统中器件与器件、组件与组件、系统与系统之间进行电气连接、信号和能量传递所必须的基础元件...
贵州省是航天航空产品生产研发基地集中地区。近年来，随着先进制造业引进涌入，对材料学科专业相关从业人员的需求量大...
一部法律的基本原则是该法律的精神的集中体现，决定该法律的价值取向和主要内容，它对法律的制定具有指导意义，对法律...
0引言 我国有三分之一的城市居民将商业医疗保险列为首选，比例超过养老保险、人寿保险和人身意外伤害保险，可见，随着...
引言 随着互联网的普及和信息技术的进步，电子商务以其快捷、高效等显著优势得到快速发展，主要有B2B ( Business to busines...
《国家中长期教育改革和发展规划纲要()》和《教育部关于大力推进高等学校创新创业教育和大学生自主创业工作的意...
明清时期，随着封建商品经济的发展，资本主义的萌芽开始出现。尤其是明末至清代，由于农业经济的商品化和工商业的发展...
在高校思政课教学中，理论教学是主要的教学形式，实现教学目的只有理论教学是远远不够的。实践教学是可以帮助完成教学...
玛丽亚蒙台梭利(Maria Montessori,)，意大利第一位医学女博士，是西方历史上继福禄贝尔之后的又一位杰出的幼儿教育家...
对话视域下的小学数学课堂，关注学生的问题意识，以问题的视角设计教学流程，强调以问题为主线、以问题为载体来设计教...
《古代文学史》是高专语文教育专业的一门专业核心课，其主要的教学目标是使学生能够把握古代文学发展的基本轮廓，掌握...并行计算基础 - 推酷
并行计算基础
并行计算是一门交叉学科，涵盖的内容非常广泛，包括并行机体系结构、编译系统、并行算法、并行编程、并行软件技术、并行性能优化与评价、并行应用等。从交叉学科的角度，并行计算可以定义为连接并行机系统和实际应用的桥梁。
并行计算（parallel computing）
是指，在并行机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加速求解速度，或者求解应用问题规模的目的。
由此，为了成功开展并行计算，必须具备三个基本条件：
1、并行机。并行机至少包含两台或两台以上处理机，这些处理机通过互连网络相互连接，相互通信。
2、应用问题必须具有并行度。也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计。
3、并行编程。在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的。
并行计算技术的主要目的
在于两个方面：
1、加速求解问题的速度。例如100台处理器的并行计算可比单处理器加速50倍。
2、提高求解问题的规模。例如100个处理器的并行计算可将问题求解规模线性地扩大100倍。
由并行计算的三个必备条件可知，
并行计算的主要研究内容
大致可分为四个方面：
1、并行机的高性能特征抽取。主要任务在于，充分理解和抽取当前并行机体系结构的高性能特征，提出实用的并行计算模型和并行性能评价方法，指导并行算法的设计和并行程序的实现。
2、并行算法设计与分析。针对应用领域专家求解各类应用问题的离散计算方法，设计高效率的并行算法，将应用问题分解为可并行计算的多个子任务，并具体分析这些算法的可行性和效果。
3、并行实现技术，主要包含并行程序设计和并行性能优化。基于并行机提供的并行编程环境，例如消息传递平台MPI或者共享存储平台OpenMP，具体实现并行算法，研制求解应用问题的并行程序。同时，结合并行机的高性能特征和实际应用的特点，不断优化并行程序的性能。
4、并行应用。这是并行计算研究的最终目的。通过验证和确认并行程序的正确性和效率，进一步将程序发展为并行应用软件，应用于求解实际问题。同时，结合实际应用出现的各种问题，不断地改进并行算法和并行程序。一个没有经过实际应用验证和确认的算法和程序，不能说是一个好的算法和程序。
并行计算不同于分布式计算（distributed computing）。
后者主要指，通过网络相互连接的两个以个的处理机相互协调，各自执行相互依赖的不同应用，从而达到协调资源访问，提高资源使用效率的目的。但是，它无法达到并行计算所倡导的提高求解同一个应用的速度，或者提高求解同一个应用的问题规模的目的。对于一些复杂应用系统，分布式计算和并行计算通常相互配合，既要通过分布式计算协调不同应用之间的关系，又要通过并行计算提高单个应用的能力。
从体系结构的角度，当前
并行机的体系结构
可分为如下三类：
机群（cluster）
。它有三个明显的特征：
a、系统由商用结点构成，每个结点包含2～4个商用微处理器，结点内部共享存储。
b、采用商用机群交换机连接结点，结点间分布存储。
c、在各个结点上，采用机群Linux操作系统、GNU编译系统和作业管理系统。
星群（constellation）
。它们也有三个明显的特征：
a、系统由结点构成，每个结点是一台共享存储或者分布共享存储的并行机子系统，包含数十、数百、乃至上千个微处理器，计算功能强大。
b、采用商用机群交换机连接结点，结点间分布存储。
c、在各个结点上，运行专用的结点操作系统、编译系统和作业管理系统。
大规模并行机系统（MPP：Massively Parallel Processing）
。它们的主要特征为：
a、系统由结点构成，每个结点含10个左右处理器，共享存储。处理器采用专用或者商用CPU。
b、采用专用高性能网络互连，结点间分布存储。
c、系统运行专用操作系统、编译系统和作业管理系统。
此类系统是传统意义的大规模并行处理系统。它区别于其他两种体系结构的一个特征就是，它的处理器或者结点间的互连网络是针对应用需求而特殊定制的，在某种程度上，带有专用并行机的特点。
组成并行机的三个要素
1、结点（node）。每个结点由多个处理器构成，可以直接输入输出（I／O）。
2、互联网络（interconnect network）。所有结点通过互联网络相互连接相互通信。
3、内存（memory）。内存由多个存储模块组成，这些可以与结点对称地分布在互联网络的两侧，或者位于各个节点的内部。
是构成并行机的最基本单位。一个结点包含2个或2个以上微处理器（CPU），并行程序执行时，程序分派的各个进程将并行地运行在结点的各个微处理器上。每个微处理器拥有局部的二级高速缓存（L2 cache）。
在结点内部，多个微处理器通过集线器（HUB）相互连接，并共享连接在集线器上的内存模块和I／O模块，以及路由器（router）。当处理器个数较少时，例如8～16个以内，集线器一般采用高速全交互交叉开关，或者高带宽总线完成；如果处理器个数较多，例如数十个，则集线器就等同于并行机的互联网络。
是连接所有结点成并行机的高速网络。对于一般的并行机使用者，无须知道互联网络底层复杂的通信原理，而只需从拓扑结构的角度了解互联网络。
互联网络的拓扑结构
可用无向图表示。其中，图中的结点唯一地代表并行机的各个结点，图中的边表示在两个端点代表的并行机结点之间，存在直接连接的物理通信通道。
互联网络拓扑结构的几个重要定义
1、并行机规模：并行机包含的结点总数，或者包含的CPU总数。
2、结点的度：拓扑结构图中，以某个结点为端点的边的条数，称为该结点的度。结点的度表示，存在多少个结点，与该结点有直接的物理连接通道。
3、结点距离：两个结点之间跨越的图的边的最少条数。
4、网络直径：网络中任意两个结点之间的最长距离。
5、点对点带宽：图中边对应的两个结点之间相互连接的物理通道的通信带宽。
6、点对点延迟：图中任意两个结点之间的一个零长度消息传递必须花费的时间。延迟与结点间距离相关，其中所有结点之间的最小延迟称为网络的最小延迟，所有结点之间的最大延迟称为网络的最大延迟。
7、折半宽度（对分带宽）：对分图成相同规模的两个子图（它们的结点数相等，或者至多相差1）时，必须去掉的边的最少条数。或者，这些边对应的网络点对点带宽的最小总和。
8、总通信带宽：所有边对应的网络通信带宽之和。
显然，评价一个互联网络的基本准则应该为：固定并行机包含的结点个数，如果点对点带宽越高、折半宽度越大、或者网络直径越小、点对点延迟越小，则互联网络质量可以说越高。
按节点间连接的性质，
拓扑结构可分为三类
静态拓扑结构
如果结点之间存在固定的物理连接，且在程序的执行过程中，结点间的连接方式不变，则称该并行机的互联网络拓扑结构是静态的。拓扑结构中，如果两个结点之间存在直接物理连接，则称之互为相邻结点。当前并行机采用的各类静态拓扑结构包括阵列（array）、环（ring）、网格（mesh）、网格环（torus，也叫环面）、树（tree）、超立方体（hypercube）、蝶网（butterfly）、Benes网等。
动态拓扑结构：
结点之间无固定的物理连接，而是在连接路径的交叉点处用电子开关、路由器或仲裁器等提供动态连接，主要包含单一总线、多层总线、交叉开关、多级互联网络（MIN：Multistage Interconnection Network）等类型。
宽带互联网络：
随着网络技术的成熟，商用宽带互联网络逐步成为连接微机而构成简易并行机的互联网络，并且，相继推出了专用于微机机群的宽带交换机。它们的出现，极大地丰富了并行机的市场，简化了并行机的研制难度，大幅度降低了并行机的成本，使得微机机群成为科研经费较少的研究所和大学的可用并行机系统。当前除了专用MPP系统采用静态的拓扑结构外，微机机群均采用宽带互联网络连接各个计算结点。几个典型的代表有：以太网（Ethernet）、商用交换机（switch）、专用微机机群互联网络。
根据Moore定律，峰值运算速度每18个月翻一番。同时，内存模块的容量以每年几乎翻一番的速度发展。但是，内存的访问速度要比处理器执行速度慢很多，难以发挥微处理器的峰值速度，这就是所谓的内存墙（memory wall）性能瓶颈问题。为此，引入了
多级存储体系结构
。从上层往下依次为：CPU、寄存器、L1 Cache、L2 Cache、局部内存、以及远程内存（其它结点的局部内存模块）。
根据内存访问的性质，
并行机的访存模型可以分为四类
均匀访存模型。
内存模块与结点分离，分别位于互联网络的两侧，互联网络一般采用系统总线、交叉开关或多级网络，称之为紧耦合系统（tightly coupled system）。该模型具有如下典型特征：
a、物理存储器被所有结点共享；
b、所有结点访问任意存储单元的时间相同；
c、发生访存竞争时，仲裁策略平等对待每个结点，即每个结点机会均等；
d、各结点的CPU可带有局部私有高速缓存（cache）；
e、外围I／O设备也可以共享，且每个结点有平等的访问权利。
当前对称多处理共享存储并行机（SMP：Symmetric Multi-Processing）均采用这种模型。
非均匀访存模型
内存模块局部在各个结点内部，所有局部内存模块构成并行机的全局内存模块。并行机的内存模块在物理上是分布的，但是，在逻辑上是全局共享的。非均匀访存模型也可称为分布共享访存模型。该模型具有如下典型特征：
a、物理存储器被所有结点共享，任意结点可以直接访问任意内存模块；
b、结点访问内存模块的速度不同：访问本地存储模块的速度一般是访问其他结点内存模块的3倍以上；
c、发生访存竞争时，仲裁策略对结点可能是不等价的；
d、各结点的CPU可带有局部私有高速缓存（cache）；
e、外围I／O设备也可以共享，但对各结点是不等价的。
非均匀访存模型的典型例子为SGI Origin系列并行机，它们采用基于cache目录一致性的非均匀访存模型（CC-NUMA：Cache-Coherent Nonuniform Memory Access），设计了专门的硬件，保证在任意时刻，各结点cache中数据与全局内存数据的一致性。
分布访访存模型
与非均匀访存模型的物理分布相同。不同的是，各个结点的存储模块只能被局部CPU访问，对其它结点的内存访问只能通过消息传递程序设计来实现。一般地，每个结点均是一台由处理器、存储器、I／O设备组成的计算机。当前的MPP并行机各个结点之间，或者微机机群各个结点之间，均是这种访存模型。
混合访存模型
这是前3类访存模型的优化组合。典型的星群系统中，每个结点内部是均匀模型或者非均匀访存模型，结点之间是分布访存模型。当前MPP系统中，大多采用混合访存模型。
按经典的指令与数据流进行分类，并行机可以分为三类
1、单指令多数据流（SIMD）：按同一条指令，并行机的各个不同的功能部件同时对不同的数据进行不同的处理。目前，这类并行机已经退出历史舞台。
2、多指令多数据流（MIMD）：不同的处理器可同时对不同的数据执行不同的指令，目前所有并行机均属于这一类。
3、多指令单数据流（MISD）：至今没有出现。
按内存访问模型、微处理器和互联网络的不同，当前流行的并行机可分为五类
1、对称多处理共享存储并行机（SMP）：
内存模块和处理器对称地分布在互联网络的两侧，内存访问属典型的均匀访问模型。SMP并行机有如下主要特征：
a、对称共享存储：系统中任何处理器均可直接访问任何存储模块中的存储单元和I／O模块，且访问的延迟、带宽和访问成功的概率是一致的。所有内存单元统一编址。各个处理器之间的地位等价，不存在任何特权处理器。操作系统可在任意处理器上运行。
b、单一的操作系统映像：全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地分配各个进程到各个处理器，并保持各处理器间的负载平衡。
c、局部高速缓存cache及其数据一致性：每个处理器均配备局部cache，它们可以拥有独立的局部数据，但是这些数据必须与存储器中的数据保持一致。
d、低通信延迟：各个进程通过读／写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信的延迟。
e、共享总线带宽：所有处理器共享总线的带宽，完成对内存模块和I／O模块的访问。
f、支持消息传递、共享存储并行程序设计。
SMP并行机具有如下缺点：
a、欠可靠：总线、存储器或操作系统失效可导致系统崩溃。
b、可扩展性（scalability）较差：由于所有处理器共享总线带宽，而总线带宽每3年才增加2倍，跟不上处理器速度和内存容量的增加步伐，因此，SMP并行机的处理器个数一般少于32个，且只能提供每秒数百亿次的浮点运算性能。
分布共享存储并行机（DSM）：
内存模块局部在各个结点内部，并被所有结点共享。这样，可以较好地改善对称多处理器共享存储并行机的可扩展能力。DSM并行机具有如下主要特征：
a、并行机以结点为单位，每个结点包含一个或多个CPU，每个CPU拥有自己的局部cache，并共享局部存储器和I／O设备，所有结点通过高性能互联网络相互连接。
b、物理上分布存储：内存模块分布在各结点中，并通过高性能互联网相互连接，避免了SMP访存总线的带宽瓶颈，增强了并行机的可扩展能力。
c、单一的内存地址空间：尽管内存模块分布在各个结点，但是，所有这些内存模块都由硬件进行统一编址，并通过互联网络连接形成了并行机的共享存储器。各个结点既可以直接访问局部内存单元，又可以直接访问其他结点的局部内存单元。
d、非一致内存访问（NUMA）模式：由于远端访问必须通过高性能互联网络，而本地访问只需直接访问局部内存模块，因此，远端访问的延迟一般是本地访问延迟的3倍以上。
e、单一的操作系统映像：类似于SMP，在DSM并行机中，用户只看到一个操作系统，它可以根据各结点的负载情况，动态地分配进程。
f、基于cache的数据一致性：通常采用基于目录的cache一致性协议来保证各结点的局部cache数据与存储器中数据的一致性。同时，也称这种DSM并行机结构为CC-NUMA结构。
g、低通信延迟与高通信带宽：专用的高性能互联网络使得结点间的延迟很小，通信带宽可以扩展。
h、DSM并行机可扩展到数百个结点，能提供每秒千亿次的浮点运算性能。
i、支持消息传递、共享存储并行程序设计。
大规模并行机系统（MPP）
典型的分布存储系统，其典型特征为：
a、由数百个乃至数千个计算结点和I／O结点组成，每个结点相对独立，并拥有一个或多个微处理器。这些结点配备有局部cache，并通过局部总线或互联网与局部内存模块和I／O设备相连接。通常地，这些微处理器针对应用特征，进行了某些定制，与商用的通用微处理器略有不同。
b、这些结点由局部高性能网卡（NIC）通过高性能互联网络相互连接。互联网络与机群互联网络不同，它一般采用由多种静态拓扑结构耦合而成的混合拓扑结构，其通信延迟和通信带宽均明显优于机群互联网络。
c、MPP的各个结点均拥有不同的操作系统映像。一般情况下，用户可以将作业提交给作业管理系统，由它负责调度当前最空闲、最有效的计算结点来执行该作业。但是，MPP也允许用户登录到某个特定的结点，或在某些特定的结点上运行作业。
d、各个结点间的内存模块相互独立，且不存在全局内存单元的统一硬件编址。一般情形下，各个结点只能直接访问自身的局部内存模块，如果要求直接访问其他结点的局部内存模块，则必须有操作系统的特殊软件支持。
e、仅支持消息传递或者高性能Fortran并行程序设计，不支持全局共享的OpenMP并行程序设计模式。
在当前并行机上，比较流行的
并行编程环境可以分为三类
：消息传递、共享存储和数据并行。下表给出它们各个特征的比较：
所有流行并行机
SMP、DSM、MPP
进程级大粒度
线程级细粒度
进程级细粒度
并行操作方式
数据存储模式
分布式存储
数据分配方式
学习入门难度
由上表可看出：
1、共享存储并行编程基于线程级细粒度并行，仅被SMP和DSM并行机所支持，可移植性不如消息传递并行编程。但是，由于它们支持数据的共享存储，所以并行编程的难度较小，但一般情形下，当处理机个数较多时，其并行性能明显不如消息传递编程。
2、消息传递并行编程基于大粒度的进程级并行，具有最好的可移植性，几乎被当前流行的各类并行机所支持，且具有很好的可扩展性。但是，消息传递并行编程只能支持进程间的分布存储模式，即各个进程只能直接访问其局部内存空间，而对其它进行的局部内存空间的访问只能通过消息传递来实现。因此，学习和使用消息传递并行编程的难度均大于共享存储和数据并行两种编程模式。
由于当前流行的种类SMP、DSM、MPP和微机机群等并行机均支持消息传递并行程序设计，因此，有必要对这些具体并行机的体系结构进行抽象，设计一个理想的
消息传递并行机模型
。基于该模型，用户可以在不考虑具体并行机体系结构的条件下，组织消息传递并行程序设计，从而简化并行程序设计，增强程序的可移植性。
互联网络－－消息传递函数库
上图是一个理想的消息传递进程拓扑结构。其中，“P”表示MPI进程，“M”表示每个进程的局部内存空间，多个“P／M”进程／内存模块通过互联网相互连接，构成一个分布式存储的进程拓扑结构。在该结构中，各个进程之间可以直接通信，但是各个进程只能直接访问自身的局部内存空间，对其他进程的局部内存空间的访问只能调用消息传递函数，通过进程间通信才能实现。因此，该进程拓扑结构的核心是连接进程的互联网络，也就是消息传递标准函数库，而构成该函数库的所有函数就构成了用户面对的消息传递并行编程环境。
如果把上图的每个P／M模块替换成处理器，且规定每个处理器只能分配用户程序的一个进程，则所得的理想并行机模型就是消息传递并行机模型。不难看出，消息传递并行程序设计所依赖的并行机模型实际上属于典型的分布式存储并行机，且每台处理器只能分配用户程序的一个进程。基于该并行机模型，用户可以自由地调用消息传递函数库中的函数来组织具体的并行程序设计，且程序研制成功后，便可以在任何支持该并行机模型隐含的进程拓扑结构的所有具体并行机上运行。
这里，有必要说明的是，消息传递分布式存储并行机模型和具体并行机体系结构没有必然的联系。无论将该模型映射到何种类型的并行机（SMP、DSM、cluster、constellation、MPP），用户面对的都是该模型隐含的进程拓扑结构，只是各类具体并行机实现的消息传递函数库的方式不同，但用户无须知道这些细节。例如：在共享存储SMP、DSM并行机中，消息传递是通过共享数据缓存区来实现的；在MPP并行机中，消息传递是通过网络通信来实现的；在机群和星群并行机中，消息传递在SMP、DSM并行机内部是通过共享数据缓存区实现的，而在SMP、DSM并行机之间是通过网络通信来实现的。因此，无论哪种类型的具体并行机，呈现在消息传递并行程序设计用户面前的必然是上图所示的分布式存储并行机模型。
1994年6月，全球工业、政府和科研应用部门联合推出
消息传递并行编程环境的标准用户界面（MPI）
，它将消息传递并行编程环境分解为两个部分，第一是构成该环境的所有消息传递函数的标准接口说明，它们是根据并行应用程序对消息传递功能的不同要求而制定的，不考虑该函数能否具体实现；第二是各并行机厂商提供的对这些函数的具体实现。这样，用户只需学习MPI库函数的标准接口，设计MPI并行程序，便可在支持MPI并行编程环境的具体并行机上执行该程序。通常意义下所说的MPI系统就是指所有这些具有标准接口说明的消息传递函数所构成的函数库。
在标准串行程序设计语言（C、Fortran、C++）的基础上，再加入实现进程间通信的MPI消息传递库函数，就构成了MPI并行程序设计所依赖的并行编程环境。MPI吸收了众多消息传递系统的优点，例如P4、PVM、Express、PARMACS等，是目前国内外最流行的并行编程环境之一。
相对其他并行编程环境，MPI具有许多优点：
1、具有很好的可移植性，被当前所有并行环境支持；
2、具有很好的可扩展性，是目前高效率的大规模并行计算（数百个处理器）最可依赖的平台；
3、比其它消息传递系统好用；
4、有完备的异步通信功能；
5、有精确的定义，从而为并行软件的发展提供了必要的条件。
MPI 1.0版于1994年推出，并同时获得了各并行机产商的具体实现；MPI 2.0于1998年10月推出，它在1.0版的基础上，增加了如下的消息传递功能：
1、并行I／O：允许多个进程同时读／写同一个文件；
2、线程安全：允许MPI进程的多个线程执行，即支持与OpenMP的混合并行编程；
3、动态进程管理：允许并行应用程序在执行过程中，动态地增加和删除进程个数；
4、单边通信：允许某个进程对其他进程的局部内存单元直接执行读／写访问，而不需要对方进程的显式干预；
5、并行应用程序之间的动态互操作：允许各个MPI并行应用程序之间动态地建立和删除消息传递通信通道。
是适合在并行机上实现的算法，一个好的并行算法应该具备充分发挥并行机潜在性能的能力。
并行计算机的出现来源于实际应用程序中存在内在并行度这一基本事实，因此，应用问题中是否存在可挖掘的并行度是并行计算机应用的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地位。
根据运算基本对象的不同，并行算法可分为
数值并行算法
主要为数值计算方法而设计的并行算法；
非数值并行算法
主要为符号运算而设计的并行算法，如图论算法、遗传算法等。
根据并行进程间相互执行顺序关系的不同可分为
同步并行算法
进程间由于去处执行顺序而必须相互等待的并行算法；
异步并行算法
进程间执行相对独立，不需要相互等待的一种算法，根据最新消息决定进程的继续或终止；
独立并行算法
进行间执行是完全独立的，计算的整个过程不需要任何通信。
根据各进程承担的计算任务粒度的不同，可分为
细粒度并行算法
通常指基于向量和循环级并行的算法；
中粒度并行算法
通常指基于较大的循环级并行；
大粒度并行算法
通常指基于子任务级并行的算法。
其实，并行算法的粒度是一个相对的概念。如果处理器的计算功能强大，则原来的粗粒度算法也可以被认为是细粒度算法。
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致}