本文目录
- 用并行可实现的算法有哪些
- pso的并行算法
- 并行处理的并行算法的基本策略
- bitonic排序
- 多核计算与程序设计的内容简介
- 并行处理技术的三种形式
- 并行算法的并行算法的研究内容
- 用C++交换排序
- 作业间数据并行框架下道集选排技术
用并行可实现的算法有哪些
首先，应用的场合和解决的问题不一样。分布式计算比较倾向于在计算寻找模式的东西，穷举暴力之类的计算。分布式的计算被分解后的小任务互相之间有独立性，节点之间的结果几乎不互相影响，实时性要求不高。而并行计算则比较倾向于一些海量数据进行分析处理的场合，每个节点的每一个任务块都是必要的，计算的结果相互影响，要求每个节点的计算结果要绝对正确，并且在时间上做到同步。举例来说，像MD5破解，就比较适合使用大规模的分布式计算来穷举，但对海量日志数据进行处理来分析用户行为就比较适合并行计算处理。 其次，实现方式区别比较大。分布式计算会是一个比较松散的结构，并行计算则是各节点之间通过高速网络或其它总线之类的东西连接。因此并行计算一般在企业内部进行，而分布式计算可能会跨越局域网，或者直接部署在互联网上，节点之间几乎不互相通信。很多公益性的项目，就是的使用分布式计算的方式在互联网上实现，比如以寻找外星人为目的的SETI项目。
pso的并行算法
与大多数随机优化算法相似，当适应值评价函数的计算量比较大时，PSO算法的计算量会很大。为了解决该问题，研究者提出了并行PSO算法。与并行遗传算法类似，并行PSO算法也可以有三种并行群体模型：主从并行模型、岛屿群体模型和邻接模型。Schutte采用同步实现方式，在计算完一代中所有点的适应值之后才进入下一代。这种并行方法虽然实现简单，但常常会导致并行效率很差。故而有人提出异步方式的并行算法，可以在对数值精度影响不大的条件下提高PSO算法的并行性能。这两种方式采用的都是主从并行模型，其中异步方式在求解上耦合性更高，更容易产生通信瓶颈。Baskar提出一种两个子种群并行演化的并发PSO算法，其中一个子种群采用原始的PSO算法，另一个子种群采用基于适应值距离比的PSO算法（FDR-PSO）；两个子种群之间频繁地进行信息交换。而El-Abd研究了在子种群中采用局部邻域版本的协作PSO算法，并研究了多种信息交换的方式及其对算法性能的影响。黄芳提出一种基于岛屿群体模型的并行PSO算法，并引入一种集中式迁移策略，提高了求解效率，同时改善了早收敛现象。Li提出延迟交换信息的并行算法属于邻接模型，该算法可以提高速度，但可能使得解的质量变差。
并行处理的并行算法的基本策略
在并行处理技术中所使用的算法主要遵循三种策略：1．分而治之法：也就是把多个任务分解到多个处理器或多个计算机中，然后再按照一定的拓扑结构来进行求解。2．重新排序法：分别采用静态或动态的指令词度方式。3．显式/隐式并行性结合：显式指的是并行语言通过编译形成并行程序，隐式指的是串行语言通过编译形成并行程序，显式/隐式并行性结合的关键就在于并行编译，而并行编译涉及到语句、程序段、进程以及各级程序的并行性。二、并行性描述定义利用计算机语言进行并行性描述的时候主要有三种方案：1．语言扩展方案：也就是利用各种语言的库函数来进行并行性功能的扩展。2．编译制导法：也称为智能编译，它是隐式并行策略的体现，主要是由并行编译系统进行程序表示、控制流的分析、相关分析、优化分析和并行化划分，由相关分析得到方法库管理方案，由优化分析得到知识库管理方案，由并行化划分得到程序重构，从而形成并行程序。3．新的语言结构法：这是显式并行策略的体现。也就是建立一种全新的并行语言的体系，而这种并行语言通过编译就能直接形成并行程序。三、并行软件并行软件可分成并行系统软件和并行应用软件两大类，并行系统软件主要指并行编译系统和并行操作系统，并行应用软件主要指各种软件工具和应用软件包。在软件中所牵涉到的程序的并行性主要是指程序的相关性和网络互连两方面。1．程序的相关性：程序的相关性主要分为数据相关、控制相关和资源相关三类。数据相关说明的是语句之间的有序关系，主要有流相关、反相关、输出相关、I/O相关和求知相关等，这种关系在程序运行前就可以通过分析程序确定下来。数据相关是一种偏序关系，程序中并不是每一对语句的成员都是相关联的。可以通过分析程序的数据相关，把程序中一些不存在相关性的指令并行地执行，以提高程序运行的速度。控制相关指的是语句执行次序在运行前不能确定的情况。它一般是由转移指令引起的，只有在程序执行到一定的语句时才能判断出语句的相关性。控制相关常使正在开发的并行性中止，为了开发更多的并行性，必须用编译技术克服控制相关。而资源相关则与系统进行的工作无关，而与并行事件利用整数部件、浮点部件、寄存器和存储区等共享资源时发生的冲突有关。软件的并行性主要是由程序的控制相关和数据相关性决定的。在并行性开发时往往把程序划分成许多的程序段——颗粒。颗粒的规模也称为粒度，它是衡量软件进程所含计算量的尺度，一般用细、中、粗来描述。划分的粒度越细，各子系统间的通信时延也越低，并行性就越高，但系统开销也越大。因此，我们在进行程序组合优化的时候应该选择适当的粒度，并且把通讯时延尽可能放在程序段中进行，还可以通过软硬件适配和编译优化的手段来提高程序的并行度。2．网络互连：将计算机子系统互连在一起或构造多处理机或多计算机时可使用静态或动态拓扑结构的网络。静态网络由点一点直接相连而成，这种连接方式在程序执行过程中不会改变，常用来实现集中式系统的子系统之间或分布式系统的多个计算结点之间的固定连接。动态网络是用开关通道实现的，它可动态地改变结构，使之与用户程序中的通信要求匹配。动态网络包括总线、交叉开关和多级网络，常用于共享存储型多处理机中。在网络上的消息传递主要通过寻径来实现。常见的寻径方式有存储转发寻径和虫蚀寻径等。在存储转发网络中以长度固定的包作为信息流的基本单位，每个结点有一个包缓冲区，包从源结点经过一系列中间结点到达目的结点。存储转发网络的时延与源和目的之间的距离(段数)成正比。而在新型的计算机系统中采用虫蚀寻径，把包进一步分成一些固定长度的片，与结点相连的硬件寻径器中有片缓冲区。消息从源传送到目的结点要经过一系列寻径器。同一个包中所有的片以流水方式顺序传送，不同的包可交替地传送，但不同包的片不能交叉，以免被送到错误的目的地。虫蚀寻径的时延几乎与源和目的之间的距离无关。在寻径中产生的死锁问题可以由虚拟通道来解决。虚拟通道是两个结点间的逻辑链，它由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成。物理通道由所有的虚拟通道分时地共享。虚拟通道虽然可以避免死锁，但可能会使每个请求可用的有效通道频宽降低。因此，在确定虚拟通道数目时，需要对网络吞吐量和通信时延折衷考虑。四、硬件技术在硬件技术方面主要从处理机、存储器和流水线三个方面来实现并行。1．处理机：主要的处理机系列包括CISC、RISC、超标量、VL1W、超流水线、向量以及符号处理机。传统的处理机属于复杂指令系统计算(CISC)结构。指令系统大，指令格式可变，通用寄存器个数较少，基本上使用合一的指令与数据高速缓存，时钟频率较低，CPI较高，大多数利用ROM 实现微码控制CPU，而当今的精简指令系统计算(RISC)处理机指令格式简单规范，面向寄存器堆，采用重叠寄存器窗口技术，具有多级Cache，多种流水线结构，强调编译优化技术，时钟频率快，CPI低，大多数用硬连线控制CPU。CISC或RISC标量处理机都可以采用超标量或向量结构来改善性能。标量处理机在每个周期内只发射一条指令并要求周期只完成从流水线来的一条指令。而在超标量处理机中，使用了多指令流水线，每个周期要发射多条指令并产生多个结果。由于希望程序中有许多的指令级并行性，因此超标量处理机更要依靠优化编译器去开发并行性。VL1W 结构是将水平微码和超标量处理这两种普遍采用的概念结合起来产生的。典型的超长指令字VL1W 机器指令字长度有数百位。在VLlW 处理机中，多个功能部件是并发工作的，所有的功能部件共享使用公用大型寄存器堆，由功能部件同时执行的各种操作是用VL1W 指令来同步的，每条指令可指定多个操作。VL1W 指令译码比超标量指令容易，但在开发不同数量的并行性时总是需要不同的指令系统。VL1W 主要是开发标量操作之间的并行性，它的成功与否很大程度取决于代码压缩的效率，其结构和任何传统的通用处理机完全不兼容。即使同一结构的不同实现也不大可能做到彼此二进制兼容。VL1W 的主要优点在于它的硬件结构和指令系统简单，在科学应用领域可以发挥良好作用，但在一般应用场合可能并不很好用。向量处理机对数组执行向量指令，每条指令都包含一串重复的操作。它是专门设计用来完成向量运算的协处理机，通常用于多流水线超级计算机中。向量处理机可以利用循环级展开所得的并行性，它可以附属于任何标量处理机。专用的向量流水线可以在循环控制中消除某些软件开销，它的效果与优化编译器将顺序代码向量化的性能很有关系。从理论上说，向量机可以具有和超标量处理机同样的性能，因此可以说向量机的并行性与超标量机相同。符号处理机是为AI应用而研制的，已用于定理证明、模式识别、专家系统、知识工程、文本检索、科学以及机器智能等许多应用领域。在这些应用中，数据和知识表达式、原语操作、算法特性、存储器、I/0和通信以及专用的结构特性与数值计算是不一样的，符号处理机也称为逻辑程序设计语言处理机、表处理语言处理机或符号变换器。符号处理并不和数值数据打交道，它处理的是逻辑程序、符号表、对象、剧本、黑板、产生式系统、语义网络、框架以及人工神经网络等问题。这些操作需要专门的指令系统，通常不使用浮点操作。2．存储器：存储设备按容量和存取时间从低到高可分为寄存器、高速缓存、主存储器、磁盘设备和磁带机五个层次。较低层存储设备与较高层的相比，存取速度较快、容量较小，每字节成本较高、带宽较宽、传输单位较小。存放在存储器层次结构中的信息满足三个重要特性：包含性、一致性和局部性。所谓包含性，指的是一个信息字的复制品可以在比它高的所有层中找到，而如果在高层中丢失了一个信息，则在比它低的所有层中此信息也将丢失。CPU 和高速缓存之间的信息传送是按字进行的，高速缓存和主存储器间用块作为数据传送的基本单位，主存和磁盘之间又是以页面为基本单位来传送信息的，而在磁盘和磁带机之间的数据传送则是按文件级处理的。所谓一致性要求的是同一个信息项与后继存储器层次上的副本是一致的。也就是说，如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改。为了尽量减少存储器层次结构的有效存取时间，通常把频繁使用的信息放在较低层次。维护存储器层次结构一致性一般有两种策略，一种是写直达策略，也就是如果，则立即在所有高层存储器中进行同样的修改；另一种是写回策略，也就是在较低层中对信息进行修改后并不立即在高层存储器中进行相应的修改，而是等到该信息将被替换或将从低层中消失时才在所有高层存储器中进行同样的修改。甚至可以将写直达和写回策略的优点结合起来，形成写一次协议来维护存储器的一致性。存储器的层次结构是在一种程序行为——访问的局部性基础上开发出来的。主要有时间局部性、空间局部性和顺序局部性。时间局部性指的是最近的访问项很可能在不久的将来再次被访问。它往往会引起对最近使用区域的集中访问。空间局部性表示一种趋势，指的是一个进程访问的各项其地址彼此很近。顺序局部性指的是在典型程序中，除非是转移指令，一般指令都是顺序执行的。在多处理机系统中一般使用共享存储器。对共享存储器的组织一般采用低位交叉、高位交叉、高低位交叉三种方法。低位交叉又称并发存取，它是把相邻的地址放在相邻的存储器模块中，在访问时不容易产生冲突，并行性较好，但可靠性容错能力和扩展性均较差。高位交叉又称允许同时存取，它是把相邻地址分配到同一个存储器模块中，可靠性、容错能力和扩展性均较强，但访问时易产生冲突，带宽较窄，并行性较差。高低位交叉存取又称C—s存取，它是结合了高位交叉和低位交叉两种方法的优点，既解决了冲突问题，又能有效地提高容错能力和并行性，最适合于向量处理机结构。3．流水线：流水线技术主要有指令流水线技术和运算流水线技术两种。指令流水线技术主要目的是要提高计算机的运行效率和吞吐率。它主要通过设置预取指令缓冲区、设置多功能部件、进行内部数据定向、采取适当的指令调度策略来实现。指令调度的策略主要有静态和动态两种，静态词度是基于软件的，主要由编译器完成，动态词度是基于硬件的，主要是通过硬件技术进行。运算流水线主要有单功能流水线和多功能流水线两种。其中多功能流水线又可分为静态流水线和动态流水线。静态流水线技术只用来实现确定的功能，而动态流水线可以在不同时间重新组合，实现不同的功能，它除流线连接外，还允许前馈和反馈连接，因此也称为非线性流水线。这些前馈和反馈连接使得进入流水线的相继事件的词度变得很不简单。由于这些连接，流水线不一定从最后一段输出。根据不同的数据流动模式，人们可以用同一条流水线求得不同功能的值。并行计算机发展简述40 年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。创建和使用并行计算机的主要原因是因为并行计算机是解决单处理器速度瓶颈的最好方法之一。并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。60 年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现，这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机（Mainframe）。IBM360 是这一时期的典型代表。到了60 年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用大大提高了并行计算机系统的性能。伊利诺依大学和Burroughs 公司此时开始实施IlliacIV 计划，研制一台64 个CPU 的SIMD 主机系统，它涉及到硬件技术、体系结构、I/O 设备、操作系统、程序设计语言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小了的16CPU 系统终于在1975 年面世时，整个计算机界已经发生了巨大变化。首先是存储系统概念的革新，提出虚拟存储和缓存的思想。IBM360/85 系统与360/91是属于同一系列的两个机型，360/91 的主频高于360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线；但是，360/85 的整体性能却高于360/91，唯一的原因就是前者采用了缓存技术，而后者则没有。其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器被用作缓存，而CDC7600 则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到了计算机中。元器件技术的这两大革命性突破，使得IlliacIV 的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。1976 年CRAY-1 问世以后，向量计算机从此牢牢地控制着整个高性能计算机市场15 年。CRAY-1 对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC 的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列全新技术手段的使用，使CRAY-1 的主频达到了80MHz。微处理器随着机器的字长从4 位、8 位、16 位一直增加到32 位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基- 梅隆大学开始在当时流行的DECPDP11 小型计算机的基础上研制成功一台由16 个PDP11/40 处理机通过交叉开关与16 个共享存储器模块相连接而成的共享存储多处理器系统C.mmp。从80 年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP 方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了Cache 一致性问题的处理方案。从此，C.mmp 开创出的共享存储多处理器之路越走越宽；现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。同一时期，基于消息传递机制的并行计算机也开始不断涌现。80 年代中期，加州理工成功地将64 个i8086/i8087 处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC 系列、INMOS Transputer 系列，Intel Paragon 以及IBM SP 的前身Vulcan 等基于消息传递机制的并行计算机。80 年代末到90 年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM将大量早期RISC 微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性（Scalability）。90 年代初期，斯坦福大学提出了DASH 计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE 在此基础上提出了缓存一致性协议的标准。90 年代以来，主要的几种体系结构开始走向融合。属于数据并行类型的CM-5 除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息；CRAY T3D是一台NUMA 结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。随着商品化微处理器、网络设备的发展，以及MPI/PVM 等并行编程标准的发布，机群架构的并行计算机出现。IBM SP2 系列机群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。今天，越来越多的并行计算机系统采用商品化的微处理器加上商品化的互连网络构造，这种分布存储的并行计算机系统称为机群。国内几乎所有的高性能计算机厂商都生产这种具有极高性能价格比的高性能计算机，并行计算机就进入了一个新的时代，并行计算的应用达到了前所未有的广度和深度。并行计算机随着微处理芯片的发展，已经进入了一个新时代。目前并行计算机的性能已经突破20PFLOPS，正在向百亿亿次发展。我国并行计算机的研制已经走在世界前列。2003年由联想公司生产的深腾6800 在2003 年11 月世界TOP500 排名中位列第14 名，2004 年曙光公司生产的曙光4000A 在2004 年6 月的世界TOP500 排名中位列第10 名，这是我国公开发布的高性能计算机在世界TOP500 中首次进入前十名，这标志着我国在并行计算机系统的研制和生产中已经赶上了国际先进水平，为提高我国的科学研究水平奠定了物质基础。2013年国际超级计算机大会最新发布的世界超级计算机500强排名中，国防科技大学研制的天河二号超级计算机系统，以峰值计算速度每秒5.49亿亿次、持续计算速度每秒3.39亿亿次双精度浮点运算的优异性能位居榜首。从TOP500 的前10 名来看，美国仍然是超级计算机的最大拥有者。按照世界TOP500 的统计数据来分析，美国在计算能力上占有近全世界的一半，在TOP500 中的所有计算机中拥有的数量超过50%。
bitonic排序
bitonic排序是一个并行排序算法。双调合并排序(Bitonicmergesort)是一个并行排序算法。它也用作建立一个排序网络的一种构造方法。这个算法是由KenBatcher提出来的。基于它生成的排序网络包含了个比较操作和的延时，这里的n是要排序的元素个数。一个排好序的序列是一个单调非降(或单调非增)序列。一个双调序列是一个满足对于特定的k()，，或者是该序列的循环移位序列。双调排序（bitonicsort）属于排序网络(SortingNetwork）的一种。相较于传统的排序算法，排序网络真正的研究价值在于，假如有机器可以同时处理多个比较器，排序的速度将大幅度提高。简单来说，它是一种可以并行计算的排序算法。
多核计算与程序设计的内容简介
第1部分介绍多核编程的基础知识，包括多核编程常见问题、锁竞争、加速比、负载均衡等基本概念，多线程退出算法、读写锁、旋转锁、原子操作等多线程编程基础知识，基于OpenMP标准的并行程序设计基础等；第2部分介绍基础的数据结构与算法，包括数组、链表、哈希表、二叉树、AVL树、复合二叉树等基本数据结构，在链表那章中还讲解了多线程并行遍历的基本方法。第3部分介绍多核并行计算方面的基础知识，并行编程包括常用的编程模式如分治模式、流水线模式、任务图分解与调度模式、动态任务调度模式等，并行搜索包括顺序搜索及终止检测算法，并行最短路径搜索等，并行排序包括并行快速排序、并行归并排序、并行基数排序等，并行数值计算包括并行矩阵乘法、并行前缀和计算等方面的内容。本部分介绍的各种并行算法和程序中，重点介绍如何解决多核系统中的计算随CPU核数的扩展性，CPUCache伪共享方面的问题。第4部分介绍多核共享资源计算方面的内容，也是《多核计算与程序设计》中最重要的内容，讲解了分布式计算设计模式如线程分组竞争模式、条件同步模式、批量私有化处理模式、数据本地化模式等。这部分中讲解了《多核计算与程序设计》中几个最重要的程序：分布式队列中实现了自动让每个线程带有一个本地队列、分布式查找中介绍了分段锁的哈希表、动态负载平衡的分布式查找等，分布式内存管理则介绍了适应多核的内存管理方案，尤其是基于抢夺式的分布式内存管理算法，在分配和释放共享内存时也几乎不需要使用锁，性能优异。第5部分介绍任务分解与调度方面的知识，这也是《多核计算与程序设计》中最重要的内容，包括任务图分解与调度的实现方法，动态任务分解与调度的实现方法等。其中还介绍了使用动态嵌套任务调度进行并行计算的方法，给出了用动态嵌套任务调度实现ParallelForo、并行快速排序、并行归并的实例。最后一章中还介绍了Lock-Free编程（使用CAS原子操作进行编程）的基础知识，如ABA问题，内存删除问题等，并给出了一个Lock-Free的队列的实现实例。
并行处理技术的三种形式
时间并行指时间重叠，在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。?时间并行性概念的实现方式就是采用流水处理部件。这是一种非常经济而实用的并行技术，能保证计算机系统具有较高的性能价格比。目前的高性能微型机几乎无一例外地使用了流水技术。 资源共享也是在并行性概念中引入时间因素，它是通过软件的方法实现的。即多个用户按一定的时间顺序轮流使用同一套硬件设备；既可以是按一定的时间顺序共享CPU，也可以是CPU与外围设备在工作时间上的重叠。这种并行措施表现在多道程序和分时系统中，而分布式处理系统和计算机网络则是更高层次的资源共享。从第一台电子计算机发明，电子计算机已经经历了五代。计算机发展到第四代时，出现了用共享存储器、分布存储器或向量硬件选件的不同结构的并行计算机，开发了用于并行处理的多处理操作系统专用语言和编译器，同时产生了用于并行处理或分布计算的软件工具和环境。到出现的计算机称为第五代计算机，它们的主要特点是进行大规模并行处理。并行处理技术是在微电子、印刷电路、高密度封装技术、高性能处理机、存储系统、外围设备、通信通道、语言开发、编译技术、操作系统、程序设计环境和应用问题等研究和工业发展的产物。并行计算机具有代表性的应用领域有：天气预报建摸、VLSI电路的计算机辅助设计、大型数据库管理、人工智能、犯罪控制和国防战略研究等，而且它的应用范围还在不断地扩大。并行处理技术主要是以算法为核心，并行语言为描述，软硬件作为实现工具的相互联系而又相互制约的一种结构技术。本文就并行处理技术的算法策略、描述性定义及软硬件方面的实现做一个简单的介绍。
并行算法的并行算法的研究内容
(1) 并行计算模型 并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。并行计算模型的第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是CPU的单位计算时间，这样科学家可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。第三代是分布共享存储模型，也是我们目前研究所处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。(2) 设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。（3）并行算法分为多机并行和多线程并行。多机并行，如MPI技术；多线程并行，如OpenMP技术。以上是并行算法的常规研究内容。
用C++交换排序
所谓交换，就是根据序列中两个记录值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。常见的交换排序有冒泡排序（Bubble Sort），鸡尾酒排序（Cocktail Sort），奇偶排序（OddEven Sort），地精排序（Gnome Sort），快速排序（Quick Sort），臭皮匠排序（Stooge Sort），梳排序（Comb Sort），Bogo排序（Bogo sort）。下面介绍前六种：（一）冒泡排序最差时间复杂度：O(n^2)最优时间复杂度：O(n)平均时间复杂度：O(n^2)最差空间复杂度：总共O(n)，需要辅助空间O(1)稳定性：稳定冒泡排序（Bubble Sort），它重复地走访过要排序的数列，一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序算法的运作如下：1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3.针对所有的元素重复以上的步骤，除了最后一个。4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。实现代码： view plaincopyvoid BubbleSort(int *a, int len) { for (int i=0; i《len; i++) { for (int j=len-1; j》i; j--) { if (a) swap(a); } } } （二）鸡尾酒排序最差时间复杂度：O(n^2)最优时间复杂度：O(n)平均时间复杂度：O(n^2)稳定性：稳定鸡尾酒排序（Cocktail sort），是冒泡排序的一种变形。它与冒泡排序的不同之处在于排序时是以双向在序列中进行排序。数组中的数字本是无规律的排放，先对数组从左到右进行冒泡排序（升序），把最大值放到最右端，然后对数组从右到左进行冒泡排序（降序），把最小的数字放到最左端。然后再以此类推，以此改变冒泡的方向，并不断缩小未排序元素的范围。直到在一趟双向冒泡后没有发生交换，排序结束。实现代码： view plaincopyvoid CocktailSort(int* a, int len) { int bottom = 0; int top = len-1; bool swapped = true; while (swapped) { swapped = false; for (int i=bottom; i《top; i++) { if (a) { swap(a); swapped = true; } } top = top-1; for (int i=top; i》bottom; i--) { if (a) { swap(a); swapped = true; } } bottom = bottom+1; } } （三）奇偶排序最差时间复杂度：O(n^2)稳定性：稳定奇偶排序（OddEven Sort），是一种相对简单的排序算法，最初发明用于有本地互联的并行计算。此算法通过比较数组中相邻的（奇-偶）位置数字对，如果该奇偶对是错误的顺序（第一个大于第二个），则交换。下一步重复该操作，但针对所有的（偶-奇）位置数字对。如此交替下去，直到不发生交换，则排序结束。在并行计算排序中，使用该算法，每个处理器对应处理一个值，并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作，交替以奇-偶、偶-奇的顺序。该算法由Habermann在1972年最初发表并展现了在并行处理上的效率。但在单处理器串行运行此算法，类似冒泡排序，较为简单但效率并不特别高。实现代码： view plaincopyvoid OddEvenSort(int *a, int len) { bool swapped = true; while (swapped) { swapped = false; for (int i=0; i《len-1; i=i+2) { if (a) { swap(a); swapped = true; } } for (int i=1; i《len-1; i=i+2) { if (a) { swap(a); swapped = true; } } } } （四）地精排序最差时间复杂度：O(n^2)最优时间复杂度：O(n)平均时间复杂度：O(n^2)稳定性：稳定地精排序（Gnome Sort），被Dick Grune称为最简单的排序算法。整个算法只有一层循环，默认情况下前进冒泡，一旦遇到冒泡的情况发生就往回冒，直到把这个数字放好，然后继续前进，前进到数组最后一个数结束。此排序算法虽然代码极短，但效率不高。实现代码： view plaincopyvoid GnomeSort(int *a, int len) { int i=0; while (i《len) { if (i==0 || a){ i++; } else { swap(a); i--; } } } （五）快速排序最差时间复杂度：O(n^2)最优时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)稳定性：不稳定快速排序（Quick Sort），使用分治法策略来把一个串行分为两个子串行，左边子串的值总小于右边的子串。此算法的三个步骤：1．分解：将数组A中的元素。下标p也在这个划分过程中计算。2．解决：通过递归调用快速排序，对数组A排序。3．合并：因为两个子数组时就地排序，将它们的合并并不需要操作，整个数组A已经排序。实现代码（其他实现方法见“三种快速排序算法的实现”）： view plaincopyint partition(int* a, int left, int right) { int x = a; int i = left-1, j = right; for (;;) { while(a 《 x) { } while(a 》 x) { if(j==left) break;} if(i 《 j) swap(a); else break; } swap(a); return i; } void quickSort(int* a, int left, int right) { if (left《right) { int p = partition(a, left, right); quickSort(a, left, p-1); quickSort(a, p+1, right); } } （六）臭皮匠排序最差时间复杂度：O(n^2.7)臭皮匠排序（Stooge Sort），是一种低效的排序算法，在《算法导论》第二版第7章的思考题中被提到，是由Howard Fine等教授提出的所谓“漂亮的”排序算法。将数列平分为三个子串，依次递归排序前两个子串、后两个子串、前两个子串，最后确保整个数列有序。此算法在最坏情况下的递归式为T(n) = 3T(2n/3) + 1。由主定理很容易知道它的算法复杂性为：T(n) = O(n^log(3/2, 3))。很显然log(3/2, 3))》2，也就是说这个算法比插入排序的O(n^2)性能还差。实现代码： view plaincopyvoid StoogeSort(int *a, int i, int j) { if(a) swap(a); if((i+1)》=j) return; int k = (j-i+1)/3; StoogeSort(a, i, j-k); StoogeSort(a, i+k, j); StoogeSort(a, i, j-k); }
作业间数据并行框架下道集选排技术
刘兰锋。作业内模块并行则需要缓存大量数据，风险较高。
图1 作业内数据并行示意图
较为直接的并行便是作业并行，具体分两种：一是作业内部数据并行，如图1所示，数据I/O由系统集中控制，将作业中除去作业头尾的输入和输出模块以外的其他处理模块复制到多个处理节点上，当各个处理节点完成处理后，控制程序回收处理后的地震数据，再将它们输出到输出文件中，从而实现处理作业（除数据I/O外）的并行运行，但由于各处理节点性能的差异，回收地震数据的顺序和分发地震数据的顺序并不能总保持一致，增加了集中控制数据I/O的复杂性；二是将集中的数据I/O任务也分散到各个处理节点上去运行，即作业间数据并行，其示意图见图2。简言之，就是根据可使用的处理节点数目和原始地震数据的存储形式，将需要处理的原始地震数据切割成相应的若干部分分发给各个处理节点，每个处理节点都启动一个独立的子作业，处理自己的那一部分地震数据，最后当各个处理节点上的子作业都完成后，再将各个处理结果数据进行合并，从而实现处理作业的并行运行。
图2 作业间数据并行示意图
多分量资料处理系统（MCS2.0）采用作业间数据并行形式，将原始作业分割成多个计算任务来管理，一个进程执行一个计算任务，其执行流程如图3所示，主控首先从数据库下载作业内容，然后将作业分割成若干个计算任务，注册到数据库等待计算节点上的守护进程调度；守护进程根据计算节点本地资源状况和计算任务量定时从数据库中下载计算任务，启动计算进程执行本次任务。
图3 作业执行流程示意图
2 并行抽道集算法
基于作业间数据并行的地震数据道头排序算法，其基本思想就是将大的数据体道头信息进行分块多级排序，这里以抽成CDP道集（即以线号、CDP号和偏移距分别为第一、二、三关键字进行3级排序）为例，其算法流程如图4所示，具体可分成以下4步来完成：
图4 并行排序示意流程图
1）首先将数据体按道顺序号分成若干块，分发给多个进程，分别进行一级排序（即按第一排序关键字排序，如线号），本地一级排序完成后，将排序结果输出到临时文件。
2）待每个进程完成一级排序后，由最后一个进程收集其他进程的排序结果，进行全局一级排序；然后将全局排序结果按第一排序关键字分成若干块，分发给多个进程。
3）每个进程接到二级排序任务后分别进行本地二级排序（即按第二排序关键字排序，如CDP号），至此已完成道集级别的排序。
4）最后读取实际地震道转存数据，同时完成道集内排序（即第三排序关键字，如偏移距）。
3 实际数据应用
我们将并行道头排序算法应用于并行地震数据加载和并行抽道集等批处理模块，实现了海量（T级）地震数据的快速访问。如图5所示，我们对一个约为970G的地震数据，共计64855988道，分成8个计算任务进行3级（线号、CDP号和偏移距）排序，然后根据排序后的道索引位置读取数据转存加载到处理系统中，耗时共计2h35min，极大地缩短了数据I/O时间，提高了处理平台的效率。
图5 并行抽道集加载地震数据
4 结论
利用地震数据自身可分割的特点，将常规串行地震数据作业的运行方式分割成若干个计算任务，分发到多个计算节点，启动多个计算任务并行运行，结合数据库的存储过程，控制并发进程间的同步、异步以及进程运行次序的判断，实现了地震数据并行抽道集算法。实际地震数据测试表明，这种并行抽道集方法充分利用了集群多节点、多进程的并行能力，极大地缩短了抽道集的运行时间，提高了地震处理系统对海量数据管理能力和运行效率。
致谢 本研究工作得到了国家重大专项 “地球物理技术软件集成”（2011ZX05005 －005－06）的资助，表示衷心的感谢。
参考文献
［1］张剑，刘梦花，等.地震勘探中超万道SPS文件整理方法.石油地球物理勘探，2010，45（增刊1）：53～57.
［2］张军华，仝兆岐.地震资料处理中的并行计算机技术（综述）.物探化探计算技术，2002，24（1）：31～36.
［3］金君，何万青，乔楠，等.iCluster软件叠前时间偏移模块的优化方法.勘探地球物理进展，2008，31（6）：433～437.
［4］黄中玉，曲寿利，等.层状各向异性介质转换波克希霍夫叠前时间偏移.地球物理学报，2009，52（12）：3109～3115.
［5］方伍宝，孙建国，赵改善，等.波动方程叠前深度偏移成像软件系统的研制及应用.石油物探，2005，44（5）：486～491.
［6］赵改善.地球物理软件技术发展趋势与战略研究.勘探地球物理进展，2010，33（2）：77 ～86.
［7］祝树云，朱旭光，等.应用并行计算框架提升地震数据处理效率分析.石油地球物理勘探，2011，46（3）：493～499.
［8］赵长海，晏海华，王宏琳，等.面向地震数据处理的并行与分布式编程框架.石油地球物理勘探，2010，45（1）：145～155.
［9］杨红霞，赵改善.21世纪的地震数据处理系统.石油物探，2001，40（4）：125～140.
［10］王宏琳.地球物理软件体系结构研究.石油地球物理勘探，2008，43（5）：606～611.
［11］王宏琳.计算机集群地震交互成像软件技术——概念、系统结构、设计模式及Internet交互处理.勘探地球物理进展，2002，25（4）：1～8.
［12］赵改善.地球物理高性能计算的新选择：GPU计算技术.勘探地球物理进展，2007，30（5）：399～404.
［13］李军.高性能MySQL（第二版）.北京：电子工业出版社，2010.
