[發(fā)明專利]一種應(yīng)用于解決粒子模擬并行數(shù)據(jù)競爭的歸約方法

有效

• 申請?zhí)枺?/td>: 201710747274.0
• 申請日: 2017-08-28
• 公開（公告）號: CN107704266B
• 公開（公告）日: 2021-03-30
• 發(fā)明（設(shè)計）人: 金曉林;劉騰宇;李斌;楊中海
• 申請（專利權(quán)）人: 電子科技大學(xué)
• 主分類號: G06F9/30
• 分類號: G06F9/30;G06F9/38;G06F9/52;G06F30/25
• 代理公司: 電子科技大學(xué)專利中心 51203
• 代理人: 閆樹平

本發(fā)明屬于粒子模擬并行技術(shù)領(lǐng)域。具體涉及一種應(yīng)用于解決粒子模擬并行數(shù)據(jù)競爭的歸約方法。本發(fā)明通過采用歸約的方法實現(xiàn)對粒子模擬中數(shù)據(jù)競爭部分的并行，每個線程選取固定的三個數(shù)據(jù)進行處理并固定輸出兩個數(shù)據(jù)作為返回值，不會發(fā)生不同線程寫入數(shù)據(jù)地址沖突的問題并且不需要對數(shù)據(jù)做分離預(yù)處理，解決了原有歸約中因輸出數(shù)據(jù)個數(shù)不固定而導(dǎo)致的數(shù)據(jù)寫入沖突的問題，從而可以高效且精確地并行粒子模擬中數(shù)據(jù)競爭部分，對整個粒子模擬程序的并行度有了極大提升。

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

本發(fā)明屬于粒子模擬并行技術(shù)領(lǐng)域。具體涉及一種應(yīng)用于解決粒子模擬并行數(shù)據(jù)競爭的歸約方法。

背景技術(shù)

近年來計算機技術(shù)的迅速發(fā)展，使人們可以利用高速度、大容量內(nèi)存的計算機來模擬復(fù)雜的物理問題，因而出現(xiàn)了一門新興學(xué)科——計算物理，其中一個突出應(yīng)用就是粒子模擬方法。

粒子模擬方法是通過跟蹤大量帶電粒子在外加及自洽電磁場中的運動并統(tǒng)計平均而得到的宏觀特性及運動規(guī)律的一種方法。粒子模擬方法不但可以用于物理規(guī)律還不勝清楚的基本理論問題的研究，還可用于幾何形狀和結(jié)構(gòu)都比較復(fù)雜的實用等離子體裝置的研究和設(shè)計。

由于粒子模擬原則上是模擬真實等離子體的行為，在某種程度上可以替代實驗，具有計算機實驗之稱。在利用粒子模擬方法對場與粒子相互作用問題描述時，由于空間網(wǎng)格劃分產(chǎn)生的大量網(wǎng)格數(shù)及隨之而產(chǎn)生的龐大的模擬粒子數(shù)目，使得粒子模擬程序的運行效率非常低。針對這種問題，并行計算技術(shù)可以很好地對程序?qū)崿F(xiàn)加速，并且已經(jīng)被廣泛使用，然而由于粒子模擬方法應(yīng)用中存在大量的數(shù)據(jù)競爭，這嚴(yán)重地制約了并行效率的提高。

粒子模擬的數(shù)據(jù)競爭有多種，其中最主要的是源的求解，這可以從粒子模擬的求解流程得出。粒子模擬方法按照求解不同形式的電磁方程，可以分為靜電模型、電磁模型和靜磁模型。以電磁模型為例，其主要求解流程如圖1所示：

在每一個時間步長內(nèi)，先通過相對論運動方程求出當(dāng)前時刻粒子的位置和速度，然后對它們進行統(tǒng)計平均得到格點處的電荷密度分布和電流密度分布，然后通過格點上的電荷密度和電流密度利用麥克斯韋方程組求解出這個格點的電磁場，再利用插值的方法求出粒子所受的力，然后利用牛頓洛倫茲運動方程求解出粒子新的位置和速度。這個求解步驟反復(fù)迭代，直到系統(tǒng)趨于穩(wěn)定。

在上述求解流程中，電流源的求解是核心求解步驟，且存在嚴(yán)重的數(shù)據(jù)競爭。由于場是位于格點上的，所以為了求解場，需要將電流分配至格點上，而為了保持電流分配的精度并抑制數(shù)值噪聲，每個粒子產(chǎn)生的電流源會同時分配至多個格點，所以求解總的電流源時會存在多個粒子同時操作同一個格點的情況(即數(shù)據(jù)競爭)，而且隨著模擬網(wǎng)格數(shù)目以及粒子數(shù)目的增多，這一數(shù)據(jù)競爭的情況會愈演愈烈。

如果并行中未對上述電流源求解中的數(shù)據(jù)競爭進行處理，則并行結(jié)果會產(chǎn)生錯誤，所以為了保證并行計算結(jié)果的準(zhǔn)確性，數(shù)據(jù)競爭部分需單獨處理。目前對于這種情況，已有兩種主要的解決方案。

第一，加鎖的方式。假設(shè)N號線程在向J號網(wǎng)格寫入數(shù)據(jù)，其它線程都會等待N號線程寫入完畢，然后N號線程釋放J號網(wǎng)格的數(shù)據(jù)地址，其它線程才有權(quán)對其操作，這種解決方案可以得到正確的結(jié)果，但是線程之間的執(zhí)行順序是序列化的，沒有發(fā)揮出多線程能夠并行執(zhí)行的優(yōu)勢。

第二，歸約的方式。如圖2所示，每個線程計算兩個值，直到最后一步，所有數(shù)據(jù)加到了數(shù)組的第一個位置，得到了整個數(shù)組的和。這種方式相對加鎖的方式來講效率有明顯的提升，對于常規(guī)數(shù)據(jù)競爭問題加速效果明顯，但是對于粒子模擬數(shù)據(jù)競爭問題的并行是不適合的，下面以電流源求解為例進行說明：

每個粒子向周圍的格點分配電流值，將這些值附帶網(wǎng)格編號存儲，如圖3。由于粒子對網(wǎng)格分配電流是隨機的行為，故一個格點具有競爭的數(shù)據(jù)個數(shù)是未知的，競爭數(shù)據(jù)分布的位置也是未知的。所以為了使用歸約的方法處理該問題，首先要對粒子分配的電流按照電流所屬的網(wǎng)格編號進行排序，這樣才能使得所有具有競爭的數(shù)據(jù)分布在一起(如圖4所示)，然后進行歸約計算。