基于FPGA的列选主元LU分解方法

摘要

本发明公开了一种基于FPGA的列选主元LU分解方法，要解决的技术问题是降低LU分解的时间复杂度，加快稠密矩阵线性方程组的求解。技术方案是首先构建基于FPGA的由主处理单元和P个从处理单元组成的主从式并行计算系统，由主从式并行计算系统对待分解矩阵进行列选主元LU分解，主处理单元向第一从处理单元发送参数和待分解矩阵，从处理单元按流水方式对矩阵进行处理，处理结果由第P从处理单元传给主处理单元。采用本发明计算精度与不选主元LU分解相比得到很大提高，且运算速度快，其主从式并行计算系统具有可扩展性。

主权项

1.一种基于FPGA的列选主元LU分解方法，其特征在于包括以下步骤：第一步，构建基于FPGA的主从式并行计算系统，主从式并行计算系统由主处理单元和P个从处理单元组成，P为正整数且P＞2；主处理单元与外部存储器、第一从处理单元、第P从处理单元相连，主处理单元由外部存储器控制器、全局状态控制模块、参数发送模块、数据发送模块和数据接收模块组成；外部存储器控制器与外部存储器、数据发送模块、数据接收模块相连，对外部存储器的读写进行控制，将从外部存储器读入的数据送往数据发送模块，将从数据接收模块获得的数据写入外部存储器；全局状态控制模块与数据发送模块、数据接收模块和参数发生模块相连，控制主从式并行计算系统的状态转换；数据发送模块与外部存储器控制器、全局状态控制模块、第一从处理单元相连，在全局状态控制模块的控制下，将从外部存储器控制器传来的数据送到第一从处理单元；参数发送模块与全局状态控制模块、第一从处理单元相连，在全局状态控制模块的控制下，向第一从处理单元发送参数M′即当前需要处理的矩阵的列数或行数；数据接收模块与第P从处理单元、外部存储器控制器相连，从第P从处理单元接收中间结果矩阵和计算结果，并将中间结果矩阵和计算结果发送给外部存储器控制器；P个从处理单元组成一维线性计算阵列，负责进行列选主元LU分解，每个从处理单元逻辑结构相同，均由参数接收模块、数据通路控制模块、浮点乘加运算模块、浮点除法运算模块、数据选择模块、选主元模块、结果发送模块、4个局部存储器和FIFO组成；4个局部存储器中的第二、第三局部存储器具有“接收数据”和“工作”两个状态，只有“接收数据”状态的局部存储器才能接收数据；初始时第二局部存储器为“接收数据”状态，第三局部存储器为“工作”状态；当一个局部存储器处于“工作”时另一个便处于“接收数据”状态，数据接收完毕变为“工作”状态；第二步，由主从式并行计算系统按以下步骤对矩阵A进行列选主元LU分解：1.主处理单元的全局状态控制模块根据当前要处理的矩阵大小M初始化参数M′＝M，M为矩阵A的行数或列数，列数＝行数，待分解矩阵A′＝A；2.主处理单元的参数发送模块把参数M′发送给第一从处理单元，主处理单元的外部存储器控制器按列从外部存储器中取出待分解的矩阵A′(a_i，j，1≤i，j≤M)，由数据发送模块发送给第一从处理单元；若M′＞P，执行步骤3；若M′≤P，转步骤4；3.P个从处理单元按流水方式对矩阵A′进行处理，由主处理单元将中间结果和运算结果存入外部存储器，具体步骤如下：3.1第一从处理单元的参数接收模块从参数发送模块接收到参数M′，传递给第二从处理单元，第一从处理单元对数据发送模块送来的矩阵A′进行如下操作；3.1.1第一从处理单元的数据通路控制模块把矩阵A′的第1列数(a_i，1，1≤i≤M′)放置在第一局部存储器，由选主元模块对进行选主元操作，即找出绝对值最大的数作为该列主元u_1，1，若主元不在该列的第1个位置，由选主元模块将主元与该列第1个位置的数进行交换，并将主元原来所在位置记录在寄存器piv中；交换后，由浮点除法运算模块将主元除以主元以外的该列所有的数，结果(l_i，1，2≤i≤M′)放置在该列所有的数在第一局部存储器的原来位置；3.1.2第一从处理单元的数据通路控制模块把第2列数(a_i，2，1≤i≤M′)放置在第二局部存储器中，第二局部存储器接收完毕后为“工作”状态，由数据选择模块交换第二局部存储器的piv值所指位置与第1位置的数据，第二局部存储器第1位置新的数据送往第四局部存储器并保存在第2个位置，记为u_1，2，其它数据(a_i，2，2≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a_1，2的乘积，结果(a¹_i，2，2≤i≤M′)通过FIFO发送给第二从处理单元；3.1.3第一从处理单元的数据通路控制模块在第一从处理单元的浮点乘加运算模块进行计算的同时把第3列数(a_i，3，1≤i≤M′)放置在第三局部存储器中，第3列数接收完毕后第三局部存储器为“工作”状态，由数据选择模块交换第三局部存储器的piv值所指位置与第1位置的数据，第三局部存储器第1位置新的数据送往第四局部存储器并保存在第3个位置，记为u_1，3，其它数据(a_i，3，2≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a_1，3的乘积，结果(a¹_i，3，2≤i≤M′)通过FIFO发送给第二从处理单元；3.1.4第一从处理单元针对其它列(a_i，j，1≤i≤M′)，其中4≤j≤M′，重复3.1.3中的操作；对于第j列，数据选择模块交换第二或第三局部存储器的piv值所指位置与第1位置的数据，第1位置新的数据送往第四局部存储器并保存在第j个位置，记为u_1，j，其它数据(a_i，j，2≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a_1，j的乘积，结果(a¹_i，j，2≤i≤M′)通过FIFO发送给第二从处理单元；3.2第k从处理单元的参数接收模块从第k-1从处理单元的参数接收模块接收到参数M′，传递给第k+1从处理单元；当第k-1从处理单元执行到它的数据通路控制模块把第k-2从处理单元送来的第3列数放置在第三局部存储器时，当k＝2时，第k-2从处理单元指主处理单元，第k从处理单元开始对第k-1从处理单元送来的数据进行如下操作：3.2.1第k从处理单元的数据通路控制模块把第k-1从处理单元送来的第1列数(a^k-1_i，k，k≤i≤M′)放置在第一局部存储器，由选主元模块对进行选主元操作，找出绝对值最大的数作为该列主元u_k，k；若主元不在该列的第k个位置，由选主元模块将主元与该列第k个位置的数进行交换，并将主元原来所在位置记录在piv中；交换后，由浮点除法运算模块将主元除以主元以外的该列所有的数，结果(l_i，k，k+1≤i≤M′)放置在该列所有的数在第一局部存储器的原来位置；3.2.2第k从处理单元的数据通路控制模块把第k-1从处理单元送来的第2列数(a^k-1_i，k+1，k≤i≤M′)放置在第二局部存储器中，第二局部存储器接收完毕后为“工作”状态，由数据选择模块交换第二局部存储器的piv值所指位置与第k位置的数据，第二局部存储器第k位置新的数据送往第四局部存储器并保存在第k+1个位置，记为u_k，k+1，其它数据(a^k-1_i，k+1，k+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^k-1_k，k+1的乘积，结果(a^k_i，k+1，k+1≤i≤M′)通过FIFO发送给第k+1从处理单元；3.2.3第k从处理单元的数据通路控制模块在浮点乘加运算模块进行计算的同时把第k-1从处理单元送来的第3列数(a^k-1_i，k+2，k≤i≤M′)放置在第三局部存储器中，第3列数接收完毕后第三局部存储器为“工作”状态，由数据选择模块交换第三局部存储器的piv值所指位置与第k位置的数据，第三局部存储器第k位置新的数据送往第四局部存储器并保存在第k+2个位置，记为u_k，k+2，其它数据(a^k-1_i，k+2，k+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^k-1_k，k+2的乘积，结果(a^k_i，k+2，k+1≤i≤M′)通过FIFO发送给第k+1从处理单元；3.2.4第k从处理单元针对其它列(a^k-1_i，j，k≤i≤M′)，其中k+3≤j≤M′，重复3.2.3中的操作；对于第j+1-k列，数据选择模块交换局部存储器中的piv值所指位置与第k位置的数据，第k位置新的数据送往第四局部存储器并保存在第j个位置，记为u_k，j，其它数据(a^k-1_i，j，k+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^k-1_k，k+2的乘积，结果(a^k_i，j，k+1≤i≤M′)通过FIFO发送给第k+1从处理单元；3.3第P从处理单元的参数接收模块从第P-1从处理单元的参数接收模块接收到参数M′；当第P-1从处理单元执行到它的数据通路控制模块把第P-2从处理单元送来的第3列数放置在第三局部存储器中时，第P从处理单元开始对第P-1从处理单元送来的数据进行如下操作：3.3.1第P从处理单元的数据通路控制模块把第P-1从处理单元送来的第1列数(a^P-1_i，P，P≤i≤M′)放置在第一局部存储器，由选主元模块对进行选主元操作，找出绝对值最大的数作为该列主元u_P，P；若主元不在该列的第P个位置，由选主元模块将主元与该列第P个位置的数进行交换，并将主元原来所在位置记录在piv中；交换后，由浮点除法运算模块将主元除以主元以外的该列所有的数，结果(l_i，P，P+1≤i≤M′)放置在该列所有的数在第一局部存储器的原来位置；3.3.2第P从处理单元的数据通路控制模块把第P-1从处理单元送来的第2列数(a^P-1_i，P+1，P≤i≤M′)放置在第二局部存储器中，第二局部存储器接收完毕后为“工作”状态，由数据选择模块交换第二局部存储器的piv值所指位置与第P位置的数据，第二局部存储器第P位置新的数据送往第四局部存储器并保存在第P+1个位置，记为u_P，P+1，其它数据(a^P-1_i，P+1，P+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^P-1_P，P+1的乘积，结果(a^P_i，P+1，P+1≤i≤M′)通过FIFO发送给主处理单元；3.3.3第P从处理单元的数据通路控制模块在浮点乘加运算模块进行计算的同时把第P-1从处理单元送来的第3列数(a^P-1_i，P+2，P≤i≤M′)放置在第三局部存储器中，第3列数接收完毕后第三局部存储器为“工作”状态，由数据选择模块交换第三局部存储器的piv值所指位置与第P位置的数据，第三局部存储器第P位置新的数据送往第四局部存储器并保存在第P+2个位置，记为u_P，P+2，其它数据(a^P-1_i，P+2，P+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^P-1_P，P+2的乘积，结果(a^P_i，P+2，P+1≤i≤M′)通过FIFO发送给主处理单元；3.3.4第P从处理单元针对其它列的数(a^P-1_i，j，P≤i≤M′)，其中P+3≤j≤M′，重复3.3.3中的操作；对于第j+1-P列，数据选择模块交换局部存储器中的piv值所指位置与第P位置的数据，第P位置新的数据送往第四局部存储器并保存在第j个位置，记为u_P，j，其它数据(a^P-1_i，j，P+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^P-1_P，P+2的乘积，结果(a^P_i，j，P+1≤i≤M′)通过FIFO发送给主处理单元；3.4主处理单元的数据接收模块按列接收第P从处理单元的FIFO发送过来的中间结果由外部存储控制器存储到外部存储器中，然后，各个从处理单元的运算结果按如下步骤传递给主处理单元，并由主处理单元的外部存储控制器存储到外部存储器中：3.4.1第一从处理单元的结果发送模块将第一从处理单元的第一局部存储器和第四局部存储器中的数据(l_i，1，2≤i≤M′)、(u_1，j，1≤j≤M′)送到第二从处理单元的结果发送模块；3.4.2第k从处理单元的结果发送模块首先将第k-1从处理单元的结果发送模块发送来的数据传递给第k+1从处理单元的结果发送模块，然后将第k从处理单元的第一局部存储器和第四局部存储器中的数据(l_i，k，k+1≤i≤M′)、(u_k，j，k≤j≤M′)送到第k+1从处理单元的结果发送模块；3.4.3第P从处理单元的结果发送模块首先将第P-1从处理单元的结果发送模块发送来的数据传递给主处理单元的数据接收模块，然后将第P从处理单元的第一局部存储器和第四局部存储器中的数据(l_i，P，P+1≤i≤M′)、(u_P，j，P≤j≤M′)送到主处理单元的数据接收模块；3.4.4主处理单元的数据接收模块接收从第P从处理单元的结果发送模块发送过来的各个从处理单元的运算结果，由外部存储控制器存储到外部存储器中；3.5主处理单元的全局状态控制模块控制参数发送模块置M′＝M′-P，A′＝由列向量组成的中间结果矩阵，转步骤2；4M′个从处理单元按流水方式对矩阵A′进行处理，由主处理单元将运算结果存入外部存储器，具体步骤如下：4.1第一从处理单元的参数接收模块从参数发送模块接收到参数M′，传递给第二从处理单元，第一从处理单元对数据发送模块送来的矩阵A′进行如下操作：4.1.1第一从处理单元的数据通路控制模块把矩阵A′的第1列数(a_i，1，1≤i≤M′)放置在第一局部存储器，由选主元模块对进行选主元操作，即找出绝对值最大的数作为该列主元u_1，1；若主元不在该列的第1个位置，由选主元模块将主元与该列第1个位置的数进行交换，并将主元原来所在位置记录在piv中；交换后，由浮点除法运算模块将主元除以主元以外的该列所有的数，结果(l_i，1，2≤i≤M′)放置在该列所有的数在第一局部存储器的原来位置；4.1.2第一从处理单元的数据通路控制模块把第2列数(a_i，2，1≤i≤M′)放置在第二局部存储器中，第二局部存储器接收完毕后为“工作”状态，由数据选择模块交换第二局部存储器的piv值所指位置与第1位置的数据，第二局部存储器第1位置新的数据送往第四局部存储器并保存在第2个位置，记为u_1，2，其它数据(a_i，2，2≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a_1，2的乘积，结果(a¹_i，2，2≤i≤M′)通过FIFO发送给第二从处理单元；4.1.3第一从处理单元的数据通路控制模块在第一从处理单元的浮点乘加运算模块进行计算的同时把第3列数(a_i，3，1≤i≤M′)放置在第三局部存储器中，第3列数接收完毕后第三局部存储器为“工作”状态，由数据选择模块交换第三局部存储器的piv值所指位置与第1位置的数据，第三局部存储器第1位置新的数据送往第四局部存储器并保存在第3个位置，记为u_1，3，其它数据(a_i，3，2≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a_1，3的乘积，结果(a¹_i，3，2≤i≤M′)通过FIFO发送给第二从处理单元；4.1.4第一从处理单元针对其它列(a_i，j，1≤i≤M′)，其中4≤j≤M′，重复4.1.3中的操作；对于第j列，数据选择模块交换第二或第三局部存储器的piv值所指位置与第1位置的数据，第1位置新的数据送往第四局部存储器并保存在第j个位置，记为u_1，j，其它数据(a_i，j，2≤i≤M′)送往浮点乘加运算模块。浮点乘加运算模块将减去与a_1，j的乘积，结果(a¹_i，j，2≤i≤M′)通过FIFO发送给第二从处理单元；4.2第k从处理单元(2≤k≤M′-1)的参数接收模块从第k-1从处理单元的参数接收模块接收到参数M′，传递给第k+1从处理单元；当第k-1从处理单元执行到它的数据通路控制模块把第k-2从处理单元送来的第3列数放置在第三局部存储器时，当k＝2时，第k-2从处理单元指主处理单元，第k从处理单元开始对第k-1从处理单元送来的数据进行如下操作：4.2.1第k从处理单元的数据通路控制模块把第k-1从处理单元送来的第1列数(a^k-1_i，k，k≤i≤M′)放置在第一局部存储器，由选主元模块对进行选主元操作，找出绝对值最大的数作为该列主元u_k，k；若主元不在该列的第k个位置，由选主元模块将主元与该列第k个位置的数进行交换，并将主元原来所在位置记录在piv中；交换后，由浮点除法运算模块将主元除以主元以外的该列所有的数，结果(l_i，k，k+1≤i≤M′)放置在该列所有的数在第一局部存储器的原来位置；4.2.2第k从处理单元的数据通路控制模块把第k-1从处理单元送来的第2列数(a^k-1_i，k+1，k≤i≤M′)放置在第二局部存储器中，第二局部存储器接收完毕后为“工作”状态，由数据选择模块交换第二局部存储器的piv值所指位置与第k位置的数据，第二局部存储器第k位置新的数据送往第四局部存储器并保存在第k+1个位置，记为u_k，k+1，其它数据(a^k-1_i，k+1，k+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^k-1_k，k+1的乘积，结果(a^k_i，k+1，k+1≤i≤M′)通过FIFO发送给第k+1从处理单元；4.2.3第k从处理单元的数据通路控制模块在浮点乘加运算模块进行计算的同时把第k-1从处理单元送来的第3列数(a^k-1_i，k+2，k≤i≤M′)放置在第三局部存储器中，第3列数接收完毕后第三局部存储器为“工作”状态，由数据选择模块交换第三局部存储器的piv值所指位置与第k位置的数据，第三局部存储器第k位置新的数据送往第四局部存储器并保存在第k+2个位置，记为u_k，k+2，其它数据(a^k-1_i，k+2，k+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^k-1_k，k+2的乘积，结果(a^k_i，k+2，k+1≤i≤M′)通过FIFO发送给第k+1从处理单元；4.2.4第k从处理单元针对其它列(a^k-1_i，j，k≤i≤M′)，其中k+3≤j≤M′，重复4.2.3中的操作；对于第j+1-k列，数据选择模块交换局部存储器中的piv值所指位置与第k位置的数据，第k位置新的数据送往第四局部存储器并保存在第j个位置，记为u_k，j，其它数据(a^k-1_i，j，k+1≤i≤M′)送往浮点乘加运算模块；浮点乘加运算模块将减去与a^k-1_k，k+2的乘积，结果(a^k_i，j，k+1≤i≤M′)通过FIFO发送给第k+1从处理单元；4.3第M′从处理单元的参数接收模块从第M′-1从处理单元的参数接收模块接收到参数M′；第M′从处理单元将第M′-1从处理单元送来一行一列即a^M′-1_M′，M′放置在第一局部存储器，记为u_M′，M′；4.4线性计算阵列将运算结果传递给主处理单元的数据接收模块，主处理单元的外部存储控制器将运算结果存储到外部存储器中，最终，运算结果完全存储在外部存储器作为输出，计算结束，具体步骤如下：4.4.1第一从处理单元的结果发送模块将第一从处理单元的第一局部存储器和第四局部存储器中的数据(l_i，1，2≤i≤M′)、(u_1，j，1≤j≤M′)送到第二从处理单元的结果发送模块；4.4.2第k从处理单元的结果发送模块首先将第k-1从处理单元的结果发送模块发送来的数据传递给第k+1从处理单元的结果发送模块，然后将第k从处理单元的第一局部存储器和第四局部存储器中的数据(l_i，k，k+1≤i≤M′)、(u_k，j，k≤j≤M′)送到第k+1从处理单元的结果发送模块；4.4.3第M′从处理单元的结果发送模块首先将第M′-1从处理单元的结果发送模块发送来的数据传递给第M′+1从处理单元的结果发送模块，然后将第M′从处理单元的第一局部存储器的数据u_M′，M′送到第M′+1从处理单元的结果发送模块；4.4.5第h从处理单元(M′+1≤h≤P-1)的结果发送模块将第h-1从处理单元的结果发送模块发送来的数据传递给第h+1从处理单元的结果发送模块；4.4.6第P从处理单元的结果发送模块将第P-1从处理单元的结果发送模块发送来的数据传递给主处理单元的数据接收模块；4.4.7主处理单元的数据接收模块接收从第P从处理单元的结果发送模块发送过来的各个从处理单元的运算结果，由外部存储控制器存储到外部存储器中。