1、第 40 卷第 3 期计算机应用与软件Vol.40 No 32023 年 3 月Computer Applications and SoftwareMar 2023基于 BWDSP1042 的复数矩阵向量乘的优化与实现蔺丽华1张美春1王佳仪1李敏1门浩21(西安科技大学通信与信息工程学院陕西 西安 710054)2(西安电子科技大学电子工程学院陕西 西安 710071)收稿日期:2020 07 24。国家“核心电子器件、高端通用芯片及基础软件产品”重大专项(2012ZX01034001-001)。蔺丽华，高工，主研领域:信息系统与信息化。张美春，硕士生。王佳仪，硕士生。李敏，硕士生。门浩，硕士
2、生。摘要采用两种方法对复数矩阵向量乘进行优化，提高其在 BWDSP1042 上的运行效率。一是按列分块与减少二级循环内循环次数相结合的方法(矩阵列非 4 的倍数);二是模八寻址与减少二级循环内循环次数相结合的方法(矩阵列为 4 的倍数)。实验结果表明，采用第一种方法可缩短复数矩阵向量乘的运行周期 2 8 倍以上，第二种方法可缩短其运行周期 3 1 倍以上。关键词BWDSP1042复数矩阵向量乘按列分块模八寻址运行效率中图分类号TP391文献标志码ADOI:10 3969/j issn 1000-386x 2023 03 047OPTIMIZATION AND EALIZATION OF COM
3、PLEX MATIX VECTOMULTIPLICATION BASED ON BWDSP1042Lin Lihua1Zhang Meichun1Wang Jiayi1Li Min1Men Hao21(College of Communication and Information Engineering，Xi an University of Science and Technology，Xi an 710054，Shaanxi，China)2(College of Electronic Engineering，Xidian University，Xi an 710071，Shaanxi，C
4、hina)AbstractTwo methods were used to optimize the complex matrix vector multiplication to improve its operationefficiency on BWDSP1042 The first method was the combination of block by column and reducing the number of cyclesin the secondary cycle(applicable to the column of matrix is not a multiple
5、 of 4)The second method was a combinationof modulo-8 addressing and reducing the number of cycles in the secondary cycle(applicable to applicable to the columnof matrix is a multiple of 4)The experimental results show that the first method can shorten the operation period ofcomplex matrix vector mul
6、tiplication by more than 2 8 times，and the second method can shorten the operation period bymore than 3 1 timesKeywordsBWDSP1042Complex matrix vector multiplicationBlock by columnModulo-8 addressingOperation efficiency0引言矩阵向量乘在视频图像处理、无线通信、数学信号处理等领域应用广泛。由于矩阵向量乘计算复杂度较高，运算过程效率低，导致其在一些领域中无法满足系统实时处理的要求1
7、2。因此，提高矩阵向量乘的运算速度是十分必要的。目前，针对矩阵向量乘的研究已经十分成熟，但如何使之适应新的数字信号处理器以获得更好的性能，是目前研究的重点。针对如何高效实现矩阵向量乘，国内外做了大量研究，肖汉等3 通过将矩阵向量乘分解成若干个子任务来提高运行速度。尹孟嘉等4 通过构建性能度量模型为不同形态的矩阵选择不同的存储格式来提高算法的性能。苏锦柱等5 提出了一种基于 FPGA 的矩阵向量乘新的并行算法。以上的矩阵向量乘实现方法是针对稀疏矩阵向量乘，不具有普遍性。另外，与 FPGA 相比，DSP 具有较高的运算能力，能够实现实时处理，具有软件的灵活性，且成本相对较低，在 BWDSP1042
8、 上研究矩阵向量乘具有重要意义。第 3 期蔺丽华，等:基于 BWDSP1042 的复数矩阵向量乘的优化与实现299本文研究了复数矩阵向量乘在 BWDSP1042 处理器上的优化和实现。根据该处理器的 VLIW 和 SIMD硬件结构，使用软件流水、循环展开、指令并行的手段，结合线性寻址和模八寻址的寻址方式，针对不同矩阵，提出两种不同的优化方法以提高复数矩阵向量乘的运行效率。方法一:按列分块与减少二级循环内循环次数相结合的方法矩阵列非4 的倍数)。方法二:模八寻址和减少二级循环内循环次数相结合的方法(矩阵列为4 的倍数)。实验结果表明:这两种方法能够有效减少矩阵向量乘的运行周期，充分挖掘了 BWD
9、SP1042处理器的潜能。1BWDSP1042 处理器BWDSP1042 是中国电子科技集团公司第 38 研究所研制的首款多核处理器。其内部集成 2 个新一代处理器核 eC104+6。eC104+采用 16 发射、单指令流，多数据流架构，其处理性能与 BWDSP100 相比得到大幅提升。eC104+中有四个执行宏(x、y、z、t)，每个执行宏中存在一个寄存器组和四个运算部件 7，其中运算部件包括一个超算器(SPU)、四个移位器(SHF)、八个乘法器(MUL)、八个算数逻辑单元(ALU)。eC104+的指令总线位宽是512 位，包含两条写总线和两条读总线，且每条总线的位宽是 256 位。数据总线
10、是全双工，因此最多可同时使用三条数据总线实现数据传输。eC104+有 6 个大小为 256k 32 bit 的内存块(block)，每个内存块中包含八个 bank。内部有三个相互独立且结构相同的地址发生器。eC104+内核的结构如图 1 所示。图 1eC104+内核的结构eC104+内核是 13 级流水线结构，可分为三部分，分别为由内存驱动的取指令3 级(fe0 fe2)、指令缓冲3 级(IAB0 IAB2)、由指令驱动的 7 级流水(指令译码4 级(dc1 dc4)，取操作数1 级(ac)，指令执行1 级(ex)，指令结果写回 1 级(wb)。如图 2 所示，在水线的 dc wb 级有很多因
11、素会引起指令流水的停顿，主要因素包括数据 bank 冲突、数据相关、原子操作、分支、访问核外存储资源引发的等待、异常及程序控制指令等。图 2eC104+内核的 13 流水线结构2复数矩阵向量乘算法传统的复数矩阵向量乘由一个二级循环实现，即复数矩阵 A 中的第 t 行与向量 x 中各个元素相乘、累加，完成 yt的计算。具体过程如下所示:复数矩阵:Am n=ai11+ar11ai1n+ar1naim1+arm1aimn+armn(1)式中:i 表示虚部，r 表示实部，m 表示行，n 表示列。n 维的复数向量:x=(xi1+xr1，xi2+xr2，xin+xrn)T(2)A 与 x 相乘得复数向量
12、y:y=(yi1+yr1，yi2+yr2，yim+yrm)T(3)任意 yt满足式:yt=nl=1artlxrl aitlxil+j(aitlxrl+artlxil)(4)该传统运算方法，在 BWDSP1042 上实现具有运算效率低的问题。3复数矩阵-向量乘算法的优化与实现3 1结合硬件资源优化复数矩阵向量乘本节结合 BWDSP1042 处理器的硬件结构以及寻300计算机应用与软件2023 年址方式，使用按列分块和模八寻址两种优化方法对复数矩阵向量乘进行优化。3 1 1传统复数矩阵向量乘方法传统的复数矩阵向量乘在 BWDSP1042 中四个执行宏中读取的方法如图 3 所示。图 3传统复数矩阵向
13、量乘在四个宏中的运算此方法在 BWDSP1042 上实现的具体过程分为五步:第一步:读取数据。取复数矩阵 A 中第 1 行相邻的四个复数，以及向量中的四个复数，其虚部和实部分别存放在四个执行宏(x、y、z、t)中。第二步:计算并读取新的数据。矩阵 A 中第 1 行相邻的四个复数与向量中的四个复数相乘累加，其结果存放在累加器中。第三步:重复第二步，直至矩阵中的第一行与向量计算结束。第四步:计算 y1并保存。四个执行宏的数相加得y1，将 y1写入内存。第五步:重复第一步至第四步，计算矩阵所有的行与向量乘。直至得到复数矩阵向量乘的结果。该方法在计算过程中，y1被分为 8 部分，分别存储在四个执行宏中
14、，在乘累加计算完成后，需要额外消耗资源将不同执行宏中的数相加。为解决该问题，本文提出了按列取数的方法。3 1 2按列分块计算复数矩阵向量乘的方法在 BWDSP1042 上实现复数矩阵向量乘。可采用图 4 中对复数矩阵按列取四个复数，分别在四个执行宏中同时与向量中的复数相乘的方法。图 4按列计算复数矩阵向量乘的运算过程此方法在 BWDSP1042 上具体的实现过程如下:第一步:读取数据。读取复数矩阵中第 1 列的四个复数，读取向量中第一个复数，分别存在四个执行宏中。第二步:计算并读取新的数据。第一列的四个复数分别与向量中的第一个复数相乘，并将结果存放于累加器中。同时读取矩阵下一列的四个复数，以及
15、向量的下一个复数。第三步:重复执行第二步，直至矩阵中前四行数据与向量乘运算结束。第四步:保存数据。保存输出向量 y1 y4的值。第五步:重复第一步至第四步的计算方法，依次计算其他行，直至得到输出向量。该方法循环一次，同时从四个执行宏中输出 y1y4的值，可避免不同执行宏间数据相加的执行过程，有效地节省了运行周期。3 1 3模八寻址计算复数矩阵向量乘的方法对于按列计算复数矩阵向量乘方法，当复数矩阵的列数是 4 的倍数时，读取复数矩阵会产生 bank 冲突。bank 冲突会造成流水线停顿，在停顿的若干个cycle 内依次访问冲突的地址，直到冲突解除才恢复流水。在程序中直接体现在读取数据时，每读一次
16、数据流水线停顿两次。为了解决 bank 冲突，当复数矩阵的列数是 4 的倍数时，采用图 5 的模八寻址方式，在读取数据时，执行宏 x 读取第一行的第一个复数，执行宏 y 读取第二行的第二个复数，执行宏 z 读取第三行的第三个复数，执行宏 t 读取第四行的第四个复数，再与复数向量中的数据相乘。图 5模八寻址计算复数矩阵向量乘3 2结合软件优化技术优化复数矩阵向量乘BWDSP1042 上的软件优化技术主要包括指令并行、循环展开、软件流水三种方法8 9。指令并行主要包括两个方面:一是基于 SIMD 指令在数据级上的并行，即同时对四个执行宏中的相同的运算单元以及通用寄存器进行相同的操作，或者同时访问数据存储器;二是在一个指令行中使用多个指令槽的技术。通过指令槽将多条语句分开，使多条指令同时执行。循环展开是多次重复循环体代码，该方法通过使用大量代码以提高代码并行度和执行效率，本质上为向量化的思想，运用循环展开的方法将迭代间并行更改为迭代内并行，节省了大量的分支判断类指令与执行条件指令等资源，进而提高了代码效率。针对BWDSP1042 的处理器，按照宏内指令编排原则，仿存及运算结果间隔两周期有效，
