FPGA上矩阵计算的并行算法与高效实现

"这篇博士学位论文主要探讨了在大规模数据分析背景下，如何利用高性能计算（High Performance Computing, HPC）技术，特别是现场可编程门阵列（Field-Programmable Gate Array, FPGA）来优化矩阵计算。作者针对FPGA的硬件资源约束，提出了一种大规模问题映射策略，该策略在LU分解和矩阵乘法等基本矩阵运算中展现了高效性和存储效率。 论文中详细阐述了LU分解的循环分块策略。在传统的LU分解循环中，存在非紧嵌套循环的问题，这不利于进行分块和时空映射。为了克服这一难题，论文提出了预处理方法，将非紧嵌套循环转换为紧嵌套循环，通过在循环语句前添加条件分支，使得所有语句具有相同的迭代空间。接着，论文对预处理后的迭代空间进行分块，以适应FPGA的逻辑资源、Block RAM（BRAM）和数字信号处理器（DSP）资源的限制。分块的大小会在时空映射后确定，以确保计算数据能存储在FPGA的局部存储器中。 此外，论文还提出了面向FPGA的高性能、高存储效率的分块矩阵乘法并行结构。通过时空映射和模型构建，作者设计了一种自动生成并行结构的框架，并针对矩阵向量乘和矩阵乘进行了实验验证。这种并行算法利用循环分块等技术优化数据传输和存储，能够处理任意大小的数据矩阵，其存储需求从O(b^2)降低到O(b)，其中b为数据块的大小。 在LU分解方面，论文提出了FPGA上的列选主元LU分解细粒度流水线并行算法，该算法充分利用了流水线并行和数据重用，不仅适用于LU分解，还可以扩展到下三角方程组求解和多右端项的线性方程组求解。论文还设计了一个全硬件实现的线性阵列，用于并行执行LU分解和下三角方程组求解，同时给出了性能模型，以便更好地分析和预测性能。 最后，论文探讨了FPGA上的分块稠密矩阵分解并行算法和结构，特别是在不选主元的LU分解中，采用分而治之的策略，结合循环分块和时空映射，以提高并行计算的效率。 这篇论文深入研究了FPGA在矩阵计算中的应用，通过一系列优化策略和并行算法设计，显著提高了计算性能和存储效率，对于推动FPGA在HPC领域的应用具有重要的理论和实践价值。"