[發(fā)明專(zhuān)利]基于FPGA并行加速的稀疏矩陣求解方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202011156271.8
• 申請(qǐng)日: 2020-10-26
• 公開(kāi)（公告）號(hào): CN112231630A
• 公開(kāi)（公告）日: 2021-01-15
• 發(fā)明（設(shè)計(jì)）人: 李猛;顧燕卿;劉洪錦;王晞陽(yáng);劉首文
• 申請(qǐng)（專(zhuān)利權(quán)）人: 國(guó)家超級(jí)計(jì)算無(wú)錫中心;太初（無(wú)錫）電子科技有限公司
• 主分類(lèi)號(hào): G06F17/16
• 分類(lèi)號(hào): G06F17/16;G06F17/12;G06F9/50
• 代理公司: 無(wú)錫知之火專(zhuān)利代理事務(wù)所(特殊普通合伙) 32318
• 代理人: 袁粉蘭

本發(fā)明提供的基于FPGA并行加速的稀疏矩陣求解方法，通過(guò)對(duì)稀疏矩陣進(jìn)行分解、對(duì)下三角矩陣對(duì)角線(xiàn)元素取倒數(shù)、根據(jù)數(shù)據(jù)依賴(lài)關(guān)系對(duì)數(shù)據(jù)進(jìn)行分割分配、并對(duì)每個(gè)處理單元內(nèi)的數(shù)據(jù)進(jìn)行排布、依據(jù)排布的運(yùn)算順序采用精確的節(jié)拍級(jí)硬件資源調(diào)度進(jìn)行計(jì)算，從而實(shí)現(xiàn)高度融合的軟硬件協(xié)同加速、稀疏矩陣求解的細(xì)粒度并行流水，有效解決了現(xiàn)有技術(shù)中存在的處理效率低、浪費(fèi)計(jì)算資源、甚至無(wú)法進(jìn)行計(jì)算的問(wèn)題，節(jié)省計(jì)算資源、提高處理效率。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及基于FPGA并行加速的稀疏矩陣求解方法。

背景技術(shù)

在電力系統(tǒng)仿真中，電磁暫態(tài)仿真是主要的系統(tǒng)仿真應(yīng)用之一，也是電力系統(tǒng)安全分析和運(yùn)行的關(guān)鍵組件。在該應(yīng)用中，其核心算法是對(duì)大規(guī)模線(xiàn)性方程組Ax＝b的求解。同時(shí)，通過(guò)對(duì)實(shí)際數(shù)據(jù)的分析可知，線(xiàn)性方程組中的系數(shù)矩陣A通常為稀疏矩陣，電力系統(tǒng)大型稀疏矩陣的稠密度通常小于1％，如果不能有效的利用矩陣的稀疏性，在使用計(jì)算機(jī)處理大型稀疏矩陣操作時(shí)會(huì)把大量的存儲(chǔ)和計(jì)算資源浪費(fèi)在無(wú)效的零元上，導(dǎo)致處理效率低下緩慢，并且部分超大規(guī)模稀疏矩陣甚至無(wú)法使用傳統(tǒng)的稠密矩陣算法來(lái)進(jìn)行求解。

發(fā)明內(nèi)容

本發(fā)明提供的基于FPGA并行加速的稀疏矩陣求解方法，以解決現(xiàn)有技術(shù)中存在的處理效率低、浪費(fèi)計(jì)算資源、甚至無(wú)法進(jìn)行計(jì)算的問(wèn)題，從而實(shí)現(xiàn)高度融合的軟硬件協(xié)同加速、稀疏矩陣求解的細(xì)粒度并行流水，節(jié)省計(jì)算資源、提高處理效率。

為解決上述技術(shù)問(wèn)題，本發(fā)明提供的技術(shù)方案為：

本發(fā)明提供的一種基于FPGA并行加速的稀疏矩陣求解方法，包括若干處理單元，包括：

對(duì)稀疏矩陣A進(jìn)行LU分解得到上三角矩陣U和下三角矩陣L稀疏線(xiàn)性方程組Ax＝b的求解轉(zhuǎn)換為上、下三角矩陣的線(xiàn)性方程組Ux＝y(tǒng)和Ly＝b的求解；

對(duì)上三角矩陣U的對(duì)角線(xiàn)元素取倒數(shù)；

依據(jù)上三角矩陣U和下三角矩陣L中的數(shù)據(jù)依賴(lài)關(guān)系分別進(jìn)行分割為若干計(jì)算域，每個(gè)計(jì)算域由一個(gè)處理單元負(fù)責(zé)計(jì)算；

依據(jù)數(shù)據(jù)的依賴(lài)和沖突關(guān)系，對(duì)每個(gè)處理單元負(fù)責(zé)計(jì)算的計(jì)算域內(nèi)乘法及加減法運(yùn)算順序進(jìn)行排布；

每個(gè)處理單元按照排布后的運(yùn)算順序進(jìn)行計(jì)算；

其中，在處理單元按照排布后的運(yùn)算順序進(jìn)行計(jì)算的過(guò)程中，當(dāng)不同的處理單元之間的非零元存在依賴(lài)關(guān)系時(shí)，處理單元將計(jì)算結(jié)果傳輸給與之有依賴(lài)關(guān)系的另一處理單元。

本發(fā)明提供的基于FPGA并行加速的稀疏矩陣求解方法，優(yōu)選地，所述處理單元包括計(jì)算單元、存儲(chǔ)單元和通信單元；

所述“處理單元按照排布后的運(yùn)算順序進(jìn)行計(jì)算”包括：

按照排布后的運(yùn)算順序，計(jì)算單元讀取本存儲(chǔ)單元內(nèi)的非零元或從前一級(jí)處理單元送來(lái)的非零元，并對(duì)每個(gè)操作數(shù)進(jìn)行乘法或者加減法運(yùn)算，得出對(duì)角元的最終結(jié)果或是非對(duì)角元的更新值，并將最終結(jié)果或者更新值存儲(chǔ)到存儲(chǔ)單元中。

本發(fā)明提供的基于FPGA并行加速的稀疏矩陣求解方法，優(yōu)選地，所述“處理單元將計(jì)算結(jié)果傳輸給與之有依賴(lài)關(guān)系的另一處理單元”具體為：

處理單元通過(guò)通信單元將計(jì)算結(jié)果傳輸給另一處理單元；

另一處理單元接收到計(jì)算結(jié)果后，將計(jì)算結(jié)果存儲(chǔ)到其對(duì)應(yīng)的存儲(chǔ)單元中。

本發(fā)明提供的基于FPGA并行加速的稀疏矩陣求解方法，優(yōu)選地，所述“依據(jù)數(shù)據(jù)的依賴(lài)和沖突關(guān)系，對(duì)每個(gè)處理單元負(fù)責(zé)計(jì)算的計(jì)算域內(nèi)數(shù)據(jù)進(jìn)行排布”中的排布方法為：

同列的非對(duì)角元的乘法運(yùn)算在同列對(duì)角元處理完成之后；非對(duì)角元的加減法運(yùn)算在同行的所有非對(duì)角元的乘法運(yùn)算之后；對(duì)角元的乘法運(yùn)算在同行的所有非對(duì)角元的加減法運(yùn)算之后；加減法運(yùn)算在完成前，不能使用同行內(nèi)的其它非對(duì)角元去更新右端項(xiàng)；