Research on Block-based Matrix Transposition and FPGA Logic Design

doi:10.19678/j.issn.1000-3428.0070145

Abstract

Abstract:

Matrix transposition is a fundamental and crucial operation in digital signal processing and has extensive applications in various fields, such as array signal processing, spectral analysis, signal filtering, and signal recognition. The traditional matrix transposition method, owing to its complex algorithm, long processing time, and low efficiency, can no longer satisfy the high-performance requirements of modern signal processing systems. To solve these problems, this paper proposes a block-based matrix transposition method based on a Field Programmable Gate Array (FPGA) and Double Data Rate 3 Synchronous Dynamic Random Access Memory (DDR3 SDRAM). The core of this method is the optimization of data mapping and access patterns. Distributing the efficiency bottlenecks in the transposition process to both the read and write stages effectively improves the transposition efficiency. Specifically, this method utilizes the high-speed parallel processing capability of the FPGA combined with the high-speed storage characteristics of the DDR3 SDRAM to achieve the rapid transposition of large matrices. Two DDR3 SDRAM chips are employed to construct a ping-pong buffering architecture. One is used for reading the original matrix data, and the other is used for writing the transposed data, thereby achieving a real-time pipelined transposition of the matrix. The test results on an actual hardware platform indicate that this method has a significant effect on handling the transposition of large M×N matrices with dimensions that are not powers of 2. Compared with distributed storage matrix transposition algorithms, this method is not limited by the size of the matrix and can be applied to the transposition of any large matrix. It is also easy to implement and has a transposition efficiency of 90%.

Key words: matrix transposition, Double Data Rate 3 Synchronous Dynamic Random Access Memory (DDR3 SDRAM), cross-row access, Field Programmable Gate Array (FPGA), block-based storage

摘要：

矩阵转置是数字信号处理中的基础关键操作, 广泛应用于阵列信号处理、频谱分析、信号滤波与信号识别等领域。传统的矩阵转置方法由于算法复杂、处理时间长、效率不高等问题, 已经逐渐不能满足现代信号处理系统对高性能的需求。为解决上述问题, 本文提出一种基于现场可编程门阵列(FPGA)与第三代双倍数据率同步动态随机存取存储器(DDR3 SDRAM)的分块矩阵转置方法。该方法的核心在于优化数据映射方式和访问模式, 通过将转置过程中的效率瓶颈分散到读写两个环节, 有效提高了转置效率。具体来说, 该方法利用FPGA的高速并行处理能力, 结合DDR3 SDRAM的高速存储特性, 实现了对大型矩阵的快速转置。同时采用两片DDR3 SDRAM形成乒乓结构, 一块用于读取原矩阵数据, 另一块用于写入转置后的数据, 从而实现矩阵的实时流水转置。硬件平台实测结果表明, 该方法对于处理非2的整数次幂的M×N大型矩阵转置问题具有显著的效果; 相比于分布式存储矩阵转置算法, 这种方法不受矩阵规模的限制, 适用于任意大型矩阵的转置, 且易于实现, 转置效率达到90%。

关键词: 矩阵转置, 第三代双倍数据率同步动态随机存取存储器, 跨行访问, 现场可编程门阵列, 分块存储

WU Changrui, JIANG Jinghong, XU Jianqing. Research on Block-based Matrix Transposition and FPGA Logic Design[J]. Computer Engineering, 2026, 52(8): 203-209.

吴长瑞, 蒋景红, 徐建清. 分块矩阵转置研究与FPGA逻辑设计[J]. 计算机工程, 2026, 52(8): 203-209.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0070145

https://www.ecice06.com/EN/Y2026/V52/I8/203

Figures/Tables 10

Fig.1 CIRO and RICO architectures

Fig.2 Structure of whole matrix data storage

Fig.3 Structure of the first block data storage

Fig.4 Schematic diagram of matrix data readout order

Fig.5 Schematic diagram of data storage in Row 1 for all M/16 blocks in DDR3 SDRAM

Fig.6 Relationship between physical address and logical address

Fig.7 DDR3_0 and DDR3_1 ping-pong structure and read/write timing

Fig.8 Comparison of DDR3 SDRAM write data simulation timing before and after optimization

References 23

1	边明明, 毕福昆, 汪精华. 实时SAR成像系统矩阵转置方法研究与实现. 计算机工程与应用, 2011, 47 (22): 117-119, 144.
	BIAN M M , BI F K , WANG J H . Research and implementation of real-time SAR imaging system matrix transposition method. Computer Engineering and Applications, 2011, 47 (22): 117-119, 144.
2	施隆照, 叶江彬. 矩阵转置切换在FFT处理器中的应用. 电子技术, 2016, 45 (5): 61- 65.
	SHI L Z , YE J B . The application of array transpose commutator in FFT processor. Electronic Technology, 2016, 45 (5): 61- 65.
3	陈亮, 李涌睿, 丁杰, 等. 星载SAR在轨成像高效处理系统硬件实现设计. 信号处理, 2024, 40 (1): 138- 151.
	CHEN L , LI Y R , DING J , et al. Hardware implementation design for an efficient on-board imaging processing system in spaceborne SAR. Journal of Signal Processing, 2024, 40 (1): 138- 151.
4	曹富军, 袁冬芳. 矩阵转置对图形变换的几何意义. 内蒙古科技大学学报, 2021, 40 (2): 112- 116.
	CAO F J , YUAN D F . The geometric meaning of matrix transposition for graphic transformation. Journal of Inner Mongolia University of Science and Technology, 2021, 40 (2): 112- 116.
5	谢应科, 张涛, 韩承德. 实时SAR成像系统中矩阵转置的设计和实现. 计算机研究与发展, 2003, 40 (1): 6- 11.
	XIE Y K , ZHANG T , HAN C D . Design and implementation of matrix transposition unit for real-time SAR image systems. Journal of Computer Research and Development, 2003, 40 (1): 6- 11.
6	NGUYEN X T, NGUYEN H T, PHAM C K. A bit-level matrix transpose for bitmap-index-based data analytics[C]//Proceedings of the 6th International Conference on Communications and Electronics (ICCE). Ha-Long, Vietnam: IEEE Press, 2016: 217-220.
7	SUN T Y , XIE Y Z , LI B Y . Efficiency balanced matrix transpose method for sliding spotlight SAR imaging processing. The Journal of Engineering, 2019 (21): 7775- 7778.
8	ZHANG B , MA Z G , YU F . A novel pipelined algorithm and modular architecture for non-square matrix transposition. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2020, 68 (4): 1423- 1427.
9	HENRIKSSON M, GUSTAFSSON O. Streaming matrix transposition on FPGAs using distributed memories[C]//Proceedings of the IEEE Nordic Circuits and Systems Conference (NorCAS). Aalborg, Denmark: IEEE Press, 2023: 1-6.
10	Micron Technology Inc. DDR3 point-to-point design support[EB/OL]. [2024-05-10]. http://www.micron.com/~/media/Documents/Products/Technical%20Note/DRAM/tn4113_ddr3_point_to_point_design.pdf.
11	JEDEC Solid State Technology Association. DDR3 SDRAM standard: JESD79-3F—2012[S]. Arlington, USA: JEDEC Solid State Technology Association, 2012.
12	Xilinx Co., Ltd. 7 Series FPGAs memory interface solutions user guide[EB/OL].[2024-05-10]. http://www.xilinx.com/support/documentation/ip_documentation/ug586_7Series_MIS.pdf.
13	姚佳辰, 马睿, 杨晓华, 等. 基于分块转置的二维快速傅里叶变换的FPGA设计. 电子测量技术, 2023, 46 (15): 38- 44.
	YAO J C , MA R , YANG X H , et al. FPGA-based design of two-dimensional fast Fourier transformation via block transposing. Electronic Measurement Technology, 2023, 46 (15): 38- 44.
14	SOLOMON M. Transpose of a matrix: properties, examples & applications[EB/OL].[2024-05-10]. https://martinsolomon.io/concepts/transpose-of-a-matrix.
15	裴向东, 王庆林, 廖林玉, 等. 多核数字信号处理器并行矩阵转置算法优化. 国防科技大学学报, 2023, 45 (1): 57- 66.
	PEI X D , WANG Q L , LIAO L Y , et al. Optimizing parallel matrix transpose algorithm on multi-core digital signal processors. Journal of National University of Defense Technology, 2023, 45 (1): 57- 66.
16	吴长瑞, 徐建清, 蒋景红. 基于Kintex-7 FPGA的DDR3 SDRAM接口应用研究. 现代电子技术, 2017, 40 (24): 21- 24.
	WU C R , XU J Q , JIANG J H . Research on DDR3 SDRAM interface application based on Kintex-7 FPGA. Modern Electronics Technique, 2017, 40 (24): 21- 24.
17	鲍胜荣, 周海斌. SAR实时成像高效矩阵转置研究和实现. 现代雷达, 2013, 35 (3): 24- 27.
	BAO S R , ZHOU H B . Study and implementation of high efficient matrix transpose for SAR real-time imaging system. Modern Radar, 2013, 35 (3): 24- 27.
18	刘小宁, 谢宜壮, 赵博雅, 等. 一种二维访问效率均衡的SAR数据矩阵转置方法. 电子学报, 2016, 44 (1): 33- 38.
	LIU X N , XIE Y Z , ZHAO B Y , et al. A SAR data matrix transpose method of efficiency balanced two dimensional access. Acta Electronica Sinica, 2016, 44 (1): 33- 38.
19	GUO C G , XU J C , XU W Y . Highly efficient design of SDRAM-based CTM for real-time SAR imaging system. IET Circuits, Devices & Systems, 2019, 13 (5): 656- 660.
20	范明亮, 郭子涵, 柴晓楠, 等. 面向FT-M7002的Sobel边缘检测算法优化实现. 计算机工程, 2022, 48 (6): 193- 199. doi: 10.19678/j.issn.1000-3428.0061903
	FAN M L , GUO Z H , CHAI X N , et al. Optimized realization of sobel edge detection algorithm for FT-M7002. Computer Engineering, 2022, 48 (6): 193- 199. doi: 10.19678/j.issn.1000-3428.0061903
21	曾灵灵, 张敦博, 沈立, 等. 便笺式存储器中一种新颖的交错映射数据布局. 计算机工程, 2024, 50 (5): 33- 40. doi: 10.19678/j.issn.1000-3428.0067271
	ZENG L L , ZHANG D B , SHEN L , et al. A novel interleaved mapping data layout in scratch pad memory. Computer Engineering, 2024, 50 (5): 33- 40. doi: 10.19678/j.issn.1000-3428.0067271
22	白澜, 魏仁乐, 郭拯危, 等. 基于GPU的多模式SAR成像加速研究. 太赫兹科学与电子信息学报, 2023, 21 (8): 1037- 1042.
	BAI L , WEI R L , GUO Z W , et al. Multi-mode SAR imaging acceleration based on GPU. Journal of Terahertz Science and Electronic Information Technology, 2023, 21 (8): 1037- 1042.
23	田卫明, 刘富强, 谢鑫, 等. 基于GPU粗细粒度和混合精度的SAR后向投影算法的并行加速研究. 信号处理, 2023, 39 (12): 2213- 2224.
	TIAN W M , LIU F Q , XIE X , et al. Research on parallel acceleration processing technology of SAR back projection algorithm based on two granularities and mixing precision of GPU. Journal of Signal Processing, 2023, 39 (12): 2213- 2224.

[1]	GAO Yu, CHENG Yaodong, ZHANG Minxing, CHENG Yaosong, BI Yujiang. Research and Implementation of Computational Storage System for High-Energy Physics [J]. Computer Engineering, 2026, 52(3): 299-307.
[2]	PENG Yun, WANG Yubing, LIANG Lei, SONG Yue, QIU Cheng, LEI Yuxin, JIA Peng, MIAO Guoqing, QIN Li, WANG Lijun. Winograd Heterogeneous Sampling Window Convolution Acceleration Operator [J]. Computer Engineering, 2025, 51(9): 71-79.
[3]	LI Yunjiayun, AN Junshe, ZHOU Li. Design and Verification of Autonomous and Controllable IP Core for Satellite-Borne FlexRay Data Bus [J]. Computer Engineering, 2025, 51(12): 311-323.
[4]	ZENG Lingling, ZHANG Dunbo, SHEN Li, DOU Qiang. A Novel Interleaved Mapping Data Layout in Scratch Pad Memory [J]. Computer Engineering, 2024, 50(5): 33-40.
[5]	DI Xinkai, YANG Haigang. FPGA-based Accelerator for Sparse Convolutional Neutral Network [J]. Computer Engineering, 2021, 47(7): 189-195,204.
[6]	CUI Bo, LIU Zhong-jin, LI Yong, SU Li, JIN De-peng, ZENG Lie-guang. Design and Implementation of Innovation Experiment Equipment for High Speed Programmable Network [J]. Computer Engineering, 2014, 40(5): 313-316.
[7]	ZHANG Jiang, WEI Ji-Ceng. SoC Implementation of Astronomical Image Difference Algorithm [J]. Computer Engineering, 2012, 38(5): 240-242.
[8]	XIE Yi-zhuang; LONG Teng. Two Dimensional Pulse Compression Based on Embedded Processor in FPGA [J]. Computer Engineering, 2010, 36(5): 248-249,.
[9]	LI Chengwei, GU Huajiang, NI Ming, CHAI Xiaoli. Contrast of Embedded Processors in Multimedia and Digital Signal Processing [J]. Computer Engineering, 2006, 32(2): 263-265.

Please choose a citation manager

Content to export