基于FPGA并行加速的稀疏矩阵求解方法

摘要

本发明提供的基于FPGA并行加速的稀疏矩阵求解方法，通过对稀疏矩阵进行分解、对下三角矩阵对角线元素取倒数、根据数据依赖关系对数据进行分割分配、并对每个处理单元内的数据进行排布、依据排布的运算顺序采用精确的节拍级硬件资源调度进行计算，从而实现高度融合的软硬件协同加速、稀疏矩阵求解的细粒度并行流水，有效解决了现有技术中存在的处理效率低、浪费计算资源、甚至无法进行计算的问题，节省计算资源、提高处理效率。

说明书

技术领域

本发明涉及数据处理技术领域，尤其涉及基于FPGA并行加速的稀疏矩阵求解方法。

背景技术

在电力系统仿真中，电磁暂态仿真是主要的系统仿真应用之一，也是电力系统安全分析和运行的关键组件。在该应用中，其核心算法是对大规模线性方程组Ax＝b的求解。同时，通过对实际数据的分析可知，线性方程组中的系数矩阵A通常为稀疏矩阵，电力系统大型稀疏矩阵的稠密度通常小于1％，如果不能有效的利用矩阵的稀疏性，在使用计算机处理大型稀疏矩阵操作时会把大量的存储和计算资源浪费在无效的零元上，导致处理效率低下缓慢，并且部分超大规模稀疏矩阵甚至无法使用传统的稠密矩阵算法来进行求解。

发明内容

本发明提供的基于FPGA并行加速的稀疏矩阵求解方法，以解决现有技术中存在的处理效率低、浪费计算资源、甚至无法进行计算的问题，从而实现高度融合的软硬件协同加速、稀疏矩阵求解的细粒度并行流水，节省计算资源、提高处理效率。

为解决上述技术问题，本发明提供的技术方案为：

本发明提供的一种基于FPGA并行加速的稀疏矩阵求解方法，包括若干处理单元，包括：

对稀疏矩阵A进行LU分解得到上三角矩阵U和下三角矩阵L稀疏线性方程组Ax＝b的求解转换为上、下三角矩阵的线性方程组Ux＝y和Ly＝b的求解；

对上三角矩阵U的对角线元素取倒数；

依据上三角矩阵U和下三角矩阵L中的数据依赖关系分别进行分割为若干计算域，每个计算域由一个处理单元负责计算；

依据数据的依赖和冲突关系，对每个处理单元负责计算的计算域内乘法及加减法运算顺序进行排布；

每个处理单元按照排布后的运算顺序进行计算；

其中，在处理单元按照排布后的运算顺序进行计算的过程中，当不同的处理单元之间的非零元存在依赖关系时，处理单元将计算结果传输给与之有依赖关系的另一处理单元。

本发明提供的基于FPGA并行加速的稀疏矩阵求解方法，优选地，所述处理单元包括计算单元、存储单元和通信单元；

所述“处理单元按照排布后的运算顺序进行计算”包括：

按照排布后的运算顺序，计算单元读取本存储单元内的非零元或从前一级处理单元送来的非零元，并对每个操作数进行乘法或者加减法运算，得出对角元的最终结果或是非对角元的更新值，并将最终结果或者更新值存储到存储单元中。

本发明提供的基于FPGA并行加速的稀疏矩阵求解方法，优选地，所述“处理单元将计算结果传输给与之有依赖关系的另一处理单元”具体为：

处理单元通过通信单元将计算结果传输给另一处理单元；

另一处理单元接收到计算结果后，将计算结果存储到其对应的存储单元中。

本发明提供的基于FPGA并行加速的稀疏矩阵求解方法，优选地，所述“依据数据的依赖和冲突关系，对每个处理单元负责计算的计算域内数据进行排布”中的排布方法为：

同列的非对角元的乘法运算在同列对角元处理完成之后；非对角元的加减法运算在同行的所有非对角元的乘法运算之后；对角元的乘法运算在同行的所有非对角元的加减法运算之后；加减法运算在完成前，不能使用同行内的其它非对角元去更新右端项；

其中，对于计算过程中及来自通信单元接收到的冲突，当前计算得出的对角元的解需要在规定的拍数内通过通信单元进行广播。

本发明提供的基于FPGA并行加速的稀疏矩阵求解方法，优选地，所述“依据上三角矩阵U和下三角矩阵L的数据依赖关系分别进行分割为若干计算域，每个计算域由一个处理单元负责计算”中“分割为若干计算域”具体为：

将对角线元素求解过程中的依赖关系转化为有向无环图结构，并采用邻接表格式进行存储；

利用METIS软件包对邻接表格式进行分割，得到若干计算域。

本发明提供的基于FPGA并行加速的稀疏矩阵求解方法，优选地，所述存储单元包括存储有对角元系数的第一存储器、存储右端项的第二存储器、存储非对角元系数的第三存储器、存储非对角元乘法运算结果的第四存储器、第五存储器和寄存器；所述计算单元包括乘法单元和加法单元；

所述“处理单元按照排布后的运算顺序进行计算”包括：

处理对角元，乘法单元分别从第一存储器、第二存储器中得到对角元系数和右端项进行乘法运算，获得对应的解向量；

若该解向量只用于本处理单元中进行计算，则存储到第二存储器中；否则，还需存储到寄存器中，由通信单元传输给下一级处理单元，存储到下一级处理单元的第五存储器中；

处理非对角元，若非对角元依赖的解向量来源于本处理单元，则乘法单元从第三存储器和第二存储器中分别获取非对角元系数和解向量进行乘法运算，运算结果存储到第四存储器中；否则，乘法单元从第三存储器和第五存储器中获取非对角元系数和解向量进行乘法运算，运算结果存储到第四存储器中；

从第二存储器中和第四存储器中分别获取右端项和非对角元乘法运算结果进行加法运算，并将加法运算结果存储到第二存储器中，以更新右端项。

本发明具有如下优点：

本发明提供的一种基于FPGA并行加速的稀疏矩阵求解方法，包括若干处理单元，包括对稀疏矩阵A进行LU分解得到上三角矩阵U和下三角矩阵L，稀疏线性方程组Ax＝b的求解转换为上、下三角矩阵的线性方程组Ux＝y和Ly＝b的求解；对上三角矩阵U的对角线元素取倒数；依据上三角矩阵U和下三角矩阵L中的数据依赖关系分别进行分割为若干计算域，每个计算域由一个处理单元负责计算；依据数据的依赖和冲突关系，对每个处理单元负责计算的计算域内乘法及加减法运算顺序进行排布；每个处理单元按照排布后的运算顺序进行计算；其中，在处理单元按照排布后的运算顺序进行计算的过程中，当不同的处理单元之间的非零元存在依赖关系时，处理单元将计算结果传输给与之有依赖关系的另一处理单元。本发明有效解决了现有技术中存在的处理效率低、浪费计算资源、甚至无法进行计算的问题，从而实现高度融合的软硬件协同加速、稀疏矩阵求解的细粒度并行流水，节省计算资源、提高处理效率。

附图说明

通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明及其特征、外形和优点将会变得更加明显。在全部附图中相同的标记指示相同的部分。并未刻意按照比例绘制附图，重点在于示出本发明的主旨。

图1是本发明实施例1提供的一种基于FPGA并行加速的稀疏矩阵求解方法的部分流程示意图；

图2是本发明实施例1提供的一种基于FPGA并行加速的稀疏矩阵求解方法的分割流程示意图；

图3是本发明实施例1提供的一种基于FPGA并行加速的稀疏矩阵求解方法的部分硬件逻辑流程示意图。

具体实施方式

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。需要注意的是，本发明所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。

如图1所示，本发明实施例1提供的一种基于FPGA并行加速的稀疏矩阵求解方法，包括若干处理单元，包括：

S101：对稀疏矩阵A进行LU分解得到上三角矩阵U和下三角矩阵L，稀疏线性方程组Ax＝b的求解转换为上、下三角矩阵的线性方程组Ux＝y和Ly＝b的求解；

S102：对上三角矩阵U的对角线元素取倒数；

S103：依据上三角矩阵U和下三角矩阵L中的数据依赖关系分别进行分割为若干计算域，每个计算域由一个处理单元负责计算；

S104：依据数据的依赖和冲突关系，对每个处理单元负责计算的计算域内乘法及加减法运算顺序进行排布；

S105：每个处理单元按照排布后的运算顺序进行计算；

其中，在处理单元按照排布后的运算顺序进行计算的过程中，当不同的处理单元之间的非零元存在依赖关系时，处理单元将计算结果传输给与之有依赖关系的另一处理单元。

通过步骤S101进行LU分解，简化消元求解过程，节省计算资源。通过步骤S102对上三角矩阵U的对角线元素取倒数，从而实现用乘法运算替代除法运算，节省硬件资源并实现节拍级流水并行，提高硬件运算性能。通过步骤S103，依据数据依赖关系对数据进行分割，分割为若干计算域，分割原则是尽可能减少每个处理单元之间的数据交互，以实现多处理单元并行计算。通过步骤S104对计算域内的数据按照运算顺序进行排布，让计算单元获知每一拍进行何种计算，从而充分利用硬件资源，缩短计算时间。本发明实施例1通过对稀疏矩阵分解、分析依赖与冲突等解耦和预处理，采用静态并行调度开发稀疏线性方程组求解中的并行性，并通过数据排布与软件模拟映射算法，生成硬件运行所需的节拍级数据，利用FPGA的高度并行特性对排布好的数据根据节拍进行计算与处理，实现高度融合的软硬件协同加速、稀疏矩阵求解的细粒度并行流水。

在FPGA中，处理单元包括计算单元、存储单元和通信单元；计算单元是处理单元执行运算的硬件部件，驱动存储单元与通信单元协同工作；每个处理单元都有对应的存储单元，用于存放对应计算单元的稀疏矩阵数据与运算结果；通信单元用于在不同处理单元间的非零元存在依赖关系时，通过通信通路来传输计算结果。因此，本实施例中的“处理单元按照排布后的运算顺序进行计算”包括：按照排布后的运算顺序，计算单元读取本存储单元内的非零元或从前一级处理单元送来的非零元，并对每个操作数进行乘法或者加减法运算，得出对角元的最终结果或是非对角元的更新值，并将最终结果或者更新值存储到存储单元中。同时，“处理单元将计算结果传输给与之有依赖关系的另一处理单元”具体为：处理单元通过通信单元将计算结果传输给另一处理单元；另一处理单元接收到计算结果后，将计算结果存储到其对应的存储单元中。

本实施例中的排布依据数据之间的依赖关系及冲突关系进行排布，具体的在本实施中“依据数据的依赖和冲突关系，对每个处理单元负责计算的计算域内数据进行排布”中的排布方法具体为：同列的非对角元的乘法运算在同列对角元处理完成之后；非对角元的加减法运算在同行的所有非对角元的乘法运算之后；对角元的乘法运算在同行的所有非对角元的加减法运算之后；加减法运算在完成前，不能使用同行内的其它非对角元去更新右端项；其中，对于计算过程中及来自通信单元接收到的冲突，当前计算得出的对角元的解需要在规定的拍数内通过通信单元进行广播。

如图2所示，本实施中的分割是根据整个稀疏矩阵求解过程中的依赖与并行关系进行分割，因此，本实施例中的“依据上三角矩阵U和下三角矩阵L的数据依赖关系分别进行分割为若干计算域，每个计算域由一个处理单元负责计算”中“分割为若干计算域”具体为：

S201：将对角线元素求解过程中的依赖关系转化为有向无环图结构，并采用邻接表格式进行存储；

S202：利用METIS软件包对邻接表格式进行分割，得到若干计算域。

本实施例中的存储单元包括存储有对角元系数的第一存储器、存储右端项的第二存储器、存储非对角元系数的第三存储器、存储非对角元乘法运算结果的第四存储器、第五存储器和寄存器；计算单元包括乘法单元和加法单元；

如图3所示，本实施例中FPGA中的处理单元在“处理单元按照排布后的运算顺序进行计算”部分硬件逻辑包括：

S301：处理对角元，乘法单元分别从第一存储器、第二存储器中得到对角元系数和右端项进行乘法运算，获得对应的解向量；

S302：若该解向量只用于本处理单元中进行计算，则存储到第二存储器中；否则，还需存储到寄存器中，由通信单元传输给下一级处理单元，存储到下一级处理单元的第五存储器中；

S303：处理非对角元，若非对角元依赖的解向量来源于本处理单元，则乘法单元从第三存储器和第二存储器中分别获取非对角元系数和解向量进行乘法运算，运算结果存储到第四存储器中；否则，乘法单元从第三存储器和第五存储器中获取非对角元系数和解向量进行乘法运算，运算结果存储到第四存储器中；

S304：从第二存储器中和第四存储器中分别获取右端项和非对角元乘法运算结果进行加法运算，并将加法运算结果存储到第二存储器中，以更新右端项。

需要说明的是，本实施例中的上一级处理单元是指本处理单元有数据依赖、需要将数据传递给本处理单元的处理单元；本实施例中的下一级处理单元是指对本处理单元有数据依赖、需要本处理单元传递数据的处理单元。

以上所述仅为本发明的优选实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。