并行构造算法

并行构造算法（精选九篇）

并行构造算法 篇1

概念格也称为Galois格,是形式概念分析理论中的核心数据结构,它利用二元关系建立一种概念间的层次关系,是进行数据分析和规则提取的有效工具[1]。随着研究深入,形式概念分析越来越多地被应用到数据挖掘、信息检索、软件工程等方面,已经成为当前计算机科学领域的一个热门研究课题。由于概念格自身的完备性,构造概念格的时间复杂度一直是影响形式概念分析应用的主要因素。随着处理的形式背景的增大,构造概念格的时空复杂度也会随之急剧增加。提高其构造效率的一种有效途径是利用高性能并行计算机和网络并行计算的能力,概念格的分布处理或并行处理采用的思想都是分治策略,当前建格算法的分布处理研究主要有形式背景的并置和叠置以及形式背景的折叠搜索子空间划分两种方法[2],这两类概念格的分布处理模型都是分治策略应用的很好的例子。但进一步的研究发现,概念格并置与叠置模型要求概念格的类型比较严格,即所能计算的概念格是一种特殊的概念格,而折叠子空间划分过于机械,过多地依赖于划分参数DP,不能很好地解决特殊概念格的划分[3]。本文也采用分治策略,提出了一种新的基于闭包划分的概念格并行生成算法———ParaPruning算法。

2 基本定义

定义1设K=(G,M,I)为一形式背景,,定义|M1′|为M′中对象的个数,,定义|G1′|为G′中属性的个数。

定义2设K=(G,M,I)为一形式背景,S为K上的概念集合,定义C0=(M′M),C1=(G,G′),且|M′|=0,|G′|=0,定义Ct={C0,C1}。

定义3设K=(C,M,I)为一形式背景,定义运算↑g,满足。

定义5设F(I)是形式背景K=(G,M,I)对象G上的闭包系统,定义:

(1)Fg(I)为形式背景对象G1上的闭包系统

(2)对象G↑g上的闭包系统:

定理1设K=(G,M,I)为一形式背景,定义F(I)为背景K的外延的闭包系统,g为∨-Prime元素,满足:

此定理说明,如果g为∨-Prime元素,则。

证明:略[4]。

证明:略[4]。

3 Para-Pruning算法的描述

Para-Pruning算法是基于对搜索空间划分及缩减来求解概念的,与已有的分布处理模型不同的是,ParaPruning算法的划分是基于闭包系统的划分,其原理是把一个闭包系统划分为多个子闭包系统分别求出概念集后,然后合并得出原闭包系统所对应的概念集。

证明:很明显,可以由命题1得出。

证明:若(m′↑g)′哿g′,则(m′↑g)″勐g″,(m′↑g)″∈Fg(I),g″∈Fg(I),即Fg(I)∩Fg(I)≠准,与原命题矛盾,假设错误,得证。

命题4设K=(G,M,I)为一形式背景,g∈G是∨-Prime,坌m∈g′,则埚mi∈Mg′,m′↑g哿mi。

证明:很明显,可以由命题1得出。

命题5设K=(G,M,I)为一形式背景,g∈G是非∨-Prime元素,则,m′↑gmi′≠准,其中mi∈M↑g。

证明:很明显,可以由命题1得出。

根据上面介绍的Para-Pruning算法的基本定义和原理,可以看出每个搜索空间是相互独立的,并且每个子搜索空间都对应一个闭包系统,所以可以派生不同的进程分别处理每个子搜索空间。Para-Pruning算法首先将原形式背景转化为有序形式背景,按照排序后背景的特点,判断对象集合中的特殊对象是否为∨-Prime元素,对搜索空间进行划分为相互独立的子闭包系统,根据所给定Depth值的大小是否进行更进一步的划分,最后在每个子空间内用批处理或者渐进式构造算法[1,6]进行概念的计算。

对∨-Prime元素的判定,在文献[4]和文献[5]中,Alain Gely和G.Markowsky提出,依据是g′=G↑g(定理3),但经进一步的研究发现,满足∨-Prime条件的元素并不仅仅满足条件g′=G↑g,通过对命题1的证明,定理3实际上是命题1的一个充分条件,这样,就为找出更多的∨-Prime元素提供了理论依据。

命题6 Para-Pruning算法的预处理Sort(K)是必要的。

证明:对原形式背景的排序,实际上在对象集合中的对象g定义了一个字典序,把每个属性所具有的对象在该字典序下排列,使排序后的背景有明显的“阶梯”状,这样,可以很方便地判断那些↑g集合中的元素,即两个阶梯间的元素{g|g∈↑g},为后续的计算提供方便。

Para-Pruingn算法的伪代码如下:

算法2:De Composition(K,d)//初始背景的划分

根据闭包系统的性质可以证明,子闭包系统对应的概念集合的并集与原闭包系统所对应的概念集合相同。Para-Pruning算法不会造成信息的丢失。Para-Pruning算法的主要计算时间在于划分完成后在每个子背景求解概念的时间,由于在计算中避免了空间的搜索,所以其时间复杂度要小于经典的Next Closue算法。

下面给出了一个具体的例子来描述算法的运算过程,假设深度设Depth=1。图1中表a给出一个形式背景K=(G,M,I),菖表示所对应的对象和属性具有关系I,即g Im。用所给出的算法计算背景a的概念描述如下。表b是该背景的排序,c、d、e和f分别是排序后背景的划分,每个背景所对应的概念集合分别为:

背景a:Sa={(ф,Ma),(7,bdf),(78,bf),(789,b),(4,chi),(459,hi),(9,behi),(45689,i),(8,befgi),(89,bei),(1,aeg),(12689,e),(689,ei),(1238,g),(128,eg),(Ga,ф)},|Sa|=16。

背景c:Sc={(1,aeg),(12689,e),(128,eg),(1238,g),(Gc,ф)},|Sc|=5。

背景d:Sd={(ф,Mf),(7,bdf),(78,bf),(789,b),(4,chi),(459,hi),(9,behi),(45689,i),(8,befgi),(89,bei),(689,ei),(Gd,ф)},|Sa|=12。

背景e:Se={(4,chi),(459,hi),(45689,i)},|Se|=3。

背景f:Sf={(准,Mf),(7,bdf),(78,bf),(789,b),(9,behi),(8,befgi),(89,bei),(689,ei),(Gf,准)},|Sf|=9。

很明显,有SaCta=(ScCtc)∪(SeCte)∪SfCtf,而且(SiCti)∩(SjCtj)=Ф,i,j∈{c,e,f},i≠j。

如果按照Alain Gely和G.Markowsky所提出定理3,此例是不能进行闭包分解的,然而,本例却划分了3个子闭包系统,由此也可说明定理3是命题1的一个充分条件。

4 实验分析

为了验证Para-Pruning算法的优越性,给出了此算法与经典Next Closure算法的比较分析。在Pentium4 2.4,256M内存,Windows XP操作系统,使用随机生成的数据集,利用VB.net 2005实现了Para-Pruning算法和Next Closure算法(参见表1、表2)。测试数据采用150组随机生成的样本数据,为提高数据的真实性,对随机生成的每10组样本数据取均值。生成随机数据集时,考虑了3个参数:对象数|G|、属性数|M|、以及用于反映背景稠密程度的参数|d|(每个对象具有的平均属性数),用来控制随机数据集的大小和稀疏程度。实验结果见图3~图5。图中横坐标表示对象数,纵坐标为表示时间(或|d|),曲线上的点表示完成概念计算所用的时间。

实验结果表明:(1)Para-Pruning算法构造出的节点数与Next Closure算法构造出的节点数是相同的,验证了Para-Pruning算法的正确性;(2)Para-Pruning算法比Next Closure算法效率高,说明把基于背景K上的子闭包系统划分为多个子闭包系统,进而分别求概念可以明显地提高运算效率;(3)上述实验结果是在一台机器上实现的,如果进行分布计算,效果会更加明显;(4)形式背景不同,Para-Pruning算法的效率是不同的,背景稀疏的背景效果更为明显。(5)图5中的Sort处理过程所耗时间远低于概念的求解时间,说明了Para-Pruning算法中排序的时间对算法的时间复杂度影响不大。

5 结论

在研究现有的两种并行建格算法基础上,提出了一种基于闭包系统划分的概念格并行生成算法ParaPruning算法。该算法将属性集合的幂集视为闭包的搜索空间,按是否包含一个对象(或属性)将整个搜索空间进行划分,并识别出那些能生成正规子闭包的子搜索空间,再进一步递归划分,从而有效提高搜索效率;在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度。在随机生成的数据集和真实数据集上进行的实验测试表明,本算法的时间性能要优于Next Closure算法。算法还有很多值得研究和改进的地方,如对子闭包系统划分的更为有效的测试及背景划分的深度等方面的问题,将在未来的工作中做进一步的研究。

摘要：随着处理的形式背景的增大,概念格的时空复杂度也会随着急剧增大。研究新的方法和手段来构造概念格,是概念格技术应用于大型复杂数据系统的前提,提高其构造效率的一种有效途径是利用高性能并行计算机和网络并行计算的能力,因此概念格的并行构造算法已成为众多学者的一个新的研究方向。概念格的并行构造思想就是根据不同的原理,采用分治策略,通过对形式背景的拆分,形成分布存储的多个子背景,然后构造相应的子概念格,再由子概念格的合并得到所需的概念格。目前建格算法的分布处理研究主要有形式背景的并置和叠置以及形式背景的折叠搜索子空间划分两种方法,本文在总结研究这两种方法的基础上,基于偏序集上闭包系统分解的思想,对提出的闭包系统划分为多个子闭包系统的判定定理进行了证明,使闭包系统的分解既不会产生冗余信息,也不会使信息丢失,并把所提出的判定定理用于概念格的并行处理,提出了一个新的基于闭包划分的概念格并行生成算法——Para-Pruning算法。通过实验,利用随机生成的数据集同经典NextClosure算法进行比较分析,验证了新算法的正确性和有效性。

关键词：概念格,并行构造算法,闭包系统

参考文献

[1]Bernhard Ganter,Rudolf Wille.Formal Concept Analysis:Mathematical Foundations[M].Berlin,Springer-Verlag,1999.

[2]Fu H,Nguifo EM.A parallel algorithm to generate formal concepts for large data[C]//Eklund P,ed.Proc.of the2nd Int’l Conf.on Formal Concept Analysis(ICFCA2004).LNCS2961,Berlin:Springer-Verlag,2004:394-401.

[3]李云,刘宗田,陈峻,等.多概念格的横向合并算法[J].电子学报,2004,32(11):1849-1854.

[4]Alain Gély.A Generic Algorithm for Generating Closed Sets of a Binary Relation[C]//B Ganter,R Godin Eds.Formal Concept Analysis:3rd Int’l Conf.ICFCA2005,LNAI3403,Springer,2005:223-234.

[5]G Markowsky.Primes,Irreducibles and Extremal Lattices[J].Order,1992,9(3):265-290.

[6]R Godin,et al.Incremental Concept Formation Algorithm Based on Galois(concept)Lattices[J].Computational Intelligence,1995,11(2):246-267.

[7]Jiawei Han,Micheline Kamber.Data Mining:Concepts and Techniques[M].2nd Edition.Beijing:China Machine Press,2006.

并行构造算法 篇2

基于PC-CLUSTER机群并行体系结构与消息传递库MPI并行环境,研究了三维非结构网格DSMC并行算法.提出一类基于结构背景网格上的非结构网格动态分区策略,保证各子区域的分子数量大致相等,实现计算进程间的动态负载平衡.利用MPI库函数构造了两类符合DSMC并行原理的.通讯法:单步通讯法与多步通讯法.采用单控制多数据流(SPMD)以及Master/Slave并行模式,设计了三维非结构网格DSMC整体并行算法.给出了跟踪模拟分子在四面体网格间迁移运动的详细计算过程.最后对全尺寸航天飞机高超声速绕流进行了并行模拟,验证并行算法的有效性.

作 者：王学德 伍贻兆 夏健 谭俊杰 WANG Xue-de WU Yi-zhao XIA Jian TAN Jun-jie  作者单位：王学德,谭俊杰,WANG Xue-de,TAN Jun-jie(南京理工大学动力工程学院,南京,210094)

伍贻兆,夏健,WU Yi-zhao,XIA Jian(南京航空航天大学航空宇航学院,南京,210016)

刊 名：宇航学报  ISTIC PKU英文刊名：JOURNAL OF ASTRONAUTICS 年，卷(期)： 28(6) 分类号：V311.4 关键词：非结构网格   直接物理模拟   DSMC   并行算法   动态负载平衡   MPI  

并行构造算法 篇3

关 键 词：MOS器件；模型参数；参数提取；器件模型

1 引言

器件的模型和模型参数提取是电子设计自动化（EDA）领域的关键工作[1]。采用遗传算法进行半导体器件模型参数提取是近年来兴起并被广泛使用的一种参数提取方法[2-3]。遗传算法全局搜索能力强、不需进行繁琐的求导运算，不依赖参数初始值等特点，理论上来说只要有足够的迭代次数种能找到最优解[4]。但是，由于遗传算法是一种搜索类算法,较之传统的基于梯度进行迭代计算的解析算法, 每进行一次迭代所需要的时间较长，计算量有了显著增加, 而且对许多复杂问题而言，例如采用的全局优化策略提取复杂模型的大量参数时，标准遗传算法的求解效果往往不是解决这个问题的最有效的方法，必须对算法进行修改与优化，这些因素无疑大大增加了遗传算法的计算量，为此必须考虑算法的耗时问题。本文针对遗传算法自身的耗时问题，讨论了并行遗传算法的特点，并以主从式遗传算法为例，证实了并行计算在参数提取工作中的可行性。

2 并行遗传算法

为了有效的解决遗传算法（GA）在模型参数提取过程中的耗时问题, 提高GA的运行速度，采用并行遗传算法（PGA）是提高搜索效率的方法之一。并行遗传算法[5-6]主要有主从式并行遗传算法、粗粒度并行遗传算法和细粒度并行遗传算法。

2.1 全局PGA模型－主从式模型（master-slave model）

如图1所示，主从式模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器。

主从式模型的优点是简单，保留了串行GA 的搜索行为，对计算机体系结构没有严格要求，适合运行在共享存储和分布式存储的并行计算机上。如果适应度估值操作比其他遗传算子计算量大的多时，这是一种非常有效的并行化方法。

2.2 粗粒度PGA模型－分布式模型（distributed model）

该模型又称分布式、MIMD、岛屿模式遗传算法模型。在处理器个数较少的情况下，我们可以将群体分为若干个子群体，每个子群体包含一些个体，每个子群体分配一个处理器，让它们相互独立地并行执行进化。为了防止子群体早熟，每经过一定的间隔(即若干进化代)，各子群体间会交换部分个体以引入其他子群体的优秀基因，丰富各子群体的多样性。除了基本的遗传算子外，粗粒度模型引入了“迁移”算子，负责管理区域之间的个体交换。如图2所示，通常存在两种迁移实现:岛屿模型、踏脚石模型。

2.3 细粒度PGA模型－分散型 (fine-grained model)

细粒度模型又称为邻域模型(neighborhood model)或细胞模型(cellular model)模型。如果并行计算机系统的规模很大，理想情况下处理器多到可以与染色体一一对应，则我们可以将每个个体分配一个处理器，让它们相互独立地并行执行进化，这样就能获得并行遗传算法的最大可能的并发性。如图3所示，在细粒度模型中，通常处理器被连接成平面网格(grid)，每个处理器上仅分配一个个体，选择和交叉只在网格中相邻个体之间进行，所以网格上的邻域关系就限定了个体空间上的关系。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广。

3 基于MPI的主从式遗传算法的的实现

3.1 总体构想

我们采用的主从式并行模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器，其个体的分配过程是这样的：假设种群规模为N, 优化模型参数变量个数为M。适应度评估时，程序传给评价函数N个长度为M的向量。并行的任务是master处理器将这个N个长度为M的向量平均分配到各slaves处理器做适应度计算，计算结束后，评价函数返回N个适应度给master处理器。计算各处理器分得的染色体个数的方法是，首先计算出每个处理器至少分配到的染色体个数为AveNum=N/Size，如果处理器个数不能整除行数，这样将有部分处理器分得到（AveNum+1）个染色体，规定多余的染色体分配到编号小的处理器上。

3.2 并行中的消息传递机制

另外，需要注意的是，仅仅依靠例如C，C++，java等编程语言所编写的程序是无法实现上面叙述的染色体在各处理器之间的传递任务。因为，在并行计算环境中，每个进程均有自己独立的地址空间，一个进程不能直接访问其它进程中的数据，因而，在进行并行计算的任务之间进行的数据传输必须通过消息传递机制。消息传递机制，是指用户必须显式地通过发送和接收消息来实现处理器之间的数据交换。

本文采用的是MPI(Massage Passage Interface)消息传递接口。MPI是一个很好的数据传递软件平台，可以通过调用MPI库函数来进行进程调度以及任务间的通信。它实际上是一个消息传递函数库的标准说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一，其特点是通用性强(只要求网络支持TCP/IP网络协议)、系统规模小、技术比较成熟。本文通过调用MPI的库程序来达到程序员所要达到的并行目的，使异构的计算机群体作为一个紧凑、灵活、经济的计算机资源来使用的并行环境。

3.3 共享内存多处理器主从式并行环境搭建

全局并行化模型并不限定计算机体系结构，它可以在共享内存和分布式内存计算机中高效实现。现在简单介绍一下两种并行编程的方法：分布式内存方法和共享式内存方法。

对于分布式内存的并行计算机，各个处理器拥有自己独立的局部存储器，不存在公用的存储单元，显然，这种方法的问题就产生于分布式内存的组织。由于每个节点都只能访问自己的内存，如果其他节点需要访问这些内存中的数据，就必须对这些数据结构进行复制并通过网络进行传送，这会导致大量的网络负载。他的优点是拥有很好的扩展性，有利于快速构造超大型的计算系统。

在共享内存多处理器计算机中构成并行环境，在共享式内存方法中，内存对于所有的处理器来说都是通用的。这种方法并没有分布式内存方法中所提到的那些问题。而且对于这种系统进行编程要简单很多，因为所有的数据对于所有的处理器来说都是可以使用的，这与串行程序并没有太多区别。这些系统的一个大问题是扩展性差，不容易添加其他处理器。

为了在微机环境下使用MPI构成分布式内存并行环境，只要将PC机联接局域网，然后在每台PC机上安装相应操作系统，并安装MPI软件包即可。分布式内存即种群被一个处理器存储。这个主处理器负责将个体发送给其它从处理器进行评估，并收集计算结果，进行遗传操作来生成下一代。

对于本文所采用的在共享内存多处理器计算机中构成主从式并行环境就更为简单，只要在PC机上安装操作系统（本文安装linux操作系统）和MPI软件包就可以实现并行环境了。在共享内存多处理器计算机中，种群可以保存在共享内存中，每个处理器可以读取被分配到的个体信息并将适应度写回，不会有任何冲突。

4 实验结果分析

将以上方法实现的基于MPI的主从式遗传算法应用于1.2um SOI MOS器件的阈值电压模型参数提取工作中。如图4所示，实验结果表明曲线拟合的效果很好，转移特性曲线最大误差都低于5%。采用并行计算后，参数提取的速度提高了接近2.5倍。

5 结论

从实际的测试效果来看，以上方法实现的程序的简洁有效，智能化程度很高，且具有较高的精确度。因此，本文提出的基于MPI的主从式遗传算法可以解决遗传算法在器件参数提取过程中的耗时问题。该方法简单易用，适合推广使用。

参考文献

[1] J.Liou A,Analysis and Design of MOSFETS: Modeling,Simulation,and Parameter Extraction[M].KLUWER ACADEMIC PUBLISHERS,1998.

[2] Kondo M,Onodera H,Tamaru K.Model adaptable MOSFET parameter extraction method using an intermediate model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(5):400-405.

[3] Yang P, Chatterjee P K, An optimal parameter extraction program for MOSFET models[J].IEEE Transaction on Electron Devices,1983,30(9):1214-1219.

[4] Li Yiming. An automatic parameter extraction technique for advanced CMOS device modeling using genetic algorithm.Microelectronic Engineering,2006,41(4): 1309-1321.

[5] 康立山，非数值并行算法(第一册)-并行遗传算法[M].科学出版社,2003.

并行谱聚类算法 篇4

关键词：谱聚类,相似性矩阵,并行

0 引言

聚类分析作为机器学习领域最为重要的一个研究方向, 在近30年间得到了快速的发展。在解决了各个领域的难题的同时, 聚类算法也发展出不同的算法家族。谱聚类算法因为其优点成为聚类算法中发展较快的一种, 并得到了学者们的极大关注。

谱聚类算法是一种点对聚类算法。其将数据看作图中的顶点, 数据间的某种关系看作图中的边, 从而将原始的聚类学习问题转化为图划分的最优化问题, 并依据谱图理论构建相似性图的拉普拉斯矩阵, 将原始的划分问题松弛为计算数据拉普拉斯矩阵的前k大的特征值及其对应的特征向量的问题, 从而简化了聚类求解的过程, 优化了聚类的质量[1,2,3]。

谱聚类算法最大的问题在于计算复杂度过高, 尤其在计算相似性矩阵及求取拉普拉斯矩阵的特征值、特征向量时, 消耗的时间最多。采用抽样的方法可以降低计算的复杂度, 但是当数据是海量的时候, 这种方法依然面临着计算的瓶颈, 因此本文采用并行的方法将计算分配到网络的计算机上, 从而加速谱聚类算法的收敛[4]。

1 并行计算

并行计算是指通过运行在多个通过某种网络连接起来的计算、存储部件上的较小任务的合作求解规模较大的计算问题的一种计算方法。这是一种随着技术进步及性能要求而发展起来的一种用于解决大规模数据计算和存储的技术。并行计算可以大大降低问题求解的规模及求解时间, 并且容错性更高、可用性更好、吞吐率更高, 因此并行计算的概念从刚刚提出即成为研究的热点。

并行计算的基本思想是分而治之[5]。分而治之是计算机算法中最古老最实用的一种算法, 其基本想法是将类似的工作划分为不同的子任务, 每次完成单个子任务, 从而降低计算的复杂度。在并行计算的系统中, 同样利用了这种思想, 其可分为两个部分:

任务并行。根据问题的特性, 把问题分解为类似的子问题, 分配到不同的处理器或者其他计算资源上处理, 从而提高计算资源的利用率。

数据并行。根据数据的存储结构, 把海量的数据分散到不同的存储设备上存储, 形成多个独立的数据存储区域, 实现数据的并行处理。

1.1 并行计算系统

根据弗林分类法 (Flynn’s Taxonomy) , 计算机按照其指令和数据的执行访问方式可以分为4类:单指令单数据计算机 (single instruction single data, SISD) , 单指令多数据计算机 (single instruction multiple data, SIMD) , 多指令单数据计算机 (multiple instruction single data, MISD) 和多指令多数据计算机 (multiple instruction multiple data, MIMD) 。其中SISD为串行计算方式, MISD仅是为了分类的完整提出的一种架构, 在实际中并不存在, SIMD具有部分的并行能力, 主要用在向量机中, MIMD结构中每个计算单元均有独立的指令及数据, 现行的并行计算系统均可归为此类。

在实际的应用中, MIMD结构按照系统内存的结构又可以分为两大类:共享内存和消息驱动[6]。共享内存方式对于内存空间进行统一的编址, 所有的计算单元均可以访问相同的内存, 不同的计算单元通过读写内存共享数据处理结果, 这种结构的通信机制简单, 但是不同的计算单元访问共享内存时需要加锁, 因此可能降低系统处理数据的速率。消息驱动的方式各个计算单元独享内存空间, 不同的计算单元通过某种网络结构连接, 通过发送消息的方式实现计算结果的共享, 这种结构对于内存的压力远远小于共享内存结构, 并且易于动态的改变整个网络的结构, 具有很好可扩展性, 但是整个系统的效率严重依赖于网络的通信能力, 并且系统的负载均衡及结构的设计均需要开发者完成, 导致设计这种结构的并行系统较困难。当前比较流行的共享内存式的并行计算系统有共享存储对称式多处理机系统 (Symmetrical Multi-Processing System, SMP) 、分布共享存储多处理机系统 (Distributed Shared Memory Multi-Processing System, DSM) , 消息驱动的并行计算系统有大规模并行计算机系统 (Massive Parallel Processing System, MPP) 、集群系统 (cluster system) , 下面对其特点一一分析。

SMP。在SMP结构中, 所有的计算单元共享相同的内存地址空间, 所有的计算单元可以直接访问内存的任意地址, 并且对于任意的计算单元, 其访问延迟、访存带宽均是相同的, 因此这种结构又被称为统一内存访问 (uniform memory access, UMA) 。SMP系统的特点是系统中的计算单元的总线结构是相同的, 并且地址空间编码一致, 不同计算单元间通信仅通过读写内存即可以完成, 因此SMP系统的通信延迟很小, 访存带宽较高, 同时SMP系统往往仅运行一个操作系统的实例, 因此易于根据不同计算单元的繁忙程度实现系统的负载均衡。公用访存总线和内存空间虽然带来了通信开销较低的好处, 但是这种方式的可用性较差, 易于导致内存访问的竞争, 并且一旦存储器或者访存总线出现问题, 将导致整个系统无法使用, 并且当扩展系统规模时, 难以设计交叉开关, 因此导致系统的可扩展性较弱, 一般情况下SMP系统中计算单元的数目不超过64个, 这也决定了SMP系统仅适用于计算规模较小的环境。在实际中, SMP系统常见于小规模并行计算机中, 如IBM50, 曙光一号。

DSM。DSM结构中内存在物理上属于不同的计算单元, 但是在逻辑上共享相同的地址编码空间。在这种结构中计算单元对于不同的内存空间的访问速度是不同的, 计算单元通过本地总线访问本地内存, 通过系统总线访问其他地址空间上的内存, 因此导致访存的速度不同, 所以这种结构也被称为非一致内存访问 (non-uniform memory access, NUMA) 。DSM结构屏蔽了系统中计算单元同非本地内存间通过网络的物理结构, 提供统一的编程模式, 大大降低了DSM系统开发的难度。同时系统可以通过网络接入更多的计算单元, 具有较高的可扩展性。DSM系统兼具共享存储结构和消息驱动结构的优点, 因此具有极高的使用价值。

DSM系统通过系统总线访问非本地内存, 其速度严重依赖于共享总线的带宽, 这也导致不同位置内存访问速度的不同, 一种可行的解决办法是加入一致性高速缓存 (cache-coherent) , 采用基于目录的方法维护缓存的一致性, 这是一种常用的DSM结构。

MPP。MPP结构往往包括成百上千的计算单元, 每个计算单元均有自己独立的总线及内存空间, 不同的计算单元间通过专用的网络连接, 计算单元间通过消息共享计算结果和数据。MPP结构的系统具有很强的计算能力和存储能力, 并且可扩展性很高, 容错性能很强, 某个计算单元发生故障不会导致整个系统失效。但是MPP系统采用专用的网络连接, 需要提供专用的通信部件才能实现较高的通信效能, 导致这种系统的研发、维护和使用的开销极高, 因此MPP结构的并行计算系统往往为国家主持开发和使用的。比较著名的MPP系统有IBM SP2和曙光1000。

集群系统。集群系统中每一个计算单元均是一个独立的计算机, 每个计算单元均有独立的CPU、内存和总线系统, 不同的计算单元通过互联网连接, 每一个计算单元均可以独立工作, 也可以协同完成比较复杂的工作。集群系统的结构灵活, 可扩展性极强, 易于更换或者增加节点, 并且集群系统中每一个节点均是独立的计算机, 因此单个节点的失效不会导致整个系统的失效, 具有极高的鲁棒性和恢复能力。相比于MMP系统采用专用通信网络和专用计算机, 集群系统采用互联网通信和普通的计算机, 因此其具有很高的性价比。

集群系统最大的瓶颈为通信开销过高, 并且系统效率严重依赖网络的吞吐率, 如何设计高效低价的通信系统是所有集群系统必须考虑的问题。其次集群系统需要合理的调度计算资源, 因此严重依赖于负载均衡算法的调度。

1.2 并行计算编程模型

上小节中介绍的是并行计算不可或缺的底层的硬件平台, 本节分析当前比较流行的并行计算编程模型。

当前最重要的并行编程模型共有两种, 其一为消息传递, 其二为数据并行。数据并行编程模型编程较为简单, 这种编程模型提供了一种全局的地址空间, 通过指定并行操作的对象即可以实现并行化的编程, 但是这种模型仅仅适用于特定的并行计算系统, 因而应用的范围并不广泛, 常用的有Open MP (Open Multi-Processing) 。消息传递并行编程模型编程较为复杂, 需要开发者控制不同进程间的消息的传递、协调进程的执行, 但是可用于的并行系统极多, 不仅仅可以用于消息传递的并行系统, 也可以用于共享内存的并行系统, 因此得到了更多的关注, 常用的消息传递编程模型有MPI (Message Passing Interface) 、MAP/REDUCE等[6]。下面对这些编程模型进行详细的讨论。

Open MP。Open MP是用于共享内存并行计算系统的一种并行计算编程模型, 它支持在多处理机上编写并行程序, 利用共享内存结构的共享内存空间地址的特性, 高效的实现了程序的并行化。Open MP编程模型包括三部分:运行库 (runtime library) 、环境变量 (environment variable) 和编译器指令 (compiler directive) 。Open MP通过环境变量及编译器指令指示编译器如何并行化程序, 并提供了运行库支撑并行系统的运行。

Open MP编程模型简化了并行编程的难度, 开发人员仅需很小的学习曲线即可以掌握高质量的并行算法设计方法, 并且Open MP的库函数对开发人员屏蔽了底层的并行粒度、负载均衡等并行系统需要解决的难题, 因此可以使得开发人员将精力投入到算法设计本身, 降低开发的代价。同时Open MP作为一种开放的并行计算模型得到主流的计算机硬件软件厂商的支持, 因此采用Open MP的并行程序具有极好的可移植性。但是Open MP编程模型仅仅支持共享内存结构的并行计算系统, 这限制了它的使用范围。

MPI。MPI是一种基于消息传递的并行化编程模型, 是用于非共享式内存并行计算系统的编程接口的标准定义。MPI以较低级的消息传递的方式同步不同计算单元的计算结果, 协调计算单元的负载, 编程形制较Open PM灵活, 并且MPI在当前流行的PC系统中都有相应的实现, 因此具有很好的可移植性和广泛的适用性。此外MPI提供了语言无关的编程接口, 通过函数库的方式实现相应的功能, 因此不需要编译器的直接支持, 这使得MPI程序具有很好的跨平台的特点, 简化了开发人员的学习过程, 因此MPI并行编程模型成为当前最为流行的并行编程模型之一。

虽然MPI编程模型具有非常广泛的适应性, 但是其仍然存在不少的问题。MPI需要开发人员自行解决通信和资源调度的问题, 增大了开发的难度, 并且对MPI程序的调试比较困难, 当系统中某个进程失败时, 将导致系统的崩溃, 鲁棒性不如Open MP模型。

MAP/REDUCE。MAP/REDUCE并行编程模型是谷歌公司最早提出的, 用于解决海量数据环境中大规模计算的问题。MAP/REDUCE编程模型将计算过程分解为了MAP和REDUCE两个阶段[7], MAP阶段根据数据键值归类成不同的分组数据, 经过调度和洗牌后, 不同的分组交由不同的REDUCE程序进行处理, 并通过合并得到最终的结果。MAP/REDUCE并行编程模型将负载均衡、联网通信等复杂的底层实现隐藏在系统的内部, 对外部提供了统一的编程接口, 开发人员只需要实现Map函数和Reduce函数即可完成并行计算的任务。

MAP/REDUCE并行编程模型适用于内部松耦合的任务, 对于这种任务可以高度的并行化, 现在已经实现的云计算平台多采用这种编程模型, 并且模型对于异构的集群系统具有很好的适用性, 部署的代价极低, 因此MAP/REDUCE并行编程模型成为当前最为流行的并行编程方式。但是MAP/REDUCE并行编程模型对于紧耦合的任务无法很好的处理, 计算过程相当繁琐, 并且由于计算过程中需要对中间结果进行归并分组, 因此系统对于通信网络的依赖极重, 其通信效率严重影响系统的性能。图5.3展示了MAP/REDUCE的一般流程。

2 并行谱聚类算法

本节讨论如何利用MAP/REDUCE框架在集群上实现并行化的谱聚类算法, 并通过在图片数据集上的实验验证算法的有效性。

整个计算过程在Hadoop环境下实现, Hadoop是MAP/REDUCE框架的一个开源的java语言实现。

Hadoop框架将计算同数据分离, 底层为分布式文件系统Hadoop Distributed File System (HDFS) , 它负责存储系统中所有的数据, 上层为MAP/REDUCE计算引擎, 负责计算任务的执行。HDFS系统及计算引擎均采用主从结构, 在HDFS系统中主节点被称为Name Node, 负责决定文件块由那些节点存储以及跟踪整个系统中文件存储的整体情况, Data Node节点负责系统中真正的文件的读写以及存储工作。计算引擎通过Job Tracker进程分配计算任务给集群中的节点, 而Task Tracker负责节点中计算任务的执行。Hadoop框架的典型架构如图4所示:

谱聚类算法可以分为三个阶段:预处理阶段, 特征分解阶段和聚类阶段。预处理阶段主要实现计算相似性矩阵和拉普拉斯矩阵, 特征分解阶段主要实现特征值及特征向量的计算并拣选前k小的特征值对应的特征向量作为最终降维后的数据集表征, 聚类阶段利用k-means算法实现最终的聚类。因此, 并行算法的设计可以从这三个阶段着手。

预处理阶段。当数据量规模较大时, 单个计算机的内存很难将所有内容装入内存, 因此可以利用MAP/REDUCE框架将计算分布到不同的机器上去。假定集群中机器的数量为m, 首先将整个数据集平均的分配到m台机器上, 每台机器计算N/un个数据的相似性关系, 并计算相应的度矩阵及最终的拉普拉斯矩阵。基本思想如图5所示:

在每台机器上均有一份完整的数据备份, 这可以减少计算时网络中数据的交换流量。每台机器中完整的数据文件并没有完全装入内存, 而是分片读入的, 这样可以减少计算所需要的内存空间。

计算相似性矩阵的过程实际上分解为两个阶段:第一个阶段为计算相似性值阶段, 第二个阶段为对称化相似性矩阵阶段。

首先进行的是第一个阶段。由于文件中的每行数据表示一个数据点, 因此按照MAP/REDUCE的思想, 首先MAP阶段根据数据行在文件中的偏移将数据读入内存中, 然后根据数据所处行号的不同映射到不同的机器上。在REDUCE阶段, 对每行数据分别计算其同其他数据间的欧氏距离, 并按照其大小关系选择最小的k个保留下来, 这一步为了减少内存空间的使用, 可以仅仅预留前k小的数据的一个有序序列及其所对应的下标, 然后对这前k小的数据计算其相似性, 并在写入文件时将同其他数据间相似性值置为0, 并写入文件中, 写入文件的格式为 (相似矩阵行号, 列号, 值) , 同时为了将其对称化, 每个非零行交换行号、列号后写入两次, 这个阶段完成了基本相似性矩阵的计算, 但是这样得到的相似性矩阵并非对称的, 因此在第二阶段将相似性矩阵对称化。

第二阶段以计算相似性矩阵第一段的输出作为输入, 在MAP阶段以输入文件中的相似性矩阵的行号及列号域作为key值, 相似性值作为值域进行映射, 在REDUCE阶段key域同MAP阶段, 值域为MAP阶段值域的均值, 然后写入文件, 写入文件的格式为 (相似矩阵行号, 列号, 值) , 在完成这两个阶段后得到相似性矩阵即是一个对称的稀疏相似性矩阵, 最终的输出存在不同的节点上。

特征分解阶段。由于预处理阶段得到拉普拉斯矩阵为稀疏对称半正定阵, 因此可以利用Lanczos方法计算特征值及特征向量。Lanczos方法是一种迭代的算法, 首先通过Lanczos迭代计算出一个对称的三对角矩阵T=CTLC, 其中C为迭代过程中得到转移矩阵, L为拉普拉斯矩阵。通过QR方法求解T的特征向量ui, 那么L矩阵的特征向量vi可以通过下式得到:

由于T矩阵的规模远远小于L的规模, 因此整个求解过程计算量最大的是Lanczos迭代过程, 并行化的重点也在这一阶段。

Lanczos迭代过程如算法1所示:

算法1 Lanczos迭代过程

在预处理阶段得到的拉普拉斯矩阵是分布存储在集群上不同的节点, 因此只需要将初始化步骤中得到C0、C1按照预处理阶段数据的分布方案分配到节点去, 然后在每个节点上计算Step 2中的步骤a和b, 最后将各个节点上对部分的aj值的计算加起来, 即可以得到aj, 按照相同的原理计算βj+1, 并在主节点生成CT, 这样即可以完成迭代过程的并行化, 在得到T矩阵后, 然后利用QR分解得到T的特征矩阵, 并将其分配到不同的节点计算L矩阵的特征向量, 并存储在各自的节点上。

聚类阶段。此处采用与计算相似性矩阵时相同的策略, 首先将特征分解阶段得到的前k小的特征值对应的特征向量通过网络传播到每个节点, 然后分割计算任务到各个节点, 每次迭代产生新的聚类中心通过Job Tracker传播到整个网络, 并参与下一轮的计算直到计算过程收敛。

下面分析并行算法的计算复杂度。计算相似性矩阵的第一个阶段的计算复杂度为O (n2) , 其中n为数据点的个数, 对称化阶段的计算复杂度同样为O (n2) , 因此整个阶段的计算复杂度为O (n2) , 整个计算非配到m台机器上去, 因此该阶段的计算复杂度为

采用Lanczos方法计算特征向量所需的时间复杂度为O (k·n2) , 但是由于相似性矩阵及转移向量均是分布在不同的机器上, 因此最终的计算复杂度为:

k-means聚类阶段同样是分布在不同机器上进行的, 因此其计算复杂度为:

因此整个算法的计算复杂度为:

3 实验

实验环境为hadoop集群, 集群中共有三台机器, 每台机器的内存为512MB, CPU为1GHZ、单核, 集群中有一台机器作为中心节点, 并且其本身也参与计算与数据的存储。

实验数据集为来自Corel图像数据集中的5000幅图像, 这些图像共分为35类。每幅图像的色度表示分成了12个格, 并在其上分别计算其颜色直方图、均值、方差等9种颜色特征, 得到一个108维颜色特征向量, 此外将图像纹理通过DWT滤波得到9种子图组合, 并计算每种组合的均值、方差等特征, 得到一个36维的纹理特征向量, 并将二者组合起来表示一幅图像, 因此每幅图像采用一个144维的特征向量表示。

下面为并行谱聚类算法加速的对比:

(单位:秒)

上表的计算结果为3次实验的平均值, 近邻数设置为10, 高斯函数的调节参数设置为5, 类别数设置为35, 特征分解阶段Lanczos生成的转移矩阵的秩同聚类数, k-means聚类阶段迭代次数最大设置为1000。

从表中可以看出, 当增加集群中机器的数目时, 程序整体运行的时间将会减少。但是由于存在网络通信以及Hadoop系统本身会带来一些时间开销, 因此算法计算复杂度的减少并不像理想情况下为线性减少的。同时由于在构建相似性矩阵的阶段job划分较小, 导致Hadoop系统开销过大, 因此使得其加速的效果并不是那么理想。

图6展示采用一台slave与两台slave消耗的时间对比及加速比。图中左侧子图为程序消耗的时间, 左侧图中第一组数据位slave为1台时的结果;右侧子图为加速比, 依次为相似矩阵构建、特征分解、kmeas和总时间的加速比, 加速比的计算方式为:

从图6中可以看出采用更多的机器时可以很好的提高算法的计算速度。

4 结论

本章首先介绍了并行计算的硬件环境以及常用的并行计算模型, 然后在MAP/REDUCE环境下实现了谱聚类算法的并行化, 验证了并行环境对于解决大规模数据处理的有效性和可行性。

在Hadoop环境中构建相似矩阵的过程较为耗时, 因此希望在未来的研究中找到一种较好的映射方法, 改善算法的效率, 提高算法的性能。

参考文献

[1]Donath, Hoffman.Lower bounds for the partitioning of graphs[J].Res Develop, 1973, 17:420-425.

[2]M.Fiedler.Algebraic connectivity of graphs[J].Czechoslovak Math, 1973, 98 (23) :298-305.

[3]Wu, Leahy.An optimal graph theoretic approach to data clustering:theory and its application to image segmentation[J].IEEE Trans on PAMI, 1993, 15 (11) :1101—1113.

[4]Luxburg.A tutorial on spectral clustering[J].Statistics and Computing, 2007, 17 (4) :395-416.

[5]孙世新, 卢光耀, 张艳.并行算法及其应用[M].北京:机械工业出版社, 2005:5-10.

[6]李建江, 薛巍, 张武生, 张卫华.并行计算机及编程基础[M].北京:清华大学出版社, 2011:6-9.

并行机调度遗传算法研究 篇5

并行多机调度问题是NP-Hard问题，它既有丰富的研究内容，同时在生产调度，机械制造等方面有广泛的实际应用价值。但是在实际操作中，人们常常按经验法则 (如处理时间短优先调度或到期日早优先调度) 进行调度，这样得到的调度结果一般不能满足实际环境的需求，而且当并行机数和工件数增加时，问题的复杂度成指数增加，传统方法不适合解决此类问题。目前的并行机调度问题研究大部分是集中于简化问题，然后寻找最优解或次优解。

如何使并行机调度问题更接近实际生产状况并找到次优解成为本问题研究热点之一。遗传算法由于其固有的全局搜索与收敛特性，能够较好地解决此类优化组合问题。用遗传算法解决并行机调度问题已经有相关研究，其中Cheng提出一套方案，利用特殊符号 (*) 和工件号组成染色体，特殊符号为分隔符，将工件分成不同的组，每个工件组指派到不同的并行机中。本文对Cheng的方案进行了改进，并且把工件延迟与提前完成成本、机器闲置时间成本和机器设备启动成本等列入考虑因素，使多机调度问题的解决更接近实际的生产状况，目的在于求得考虑实际因素下的次优调度结果，以降低存货存储、交货延迟的违约、设备及人力等成本。

（二）遗传算法与并行机调度问题

1. 遗传算法

遗传算法是一种模仿自然界中优胜劣汰自然选择规则的随机搜索方法，该算法是从一系列的初始点 (被称为初始种群) 开始，通过循环执行选择、交叉和变异等遗传操作，逐步得到问题接近全局的最优解。

2. 并行机调度问题

考虑并行机调度中的实际需求定义如下并行机调度问题：设有m (m>1) 台并行机M1, M2, …Mm，需要加工n个工件，F时调度工作结束，每个工件订单零时刻到达，可在任一台机器上完成加工。工件一旦分配给某机器加工就必须加工完毕，不许中断。工件i在机器j上加工前准备时间为Zij，加工时间为Tij，工件i的到期时间为Qi，机器j一天的工作时间为Wj，启动成本为Sj，闲置成本权重比例为Rj，则工件i的完成日期Ci为本身加工前准备时间Zij (j为工件i的加工机器) 、加工时间Tij与机器j中i工件之前所有工件消耗时间之和，提前完成时间Bi为max (0, Qi-Ci) ，延迟时间Di为max (0, Ci-Qi) ，机器j的闲置时间为Ij (F减j上最后一个工件完工时间) 。问如何安排每台机器上所加工的工件及加工顺序使成本最小。

（三）算法设计

在Cheng的方案基础上，提出了一个染色体的改进的编码组成方式，重新设计了适应度函数和进化机制。

1. 染色体编码与适应度函数设计

并行机调度问题的染色体必须表示两个方面的信息：一方面确定工件加工所在的机器，另一方面确定每台机器上工件的加工顺序。本算法中染色体编码时用自然数序列表示工件排列，用含数字下标的分隔符*i (0

遗传算法演化过程的目的在于使适应度函数最小化，如果用B, D, S, I分别表示提前、延迟、重启和闲置成本，则演化的目的是要找到最好的排列使得：

F (B*, D*, S*, I*) =min{F (B, D, S, I) }, 适应度函数为F,

Bi, Di, Sj, Rj, Ij意义同上，α (Bi) , β (Di) 分别为提前和延迟完工成本函数，γj的值在机器j上有工件分配时等于1，否则为0。

2. 种群初始化

初始种群的个体分为两类，第一类个体随机生成;另一类个体可以按一定经验法则生成，比如可以把处理时间作为考虑因素，处理时间越短越先安排，确保在最短的时间里做尽可能多的工件，或者按到期日期为标准，越早到期的工件越早安排，可以使大部分工件如期完成。

3. 选择

选择过程的目的是为了从当前群体中选出优良个体，使他们有机会作为父代将其优良的个体信息传递给下一代，使子代向最优解逼近[1]。判断个体优良与否的标准是各自的适应值。每个个体的选择概率采用基于排序的适应度分配 (rank-based fitness assignment) 方法，种群按适应度进行排序，个体的生存概率使用Baker提出的线性排序计算公式求得：其中i为个体排序序号，N为种群大小，1<=η+<=2, η–=2–η+。然后用轮盘赌选择法 (roulette wheel selection) 来决定每个个体的选择份数，选择后的N个个体送到配对库，以备配对繁殖。

4. 交叉

交叉是结合来自父代种群的信息产生新的个体，依据个体基因编码表示方法的不同有多种交叉算法。这里采用两点顺序交叉 (OX) ，顺序交叉能够保留排列并融合不同排列的有序结构单元。如有下面两个父个体，交叉操作步骤如下：

(1) 随机选择两个交叉点”|”，保留交叉点之间的中间段不变。

(2) 把父个体2从第2个交叉点作排列，到达表尾时返回表头继续，得到排列*3 2 7*4 8 4 1*2 5*1 3 6，减去父个体1中已有基因部分4 5*1*3 2得到排列顺序7*4 8 1*2 36，再将这个顺序从第2个交叉点开始复制给子个体1，以此决定子个体1对应位置的未知码x，生成子个体1即q1: (3 64 5*1*3 2 7*4 8 1*2) ，同样产生子个体q2: (*3 2*2 5*13 6 7*4 8 1 4) 。

5. 变异

变异是子代基因按小概率产生的变化。同样可以采用多种方法实现基因变异，如可以采用交换两个基因位置实现变异，但是这种方法个体变异较小，不利于新个体的生成，特别是当交换的两个基因都是数字时，新个体只是改变了两个工件的加工位置。这里使用另外一种方法实现变异操作即首先随机选取父代中的某优秀染色体，对照染色体基因个数 (m+n) 随机生成一个二进制序列，将染色体中对应0的基因选为一组，对应1的基因选为另一组，两组基因重新组合得到子个体。变异操作如下：

6. 种群进化与停止准则

标准遗传算法若在群体选择前 (或后) 保留当前最优值，则最终能收敛到全局最优值。本算法通过改进标准遗传算法，在群体选择作用前保留当前最优解，则保证本算法在某些情况下收敛到全局最优解。

停止准则一般预先设定一个最大的繁殖代数Nmax，在繁殖过程中进行到最大的繁殖代数则停止运行。

综上所述，本并机行排序问题的遗传算法伪码如下：

（四）结果

设有45个工件要在3台机器上加工。在工作提早与延迟完成成本方面，按照工件的重要性将提前与延迟完成成本公式分为三类：

对重要性不高的工件成本公式为：

对重要性一般的工件成本公式为：

对优先权高的工作成本公式为：

工件在不同机器上的加工时间，加工前准备时间，机器启动和闲置成本表略。种群大小为50，最大遗传代数为80，交叉概率为0.6，变异概率为0.01。按本文与Cheng所提算法分别演算，所得结果如表1所示：

由表1可知，本文算法有助于使最后解答的染色体之间的差异性小，每次运算后的解接近最优解。

（五）结束语

本文重新设计了染色体的组成方式，问题的解空间表示得更明确，设计了算法进化机制，求解效率得到提升，考虑了并行机调度问题中的更多实际因素，本算法有一定的实用价值。然而实际影响并行机调度的因素并不限于本文所讨论的范围，另外适应度函数中的权重比例，也需要根据不同工厂的需求做适当的调整。今后将研究影响并行机调度的其它一些因素，使并行机调度问题与实际应用紧密结合，并且考虑把遗传算法与其它算法结合，使遗传算法收敛更快更高效。

摘要：为解决接近实际生产状况的并行机调度问题, 将工件延迟与提前完成成本、机器闲置时间成本、机器启动成本列入考虑因素。在遗传算法的设计上, 提出了一套染色体的组成方式, 设计了适应度函数和进化机制, 使其能较好地表示问题的解空间并提升求解效率, 具有一定的实用价值。

关键词：并行机调度,遗传算法,适应度

参考文献

[1]何军辉, 周泓.求解含调整时间并行机排序问题的遗传算法[J].系统工程理论方法应用, 2002, 12.

[2]欧锦文, 施保昌.平行机排序邻域搜索算法设计[J].计算机工程与应用, 2003, 18.

[3]Cheng, Runwei.Minmax Earliness/Tardiness Scheduling in Identical Parallel Machine System Using Genetic Algorithms[J].International Conference on computers and industrial Engineering, 1995:29:513-517.

[4]张聚, 李平.基于演化算法的车间作业调度问题的求解方法[J].浙江大学学报, 2004, 12.

并行构造算法 篇6

近年来, 随着电子技术的快速发展, 电力系统暂态录波明显向高采样率、连续稳态记录和海量存储的趋势发展[1]。其中, 为了提高海量故障录波数据的传输效率和降低存储空间, 众多文献提出了各种各样的数据压缩算法[2,3], 但是, 随着电力通信网络的改善, 百兆、千兆以太网大规模安装, 通信效率已经不再是难以克服的瓶颈, 因此, 目前众多厂家已经开始放弃了原有复杂的压缩方案, 而直接在高速以太网上传输录波数据。目前, 这种录波数据海量化趋势已经给各种基于串行编程方式设计的分析软件[4,5,6,7]增加了不小的计算压力, 其中最明显的就是海量录波记录文件解析时间过长而导致的软件效率低下。而在计算机硬件技术发展方面, 目前已经进入多核计算时代, 原来传统的面向单核的串行编程技术被完全颠覆, 逐渐被基于多线程模式的并行编程技术所取代[8]。

针对这2个方面的发展趋势, 本文研究并实现了海量电力系统暂态数据交换通用格式 (COMTRADE) 数据文件的并行解析算法。算法可极大地提高面向海量故障录波数据、海量广域测量数据和海量电能质量录波数据的软件处理效率, 并可随着未来CPU核数的增加和COMTRADE数据文件的加大获得线性加速比[8]。

1 COMTRADE标准

为规范不同厂家的电力数字记录设备进行系统故障录波与暂态仿真的存储格式, 便于第三方的处理和分析, IEEE在1991年制定了COMTRADE标准 (IEEE Std C37.111—1991) [9]。最新修订的1999标准 (IEEE Std C37.111—1999) 规定与记录信息相关的文件有4个:头标文件、配置文件、数据文件和信息文件。其中对于第三方暂态数据分析软件而言最重要的是配置文件和数据文件, 其他文件是可选的。

数据文件记录着每个采样通道中的每个采样数值。数据文件可以是美国标准信息交换码 (ASCII) 格式或二进制格式。二进制数据文件与ASCII数据文件格式类似, 每一行应分为“TT+2”列, 其中TT代表配置文件中模拟量通道和状态量通道的总和, 另外2个是采样序号和时间标记。二进制文件以比特形式集中存放状态量通道数据, 各个数据之间没有分隔符, 每组采样值之间没有回车换行符隔开。各列的具体内容如下所示:第1列为采样序号;第2列为采样数据的时间标记;第3组的列为表示模拟量通道信息的采样数据值;第4组的列为表示状态量通道信息的采样数据值。

2 并行解析算法设计

2.1 二进制数据文件并行解析算法

二进制数据文件的并行解析算法原理如图1所示。

由图1可知, 二进制数据文件的并行解析算法被设计为2个阶段的并行流水线[10,11]结构:

1) 第1个阶段:由读取线程依次读取COMTRADE数据文件中的静态数据块Bs1～Bsn (块大小为LNOneRowBytes, L为算法预先设定的每次最多读取的采样次数, NOneRowBytes为每次采样所占字节数) , 进入共享解析队列DequeBinary中, 形成最大队列长度为m的待解析数据队列。

2) 第2个阶段:为每个CPU核启动J个线程, J个线程中有Z个可并发解析数据, 而剩余的J-Z个线程则必须等待, 并不断地向共享解析队列请求新的数据块。

此算法中解析结果作为已经被预先分配大小的全局向量组被全部的解析线程共享, 不同解析线程在解析时以序号信息为下标直接插入到不同向量对应的位置中, 线程之间的工作完全不相干, 解析阶段可彻底地并行执行。

2.1.1 关键数据结构

共享解析队列DequeBinary的接口定义如图2所示。

由于有多个线程同时访问此队列, 所以对出队列函数pop_front、入队列函数push_back和清空函数clear进行了同步处理, 加入了临界区变量m_lock。队列元素及其相关重要变量的定义如下:

2.1.2 并行解析算法的详细步骤

二进制格式数据文件并行解析算法的具体步骤如下:

步骤1:解析配置文件获取模拟量通道数NACount和状态量通道数NDCount, 计算出每次采样所占字节数NOneRowBytes和采样总数NSamples。建立时间数据向量Tv、NACount个模拟量数据向量Av、NDCount个状态量数据向量Dv。并将这些向量的大小设置为采样总数NSamples, 并分配相应的内存。

步骤2:创建共享解析队列DequeBinary。

步骤3:通过操作系统应用编程接口 (API) 获取到当前系统的CPU核数P。逐个创建解析线程, 为保证算法运行过程中每个核都处于最大工作状态, 为每个CPU核启动J个解析线程 (J≥2) , 总共PJ个解析线程。而后通过操作系统API为每组线程指定相应的CPU核。线程创建后被设置为挂起状态。

步骤4:启动读取数据线程, 使能各个被挂起的解析线程。动态分配一个队列元素BLOCK_BINARY, 按LNOneRowBytes大小读取数据文件, 并将数据指针保存到pBuffer中, 而后填入NRealSamples, 最后将队列元素指针压入队列中。持续此过程直到队列已经填充了m个动态分配的BLOCK_BINARY指针。假如发现队列元素个数小于m, 则重复以上程序, 持续此过程直到全部文件数据被读取完毕。

步骤5:被映射到同一CPU核的线程组同时向共享解析队列请求BLOCK_BINARY块指针, 其中只有固定数量的线程可被分配BLOCK_BINARY块指针, 其他线程必须等待。

步骤6:监视DequeBinary是否为空, 假如是就激活通知退出事件, 等待所有线程退出, 完成并行解析。

2.1.3 解析线程内的算法

解析线程在获取结构BLOCK_BINARY的有效指针pCB后, 根据其中自带的信息可快速解析pBuffer中的数据块, 解析线程内的算法伪码如下:

从上述伪码片段可知, 通过利用以往在串行解析中无用的采样序号信息, 实现了快速的信息解析和插入, 使得各个并行工作的解析线程完全不相干, 可独立地完成解析工作。

2.2 ASCII数据文件并行解析算法

ASCII数据文件并行解析算法原理如图3所示。

由图3可知, ASCII数据文件的并行解析算法被设计为3个阶段的并行流水线[10,11]结构。

1) 第1个阶段:

由读取线程依次读取COMTRADE数据文件中的静态数据块Bs1～Bsn (块大小为NBlockSize) , 进入共享解析队列DequeAscii中, 形成最大队列长度为m的待解析队列数据块Bw1～Bwm。由于ASCII数据文件中每次采样数据的保存长度各不相同, 所以读取线程每次获得的数据不可能像二进制文件一样对齐, 所以产生了如图4所示的不能被正确解析的上边缘数据和下边缘数据。

2) 第2个阶段:

为每个CPU核启动J个线程, J个线程中有Z个可并发解析数据, 而剩余的J-Z个线程则等待, 并不断向共享解析队列请求新的数据块。每个解析线程首先需寻找出ASCII数据块中的上边缘和下边缘数据, 经过整理后将其分别插入边缘数据向量Ev中。

3) 第3个阶段:

块边缘数据解析线程不断监测边缘数据向量Ev中是否有可被解析的边缘数据, 若有就将数据解析, 而后插入到不同的向量中。

2.2.1 关键数据结构

共享解析队列DequeAscii的接口定义与DequeBinary完全一样, 其队列元素、块边缘, 及其相关重要变量定义如下 (其他向量定义与2.1.1节一样, 此处就不赘述) :

2.2.2 并行解析算法的详细步骤

ASCII数据文件的并行解析算法具体步骤如下 (步骤1～步骤3与二进制数据文件算法所对应的步骤内容类似, 此处就不赘述) :

步骤4:通过数据文件大小和每次读取的NBlockSize计算出读取线程的最终读取次数M, 并将边缘数据向量Ev的大小设置为2M。

步骤5:启动读取数据线程, 使能各个被挂起的解析线程。动态分配一个队列元素BLOCK_ASCII, 按NBlockSize大小读取数据文件, 并将数据指针保存到pBuffer中, 然后填入NRealSize, NSequence和NBlockSize, 最后将队列元素指针压入队列中。持续此过程, 直到队列已经填充了m个动态分配的BLOCK_ASCII指针。假如发现队列元素个数小于m, 则重复以上程序, 持续此过程直到全部文件数据被读取完毕。

步骤6:被映射到同一CPU核的线程组同时向共享解析队列请求BLOCK_ASCII块指针, 其中只有固定数量的线程可被分配BLOCK_ASCII块指针, 其他线程必须等待。

步骤7:块边缘数据解析线程随时扫描边缘数据向量Ev, 发现有配对项就进行解析。当解析次数等于M-1 (读取线程的最终读取次数) 时, 线程就自动退出。

步骤8:监视DequeAscii是否为空, 若是就激活通知退出事件, 等待所有线程退出, 完成并行解析。

2.2.3 解析线程内的详细算法

解析线程在获取结构BLOCK_ASCII的有效指针pCB后, 根据其中自带的信息可快速解析pBuffer中的数据块, 解析线程内的算法伪码如下:

从上述片段可知, 通过利用以往在串行解析中无用的采样序号信息和多线程技术, 使得过去基于ASCII的串行文本流解析变成了并行文本流解析, 从而突破了海量ASCII文本数据解析的瓶颈。

2.2.4 块边缘解析线程内的算法

块边缘解析线程内伪码如下:

从以上伪码可见, 通过将连续2个数据块间的上边缘数据和下边缘数据连接起来就可还原一条完整的采样ASCII数据。块边缘解析线程由于解析工作量很小, 所以可每扫描一次适当休眠一段时间, 再进行新的扫描。

3 算法试验

算法试验计算机配置为:4核, 单核2.4 GHz, 内存2 GB, 硬盘7 200 r/s。分别采用403 MB的二进制格式数据文件和455 MB的ASCII数据文件进行试验, 这2个文件包含33个模拟量通道、64个状态通道。试验结果如表1所示。

从表1可见, 采用并行解析可获得相当高的加速比:在逐渐普及的4核CPU上, 二进制数据文件获得了至少3倍的加速比, 效率提升显著;而ASCII文件, 由于打破了原有的串行文件解析过程, 在4核CPU上获得10倍多的加速比, 效果非常显著。同时由表1推知, 2种并行解析算法都具有线性加速比, 可随着CPU核数的增加和COMTRADE数据文件的加大获得线性加速比。

4 结语

随着中国电力系统自动化的快速发展, 系统安全性的提升必然越来越依靠各种暂态监测数据, 而目前对海量暂态数据研究的着重点在前端压缩算法上, 忽略了后端直接面向海量暂态数据的处理算法。本文所提出的并行解析算法可以让后端处理软件适应多核并行化的硬件发展趋势, 极大地提升软件处理海量暂态数据的效率。

参考文献

[1]白青刚, 夏瑞华, 周海斌, 等.采用高性能集成芯片的故障录波故障设计.电力系统自动化, 2005, 29 (22) :94-96.BAI Qinggang, XI A Ruihua, ZHOU Haibin, et al.Design of fault wave recording device using high performance integrated microchip.Automation of Electric Power Systems, 2005, 29 (22) :94-96.

[2]乐全明, 郁惟墉, 柏传军, 等.基于提升算法的电力系统故障录波数据压缩新方案.电力系统自动化, 2005, 29 (5) :74-78.YUE Quanming, YU Weiyong, BAI Chuanjun, et al.Novel compression scheme of fault recording data in power systems based on lifting algorithm.Automation of Electric Power Systems, 2005, 29 (5) :74-78.

[3]周瑞, 鲍文, 于霄, 等.基于提升小波和混合熵编码的数据压缩方法.电力系统自动化, 2007, 31 (22) :65-69.ZHOU Rui, BAO Wen, YU Xiao, et al.Data compression method based on lifting wavelet transform and hybrid entropy coding.Automation of Electric Power Systems, 2007, 31 (22) :65-69.

[4]郑敏, 黄华林, 吕鹏, 等.故障录波数据通用分析与管理软件的设计.电网技术, 2001, 25 (2) :75-77.ZHENG Min, HUANG Hualin, L Peng, et al.Generalanalysis and management software for transient data from protective relaying and fault recorder.Power System Technology, 2001, 25 (2) :75-77.

[5]宋墩文, 蒋宜国, 许勇.波形数据通用分析系统的设计.电网技术, 2002, 26 (11) :77-79.SONG Dunwen, JI ANG Yiguo, XU Yong.Design of versatile analysis software for waveform data.Power System Technology, 2002, 26 (11) :77-79.

[6]桂勋, 郭凯, 谭永东, 等.基于网络的全图形化故障录波分析软件系统.继电器, 2004, 32 (24) :44-50.GUI Xun, GUO Kai, TANG Yongdong, et al.All-graphic software system for fault record analysis based on network.Relay, 2004, 32 (24) :44-50.

[7]桂勋, 刘志刚, 钱清泉.基于模式的电力系统通用可扩展故障分析软件系统.电力系统自动化, 2007, 31 (15) :99-102.GUI Xun, LI U Zhigang, QI AN Qingquan.General extensible fault analysis software for power system based on patterns.Automation of Electric Power Systems, 2007, 31 (15) :99-102.

[8]AKHTER S, ROBERTS J.多核程序设计技术.李宝峰, 富弘毅, 李韬, 译.北京:电子工业出版社, 2007.

[9]IEEE Std C37.111—1999IEEE standard common format for transient data exchange (COMTRADE) for power systems.New York, NY, USA:IEEE, 1999.

[10]MATTSON T, SANDERS B, MASSI NGILL B.Patterns for parallel programming.Upper Saddle River, NJ, USA:Addison-Wesley Professional, 2004.

并行量子进化算法的研究与实现 篇7

进化计算是一类模拟生物进化过程与机制求解问题的自组织、自适应人工智能技术,进化算法[1,3,5,6,8]是模拟自然进化过程而产生的一类随机搜索技术,已在人工智能、神经网络及众多的工程应用领域中显示了其解决复杂问题的特别能力。笔者也曾对算法进行改进,提出基于免疫原理的量子进化算法[2](MQEA),并基于Markov随机过程理论,证明了此算法的收敛性。

但无论如何对于大规模或超大规模的求解任务,串行进化算法显然力不从心。进化算法具有天然的并行性,非常适合于在大规模并行计算机上实现,而大规模并行计算机的日益普及,为并行进化算法PEA(Parallel Evolutionary Algorithm)奠定了物质基础。目前典型的并行进化算法主要有全局、粗粒度和细粒度等几种.近些年,许多学者在这方面做了大量研究[4,7]并取得了可喜的进展。然而,如何突破通信瓶颈,充分发挥硬件资源,提高算法性能以及如何使并行进化算法具有更好的可扩展性等问题依然困扰着并行进化算法的进一步发展。

本文分析讨论了并行进化模型理论及性能,将量子的多宇宙特性和进化算法相结合,提出了基于学习的多宇宙并行免疫量子进化算法,算法中将种群分成若干个独立的子群体,称为宇宙。并给出了多宇宙的并行拓扑结构,提出了宇宙内采用免疫量子进化算法,宇宙之间采用基于学习的移民和模拟量子纠缠的交互策略进行信息交换。即在多宇宙并行结构中,宇宙中个体向着各自的目标演化,宇宙之间采用基于学习机制的移民和模拟量子纠缠的交互策略交换不同进化环境下的优秀个体和优秀模式,这样能提高种群多样性有效克服早熟收敛现象,使得搜索效率和搜索能力得到更进一步提高。我们用典型的测试函数验证了算法的并行效果。

1 并行计算模型及理论

使用并行计算机解决一个应用问题时,并行算法的设计是非常重要的。而并行算法最终要成为一个由程序实现的结构依赖的算法,就特别需要一个抽象的并行计算机结构作为研究高效的结构依赖性算法的基础,以保证并行算法适应于广泛的并行计算机结构,并能够依照抽象的结构分析并行算法的效率,以及指导与并行机结构相匹配的并行算法的设计。并行计算模型就是为并行算法的设计、分析而研究出的并行计算机的抽象结构。

当前对进化计算所进行的理论研究工作主要包括如下几类:表示理论、操作子理论、结构化算法、收敛性理论、适应值景象理论、一致性理论、工作模型理论和物种形成理论与小生境,其中,结构化算法、一致性理论与工作模型理论和并行进化计算直接相关。无论是串行算法还是并行算法,计算复杂性都是算法效率的度量尺度,是评价算法优劣的重要依据。一个算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多,算法的复杂性越高;反之,所需的资源越少,则算法的复杂性越低。下面我们介绍度量并行算法性能的一些基本概念:算法复杂度、加速比和效率等。

1) 运行时间

定义1 并行算法的运行时间是指算法在并行计算机上求解一个问题所需的时间。即表示算法开始执行到执行结束的这一段时间。如果多个处理机不能同时开始或同时结束时,则算法的运行时间定义为:从最早开始执行的处理机开始执行算起直到最后一台处理机执行完所经过的时间。

2) 加速比和效率

并行加速比是表示采用多个处理器计算速度所能得到的加速倍数。设tseq表示用串行机求解某个计算问题所需的时间,tp是用P个处理器求解该问题所需的时间。

定义2 并行加速比Sp=tseq/tp,这里tseq是表示用串行机求解该问题所需的时间。并行程序的效率定义为:Ep=Sp/p,其中P为处理器个数,加速比Sp接近P时,效率易接近于1,影响并行效率的因素很多。

2 并行免疫量子进化算法研究

MQEA引入了量子比特的概率描述和量子旋转门演化机制,通过应用免疫算子能有效地提高算法的运算效率,但MQEA并没有利用生物界物种演化的并行及小生境特点。本文提出了多宇宙并行免疫量子进化算法(MPMQEA)。MPMQEA采用多宇宙并行结构,不同的宇宙向着各自的目标演化,宇宙之间采用基于学习的移民和模拟量子纠缠的交互策略交换信息,具有比MQEA 更快的收敛速度。

2.1 多宇宙并行拓扑结构

并行算法的基本思想是将一个复杂任务分解为多个较简单的子任务,然后将各自任务分配给多个处理器并行执行求解.PEA的三种基本模型:全局并行模型、粗粒度模型和细粒度模型。MQEA 的内在并行性使得它特别适合粗粒度的并行计算。粗粒度模型又称作分布式模型或孤岛模型.是目前最流行的一种并行进化算法.它将整个种群划分为多个子种群,每个子种群独自运行一个串行进化算法。在每个子种群内部进行选择、交叉、变异等遗传操作,且每经过一定遗传代数再在各子种群间交换优秀个体(迁移算子)来丰富各子种群的多样性,减小了未成熟收敛的可能性。

在PEA中,一个重要问题是如何降低通信开销,包括:1)迁移率的确定;2)拓扑结构的确定;3)迁移间隔,表示两次迁移之间间隔的演化代数;4)迁移策略。这4个主要参量对迁移的效果和性能起到不同程度的作用,共同决定了迁移算子的行为特性。其中拓扑结构对并行遗传算法的整体性能是非常重要的,它控制着优质遗传信息在各个子种群中的传播方式和速度,也就影响了整个算法的收敛速度。许多学者试图通过比较在不同的拓扑结构上并行进化算法的实验结果寻求算法性能的提升[7]。粗粒度模型中,采用随机选择方式来进行岛屿之间的迁移缺乏一定的导向,不利于各岛屿向着自己最有利的方向发展。

本文采用改进的粗粒度模型,如图1所示。在各宇宙中选择一虚拟服务器,称为master种群,其余处理器称为slave种群,master种群保存各slave种群中的优秀个体。slave种群和master种群间迁移优秀个体,形成星状结构,而各宇宙的master服务器以环状相连,这样可以有效减少在各宇宙间的通信开销。特别是基于学习的个体迁移能引导各宇宙向着自己最有利的方向发展。

2.2 多宇宙之间信息的交换

本文采用基于学习的移民(图2)和模拟量子纠缠的交互两种策略来实现多宇宙之间信息的交换。 通过各宇宙之间的移民和交互,使得一个宇宙内的信息发生变化,能迅速引起其他宇宙的信息发生变化。

2.2.1 宇宙间学习算子

宇宙间学习算子是通过控制slave种群内部部分个体对master种群的全局最优模式的学习来实现的。基于学习的个体迁移策略,能根据种群的平均适应度调节学习频率。通过slave种群向master种群迁移最优个体以及低平均适应值的slave种群向master种群的优秀模式学习加快了算法的收敛进程。考虑到算法本身的仿生学特征,利用生物学的观点解决群间学习频率的选取问题。当一个种群的平均适应度较低时,该种群为了赶超其他种群,应更有必要向优秀模式学习,因此设定低平均适应度的种群的群间学习频率高。

宇宙间学习操作算法如下:

1) 生成[0,1]之间的随机数rand,如果rand<Ps(Ps为slave种群的学习频率),则执行下面的操作;

2) 向master发送宇宙间学习请求,在可能的情况下获取master上的全局最优模式;

3) 计算宇宙中个体的适应度,并调整Ps,Ps可如下计算:

${\rm P}s=\mu \frac{\text{m}\text{a}\text{x}\text{f}\text{i}\text{t}\text{n}\text{e}\text{s}\text{s}\text{a}\text{v}\text{e}\text{f}\text{i}\text{t}\text{n}\text{e}\text{s}\text{s}}{\text{m}\text{a}\text{x}\text{f}\text{i}\text{t}\text{n}\text{e}\text{s}\text{s}\text{m}\text{i}\text{n}\text{f}\text{i}\text{t}\text{n}\text{e}\text{s}\text{s}}$

maxfitness,minfitness,avefitness分别为宇宙中的最大适应度,最小适应度,平均适应度,μ为调整系数,一般取1.0。

2.2.2 种群交互

在MPMQEA 中最能体现各宇宙结构信息的是各宇宙的演化目标。于是我们提出了一种种群交互操作。通过在两宇宙之间暂时交换各自的演化目标,使得本宇宙的结构信息有效地传递给另一参加交互的宇宙,并对对方宇宙的演化方向产生影响,同时本宇宙也从对方宇宙的演化目标中获得对方的演化信息。具体实现如下:

(1) 按确定的选择概率从宇宙中选取若干个体;

(2) 再随机选取若干其他宇宙,分别以各宇宙的演化目标作为若干个体当前的演化目标,对个体进行一次量子旋转门演化操作;

(3) 重复(1)和(2) 操作,直至全部宇宙都进行量子纠缠交互操作。

移民操作和量子交互操作都可实现宇宙间信息的交互,但两者侧重点不同。前者是将最佳个体按确定的拓扑结构和移民策略,在各宇宙中传递;后者是将各宇宙的演化目标通过量子交互的方式进行交互。 两者相辅相成,使得整个系统的收敛速度加快,运算效率提高,且能有效地避免早熟收敛。

2.3 多宇宙并行免疫量子进化算法的算法流程

MPMQEA算法的具体步骤如下:

1.初始化各宇宙中的所有子种群:按照宇宙的数目将整个种群分成若干个子种群,并将所有的子种群进行初始化。

2.选择一master种群作为虚拟主服务器,其余种群为slave种群。

3.进入循环:

(1) 每个子种群单独进化若干代。

(2) 在master种群和slave种群之间执行基于学习的移民,在宇宙间执行模拟量子纠缠的交互。

(3) 重新循环,直至规定的遗传代数或演化目标。

MPMQEA所需的种群规模小,只需在master种群和slave种群间迁移最佳个体,从而通信开销很小,master种群能及时获得全局最佳个体。若计算规模大可以选择多个master种群,各master种群间以环形结构相连,master种群中可再选择一种群作为虚拟主服务器,以交换和保存各master种群中的最优个体。slave种群需要学习时可获取此master种群中的最优个体。

3 实验结果及分析

本文选取了Ackley函数f1,对多宇宙并行免疫量子进化算法(MPMQEA)的并行性能进行测试。

f1(x1,x2)

$=-c1\exp (-c2\sqrt{\frac{1}{2}{\displaystyle \sum _{i=1}^{2}x}i{}^2})-\exp (\frac{1}{2}{\displaystyle \sum _{i=1}^2\cos }(2\pi xi))+c3+e$

c1=20 c2=0.2 c3=20 e=2.71282

f1是一个多峰值函数具有许多的局部极小点,其中只有一个是全局极小点,全局极小值为f(0,0)=0。利用传统的优化方法往往容易陷人局部最优,因此该函数成为进化算法能否实现全局最优搜索的测试函数。局域网的普及为并行性能的测试提供了平台,我们将种群分成若干子群,每个子群在局域网的一台PC机上运行,表1为实验结果。

由表1 可以看出多个子群并行执行可显著减少执行时间,例如:3个结点比一个结点的总执行时间减少43秒,但是当子群数目继续增加时,执行时间几乎不再减少,例如:8个结点比4个结点的总执行时间仅仅减少2秒,因为子群数目太多则结点间的通信代价会急剧增加。实验表明子群数目一般为3至5个效率较高。

4 结束语

分析讨论并行进化模型理论及性能,结合笔者曾经提出的基于免疫原理的量子进化算法,又设计了多宇宙并行免疫量子进化算法(MPMQEA),MPMQEA所需的种群规模小、收敛速度快、运算效率高且能有效地避免早熟收敛,基于学习的移民和模拟量子纠缠的交互策略导致通信开销很小。我们用典型的测试函数验证了它的并行性能。接下来要进一步充分挖掘和利用量子的并行机制,探索更高效合理的并行进化模型,研究其中参数(包括子群数目)设置的合理性。

摘要：分析讨论并行进化模型理论及性能,提出了基于学习的多宇宙并行免疫量子进化算法,算法中将种群分成若干个独立的子群体,称为宇宙。并给出了多宇宙的并行拓扑结构,提出了宇宙内采用免疫量子进化算法,宇宙之间采用基于学习的移民和模拟量子纠缠的交互策略进行信息交换。这样能提高种群多样性,有效克服早熟收敛现象。算法综合了量子计算的天然并行性和免疫算法的充分自适应性,它比传统的进化算法具有更好的种群多样性,更快的收敛速度。通过并行实验验证了该算法的优越性。

关键词：并行进化模型,量子进化算法,免疫算子,交叉变异

参考文献

[1] Narayanan A,Moore M.Genetic quantum algorithm and its application to combinatorial optimization problem.In Proceedings of the 1996 IEEE International Conference on Evolutionary Computation,IEEE Press,1996:61-66

[2]You XM,Shuai DX,Liu S.Research and Implementation of QuantumEvolution Algorithm Based on Immune Theory.In Proceedings of the6th World Congress on Intelligent Control and Automation,2006,Ac-cepted for publication.

[3] Han K H,Kim J H.Quantum-Inspired Evolutionary Algorithms with a New Termination Criterion,Hε Gate,and Two-Phase Scheme.IEEE Transactions on Evolutionary Computation,IEEE Press,2004(8):156-169.

[4]Fukuda T,Mori K,Tsukiyama M.Parallel search for multi-modal func-tion optimization with diversity and learning of immune algorithm.Arti-ficial Immune Systems and Their Applications.Berlin:Spring-Verlag,1999:210-220.

[5]Mori K,Tsukiyama M,Fukuda T.Adaptive scheduling system inspiredby immune systems.In Proceedings of the IEEE International Confer-ence on Systems,Man,and Cybernetics,San Diego,CA,12-14 Octo-ber,1998:3833-3837.

[6]Ada G L,Nossal G J V.The clonal selection theory,Scientific Ameri-can,1987,25:50-57.

[7]Enrique A,Jose MT.Improving flexibility and efficiency by adding par-allelism to genetic algorithms,Statistics and Computing,2002(12):91-114.

并行构造算法 篇8

现代空间遥感技术的发展已经使传感器的空间分辨率、光谱分辨率和时间分辨率大幅度提高, 使得遥感图像的数据量大增, 有的影像文件大小甚至达到GB级[1], 与此同时, 人们对遥感影像的处理和从影像获取信息的速度却远远落后于影像数据的增长速度, 其原因主要有以下两点: (1) 遥感影像数据量过大, 所需处理图像点的个数过多; (2) 另一个很重要的原因则是遥感影像的处理和信息提取算法越来越复杂, 一次算法的执行往往需要对同一幅图像做多次遍历和处理。对于第一个问题, 可以通过对遥感影像进行多尺度影像分割的方法来降低单幅影像的处理时间[2]针对后一个问题, 在硬件条件和遥感影像大小一定的情况下, 如何提高遥感产品算法的执行速度和并行度, 充分利用计算节点CPU的运算能力, 成为解决问题的关键;在复杂的遥感产品算法执行中利用并行计算技术, 需要从算法本身入手, 对这些算法进行细化和拆分, 以使得对拆分后得到的原子算法集合进行并行执行, 遗憾的是, 现有文献对遥感图像并行处理研究多集中在影像处理的基础算法方面, 比如遥感图像辐射校正、几何校正、图像融合等, 但是这些算法恰恰是遥感图像处理所用到的最基本的算法, 很难拆分出可进行并行的子算法集合;对于复杂的遥感产品算法并行计算研究的比较少, 本文从复杂的遥感产品算法的分解以及遥感产品算法树的构建和执行处着手, 着重分析了基于算法生成树的复杂遥感产品算法的并行计算方法, 以实验数据验证了此方法的可行性, 最后描述了此策略在实际项目中的应用。

2、算法生成树的构建

一个复杂的遥感产品算法的执行, 往往需要很多依赖的遥感产品算法的支持, 我们称这些遥感产品算法为中间算法, 个最终产品的生产往往需要几个低层次的图像处理得到的结果来作为依赖产品, 一般来说越是高级的图像处理功能, 需要越多的的底层图像处理功能的叠加来实现。一幅原始影像数据的处理, 一般要经过以下三个步骤: (1) 图像预处理, 比如几何纠正, 大气纠正, 辐射纠正等均是常用到的图像预处理算法, 这些算法也被称作基础算法。 (2) 图像中间处理, 这里分为两种:第一种我们称之为基础中间算法, 许多中间算法均需要这些算法的计算结果做为参数, 常用到中间基础算法有CCD表观辐亮度 (CCDTOAL) 、CCD表观反射率 (CCDTOAR) 、CCD太阳天顶角 (CCDSOLARZA) IRS像元纬度 (IRSPixelat) 等等;另一种中间算法处于基础中间算法和最终算法之间, 它为最终算法的执行提供所必须的参数。例如归一化植被指数 (NDVI) 、植被覆盖度指数 (VCI) 、比辐射率 (EP) 等 (3) 最终处理在得到最终产品算法执行所需的一系列参数后, 调用最终的遥感产品算法对图像进行最后的处理。一个复杂遥感产品算法, 其实可以看做是一棵由以上四种算法组合得到的算法生成树, 图1展示了一个复杂遥感产品算法执行的各个阶段以及其产出。

下面我们以地表温度产品 (LST) 为例, 来描述算法生成树的构建过程:

地表温度产品的计算公式如下所示:

其中λ、K1为常数, EP和IRSTOAL分别是比辐射率产品算法 (EP) 和基础中间产品算法表观辐亮度 (IRSTOAL) 的执行结果, 因此可知道, LST直接依赖于EP和IRSTOAL, 对于EP来说

其中NDVI、NDVImin、NDVImax均为归一化植被指数产品算法的执行结果 (NDVI) , 则EP依赖于NDVI, 同时EP的计算结果需要根据CCD表观反射率 (CCDTOAR) 的计算结果做校正, 因此EP依赖两个产品算法NDVI和CCDTOAR, CCD表观反射率的计算需要CCD表观辐亮度 (CCDTOAL) 和CCD太阳天顶角 (CCDSolarZA) 的计算结果, NDVI需要CCD表观辐亮度 (CCDTOAL) 的计算结果, 因此可得出LST的算法生成树如图2所示:

3、算法执行策略和并行度分析

在上节中, 以地表温度产品算法为例讲述了算法生成树的构建过程, 在本节中将重点讲述如何以并行方式执行算法生成树

算法生成树的执行遵循如下三个原则

(1) 启动算法调用时, 首先从从最左侧叶子节点开始调用, 同一级别的算法可并行执行然后逐层向上调用, 每一层都是从左到右执行, 启动一个线程调用执行

(2) 只有当一个算法所有依赖算法全部执行完毕, 才执行此算法每个算法调用完毕后生成的与算法同名的结果 (CSV或tif) , 均生成与其算法名对应的图像文件或CSV文件, 供上层算法调用。

(3) 在调用过程中, 如果同名的算法正在被执行或已执行完毕, 则跳过此算法的生产。例如, 图2第四层有两个CCD表观辐亮度产品算法 (CCD-TOAL) , 在执行时, 只需要执行最左边的即可, 这样的执行方式大大节约了计算资源, 缩短了产品算法的执行时间。

仍以地表温度产品为例, 根据上面所述的三个原则, 地表温度产品算法生成树的调用顺序如下图所示:

由于同一级的产品算法可并行执行, 并且同名产品算法的重复执行, 在这里简单的假设每个产品算法的的执行时间均为T, 那么对于算法生成树的执行总时间为TA=T+T+T+T=4T, 而常规的产品算法, 由于未用到并行技术, 执行所用的时间为每一个算法执行的时间总和TC=8×T=8T用时比S=TA/TC=2.63, 当然, 这里, 只是在理论上进行了一个估计, 在算法的实际执行中, 由于不同产品算法执行所用的时间不同, 包括并行执行对计算节点CPU造成的影像, 对比的结果会有一定的差别, 在下节中, 将通过仿真实验进行详细的比较%

4、仿真与分析

为能真实反映本文提出的算法生成树的产品算法执行方法在执行时间和效率方面对比原有产品算法的优势, 本文仿真实验采用进行如下仿真实验:

实验采用8台相同配置的PC机, 其硬件配置如表1所示

仿真实验采用的原始影像为2011年11月1号环境星拍摄的北京区域大小为5898×5987的遥感影像, 每个计算节点对此幅影像计算地表温度 (LST) ,

测试采用两种方式来进行, 第一种采用本文所述的算法生成树并行的方式调用执行此过程, 另一种调用常规的地表温度算法, 8台PC机分作两组, 每四台一组, 采用向计算节点分发任务的方式, 每个任务为一次LST的执行过程, 一次性的向每台PC机分发五个任务, 然后计算出两种执行过程所用的平均时间和CPU平均利用率。

从实验结果可以看到, 由于采用了并行计算技术, 采用基于算法生成树的遥感产品算法的平均CPU利用率约是常规算法的3倍, 由于单位时间内处理的图像点的个数比常规算法的要超出很多, 因此, 算法执行平均所用时间也比常规算法节约了三分之二, 由此可见, 本文提出的基于算法生成树的遥感产品算法调用方法在用时和CPU利用率方面的表现明显比常规算法更为优异。

5、项目应用实例

本文提出的算法生成树的思想已经在遥感环境产品监测与生产分系统中得到了应用, 该系统实现了对200多种遥感产品的并行生产, 其连续处理能力能够满足海量遥感数据处理的需求, 下面, 给出地表温度产品 (LST) 并行生产的监控示意图 (如图4) :

6、结束语

本文针对当前遥感影像处理中存在的算法执行效率不高, 执行时间过长的问题进行了深入的论述和研究, 提出了算法生成树的概念, 并论述了其并行执行策略, 实现了对复杂遥感产品算法的可并行化生产, 并使得算法执行的时间和效率得到一定的提高, 该算法已经在实际项目中得到了应用, 对遥感影像处理的并行化和集群化提供了强力的依据, 尽管如此, 本文提出的遥感产品算法生成树的并行执行策略仍有改进的空间, 在下一步的研究中, 将进一步进行算法优化, 同时还将对遥感数据的并行生产进行研究, 以期实现多级并行, 在计算性能上得到更大的提高。

参考文献

[1]郑友华, 王晓青, 窦爱霞.并行计算在遥感震害中的应用[J].地震, 2011-01-10, 31 (1)

[2]沈占锋, 骆剑承, 陈秋晓.高分辨率遥感影像并行处理数据分配策略研究[J].哈尔滨工业大学学报, 2006-11-30, 38 (11) :1968-1971.

[3]曾志, 刘仁义.一种基于分块的遥感影像并行处理机制[J].浙江大学学报, 2012-03-15, 39 (2) :135-141.

[4]樊兴, 张国平, 夏学知.一种实现动态负载均衡的多机情报并行处理方法[J].解放军理工大学学报, 2009-12-15, 10 (6) :523-527.

[5]桂兵祥, 何健.基于高性能云的分布式数据并行处理机制[J].武汉工业学院学报, 2010-03-15, 29 (1) :60-64.

[6]张树凡, 余涛, 李家国.基于三级并行的遥感业务化处理系统研究[J].计算机工程与设计.2012-10-18, 33 (10) :3828-3832.

基于并行处理的FFT快速算法 篇9

在遥感科学中,数字图像处理日益成为重要的核心技术,各种图像数据由传感器获取后必须先经过计算机做数字图像处理技术的加工才能将抽象的数据变得有实用价值。在遥感图像增强、复原、融合等算法中,傅立叶变换成为重要核心。根据“90-90规则”(Tom Cargill,贝尔实验室)[1],程序在运行中90%的时间都在执行10%的代码,即10%的代码量通常要消耗多达90%的系统资源以及运行时间,这些区域被称为热点(Hotspots)。而图像处理算法中傅立叶变换过程就恰恰处于程序中的热点位置,所以如何提高傅立叶变换过程的效率,缩短其运行时间成为了提高图像处理程序和软件效率的最重要环节。其次,计算机处理器从初期的面向简单算术和逻辑计算逐步向复杂功能和专业目标处理发展,趋于由硬逻辑代替软逻辑,大幅提高了专业计算的效率。最后,由于并行计算技术迅速发展,图像处理程序应针对多核环境做特殊处理,以充分利用计算机硬件的潜能而有效提高处理速度。本文着眼于以上几点,提出了一整套解决方案,并已在实践中取得了非常好的效果。

1适于SIMD计算的自然序FFT算法

对于二维傅立叶变换[2],其离散形式如式(1)所示:

f(x,y)=${\displaystyle \sum _{u=0}^{{\rm M}-1}}{\displaystyle \sum _{v=0}^{{\rm N}-1}}$$F(u,v)\text{e}{}^{\left[j2\text{π}\left(\frac{ux}{{\rm M}}+\frac{vy}{{\rm N}}\right)\right]}$ (1)

频谱公式如公式(2)所示

$\begin{array}{l}F(u,v)=\left|F(u,v)\right|\text{e}{}^{j\phi (u,v)}=R(u,v)+j{\rm I}(u,v)\\ \left|F(u,v)\right|=\left[R{}^2(u,v)+{\rm I}{}^2(u,v)\right]{}^{\frac{1}{2}}(2)\end{array}$

可以看出先对f(x,y)按列进行DFT得到F(x,v),再对F(x,v)按行进行DFT即可得f(x,y)的DFT结果。故可对图像先按列进行DFT, 将结果替换原图像,再按行进行DFT即可完成对整个图像的DFT。故一维DFT成为算法核心。

根据旋转因子W${}_{{\rm N}}^{nk}$的对称性、周期性、可约性和特殊点,可以推出按频率抽取的基2-FFT算法:

设序列x(n)长度为N=2M,首先将x(n)前后对半分开,得到两个子序列,其DFT可表示为:

X(k)=${\displaystyle \sum _{n=0}^{{\rm N}-1}}$x(n)W${}_{{\rm N}}^{kn}$=${\displaystyle \sum _{n=0}^{{\rm N}/2-1}}$x(n)W${}_{{\rm N}}^{kn}$+${\displaystyle \sum _{n={\rm N}/2}^{{\rm N}-1}}$x(n)W${}_{{\rm N}}^{kn}$=

${\displaystyle \sum _{n=0}^{{\rm N}/2-1}}$$\left[x(n)+(-1){}^{k}x(n+{\rm N}/2)\right]W{}_{{\rm N}}^{kn}$;k=0,1,…N-1 (3)

按k的奇偶将X(k)分为两部分,令k=2r,k=2r+1,r=0,1,2,…N/2-1可得

$\{\begin{array}{l}{\rm K}\text{为}\text{偶}\text{数}:X{}_1(k)=X(2r)=\\ {\displaystyle \sum _{n=0}^{{\rm N}/2-1}\left[x(n)+x(n+{\rm N}/2)\right]}W{}_{{\rm N}/2}^{rn}=\\ {\displaystyle \sum _{n=0}^{{\rm N}/2-1}x}{}_1(n)W{}_{{\rm N}/2}^{nr}\\ {\rm K}\text{为}\text{奇}\text{数}:X{}_2(k)=X(2r+1)=\\ {\displaystyle \sum _{n=0}^{{\rm N}/2-1}\left[x(n)-x(n+{\rm N}/2)\right]}W{}_{{\rm N}}^{n}W{}_{{\rm N}/2}^{rn}=\\ {\displaystyle \sum _{n=0}^{{\rm N}/2-1}x}{}_2(n)W{}_{{\rm N}/2}^{nr}\end{array}(4)$

其中,

$\{\begin{array}{l}x{}_1(n)=x(n)+x(n+{\rm N}/2)\\ x{}_2(n)=\left[x(n)-x(n+{\rm N}/2)\right]W{}_{{\rm N}}^n\end{array}(5)$

(5)式可以抽象为以下的蝶形运算:

按以上步骤奇偶组继续分为奇偶组,直到分解为求两个点的DFT为止。此算法将DFT的运算量降为$\frac{{\rm N}}{2}\lg {}_2{\rm N}$次复数乘法和Nlg2N次复数加法。当N=8时的FFT运算图为:

但是图2的算法是按照原数据自然顺序输入,而输出为乱序,在完成计算后必须对结果数据经过严重影响算法效率重排序处理,并且由于蝶形运算的输入数据是不连续存储,非常不适合于SIMD计算模式。图3为改进后的FFT算法图。

此算法的输入输出数据均为自然顺序[3],每一级运算的输出数据都作为下一级的输入数据,均为原址运算;算法在保持了FFT算法性能的同时,每阶的每个蝶形运算的数据输入间距保持一致,使得输入端的数据存储地址连续,适用于SIMD指令所需的存储模式。图4为此算法的流程图。

2基于SIMD的并行算法实现

2.1运用SSE3指令完成高效复数乘法

2.1.1 DFT和FFT的计算次数分析

N个点的DFT计算过程如下:

X(k)=DFT[x(n)]=${\displaystyle \sum _{n=0}^{{\rm N}-1}}$x(n)W${}_{{\rm N}}^{nk}$, 0≤k≤N-1 (6)

即:

X(0)=x(0)W${}_{{\rm N}}^{0\cdot 0}$+x(1)W${}_{{\rm N}}^{1\cdot 0}$+…+x(N-1)W${}_{{\rm N}}^{({\rm N}-1)\cdot 0}$,k=0

X(1)=x(0)W${}_{{\rm N}}^{0\cdot 1}$+x(1)W${}_{{\rm N}}^{1\cdot 1}$+…+x(N-1)W${}_{{\rm N}}^{({\rm N}-1)\cdot 1}$,k=1

X(2)=x(0)W${}_{{\rm N}}^{0\cdot 2}$+x(1)W${}_{{\rm N}}^{1\cdot 2}$+…+x(N-1)W${}_{{\rm N}}^{({\rm N}-1)\cdot 2}$,k=2

︙

X(N-1)=x(0)W${}_{{\rm N}}^{0\cdot {\rm N}-1}$+x(1)W${}_{{\rm N}}^{1\cdot {\rm N}-1}$+…+x(N-1)W${}_{{\rm N}}^{({\rm N}-1)\cdot {\rm N}-1}$,k=N-1 (7)

以上每一个点的DFT需要N次复数乘法,N-1次复数加法,故N个点的计算次数为N2次复数乘法,N(N-1)次复数加法。而N=2M点的DFT运算可分成M级,每一级有N/2个蝶形,每个蝶形有一次复数乘法和两次复数加法,所以N点FFT共需要$\frac{{\rm N}}{2}\lg {}_2{\rm N}$次复数乘法和Nlg2N次复数加法。而一次复数乘法又需要4次实数乘法和2次实数加法,一次复数加法需要2次实数加法来完成。可见,大量的复数计算成为算法中最耗时的部分。

2.1.2 运用SSE3指令完成高效复数乘法

Intel处理器的MMX/SSE/SSE2指令集[4,5,6]引入了单指令多数据-(Single Instruction Multiple Data,SIMD)技术。SIMD的核心就是一条指令能同时完成多条相同的操作。典型的SIMD执行模式如图,其中操作符op可以代表普通的+、-、*、/等算术运算,也可以表示各种逻辑运算等,Source1和Source2是源操作数,经过指令执行后结果存于Destination中,其中Source1、Source2、Destination为SIMD同时引入的紧缩单精度浮点数(即4个单精度浮点数组成的128位数据类型)。

单指令多数据(SIMD)指令可以使软件在获得更高数据处理能力的同时使用更少指令。SSE3是SIMD指令集的新扩展,可以提高专业领域的计算能力。以下为运用SSE3指令完成复数乘法的过程。

用到的指令MOVSLDUP、MOVAPS、MULPS、SHUFPS、MOVSHDUP、ADDSUBPS。

MOVSLDUP(Move Packed Single-FP Low and Duplicate)将紧缩单精度浮点型的源操作数第0、2位置的单精度浮点数复制到目标操作数的第1、3位置。

MOVAPS(Move Aligned Packed Single-Precision Floating-Point Values)传送对齐的紧缩单精度浮点数;MULPS(Multiply Packed Single-Precision Floating-Point Values)紧缩单精度浮点数乘法;SHUFPS(Shuffle Packed Single-Precision Floating-Point Values)重排紧缩单精度浮点数;MOVSHDUP(Move Packed Single-FP High and Duplicate) 将紧缩单精度浮点型的源操作数第1、3位置的单精度浮点数复制到目标操作数的第0、2位置;ADDSUBPS(Packed Single-FP Add/Subtract)紧缩单精度浮点数指定位置的加/减法。

设要完成复数乘法的复数为A0=a0+ib0,A1=a1+ib1,B0=c0+id0,B1=c1+id1,以下指令将同时完成A0×B0和A1×B1的复数乘法。

如果不使用SIMD指令,每一次复数乘法需要经过4次实数乘法和2次实数加减法,并需要若干次数据载入。而通过将算法分解为适于并行计算的步骤,两次复杂的复数乘法只需要通过7条(其中3条运算指令和4条数据操作指令)SIMD指令即可完成。可见运用SIMD对算法性能的提高是显而易见的。

2.2运用SSE指令进行数据类型转换

目前源图像数据多以BMP、TIFF等格式存储,各波段数据通常为8位的整型数值,图像数据在经过算法进行计算时往往需要用精度更高的浮点数进行存储,而在处理之后又必须将计算结果按照图像数据要求的整型数值存储,并且由于普通库函数的低效和数据转换任务巨大,故在此部分程序也损失了效率。运用SIMD指令可以高效解决这一问题,以下代码可以仅用4条指令完成4次从单精度浮点数向整型值的转换:

movaps xmm0,[Source]

cvttps2pi mm0,xmm0

shufps xmm0,xmm1,Eh

cvttps2pi mm1,xmm1

其中Source中为将要转换的4个单精度浮点数,程序将源数据载入SSE寄存器,首先将地址的两个浮点数直接通过CPU转换成整型数并存入MMX寄存器,然后再对高址的两个浮点数做同样的处理。

3基于多核的FFT算法

3.1使用OpenMP进行多核处理

在FFT计算过程中将循环对图像每行和每列的数据依次进行计算,而在不同行列之间的计算过程是彼此独立的。各循环中的任意一次迭代不依赖于其他迭代的结果,执行循环时不存在循环依赖,所以可以将整个计算过程并行处理。如果用单核多线程处理方式,可以产生两个以上的线程“同时”计算,但是这样得到的效率提升是非常有限的,因为这本质上是对算法的并行化模拟,实际上还是单个处理器串行化完成计算任务,而由于处理器还需要对多个线程进行调度和维护,反而影响了计算任务本身的效率。如果针对多核处理器对程序进行改进,则系统将把整个计算任务分配给多个物理核心共同分担,而又因为不存在循环依赖,核心之间也不需要大规模的通信,所以各核心可以独立的完成计算任务。

OpenMP[7]是用以编写可移植的多线程应用程序的API库,内部使用Windows线程池,可以很好的支持多核平台的并行程序设计。以下代码将使程序以多核多线程模式并行运行:

程序中开启了动态线程和嵌套线程设置,使计算任务按内核数量进行平均分配,而嵌套线程又使各个核心内再嵌套生成同样数量的线程。如果系统内核心数为2,则计算任务先被分配到两个核心,然后每个核心又将产生两个线程共同工作。整个计算任务的线程数不宜过多,否则系统需要为管理和调度线程花费过多资源;线程数最好为核心数的整数倍,否则将不利于各核心的负载均衡。

3.2滚动型缓冲区

“滚动型” 缓冲区为在程序在堆区创建的一块内存,当程序对此块内存进行读写时,指向当前地址的指针由首地址向末尾地址移动,并当指针指向最末地址且有新的写入请求则指针重新指向首地址,整个存储区地址抽象为一个环形,环形地址中的每一个元素指向一块连续的存储区,大小为图像每行(列)的数据量。在缓冲区内部根据一系列参数进行分块,设为程序提供的内存数为nMemCount,图像高度为nHeight,图像宽度为nWidth,分块高度为nBlockHeight,系统处理器核心数为nCPUcount,各核心线程数为nThreadCount,则缓冲区分块数据高度为

nBlockHeight=

nMemCount/(nWidth*nBlock*nCPUCount*nThreadCount) (8)

而由实验测得nBlockCount设置为nCPUCount×nThreadCount×2即可充分避免由于IO造成的计算线程对读写线程的等待,故可又上式得出分块高度nBlockHeight。

程序在运行时,分为数据读写线程和数据处理线程两类线程。在程序运行之初,将开启两类线程,即数据读取线程Thread_Data_Read、数据处理线程Thread_Data_Process。如图,数据读取线程从硬盘向缓冲区内读入数据,当一个缓冲区块完全装满数据时,程序设置数据就绪标志,此时数据处理线程可以得到此块数据的指针并为数据块加锁,然后作为源数据交由多个核心进行处理,处理结果数据将通过缓冲区写回硬盘。

4实验结果

本文算法的运行环境为Intel Pentium4 1.86 GHz处理器和Intel Pentium Core 1.8 GHz双核处理器,内存均为1G,操作系统均为Windows XP sp2,编译器为Intel C++Compiler 10.0,文中算法中用到的SIMD指令由编译器中的Intrinsics函数提供。实验将对不同尺寸图像在不同的系统设计和平台下的处理时间进行记时,根据20次实验结果得到平均时间。实验将验证本文算法在单核和双核下,以及针对双核的缓冲区设计带来的效率提升。

表中为本文中的算法配合本文缓冲区在两个平台下的平均运行时间,并与目前广泛应用且效率最高的FFT函数库FFTW在双核平台下的平均运行时间进行比较。可见,在未使用文中设计的缓冲区的条件下,本文的算法在双核下的速度比FFTW在相同环境下有了极大提升;而在应用本文缓冲区后,系统运行效率最高提高到了原来的4.5倍。值得注意的是由于线程管理和同步的系统开销,在尺寸较小图像的处理中会抵消部分效率提升,而在处理大尺寸图像时,系统效率提升更加明显。

5结论

本文通过分析图像处理系统中快速傅立叶变换潜在的效率提升点,有针对性的提出了解决方案。文中选择了适用于SIMD指令进行并行计算的自然顺序FFT算法,配合SIMD指令和OpenMP并行库,并设计了可以大幅降低文件读写时间的缓冲区,使得整个系统效率得到极大提升,特别在大尺寸图像的频域处理方面效果尤为突出。对于日益高速发展的计算机硬件,新的效率提升点将会带来更多有待深入研究的问题,本文将在日后的工作中继续完善。

摘要：FFT算法是频域图像处理中最重要的核心算法之一,是影响数字图像处理软件系统整体效率的关键。提出的一种适于SIMD计算模式的自然顺序二维FFT算法,利用Intel处理器提供的新指令对算法进行了改进。应用OpenMP对算法进行了多核环境下的优化,并设计了与之配套的滚动型缓冲区。实验结果表明,这种FFT算法在多核下的运行效率最高可达到目前广泛使用的FFT算法的4.5倍,这种算法对海量图像数据的处理优势尤为显著。

关键词：FFT,算法,并行,SIMD,SSE

参考文献

[1]Kaspersky K.Code optimization:effective memory usage,Publishing House of Electronics Industry,2004

[2]Rafael C.Gonzalez,Richard E.Woods,数字图像处理(第二版).阮秋琦,阮宇智,译.北京:电子工业出版社,2007

[3]Crandall R,Klivintong J.Super-computing style FFTlibrary for apple G4.http://images.apple.com/acg/pdf/g4fft.pdf,2000:2-10

[4]Intel,Intel64and IA-32Architectures Software Developer’s Manual,Volume1:Basic Architecture,2007.08

[5]Intel,Intel64and IA-32Architectures Software Developer’s Manual,Volume2:Instruction Set Reference,2007.08

[6]Intel,Intel64and IA-32Architectures Software Developer’s Manual,Volume3:System Programming Guide,2007.08

[7]Gatlin,K S Isensee.P Reap the Benefits of Multithreading without All the Work,http://msdn.microsoft.com/msdnmag/issues/05/10/OpenMP/default.aspx,2005