高性能SAR成像程序的并行粒度选择技术
开篇：润墨网以专业的文秘视角，为您筛选了一篇高性能SAR成像程序的并行粒度选择技术范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
收稿日期:2011-03-03;修回日期:2011-04-27。
基金项目:国家973计划项目（613900103）;中国博士后科学基金资助项目（20090451525）。
作者简介:杜静（1979-）,女,山西晋中人,助理研究员,博士,主要研究方向:高性能计算、并行仿真; 敖富江（1975-）,男,河南信阳人,高级工程师,博士,主要研究方向:复杂系统仿真; 王华兵（1979-）,男,云南陆良人,工程师,硕士研究生,主要研究方向:雷达电子战仿真;汪连栋（1966-）,男,天津宝坻人,研究员,博士,主要研究方向:电子对抗仿真试验与评估。
文章编号:1001-9081（2011）08-02079-04doi:10.3724/SP.J.1087.2011.02079
（63880部队 博士后科研工作站,河南 洛阳471003）
（.cn）
摘 要:高性能并行仿真程序必须采用针对性的并行优化技术以获得高效的性能加速。而根据程序特性，确定适合的并行粒度是设计并行优化技术的基础。因此，以典型合成孔径雷达（sar）成像程序――距离―多普勒（RD）程序为代表，研究了高性能SAR成像程序的并行粒度选择技术，重点针对并行粒度的基本准则和RD算法的并行粒度选择方法进行了研究。实验结果证明，经过并行粒度优化选择的SAR成像程序能够获得显著的性能提升，并且具有良好的可扩展性。
关键词:合成孔径雷达成像程序；并行粒度；并行度；并行开销；滑动窗口
中图分类号: TP391.413; TP301.6文献标志码:A
Parallel granularity selection technique for high performance SAR imaging program
DU Jing, AO Fu-jiang, WANG Hua-bin, WANG Lian-dong
（Postdoctoral Scientific Research Workstation, Unit 63880, Luoyang Henan 471003, China）
Abstract: High performance parallel simulation programs need adopt parallel optimizing techniques to achieve efficient performance acceleration. And achieving appropriate parallel granularity according to the characteristics of given program is the basis of parallel optimizing technique. Therefore, represented by a typical Synthetic Aperture Radar （SAR） imaging program, namely Range-Doppler （RD）, the authors researched into parallel granularity selection techniques for high performance SAR imaging programs. Especially, two important components were researched, including the basic rules of parallel granularity selection and the parallel granularity selection approach of RD algorithm. The experimental results show that according to the selected parallel granularity, the SAR imaging program can achieve obvious performance improvement and high scalability.
Key words: Synthetic Aperture Radar （SAR） imaging program; parallel granularity; parallel degree; parallel overhead; sliding window
0 引言
实时、高分辨率合成孔径雷达（Synthetic Aperture Radar, SAR）成像技术是当前仿真领域的热点研究问题。SAR成像处理具有庞大的数据量和运算量，通常需要十亿至百亿次的运算速度，该运算能力需求已远远超过了目前单CPU所能达到的程度［1-3］。在这种背景下，采用并行计算平台和并行优化技术是实现高性能SAR成像的必由之路。
在设计各种面向性能的并行优化技术之前，首先需要进行任务划分。就是在相关性分析的基础上，将原始串行程序划分成一组任务，并分配到不同的处理器并行执行，从而缩短程序运行时间。本文将划分后子任务的规模定义为该并行程序的并行粒度。并行粒度的大小直接影响到程序中并行度的多少和并行开销的大小。而并行算法设计的关键技术之一是尽可能获得最大的并行度和最小的并行开销，因此，控制并行粒度对于提高并行算法的性能至关重要。为此，本文以工作站机群为平台，以典型SAR成像程序――距离―多普勒（Range-Doppler，RD）程序为代表，研究了高性能SAR成像程序的并行粒度选择技术，重点针对并行粒度的基本准则和RD算法的并行粒度选择方法进行了研究。该项研究能够根据给定程序确定适合的并行粒度，为设计面向性能的并行优化技术提供易于优化的程序平台。
1 SAR成像算法
成熟的SAR成像算法主要包括RD算法、波数域算法和ChirpScaling算法［4-6］。其中，RD算法是现阶段应用最广且最成熟的成像算法之一，该算法简单有效，在机载合成孔径雷达成像中得到普遍应用。为了举例验证所研究的并行粒度选择技术，本文以典型的SAR成像算法――RD算法为代表，通过该算法的并行粒度选择过程来研究高性能仿真程序的普适性并行粒度选择技术。
RD算法利用雷达目标的回波信号可近似看成在距离向和方位向独立的线性调频信号的原理，在距离向和方位向分别进行匹配滤波，最终得到SAR的图像数据。该算法的主要特点是在距离―多普勒域通过插值来精确、高效地实现距离徙动校正。SAR成像并行计算技术目前在国内外都已经取得了初步成果。电子科技大学、中国科学院电子学研究所等单位分别在大规模并行计算机系统上实现了SAR成像算法［1,3,5］。然而现有的研究还存在很多不足之处。首先，现有的研究着重于特定体系结构下的并行算法，缺乏面向不同体系结构性能优势以及SAR成像应用特点的并行粒度划分技术研究，缺乏可扩展、可移植的SAR成像并行软件系统。其次，现有研究集中于单纯的并行化方法，没有研究如何将并行化结果集成到更广泛的应用范围和复杂的实际系统中。针对上述问题，本文深入研究典型SAR成像算法的特点和规律，提出控制并行粒度的基本准则，为开发更多高性能并行仿真程序提供可借鉴的并行粒度优化手段。
2 控制并行粒度的基本准则
并行粒度首先直接关系到并行任务数量的多少，其次在性能方面将影响到通信同步开销、负载平衡情况、调度开销以及并行度［7］。经过分析发现，若并行粒度过大则任务数量较少，虽然导致较小的任务调度开销以及通信开销，但是难以做到良好的负载平衡，并且较低的并行度难以充分开发大规模并行计算平台的并行能力。随着并行粒度的减小，任务数量也随之逐渐增多，受程序中固有数据依赖关系的制约将导致通信开销和调度开销显著增大；并且任务粒度的减小也将导致向处理器分配的单位负载的减少，小规模的单位负载更易于任务的分配和调度，因此，任务粒度的减小更有利于实现负载平衡，提高程序的并行度。当并行粒度过小时，任务数量急剧增多，导致庞大的任务调度开销和通信开销，虽然最易于实现负载平衡和获得很高的并行度，但复杂的程序关系导致程序性能很低。图1给出了随着并行粒度的变化，各性能指标的变化趋势示意图。可见，随着并行粒度的持续增大或者持续减小，都无法获得持续的性能提升。最佳的并行粒度应当在负载平衡、并行度、通信开销、调度开销之间权衡得失［8］，最终取得性能指标相互的折中。图2给出了随并行粒度变化的程序性能变化示意图，可以看出，随着并行粒度的变化，程序的性能变化曲线将会产生一个拐点，该拐点就是最优性能时的最佳并行粒度。
图1 各性能指标随并行粒度变化
图2 程序性能随并行粒度变化
然而，实际情况时大多数程序无法获得理论上的最佳并行粒度。这是因为以下三方面原因：首先，受并行粒度大小变化影响的性能指标虽然重点在于前述四种，但还存在一些其他因素，例如编程复杂性难以被完全捕获；其次，受程序中数据依赖关系的影响，所有性能指标随并行粒度的变化趋势并非连续函数，难以对其准确量化；再次，受程序语义和控制关系的影响，并行粒度的大小也并非能够连续选择，必须为一个完整的功能模块。因此，图2只是一个理想情况下的示意图，实际操作时，只能在可以选择的范围内确定一个近优并行粒度。确定近优并行粒度的基本准则包括两个方面。首先，需要考虑并行计算平台的性能优势，例如，若某并行计算平台具有高速通信网络，可以重点考虑负载平衡和并行度因素，将并行粒度尽可能划分得小一些。而对于数据并行程序，并行系统的负载平衡很容易达到，则需重点考虑通信和调度因素，尽可能将粒度划分得大一些。其次，需要考虑程序本身的特点。任务划分时，并行粒度不一定能连续控制，因此，需要根据程序的功能以及数据的组织方式，基于依赖分析技术，在可选择的粒度范围内确定合适的并行粒度。
3 确定RD算法的并行粒度
前面介绍了在任务划分的同时如何平衡地选取并行粒度的准则。基于该准则，本文对RD成像程序进行合理的任务划分，并确定适合的并行粒度，为进一步实施并行优化技术奠定基础。经过分析，RD成像程序适合采用数据并行方式，因此，RD成像程序需要依据输入数据――SAR原始回波数据进行任务划分。下面首先介绍RD程序的数据区域访问特征，然后提出RD算法的并行粒度选择方法。
3.1 数据区域的访问特征
RD成像程序的数据区域中最小功能完整的单位是一个孔径的数据，然而单孔径数据通常只能完成距离压缩，而不够数据量完成方位压缩，因此不能完成一次完整的RD成像。一次完整RD成像最少需要的孔径数据组合了一个滑动窗口，也就是说，成像是以滑动窗口为单位的。滑动窗口内对应的脉冲数据就是成像算法输出一幅完整的图像所输入的脉冲数据。滑动窗口的列数为脉冲采样点数；其行数缺省为两个孔径的脉冲数目。滑动窗口只在方位向上移动，移动至下一个位置所越过的脉冲数目称为滑动步长。滑动窗口不断在方位向上向前滑动，于是成像算法不断输出新的图像数据。由于滑动步长大小通常不等于滑动窗口的行数，因此相邻两个滑动窗口所对应的脉冲数据可能会有部分重叠。
3.2 RD算法的并行粒度选择
本节根据提出的确定并行粒度的基本准则，对RD算法进行并行粒度选择。依据准则，首先确定所运行并行平台是多机机群，通信开销是系统的瓶颈，因此，应当尽可能减少通信操作；其次，依据程序特性选择并行粒度，这是确定RD算法的并行粒度的主要准则。
RD成像程序的数据区域中最小功能完整的单位是一个孔径的数据，然而单孔径数据通常只能完成距离压缩，而不够数据量完成方位压缩，因此不能完成一次完整的RD成像。一次完整RD成像最少需要的孔径数据组合了一个滑动窗口，也就是说，成像是以滑动窗口为单位的。通过对RD成像程序的数据访问模式进行分析，可以发现若以滑动窗口为单位进行任务划分，并映射到不同节点上进行处理，则可以将一幅幅子图像（可成像的最小图像）在每个节点内部成像完毕；若将滑动窗口划分为细粒度任务（例如单孔径数据），并映射到不同节点上进行处理，则这些节点共同拥有成一幅子图像所需要的数据，将导致节点间频繁的数据通信，带来庞大的通信开销。因此，RD算法进行任务划分时，至少要以滑动窗口为单位。任务粒度选择也存在以下4种情况（由大到小）。
1）以文件为并行粒度。
SAR雷达在实际工作时，一个飞行架次可能要记录多个数据文件，每个数据文件对应一个成像条带，最后需要将所有文件进行SAR成像处理并合并输出一幅图像。数据文件通常会保存到一个或若干个磁盘阵列中。当同时需要处理多个文件时，可以考虑直接以文件为并行粒度进行任务划分，即将不同的数据文件分配给不同的节点执行成像任务。这是因为文件之间没有任何的数据相关性，可以完全并行，避免了成像节点之间的通信操作。这种方法思路简单，不存在重复的数据通信，适用于文件的数量超出系统中节点数量的情况，从而能够保证程序具有足够的并行度。但是本文没有采用这种任务划分方法，是因为当文件大小不一时，仍然可能存在负载不平衡的情况。并且由于一个文件只分配给一个节点且节点能力有限，无法及时输出单文件的图像，延缓了图像分析的过程。
2）以单个滑动窗口为并行粒度。
这是最简单直观的任务划分方法，如图3所示。该方法适合任何波段的数据。当波段改变带来庞大数据量时，仅仅增加了单孔径内部的脉冲数量，对滑动窗口的功能划分没有影响。相邻滑动窗口之间存在重叠区域，虽然该方法需要将重叠部分在数据节点和成像节点之间进行重复的数据通信，增加了部分通信开销和计算开销，但是若能够实现良好的计算与访存重叠，这部分开销不会对性能造成很大影响。并且该方法易于编程实现，因此，本文采用了这种并行粒度。
图3 一个滑动窗口为并行粒度
3）以多个滑动窗口为并行粒度。
相邻滑动窗口之间存在重叠区域，该区域的数据需要被冗余计算和重复通信，因此以相邻的多个窗口为任务，如图4所示，保证了这些窗口能够映射到同一节点，则可将冗余计算在节点内部完成。该方法既可以复用对重叠区域的计算结果，也能够减少节点间的绝对通信开销。然而，这种任务划分方法需要特定编程接口或硬件的支持，能够偏移访问磁盘中文件的任意位置，因此，制约了该种任务划分方法的使用。以本文的研究为例，由于实验采用的SAR原始采样数据具有一些特定的格式（需要使用某个特定的编码在文件中定位每个脉冲的数据采样起始位置），只能以顺序的方式读取数据文件，而无法随机读取文件，因此只能按顺序将较大的任务分配给各个成像节点，对于计算量相对不是太大并且读取速度较慢的情况，这种方法并不适用。
4）以二维数据矩阵的行/列为并行粒度。
RD成像处理的各个主要步骤，其实就是对一个二维数据矩阵（m行n列）进行不同操作的过程。下面以距离压缩为例进行说明，其他操作同理可得。
距离压缩需要对二维数据矩阵的m行数据分别进行相同的操作，可以采用数据并行的方式，将这m行数据平均分配给各个处理器。有两种策略：其一，在同一个节点上的不同处理器之间进行数据分配；其二，在不同节点间进行数据分配。显然前一种策略不涉及网络通信，通信延迟较小。第一种策略还能与上面讨论的以滑动窗口为并行粒度的方法很好地融合到一起。因此本文采取第一种策略。
综上所述，本文采用滑动窗口和二维数据矩阵的行/列两种并行粒度相结合的方式进行任务划分，这种方法符合多核工作站机群的特点，配合合理的任务映射和针对性的并行优化技术，应当可以收到良好的性能收益。
图4 三个滑动窗口为并行粒度
4 实验评测
本章介绍了SAR成像并行软件在多核工作站机群上的实验测试结果。通过实验评测和性能分析，验证了本文研究的并行粒度选择技术的有效性。
实验分别测试了RD成像程序的串行版本和多机的OpenMP+MPI混合版本的性能。这些版本分别以X、L波段SAR实测数据为输入。其中，完成一次成像迭代所需输入的原始回波数据量（采用float型存储），L波段的为2.93GB，X波段的为1.07GB，前者是后者的2.7倍。各软件版本都以VC2005作为开发环境，选择-O3优化开关。所运行的工作站机群详细的硬件参数如表1所示。MPI编程环境主要使用mpich2-1.2.1，某些测试还用到了mpich 1.2.5和intel MPI库3.1。
表1 测试平台参数
图5给出了X波段和L波段的并行程序的最大加速比测试结果。显然，并行程序能够获得有效的性能加速。X波段最大加速比能够达到7.28，L波段最大加速比能够达到11.01597。这说明，通过采用所设计的并行粒度选择技术，能够有效地发掘工作站机群的多层次并行能力，从而开发并行计算平台强大的计算能力。根据Amdal定律，理论最大加速比受限于程序中必须串行的部分占总程序运行时间的比例。在实验测试过程中，受限于平台I/O特性，RD程序中“读取数据”和“映射并输出图像”两部分只能串行执行。根据实验数据，X波段的理论最大加速比为7.40，L波段的理论最大加速比为22.94。根据图5的加速比测试结果，X波段的实际最大加速比已经接近理论最大加速比，L波段程序未来优化方法应当考虑通过硬件优化，尽可能将读取数据部分并行执行，以获得更大的加速。
图5 最大加速比
图6（a）给出了随着任务数的增大，X波段和L波段并行程序的加速比变化情况。从图中首先可以看出，L波段程序的加速比大于X波段程序的加速比。这是因为为了成像，需要更长时间的L波段数据，导致L波段的数据量很大，从而并行粒度划分后重叠部分的额外开销比重相对较小，易于开发窗口之间的数据并行性，并且能够充分利用众多计算单元的强大计算能力。实验结果说明所提出的并行粒度选择技术适合具有大规模数据的程序，能够成功应用于复杂大系统仿真程序的加速。
图6（b）给出了随着节点数的增大，X波段和L波段并行程序的加速比变化情况。从图中可以看出，随着节点数增大，L波段和X波段的所有版本程序的加速比都不断提高，这说明所提出的并行粒度选择技术具有良好的可扩展性，适合运行于更大规模的并行计算机系统，以达到更高的性能加速。
图6 加速比变化情况
5 结语
确定适当的并行粒度是并行化的关键技术之一，从而能够有效地进行任务划分，以充分利用并行计算机的资源［10］。本文研究了并行粒度选择技术，提出了确定并行粒度的基本准则。该研究为进一步实施针对性的并行优化技术奠定了基础。并且以典型SAR成像程序为例，详细验证说明了所提出的并行粒度选择方法，确定SAR成像程序应当采用层次式并行粒度。实验结果表明，采用本文所选择的并行粒度，SAR成像程序能够获得显著的性能提升。
未来的工作主要包括以下几个方面：首先，从模型指导的角度，详细分析并量化影响流最优并行粒度的关键因素，建立并行粒度选择模型；其次，以更多的仿真程序来验证所提出的并行粒度选择技术；最后，将继续研究适用于SAR成像程序的更多并行优化方法。
参考文献:
[1] 龙卉.合成孔径雷达并行成像算法研究及实现［D］.成都:电子科技大学,2001.
［2］ KONG F, ZHAO J, XUE B. Research on parallel processing of SAR imaging algorithm ［C］// Proceedings of the 2nd International Asia-Pacific Conference on Synthetic Aperture Radar. Washington, DC: IEEE Computer Society, 2009: 784-787.
［3］ 王曦爽,黄立胜,王贞松.分布式星载SAR回波仿真的并行化计算研究［J］.系统仿真学报,2006,18（8）:2097-2100.
［4］ APPIANI E, CORVI M, GARIBOTTO G, et al. High-performance SAR image formation and post-processing ［C］// Proceedings of the 2nd International Euro-Par Conference on Parallel Processing. Berlin: Springer-Verlag, 1996: 139-146.
［5］ 雷斌.SAR成像处理中的高性能计算问题［D］.北京:中国科学院电子学研究所,2003.
［6］ 徐永健.SAR实时并行成像系统研究［D］.北京:中国科学院电子学研究所,2001.
［7］ LIN C, SNYDER L.并行程序设计原理［M］.陆鑫达，林新华，译.北京:机械工业出版社,2009.
［8］ 杜静.流体系结构的编译技术研究［D］.长沙:国防科学技术大学,2008.
［9］ 都志辉.高性能计算之并行编程技术――MPI并行程序设计［M］.北京:清华大学出版社,2001.
［10］ ALLEN R, KENNEDY K. Optimizing compilers modern architectures: A dependence-based approach ［M］. San Francisco: Morgan Kaufmann, 2004.