FPGA矩阵计算并行算法与结构

发布时间：2020-04-13 21:05

【摘要】：可重构计算是一种基于定制硬件实现的计算形式,现场可编程门阵列(FPGA)便是典型的可重构计算平台。近年来,FPGA芯片集成了越来越多的硬件资源,提供了强大的计算能力,可重构计算领域已渐渐步入可重构超级计算的时代。矩阵计算是科学和工程应用的核心问题,FPGA可重构计算系统在加速矩阵计算方面具有巨大的潜力。然而,FPGA实现矩阵计算还面临着硬件编程、并行算法设计、硬件结构优化等挑战,已有的矩阵计算硬件结构占用了大量FPGA资源、存储需求太高、带宽需求过大,可扩展性也很差。为应对这些问题和挑战,本文对矩阵计算的FPGA实现技术进行了深入的研究。本文的主要工作和创新点如下: (1)提出了面向基本矩阵运算的FPGA设计方法和高性能、高存储效率分块矩阵乘并行结构。以矩阵向量乘和矩阵乘为例,研究了矩阵计算FPGA实现技术中的时空映射和模型构建方法,实验评测验证了这两种基本矩阵运算并行结构的自动生成框架。利用包括循环分块在内的一系列变换和优化,推导出数据传输优化、存储优化的分块矩阵乘并行算法,得到了一种能够处理任意数据规模矩阵的高性能、高存储效率的矩阵乘并行结构。实验结果表明该并行结构优于相关工作,且存储需求从O(b2)降到了O(b),b为数据块大小。 (2)提出了FPGA列选主元LU分解细粒度流水线并行算法和实现该算法的线性阵列。提出的并行算法能够充分开发LU分解中的流水线并行和数据重用,可以扩展到下三角方程组求解和多右端项的线性方程组求解问题。本文提出了FPGA全硬件实现稠密线性方程组求解的并行结构,结构的核心是实现该并行算法的线性阵列,线性阵列可以同时实现列选主元LU分解和下三角方程组求解。本文还给出了该并行结构的性能模型,从而可以更好地分析和预测其性能。实验结果表明该并行结构优于相关工作和通用处理器的软件实现。 (3)提出了FPGA分块稠密矩阵分解的并行算法和并行结构。以不选主元LU分解为例,提出了一种分而治之的稠密矩阵分解分块策略和FPGA实现方法。该策略对串行LU分解应用包括循环分块、时空映射在内的一系列变换,推导出能够处理任意规模矩阵的分块LU分解并行算法。主要思想是把LU分解算法分解成细粒度计算任务,细粒度任务能够直接映射到FPGA实现的线性阵列,这些任务按照正确的顺序在线性阵列上执行。提出了实现该算法的高性能、高存储效率分块LU分解并行结构。与需要两组线性阵列的结构相比,该结构仅需要一组线性阵列,且存储需求从O(b2)降到了O(b),b为数据块大小。本文还把该分块策略和实现方法扩展到了多FPGA系统,并应用到Cholesky分解。实验结果表明,提出的并行结构计算效率高于通用处理器。 (4)提出了两种稀疏矩阵LU分解并行算法和实现这些算法的并行结构。稀疏矩阵LU分解的数值计算是直接法求解稀疏线性方程组过程中最耗时的一部分,本文提出了两种稀疏矩阵LU分解并行算法:Right-Looking (RL) LU分解并行算法和Left-Looking (LL) LU分解并行算法。前者能够通过开发分解因子的数据重用来减少数据传输,后者能够通过动态相关性检测来开发更多的并行性;两种算法对应的并行结构都能够动态生成分解因子的数据结构。实验结果表明,LL LU分解的并行结构的性能优于RL LU分解的并行结构和通用处理器的软件实现。 (5)提出了新颖的稀疏矩阵向量乘(SpMV)并行结构和共轭梯度法(CG)并行结构。迭代法的计算量往往都集中在处理SpMV,本文对SpMV并行结构进行了深入的研究,并应用到了CG的FPGA实现。提出了一种适合于FPGA设计的稀疏矩阵分块方法和存储格式,基于该存储格式的SpMV并行结构可以有效处理任意大型稀疏矩阵。与相关工作相比,本文提出的两种高效的SpMV并行结构无需改变任何设计参数便可以处理任意矩阵,其中一种结构可以有效减少零的填充。实验结果表明,提出的SpMV并行结构的性能优于相关工作和通用处理器的软件实现;提出的CG并行结构的性能也优于通用处理器的软件实现。
【图文】：

布尔函数

值表的直接硬件实现，下面以一个 3 输入的 LUT 为例来说其原入 LUT 实现了布尔函数 f(a, b, c) = a AND (b OR c)，a、b 和入的值，LUT 选择图中左边一列数的值（这些值实际上存储在基储器中），如果输入为 000、001、010、011 和 100，输出均为101、110 和 111，则输出均为 1，从而实现了布尔函数 f(a, b, c)。

器件,布尔函数,硬件实现

值表的直接硬件实现，，下面以一个 3 输入的 LUT 为例来说其原入 LUT 实现了布尔函数 f(a, b, c) = a AND (b OR c)，a、b 和入的值，LUT 选择图中左边一列数的值（这些值实际上存储在基储器中），如果输入为 000、001、010、011 和 100，输出均为101、110 和 111，则输出均为 1，从而实现了布尔函数 f(a, b, c)。
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：TP338.6;TN791

【相似文献】