基于多核处理器的并行雷达数据处理研究

朱海涛，倪世道，杜南山

(中国电子科技集团公司第三十八研究所，合肥 230088)

0 引言

未来战争中的电磁环境将异常复杂，雷达会受到各种形式的欺骗和干扰，产生大量的杂波，并且需要检测的目标日益增多，目标的运动速度越来越快，机动性也越来越灵活［1］。上述情况的出现将会大大增加雷达数据处理的运算量，而雷达数据处理系统作为一个实时系统，必须在规定的时间内计算出结果。这对数据处理的计算能力提出了很高的要求。

一直以来，处理器芯片厂商通过不断地提高主频来提高处理器性能。但是，随着芯片工艺的不断进步，传统的处理器体系结构技术已经面临瓶颈，晶体管的集成度已经超过上亿个，很难单纯地通过提高主频来提升性能，而且主频的提高同时也带来功耗的增 加。从应用需求来看，日益复杂的科学计算、多媒体、虚拟化等多个应用领域都迫切需要强大的计算能力。在这样的背景下，各处理器厂商将芯片从提高主频转向多核、多线程［2］。

目前，雷达数据处理系统普遍采用单核处理器时代的串行架构，不能充分利用多核处理器的计算资源，早已不适应计算机技术的发展。本文基于多核处理器研究并行雷达数据处理架构的可行性，以提高雷达数据处理计算性能。

1 并行处理介绍

图1 多核处理器结构

典型的多核处理器结构如图1所示［3-4］，包含多个相同的处理器核，每个处理器核有自己的高速缓存，所有处理器核共享内存资源。这种结构属于对称多处理器(Symmetric Multi-Processor，SMP）。

在SMP处理器结构中，一般采用共享存储并行编程模型，对需要并行的代码段创建多线程进行计算，线程之间通过共享内存进行通信。

由于线程共享同一进程的内存空间，多个线程可能会同时访问同一个数据。如果没有正确的保护措施，对共享数据的访问会造成数据的不一致和错误。

假设有一个共享变量counter 初始值为1，线程A执行counter++，线程B 执行counter--。这两条语句实际是分别通过多条语句完成的:

线程A线程B

temp1=countertemp2=counter

temp1=temp1+1temp2=temp2－1

counter=temp1counter=temp2

两个线程一种可能的执行序列如下:

(1）线程A:temp1=counter(temp1=1）

(2）线程A:temp1=temp1+1(temp1=2）

(3）线程B:temp2=counter(temp2=1）

(4）线程B:temp2=temp2－1(temp2=0）

(5）线程A:counter=temp1(temp1=2）

(6）线程B:counter=temp2(temp2=0）

counter 正确的结果应该为1，但在两个线程交叉执行时就可能出现0 或2的错误结果。为了避免这种错误的发生，在多个线程访问共享数据时需要进行同步。常用的同步机制包括临界区、信号量和互斥量，比较常用的同步方法是互斥量和信号量［2］。

作为一种互斥设备，互斥量有两个状态:上锁和空闲。在同一时刻只能有一个线程能够对互斥量加锁。对于一个已经加锁的互斥量，当另一个线程试图对它加锁时，该线程会被阻塞，直到互斥量被释放。

Linux 操作系统的IEEE POSIX 标准Pthreads 库提供了互斥同步函数pthread_mutex_lock、pthread_mutex_unlock 等。

上述举例通过互斥量同步机制可以得到正确的结果，如表1所示。假设线程A 首先获得锁。

表1 线程A和B的同步方法

并行算法(程序）执行速度相对于串行算法(程序）执行速度加快的倍数称为并行加速比［2］。假设Sp是加速比，T1是单处理器下的运行时间，Tp是在有P个处理器并行系统中的运行时间，则

并行程序的效率Ep为

当Sp=P时，加速比被称为线性加速比。在实际应用中，由于线程间同步、通信等额外的开销导致Sp往往小于P。

2 数据处理流程分析

雷达数据处理系统接收到信号处理送来的点迹，一般按照图2所示流程进行处理［5］。

图2 数据处理流程

图2所示的各个步骤是一个顺序的过程，不能并行执行。接下来对每个步骤进行分析，判断是否适合并行处理。

(1）点迹预处理

把点迹从目标量测坐标系转换到数据处理所在坐标系。该步骤是一个循环操作，每个循环对单个点迹进行坐标变换，循环之间没有数据依赖关系，适合并行处理。

(2）数据互联

建立当前时刻新点迹与历史数据之间的关系，以确定这些点迹是否来自同一个目标，分为新点迹与航迹的互联、新点迹与旧点迹的互联。数据互联方法主要有极大似然类算法和贝叶斯类算法。常用的最近邻域算法及其改进算法属于贝叶斯算法［5-6］。在最近邻域算法中，根据每一个目标的预测位置设置该目标的跟踪门(相关波门）。每一个新点迹与所有航迹一一进行相关，判断其是否落入目标的跟踪门内，如果落入该目标的跟踪门内则形成点航配对，并根据新点迹与预测位置的距离差设置该配对的相关度，每个新点迹可能与多个航迹配对成功，按照相关度从高到低选择最优点航配对［6］。点点配对方法与点航配对相同。每一个点迹与所有航迹一一进行相关。该操作是循环操作，循环体之间没有数据依赖，能够采用并行处理方法。

(3）航迹起始

航迹起始是目标跟踪的第一步，主要包括暂时航迹形成和轨迹确定。航迹起始可以划分成多个独立的子任务并行处理。

(4）跟踪

根据数据互联步骤中选择的点航配对，对来自每个目标的新点迹进行跟踪处理。目前，经常采用的目标跟踪方法有交互式多模型算法、Jerk 模型算法等。滤波算法多使用卡尔曼滤波［5-6］。交互多模型算法通过多个目标模型的有效组合来实现对目标机动状态的自适应估计［5-7］。跟踪是根据数据互联步骤选择的点航配对，对每个航迹的更新操作，各个航迹更新操作之间没有数据依赖，可以并行处理。

(5）点迹与航迹维护

对每个点迹和航迹进行维护，删除满足条件的点迹和航迹。该步骤以单个点迹和航迹为单位进行操作，各个点迹、航迹之间没有数据依赖，可以并行处理。

根据上述分析可知，5个步骤内部均可以采用多个线程并行处理的方法，如图3所示。由于各步骤之间必须顺序执行，因此需要在每个步骤执行结束时设置栅障(barrier），对并行处理的多个子任务进行同步。

3 实验结果分析

根据上述分析，对雷达数据处理系统进行了并行架构设计以及实验测试。实验环境为Linux 2.6.32 操作系统，Intel Xeon W3565 4 核处理器，6 GB 内存。在实验中，仿真了2000 帧数据，每帧模拟2000个目标，随机产生20000个杂波点。

图4 是并行数据处理系统执行时间以及加速比统计。从图中可以看出，随着线程个数增加，执行时间逐渐降低。单线程串行程序执行时间为510 s，4 线程并行程序执行时间降低到174 s，加速比接近3，数据处理系统性能得到了明显提升。

图3 并行处理示意图

图4 并行运算时间及加速比

根据第2节的分析可知，数据处理各个步骤均可以并行处理，因此4 线程并行程序加速比理论上应达到4，效率应达到1，而实验中4 线程并行程序的效率只有Ep=2.92/4=73%。接下来对并行加速比的损失进行分析，图5 是各个步骤执行时间随线程个数的变化情况。

点迹预处理、数据互联、航迹起始和跟踪中的数学操作易于划分成多个子任务并行执行，并且各个子任务之间数据依赖较少，增加线程数可以显著的降低执行时间。但是，由图3 可知，每个步骤结束时都设置了barrier，只有等最慢的线程执行结束时才会进行下一个步骤，CPU 利用率达不到100%，因此加速比不能线性提升。

图5 各步骤并行执行时间统计

点迹与航迹维护主要是对共享数据结构(如链表、堆等）的操作以及内存的读写。根据第2节的介绍可知，同时访问共享数据结构会导致线程的阻塞，多个线程竞争有限的内存带宽，每个线程实际利用带宽都不高，因此点迹与航迹维护并行处理的效果不明显。

4 结束语

未来日益复杂的电磁环境对雷达数据处理系统的计算能力要求将会非常高。为了提高数据处理的计算性能，本文基于多核处理器结构，对并行雷达数据处理架构进行了研究。从实验结果可知，并行处理架构性能比传统的串行系统有了明显提升，在4 核处理器上，性能提高了将近3 倍。这表明雷达数据处理系统是适合并行处理的。但是，由于线程间同步、共享变量过多以及访问内存竞争激烈等原因，并行系统的效率没有达到最优。在未来的工作中，将针对上述问题进行深入研究，进一步提高并行雷达数据处理系统的性能。

［1］俞志富，吕久明.基于航迹跟踪的EKF 应用研究［J］.现代防御技术，2007，35(2）:113-117.

［2］多核系列教材编写组.多核程序设计［M］.北京:清华大学出版社，2007.

［3］Franchetti F，Puschel M，Voronenko Y，Chellappa S，Moura J M F.Discrete fourier transform on multicore［J］.IEEE Trans.on Signal Processing Magazine，2009，26(6）:90-102.

［4］Hu Weiwu，Wang Jian，Gao Xiang.Godson-3:A Scalable Multi-core RISC Processor with X86 Emulation Support［J］.IEEE Trans.on Micro，2009，29(2）:17-29.

［5］何友，修建娟，张晶炜，等.雷达数据处理及应用［M］.2 版.北京:电子工业出版社，2009.

［6］蔡庆宇，张伯彦，曲洪权.相控阵雷达数据处理教程［M］.北京:电子工业出版社，2011.

［7］Averbuch A，Bar-Shalom Y，Dayan J.Interacting multiple model methods in target tracking:a survey［J］.IEEE Trans.on Aerospace and Electronic Systems，1998，34(1）:103-123.