五點(diǎn)差分格式求解泊松方程并行算法的研究

以二維靜電場(chǎng)泊松方程數(shù)值求解的串行算法(雅可比迭代、超松弛迭代)為基礎(chǔ)，提出了五點(diǎn)差分格式超松弛迭代(SOR)求解二維靜電場(chǎng)泊松方程的并行算法，通過(guò)與雅可比迭代(Jacobi)并行算法的時(shí)間復(fù)雜度、加速比和空間復(fù)雜度進(jìn)行對(duì)比，得出超松弛迭代的并行算法具有更低的時(shí)間復(fù)雜度、空間復(fù)雜度和更高的加速比與效率。通過(guò)實(shí)驗(yàn)驗(yàn)證，CHIPIC軟件的泊松模塊宜采用超松弛迭代并行算法。
關(guān) 鍵 詞 雅可比迭代; 并行算法; 泊松; 超松弛迭代

CHIPIC[1]是我國(guó)自行開發(fā)的電磁粒子模擬[2]軟件，其模擬計(jì)算通?；ㄙM(fèi)大量的時(shí)間，因此有必要開發(fā)其并行版本。作為這一工作的前期實(shí)踐，本文對(duì)其靜電場(chǎng)計(jì)算模塊即泊松模塊的并行計(jì)算進(jìn)行了研究。
1 二維靜電場(chǎng)泊松方程的串行算法[3]
為簡(jiǎn)單明了地說(shuō)明算法的設(shè)計(jì)思想，本文采用一個(gè)最簡(jiǎn)單求解二維場(chǎng)域內(nèi)電位的例子。如圖1所示，一個(gè)長(zhǎng)直接地金屬矩形槽，其側(cè)壁與底面電位均為0，頂蓋電位為100。則求解場(chǎng)域內(nèi)電位?的方程為泊松方程(退化為拉普拉斯方程)：

2 二維靜電場(chǎng)泊松方程的并行算法
當(dāng)今國(guó)外的電磁粒子模擬軟件[6-7]并行版本大都是基于消息傳遞機(jī)制[8](MPI)的。MPI被當(dāng)前所有高性能并行機(jī)所支持，程序設(shè)計(jì)方便，并具有良好的擴(kuò)展性，非常適合于機(jī)群系統(tǒng)。
通用的求解泊松方程的并行模塊大都采用Jacobi并行迭代算法[8-9]，因?yàn)镴acobi迭代算法中各個(gè)更新操作是完全并行的，可以采用分塊策略。一般有一維分塊和二維分塊兩種，二維分塊的優(yōu)越性主要在于更好的擴(kuò)展性。由于在通常的實(shí)際問(wèn)題中網(wǎng)格數(shù)非常巨大，而PC機(jī)比較有限，目前的通用電磁粒子模擬軟件中采用一維分塊。SOR迭代算法每次計(jì)算第n+1次的U[i][j]時(shí)，都需要n+1次的U[i?1][j]和U[i][j?1]，初略看不適合分塊并行迭代。目前關(guān)于SOR的并行迭代算法主要有著色法[10]，但著色法可擴(kuò)展性差，不適合通用的電磁粒子模擬軟件，因此有必要開發(fā)出基于SOR分塊并行迭代算法。