[發(fā)明專利]一種眾核平臺上面向規(guī)則網(wǎng)格問題的結(jié)構(gòu)化著色方法

有效

• 申請?zhí)枺?/td>: 201911047165.3
• 申請日: 2019-10-30
• 公開（公告）號: CN110942504B
• 公開（公告）日: 2021-07-27
• 發(fā)明（設(shè)計(jì)）人: 劉芳芳;吳麗鑫;馬文靜;汪荃;王志軍;孫家昶;楊超
• 申請（專利權(quán)）人: 中國科學(xué)院軟件研究所
• 主分類號: G06T15/00
• 分類號: G06T15/00
• 代理公司: 北京東方盛凡知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11562
• 代理人: 張雪

本發(fā)明公開一種眾核平臺上面向規(guī)則網(wǎng)格問題的結(jié)構(gòu)化著色方法，包括如下步驟：步驟一、依賴特性分析：對按照stencil模板格式生成的計(jì)算問題中的各計(jì)算任務(wù)之間的依賴特性進(jìn)行分析，包括依賴傳遞特性分析和強(qiáng)弱依賴方向分析；步驟二、參數(shù)搜索：根據(jù)依賴特性分析結(jié)果，使用四種參數(shù)搜索模式進(jìn)行最優(yōu)的著色規(guī)則參數(shù)搜索；步驟三、計(jì)算任務(wù)劃分：根據(jù)最優(yōu)的著色規(guī)則參數(shù)為每個計(jì)算任務(wù)著色，并將相同顏色的計(jì)算任務(wù)分為一組，不同顏色的計(jì)算任務(wù)分為不同組，總的顏色數(shù)即為計(jì)算任務(wù)的總的劃分組數(shù)，完成計(jì)算任務(wù)的劃分；本發(fā)明保證了在相同顏色數(shù)的限制下，保留更多的核心依賴關(guān)系，從而有效減少了計(jì)算的整體迭代次數(shù)，并提高了著色質(zhì)量。

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

本申請涉及眾核平臺上的著色領(lǐng)域，具體涉及一種眾核平臺上面向規(guī)則網(wǎng)格問題的結(jié)構(gòu)化著色方法。

背景技術(shù)

stencil計(jì)算是高性能計(jì)算領(lǐng)域的重要計(jì)算模式之一。stencil本身是數(shù)值分析領(lǐng)域的一個概念，由一組在幾何空間中以當(dāng)前點(diǎn)為中心的點(diǎn)組成，這些點(diǎn)定義了更新當(dāng)前點(diǎn)需要參與計(jì)算的依賴點(diǎn)集合。使用這些依賴點(diǎn)對計(jì)算問題進(jìn)行差分離散化，就可以生成稀疏方程組進(jìn)行問題的求解。不同的stencil因?yàn)榭紤]了幾何空間中不同位置的點(diǎn)來形成迥異的依賴關(guān)系，所以不同的stencil適合于模擬不同的計(jì)算問題。

由于stencil計(jì)算用于模擬的計(jì)算問題通常規(guī)模巨大，而普通的計(jì)算機(jī)往往不具備這樣的求解能力，所以這些應(yīng)用通常需要借助眾核結(jié)構(gòu)的超級計(jì)算機(jī)來進(jìn)行超大規(guī)模計(jì)算問題的求解。HPCG(High Performance Conjugate Gradient，高性能共軛梯度法)基準(zhǔn)測試作為超級計(jì)算機(jī)的評估指標(biāo)之一，不同于HPL(High Performance Linpack)指標(biāo)只側(cè)重于衡量系統(tǒng)的浮點(diǎn)運(yùn)算能力，而是加強(qiáng)了對程序中不規(guī)則的內(nèi)存訪問模式的模擬，更強(qiáng)調(diào)系統(tǒng)在浮點(diǎn)運(yùn)算、通信帶寬與讀寫延遲之間的性能平衡，能夠更好地度量超級計(jì)算機(jī)系統(tǒng)在stencil計(jì)算這種訪存受限的應(yīng)用程序中的實(shí)際性能，并且通過擴(kuò)展HPCG支持的stencil格式，使其適用于所有截?cái)嗍竭吔鐥l件的結(jié)構(gòu)網(wǎng)格計(jì)算問題。

在HPCG的CG(Conjugate Gradient，共軛梯度法)求解方法中，SpMV(SparseMatrix-Vector Multiplication，稀疏矩陣向量乘法)和SymGS(Symmetric Gauss–Seidel，對稱高斯-賽德爾迭代法)為核心操作，其中SymGS更是占用了60％以上的運(yùn)行時間，是CG算法優(yōu)化工作的關(guān)鍵。標(biāo)準(zhǔn)的串行版SymGS嚴(yán)格地保持了計(jì)算任務(wù)之間的原始數(shù)據(jù)依賴，在參考版程序運(yùn)行50輪迭代時便可以達(dá)到一個較低的殘差水平，而該殘差將作為后續(xù)優(yōu)化版程序的殘差閾值。

在SymGS中使用level scheduled方法可以實(shí)現(xiàn)計(jì)算核心的并行化，并且能夠較好地保持原始的數(shù)據(jù)依賴，但是該方法提供的并行度往往非常有限，為了達(dá)到更高的并行度，可以使用著色方法對計(jì)算任務(wù)進(jìn)行分解，讓相同顏色的計(jì)算任務(wù)并行更新，不同顏色的計(jì)算任務(wù)按照顏色次序依次更新。

雖然著色方法能夠?yàn)槌绦蛱峁┳銐虻牟⑿卸龋尦绦蚋蟪潭鹊匕l(fā)揮眾核系統(tǒng)的性能，但是該方法只能確保鄰居點(diǎn)的數(shù)據(jù)依賴，而其他計(jì)算任務(wù)間的依賴關(guān)系保持或者破壞則由著色方法給出的具體著色方案決定，所以使用不同的著色方法將會影響CG算法的迭代次數(shù)，而不同著色方法給出的并行方案的顏色數(shù)不同，即為SymGS計(jì)算核心提供的并行度不同，導(dǎo)致SymGS計(jì)算核心的性能也存在差異，這兩方面的影響決定了在CG計(jì)算中使用不同的著色方法進(jìn)行計(jì)算任務(wù)的劃分和重排將會得到完全不同的最終性能。此外，著色過程的時間也包含在整體的運(yùn)行時間中，所以該指標(biāo)同樣需要被考量。因此著色方法為CG計(jì)算提供的著色方案的優(yōu)劣可以通過迭代次數(shù)、顏色數(shù)、著色性能這三個指標(biāo)來進(jìn)行全面的衡量。