FPGA上的矩阵计算并行算法与结构优化

本文主要探讨了稀疏矩阵在高性能计算中的应用，并介绍了两种常见的压缩存储格式：COO（Coordinate Format）和CSR（Compressed Sparse Row）。稀疏矩阵在大数据处理中具有重要意义，尤其是在处理大规模计算问题时，可以有效减少存储需求和提高计算效率。 在COO格式中，矩阵的非零元素以三元组的形式存储，包含值、行索引和列索引。而CSR格式则是对COO格式的一种优化，通过添加额外的`row_ptr`数组记录每行非零元素的起始位置，从而节省存储空间。CSR格式特别适用于按行遍历的矩阵操作，而CSC（Compressed Sparse Column）格式则是按列压缩的版本，适合按列遍历的操作，如Matlab中采用的格式。 文章进一步提到，FPGA（Field-Programmable Gate Array）在矩阵计算中的应用。FPGA作为可重构计算平台，其并行计算能力强大，可以高效地处理矩阵计算任务。尽管如此，FPGA在实现矩阵计算时仍面临硬件编程复杂、存储和带宽需求高、可扩展性差等问题。 针对这些问题，论文作者邬贵明在国防科学技术大学攻读博士学位期间，提出了以下创新点： 1. 针对基本矩阵运算，如矩阵向量乘和矩阵乘，设计了FPGA分块矩阵乘的并行结构。通过循环分块和一系列优化，实现了数据传输和存储的高效，并降低存储需求，从原本的O(b²)降至O(b)，其中b为数据块大小。 2. 提出了FPGA上的列选主元LU分解的细粒度流水线并行算法，以及基于线性阵列的硬件实现。这个并行结构不仅适用于LU分解，还可以扩展到下三角方程组求解和多右端项的线性方程组求解，其性能优于已有工作和通用处理器的软件实现。 3. 设计了FPGA上分块稠密矩阵分解的并行算法和结构，以不选主元LU分解为例，采用分而治之的策略，结合循环分块和时空映射实现。这种方法优化了串行LU分解过程，提高了FPGA在矩阵分解任务中的效率。 这些研究成果为FPGA在大规模矩阵计算中的应用提供了新的思路和优化方案，有助于提高计算速度和资源利用率，尤其是在处理大数据和高性能计算场景时。