高适用性大维度矩阵求逆器的算法优化和实现

发布时间：2020-03-23 13:46

【摘要】：随着现代科学研究中云存储、云计算和云物联等技术的不断发展,相关的数据信息也呈现出爆炸式增长。矩阵类运算在海量数据的存储和计算中占比越来越大,矩阵求逆是其中最复杂的运算之一。国内外的学者们在不断研究探索后提出了众多有效的矩阵求逆算法,并在不同的硬件结构上得到验证与实现。求解逆矩阵的计算量庞大,硬件实现时受资源因素制约。常见矩阵求逆多以小矩阵或者特殊矩阵为对象,适用于大规模任意矩阵求逆方法研究较少,对于硬件实现更加罕见。大规模矩阵直接求逆被认为是其中最具挑战性问题之一,且不可规避。因此,探索大规模非奇异矩阵求逆的硬件实现具有重要的现实意义。本文针对上述问题,进行了有关大规模非奇异矩阵求逆算法和硬件结构设计的研究。主要工作内容如下:(1)研究分析了典型的矩阵求逆算法、适用性及运算复杂度,选择了基于LU分解的原位替换求逆算法。对原位替换矩阵求逆算法的计算公式进行修正,提出一种改进的大维度矩阵求逆算法。新算法通过主元交换和行修正操作,将应用范围扩展至非奇异矩阵,克服了既有原位替换算法适用矩阵类型有限的缺点。(2)根据新算法的运算特征,设计大维度任意阶矩阵求逆器的硬件方案。该设计延续了“原位替换”存储结构上的优点,并且采取多路并行和运算器分时复用的策略提高运算速度。(3)完成硬件实现,并在Xilinx公司FPGA芯片上进行功能验证和性能测试。硬件实测结果表明,本文设计可在332K个周期内完成128阶单精度浮点非奇异矩阵求逆任务,结果精度达10~(-5)。
【图文】：

对比图,对比图,文献,求逆算法

将所得的三角逆矩阵做矩阵乘，可以得到一个未修正恢复的逆矩阵-1A ，，如公式(3.11)所示。-1 1 1A U L (3.11)主元交换和行修正重组了源矩阵和中间过程矩阵的行向量，通过公式(3.12)可以对矩阵-1A 进行列向量恢复。先后通过乘矩阵 M 和矩阵 P 修正，从而得到初始矩阵的逆矩阵-1A 。 1 -1A A M P (3.12)3.1.2 算法优势分析本文中换主元和行修正操作将原位替换求逆算法的适用范围扩展至非奇异矩阵，而文献[33]也采用二次约化系数计算和选主元的优化方法拓宽了算法适用性。图 3.1 为本文改进的原位替换矩阵求逆算法和文献[33]中算法的运算操作次数对比折线图。图中虚线和实线分别代表本文和文献[33]，图 3.1(a)为两个矩阵求逆算法的乘法运算操作次数对比情况，图 3.1(b)为两个矩阵求逆算法的加法运算操作次数对比情况。其中，横轴表示矩阵阶数，纵轴表示运算操作次数。

示意图,矩阵乘,互连结构

合肥工业大学硕士学位论文Memory0、Memory1 都是由 8 小块存储深度为216n，数据位宽为 64bit 的Block RAM构成。Dist_mem0、Dist_mem2 都是由 8 小块存储深度为8n，数据位宽为 32bit 的分布式 RAM 构成。Dist_mem2 中存放的是行修正过程中产生的修正矩阵 M 的主对角元数据。之所以比约化系数运算过程少了一组分布式 RAM，是因为分布式 RAM 存储器Dist_mem1 中保存的数据为换主元操作时更新的标志矩阵 P 相关数据，该数据仅用于换主元的约化系数运算和求逆结果恢复模块。上、下三角逆矩阵的矩阵乘运算模式下，本文利用数据对称存储的优势采取的三角逆矩阵直接相乘的运算方式，主要的运算器为乘法器 IP 和加法器 IP，其互连结构示意图如图 4.5所示。
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：O151.21;TN791

【参考文献】