散文網(wǎng) » 科技 »汽車 » MX Direct Solver——高性能稀疏線性求解器

MX Direct Solver——高性能稀疏線性求解器

2023-03-21 14:51 作者:Mack丨邁曦科技 0人讀過 | 我要投稿

? ? MXDSV是基于直接方法的大規(guī)模稀疏線性方程求解器，目前支持非對稱、結(jié)構(gòu)對稱以及對稱方程組，實(shí)數(shù)與復(fù)數(shù)方程組等求解功能。

? ?求解形式為Ax=b的線性方程組的直接方法是基于高斯消元計(jì)算A=LU，其中A和U分別為下三角和上三角矩陣，計(jì)算系數(shù)矩陣A的三角分解也稱為LU分解。分解后，通過求解三角形系統(tǒng) Ly=b 和Ux=y即可簡單求解原系統(tǒng)。如果A是對稱的，則通過Cholesky分解來計(jì)算形式A=LLT或A=LDLT的分解，其中A是一個(gè)下三角的矩陣(在A=LDLT分解的情況下，為單位下三角矩陣)，并且D是一個(gè)對角矩陣。

? ?圖1和圖2分別展示了稠密矩陣的LU分解和Cholesky分解的一組常用公式。在此基礎(chǔ)上，通過在這些算法中重新排列循環(huán)，可以得到其他數(shù)學(xué)上等價(jià)的公式。這些算法同樣適用于稀疏矩陣—其大部分元素是零。

例如，如果A[j,i]除法步驟中的分子為零，則不需要執(zhí)行該操作。類似地，如果A[j,i]或A[i,k](如果是對稱的，則A[k,i])為零，則可以省略更新步驟。

圖1 列優(yōu)先的密集矩陣LU分解算法

圖2 列優(yōu)先的密集矩陣Cholesky分解算法

? ?當(dāng)A是稀疏的時(shí)，三角矩陣L和U通常會在額外的位置產(chǎn)生非零元，這種現(xiàn)象被稱為填充（fill-in），這會導(dǎo)致使用直接方法求解稀疏系統(tǒng)的內(nèi)存和時(shí)間需求相對于系統(tǒng)產(chǎn)生超線性增長。盡管直接方法需要很高的內(nèi)存，但由于其通用性和魯棒性，在許多工程實(shí)際應(yīng)用中仍然是首選方法。在需要求解多個(gè)右端向量并且系數(shù)矩陣不變的應(yīng)用中，直接方法更是求解者的選擇，因?yàn)橐淮螖?shù)值分解的開銷可以平攤在多個(gè)快速的三角矩陣求解上。

01??算法線路

? ?稀疏線性系統(tǒng)的直接求解過程通常包括四個(gè)階段。兩個(gè)計(jì)算階段，因式分解和三角求解已經(jīng)提到過。有些時(shí)候，因子中非零元的數(shù)目是系數(shù)矩陣的行和列的初始排列的函數(shù)。在許多并行的稀疏分解形式中，這種排列也會對負(fù)載平衡產(chǎn)生影響。因此，直接求解稀疏線性系統(tǒng)的第一步是應(yīng)用啟發(fā)式算法來計(jì)算矩陣的理想排列，這一步被稱為排序。稀疏矩陣可以看作是圖的鄰接矩陣，排序啟發(fā)式通常使用矩陣的圖形視圖，并按照特定的順序標(biāo)記頂點(diǎn)，這相當(dāng)于計(jì)算具有理想屬性的系數(shù)矩陣的排列。第二個(gè)階段，稱為符號分解，計(jì)算因子的非零元模式（分布）。

? ?在實(shí)際計(jì)算因子之前了解因子的非零模式是有用的，原因有幾個(gè)：

(a)在符號分解過程中，可以預(yù)測數(shù)值分解的內(nèi)存需求；

(b)由于預(yù)先知道非零的數(shù)量和位置，在數(shù)值分解過程中可以避免大量的間接尋址，從而提高性能；

(c)在并行實(shí)現(xiàn)中，符號分解有助于數(shù)據(jù)和計(jì)算在處理單元之間的分配。

排序和符號分解階段也稱為預(yù)處理或分析步驟。迭代細(xì)化的第五個(gè)階段有時(shí)在求解階段之后使用，以提高求解的精度。

? ?在實(shí)際計(jì)算中，數(shù)值分解通常消耗最多的內(nèi)存和時(shí)間。許多應(yīng)用涉及到分解幾個(gè)具有不同數(shù)值但具有相同稀疏結(jié)構(gòu)的矩陣，在這種情況下，排序和符號分解步驟的部分或全部結(jié)果都可以重用。這對于并行稀疏求解器也是有利的，因?yàn)椴⑿信判蚝头柗纸馔ǔＪ强蓴U(kuò)展性較差的。將這些步驟的成本分?jǐn)偟綆讉€(gè)分解步驟中，有助于保持求解器的整體可伸縮性接近于數(shù)值分解的可伸縮性。三角求解的并行化高度依賴于數(shù)值分解階段的并行化。數(shù)值因式分解的并行形式規(guī)定了因子如何在并行任務(wù)中分配。隨后的三角求解步驟必須使用一個(gè)并行化方案來處理這種數(shù)據(jù)分布，特別是在分布式內(nèi)存并行環(huán)境中。

02?異構(gòu)計(jì)算

? ? 目前對于線性方程直接法中數(shù)值分解的并行加速工作主要基于兩個(gè)方面：一個(gè)是節(jié)點(diǎn)并行，另一個(gè)是樹并行。很多直接求解器使用GPU加速數(shù)值分解都是基于節(jié)點(diǎn)并行的方式，也就是說利用GPU對部分dense kernel（blas or lapack）進(jìn)行加速計(jì)算。在許多問題中這種輔助計(jì)算的方法并不能充分利用GPU的計(jì)算資源，所以計(jì)算效率難以得到大幅提升。然而，GPU擁有大量可并發(fā)的線程和高訪存帶寬，這為我們提供一種新的并行策略：同時(shí)使用節(jié)點(diǎn)并行和樹并行。因此，我們提出了一種面向多GPU的多級并行策略對稀疏分解進(jìn)行加速計(jì)算，并在此基礎(chǔ)上針對有限元分析設(shè)計(jì)高效地求解算法。

03MXDSV性能表現(xiàn)

? ? 我們從SuiteSparse Matrix Collection (http://sparse.tamu.edu/)矩陣集中選取了前10個(gè)較大的稀疏矩陣作為測試集，與知名商業(yè)求解器MKL PARDISO進(jìn)行求解性能對比。