基于OpenMP的包络对齐并行方法研究与实现＊

张佳佳，姜卫东，李 宽

（1.国防科学技术大学电子科学与工程学院，湖南 长沙410073；2.国防科学技术大学计算机学院，湖南 长沙410073）

1 引言

在逆合成孔径雷达（ISAR）成像中，包络对齐是决定成像质量的关键技术。包络对齐的经典算法有最大互相关法［1～3］、最小熵法［4］、峰值最大法，最大互相关法包括相邻互相关法［1］、积累互相关法［2］以及整体互相关法［3］。积累互相关法和最小熵法性能较好，然而两者对齐精度直接受限于雷达距离分辨单元。超分辨技术［5］可以提高距离分辨率，但是该方法需要足够的信噪比，工程上难于实现。而巧妙利用Fourier变换的频域移位性质，可以缩短包络对齐处理步长，有效减小一维距离像对齐误差［6］。

本文采用加矩形窗的积累互相关法获得粗对齐包络，而后基于频移因子利用最小熵准则调整对齐结果。一般ISAR 成像原始回波数据量大，互相关法和最小熵法计算量都很大，在序列成像、实时成像等条件下对计算资源是一大挑战。为提高包络对齐速度，文献中出现多种方案：基于GPU 的最 小 熵 包 络 对 齐 法［7］、FPGA 加 多 片 单 核DSP 的ISAR 实时成像［8］、基于多核DSP的信号处理平台减少对齐时间［9］等硬件处理手段，但是硬件优化结构研制和改进周期长、费用高昂且维护不便。

针对上述问题，考虑到CPU 计算性能飞速提升以及多核处理器的广泛应用，本文提出基于OpenMP（Open Multi－Processing）［10］共享存储的包络对齐优化算法，分别将互相关法和最小熵法划分为多个独立任务，利用OpenMP 将各任务映射到不同线程中并行执行，充分利用多核处理器资源，提高程序运行效率。实验结果显示，并行算法加速效果明显，加速效率最高可达98%，并且该方法无需额外硬件支持，费用低廉，易于实现。

2 包络对齐算法

逆合成孔径雷达成像经典算法为距离－多普勒（R－D）成像算法，包含三个步骤：距离压缩、运动补偿和方位压缩，运动补偿又由包络对齐和相位补偿组成。R－D 算法如图1所示。

Figure 1 Range－Doppler algorithm图1 ISAR 成像距离－多普勒算法

由图1知，包络对齐的前提是原始回波的距离压缩，其实质为对每个脉冲回波进行FFT 获得相应的一维距离像。而由于目标相对于雷达的平动，距离像之间出现未对齐现象。本文包络对齐分两步：加矩形窗的积累互相关对齐和基于频移因子的最小熵对齐。

加矩形窗的积累互相关算法中，参考包络是窗长的已对齐包络的加权和产生的合成包络（此处为矩形窗加权，即权值都为1，窗长尽可能大）。本文对参考包络和待对齐包络分别进行FFT 处理，FFT 结果相乘，之后进行IFFT 处理获得粗对齐一维距离像，如图2所示。

Figure 2 Accumulated cross correlation algorithm based on rectangular window图2 加矩形窗的积累互相关包络对齐法

基于频移因子的最小熵法以积累互相关得出的每次回波的对齐偏移量τi为中心，在［τi－Δτ，τi＋Δτ］ 内 求 得L个 频 移 因 子 exp（j2πτilΔfnTs）（Δf为FFT 频谱分辨单元，Ts为脉内采样周期），与该次回波si（）n相乘，然后依据最小熵准则调整互相关对齐精度，如图3所示。

Figure 3 Minimum entropy range alignment algorithm based on frequency shifting property图3 基于频移因子的最小熵包络对齐法

3 包络对齐并行策略

3.1 OpenMP简介

OpenMP［11］是共享存储多核处理器编写并行程序的一套编程接口，由环境变量、编译制导指令以及支持它的函数库组成。OpenMP 并行执行模型为分叉－合并（Fork－Join）模式（如图4所示）：程序开始时，主线程串行执行；遇到派生点后，主线程创建并行线程队列，执行并行区代码；并行代码执行完毕，派生线程挂起或退出，由主线程继续执行串行程序，直到遇到下一个派生点。

Figure 4 Fork－Join pattern of OpenMP图4 OpenMP分叉－合并模型

使用OpenMP 开发并行程序简单且通用性强，无需关注并行化细节。在源代码中加入合适的＃pragma编译指导指令，编译器自动并行化程序。OpenMP与编译器无关，开发平台不支持OpenMP时，编译器自动忽略＃pragma指令，程序转为串行代码顺序编译并正常运行。

3.2 包络对齐的并行设计思想

包络对齐数据流为二维矩阵，算法以距离像包络为单位循环执行对齐任务。因此，本文主要是对循环部分进行并行化设计，研究带有循环结构的大数据量计算的并行方法时，首先分析计算数据之间的相关性，然后讨论计算执行时的数据划分方法，最后进行必要的调整。

原始回波数据矩阵由回波个数和回波采样点数组成，一般回波个数和采样点数都较大。距离压缩时各个脉冲回波相互独立，循环对每个回波进行FFT 处理，因此只需在循环外直接使用OpenMP指令即可有效实现程序并行优化。包络对齐基于相邻脉冲回波的强相关性，当前回波的参考信号依赖前面矩形窗长的已对齐回波距离像包络，但是与矩形窗外回波相关性较小，而且脉冲回波数目远远大于矩形窗内回波数目，因此，本文提出依据处理器核数对回波数据进行均匀分块，每块回波数目远大于窗长，能够大大消除数据块间的相关性。同时，为保证对齐质量，本文提出由第一块待对齐数据获得的参考信号作为其它各块待对齐回波的参考距离像。因此，本文在多核处理器上进行数据分块并行执行包络对齐任务，既保证对齐质量，又提高对齐速度。

3.3 距离压缩并行方法

由于原始回波数目大，各次回波循环执行FFT，OpenMP利用函数omp＿set＿num＿threads（）设置线程数目，编译指导指令＃pragma omp for直接作用于循环语句，程序即自动依照线程数目并行执行循环运算，有效减少距离压缩时间且实现简单。

3.4 加矩形窗的积累互相关并行方法

积累互相关包络对齐是每个待对齐一维距离像与参考距离像进行互相关得到粗对齐一维距离像。首先，根据处理器核数n，将待对齐数据顺序均匀分成n块，利用OpenMP 编译指导指令＃pragma omp section将各块数据分配到各线程，每个线程参考包络都使用第一块数据获得的参考包络以保证对齐质量。整个并行互相关运算就是各块待对齐数据分别与参考包络在各线程中并行执行互相关，执行结果合并即为粗对齐一维距离像，并行过程如图5所示。

3.5 基于频移因子的最小熵并行方法

Figure 5 Parallel accumulated cross correlation algorithm图5 积累互相关并行方法

该模块依据处理器核数n，将粗对齐数据均匀分为n块，第一块数据计算得到参考距离像作为其它各块数据的参考包络，利用OpenMP 编译指导指令＃pragma omp section自动将各块数据与参考数据分配到各线程，并行执行基于频移因子的最小熵运算，并行过程如图6所示。此时，各数据块的数据量基本相同，运算量相当，因此各线程负载均衡，并行执行效率高。

Figure 6 Parallel minimum entropy algorithm图6 最小熵并行方法

4 实验性能评测与结果分析

4.1 实验性能评测标准

为方便描述并行性能，采用传统的加速比和效率性能评价标准。加速比定义为：

其中，Ts是串行算法单线程运行时间，Tp是并行算法在多核处理器上用P个核并行处理运行时间。

效率定义为：

其中，P为处理器核数。相同线程下加速比越大，并行效率越高，则并行程序性能越好。

4.2 算法并行效率理论分析

本文包络对齐并行方法为依据线程数目n对各算法输入数据进行分块处理，即输入数据分为n块共同执行各处理算法，故而理论上各算法并行执行时间为串行程序耗时的1/n倍，加速比达到n，并行效率高达100%。但是，由于算法程序无法完全并行化、计算机性能的影响以及多核处理器共享内存访问带宽增大访问开销，导致并行效率无法达到理论数值，后续工作应该尽可能减少抢占内存资源带来的访问开销。

4.3 实验结果

本文使用Microsoft Visual Studio 2010开发工具，采用OpenMP 并行编程接口设计并行优化程序。仿真实验平台为八核处理器Intel（R）Core（TM）i7－4770CPU ＠3.40GHz，16GB内存，64位操作系统。实验数据为1 024×1 001的雷达回波数据，即单脉冲采样点数1 024点，脉冲回波个数为1 001个，数据大小为7 104KB。

实验分为距离压缩和包络对齐两部分。为提高对齐精度，包络对齐分两个模块：积累互相关对齐模块和最小熵对齐模块。因此，距离压缩、互相关法和最小熵法为三个独立模块，包络对齐是互相关法与最小熵法的整体执行效果。文中用单线程以及2、4、6、8个线程分别进行程序性能优化处理，为了得到更直观的视觉效果，四个模块的执行时间、加速比及并行效率用折线图表示，如图7～图9所示。

Figure 7 Execution time of the serial and parallel algorithms图7 各算法模块串行、并行执行时间（ms）

由图7可知，包络对齐法执行时间略大于互相关模块和最小熵模块运算时间的总和，完全符合互相关法和最小熵法共同执行得到对齐包络的事实。距离压缩、互相关对齐和最小熵对齐模块中，相同线程数目下，距离压缩处理耗时最少，最小熵法计算量最大，且随着线程数目增加，各模块执行时间逐渐减少，有效提高成像速度。

图8显示，随着线程数目增加，各模块加速比逐渐增大。相同线程数目下进行程序优化处理时，最小熵法加速比最大，这是因为最小熵对齐运算量最大，耗时最长，因此多线程性能优化最好。但是，包络对齐加速比反而小于最小熵模块加速比，这是因为互相关包络对齐法运算复杂，多线程并行优化性能较差，抑制包络对齐整体优化性能。

Figure 8 Speed－up of the four algorithms图8 各算法模块加速比

图9为多线程并行优化效率，并行线程数目较少时，并行效率高达95%以上，随着线程数目增加，优化效率降低，甚至八线程互相关并行效率降到50%以下，综合图7和图8内容，随着线程个数达到一定数目，程序执行时间减小速度下降且加速比增大速度降低，这是由于OpenMP 是基于共享存储的并行编程模型，多核处理器共享内存访问带宽，线程过多会抢占带宽资源，增大内存访问开销。但是，最小熵模块的八线程并行效率依然在60%以上，而且最小熵法各线程并行效率和加速比都高于其他模块，这是因为最小熵处理计算量大，并行性能优化空间大，即耗时长的程序比耗时短的程序优化效果更明显。然而，尽管互相关法加速比不高，并行效率低，但是相对于最小熵方法，其执行时间较短，故而综合积累互相关对齐和最小熵对齐的并行效果，包络对齐整体优化性能较好。因此，多线程并行算法并不是线程越多越好，要根据数据量、算法计算量以及算法复杂程度选择适当的线程数目进行并行优化。

Figure 9 Parallel efficiency of the four algorithms图9 各算法模块并行效率

5 结束语

本文设计了基于OpenMP的包络对齐并行方法，在多核处理器上对程序进行多线程并行优化。从减少程序执行时间和保证对齐质量着手，对计算数据分块，各块数据并行执行对齐任务。仿真实验结果表明，包络对齐的多线程并行处理有效缩短对齐时间，提高一维距离成像速度，为ISAR 成像的实时性提供条件。

本文是在多核处理器上进行包络对齐并行优化研究，在未来的工作中，针对雷达处理上的多种复杂算法，考虑使用消息传递机制MPI实现多机并行优化，以及使用GPU（CUDA）实现异构加速。

［1］ Chen C C，Andrews H C.Target－motion－induced radar imaging［J］.IEEE Transactions on Aerospace Electronic Systems，1980，16（1）：2－14.

［2］ Delisle G Y，Wu H Q.Moving target imaging and trajectory computation using ISAR［J］.IEEE Transactions on Aerospace Electronic Systems，1994，30（3）：887－899.

［3］ Xing Meng－dao，Bao Zheng，Zheng Yi－ming.Rang alignment using global optimization criterion in ISAR imaging［J］.Acta Electronic Sinica，2001，29（12A）：1807－1811.（in Chinese）

［4］ Wang Gen－yuan，Bao Zheng.The minimum entropy criterion of range alignment in ISAR motion Compensation［C］∥Proc of Conference Radar，1997：236－239.

［5］ Wang Kun，Luo Lin，Bao Zheng.Using super resolution technique improve range alignment accuracy of ISAR imaging［J］.Journal of Xidian University，1997，24（Supp）：109－115.（in Chinese）

［6］ Liu Ai－fang，Li Yu－sheng，Zhu Xiao－hua.ISAR range alignment using improved envelope minimum entropy algorithm［J］.Journal of Signal Processing，2005，21（1）：49－51.（in Chinese）

［7］ Shi Xin－liang，Xie Xiao－chun.GPU acceleration of range alignment based on minimum entropy criterion［C］∥Proc of IET International Radar Conference 2013，2013：1－4.

［8］ Yang Jian，Du Lin－lin，Xin Yu－lin，et al.Real－time ISAR imaging of multilevel parallel processing based on R－D method［J］.Journal of Astronautics，2010，31（5）：1427－1432.（in Chinese）

［9］ Guo Rui，Zhang Yue，Sun Gang，et al.Research on ISAR real－time imaging technology using multicore DSP［J］.Journal of Signal Processing，2013，29（9）：1238－1243.（in Chinese）

［10］ OpenMP application program interface version 3.0［EB/OL］.［2010－10－10］.http：//www.openmp.org/mp－documents/spec30.pdf.

［11］ Cai Jia－jia，Li Ming－shi，Zheng Feng.OpenMP－based parallel computation on multi－core PC［J］.Computer Technology and Development，2007，17（10）：88－91.（in Chinese）

附中文参考文献：

［3］ 邢孟道，保铮，郑义明.用整体最优准则实现ISAR 成像的包络对齐［J］.电子学报，2001，29（12A）：1807－1811.

［5］ 王琨，罗琳，保铮.应用超分辨技术提高逆合成孔径雷达成像包络对齐精度［J］.西安电子科技大学学报，1997，24（增刊）：109－115.

［6］ 刘爱芳，李彧晟，朱晓华.用改进的包络最小熵法进行包络对齐［J］.信号处理，2005，21（1）：49－51.

［8］ 杨剑，杜琳，辛玉林，等.基于多级并行处理的R－D 方法的ISAR 实时成像［J］.宇航学报，2010，31（5）：1427－1432.

［9］ 郭瑞，张月，孙刚，等.多核DSP上的ISAR 实时成像技术研究［J］.信号处理，2013，29（9）：1238－1243.

［11］ 蔡佳佳，李名世，郑锋.多核微机基于OpenMP的并行计算［J］.计算机技术与发展，2007，17（10）：88－91.