快速并行算法

快速并行算法（精选八篇）

快速并行算法 篇1

在遥感科学中,数字图像处理日益成为重要的核心技术,各种图像数据由传感器获取后必须先经过计算机做数字图像处理技术的加工才能将抽象的数据变得有实用价值。在遥感图像增强、复原、融合等算法中,傅立叶变换成为重要核心。根据“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

快速并行算法 篇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

谷物粒型作为谷物外观的主要形状，是评价谷物品质的重要指标之一[1,2]。此外，粒型还与谷物重量密切相关，在估计谷物产量中具有重要意义[3]。传统粒型(粒长与粒宽之比)测量方法为人工方法。按照中华人民共和国国家标准GB1350-1999，粒型人工测量方法是随机取10粒完整无损的精米，将精米按头尾对接的方式排列，用直尺测量总长度，取其平均值为粒长。将精米按肩靠肩的方向排列，取宽度的平均值为粒宽。计算粒长与粒宽的比值即为粒型。人工方法耗时，工作量大，且容易受测量人员的主观因素影响，人为误差较大，测量结果不准确。

机器视觉是一种快速、经济、一致和客观的测量技术，在农业中的应用非常广泛[4]。利用机器视觉技术对谷物品质进行检测，具有准确度高、重复性好等优点。目前，根据图像采集方式，用于检测谷物品质的机器视觉系统主要可分为基于平板扫描仪的系统[5,6,7]和基于数字摄像机的系统[7,8,9]。平板扫描仪虽然不受外界光照条件的影响，但采集图像前需要手动将谷粒平铺放置于平板上，且其扫描速度慢，系统不能满足实时在线检测的要求。而基于数字摄像机的系统中，可以借助传输系统将谷物运输到成像区域并对检测完的谷物进行收集，实现谷物在线测量。为实时识别谷物中的饱满粒和空瘪粒，测量实粒数、瘪粒数，我们小组研发了一套结合可见光成像技术与X射线成像技术的机器视觉系统，测量效率约每分钟2 000粒[10]。利用该系统进行粒型测量时，需要对图像中每颗谷粒计算粒长、粒宽。当谷粒数较多时，粒型计算量大，系统效率的提高将会受限制。此外，若系统中加入其它品质参数测量，图像处理的运算复杂度增大也会影响实时测量系统的效率。为提供系统高速测量多个参数的可能，粒型测量算法耗时的缩短非常必要。因此，提高算法执行效率是保证系统高效率的重要手段。图形处理器(GPU)具有很强的浮点运算能力和存储带宽，其强大的并行计算能力在图像处理算法诸如图像滤波[11]、直方图均衡化[12]、边缘检测[13]等中有广泛应用。本文采用线阵列采集技术和工业输送技术获取谷物图像，并提出了一种基于GPU并行处理的谷物粒型快速测量算法。

1 自动测量系统和材料

系统的硬件部分主要包括给料机、线阵列摄像机、传输带、光源、收集装置和计算机。待测谷物通过给料机落到传输带上，谷物随传输带运动的同时摄像机拍摄图像。图像经采集卡传输至计算机，由计算机对图像进行处理获得粒型信息并控制整个系统运作。测量结束后，谷物落入收集装置。系统组成结构细节介绍见文献[10]。系统检测总流程如图1所示。线阵列摄像机采集得到的图像经过校正、二值化、去噪、分割等图像预处理操作后，得到谷粒二值图。然后基于并行处理技术，在GPU中计算每颗谷粒的粒型。最后把计算结果拷回中央处理器(CPU)显示与存储。

2 基于并行处理技术的粒型测量算法

本文利用谷粒轮廓，求取单颗谷粒的粒长、粒宽，计算粒长与粒宽的比值从而得到谷物粒型。粒长、粒宽示意图如图2所示。用f(x,y)表示谷粒轮廓，点

Pi(xi,yi)为轮廓上的任意点，谷粒轮廓点个数为num。设点P1(x1,y1)、P2(x2,y2)为轮廓上距离最远的两点，则以过点P1和P2的直线l为粒长所在直线，P1,P2两点间距离为粒长值。即粒长L的计算过程表达式为

式中：dij为轮廓点Pi(xi,yi)和Pj(xj,yj)的距离，0≤i,j

按照人工测量粒型方法，基于图像测量的粒宽可定义为谷粒在垂直粒长方向上的投影宽度，即平行于l且与f(x,y)相切的两切线之间的距离。从图2中可以看到，直线l将谷粒轮廓划分为直线上方和直线下方两部分，分别计算这两部分轮廓点到粒长直线的距离最大值，即可找到切点P3(x3,y3)、P4(x4,y4)。记两切点到直线l的距离分别为dl1,dl2，则粒宽w为dl1与dl2之和。若将距离值记为有符号值，粒宽w的计算过程表达式为

式中：dli为轮廓点Pi(xi,yi)到直线l的距离，0≤i

由于每颗谷粒粒长、粒宽的计算互不相关，因此可以利用GPU技术，并行计算每颗谷粒粒型。基于并行处理技术的谷物粒型测量算法流程如图3所示。

步骤1：图像校正。系统传输带的运动速度与相机采集速度不匹配，因此，为保证粒长、粒宽测量的准确性，采用模板校正的方法对原始图像进行校正。

步骤2：二值化。二值图像包含了完整的谷粒形状信息，为减少后续处理的复杂度，对图像进行二值化处理。系统中传输带为黑色，即图像中背景颜色为黑色。因此，可选用合适的固定阈值对图像进行处理，得到二值图像。

步骤3：去噪。由于图像采集时光照不均匀等环境的干扰导致图像中存在一些噪声，图像中面积小于阈值的连通区域被认为噪声点并去除。

步骤4：分水岭分割。考虑到谷粒粘连现象，利用分水岭算法对图像分割。将图像中的粘连谷粒分割为单颗谷粒，得到谷粒的二值图像。为避免分水岭过分割，分水岭分割前对图像进行距离变换与灰度重建操作。

步骤5：轮廓标记。记步骤4得到的二值图像为Ib，对Ib腐蚀得到图像Ie。将图像Ib与图像Ie相减得到谷粒轮廓图像Ic。从上至下，从左至右扫描图像Ic，为图像中每颗谷粒的轮廓标记。第一个扫描到轮廓上的像素点标记值为1，之后轮廓的标记值依次加1。标记过程中，同时保存每颗谷粒轮廓点的坐标值并计数轮廓点。对标记值为i的谷粒，轮廓点的横纵坐标值分别存于数组x[i-1][.]，y[i-1][.]中，轮廓点个数保存于数组num[i]。标记完成后，可得到所有谷粒的轮廓坐标及谷粒个数N。

步骤6：粒型计算。将数组x[i-1][.]，y[i-1][.]，num[i]数据拷入GPU中，并行计算每颗谷粒的粒型。最后把计算结果拷回中央处理器(CPU)显示与存储。具体粒型并行化测量算法描述如下。

2.1 算法并行化

算法并行执行性能的优化基于算法本身的可并行性，即数据并行性。因此，要实现算法的并行执行，首先需要对算法结构化，尽可能寻找算法计算过程中的数据无关性。经分析，粒型计算过程中主要包含4个并行计算部分。

a)由于每颗谷粒粒型计算时只需利用其轮廓点的坐标信息，因此每颗谷粒的粒型计算可以并发执行。

b)粒长计算式(2)可以写成：

式中di为轮廓点i到其余轮廓点的最大距离。即对每个轮廓点可通过共享所有轮廓点的坐标，并行计算di。

c)轮廓点到粒长直线的距离由该轮廓点坐标和粒长直线确定，不同轮廓点的dli可以进行并行计算。

d)求取距离最大值时，可使用削减操作[14]，最大化算法的并行性。

如图4所示，获得所有谷粒轮廓点坐标后，可以并行计算每颗谷粒的粒型参数。在每颗谷粒的粒型参数计算过程中，不同轮廓点间距离、不同轮廓点到直线的距离都可以并行计算。

2.2 GPU内核函数配置

统一计算设备架构(CUDA)编程模型中，GPU上运行的程序部分以内核函数定义，每个核函数由线程网格中的不同线程并行执行。每个线程可根据线程号对不同的数据执行相同的内核函数，即单指令多数据。线程数量由所处理的数据大小决定，而每个线程块内的线程数量有限，同时线程块内可共享的存储空间也有限。因此，为内核函数合理安排配置线程块，最大化可用计算资源利用率，是充分利用GPU并行性能的前提之一。本系统中利用的显卡为GeForce 9800 GT，每个线程块中最大线程数为512，线程网格中最大线程块数为512×512×64。根据2.1节中分析，假设图像中谷粒数为N，则设置N个线程块，每个线程块负责计算一颗谷粒的粒型。而每颗谷粒粒型计算中的并行部分，则可以利用线程块中的每个线程来实现。具体处理方式为线程i负责处理轮廓点i，使各线程并行计算di，然后同步线程块中的线程计算L和直线l方程，再用每个线程并行计算dli，最后同步各线程计算w。由于每个线程块中的线程数必须相同，考虑到轮廓点个数不多于256，配置每块线程数为256，程序运行中通过实际轮廓点个数控制各线程是否执行。

2.3 数据存储器类型

CUDA存储模型中，每个线程可直接访问寄存器和本地存储器，每个线程块内的所有线程可通过共享存储器共享数据，线程网格内所有线程均可访问全局存储器、常量存储器和纹理存储器。不同存储器的访问模式不同，空间大小不同，速度也不同。组织存储器访问，优化存储器利用率，使存储器带宽最大化，是程序性能的优化的重要步骤。按照内核函数配置，线程块中每个线程计算时要使用该线程块对应谷粒的所有轮廓点坐标，即f(x,y)。为减少访问延迟，同时考虑数据大小，可使用共享存储器存储f(x,y)。另外，计算L和w过程中，对求取距离最大值进行削减操作时，各线程之间需要数据共享，因此计算中间结果di,dli也采用共享存储器存储。

3 实验结果与分析

供试材料为中花11水稻。利用系统采集的30幅谷粒图像(图像分辨率为2 715×3 350)对基于GPU并行处理优化后的算法进行性能测试。算法优化前后，即在CPU和GPU上运行耗时对比如表1所示。其中算法执行时间包括轮廓提取、轮廓标记和粒型计算三个部分。系统使用CPU为Intel(R)Xeon(R)，主频为2GHz，内存为3 GB，系统使用GPU为GeForce 9800 GT。

从表1中可以看到，使用GPU并行处理技术优化算法后，算法执行速度明显提高。结果说明，粒型测量算法具有很好的并行性，可以充分利用GPU的并行处理性能，同时计算多颗谷粒的粒型，从而有效地提高算法速度。如表1所示，30幅图像粒型计算耗时不等，算法优化后加速比也不同。这是因为不同图像中谷粒数目不同，谷粒数越多，粒型计算耗时就越长。测试50幅图像，比较不同谷粒数图像粒型计算所需要的时间，结果如图5所示。

如图5中曲线所示，加速比随谷粒数的变化而变化。图像中谷粒数目越多，GPU并行加速效果越明显。当图像中谷粒数为2 000颗时，加速比接近450倍。出现这种现象的原因是随着谷粒数的增多，处理数据量增大，GPU执行中线程切换、系统调度开销等占用的执行时间较少。

4 结论

快速并行算法 篇4

数学形态学用具有一定形态的结构元素去量度和提取图像中的对应形状,从而实现对图像的分析和识别。数学形态学处理在边缘检测、特征提取、图像分割、细节去除、孔洞填充等图像处理以及计算机视觉领域有着非常广泛的应用[1]。

形态学处理一般算法是将一个结构元素在二值图像上逐点移动,对每个像素点进行若干次逻辑判断从而得到处理结果。为提高形态学处理的运算效率,杨琨等提出利用结构元素在运算过程中存在的大量的重复运算区域,通过在后一次运算中使用前一次运算的结果来缩短运算时间的算法[2]。该算法具有理论基础简单,实现方便的特点,但是对于比较小的结构元素,性能提高不明显。陆宗琪等提出采用线段编码的方式,将当前线段与其相邻的上下线段之间进行逻辑运算,从而实现膨胀腐蚀运算[3]。该算法由于需要对二值图像进行额外的线段编码工作,导致对单个膨胀腐蚀操作效果的改善大打折扣,没有较为广泛的适用性。Cheng等通过检测二值图像的边缘,对边缘像素点进行操作来实现膨胀腐蚀的快速运算[4],对于边界比较复杂的情况,该算法的优化效果不好。Matthew J. Thurley等利用图形处理器( GPU) 的并行计算优势,采用CUDA这一NVIDIA推出的并行计算架构进行性能优化[5]。该算法对于分辨率较高的图像会有较高的性能提升,但是对硬件的要求较高,适用性不强。

本文将4 连通或8 连通结构元素分解为不同方向上的一维结构元素,利用分步的移位操作实现形态学腐蚀膨胀。同时利用二值图像的特点,即其像素值为0或者1,采用分段的方式,将相邻的若干个像素看成一个整体,通过并行操作实现算法性能提升。算法的速度可以提高4 ~ 6 倍,具有易操作适用性广泛的特点。

2 膨胀与腐蚀

定义1,作为Z2中的集合A和B,B对A的膨胀定义为

该公式可以等价表示为

式中: z表示结构元素的位移;表示集合B的反射集合。由定义得出的膨胀算法为将给定的结构元素在二值图像上依次平移,若该结构元素覆盖的原二值图像上有一个或多个点像素值为1,则将结构元素中心点所在的二值图像像素值赋为1,否则将该点像素值赋为0,当结构元素走完整幅图像时,便可以得到膨胀结果。

定义2,作为Z2中的集合A和B,B对A的腐蚀定义为

该公式可以等价表示为

式中: Ac是A的补集; Ф 是空集。

同理,由定义得出的腐蚀算法为当结构元素覆盖的二值图像像素值全部为1 时,将结构元素中心点所在的二值图像像素值赋为1,否则赋为0。由定义得出的形态学处理算法效率较为低下,原因在于需要遍历整个图像的每个像素值,对于每个像素值,仍需要进行一系列的逻辑判断才能得到运算结果。当结构元素较为庞大或者二值图像分辨率较高时,处理速度会变得尤其慢。此外,由于结构元素在二值图像上依次滑动处理每个像素,因而会有大量重复的逻辑判断,当图像前景区域比较大时,这些重复判断会造成更加多的资源浪费。

结论1,由定义可知膨胀和腐蚀关于集合求补运算和反射运算是对偶的,即

因此,可以利用相同的结构元素,使用B膨胀图像的背景( 即膨胀Ac) ,并将结果求补即可得到B对该图像的腐蚀结果。

3 基于分解的膨胀腐蚀快速算法

3. 1 基于分解的膨胀快速算法

3. 1. 1 算法原理

对于一幅需要进行形态学操作的二值图像,不需要对每个像素进行单独处理,而是可以利用一个无符号整数( unsigned int) 来表示连续的若干个像素值,这个无符号整数的每一位均代表原图中的一个像素点的像素值。因此,一幅M × N的二值图像可以按行表示为M个整数,其中每个整数都是一个N位的无符号整数。同理,也可以按列表示为N个整数,其中每个整数都是一个M位无符号整数。

本文将讨论4 连通和8 连通的结构元素,如图1所示。

对于4 连通的结构元素,可以将其分解为( 1 1 1)和( 1 1 1) ’两个方向上的一维结构元素,其中( 1 1 1) ’表示矩阵( 1 1 1) 的转置。( 1 1 1) 对原始图像的膨胀结果可以表示为将图像中每个像素值为1 的点的左、右像素点均赋值为1,这一步也可以通过将按行构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。( 1 1 1) ’对原始图像的膨胀结果可以表示为将图像中每个像素值为1 的点的下、上像素点均赋值为1,这一步也可以通过将按列构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。最后,将上述两个步骤得到的两个整数按位取或即可得到最终膨胀结果。4 连通膨胀算法流程见图2 所示。

对于8 连通的结构元素,同样可以将其分解为( 1 11) 和( 1 1 1) ’两个方向上的一维结构元素。( 1 1 1) 对原始图像的膨胀结构可以表示为将图像中每个像素值为1 的点的左、右像素点均赋值为1,这一步也可以通过将按行构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。( 1 11) ’对原始图像的膨胀结构可以表示为将图像中每个像素值为1 的点的下、上像素点均赋值为1,与4 连通结构元素不同的是,这一步需要将( 1 1 1) 对原始图像膨胀的结果按列构造出的若干个整数向左按位平移一位,向右按位平移一位,将这3 个整数按位取或得到。8 连通膨胀算法流程见图3 所示。

3. 1. 2 算法流程

根据上述原理,可以通过对按行或者按列构造的若干个整数进行位操作来得到最终膨胀结果。将若干个相邻像素点视为一个整体使用并行的操作方式可以提升算法的效率。

在本文中,对于一幅大小为M × N的二值图像,将每一行连续的32 个像素值作为一个整数,当N/32 不等于0 时,即每行像素值个数不是32 的整数倍时,在每行末尾补充32 - N% 32 个值为0 的像素,这样便可以将原始的M × N的二值图像分段成一幅M × ? N%32」的新图,该图中每个“像素值”均为一个32 位的无符号整数。构造过程如图4 所示,图5 显示了构造之前的图像和对应分段图。

同理,若将原始图像矩阵转置后进行如上操作,可以得到图像按列构造出的分段图。构造完二值图像对应的分段图之后,形态学膨胀腐蚀便可以在分段图上进行操作。4 连通和8 连通的膨胀快速算法见图6 和图7。在进行移位操作时,需要考虑相邻两个整数的边界位,即当x的最后一位为1,而x右边的整数y第一位为0 时,若需要进行右移移位,则需要将y的第一位置为1; 同理,当x的第一位为1,而x左边的整数z最后一位为0 时,若需要进行左移移位,则需要将z的最后一位置为1。

3. 2 基于分解的腐蚀快速算法

根据结论1,可以知道形态学腐蚀和膨胀具有对偶性的特点,因此为得到4 连通或者8 连通结构元素对一幅二值图像的腐蚀结果,将二值图像取反,然后进行上述膨胀操作,最后将得到的结果再次取反即可。由于二值图像取反操作也可以在分段图上进行,因此腐蚀快速算法的流程仍是建立在分段图之上的。

3. 3 性能比较

在Intel Core i5 - 3470 CPU @ 3. 2 GHz,4 Gbyte RAM,Windows8 32 位操作系统的硬件环境下进行实验。对不同分辨率以及不同纹理复杂度的二值图像进行了实验,采用的结构元素为8 连通结构元素,进行膨胀实验的原始图像以及最后结果见图8,性能比较见表1。由于运行时间与计算机速度、负载有关,因此本文中的数据取的是平均值。由于本文的快速算法只是对32 bit整数操作,并不关心整数的具体内容,因此二值图像的纹理复杂程度并不会对本算法的性能有较大影响。

4 结论

本文提出了一种基于结构元素分解的二值形态学并行快速算法。将结构元素分解为不同方向的一维结构元素,通过分步的移位操作实现形态学腐蚀膨胀。最后利用二值图像的特性,构造出32 bit整数形成的分段图,在该分段图上进行并行的位操作来实现算法的性能提升。该算法相比于传统的形态学处理操作,在性能上有了大幅提升。二值图像分辨率越大,本算法的性能提升越明显。同时,由于本算法只是对整数操作,并不关心整数的具体内容,因此,二值图像本身的纹理复杂程度并不会影响本算法的性能,这也是对一些需要首先进行边界检测的形态学处理方法的提升。

参考文献

[1]RAFAEL C.数字图像处理[M].3版.北京:电子工业出版社,2013.

[2]杨琨,曾立波,王殿成.数学形态学腐蚀膨胀运算的快速算法[J].计算机工程与应用,2005(34):54-56.

[3]陆宗琪,朱煜.数学形态学腐蚀膨胀运算的快速算法[C]//第十三届全国图象图形学学术会议.北京:清华大学出版社,2006:15-20.

[4]CHENG Xinyu.Fast binary dilation/erosion algorithm using reference points[C]//Proc.International Conference on Networking and Digital Society.[S.l.]:IEEE Press,2009:87-90.

快速并行算法 篇5

关键词：直扩系统,pn码捕获,FFT频谱分析

扩频通信建立在Shannon的信息论基础上,并率先应用于军事通信中的,而从其技术的实现手段上看,它经历了模拟扩频技术、数模混合扩频技术以及完全数字化扩频技术等发展阶段。目前,随着CDMA扩频技术在民用移动通信里的深入应用和不断渗透,以及在卫星的深空通信、武器制导、GPS定位系统、无人机测控等国防军事通信的需求下,扩频通信技术显得愈来愈重要,而扩频通信中的数字基带技术又属于其关键技术。由于pn码的捕获过程为一个统计变量的随机过程,随机变量遍历各态,俗称pn码的捕获或截获、搜索。

目前传统的pn码捕获方法有滑动相关一步固定积分时间法、匹配滤波器捕获,序贯检测法,采用频域/时域二维序贯搜索捕获环与窄间隔超前、滞后型数字延迟跟踪环等方法;而为保证载波快速捕获的同时具有好的动态及噪声性能,采用鉴频、鉴相算法相结合的自动频率、相位跟踪捕获环等方法;在通常pn码不太长,对捕获时间要求不高的情况下,一般采用串行捕获的方法,通过扣除码钟来移动本地pn码的相位[1]。

1 基于并行FFT的pn码捕获原理

在直扩通信系统中,当基带数据调制pn码时,就可以获得数据信号d(t)和pn信号a(t)的积[2]。假设数据速率为Rb/bit·s-1,Tb=1/Rb为bit持续期,Tc是pn码片间隔周期。于是,它们可以表示为

$d(t)={\displaystyle \sum _{k=-\infty }^{\infty }d}{}_k{\rm P}{}_{{\rm T}{}_b}(t-k{\rm T}{}_b)$ (1)

$a(t)={\displaystyle \sum _{k=-\infty }^{\infty }a}{}_k{\rm P}{}_{{\rm T}{}_b}(t-k{\rm T}{}_b)$ (2)

式中,dk为数据序列的第k位;ak为pn序列的第k个码片;PT(t)是脉宽为T的矩形脉冲的单位幅度,即

其处理增益G=Tb/Tc,假设pn码序列的周期长度为L,即对于所有的k,有ak+L=ak存在。因此,一个数据信息bit脉宽包括了pn码一个周期长度的时间宽度。

在捕获系统中,通常采用相关器使本地pn码信号在其周期间隔T0内跟接收信号进行相关运算。如果没有调制数据并且忽略噪声,相关器的输出为

Co=∫${}_0^{{\rm T}{}_0}$a(t-iTc)a(-jTc)dt (4)

式中,iTc为接收端输入至相关器的pn码相位,jTc为本地输入至相关器的pn码相位。当两个pn码信号完全同步时(即i=j),相关器的输出为T0。

基于最大似然估计理论进行捕获系统设计,传输时延τ作为一个信号参数来估计,接收信号为

r(t)=ts(t,τ)+n(t) (5)

式中,rs(r,τ)为有用信号;n(t)意味着具有双边带功率谱密度等于N0/2的加性高斯白噪声。于是,有用信号就可表示为[1,2]

$r{}_s(t,\tau )={\displaystyle \sum _{k=-\infty }^{\infty }\sqrt{2S}}d{}_k{\rm P}{}_{{\rm T}{}_B}(t-k{\rm T}{}_b-\tau )a(t-k{\rm T}{}_b-\tau )\cos \omega {}_{0}t$ (6)

其中,S为信号功率;ω0为载波功率。

对于τ的所有可能值,由于τ是连续参数,其值存在无穷大,一种可能实现的估计是从其值的离散集合中获得,然后对其进行精细的调整,这就是通常所说的pn码粗捕和精跟的两个过程。其算法实现步骤如图1所示。

采用上述理论可设计针对多路扩频信号的pn码捕获程序,其原理框图如图2所示。捕获模块对多路信号的锁定状况进行检测,检测到信号失锁后,启动对相应通道的捕获。由于信号调制有数据信息和多普勒频率,存在着相位翻转,直接相关可能会引起相关损失甚至得不到相关增益。另外,伪码存在较大的多普勒频偏,码元会产生滑动,相关处理时间较长会得不到需要的相关增益。所以考虑将捕获分为粗搜和精搜两个过程。

为降低捕获时间,采用8路并行相关,相关积分结果先缓存,再以系统时钟高速读取进行处理的方法。由于粗搜只能确定频率范围,对伪码搜索结果滞后较大,需要再进行精搜,根据多普勒分析结果,将载波和伪码的多普勒都进行相应的设置,再进行1次搜索,由于粗搜确定了伪码的相位,按照可能产生的码片滑动,进行部分码相位搜索,确定伪码相位。

2 pn码快速捕获算法实现

2.1 pn码捕获模块组成

伪码捕获程序有相干积分模块、FFT运算处理模块和搜索控制状态机等模块组成。相干积分模块完成输入信号的相关和相干积分处理,获得需要的相关增益。FFT运算处理模块完成输入信号的频谱分析、载波多普勒频率检测和伪码同步位置的搜索。搜索控制状态机完成搜索过程的启动结束、伪码序列的移位控制和粗搜/精搜的切换。实现框图如图3所示。

2.2 pn码捕获控制流程

粗搜时载波跟踪NCO频率置为中心频率,伪码时钟频率无偏置,搜索全部码片,根据搜索结果对载波NCO和伪码码钟进行多普勒预置,再进行搜索,再搜索粗搜码片结果的±64个码片。

具体流程如下:

(1)捕获开始,设置载波NCO频率字和码钟频率字。

(2)产生开始信号,启动一次相干积分运算,同时存储相干积分运算结果。

(3)此次相干积分运算结束,产生停码控制信号,移动8个码片。

(4)同时以系统时钟高速读取缓存内的数据,启动FFT运算计算功率谱,在功率谱上作积分处理和峰值搜索,与前一次搜索结果比较,记下最大值的结果以及位置。

(5)依次重复(2)、(3)、(4)三个过程。

(6)直至码片搜索完成,根据搜索结果预置载波NCO频率字和码钟频率字,并调整码跟踪环的码发生器的码片相位,在粗搜结果的±64个码片处启动精搜。

(7)精搜流程与粗搜类似,搜索码片相位只有128个,比粗搜的1 023个少。

(8)结束精搜再次预置搜索结果,在码相位同步时刻启动载波环和伪码环闭环,完成此次搜索过程。

2.3 需考虑的参数设计

(1)FFT分辨率。

FFT分辨率即谱分析的分辨率,可由FFT谱分析的输入数据率与FFT点数的比值得到。

(2)相干积分长度。

相干积分运算输入数据率与相干积分结果输出数据率之比值即为相干积分长度,由上述pn码捕获原理可知,相干积分结果输出数据率即为谱分析的输入数据率。多路输入信号之间的多址干扰和搜索检测门限的设置都是影响相关积分增益选取的因素。

(3)FFT运算点数。

按系统时钟读取乒乓缓存内的数据进行N点FFT运算,求取功率谱。由于数据的影响,功率谱上出现数据包,采用滑窗对功率谱进行积分处理,累积出单峰搜索峰值位置,获取载波的多普勒值。滑动窗宽度为信息速率同输入数据率的比值再乘以FFT点数。

3 结束语

采用Matlab对pn码捕获算法进行了仿真,FFT点数为2 048,图4为仿真结果。左图4(a)为加有多普勒信号频谱图,图4(b)为对信号做FFT运算得出的功率谱。

此算法已在工程中得到应用,对于提高多路扩频信号同时接收的系统捕获时间有良好的效果。

参考文献

[1]张欣.扩频通信数字基带信号处理算法及其VLSI实现[M].北京:科学出版社,2004.

分布并行算法分析与设计 篇6

在过去计算机并行处理技术发展缓慢, 主要原因是计算机电子设备处理器价格比较贵, 网络通信处于前期发展阶段不太成熟, 使用并行技术开发的软件功能和应用上不完善。在20 世纪后期, 随着网络通信技术的迅速发展, 高位数处理器的开发和应用, 给并行处理技术提供了很好的发展空间。在计算机产业中, 人们意识到计算机的处理计算的能力在高科技的技术发展中被人们越来越重视, 并行处理技术是高性能计算机处理技术未来主要技术, 并行处理技术可以大大提高计算机的整体性能。 现代科学技术和全球经济的发展都离不开计算机技术, 计算机技术已经改变了人们的生活方式, 存在各个领域, 计算机技术的发展比其他科学技术的发展要快, 对人类的影响比较深远。 工程领域对计算机计算的需求是无限的, 然而计算机的单机计算是有限的, 这两个关系决定了分布式并行计算方法必然称为计算机计算方法的主导。

2 研究现状

国内在国防和国家科技的建设上, 并行处理技术起着重要作用, 我国对高性能计算机的发展非常重视, 尤其在石油、气象、 航空等大范围领域的研究逐年增加, 我国在并行处理技术领域比其他领域发展显著主要是因为并行处理技术领域的高性能计算机。 国内的科技工作者正努力研究多种并行处理的计算方法, 软件发展的重心主要体现在算法能力上面, 我国研发的数据库并行处理系统处于世界同领域的领先地位, 并行体系结构、 并行系统软件、 并行算法是并行处理技术的3个方面, 我国在高性能计算机的研制方面投入多, 在系统开发方面投入较少, 低成本延迟高带宽、 并行应用软件和并行算法是我国研发的重点。

国外美国、 日本在并行计算方面发展出力领先水平, 美国在商业领域已经应用高性能计算, 并行检索技术, 在并行计算方面的研究资料国外设计的也比较全。 国内外差距大, 我国发展高性能计算机技术不能再等, 算法是研究的重要内容。

3 并行计算机分类和计算环境

3.1 并行计算机的分类

并行算法能够运行的基础主要是并行计算环境和并行计算机, 并行算法的设计和实现取决并行计算机环境和并行计算机, 并行计算机从最初的向量机, 如今并行计算机主要是机群系统, 并行计算机分为SIMD型并行计算机、 共享存储MIMD并行机、 分布式存储MIMD并行机、 分布共享存储MIDI。

SIMD型并行计算机是单指令流多数据流并行机, 在指令流执行的时候, 处理机对多组数据执行相同指令流, 也就是说SIMD并行机无论怎样运行它的指令只有一条, 同步性、 确定性是SIMD型并行计算机的特征, SIMD型并行机已经不能满足并行技术的发展, 是早期产品, 如今已经不被使用。

共享存储MIMD并行机是多指令流多数据, 所有处理机执行统一程序, MIMD并行机是现在并行算法中普遍使用的编码方式。

分布式存储MIMD并行多处理机解决了共享存储MIMD并行处理机的瓶颈问题, 在整个系统中, 每个节点都有自己的存储器, 在访问的时候只能自己访问自己的存储器, 不能互相访问, 各个节点通过网络作为传输介质连接到一起, 分布式存储扩展性强, 但是编程复杂, 在节点之间的信息传递不是通明的, 分不知存储MIDI并行处理机分两类, 大规模处理机和群集系统。

分布共享存储MIDI并行机在系统中每个处理机有自己的存储器, 共享地址空间由各个局部存储器连接组成。

3.2 并行计算机的计算环境

并行计算机体系结构, 并行算法的效率直接受并行计算机体系结构的影响, 在这个系统中处理机的连接方式构成并行计算机体系结构。 并行处理机互连方式主要是网络直径和等份宽度两个重要因素。 网络系统中两个距离较远的处理机之间的具体构成网络直径, 两个距离远的处理机在消息传递的时候出现时间的延迟用网络直径这个参数来衡量。 等份宽度是网络系统中两个相等距离所去掉的网络边的条数。 判断并行体系结构性能重要原则是小的网络直径和大的等份宽度。集群系统中处理机的连接方式用总线结构表示, 在总线结构中, 各处理机连接在一个总线上面, 靠一个总线进行传输, 在消息进行传输时要判断先后顺序, 总线结构图如图1 所示。

并行计算机的软件环境包括编码语言、 操作系统、 计算环境3 部分, 用于消息传递的并行环境常用的是PVM和MPI。PVM并行计算环境叫做并行虚拟机系统, 系统规模小通用性强, 在TCP/IP协议环境下也适用, PVM特点支持多用户同时执行多个应用程序, 提供通信原语, 多个进程组成一个进程组, 同一个进程可以属于多个进程组, 在不同的网络系统中可以使用, 兼容性强, 容错功能强。 MPI并行计算环境是消息传递界面的一种方式, MPI并行计算环境特点实现的开发工具方式多, 消息的发送和接收可以重叠, 对消息缓存区可以有效管理, 可靠地运行在集群系统中, 保证其他软件可以正常运行, 标准平台上也可以使用。

4 并行算法定义及分类

算法是解决某个特定类型问题的解题方法的一系列规则, 并行算法是在解决问题方面相互联系起协调作用的可以并行执行的过程的集合。 并行算法是在并行处理机上把多个问题和任务映射到多处理机进行求解的处理数据的一种方法。 传统的算法树是一维问题的串行算法, 靠算增加算法树的深度来进行大型计算机计算, 并行算法减少时间上的复杂性, 计算量增加, 算法步骤减少, 把时间上的复杂性转化为空间上的复杂性。

并行算法分类, 并行算法根据运算对象不同分为数值并行算法和非数值并行算法两类, 数值并行算法有线性方程组和多项式求解等, 非数值并行算法指排序、 选择、 分类等设计。 并行进程执行顺序不同分为同步并行算法、 异步并行算法、 独立并行算法, 同步并行算法指进程执行要等待其他进程的计算方法, 异步并行算法指进程在执行的时候彼此不用相互等待, 独立并行算法指进程在执行的时候是独立执行的。

5 并行算法设计

用并行处理机系统进行并行计算求解问题一般遵守需要解决的问题本身提出满足需要的特定的并行算法, 或者在相似的问题上把已有的并行算法改变下, 来解决问题原则。 常用的并行算法技术有流水线技术、 分治策略和加速级连策略等。

流水线技术是重要的并行计算技术, 在VLSI并行算法中, 基本设计是把一个任务设置为A, 然后分成几个小的子任务A1、 A2、 …AN, 在执行的时候按顺序执行, 先执行A1再执行后面子任务, 计算速度是一样的。

分治策略就是把问题分解多个特征相同的子问题, 计算机单个结点平均分摊计算机的负载提高工作效率, 子问题的类型和原问题的类型一样, 采用分而治之的原则。

加速级连策略是采用最优算法来解决问题, 开始使用最优算法, 当任务规模缩小到一个值的时候, 使用最快非最优的方式接续完成任务解决问题, 使用最优串行算法并发解决子问题。

并行计算模型把并行机的基本抽象特征表现出来, 从计算模型中可以看出来并行计算模型、 并行算法设计、 并行机三者关系, 并行算法映射到并行机上, 基于并行机进行算法的设计。 计算机模型为并行算法提供了框架和物理基础, 使用多种并行机。 并行计算模型如图2 所示。

并行算法评价标准是加速比和效率, 并行算法在并行机上求解实际问题,

并行算法的加速比

TA串行算法在单处理机上最优运行时间

TB并行算法使用B台处理机的计算时间

并行算法的效率定义

B为处理机台数

在处理台数规模不变的特定情况下并行算法加速比SB和处理机台数B成正比, 也叫算法线性加速比, 如果SB比B多, 那么该算法是超线性加速比。

设计高性能计算机并行算法要充分考虑到并行算法的扩展性, 这也是再设计并行算法结构时要充分考虑到的问题, 扩展性有3 种分别是资源扩展、 技术扩展和应用扩展, 扩展性主要是并行算法在对处理机数目的有效利用的一个度量, 并不是算法内在的通信和并行性需求。

加速比、 效率和扩展性是评价并行算法性能的3 个指标, 加速比是最优串行算法运行时间和B太处理机并行运行时间的比值, 效率是加速比与B的比值, 我们在设计并行算法的时候要充分考虑到加速比、 效率和扩展性3 个指标。

6 结语

从理论和设计方法两方面对分布式并行算法进行了简单的描述, 随着计算机技术的发展, 人们对计算机的数据处理性能有很高的要求, 最初的计算机处理能力已经不能满足计算机领域的发展, 并行处理技术可以提高计算机大数据的并行处理性能, 从国内外并行算法的应用上分析出我国对并行处理能力要加大投入, 才能追上技术领先国家。 分布式并行算法提高计算机的数据处理能力, 在计算机技术领域发挥着重要的作用。 并行处理技术分硬件技术和软件技术, 目前硬件方面有很大的提高, 但是在软件方面还存在问题需要解决, 算法是软件的核心, 要推动并行处理技术的发展, 必须要先重点研究并行算法。

摘要：计算机计算方法从单机技术发展到多机并行技术, 这是计算机计算模式适应未来科技发展的趋势, 国家的科技发展需要并行处理技术的推动, 并行处理技术能快速地发展, 源动力来自于人们对工程计算机能力的需求。在这几年, 并行处理技术得到很大的推动与发展, 并行算法处理技术的应用提高了计算机大数据处理的能力。介绍并行算法应用情况的背景和研究现状, 阐述了并行算法技术的分类及设计方法。

关键词：分布式,并行算法,计算机计算方法

参考文献

[1]许林.群智能算法可并行性分析及其FPGA实现[J].journal6, 2010, 46 (33) :54-57.

快速并行算法 篇7

接触网高度测量主要分为两大主流方向, 即接触式测量与非接触式测量[5,6]。接触式测量, 一般是在受电弓上安装角位移传感器, 受电弓弓板高度发生变化时, 主轴的角度发生变化, 根据此角度变化值即可反演出接触网的高度变化[7]。非接触式测量主要是基于光学原理, 一端由光源对准接触网发射准直光束, 另一端由探测器接收反射光束, 根据光束在探测器靶面的投影位置得出接触网高度[8]。

接触式测量一般为间接式测量, 无法真实反映出接触网高度的实际变化情况, 因而不能为受电弓提供反馈预测, 而非接触式测量则可有效规避上述问题, 同时不会对被检测受电弓的力学特性产生任何影响, 所以成为当前主流的测试手段。但是, 现有非接触式测量大多基于光学方法, 容易受到外界光线环境干扰, 特别是接触网高度测量大部分是以天空为背景, 在太阳直射的情况下, 会在一定程度上影响测量结果, 因此应在减弱非相干光源干扰等方面加以改进。本文所设计的接触网高度快速检测系统 ( 见图1) , 在现有的非接触式测量设备的基础上, 增加了GPS太阳高度角定位模块, 通过激光雷达对准角度的反向调整使其尽量避免太阳直射对测量结果的影响, 测量示意图如图2 所示。

1 系统的硬件结构

该接触网高度检测系统主要由激光雷达阵列、GPS太阳高度角定位模块、数据采集及处理模块、激光雷达对准角度调整结构、接触网高度输出模块等几部分组成 ( 见图3) , 固定在电力机车顶部受电弓装置附近。

1. 1 数据采集及处理模块

作为整个系统的数据处理及时序控制的核心部分, 采用FPGA + DSP双处理器结构。其中, FPGA用于时序信号的产生、信号采集芯片的驱动、控制命令的收发; 而DSP则主要是用于高速信号的提取与处理。

1. 2 激光雷达阵列

为了减小受电弓的单点磨损, 接触网沿导轨的水平方向呈“之”字形分布, 因此, 不同时刻接触线与受电弓接触点位置不同。要想测量其当前高度, 必须首先对其位置进行快速定位后再进行测量。在实际测量中, 接触网高度起伏在5. 3 ~ 6. 5 m, 去除车体及结构高度, 测量高度范围小于2 m。由于动车的接触网线径为12. 9 mm, 为检测出接触线高度, 要求激光雷达角分辨率不大于0. 37° 即可[9]。为此, 本系统选择UTM - 30LX - EW型2 维激光扫描雷达对机车上方接触线可能存在的位置进行快速扫描, 通过信号处理, 可计算出当前接触网位置和高度。该雷达测量范围270°, 可在100 000lx光强下工作, 且扫描角分辨率高达0. 25°。与本文数据采集及处理模块相结合, 单次扫描及高度测量时间小于30 ms。

为了进一步缩短单次测量时间, 提高检测频率, 采用了激光雷达阵列结构。该结构由若干激光雷达排列组成, 用于实现对当前接触网高度进行等间隔分时循环采样, 时序图如图4 所示, 以进一步提高测量频率。本系统采取的雷达阵列数为2。

1. 3 GPS定位模块及雷达对准角度调整结构

本系统通过GPS模块实时获取机车当前位置、时间信息, 计算出当前太阳高度角后, 根据计算的角度通过反向调整激光雷达的对准角度调整结构, 使雷达阵列背对太阳的角度进行接触网高度测量, 以避免太阳直射的影响。为了避免对准角度调整结构的频繁调整对测量速度产生影响, 仅将机车上表面以上的半球空间平分为两大部分, 如图5 所示。当太阳高度角位于空间1 范围内时, 调整雷达阵列对准1 位置;当太阳高度角位于空间2 范围内时, 调整雷达阵列对准2 位置。只有太阳高度角在空间1 和空间2 发生角度变换时, 才进行角度调整, 其他时刻雷达阵列位置保持不变, 从而避免了调整结构的频繁扰动。

1. 4 接触网高度输出模块

每次接触网高度计算结束后, 实时通过该模块的RS485 串行接口将计算结果反馈给受电弓控制器, 以便为受电弓的搭接角度提供信息参考。

2 系统的软件控制流程

结合上述硬件部分的描述, 本检测系统主要实现如下功能: GPS信息采集及太阳高度角计算、雷达阵列对准角度的调整、雷达阵列的驱动与数据采集、接触网高度的数据处理与计算、检测结果的反馈输出。系统流程图如图6 所示。

设备在运行过程中, 数据采集及处理模块首先利用GPS定位模块, 读取机车当前的位置和时间信息, 按照太阳高度角计算公式对当前位置太阳高度角进行计算。根据计算得到的太阳高度角范围, 按照图5 方式, 通过角度调整结构对激光雷达阵列的对准角度进行判断和调整。角度调整结束后, 数据采集及处理模块通过时序驱动信号, 对激光雷达阵列依次进行等间隔驱动控制, 如此循环往复。激光雷达阵列将采集到的扫描数据依次传输给数据采集及处理模块。数据处理模块将扫描数据进行提取和计算, 将计算结果实时反馈给受电弓控制器, 以实现对接触网高度的持续测量。

3 实验结果

检测精度是衡量整个系统性能的最为关键性的指标。利用该系统分别对500 mm、1 000 mm、1 500mm、2 000 mm的给定距离进行100次连续测量, 测得的误差范围分别为±14 mm、±10.5 mm、±10.5mm和±8.5 mm。

在500 ~2 000 mm测量范围内, 本系统的测量精度小于 ± 15 mm。此外, 在系统实时性方面, 通过实际测量, 平均单次采样及处理时间小于16 ms, 即测量频率小于50 Hz。

4 结论

非接触式接触网高度快速检测系统与现有常规接触网高度检测设备相比, 引入了多个激光雷达等时差并行循环测量, 大大缩短了单次扫描与测量所消耗的时间。此外, 还将太阳高度角测量模块引入系统中, 作为参考值反向调整激光雷达测量时的对准角度, 进一步降低太阳直射对测量结果造成的干扰, 增强了系统的适应性和稳定性。

参考文献

[1]占栋, 于龙, 肖建, 等.接触网几何参数高速动态视觉测量方法研究[J].仪器仪表学报, 2014, 35 (8) :1852-1859.

[2]林邓伟, 李东亮.铁路接触网导线几何参数的激光测量系统[J].电子器件, 2015, 38 (1) :174-177.

[3]王春革.铁路接触网融冰电器系统设计[J].工业控制计算机, 2015, 28 (2) :113-115.

[4]郭晓旭, 刘志刚, 张桂南, 等.角点配准与图像查分的接触网绝缘子故障检测[J].电力系统及其自动化学报, 2015, 27 (2) :8-14.

[5]马金芳, 于龙.我国地铁接触网检测现状及发展趋势[J].都市快轨交通, 2013, 26 (2) :26-29.

[6]彭朝勇.便携式接触网导线几何参数检测系统[D].四川:西南交通大学, 2005.

[7]朱德胜.德国接触网动态检测技术[J].电气化铁道, 2004 (3) :13-17.

[8]牛大鹏.非接触式接触网几何参数检测系统研究[D].四川:西南交通大学, 2004.

快速并行算法 篇8

近年来, 随着电子技术的快速发展, 电力系统暂态录波明显向高采样率、连续稳态记录和海量存储的趋势发展[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.