并行处理技术

关键词：

并行处理技术（精选九篇）

并行处理技术 篇1

谷物粒型作为谷物外观的主要形状，是评价谷物品质的重要指标之一[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 结论

一种新型多DSP并行处理结构论文 篇2

实现一个典型的多DSP并行处理结构，各处理器的三大总线要全部相连。图2给邮一个基本的多处理器系统结构图。在多系统中，某一时刻总线由主处理器控制，并且主处理器驱动所总线。由于民多处理器后，包括片内存储器以及IOP寄存器在内的所有地址空间是统一编址的，因此事实

上只有两个节点（处理器或外设）在同时刻在总线上活动，而此刻总线对于其它节点来谙阻塞的。这，其它接口点能通过链路口或者FLAG标志口进行点对点通信来交换数据和消息。

在多处理器系统中，各控制线上除主DSP外的其它所有节点都属于负载，所以对于每一根控制线来说都是一个多负载的连接，必须在每个DSP附近接串接电阻以增强驱动能力，否则会由于驱动能力不足而导致所进行的操作失效。另外在所有低电平有效的一上应接上拉电阻，以保证在没有进行操作时从DSP以及外接不会接收到虚假的指令。由于本系统是一个独立的结构，并没有与外部主机相连，故主机接口控制线在各DSP相连的情况下，应像其它未用管脚一样根据ADI技术文档的要求进行处理。而本结构与外部的通信可以通过同步串口工者在总线上挂接一片双端口RAM来进行。

另外多处理器系统的时钟、复位步问题一个决定系统工作正常与否的关键问题，各DSP的复位信号可同时接到看门狗的输出端。时钟信号必须在阻抗可控的传输线中传输，为保证各DSP的时钟信号之间不存在相位差，或者说相位差在系统允许的范围内，一般应采取始端连接的方式。图3给出串联传线分配时钟的例子，它允许在不同的路径中存在延时，每个设备必须在线的终端。传路径必须均匀分布，以使各路径上的传输延迟相互匹配。匹配的反相器必须在同一IC上，且相互之间的时间滞后差必须小于1ns。

并行处理系统的硬件结构搭建好后，如何才能很好地发挥其超强的处理能力，则要靠软件的设计来实现。为适应计算任务的多样性，可以采用1片ADSP-21161N作任务管理器，另外5片ADSP-21161N作运算器的主、从式拓扑结构。这样做还有利于实现指令间的流水处理，提高执行效率。而软件实现是可以根据具体的要求来完成，考虑到系统的高速、高效、实时性，软件可采用ADSP-21161N汇编语言进行编程。

多路处理器的并行处理 篇3

1.1 原始题目

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai;若由机器B来处理, 则需要时间bi。既不能将一个作业分开由2台机器处理, 也没有一台机器能同时处理2个作业。设计一个动态规划算法, 使得这2台机器处理完这n个作业的时间最短 (从任何一台机器开工到最后一台机器停工的总时间) 。研究一个实例:

要求:

输入:输入一个正整数n, 表示要处理n个作业。在接下来的2行中, 每行有n个正整数, 分别表示处理机A和B处理第i个作业需要的处理时间。

输出:计算出的最短处理时间。

1.2 解题思路

以作业划分阶段, 每个阶段保存2个状态:

(1) 当前作业在A上完成, 且总时间最小时, A, B机器分别的处理的时间。

(2) 当前作业在B上完成, 且总时间最小时, A, B机器分别的处理的时间。A机器和B机器可同时处理作业, 但同一时刻只能完成一项作业。

具体算法:

整型三维数组保存状态

第一维表示第几个作业, 第二维表示当前作业在哪台机器上完成, 第三维表示此时A, B的处理时间。

递推计算即可。

程序中声明了以下全局变量:

可以看出声明了一个三维数组和一个四维数组, 其中的400是根据“result=mn=m*n;//m是所有完成作业的时间中最长的一个作业时间, mn是所有作业的最长完成时间”中的//mn来确定的。可以看出, 当任务个数和最长作业完成时间很大时, 开辟的数组是惊人的大。

其中的p[i][j][k]表示完成k个作业前, A机器有i个时间可以处理, B机器有j个时间可以处理。

1.3 动态规划代码

1.4 运行结果

研究一下竟然发现该计算结果是错误的。其实如果把机器换成处理器, 把作业换成任务, 则题目其实就是二处理器的并行处理问题。于是考虑是否有新的解决问题的办法呢?

2 过渡方案

题目实质就是确定每一个任务选择哪一个处理器, 因此对每一个任务设置一个变量, 循环设置每一个处理器的状态 (0或1) , 来用贪婪法求解出结果。代码是:

如果任务很多, 那么该程序实现起来是不现实的。

3 动态规划

3.1 修改的题目

一台机器有M个处理器, 每个处理器可以同时处理任务, 同一个处理器一次只能处理一个任务。共有N个任务等待处理。现给出每个处理器处理每个任务所需的时间, 计算完成这些任务需要的最少时间。

3.2 声明的全局变量

跟原始的算法相比, 声明的全局变量占用的空间小了许多。而且数组的含义更加简明易懂。对比 (sel[j]和p[i][j][k]) 。

3.3 初始化

3.4 动态规划算法

3.5计算最优解

3.6主函数测试多个处理器

可以看出, 算法跟前面对比简洁了许多。

4算法特色

4.1占用内存空间小

占用内存大的几个变量如下:

对比“机器调度”中的变量定义:

其中mn=m*N, 当m为2000, N为10000时, 定义的变量占用的内存空间是巨大的。

4.2算法简明易懂

对比“机器调度”中的相关代码:

4.3计算最优解更加简单方便

对比“机器调度”中的相关代码:

4.4算法功能强大

本算法可以计算32768个处理器处理10000个任务的最小时间:

而“机器调度”算法处理2个处理器和100个任务已是十分困难了。

5测试结果

系统有2个处理器处理任务:

2个处理器并行处理完成10000个任务需要的最少时间是5608106。

系统有32768个处理器处理任务:

可以看出随着处理器的翻倍增加, 并行处理10000个任务需要的最少时间也是很快递减。

参考文献

[1]软件创新之路--冲破高技术营造的牢笼.电子工业出版社.

[2]程序设计实践.机械工业出版社.

[3]数据结构教程与实训.北京理工大学出版社.

[4]软件工程实践者之路 (英文影印版) .5版.清华大学出版社.

[5]软件工程-实践者的研究方法.机械工业出版社.

[6]测试流程管理.北京大学出版社.

[7]软件需求.机械工业出版社.

[8]计算理论基础 (英文影印版) .2版.清华大学出版社.

[9]应用程序调试技术.清华大学出版社.

并行处理技术 篇4

取消方案一中的中间库数据迁移工作，采用数据同步技术，提前将老系统的数据同步至中间库，在老系统业务停机几小时后即可完成数据同步，开始进行数据转换，既降低方案一中的网络带宽花销，又减少了方案一中老系统至中间库的数据迁移时间。数据同步需在老系统数据库与中间库上部署数据同步软件，该软件从老系统生产数据库中获取实时数据，与中间库建立连接，将实时数据同步发送至中间库[2]。

数据同步包含首次数据同步与增量数据同步，首次数据同步指数据同步软件将有迁移需求的数据以某时间点为截止全量迁移复制至目标数据库，增量数据同步指首次数据同步结束后到业务系统停止时将所产生的新增数据实时同步至目标数据库。增量数据同步的原理为实时分析源端数据库的日志，生成数据变动的压缩表，以捕获增量数据，数据经压缩和加密后传送至目标数据库，经过目标库数据同步软件的.装载后，即实现了增量数据的同步。

2.2.2、分库并行数据转换

在采用实时数据同步的基础上，放弃使用原有中间库，新建 4 个中间库进行数据转换及校验工作，中间库既作为数据源也作为数据迁移中间库，可实现 4 个中间库并行的数据转换及迁移工作。在此过程中需要数据同步软件将老系统数据实时同步到 4 个中间库 , 正式数据迁移开始之后即可开展数据转换、校验、整改与迁移工作。按此方案，采用并行的数据迁移方式，可在不同的中间库分配不同的供电局业务数据，相较之前的单链路串行数据迁移方式，即需要按顺序依次进行各局数据迁移、转换的方式，此方案极大程度提高了数据迁移所需时间，方案二如图 2 所示。

2.3、对比结论

试点局上线进行数据迁移工作时采用数据迁移方案一，数据迁移时数据量约为 1 T，耗时为 4 天。由于南方电网营销管理系统后续上线供电局较多，迁移数据量较大，约为 2 T，采用方案一耗时较长。在数据迁移过程中，为保障新老系统数据的一致性及数据迁移的成功率，需要对老系统进行业务系统停机处理，若按方案一，需要对老系统停机 7 天或更久。停机时，无法进行客户算费收费工作，而电网公司业务上不允许长时间对业务系统停机。为保障电网公司利益不受损失，市场营销业务能正常快速开展，综合对比后正式数据迁移采用数据迁移方案二。

3、数据迁移改进方案实施应用

3.1、数据迁移方案实施

3.1.1、全量数据实时同步

通过对业务数据量及服务器性能分析后，4 个分库的建设工作顺利完成。在正式数据迁移开始前，需完成全量数据实时同步工作。同步过程需要使用数据同步软件将数据从老系统同步至 4 个中间库，因此需要在老系统数据库服务器上及 4 个中间库上分别安装部署数据同步软件。此次同步为异构服务器且不同数据库之间的数据同步，源端(老系统)为 AIX 服务器，目标端(中间库)服务器为 LINUX 服务器;源端数据库版本为 oracle10g, 目标端版本为 oracle11g。

由于分为 4 个中间库，首先需在源数据库和目标数据库创建 4 个同步队列，随后在源端数据库与 4 个目标端数据库创建同步用户，最后在源端导出数据库结构并在目标端进行导入。上述准备工作完成后即可开始同步数据，同步完成后进行同步数据比对工作，比对内容为源端与目标端核心数据表的记录数与内容。针对比对后遗漏或缺失的数据表，采取两种方式进行修复：对于数据量比较小的表，通过ORACLE DBLINK 技术进行修复;对于数据量比较大的表，采用数据同步软件进行重新同步。

正式上线前一天，首次数据同步开始，通过数据同步软件将老系统数据库数据从 AIX 主机(老系统数据库)同步至 4 台 LINUX 主机(4个中间库)。首次数据同步完成后，开始增量数据同步。在老系统业务停止后，实时增量数据同步结束，开始进行数据比对与修复工作，约两小时后，数据比对修复工作完成，一致率100%，数据同步工作顺利完成。

3.1.2、并行数据转换与迁移

数据同步完成后，在 4 个中间库同时开展数据转换与迁移工作，根据“南方电网营销系统物理数据模型”为标准，开展新老系统数据转换与迁移工作，将老系统数据编码通过数据库脚本转换为新系统所支持的数据编码。为提升数据迁移脚本执行效率，在数据迁移脚本中适当加入索引能提高数据库的性能，建立索引之后，可以合理的使用资源;此时同样需要由良好的 SQL 语句进行支持[3]，进行 SQL 语句优化之后，可进一步提升数据迁移时的效率。

在数据同步开始前，针对不同的分库分配了不同的业务数据，如不同的分库同步不同供电局的老系统历史数据，且每个分库的数据量基本一致，因此可以实现四库并行的同步数据转换与迁移工作，与之前方案相比，数据转换将近提升了 4 倍。

在正式数据迁移时，应设计南方电网营销管理系统的应用级灾备切换场景[4]，当数据迁移过程中发生灾难且无法恢复时，致使营销服务中断，应快速切换回老系统，确保公司核心业务系统运行的连续性。

3.2、核心数据功能验证质量提升

迁移完成后，对南方电网营销管理系统数据库与《南方电网营销系统物理数据模型》进行完整性对比，保证数据的安全、完整、真实，如图 3 所示。

4、结束语

本文通过分析南方电网营销管理系统迁移现状，结合业务现状、技术现状等角度提出了两种数据迁移方案，进行了详细的分析与阐述，并重点描述了方案二的设计原理与实施应用。本文所提出的历史数据迁移改进方案已经应用于云南电网公司南方电网营销管理系统的实施上线工作中，并取得了工程实际的应用经验。

该方案为大规模企业级管理信息系统的上线实施数据迁移工作提供了高效实用的技术支持，减少了不必要的损失，节省人力资源。

参考文献：

[1] 田V. ERP系统集中部署模式下的历史数据迁移方案研究[J]. 电力信息与通信技术, , 12(8): 77-81.

[2] 陈然. 大规模电网运行数据实时同步技术研究[J]. 云南电力技术, 2015, (5):24-26.

[3] 罗伟,蒋苏湘,周沿东,魏鹏飞. 湖南电力营销系统数据库性能优化研究[J]. 电力信息与通信技术, 2014, 12(4): 30-34.

[4] 郭晓艳，王扬，孙轶凡，侯丹，章斌. 营销系统应用级灾备体系研究及建立[J]. 电力信息与通信技术, 2014, 12(10): 13-17.

视频并行处理系统分析与设计 篇5

关键词：非透明桥,PCI-E协议,并行运算,视频,同步机制

引言

图像与人们的生产生活息息相关, 是人类获取和交换信息的主要来源, 据统计人类有80%以上的信息来自于图像。随着数字化进程的加速普及, 人们对视频的需求提出了更高要求, 电视、内容、数字摄像机等提供的各种形式视频正在向高清转变。高清晰度的视频在各个领域的应用越来越广, 3D技术也日趋成熟, 需要对海量视频数据进行复杂处理的应用越来越多, 这对视频处理技术提出了一个新的挑战。传统的视频处理多采用GPU (Graphic Processing Unit图形处理器) 进行, 限于目前单个显卡的处理能力有限, 需要同时对一个大屏幕的高清视频数据进行纹理映射、颜色混合、3D渲染等操作的场合已经很难胜任了。近年来, 对于视频并行运算的研究取得了很多进展, 提出了很多的解决办法, 但是这些办法都是仅仅解决了视频处理中的某一个问题。例如目前利用网络进行并行运算的计算机系统, 虽然其并行运算的能力较强, 但是对于海量的视频数据, 其数据传输能力有很大的局限性;网络带宽不足以实时地传输信号, 这导致出现图像无法流畅显示的问题, 随着目前需要处理的视频数据量的增加, 这种缺陷已越来越严重。

1 非透明桥技术

非透明桥顾名思义是一座连接两端处理器的桥梁, 且两端的处理器均有独立的地址空间, 桥两端的主机不能看到另外一个主机完整的地址或者I/O空间。在非透明桥环境中, PCI Express系统需要在从一个内存地址空间穿越到另一个地址空间时进行地址翻译。每一个非透明桥 (NTB) 端口都有两套基地址寄存器 (BAR) , 一套是给主设备端用的, 另一套是给从设备端用的。基地址寄存器可用来定义在非透明桥另一端的内存地址空间的地址翻译窗口, 并允许这个翻译被映射到本地的内存或I/O空间。

非透明桥允许桥两边的主机通过便笺寄存器、门铃寄存器和心跳消息来交换一些状态信息。便笺寄存器在非透明桥的两端都是可读写的, 但是, 便笺寄存器的数量在具体的实现中是可以不同的。他们可以被桥两边的设备用来传送一些状态信息, 也可作为通用的可读可写寄存器使用。门铃寄存器被用来从非透明桥的一边向另一边发送中断。非透明桥的两边一般都有软件可以控制的中断请求寄存器和相应的中断屏蔽寄存器。这些寄存器在非透明桥的两边都是可以被访问的。心跳消息一般来自主设备端往从设备端的主机, 可用来指示它还活着。从设备主机可监控主设备主机的状态, 如果发现出错, 它就可以采取一些必要的措施。通过门铃寄存器可以传送心跳消息。当从设备主机没有收到一定数量预先规定好的心跳消息时, 就可以认为主设备的主机出错了[1]。

2 视频处理系统架构

本文提出了一种并行视频处理的系统架构, 具体见图1, 该并行视频处理系统包括了多个视频处理系统, 一个非透明桥和一个视频输出系统。视频处理系统主要完成规定的各种视频处理, 视频输出系统负责完成视频数据对屏幕的输出。非透明桥 (NTB) 用于连接视频处理系统和视频输出系统, 控制数据和视频数据的交互通过非透明桥芯片实现;非透明桥为系统之间提供一个高速的数据交换通道和通信的桥梁。多个视频处理系统和一个视频输出系统通过PCI-E总线和非透明桥 (NTB) 相连接, 利用NTB的交换 (switch) 功能, 实现多个视频系统之间的点对点通信。各个视频处理系统之间相互连接, 每个视频处理系统都可以单独和任意一个视频处理系统之间通信和进行海量数据传输;视频输出系统通过非透明桥的连接, 也可以和任意一个视频处理系统连接, 视频处理系统可以将任意一个视频处理系统的数据输出给屏幕显示。每个视频处理系统具有一个或多个外围设备相关联的信息处理模块, 外围设备信息通过PCI-E协议进出传输。

数据传输中采用了高速的PCI-E传输通道, 该并行架构系统解决了海量视频数据传输的瓶颈问题, 为并行处理提供了硬件基础。单通道的PCI-E总线[2]带宽可以达到10Gbps, 该总线有X1、X2、X4、X8和X16、X32 (X32目前还不支持) 通道规格可选, 如果采用X4, 通道的总带宽可以达到40Gbps (PCI-E 2.0协议) , 单方向带宽可以达到20Gbps。超宽的PCI-E数据传输通道为海量视频数据提供了高速通道。例如逐行扫描制式, 帧率通常为60Hz的1080P无压缩视频, 传输需要3Gbps的数据通道, 采用PCI-E通道可以传输多个1080P视频数据, 保证了视频信号传输的流畅。

3 视频并行处理方法

在图像处理的过程中, 需要对图像进行纹理映射[3]、颜色混合、深度缓冲、模板缓冲等步骤。这些串行步骤的执行均需要非常大的计算量, 并且耗时。因此, 在上述的并行视频处理系统的基础上, 提出了一种并行视频处理[4,5]的方法。我们这里将视频图像的处理分成若干个步骤, 分别由不同的视频处理系统来处理, 最后完成视频图像的处理并通过视频输出系统进行输出显示。每个视频处理系统都具备任意一个图像处理步骤的功能, 它根据上一个数据流携带的处理命令来执行相应的处理。我们在传输过程中对视频流数据进行打包, 一包数据可以包含一帧图像或者几十帧图像, 这可以根据实际的需求而定, 原则是数据交换的次数越少越好, 但是数据包也不能太大, 以至于影响到图像处理的时间。在数据包里边, 专门指定了一个位置用于包含视频数据处理命令。该处理命令在该包数据被成功处理后, 该位置的处理命令改为下一个处理命令。若该包数据没有被成功处理, 该处理命令不变。

该方法人为地将需要使用的视频处理过程分为若干个步骤, 每个步骤分块的原则是处理时间基本相等;视频处理步骤的粒度可大可小, 小至包括一个视频数据的深度缓冲或者对数变换, 大至视频数据的整个3D渲染过程;每个视频处理步骤由系统内的单个视频处理系统进行处理, 同时考虑到每个处理步骤的时间差异性问题, 提出了一种同步机制;在处理过程中, 同一个时间内, 每个视频处理步骤是同时在每个视频处理系统进行的, 达到了并行处理的效果;最后处理好的数据统一由高速的PCI-E通道送至视频输出系统进行输出显示。

因为有了各个视频处理系统间的高速PCI-E通道, 所以数据包传送的时间相对于图像处理步骤的时间来说非常少。每个图像处理步骤都包含了一个完整的流程, 如图2所示。

我们可以将图像处理的过程分为A、B、C、D四个步骤, 每个步骤在一个视频处理系统中执行。如图3所示, 我们采用视频处理系统并行做图像处理。

在T1时间周期内, 由视频处理系统1发起图像处理的命令, 并且将完成了图像处理步骤A后的数据打包, 同时加上图像处理步骤B的处理命令, 发送到视频处理系统2。发送完数据以后, 视频处理系统1继续对后续进来的视频流信号做处理。在T2时间周期内, 视频处理系统2接收到视频处理系统1发送过来的数据包后, 首先分析其图像处理命令, 发现是图像处理的步骤B, 便完成步骤B, 同时打包该处理完的数据并加上图像处理步骤C的处理命令, 将数据发送到视频处理系统3。发送完数据后视频处理系统2继续完成其后续视频流的处理。在T3时间周期内, 视频处理系统1和视频处理系统2在进行视频图像处理的同时, 视频处理系统3接收到发过来的视频数据包后, 对处理步骤命令进行分析, 完成步骤C的处理;处理完毕, 数据打包并添加步骤D的处理命令后发送到视频处理系统4。视频处理系统3继续完成后续的视频流的处理。在T4时间周期内, 视频处理系统1和视频处理系统2在进行视频图像处理的同时, 视频处理系统3接收到发过来的视频数据包后, 对处理步骤命令进行分析, 完成步骤C的处理;处理完毕, 数据打包并添加步骤D的处理命令后发送到视频处理系统4。视频处理系统3继续完成后续的视频流的处理。在T4的时间周期内, 视频处理系统1、视频处理系统2和视频处理系统3同时在做视频图像处理;视频处理系统4接收到数据后, 判断处理命令, 完成步骤D的处理, 此时该包图像全部处理完毕, 便送视频输出系统进行显示。

上述的处理过程只是一个基本视频数据并行处理方法, 它的一个关键在于整个图像处理步骤时间的合理安排, 要求每个操作步骤的划分合理。如果前级操作时间恰好等于后级的操作时间, 则最为简单, 前级的输出直接汇入后级的输入即可;如果前级操作时间大于后级的操作时间, 则需要

对前级的输出数据适当缓存才能汇入到后级输入端;如果前级操作时间恰好小于后级的操作时间, 则必须通过复制逻辑, 将数据流分流, 或者在前级对数据采用存储、后处理方式, 否则会造成后级数据溢出。

4 同步机制与异常处理

为了解决数据溢出问题, 本文在对图像处理步骤进行划分时, 尽量使得每个步骤的处理时间都相同, 这样可以很大程度上缓解前后级之间处理时间不一致造成的矛盾;同时引入同步机制[6], 在多个视频处理系统之间建立一个同步信息传递机制, 每个视频数据包被处理后往同步处理模块发送一个值, 当在一个时间周期内所有的处理步骤往同步处理模块发送了处理完毕的值后, 由同步处理模块发送视频数据流统一下传的命令。

图4为同步模块处理流程, 每次进入一个新的视频图像处理流程后, 同步模块开始计数;在同步模块计数器件, 图像处理的每个步骤处理完毕后, 视频处理系统均会发出处理完毕命令;同步模块接收该命令, 并对此进行判断在该图像处理周期中所有的处理步骤是否处理完毕;如果处理完毕则发出下个处理步骤的同步信号;若没有处理完毕则通过计数器判断该次处理周期时间是否达到T, 如果达到时间T则强制完成该处理周期, 发出下一个处理步骤的同步信号, 如果没有达到时间T则转入判断所有步骤是否处理完毕的流程中。

当强制同步信号到来时, 由于某种特殊情况, 视频处理系统对于本系统的图像处理步骤无法完成, 如图5所示, 在T3周期, 视频处理系统3处理出错。此时, 为了不影响整个处理流程的时间, 将数据包继续往下一级发送, 并且执行相同的处理步骤。在T3时间周期, 本来由视频处理系统3完成的处理步骤C, 出错后, 在T4时间周期, 由视频处理系统4完成。上述提到图像处理步骤A、B、C、D可以根据不同的应用来定义, 处理步骤的粒度可大可小。对于一些比较大粒度的功能分工, 如3D处理和GIS等, 也可以采用上述提到的并行处理方法完成。如图3所示, 可以用步骤A表示3D处理, 步骤B表示GIS处理, 由两个视频处理系统分别完成, 同时在视频输出进行叠加显示;并采用方法中提到的同步机制使得两个系统处理后的图像能同时显示。

5 结果与分析

本文根据目前一些海量数据并行处理的应用限制, 提出了通过非透明桥连接的多CPU并行出现系统架构, 并提出了一种并行处理的方法。该并行处理方法在笔者设计的系统平台中得到了实际应用和验证, 运行效果良好, 突破了单个高性能CPU计算能力, 大大提高了海量视频信号的处理能力;而且该处理方法不会单纯地依靠硬件技术如CPU处理速度等的发展, 可以通过合理调节视频处理步骤来实现快速视频处理的功能, 具有很高的产品推广价值。

参考文献

[1]李才华.PCI_Express非透明桥在智能系统中的应用设计[J];电子元器件应用.2009 (8)

[2]樊博, 王延杰, 孙宏海, 基于PCIe的高速图像注入式仿真系统[J];计算机工程与设计.2014 (3)

[3]薛军涛, 贺怀清, 张宇翔, 等, 典型纹理映射实现方法的研究[J].计算机工程, 2005 (3)

[4]易勇, 分布式并行视频服务器设计技术[J].贵州科学, 2000 (12)

[5]谷国太, 肖汉, 并行计算与并行处理技术的应用研究[J].河南理工大学学报, 2009 (10)

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

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

并行处理技术 篇7

传感器、遥感平台、数据通信等技术的不断进步使得遥感数据的获取趋于“三多”(多平台、多传感器、多角度)和“三高”(高空间分辨率、高光谱分辨率和高时间分辨率),也使得所获取的遥感数据爆炸式增长[1,2]。另一方面,以军事、监测、灾害应急等为目的的遥感应用对于时效性的需求越来越高,这都为遥感数据的处理带来了新的挑战。同时,在地学、空间科学和探测学等领域还有对数据进行实时处理或近实时的处理的应用需求。随着这些新的需求的出现,高性能计算(High Performance Computing)和并行计算(Parallel Computing),已成为遥感数据处理系统发展的必然趋势。

并行计算是指同时使用多种计算资源解决计算问题的过程。并行计算并不是什么新的思想,只是将它扩展应用于计算机而已[3]。集群是一组计算机,作为一个整体向用户提供一组网络资源,组成集群的单个计算机是集群的节点(node),集群系统具有结构简单,对单台计算机的性能要求不高,结构上便于扩展等特点。1997年,美国NASA的Goddard太空飞行器研究中心(Goddard Space Flight Center)创建了第一个Beowulf集群——HIVE集群[4] 。此外,一些分布式的计算框架,如普通组件架构(Common Component Architecture)、Hadoop[5]、ProActive[6]等,也被应用在遥感数据处理当中。综观这些分布式计算框架,它们提供的接口复杂,开发人员需要较多的学习时间才具备二次开发的能力;而且这些都是通用计算框架,结构复杂,维护成本较高。针对这些问题,并考虑到遥感数据预处理过程中分块处理的可行性,在集群上研究并实现一种结构简单且具备通用性、可扩展性的遥感数据并行处理框架(下面简称并行处理框架),以简化遥感数据并行处理软件的开发过程。

1 并行处理框架设计

1.1 设计目标

1.1.1 通用性

为了易于实现遥感数据并行处理功能并简化其软件开发工作,需要并行处理框架的运行与具体的载荷和数据处理算法耦合程度较低,且灵活支持不同的遥感数据预处理并行步骤的实现。

1.1.2 可扩展性

并行处理框架的可扩展性包括两个方面:一是整个并行计算环境所包含的节点应该是可扩展的,这样可以方便用户的使用,适用更广泛的应用环境;二是支持新的遥感载荷数据处理功能的可扩展。

1.1.3 易用性

为了使用户在研制并行处理系统时,不需要实现消息通信、数据交换这些底层细节,只需专注于数据处理业务逻辑的实现,需要并行处理框架支持数据传输、任务调度、负载均衡等共用功能,并提供简单易用的接口,以实现简化并行程序设计与开发。

1.2 数据流程

首先解释本文中涉及到的两个词含义:作业和任务。作业是某一个遥感数据预处理的所有处理步骤的集合,任务则是指该遥感数据预处理过程中的某一个步骤,一个作业包含多个任务。考虑到遥感数据处理作业数据量大、计算密集、处理流程相对固定的特点,可将作业进行三步式处理。首先将作业划分成任务,然后将任务调度到各个计算机节点进行并行处理;处理完成后进行处理结果汇总并生成产品。数据处理流程如图1所示。

基于这个数据流程,并行处理框架采用主从模型(Master-Slave),Master-Slave模型中,有两种类型的进程,单个的Master中维持有全局数据结构并负责任务的划分和分配,而Slave完成任务的计算工作,并把结果返回给Master[7]。运行时将会在集群环境中选择一个节点作为管理节点运行Master进程,将其他节点作为承担任务处理的计算节点,运行Slave进程。

1.3 框架组成

消息传递接口(MPI)是比较成熟的并行计算的API,通过MPI可以很方便的在管理节点和计算节点间进行消息和数据的发送与接收。该框架包括了运行管理器、任务划分器、任务规约器、故障管理器、插件管理器和任务处理器等组成部分,如图2所示。另外框架通过所实现功能的应用编程接口(API)以及预定义的用于应用处理的应用编程接口,供用户进行框架扩展开发,实现用户需要的功能。

运行管理器:运行于管理节点时,主要负责对作业进行任务划分、任务调度、进行处理结果的汇总与保存;而在计算节点上,运行管理器接收管理节点发送的任务、进行任务的处理和处理结果的反馈。采用配置方式提高运行管理器的对多种遥感数据处理的适应性。运行管理器的工作流程是:1)读取配置参数,初始化运行环境;2)管理节点与计算节点建立通信;3)调用插件管理器,进行插件的注册;4)调用任务划分器插件进行任务划分;5)在管理节点上,进行任务调度,在计算节点上,接收管理节点分配的任务,调用任务处理器插件进行处理。任务调度策略参见第2节。

任务处理器:主要是用来实现基于数据划分的各并行任务的处理,在框架中预定义了任务处理器的接口,具体功能将由用户根据数据具体任务内容来实现。计算节点的运行管理器接收到管理节点的运行管理器分发的任务后,将自动调用任务处理器对任务进行处理。

任务划分器:主要是根据作业并行处理的需要,将需要进行并行处理作业的遥感数据划分成适合任务处理器处理的数据块。在框架中预定义了任务划分器的接口,具体功能将需用户根据任务处理器的具体数据处理需求来实现。任务划分器对数据进行划分后,返回一个任务列表给管理节点的运行管理器。

任务规约器:主要用来实现将各计算节点处理完成的结果进行汇总,它定义了如何将每一个任务的处理结果进行汇总以及其他操作。在框架中预定义了任务规约器的接口,具体功能将需用户根据数据具体需求来实现。

故障管理器:负责发现并行计算环境中管理节点与计算节点出现的异常,并采用一定的机制,自动进行故障处理,使系统具备容错能力,保证作业的并行处理能够顺利、正常执行。管理节点和计算节点重要性不同,采用不同的故障处理方式。对于管理节点,采用备用管理节点的方式实现容错,如果,作为备用管理节点的计算节点侦测到管理节点出现异常后,其将自动让备用管理节点的运行管理器接管并行任务管理,并采用类似于数据库检查点回卷恢复(Rollback Recovery)的策略完成管理节点的切换[8]。对于计算节点,采用代替资源的方式,当某个计算节点出现故障,故障管理器自动寻找一个新的节点,对故障节点未完成的任务进行重新分配。

插件管理器:主要完成框架中任务划分器、任务处理器、任务规约器等插件的加载和注册,以供运行管理器使用。工作流程是:1)根据配置文件确定每一个插件的名称和位置;2)加载插件;3)查找插件中的注册函数位置;4)调用注册函数的指向类。框架定义了TaskSpliter、TaskCollector和TaskProcesser,并对这些插件设计提供了接口定义的规范与约束。各个插件的接口定义如表1所示。

任务处理器、任务划分器和任务规约器与具体的载荷数据处理过程有关,需要用户根据具体情况实现,在框架中定义了简单的接口规范,用户很容易遵循实现。而运行管理器、故障管理器和插件管理器与具体的载荷数据处理运行与实现无关,由并行框架统一实现,减少了并行开发的工作。这样,用户只需进行与遥感数据处理相关插件开发,就可基于并行处理框架构建一个并行处理系统,而无需关注并行处理底层具体的细节实现。

1.4 基于插件的开发模式

在用户进行任务划分器、任务规约器以及任务处理器开发时,必须继承并行处理框架提供的基类(采用工厂模式)。插件管理器通过注册函数来完成插件工厂类的注册,注册函数registerPlugin(PluginFactory &)的实现如下面程序片段所示。

void registerPlugin(PluginFactory &factory)

{

// MyTaskSpliterFactory派生自

// TaskSpliterFactory,并实现其中接口

factory.setTaskSpliterFactory(new MyTaskSpliterFactory());

}

如前所述,任务划分器、任务规约器和任务处理器是由用户根据一定的规范实现的,以动态链接库的形式封装,作为插件嵌入整个框架运行的。插件的描述采用XML格式,主要包括以下几个方面的内容:插件名称、动态连接库位置、注册函数、工厂类等。例如:

<plugin>

<pluginname> TaskSpliter</pluginname>

<pluginpath>pluginTaskSpliter.dll</pluginpath>

<registerfunction>registerPlugin</registerfunction>

<factoryname>TaskSpliterFactory</factoryname>

</plugin>

2 并行处理框架调度策略

常用调度算法有先到先服务调度(first-come first-served,FCFS)、最短作业优先调度(shortest-job-first,SJF)、优先级调度(Priority)、首次适配(FirstFit)、启发式调度算法(如模拟退火算法[9,10]、遗传算法[11])等。

评价一种调度策略优劣的通用准则包括CPU使用率(cpu rate)、周转时间(turnaround time)、吞吐量(throughput)、响应时间(interactive response time)、等待时间(wait time)等。除了这些准则外,为了更好的利用集群中每个计算节点的资源,还可能需要并行处理过程中系统资源的使用尽可能公平共享。另外,遥感数据并行处理系统的作业调度有自己的特点,要求系统在应急情况下具备一定的快速响应能力,应急情况下所提交的作业具有更高的优先级。

因此,并行处理框架在任务调度方面采用了如下基于优先级和时间戳的调度策略:为了能够有效调度,作业被赋予两个属性:优先级和时间戳。采用根据优先级排序的队列管理方式,在调度过程中,如发现优先级较低的作业等待时间超过了设定的最长等待时间,则将该作业转移到优先级高一级的队列中,并更改时间戳为当前加入队列的时间。

为了有效利用计算节点资源,在调度一个作业之前,预先估算系统中的计算资源是否能够满足该计算作业的需求;如果能够满足则继续调度该作业进行处理;如果不能满足则等待其他作业完成,或者挑选当前计算资源所能满足的作业进行调度。

3 实验与分析

基于上述的并行处理框架设计思想,现采用C++和MPI技术实现了并行处理框架,并在此基础上实现了遥感数据并行处理系统,其物理部署如图3所示。其中集群由1个管理节点和5个计算节点组成,各个节点的配置: Intel Xeon E5520 2.26 GHz CPU,8 GB内存,操作系统Windows Server 2003 x64。

现以数据分幅作业并行处理为例来分析并行程序效率。实验采用“无人机遥感载荷综合验证系统”项目获取的多光谱数据。多光谱数据共有4个波段,每一帧含有6 000个10 bit像素,测试数据的大小为8.8 GB。多光谱数据分幅作业并行处理的实验结果如表2、图4 、图5、图6所示,其中Nnode表示参与运算的节点个数,T(s)表示处理时间,Sp表示加速比,Ep表示并行效率。

通过实验结果可以看出,只有五个计算节点时,作业处理的时间会随着节点数目的增加逐渐缩减,但是缩减的幅度并不是线性的。从图4可以看出,处理时间在经过一个较大幅度缩减的阶段之后,会达到一个相对平稳的阶段。之所以会产生这种现象,是因为随着节点数目的增加,并行环境的管理开销和通信开销会随之增加。

4 结束语

经过深入研究并行编程模式和遥感载荷数据处理过程,设计了遥感数据处理并行框架。该框架可部署在集群系统上,支持多载荷、多种遥感数据处理步骤的并行实现,具有较强的通用性和扩展性;由于采用公共功能封装、具体数据处理功能通过插件实现的设计思想,简化了遥感数据处理并行实现的工作量,提高了遥感数据并行处理系统开发的效率。对并行系统而言,调度策略、负载均衡技术和容错机制等方面都会直接影响系统的并行效率和稳定性,将在以后开展更深入的研究。

摘要：为了简化对地观测地面系统遥感数据并行处理软件的开发工作,在分析遥感数据处理流程、并行任务调度和容错策略的基础上,设计了遥感数据并行处理框架。该框架集成了遥感数据预处理并行任务调度、消息和数据交换、故障管理等公共功能,并设计实现了简单易用的插件接口规范,以支持多载荷、多种遥感数据预处理功能的扩展以实现并行处理,具有较好的通用性和功能扩展性。最后基于消息传递接口(MPI)技术,在集群上实现了遥感数据处理并行框架,并在此框架上实现遥感数据预处理的并行系统,完成了系统并行性能测试与分析,结果表明该框架在简化遥感数据预处理并行功能开发的同时还能满足遥感数据并行处理效率要求。

关键词：遥感,并行处理,插件,集群,通用处理框架,MPI

参考文献

[1]朱述龙,张占睦.遥感图像获取与分析.北京:科学出版社,2000:52—52

[2]高恒振.高光谱遥感图像分类技术研究.长沙:国防科学技术大学,2011:4—4

[3] Gill S.Parallel programming.The Computer Journal,1958;1:2—10

[4] Dorband J,Palencia J,Ranawake U.Commodity computing clustersat goddard space flight center.Journal of Space Communication,2003;1(3):15—21

[5]霍树民.基于Hadoop的海量影像数据管理关键技术研究.长沙:国防科学技术大学,2010:24—26

[6]张建兵.基于网格的空间信息服务关键技术研究.北京:中国科学院遥感应用研究所,2006:95—96

[7]李军,李德仁.分布式遥感图像处理中的关键技术.武汉测绘科技大学学报,1999;24(1):15—19

[8]王亚楠.分布式容错检查点算法研究与软件设计.济南:山东大学,2010:8—9

[9]吴浩扬,常炳国,朱长纯,等.基于模拟退火机制的多种群并行遗传算法.软件学报,2000;11(3):416—420

[10]李文,陈英武,李菊芳,等.基于快速模拟退火的遥感数据处理调度方法.系统工程与电子技术,2011;33(2):334—338

并行处理技术 篇8

合成孔径雷达作为一种全天时﹑全天候的微波成像雷达,它在战场感知和灾情监测等方面有着不可替代的作用,随着SAR成像技术的发展,对回波数据实现实时处理的要求也越来越迫切。实时成像意味着信号处理器需要满足SAR信号处理过程中大数据通信带宽和大运算量及快速运算等处理能力的要求,由于SAR成像算法本身的复杂度和雷达数据的高速率,实时处理面对很大的挑战性,使用单处理器或处理芯片几乎难以实现,为了在不影响成像精度的前提下获得更好的实时性,并行处理成为解决这一问题的关键技术。

SAR并行成像系统按照划分方式不同,主要包括两种并行结构:基于数据划分和基于任务划分。对于这两种结构已有许多学者作过这方面的研究[1,2,3],文献[1]采用了数据划分结构,实现了一个基于ADSP21160的实时成像处理系统,该系统采用多块处理板卡形成分布式处理,各板卡彼此独立;文献[2]采用了一种板内多DSP并行处理,板间数据流水的形式实现实时处理;文献[3]设计了一种完全可编程的数字信号处理器,该处理器包括了16路并行通道和一个二维的内存结构以适应图像处理算法。以上并行处理系统都采用了多块处理芯片或处理器,系统并行结构复杂,不仅导致开发周期长而且硬件成本高。本文以目前应用最广泛的RD算法为基础,提出了一种基于GPU的并行成像处理方案,该方案充分发掘了RD算法内在的可并行性,不仅使成像速度大幅度提升,而且节约了硬件成本。

1 RD算法可并行化分析

GPU即图形处理器(Graphics Processing Unit),图形芯片最初用作固定功能图形管线,随着时间的推移,图形芯片的可编程性也随之日益增加,在此基础之上NVIDIA推出了第一款GPU,通过对GPU进行编程可以实现通用科学与工程计算。由于GPU专用于解决可表示为数据级并行的问题,通过为每个数据元素分配一个线程,通过SIMT(Single Instruction Multiple Threads)组织模式管理硬件中同时存在的线程,实现对所有数据元素的并行处理。

因此RD算法的可并行化程度成为获取高加速比的关键。RD算法的本质是将SAR成像的二维处理分解为两个一维处理过程,分别为距离向处理和方位向处理,在分解之前需要将雷达回波数据进行解耦。RD算法的计算开销主要体现在距离脉压、RCMC和方位脉压上。距离脉压通常采用频域匹配滤波的实现方式,实现过程为

undefined

式中:S0(fr,tm)为雷达回波在快-慢时间undefined域经过快时间傅立叶变换后的信号;H(fr)为频域匹配滤波的参考函数。从式(1)可以看出,匹配滤波主要包括3种运算:距离向FFT﹑频域相乘及距离向IFFT。

由于SAR回波数据沿方位向存储,在进行距离向FFT变换时,每条距离线数据之间是相互独立的,对于一块大小为Nr×Na的数据而言,(其中Nr和Na分别为距离向和方位向点数),Na条距离线数据可以同时进行FFT变换,因此距离向FFT变换的并行度为Na。并行度指在某一时刻可以同时执行的操作数[4],在理想条件下,并行运算所能获得的加速比等同于并行度,

但由于并行处理所涉及的资源分配及调度等原因,加速比在实际情况下要低于并行度。尽管如此,并行度为Na的FFT和IFFT变换经过并行处理后还是能获得很高的加速比。

匹配滤波的第2个步骤包括滤波器的生成和频域相乘运算。对于1个匹配滤波器,只需知道它的几个参数即可确定它,在并行处理环境下,匹配滤波器的生成有两种方式:一是在主机上计算出滤波器的数值,然后将滤波器数据传给并行计算设备GPU,这个过程会消耗通信时间;二是在每个并行节点上计算出滤波器的数值,但由于匹配滤波器对于各个距离线而言都是相同的,因此这种方法存在着大量的重复计算。由于GPU在并行计算过程中,每个计算结点的运算速度要远低于主机处理速度,因此本文中滤波器的产生采用第一种方式。

为了有效抑制距离压缩后数据的旁瓣值,匹配滤波器在产生后还应加窗,通常采用的窗函数有泰勒窗、余弦窗等[5]。对整个回波进行频域相乘的过程如图1所示, 整个回波数据沿着方位向逐次进行相乘,实际上是每个距离线与参考函数进行对应位置相乘,由于每个距离线的处理之间相互独立也不存在数据交互,因此可分别由不同的处理节点同时处理。

以上过程在进行并行处理时,存在着2种不同层次的并行策略,它们的并行度不同。一种是数组级的并行,即将原始数据沿着方位向划分为Na个数组,每个数组大小为Nr×1,此时每个数组可分配给待处理的各个计算节点,可同时处理,因此这种并行策略的并行度为Na。但每个节点内部在进行数组元素相乘时,仍需采用串行处理,此时并行处理单元为一条条距离线。通过进一步分析可以发现,并行处理单元仍然可以加以细化,如图1所示,如果将SAR数据中的每个元素视为并行处理粒度,那么频域相乘可以理解为每个元素同时与参考函数中对应元素相乘,这是因为每个元素的相乘运算是相互独立的。与第一种并行策略相比,这种情况下的并行度提高了Nr倍,即并行度为Nr×Na。但与此同时,在访问参考函数时,每个并行计算节点之间的寻址冲突也更加剧烈,因此与第一种并行策略相比,它带来的加速比的提升倍数实际上远达不到Nr。

RD算法的距离徙动校正通常在距离多普勒域实现,这是因为最近距离相同的一组目标在该域下具有相同的能量轨迹即目标响应曲线,每次RCMC操作可以校正某一方位处理块中的一组目标,大大提高了处理效率。但由于它的插值实现会导致RCMC在整个算法中占据了很大一部分的计算开销。

RCMC插值函数的生成和使用要考虑3个因素:插值核长度、偏移量和系数值。基于效率考虑,本文算法所采用的插值核长度为8,通常8点插值函数已能满足精度要求。将SAR原始数据变换至方位频域后,每个点由于距离徙动所造成的偏移量主要由两部分组成:距离走动和距离弯曲。在计算出每个点对应的偏移量后,就可以选择适当的插值核拟合出每个点偏移前所对应的值,本文选用的插值核为sin c函数。对位于第i个距离单元、第k条距离线上的点,假设它的偏移量为ΔR,则插值过程如下:

undefined

通过式(2)可以发现,任一距离单元上点校正后的值可以通过邻近8个距离单元数据获取,与方位脉冲无关。因此距离徙动校正过程也存在着两种不同层次的并行策略:一是处理粒度为每条距离线;二是处理粒度为数据中每个点,但由于一次结果的获取要通过邻近8个数据点,为了确保所有点校正结果的正确性,原始数据一定不能被覆盖,在这种并行策略下,需要在并行计算设备中另开辟一个大的内存空间,用于存储每个数据点校正后的值。

方位向脉压处理与距离向类似,并行度具有对应关系。对于距离向点数为Nr,方位向点数为Na的数据,通过以上分析,总结出RD算法中各个功能模块的并行度及处理粒度见表1所示。处理粒度指各个计算节点在并行处理时对应的数据大小。

2 并行RD算法的GPU实现

从上节的分析可知,RD算法中各个模块的并行度不尽相同,但都具有很高的并行性。为了充分利用算法本身中的高并行度以实现实时成像,并行计算设备GPU必须能提供对应的高并行机制。GPU的硬件构造不同于CPU,当进行并行处理时,它可以作为协处理器能够同时执行大量并行线程[6]。因此GPU内部可同时存在的线程总数决定了它可支持算法的并行度上限。

并行开发环境CUDA提供了2种不同层次的线程总数:物理线程总数和逻辑线程总数。以本文使用的GPU设备GTX260为例,其内部SM(Streaming Multiprocessor)总数为27,在进行线程映射时,每个SM内部最多可包含768个线程,因此这种型号的GPU可容纳的物理线程总数为N=27×768=20 736个。实际上在大型科学计算中,如此数量的线程总数也远远不足,尤其是对于并行度非常高的问题求解,实际在软件环境中,GPU的线程是以网格和线程块来进行组织的,一个网格中可以包含多个线程块,同样以GTX260为例,网格的最大维数为65 535×65 535,即一个网格中可以存在65 535×65 535个线程块,而每个线程块最多可以容纳512个线程,因此,逻辑线程总数为2 198 956 147 200个,这种情况下的线程总数基本上可以满足大多数问题的求解。

通过上面分析可知,GPU完全符合RD算法高并行性的要求。为了将算法映射至GPU中,并行度不同的各个模块需要不同的线程总数,线程组织结构也不相同。因此在实现过程中,需要编写不同的内核函数以适应不同的并行度。由于SAR原始数据以二维形式存储,总会存在某一维之间数据地址不连续的情况,并行FFT或IFFT变换要求各个数组之间地址连续,因此数据矩阵中各个列之间显然不满足要求。为了解决这个矛盾,在进行方位脉压之前,还需对回波数据矩阵进行并行转置,以适应上述要求。因此,转置算法成为整个并行算法中的一个重点和难点,如果采用常规的串行转置算法,那么仅转置运算所带来的消耗将会在整个算法中占据很大的比例,为此必须设计新的并行转置算法。

为了使转置算法的时间消耗达到最小,并行度必须达到最大。对于尺寸为Nr×Na的矩阵,最小数据粒度可以为每个元素,考虑采用并行度为Nr×Na的并行转置算法。由于矩阵中第(i,j)个元素转置存储后位置变为(j,i),因此转置过程可以简单地理解为多次赋值,即将原矩阵元素的值赋予转置后矩阵中对应元素。为了实现并行过程,创建Nr×Na个线程,每个线程仅负责一次对应元素的赋值过程。

3 实验结果及分析

由于GPU并行计算采用的是主从模式,即算法中串行部分在主机即CPU运行,并行部分以内核为单位在GPU上完成计算。在整个成像实验中,GPU一直扮演着协处理器的角色,因此本次实验中,除了GPU参数外,还需详细说明主机参数。具体参数见表2所示。

GPU成像实验结果如表3所示,其中成像数据大小为4 096×2 048,各模块结果来自于多次统计平均获得。表3中并行时间是指RD算法中某一功能模块通过并行化后在GPU上的运行时间;串行时间是指模块在主机上的串行执行所消耗时间。

除了表3中3个模块外,整个成像算法还包括一些无法并行化的运算,例如读取数据、数据格式转换和量化显示等,这些串行运算的时间开销为1.937 s,在主机和GPU上运行时间相同。除了表3中列出模块外,GPU运算还包括一次矩阵转置,利用本文设计的并行矩阵转置算法,在用标准C语言函数测量转置的时间开销时,一次转置的时间开销小于最小精度,接近于零开销。

从实验结果可以看出,GPU带来加速比的提升还是非常可观的,尽管并行效率低下,但由于GPU线程属于轻量级线程,因此依靠并行度和线程数量来获取高的加速比是可行的。将表3中各模块与程序中无法并行化的部分的时间开销求和,发现串行情况下总时间为29.422 s,GPU可并部分执行时间与无法并行部分时间和为2.519 s(其中包括数据传输时间开销0.457 s),由于2.519<2 048/476=4.3,其中PRF=476,所以GPU成像满足实时性要求。

4 结束语

本文提出了一种基于数据划分的SAR并行成像方案,该方案结合了RD算法高并行性的特点及GPU的计算处理能力,能大幅度减少成像时间;同时该方案是通过并行处理以实现实时成像,不以损失分辨率或精度为代价;最后由于GPU造价较便宜,能大量减少硬件成本,因此本文提出的实时成像方案在工程应用中具有重要意义。

摘要：结合RD成像算法的特点和GPU的计算处理能力,提出了一种具有高并行度的机载SAR实时并行成像处理方案。对实测数据进行成像处理的结果表明,本文提出的方案能够在不损失分辨率及成像精度的基础上,满足实时处理的要求,同时与传统实时成像处理系统相比较,能够大幅度的降低硬件成本。

关键词：RD,SAR,GPU,实时,并行

参考文献

[1]吕守业,龙腾.机载合成孔径雷达实时成像处理系统研究[J].北京理工大学学报,2005,25(2):155-58.

[2]唐月生,邓海涛,张长耀,等.机载SAR实时处理系统设计[J].遥感技术与应用,2005,20(1):81-84.

[3]SIMON-KLAR C,FRIEBE L,KLOOS H,et al.A multi DSPboard for real time SAR processing using the HiPAR-DSP 16[C]//Proceedings of2002 IEEE International Geoscience andRemote Sensing Symposium,June 24-28,2002,Hanover,Germany,2002:1-3.

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

[5]吴顺君,梅晓春.雷达信号处理和数据处理技术[M].北京:电子工业出版社,2008.

并行处理技术 篇9

20世纪60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展导致了并行计算机的出现，这一时期的并行计算机多是有一定规模的所谓大型主机(mainframe)。而并行机的应用以数值计算为主，并行算法的研究也以经典的数值并行算法(如快速傅里叶变换等)为主。创建和应用并行计算是解决单处理器速度瓶颈的最好方法之一。而并行计算的硬件平台是并行计算机，由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。

并行计算的现今研究状况:并行计算的研究面很广，主要包括了并行计算的硬件平台(即并行计算机)、并行计算的软件支撑(即并行程序设计)、并行计算的理论基础(即并行算法)以及并行计算的具体应用。本文设计了双DSP并行处理平台，并通过设计并行遗传算法在双DSP(DM6467)上运行实现，结果表明并行平台效率相对于PC机和单DSP效率上具有更快的速度，更低的频率更少的功耗。

1 并行化的硬件设计

整个并行处理平台硬件部分需要完成的任务是:通过图像采集模块将外界图像采集到系统内部，然后利用图像解码模块将得到的图像模拟信号转换为数字信号，接着图像处理模块将数字图像信号送入图像预处理模块进行预处理并存储，最后将处理后的图像信号读入并行处理系统对其进行并行处理。

由于系统中要处理的图像数据的数据量非常大，因此，系统采用Serial Rapid I/O(SRIO)作为FP-GA与DSP、DSP与DSP之间的数据通信总线，它的传输速率可以达到3.125Gbps，可以达到系统对处理芯片间高速传输数据的要求。系统中还应该要设计电源、时钟、复位电路为系统提供能源、时钟和复位信号，同时还需要配置电路方便程序的下载和调试。并行处理系统的平台整体结构如图1所示。

1.1 图像采集

图像采集是整个系统的传感器部分，是整个视觉系统的“双眼”，它完成了外界图像向图像信号的转换，只有选取合适的成像设备才能使视频采集模块功能完备，才可以使输出的图像信号达到要求。

1.2 图像解编码

因为采集到的是模拟信号，需要对其进行模数转换。CCD输出的信号中不仅包含图像信号，而且还包括了场同步信号、行同步信号、行消隐信号、场消隐信号、槽脉冲信号、后均衡脉冲、前均衡脉冲等多种信号干扰的信号，所以，需要把收到的信号进行必要的分离，得到完整的图像信号，并对其进行解码。又因为要将DSP处理过的数字信号转化为外界可以识别的模拟信号，所以后面又要进行数模的转换。系统选用H.264完成图像的模拟数字的转换，并向FPGA输送。H.264能够提供转化后的连续的、流畅的高质量图像数据，能够防止在不稳定的网络环境下容易发生的丢包等错误，以及提供了不同的网络段上的传输，并且能够提供很高的数据压缩比率，这样将大大节省用户使用时的下载时间。

1.3 FPGA模块

FPGA是对图像进行预处理模块，因此摄像头采集图像后，经过A/D转换，并将其结果交给FPGA模块，FPGA模块对其图像数据进行预处理。图像预处理模块会对图像进行中值滤波，边缘检测处理，并把处理过后的数据交给SDRAM进行存储。FP-GA在系统中有作为数据流调度中心的作用和协处理器的作用，能够将图像采集显示地址进行生成，并且实现图像的预处理，还将图像数据的显示格式进行变换，并将其交给DSP中进行处理。

1.4 SDRAM

由于考虑到TMS320DM6467内部的存储空间非常有限，同时由于DSP在进行图像处理时需要很大的数据交换空间，所以用256MB的SDRAM存储器来作为系统的内存的方法来配合TMS320DM6467进行高速处理工作。

1.5 并行处理

双DSP之间的高效通信方式是为了确保数字图像处理系统的性能的重要指标。使双DSP之间的通信正常，系统的工作状态也就得到了保证，系统的实时性要求也就得到了实现。在系统设计时，采用了SRIO的数据方式进行传输。Serial Rapid I/O是一种高带宽系统级互连总线，基于高性能包交换的互连技术，主要应用于系统内部互连，板到板或芯片到芯片间的通信。

SRIO的数据传输和DMA传输是结合的，SRIO的数据包有效载荷为256字节，每个信息由多达16个数据包构成。每一个数据包传送完成后会发出请求，以便DMA将数据搬移到内存中。

2 并行化的软件设计

为验证并行处理系统的性能，以并行遗传算法做测试平台，通过求解TSP问题的遗传算法来对不同平台的运行效率进行比较。设计一个简单的TSP问题。TSP问题描述如:求一条遍历所有已经确定过的若干目的地的最短路径。用数学语言描述:设有n个目的地的集合D={D1,D2，…，Dn}，其中任意2个目的地之间的距离为dij，求一条一次仅且一次经过D中所有目的地的闭合路径，使得这个闭合路径为最小。

2.1 基因的编码和种群的初始化

2.1.1 基因的编码

对于TSP问题，通过目的地的先后顺序就是问题的解，可以对目的地先进行编号，采用十进制方法表示∧=(u1,u2,u3，…，un-1,un)=(x1,y1,x2,y2，…，xn,yn)，式子中，∧为染色体;uj为基因，uj=j,j=1,2,3…，n;xi,yi分别代表第i个基因的横坐标和纵坐标，i=1,2,3，…，n;且有0≤xi≤500,0≤yi≤500[3]。

2.1.2 种群初始化

种群初始化，通过随机抽取每个染色体中的各个基因，生成一条初始路径:

Pi=(u9,u1,un-3,u2，…，u6,u14),Pi代表第i个种群，i=1,2,3，…，n。

2.2 适应度

对群体中的每个染色体计算适应度值，值越高，染色体的解就更可取。适应度值以巡游目的地的总长度的倒数来决定，总长度倒数越大则适应度值就越高。

2.3 赌轮选择法

类似常见的抽奖活动中的转盘。盘上的扇形块越大，中奖的概率也就越大。比如，一代中有m个染色体，则盘被分为m个块。每个块的大小根据每个染色体的适应度值来决定。算法如下:

随机取一个数，范围在所有适应性分数的总和之内

将前j个染色体的适应性分数进行叠加，当大于随机取的数时跳出循环;

}

当前的第j个染色体为选中的染色体

2.4 杂交算法

杂交算法有很多种，比如变位杂交，交点杂交，顺序杂交，这里采用OX杂交法。

2.5 变异算法

采用交换变异，假设对新产生的子代(3,4,6,5,0,2,1,7)进行变异，随机取第2位和第4位，交换位置，成为(3,5,6,4,0,2,1,7)即可。

2.6 最优染色体选择

为了使遗传算法较快地收敛，在每一代中可以按一定比例选择适应性最高的染色体直接复制到下一代:BestPathin=best(Pi)n,i=1,2,3，…，n,BestPathin代表从第i个种群中读取n个最优个体，Pi代表第i个种群;Pi经过变异，交叉，适应值选择后，BestPathin复制到子代Pi中。本文是遗传算法在双DSP系统的DM6467上执行，DM6467内部结构如图2所示。

Core 0产生初始种群Pi，然后存储于共享内存DDR2的中，Core1与Core2从共享内存中复制初始种群Pi存放于各自芯片的SDRAM中。Core0通过SRIO将初始种群Pi发送给DSP-2的Core0,Core0将初始种群Pi存储于DDR2中，Core1与Core2再从共享内存中复制初始种群Pi存放于各自芯片的SDRAM中。

每个Core通过初始种群计算适应度值，通过交叉，变异，赌轮选择法选择出最优的染色体集BestPathin。每迭代4代，两个芯片分别将最优染色体集BestPathin存储于共享内存DDR2中，然后通过SRIO将最优染色体集发送到对方的共享内存DDR2中，将这个最优染色体集合，直接拷贝到每个Core下一代的子代中。迭代n次后，6个核分别得到各自的最优解。然而通过最优解的不断交换，它们的最优解大致上相同。

3 实验

实验的执行条件:群体规模100，交叉概率为0.70，变异概率为0.04，分别将目的地数取30,40,50进行测试。通过实验，在不同的硬件平台运行算法，收集不同平台上算法的运行时间，运行时间的数据都是经过20次测试得出的平均结果。如表1所示。

通过实验，得出图3是种群的相异度变化，从图中可以看出种群的相异度保持的比较好，种群不断发现新的模式，增加最优个体出现的概率，避免种群陷入局部最优。

通过实验，得出种群在进化过程中最大适应度的变化图，可以清楚得出相同的实验条件，不同的硬件平台下，最大适应度的收敛速度。图4是目的数为30时，单DSP和双DSP(DM6467)达到的最大适应度的收敛图，图5是目的数为40时，单DSP和双DSP(DM6467)达到的最大适应度的收敛图，图6是目的数为50时，单DSP和双DSP(DM6467)达到的最大适应度的收敛图(纵坐标为最优距离的倒数，横坐标为迭代数)。

4 结束语

本文设计了一种双DSP并行处理图像数据的硬件系统，为测试平台性能，设计了并行遗传算法求解TSP问题，实验表明，并行的DSP(DM6467)硬件平台在算法的运行效率上比单DSP和PC机的运行效率高，收敛速度快，并行平台遗传算法种群相异度保持较好。因此，并行的DM6467硬件平台处理数据的能力强，系统有明显的优越性。

参考文献

[1]陈国良.并行算法的设计与分析[M].北京:高等教育出版社,2002

[2]陈国良,孙广中,徐云,等.并行计算的一体化研究现状与发展趋势[J].科学通报,2009,54(8):1043-1049.

[3]马庆雷.基于遗传算法的公路平面优化[J].中国公路学报,2006(1):1-19.

[4]章奇.基于DSP+FPGA架构视频处理系统设计及实现[D].西安:中国科学院西安光学精密机械研究所,2006.

[5]马庆雷.基于遗传算法的公路平面优化[J].中国公路学报,2006(1):1-19.

[6]周晓亮.基于DSP的数字视频图像获取与处理技术研究[D].湖北:华中科技大学,2004-4:1-3.

[7]田耘,徐文波,胡彬,等.Xilinx ISE Design Suite 10.x FPGA开发指南-逻辑设计篇[M].北京:人民邮电出版社,2008.

[8]Asanovic K,Bodik R,James J,et al.The landscape of parallel computing research:A view from Berkeley[R].Technical Report,Electrical Engineering and Computer Sciences,University of California,Berkeley.2006.

[9]王鹏,吕爽,聂治,等.并行计算应用及其实战[J].机械工业出版社,2009(1):25-45.