下三角复矩阵求逆的ASIC设计及实现
熊洋 郑建宏 重庆邮电大学 400065
摘要：本论文提出了一种便于ASIC实现的矩阵求逆算法，可以完成对1到16维下三角复矩阵的求逆运算，并用Verilog硬件描述语言进行实现。利用SMIC 0.13um工艺库和Synopsys公司的Design Compiler工具对代码进行了综合，并进行了低功耗优化，最后使用Modelsim工具对代码进行了仿真验证，得到的结果同C代码模拟的结果完全一致，证明本模块完全可以达到预期目的。
关键词：ASIC；矩阵求逆；下三角复矩阵；Verilog；综合；仿真
ASIC Designing and Implementation of Lower
Triangular Complex Matrix Inverse
Xiong Yang Zheng Jianhong
Chong Qing University of Posts and Telecommunications 400065
Abstract：This Paper presents a kind of matrix inverse arithmetic suitable for ASIC implementation, which could process 1~16 dimension lower triangular complex matrix, and is coded by Verilog HDL. Using SMIC 0.13um process library，we synthesis the codes by Design Compiler and optimize the power. At last, we verify the function of the module using Modelsim, and the result of Modelsim simulation is consonant with c code simulation, which prove that our module achieve anticipative goals.
Key words：ASIC；matrix inverse；lower triangular complex matrix；Verilog；Synthesis；simulation 1、概述
矩阵运算是很多科学运算和工程运用中的常见运算，大多数科学计算都可以归结为矩阵问题，在实际工程项目中更是如此。而矩阵求逆更是矩阵运算中一种相当重要的运算，在数字信号处理中常常被用到。
为了不失通用性，本论文针对的矩阵元素采用复数表示。为了简化处理流程，通常先会将某个矩阵进行分解，例如LU分解，得到两个三角矩阵，再将下三角矩阵（上三角矩阵亦可通过转置运算变换为下三角矩阵）置入本设计模块进行求逆。
硬件设计通常需要在速度（时钟）和资源（面积）之间做一个权衡，随着制造工艺向超深亚微米的过渡，soc可以运行在更快的时钟频率之下。在这种情况下，将求逆运算固化到硬件上，可以充分利用硬件速度快的特点，对数据进行高速有效的处理。文献[5]提到的心动阵列处理方法是一种并行处理方法，它是以牺牲资源为代价来达到节省时间的目的。在处理速率满足要求的前提下，硬件设计者应当考虑如何最大限度地节省资源，采用串行处理的方式不失为一种好的选择。
基于如上考虑，本论文将针对1~16维的下三角复矩阵设计一个求逆模块，并用Verilog 硬件描述语言进行实现，数据的处理采用串行处理的方式，并利用流水线以节约时钟开销。
2、算法及其实现概述
设矩阵A为下三角矩阵， 是A的逆矩阵，n是A的维数：
10E=
000100............00
=A×A−1=01
a11a21...an1
0a22...an2
.........0b110b
×21......
bn1
b22...bn2
.........00
...
...ann...bnn
根据矩阵乘法：ci,j=
∑(a
k=j
i
i,k
×bk,j) （j
而：ci,j=0（i≠j）； ci,j=1 ( i=j )
（i=1,2,…,n） ……(1) 由上可知，首先可以求得一些初始值：bi,i=1/ai,i，
然后可得出计算 其他值的递推公式：
bi,j
1
=−
ai,i
∑(a
k=j
i−1
i,k
×bk,j) =−bi,i∑(ai,k×bk,j)（i=1,2,…,n ; j=1,2….,i-1）……(2)
k=j
i−1
通过对上面算法的阐述，我们可以发现，由于该算法是采用递推方式实现，正好符合串行处理的特点，再利用流水线的思想的话，应该是一种很好的方案。
具体的说，通过式（2）计算每一个具体的过当前行数控制的组合逻辑得到；而换；
bi,j
ai,k
时，其中的
bi,i
在进入每一行时，可以通
可以通过和当前写地址一样的读地址从INV_inbuf
（输入存储器）重新读出，在计算每个具体的
bi,j
bk,j
时，保存一次，因为要涉及累加地址的转
是在每次从写了对角线上的值后，向左跳转时赋了初值，由于一系列
bk,j
的实质就
是三角阵b中的一列，所以他们地址之间的关系是增量再递增1的关系，而每次向左跳转时，
bk,j
的地址增量也是这个关系。当计算到每一行的第一列所有累加完毕后，写地址就要跳到对于除法器的输入，被除数使用32’b3FFF_FFFF表示“1”。
下一列对角线上，这些就是读写地址变换的规律。 3、HDL实现架构
图1 矩阵求逆模块架构
上图1是矩阵求逆模块的HDL实现架构。首先，矩阵的大小信息，即模值被写入mi_ctrl寄存器，然后在Dsp控制信号的控制下，待进行转置运算的三角矩阵被写入输入存储器（INV_inbuf），当mi_ctrl的求逆控制位被置“1”，模块开始进行求逆操作。求逆完成后mi_ctrl的求逆控制位被置回“0”，求逆的结果被存入输出存储器（INV_outbuf）。求逆结束后，接
口模块会发出一个中断信号，当Dsp收到中断信号后，在Dsp控制信号的控制下，INV_outbuf中的求逆结果可被读出。 4、提高精度的策略
在对数据的处理过程中，溢出是必然的，比如两个16位数据相乘，从乘法器出来的结果应该是32位，但结果应该是16位的。为保证精度，本设计对中间数据的处理结果并没有直接取舍，比如一个乘加复合运算，乘法的结果暂时取为32位，做了加法之后再取舍。
其次，输入本模块的数据有可能大小不一，甚至出现所有数据的前几位都为零的情况（最高位不计，为符号位），针对这种情况，本论文会在将数据存入存储器的同时，对数据进行归一化处理，旨在提高精度。 5、 资源占用
本设计选用两个256×32的存储器，分别用于输入（inbuf）和输出（outbuf），在存储器里，实部放高16位，虚部放低16位。 6、 时间消耗
对于模值为N（1≤N≤16）的下三角矩阵，由于采用的是流水线设计，其存入inbuf时间为(1+N)×N/2个clk，从收到MI_CTRL[4]的启动信号算起，到发出求逆完毕中断止，需要A＋B个clk，其中A为计算归一化移位位数的时间，N≤A≤N+15，B为矩阵求逆时间，B≡1+N+5×N×(N−1)÷2。 7、DC综合
DC（Design Compiler）是Synopsys公司发布的ASIC综合工具，是业界最流行的综合工具之一。它根据设计描述和约束条件并针对特定的工艺库自动综合出一个优化的门级电路。它可以产生多种性能报告，在缩短设计时间的同时提高设计性能。
通过DC可以对代码进行一系列功耗方面的优化，包括插入门控时钟和多阈值处理。本文采用SMIC 0.13um工艺库对代码进行综合和优化。
图2 DC的门控时钟报告
上图2是DC插入门控时钟的报告，从图中可以看出代码的大部分寄存器（98.48％）都可以插入门控时钟，这样可以在空闲的时间段关掉时钟源，消除该段时间由时钟翻转导致触发器产生的动态功耗。
图3 多阈值处理前（上图）后（下图）模块功耗对比
上图3是多阈值处理前后的功耗对比，从图中可以明显的看出经多阈值处理过后，模块
的动态和静态功耗都有大幅度的降低，其中动态功耗降低20.6％，静态功耗降低13.8％。 8、Modelsim仿真
为方便读者观察波形，这里以一个三维下三角复矩阵为例。
图4 求逆最后阶段：求逆结果被顺次写入存储器的仿真波形片断
上图4是Modelsim的一个仿真波形片断，该片断还清晰地表现了流水线的思想。传统的数据处理方法是读一个数据，经过计算再写出一个数据；而在流水线方式下，输入和输出可以不间断地进行。qb_out是计算模块向存储器out_buf写数据的信号，计算模块对数据求逆的结果通过该信号线被顺次写入out_buf，求逆结束后，寄存器miff被置1，但向存储器写数据的过程并没有停止。
通过对测试程序的处理，写入存储器的数据可以导出到一个外部文件，下图5 是原三角矩阵、Modelsim仿真结果、c代码求逆结果（归一化）的比较图，数据采用的是16进制表示，高位为虚部，低位为实部。除此之外的1到16维下三角矩阵，笔者也都一一进行了验证，限于篇幅这里不再赘述。
图5 原三角矩阵、Modelsim仿真结果、c代码求逆结果（归一化）的比较图
9、结束语
本文提出了一种下三角复矩阵求逆算法，并通过Verilog HDL进行实现，同时利用流水线的思想提升了模块的处理速度。模块还具有1～16维矩阵选择能力，具有一定通用性。通过DC综合，进一步对代码进行了优化，模块具有低功耗的特点。最后通过Modelsim仿真，对模块的功能进行了验证。
参考文献：
[1] 夏宇闻. Verilog数字系统设计教程. 北京航空航天大学出版社, 2004.
[2] Design Compiler Reference Manual: Optimization and Timing Analysis. SYNOPSYS. 2007,3. [3] Design Compiler Reference Manual: Constraints and Timing. SYNOPSYS. 2007,3. [4] ModelSim SE User’s Manual. Mentor Graphics. 2005,4.
[5] 王前, 吴淑泉 等. 三角矩阵求逆的ASIC实现研究[J]. 微电子学与计算机. 2004, 21(8), 135-136.
[6] 徐建,郑建宏. TD-SCDMA中Viterbi译码器的硬件设计与实现[J]，微计算机信息 , 2007,(17) .
本文作者创新点：提出的下三角矩阵求逆算法特别适于ASIC硬件实现，考虑了复数的情况，并可以通过软件编程控制矩阵的维数，使用verilog HDL进行编码实现时，运用了流水线技术，大幅提高了模块的吞吐速度，这些特点在国内同方向论文中属首次提出。在对代码进行后端实现时，通过多种方式的综合优化，使得模块具有低功耗的特点，具有一定创新性。
作者简介：熊洋（1982－），男，重庆人，重庆邮电大学通信专业硕士研究生，研究方向为第三代移动通信，现在重邮信科3G研究院从事芯片后端设计工作。
郑建宏（1961－），男，四川人，重庆邮电大学通信专业教授，博士生导师，研究方向为第三代移动通信，TD-SCDMA 3G手机开发。
Biography: Xiong Yang (1982－), male, Chongqing, Chong Qing University of Posts and Telecommunications, Post Graduate student, majoring in the 3rd Mobile communication system, chip backend designing of ASIC in CQCYIT.
Zheng Jianhong (1961－), male, Sichuan, Chong Qing University of Posts and Telecommunications, professor, PhD tutor, Research in the area of the 3rd Mobile communication system, Researching and Development of TD-SCDMA 3G mobile. 中图法分类号：TP302 文献标识码：A
基金项目：国家高技术研发发展计划（863）2004AA123150
下三角复矩阵求逆的ASIC设计及实现
熊洋 郑建宏 重庆邮电大学 400065
摘要：本论文提出了一种便于ASIC实现的矩阵求逆算法，可以完成对1到16维下三角复矩阵的求逆运算，并用Verilog硬件描述语言进行实现。利用SMIC 0.13um工艺库和Synopsys公司的Design Compiler工具对代码进行了综合，并进行了低功耗优化，最后使用Modelsim工具对代码进行了仿真验证，得到的结果同C代码模拟的结果完全一致，证明本模块完全可以达到预期目的。
关键词：ASIC；矩阵求逆；下三角复矩阵；Verilog；综合；仿真
ASIC Designing and Implementation of Lower
Triangular Complex Matrix Inverse
Xiong Yang Zheng Jianhong
Chong Qing University of Posts and Telecommunications 400065
Abstract：This Paper presents a kind of matrix inverse arithmetic suitable for ASIC implementation, which could process 1~16 dimension lower triangular complex matrix, and is coded by Verilog HDL. Using SMIC 0.13um process library，we synthesis the codes by Design Compiler and optimize the power. At last, we verify the function of the module using Modelsim, and the result of Modelsim simulation is consonant with c code simulation, which prove that our module achieve anticipative goals.
Key words：ASIC；matrix inverse；lower triangular complex matrix；Verilog；Synthesis；simulation 1、概述
矩阵运算是很多科学运算和工程运用中的常见运算，大多数科学计算都可以归结为矩阵问题，在实际工程项目中更是如此。而矩阵求逆更是矩阵运算中一种相当重要的运算，在数字信号处理中常常被用到。
为了不失通用性，本论文针对的矩阵元素采用复数表示。为了简化处理流程，通常先会将某个矩阵进行分解，例如LU分解，得到两个三角矩阵，再将下三角矩阵（上三角矩阵亦可通过转置运算变换为下三角矩阵）置入本设计模块进行求逆。
硬件设计通常需要在速度（时钟）和资源（面积）之间做一个权衡，随着制造工艺向超深亚微米的过渡，soc可以运行在更快的时钟频率之下。在这种情况下，将求逆运算固化到硬件上，可以充分利用硬件速度快的特点，对数据进行高速有效的处理。文献[5]提到的心动阵列处理方法是一种并行处理方法，它是以牺牲资源为代价来达到节省时间的目的。在处理速率满足要求的前提下，硬件设计者应当考虑如何最大限度地节省资源，采用串行处理的方式不失为一种好的选择。
基于如上考虑，本论文将针对1~16维的下三角复矩阵设计一个求逆模块，并用Verilog 硬件描述语言进行实现，数据的处理采用串行处理的方式，并利用流水线以节约时钟开销。
2、算法及其实现概述
设矩阵A为下三角矩阵， 是A的逆矩阵，n是A的维数：
10E=
000100............00
=A×A−1=01
a11a21...an1
0a22...an2
.........0b110b
×21......
bn1
b22...bn2
.........00
...
...ann...bnn
根据矩阵乘法：ci,j=
∑(a
k=j
i
i,k
×bk,j) （j
而：ci,j=0（i≠j）； ci,j=1 ( i=j )
（i=1,2,…,n） ……(1) 由上可知，首先可以求得一些初始值：bi,i=1/ai,i，
然后可得出计算 其他值的递推公式：
bi,j
1
=−
ai,i
∑(a
k=j
i−1
i,k
×bk,j) =−bi,i∑(ai,k×bk,j)（i=1,2,…,n ; j=1,2….,i-1）……(2)
k=j
i−1
通过对上面算法的阐述，我们可以发现，由于该算法是采用递推方式实现，正好符合串行处理的特点，再利用流水线的思想的话，应该是一种很好的方案。
具体的说，通过式（2）计算每一个具体的过当前行数控制的组合逻辑得到；而换；
bi,j
ai,k
时，其中的
bi,i
在进入每一行时，可以通
可以通过和当前写地址一样的读地址从INV_inbuf
（输入存储器）重新读出，在计算每个具体的
bi,j
bk,j
时，保存一次，因为要涉及累加地址的转
是在每次从写了对角线上的值后，向左跳转时赋了初值，由于一系列
bk,j
的实质就
是三角阵b中的一列，所以他们地址之间的关系是增量再递增1的关系，而每次向左跳转时，
bk,j
的地址增量也是这个关系。当计算到每一行的第一列所有累加完毕后，写地址就要跳到对于除法器的输入，被除数使用32’b3FFF_FFFF表示“1”。
下一列对角线上，这些就是读写地址变换的规律。 3、HDL实现架构
图1 矩阵求逆模块架构
上图1是矩阵求逆模块的HDL实现架构。首先，矩阵的大小信息，即模值被写入mi_ctrl寄存器，然后在Dsp控制信号的控制下，待进行转置运算的三角矩阵被写入输入存储器（INV_inbuf），当mi_ctrl的求逆控制位被置“1”，模块开始进行求逆操作。求逆完成后mi_ctrl的求逆控制位被置回“0”，求逆的结果被存入输出存储器（INV_outbuf）。求逆结束后，接
口模块会发出一个中断信号，当Dsp收到中断信号后，在Dsp控制信号的控制下，INV_outbuf中的求逆结果可被读出。 4、提高精度的策略
在对数据的处理过程中，溢出是必然的，比如两个16位数据相乘，从乘法器出来的结果应该是32位，但结果应该是16位的。为保证精度，本设计对中间数据的处理结果并没有直接取舍，比如一个乘加复合运算，乘法的结果暂时取为32位，做了加法之后再取舍。
其次，输入本模块的数据有可能大小不一，甚至出现所有数据的前几位都为零的情况（最高位不计，为符号位），针对这种情况，本论文会在将数据存入存储器的同时，对数据进行归一化处理，旨在提高精度。 5、 资源占用
本设计选用两个256×32的存储器，分别用于输入（inbuf）和输出（outbuf），在存储器里，实部放高16位，虚部放低16位。 6、 时间消耗
对于模值为N（1≤N≤16）的下三角矩阵，由于采用的是流水线设计，其存入inbuf时间为(1+N)×N/2个clk，从收到MI_CTRL[4]的启动信号算起，到发出求逆完毕中断止，需要A＋B个clk，其中A为计算归一化移位位数的时间，N≤A≤N+15，B为矩阵求逆时间，B≡1+N+5×N×(N−1)÷2。 7、DC综合
DC（Design Compiler）是Synopsys公司发布的ASIC综合工具，是业界最流行的综合工具之一。它根据设计描述和约束条件并针对特定的工艺库自动综合出一个优化的门级电路。它可以产生多种性能报告，在缩短设计时间的同时提高设计性能。
通过DC可以对代码进行一系列功耗方面的优化，包括插入门控时钟和多阈值处理。本文采用SMIC 0.13um工艺库对代码进行综合和优化。
图2 DC的门控时钟报告
上图2是DC插入门控时钟的报告，从图中可以看出代码的大部分寄存器（98.48％）都可以插入门控时钟，这样可以在空闲的时间段关掉时钟源，消除该段时间由时钟翻转导致触发器产生的动态功耗。
图3 多阈值处理前（上图）后（下图）模块功耗对比
上图3是多阈值处理前后的功耗对比，从图中可以明显的看出经多阈值处理过后，模块
的动态和静态功耗都有大幅度的降低，其中动态功耗降低20.6％，静态功耗降低13.8％。 8、Modelsim仿真
为方便读者观察波形，这里以一个三维下三角复矩阵为例。
图4 求逆最后阶段：求逆结果被顺次写入存储器的仿真波形片断
上图4是Modelsim的一个仿真波形片断，该片断还清晰地表现了流水线的思想。传统的数据处理方法是读一个数据，经过计算再写出一个数据；而在流水线方式下，输入和输出可以不间断地进行。qb_out是计算模块向存储器out_buf写数据的信号，计算模块对数据求逆的结果通过该信号线被顺次写入out_buf，求逆结束后，寄存器miff被置1，但向存储器写数据的过程并没有停止。
通过对测试程序的处理，写入存储器的数据可以导出到一个外部文件，下图5 是原三角矩阵、Modelsim仿真结果、c代码求逆结果（归一化）的比较图，数据采用的是16进制表示，高位为虚部，低位为实部。除此之外的1到16维下三角矩阵，笔者也都一一进行了验证，限于篇幅这里不再赘述。
图5 原三角矩阵、Modelsim仿真结果、c代码求逆结果（归一化）的比较图
9、结束语
本文提出了一种下三角复矩阵求逆算法，并通过Verilog HDL进行实现，同时利用流水线的思想提升了模块的处理速度。模块还具有1～16维矩阵选择能力，具有一定通用性。通过DC综合，进一步对代码进行了优化，模块具有低功耗的特点。最后通过Modelsim仿真，对模块的功能进行了验证。
参考文献：
[1] 夏宇闻. Verilog数字系统设计教程. 北京航空航天大学出版社, 2004.
[2] Design Compiler Reference Manual: Optimization and Timing Analysis. SYNOPSYS. 2007,3. [3] Design Compiler Reference Manual: Constraints and Timing. SYNOPSYS. 2007,3. [4] ModelSim SE User’s Manual. Mentor Graphics. 2005,4.
[5] 王前, 吴淑泉 等. 三角矩阵求逆的ASIC实现研究[J]. 微电子学与计算机. 2004, 21(8), 135-136.
[6] 徐建,郑建宏. TD-SCDMA中Viterbi译码器的硬件设计与实现[J]，微计算机信息 , 2007,(17) .
本文作者创新点：提出的下三角矩阵求逆算法特别适于ASIC硬件实现，考虑了复数的情况，并可以通过软件编程控制矩阵的维数，使用verilog HDL进行编码实现时，运用了流水线技术，大幅提高了模块的吞吐速度，这些特点在国内同方向论文中属首次提出。在对代码进行后端实现时，通过多种方式的综合优化，使得模块具有低功耗的特点，具有一定创新性。
作者简介：熊洋（1982－），男，重庆人，重庆邮电大学通信专业硕士研究生，研究方向为第三代移动通信，现在重邮信科3G研究院从事芯片后端设计工作。
郑建宏（1961－），男，四川人，重庆邮电大学通信专业教授，博士生导师，研究方向为第三代移动通信，TD-SCDMA 3G手机开发。
Biography: Xiong Yang (1982－), male, Chongqing, Chong Qing University of Posts and Telecommunications, Post Graduate student, majoring in the 3rd Mobile communication system, chip backend designing of ASIC in CQCYIT.
Zheng Jianhong (1961－), male, Sichuan, Chong Qing University of Posts and Telecommunications, professor, PhD tutor, Research in the area of the 3rd Mobile communication system, Researching and Development of TD-SCDMA 3G mobile. 中图法分类号：TP302 文献标识码：A
基金项目：国家高技术研发发展计划（863）2004AA123150