[發明專利]基于GPU的稀疏矩陣LU分解方法

在審

• 申請號: 201310329479.9
• 申請日: 2013-07-31
• 公開（公告）號: CN103399841A
• 公開（公告）日: 2013-11-20
• 發明（設計）人: 任令;陳曉明;汪玉;楊華中
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

1.一種基于GPU的稀疏矩陣LU分解方法，其特征在于，包括以下步驟：

A：在CPU上建立待仿真的電路網單的電路矩陣，并對所述電路矩陣進行預處理和稀疏化；

B：根據預處理結果選擇對所述稀疏矩陣LU進行處理的計算平臺；

C：如果對所述稀疏矩陣LU進行處理所使用的計算平臺為GPU，則通過所述GPU對所述稀疏矩陣LU進行分解，包括：

C1：將所述電路矩陣的非零元位置、值以及所述稀疏矩陣的LU因子的非零元位置輸入所述GPU；

C2：確定群并行模式和流水線并行模式的分界點；

C3：依次計算屬于所述群并行模式的各層直至所有層均計算完成；

C4：通過所述流水線并行方式計算剩余各層；

C5：將所述稀疏矩陣LU中非零元的值寫回到所述CPU；

D：通過所述CPU對所述稀疏矩陣LU中非零元的值進行回代求解，以完成對稀疏矩陣LU的分解。

2.如權利要求1所述的基于GPU的稀疏矩陣LU分解方法，其特征在于，所述對所述電路矩陣進行預處理，進一步包括：

對數值進行處理以提高所述數值的穩定性；

根據近似最小自由度算法減少分解過程中的非零元寫入；

根據部分選主元的數值分解計算所述矩陣LU的非零元結構。

3.如權利要求2所述的基于GPU的稀疏矩陣LU分解方法，其特征在于，根據HSL_MC64方法對所述數值進行處理以提高所述數值的穩定性。

4.如權利要求1所述的基于GPU的稀疏矩陣LU分解方法，其特征在于，所述根據預處理結果選擇對所述稀疏矩陣LU進行處理的計算平臺，進一步包括：

對所述矩陣LU中每行的非零元按列號進行排序；

建立消去圖，并對所述消去圖進行分層；

根據浮點運算次數確定要使用的平臺；

如果所述浮點運算次數大于或等于預設次數，則使用GPU平臺；

如果所述浮點運算次數小于所述預設次數，則使用CPU平臺。

5.如權利要求4所述的基于GPU的稀疏矩陣LU分解方法，其特征在于，所述建立消去圖，并對所述消去圖進行分層，進一步包括：

建立消去圖，其中，所述消去圖中包括節點，且各節點表示各行。

對所述消去圖進行分層，其中，所述節點的層號為所述節點所依賴的行所處的最大層號加1。

6.如權利要求5所述的基于GPU的稀疏矩陣LU分解方法，其特征在于，所述對所述消去圖進行分層之后，還包括：

依次處理所述消去圖的每一層，所述每一層內部的各行可按照任意順序進行計算。其中，

處理所述消去圖的方式包括：群并行模式和流水線并行模式，所述群并行模式指所述每一層有足夠多的行被并行分解；所述流水線并行模式指所述每一層只有很少的行，且來自不同層的行重疊執行分解。

7.如權利要求1所述的基于GPU的稀疏矩陣LU分解方法，其特征在于，所述通過所述流水線并行方式計算剩余各層，進一步包括：

如果檢測到未計算完成的行，則設為第k行，并計算所述第k行；

依次檢測所述第k行所依賴的行，并設為第j行，并判斷所述第j行是否計算完成；

如果所述第j行計算完成，則從第K行中減去第j行乘以其相應系數；

如果第j行未完成，則等待預設時間后重新檢測第j行是否計算完成；

依次確認所述第k行所依賴的每一行均計算完成后，從所述第k行中減去該行乘以其相應系數；

將第k行的計算結果寫回到所述GPU中，并判定第k行已計算完成，并進一步處理下一個未完成的行，直至所有行均已完成計算。