刘小宁，谢宜壮，赵博雅，陈　禾，杨　晨

(北京理工大学信息与电子学院，北京100081)



一种二维访问效率均衡的SAR数据矩阵转置方法

刘小宁，谢宜壮，赵博雅，陈禾，杨晨

(北京理工大学信息与电子学院，北京100081)

摘要：针对SAR成像矩阵转置效率偏低的问题，提出了矩阵分块三维映射法.该方法基于带有bank划分的存储介质并利用其数据访问特性，通过矩阵分块和跨bank优先数据访问方式将二维数据矩阵映射至存储介质的三维存储空间，能够充分发挥存储介质的数据访问效率.实测结果表明，该方法使二维数据的访问效率都接近于顺序访问的效率，极大提高了SAR成像的矩阵转置效率.

关键词：SAR成像;矩阵转置;跨行访问;三维映射

1　引言

合成孔径雷达(SAR，Synthetic Aperture Radar)采集到的原始数据为一个二维数据矩阵，二维数据矩阵每一行的数据为发射的线性调频脉冲的各个采样点的值，每一列的数据为雷达在不同的空间位置处接收到的线性调频脉冲的相应的采样点值.这样，二维数据矩阵的行方向就为距离向，列方向就为方位向［1］.常用的SAR成像处理算法，如RD算法、CS算法将二维数据矩阵的处理转化成多次的一维处理，即距离向处理和方位向处理，继而实现二维高分辨率成像.多次的一维处理之间需要进行行列转换，即矩阵转置.

SAR成像中的矩阵转置实际上是方位向数据访问和距离向数据访问之间的相互转换，是依靠转置存储器(CTM，Corner Turning Memory)来完成的.不同的SAR成像算法中矩阵转置的次数是不同的，RD算法在成像处理过程中至少需要一次矩阵转置，CS算法至少需要三次矩阵转置［2］，每一次矩阵转置都需要遍历CTM内的数据.因此，矩阵转置的效率是影响SAR成像实时性的重要因素.

针对SAR成像处理，Morio Onoe提出了无数据转置的快速处理方法［3］.随着SAR成像技术的发展，SAR成像分辨率越来越高，SAR成像所处理的数据量和运算量也随之增大，这种情况下无数据转置的处理方法已经很难适应.现有的矩阵转置方法有行进列出法、列进行出法、两页式［4，5］、三页式［6，7］矩阵转置法、矩阵分块线性映射法［8］以及实时矩阵转置方法［9］等.行进列出法、列进行出法会造成距离向和方位向上的数据访问效率极为不均衡.两页式、三页式矩阵转置方法实际上是列进行出法和行进列出法的综合应用，适合于需要单次转置的SAR成像算法(如RD算法)的流水实现，而对于需要多次矩阵转置的SAR成像算法(如CS算法)则需要多个CTM来完成SAR成像处理中的多次矩阵转置，难以实现单板单节点的SAR成像，不利于降低成本和系统集成.矩阵分块线性映射法和实时矩阵转置方法两者相近，给出了距离向和方位向效率均衡的矩阵转置方法，但是没有充分利用CTM的数据访问特性以发挥更高的矩阵转置效率.

本文提出的矩阵分块三维映射法是一种可以在同一CTM内完成多次矩阵转置的原位存储方法.该方法结合矩阵分块的思想，将CTM视为三维的存储空间，并有效利用CTM的数据访问特性，同时实现了距离向和方位向数据的二维高效访问.两个方向的访问效率均能达到90%以上，极大的提高了SAR系统成像效率.

2　CTM效率分析

SAR成像处理数据量和运算量巨大，例如，条带模式下对50km×50km的场景进行5m分辨率成像，需要处理的数据量高达2GB.要达到实时高精度成像，需要高速海量存储作为CTM.目前，能够达到此要求的存储芯片有DDR SDRAM、DDR2 SDRAM和DDR3 SDRAM等几种存储芯片.这几种存储芯片的存储原理和数据访问特性类似，存储空间都划分为数个bank.本文以DDR3为例，利用其结构和数据访问特性讲述矩阵分块三维映射法.

DDR3的存储空间根据具体型号的不同，划分为8 或16个bank，每个bank有8K、16K或32K行(Row)，每行有1K或2K个存储单元，也称作列(Column)，每个存储单元可以存储8bit或16bit数据［10］.

DDR3的访问效率受多个时间参数约束［10］，读效率和写效率也略有差别，由于篇幅限制，本文仅对影响DDR3访问效率的两个主要因素刷新和跨行访问进行分析.DDR3工作时，平均每隔tREFI时间都需要占用tRFC的时间对内部存储单元进行刷新(Refresh)，以保证DDR3内的数据不会丢失，刷新期间无法对DDR3内的数据进行访问.其中，tREFI为刷新时间间隔，典型值为7800ns; tRFC为刷新时间，典型值为110ns.另外，对DDR3内某bank中一行的数据访问，需要先对该行进行激活操作(Active)，tRCD时间后才能对该行进行数据访问;对当前活动行的数据访问完成后，需要时间tRP对该行进行预充电操作(Precharge)以关闭当前活动行.其中，tRCD为激活操作与内部数据访问之间的时间间隔，最小值为13ns; tRP为预充电操作的执行时间，最小值为13ns.因此，DDR3的数据访问效率η是数据访问的有效时间tDATA占访问该数据所耗费的所有时间的比值，即:

对DDR3进行连续顺序访问时，在用户时钟频率为200MHz的情况下，每连续访问一行1024点数据，数据访问有效时间为256个时钟周期，即tDATA= 1280ns，理论效率最高可达η1= 96.6%.而对DDR3进行频繁跨行访问时，特别是当每行只进行一次读操作时，每行访问8点数据，数据访问有效时间为2个时钟周期，即tDATA=10ns，此时的访问效率降低为η2=27.4%.

由此可见，对于DDR3连续地址空间的数据访问即逐行顺序访问时，数据访问效率很高，但是对于频繁跨行访问的情况下，数据访问效率则降低数倍，严重影响CTM的矩阵转置效率.

带有bank划分的存储介质还存在一种数据访问特性，在满足一定时序条件下，在对当前bank中某一行进行数据访问的同时可以对另一bank中的某一行执行激活或者预充电操作［10］.当对某一bank中的一行进行数据访问时便激活将要访问的处于不同bank的一行，该行访问完毕后，对该行执行预充电操作的同时便可以对另一bank中已经激活的行进行数据访问.此种每访问一行都要跨bank的数据访问方式能够屏蔽掉激活和预充电操作带来的效率损失，因此，比在同一bank内连续跨行的数据访问方式效率高［11］，能够使对DDR3的数据访问最高效率达到:

本文将这种每次换行都要跨bank的数据访问方式称为跨bank优先数据访问方式，当数据访问需要频繁跨行时，这种跨bank优先数据访问方式的效率优势会非常明显.

3　矩阵分块三维映射法

矩阵分块三维映射法结合了矩阵分块和跨bank优先数据访问方式的优势.首先，将SAR成像要处理的二维数据矩阵分成大小相等的子矩阵，每个子矩阵的数据正好能够映射至CTM中的一行.然后，将每个子矩阵按照跨bank优先数据访问方式映射至CTM的每一行.这样便实现了将SAR成像所处理的二维数据矩阵内的数据由其逻辑地址至物理地址的映射.其中，逻辑地址为该点数据在二维数据矩阵内的行列位置，物理地址为该数据点在CTM三维存储空间内的存储地址.

3.1矩阵分块

设SAR成像所处理的二维数据矩阵为A(x，y)，0≤x≤NA-1，0≤y≤NR- 1 .其中，NR为距离向采样点数，NA为方位向采样点数.SAR成像处理过程中需要进行FFT运算，因此NR和NA一般为2的整数次幂.

DDR3为一个三维存储空间，记为B(i，j，k).其中，i为行地址，j为列地址，k为bank地址.Cn为DDR3的列数，Bn为bank数，而行数可以根据二维数据矩阵A(x，y)的大小通过外加存储器的方法进行扩展.则，0≤i≤NANR/(CnBn)-1，0≤j≤Cn-1，0≤k≤Bn-1.

为了均衡DDR3内距离向和方位向的数据访问效率，需要把矩阵A(x，y)划分为多个子矩阵，然后将子矩阵映射至DDR3的一行.这样在DDR3的一行中既有在同一距离向上的相邻数据，又有在同一方位向上的相邻数据.

划分后的子矩阵大小为NaNr.其中，Na为子矩阵的方位向点数，Nr为子矩阵的距离向点数，且NaNr= Cn.完整访问完该行的数据需要跨行的次数RCN(Row Crossing Number)为:

当Cn=1K时，RCN的值与Na的关系曲线如图1所示.

由图1可以看出，当Na= Nr= 32时，RCN取最小值64，这样距离向和方位向的数据访问效率最为均衡.当Cn=2K时，则Na=32，Nr=64或者Na=64，Nr=32，RCN取最小值96.

如式(4)所示，将原始数据矩阵A(x，y)分成M×N个大小相等的子矩阵，每个子矩阵用Am，n表示.其中，0≤m≤M - 1，0≤n≤N - 1.M为方位向上子块的个数，M = NA/Na; N为距离向上子块的个数［8，11］，N = NR/Nr.

子矩阵Am，n内数据与DDR3存储空间的一行的映射关系如图2所示.

3.2跨bank优先数据访问方式

矩阵分块后，通常的做法是将二维数据矩阵的子矩阵沿距离向从DDR3存储空间的bank 0的第0行开始逐行映射，直到bank 0的最后一行映射完毕后再从bank 1的第0行开始逐行映射，一直到最后一个子矩阵映射完毕［8，9］.这种逐行映射的方式是先将当前的bank映射完毕后再将其后的子矩阵映射至下一bank，每个子矩阵映射至DDR3存储空间后所处的bank分布如图3所示.

图3中的每个小方块为一个子矩阵，方块内的数字代表该子矩阵映射至DDR3存储空间后所处于的bank号.可以看出，距离向上每个相邻的子矩阵在DDR3存储空间内处于同一bank不同行，这样在对距离向数据进行访问时，每次访问32点数据都要跨行一次，占用激活时间tRCD和预充电时间tRP.用户时钟频率为200MHz的情况下单纯的数据访问时间tDATA= 40ns，此时的数据最高访问效率为η3= 59.7%.同样，方位向数据访问的最高效率也近似等于η3.因此，简单的依靠矩阵分块仅能使距离向和方位向的数据访问效率有所均衡，不能避免由于频繁的跨行带来的访问效率损失.

本文的矩阵分块三维映射法采用跨bank优先数据访问方式来解决上述问题，通过使距离向和方位向数据的跨行访问都以跨bank优先的方式进行，有效的避免了由于频繁的跨行访问所导致的效率降低.

为了保证对DDR3内距离向数据和方位向数据的访问都以跨bank优先的方式进行，同时需要使沿距离向分布的相邻子矩阵和沿方位向分布的相邻子矩阵映射至DDR3存储空间的不同bank内，形成如图4所示的子矩阵bank分布.

为了达到上述效果，本文的矩阵分块三维映射法做了如下设计:

首先，将第0行距离向上N个子矩阵A0，0～A0，N -1以跨bank优先的方式逐一映射至bank 0～bank Bn- 1的第0行，然后是bank 0～bank Bn- 1的第1行，按照此方式依次映射，直至子矩阵A0，N -1映射至bank Bn- 1的第N/Bn-1行.

然后，对于第1行距离向子矩阵A1，0～A1，N -1，则从bank 1的第N/Bn行开始映射，映射至bank Bn-1的第N/ Bn行后再返回bank 0的第N/Bn行，然后是bank 1的第N/ Bn+1行，如此继续下去直至A1，N -1映射至bank 0的第2N/ Bn-1行.这样，映射起始于bank 1，结束于bank 0.

按照如上规律，对于第m行子矩阵Am，0～Am，N -1(0 ≤m≤M -1)，映射起始于bank p的第mN/Bn行，结束于bank q的第(m + 1)N/Bn- 1行.其中p = mod(m，Bn)，0≤p≤Bn- 1，q = mod(m + Bn- 1，Bn)，0≤q≤Bn-1(mod(x，y)为对x/y取余).如此映射下去将会得到如图4所示的子矩阵所映射bank分布图.

图5为当Bn=8时，每个子矩阵在DDR3三维存储空间内的位置分布.

按照矩阵分块三维映射法将二维数据矩阵映射至DDR3三维存储空间后，无论是在距离向上还是在方位向上，二维数据矩阵中的每个相邻的子矩阵都分布在DDR3不同的bank中.这样，在对DDR3进行距离向或方位向数据访问时，都可以充分利用跨bank优先数据访问方式的优势，从而使距离向和方位向数据访问的效率同时达到最优.

3.3地址映射

利用矩阵分块三维映射法实现SAR成像矩阵转置存储时，处理器芯片所执行的程序需要依照该矩阵转置存储方法的地址映射规律将二维数据矩阵内数据的逻辑地址映射至DDR3存储空间的物理地址.对存储在DDR3内的二维数据矩阵进行距离向或方位向数据的读写则按照该地址映射规律执行.

二维数据矩阵A(x，y)内任意一点的数据的逻辑地址为(x，y)，其中，0≤x≤NA-1，0≤y≤NR-1，则:

DDR3存储空间B(i，j，k)内的存储单元对应的物理地址为(i，j，k).本文在矩阵分块三维映射法中，实现了SAR成像处理过程中的数据由其逻辑地址(x，y)至物理地址(i，j，k)的映射.按照矩阵分块三维映射法，(x，y)与(i，j，k)之间有如下映射关系:

此映射关系将对二维数据矩阵中逻辑地址(x，y)的数据访问转化成了对DDR3三维存储空间中物理地址(i，j，k)的访问.SAR成像矩阵转置的数据访问的物理地址跳变规律较为复杂，而逻辑地址跳变特别简单.进行程序设计时，根据此映射关系设计一个地址变换器，物理地址则由逻辑地址通过地址变换得到.

4　效率测试与结果分析

本文采用Xilinx公司的KC705开发板作为测试平台，ISE14.3作为软件开发环境.通过KC705开发板上的XC7K325T完成对片外存储空间DDR3 SODIMM的访问，并对矩阵分块三维映射法及其它矩阵转置方法进行效率了测试.

本文对矩阵分块三维映射法的数据访问效率进行了测试，测试方法为将一个SAR成像所要处理的8192 ×8192点二维数据矩阵按照矩阵分块三维映射法的地址映射规律分别沿距离向(方位向)写至KC705开发板上的片外DDR3 SODIMM，然后以距离向(方位向)的方式读回数据并校验其正确性，同时，以计数器的方式计算出所访问数据的个数Data-count和数据访问时间Time-count.

数据访问效率的公式如下:

由式(7)可以看出，数据访问效率等于所访问数据的个数与传输数据所用的时间的比值.以同样的方法分别对行进列出法和矩阵分块三维映射法进行了效率测试，并与本文中的矩阵分块三维映射法进行对比.各种矩阵转置方法效率测试结果如下:

表1　矩阵转置方法效率测试

由表1中的测试结果可以看出，行进列出法或者列进行出法在一个方向上的数据访问效率很高，而在另一个方向上数据访问效率很低.矩阵分块线性映射法两个方向的数据访问效率相对均衡，但是都无法达到顺序访问的效率.矩阵分块三维映射法相对于其他的矩阵转置方法有很大的效率优势，距离向和方位向的读写效率都能够达到90%以上，接近于顺序访问的效率.

5　结论

本文中的矩阵分块三维映射法是一种原位存储方法，结合矩阵分块的思想，充分利用了DDR3的数据访问特性，将二维数据矩阵划分为多个子矩阵并按地址映射规律映射至DDR3存储器的每一行中.按照该方法，二维数据矩阵的距离向和方位向的数据都能够以跨bank优先数据访问方式被访问，从而使两个方向的数据访问效率均能接近顺序访问的效率.实践表明，该方法适用于采用DDR、DDR2、DDR3等带有bank划分的存储介质作为CTM的SAR成像系统，极大的提高了SAR成像处理中的矩阵转置效率.

参考文献

［1］皮亦鸣，杨建宇，付毓生，等.合成孔径雷达成像原理［M］.成都:电子科技大学出版社，2007.Pi Yi-ming，Yang Jian-yu，Fu Yu-sheng，et al.Synthetic Aperture Radar Imaging Principle［M］.Chengdu: University of Electronic Science and Technology Press，2007.(in Chinese)

［2］熊君君，王贞松，姚建平，等.星载SAR实时成像处理器的FPGA实现［J］.电子学报，2005，33(6): 1070 -1072.Xiong Jun-jun，Wang Zhen-song，Yao Jian-ping，et al.The FPGA design of on board SAR real time imaging processor［J］.Acta Electronica Sinica，2005，33(6): 1070 -1072.(in Chinese)

［3］Onoe Morio，Kubota Ichiro，Masubuchi Yoshio.Fast processing of synthetic aperture radar without data transposition［A］.Proceedings of the 13th Int’l Symposium on Space Technology and Science［C］.Tokyo: AGNE Publ Co，1982.1305 -1310.

［4］卢世祥，韩松，王岩飞.合成孔径雷达实时成像转置存储器的两页式结构与实现［J］.电子与信息学报，2005，27(8): 1226 -1228.Lu Shi-xiang，Han Song，Wang Yan-fei.The structure and implementation of the two-frame corner turn memory(CTM)in real time imaging of SAR［J］.Journal of Electronics and Information Technology，2005，27(8): 1226 -1228.(in Chinese)

［5］谢应科，张涛，韩承德.实时SAR成像系统中矩阵转置的设计和实现［J］.计算机研究与发展，2003，40(1): 6 -11.Xie Ying-ke，Zhang Tao，Han Cheng-de.Design and implementation of matrix transposition unit for real time SAR image systems［J］.Journal of Computer Research and Development，2003，40(1): 6-11.(in Chinese)

［6］李早社，禹卫东，汪亮，等.基于SDRAM的星载SAR星上实时成像转置存储器［J］.信号处理，2007，23(3): 433 -436.Li Zao-she，Yu Wei-dong，Wang Liang，et al.Corner turning memory based on SDRAM for spaceborne SAR onboard real-time imaging［J］.Signal Processing，2007，23(3): 433 -436.(in Chinese)

［7］Ren G，Han J，Han C.CTM on multiprocessor: solution for bottleneck of SAR［A］.Proceedings of the 5th International Conference on Signal Processing［C］.Beijing: IEEE，2000.1915 -1920.

［8］边明明，毕福昆，汪精华.实时SAR成像系统矩阵转置方法研究与实现［J］.计算机工程与应用，2011，47(22): 117 -119.Bian Ming-ming，Bi Fu-kun，Wang Jing-hua.Research and implementation of matrix transpose for real-time SAR imaging system［J］.Computer Engineering and Applications，2011，47(22): 117 -119.(in Chinese)

［9］鲍胜荣，周海斌.SAR实时成像高效矩阵转置研究和实现［J］.现代雷达，2013，35(3): 24 -27.Bao Sheng-rong，Zhou Hai-bin.Study and implementation of high efficient matrix transpose for SAR real-time imaging system［J］.Modern Radar，2013，35(3): 24 - 27.(in Chinese)

［10］Micron Technology Inc.1Gb-DDR3-SDRAM.pdf［DB/ OL］.http: / /www.micron.com，2009.

［11］Xiaoning Liu，He Chen，Yizhuang Xie.Research and implementation of CTM for real-time SAR imaging processing［A］.Proceedings of the IET International Radar Conference 2013［C］.Xi’an: IET，2013.0228.

刘小宁男.1987年11月出生，山东德州人.现为北京理工大学信息与电子学院博士研究生.主要研究方向为星上SAR实时成像处理.E-mail: liuxiaoning@ bit.edu.cn

谢宜壮(通信作者)男.1980年1月出生，吉林长春人.2009年在北京理工大学获得工学博士学位，2011年北京大学信息科学与技术学院博士后流动站出站.现为北京理工大学信息与电子学院讲师.主要研究方向为星上实时信息处理技术与系统架构设计.

E-mail: xyz551-bit@ bit.edu.cn

A SAR Data Matrix Transpose Method of Efficiency Balanced Two Dimensional Access

LIU Xiao-ning，XIE Yi-zhuang，ZHAO Bo-ya，CHEN He，YANG Chen
(School of Information and Electronics，Beijing Institute of Technology，Beijing 100081，China)

Abstract:A sub-matrix three-dimensional mapping method was proposed to improve the matrix transpose efficiency for SAR imaging processing.This method，which is based on storage medium consisting of several banks and uses its data access features，maps two-dimensional data matrix to three-dimensional space of storage medium.The mapping is implemented through sub-matrix and cross bank first data access，and it can give full play to data access efficiency of storage medium.The experimental results show that this method enables the data access efficiency of both dimensional to be closed to sequential access efficiency.It greatly improved the matrix transpose efficiency for SAR imaging processing.

Key words:SAR imaging; matrix transpose; cross row access; three-dimensional mapping

作者简介

收稿日期:2014-06-07;修回日期: 2014-08-26;责任编辑:李勇锋

DOI:电子学报URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.006

中图分类号：TN952

文献标识码：A

文章编号：0372-2112(2016)01-0033-06