论文总字数：39297字

摘 要

动态可重构系统是一套以主处理器和可重构硬件为主的新型计算系统。动态可重构阵列作为动态可重构系统的主要计算核心，其计算单元的映射排布和路由结构是直接决定系统计算性能的重要因素。矩阵求逆运算作为数字信号处理中主要的运算之一，其具有广泛的应用性，较高的复杂度和大规模的计算量。因此，矩阵求逆在动态可重构系统的实现具有推动通信，电子领域发展和深度了解、完善动态可重构系统的重要意义。本文以动态可重构系统和矩阵求逆作为主要研究对象，以提升计算效率，减少计算周期为主要目标，着重讲述矩阵求逆映射方案选择和阵列路由结构的改进。

本文从矩阵求逆的数据流特性入手，着重分析矩阵求逆的数据流图，深度挖掘动态可重构阵列的特性，实现基本的矩阵求逆映射方案，并在此基础上发掘映射方案中存在的问题，以出现的问题为针对对象，转化为设计目标并对矩阵求逆算子作出改进映射方案。对阵列路由结构中存在的不利于矩阵求逆的结构进行改进调整。主要包括以下三个部分：①从线性代数的角度对矩阵求逆进行分析，基于分析得到了基本计算流程和数据流图。选择LU分解法作为矩阵求逆的方法。对动态可重构阵列的深度挖掘，展开了矩阵求逆算子的基本映射，为后续的工作提供理论基础；②根据基本映射方案中存在的问题提出三个设计目标：提高阵列单元利用率，提高流水程度以及提高数据读取存储利用率。根据设计目标，对重构计算阵列内的通用阵列进行修改。针对LU分解方案中提出二级乘-减的单元组合。针对三角矩阵求逆中选择二级乘-加的单元组合。针对矩阵相乘中选用二级乘-加到累加阵列的步骤。根据上述映射方案给出周期计算的具体公式；③针对通用阵列-累加阵列间出现的流水气泡过多，数据读取效率过低的问题，本文提出通用阵列一分为三的设计方案，使三个通用阵列独立工作和读取。改进后的动态可重构系统显著提升了流水线性能并且增加了数据读取效率。

本文针对动态可重构系统在C模型和RTL级做了功能性验证，结果表明：本文所述的矩阵求逆改进映射方案在基本方案的基础之上，计算单元利用率理论上保持在90%以上，流水程度提升1~2倍，数据读取存储效率提升1~2倍。本文所述的三个通用阵列结构极大地提升了映射方案与阵列的匹配度。在改进映射方案的基础之上，计算单元利用率理论可保持在90%～100%，流水程度提升30%~70%，数据读取存储效率提升1倍。

关键词：矩阵求逆，可重构，信号处理，路由结构

The Mapping and Optimization of

Matrix Operation based on

Dynamic Reconfigurable System

Abstract

Dynamic Reconfigurable System(DRS) is a new computer architecture which is mainly combined with main processor and reconfigurable hardcore. Array is the main processor of DRS and basis mapping arrangement on it and the structure of the route of it are two main factors to determine the performance of the calculation. As one of the most important domains in DSP, matrix inversion has worldwide uses, high complexity and needs large volume of calculation. Hence the implementation of matrix inversion on DRS is supposed to promote network and electronic engineering, understand deeply and develop DRS. In this thesis we focus on DRS and matrix inversion. The design of mapping arrangement and the development in the structure of the route are discussed with the main goal of improvement in the performance of calculation.

The implementation method using data flow function of matrix inversion and deep research on DRS is discussed in the thesis. Then problem in method is discussed to firstly establish design goals and then based on this goals to improve the performance of matrix inversion mapping on DRS and the structure of the route. First, mathematically analysis of matrix inversion firmly supports the basic calculation steps and data flow function. LU method is selected as the method for matrix inversion in DRS. Through deep research of DRS and first mapping of matrix inversion in DRS, the ground is built firmly for further research. Second, according to some problems in first mapping, goals are made: To improve units uses, pipeline efficiency and efficiency of loading and saving data in DRS. In this thesis we have made several changes inside mapping of General Array. For example, two combined units, multiply unit as well as minus unit, is designed for LU decomposition. Three combined units, two multiply units and a single add unit for triangle matrix inversion. Three combined units, two multiply units and a single add unit also for matrix multiply with Accumulation Array. Cycle calculation and evaluation are discussed later. Third, to make pipeline faster between General Array and Accumulation Array and improve efficiency of loading and saving, a new structure of the route is raised. It divides General Array into three and allows this three arrays to work together. The new structure makes pipeline faster and increase the speed of loading and saving.

The experimental results show that compared to first mapping, proposed advanced mapping can use 90 percent units simultaneously. The performance of pipeline improves 1 to 2 times and that of loading and saving improves 1 to 2 times also. Compared to advanced mapping, new structure of the route could use at least 90 percent units simultaneously, making improvement between 30 percent and 70 percent in pipeline and 1 time in loading and saving.

Keywords: matrix inversion, reconfigurable, signal processing, structure of route

目录

摘要 I

Abstract II

目录 III

第一章 绪论 1

1.1 研究背景 1

1.2 国内外研究现状 2

1.3 论文研究内容及意义 3

1.4 论文组织结构 4

第二章 矩阵运算原理概述及算法特征分析 5

2.1 矩阵求逆运算基本介绍 5

2.2 矩阵求逆算法分析与数据流图 7

2.3 动态可重构系统介绍 10

2.4 基于动态可重构系统的矩阵求逆运算基本映射方案和问题 13

2.4.1 基于可重构系统与可重构阵列级别的矩阵求逆算子映射方案 13

2.4.2 基于阵列级别的矩阵求逆算子映射方案 15

2.5 本章小节 18

第三章 基于动态可重构系统的矩阵求逆算子映射方案优化 19

3.1 基于动态可重构系统的矩阵求逆运算基本流程简介 19

3.2 基于动态可重构系统的矩阵求逆算子映射优化方案 20

3.2.1 矩阵求逆算子的映射方案设计目标 20

3.2.2 矩阵求逆算子映射优化方案的周期对比 23

3.3 基于映射方案的动态可重构阵列路由结构改进 26

3.3.1 基于动态可重构系统的矩阵求逆理想映射方案 26

3.3.2 基于矩阵求逆理想映射方案的阵列路由结构改进 27

3.3.3 基于改进动态可重构阵列的矩阵求逆映射方案的周期对比 30

3.4 本章小结 31

第四章 实验结果与分析 33

4.1 面向矩阵求逆算子的动态可重构系统仿真验证平台 33

4.2 实验结果与分析 34

4.3 本章小结 35

第五章 总结与展望 37

5.1 全文总结 37

5.2 展望 37

致谢 39

参考文献 41

绪论

随着通信、计算机、微电子等领域技术的飞速发展，各类应用系统对数字信号处理能效性、数据吞吐率以及系统响应延迟等关键指标的要求越来越高。关键指标的微小提升可以对应用系统的效率产生巨大影响。矩阵类运算是数字信号处理中的一个重要算子。它在通信领域，雷达成像，图像处理中起到核心作用。而矩阵运算包含矩阵加法，矩阵减法，矩阵求逆，矩阵乘法等一系列相关运算。并且目前应用性最强，影响力最深而有涉及到矩阵的相关运算就是矩阵求逆。因此，深刻研究矩阵求逆不仅对矩阵其他运算的研究有促进作用，为研究其余矩阵运算提供了正确的思路和方向，更是有极强的实际应用价值。而且矩阵求逆的运算中分成几个小步骤，每个小步骤都涉及到了矩阵加法，矩阵乘法等，单独研究矩阵求逆运算本身本就涉及到了矩阵所有运算的方方面面。

为实现矩阵求逆算法，若采用传统的解决方案，很难同时在计算性能与算法灵活性上获得满意。ASIC是标准定制电路，灵活性差，不能兼容各类阶数的矩阵类运算。CPU/GPU作为指令流处理，计算效率差，不能应对实时计算需求。FPGA具有一定的系统灵活性、有具备高能效、高计算效率，但由于计算粒度为bit级，配置信息冗余，硬件浪费严重。近年来，可重构架构处理器被广泛应用于通信、媒体等众多领域。动态可重构计算不仅可以保证灵活性，适用于多种算法，同时也可以提供高效的计算性能，并且硬件利用率高，配置信息相对简单。

剩余内容已隐藏，请支付后下载全文，论文总字数：39297字