一種多相并行粒子模擬的無線通信模式

一種多相并行粒子模擬的無線通信模式

1城市粒子并行計算中的生成和傳遞顆粒方法（pm）為復(fù)雜的顆粒網(wǎng)絡(luò)系統(tǒng)提供了一種靈活的處理方法，已經(jīng)廣泛使用到各個領(lǐng)域，成為許多研究人員的中心主題。由于各種粒子方法在處理問題的思想和方法上都有許多相似之處,中國科學(xué)院過程工程研究所的葛蔚研究員提出在各種粒子方法相似性的基礎(chǔ)上,為它們的應(yīng)用提供一個通用的并行計算軟件環(huán)境的設(shè)想,在多相反應(yīng)實驗室并行粒子模擬小組的努力下,已經(jīng)建立了這樣的一個通用平臺框架并應(yīng)用。粒子方法并行計算時,通常采用區(qū)域分解(domaindecomposition)法。將模擬區(qū)域劃分為若干個子區(qū)域,每個進程(對應(yīng)一個計算節(jié)點)負責(zé)計算一個子區(qū)域內(nèi)所有粒子,則這個子區(qū)域稱為該進程的計算區(qū)域。因此并行計算為粒子模擬系統(tǒng)巨大計算量提供了有效的解決方案。但是,并行計算給粒子模擬的程序設(shè)計和實現(xiàn)卻帶來了新的問題:相鄰計算區(qū)域交界附近的粒子往往會發(fā)生相互作用,對采用分布式存儲器的并行處理器系統(tǒng),這些粒子被分配在不同的進程上,進程不知道交界區(qū)域附近的粒子的信息,只知道自己計算區(qū)域內(nèi)的粒子的信息,因此必須通過數(shù)據(jù)通信,交換各自的粒子,才能使每個進程正確計算其計算區(qū)域內(nèi)粒子的受力。所以給并行程序的實現(xiàn)和調(diào)試工作帶來了新的困難和挑戰(zhàn)。Shift并行數(shù)據(jù)傳遞模式,可以簡化區(qū)域劃分后的進程間的通信。模擬二維平面區(qū)域分解的粒子,盡管與每個位于中間的區(qū)域周圍有8個區(qū)域;但采用Shift傳遞模式,只需和其中4個進行數(shù)據(jù)通信,就能知道它所需要的所有相鄰粒子,如圖1所示,甲區(qū)域只需和其相鄰的乙、丙、丁和戊進行數(shù)據(jù)通信即可。如此類似,模擬三維空間分解的粒子,中間區(qū)域只需和6個鄰區(qū)交換數(shù)據(jù)即可。當(dāng)處理器的區(qū)域相同時,每個處理器需要傳遞和接收的區(qū)域是有規(guī)則的(如圖2所示),Shift通信模式可以很順利,可以從任意坐標(biāo)軸方向開始傳遞,最后得到的粒子信息相同。但當(dāng)處理器的計算區(qū)域是動態(tài)劃分時,各個處理器的區(qū)域大小不一,它們所交換的區(qū)域形狀也不同,如果處理器和它的通信對象之間,在同向越過了一個處理器,則使用Shift或修正的Shift通信模式處理器間通信時會有問題而無法進行計算。如圖3所示動態(tài)劃分的區(qū)域,處理器乙2中的A區(qū)域的粒子信息,是處理器甲計算粒子受力所需,傳不到甲,因為甲和乙2在Y方向上被丁阻隔了。在Shift通信模式中,乙2中的A部分粒子信息首先沿X方向傳遞給了丁1,但是在目前平臺采用的Shift通信模式下,丁1在Y軸正方向上只能與丁通信,因此該部分信息不可能傳遞到甲。對于這種具有復(fù)雜拓撲結(jié)構(gòu)的區(qū)域劃分,需要一種新的通信模式才能滿足處理器之間的通信需求。2光學(xué)處理器通信的步驟本文用A112All并行通信模式,解決上述Shift通信模式問題。All2All的功能與MPI群集通信(collectivecommunications)里面的MPI＿Alltoall稍類似,但用非結(jié)構(gòu)化的通信模式,在數(shù)據(jù)交換之前每個進程之間的兩次握手確定通信對象,實現(xiàn)每個處理器只與其需要通信的處理器通信,而不是像MPI＿Alltoall與所有的處理器都廣播式地通信。在本文的All2All并行算法中,實際的物理模擬區(qū)域被分解為三維空間中的小盒子,每個處理器分配一個。如前所述,這就是負載的空間分解(spacedecompositon,SD)。在每一個時間步,每個處理器計算其所屬盒子內(nèi)的所有粒子受力,并更新它們的位置和速度。當(dāng)粒子由于運動而穿過其物理邊界時,就把它分配給新的處理器。為了計算其區(qū)域內(nèi)粒子的受力,處理器需要知道鄰近盒子內(nèi)的部分粒子信息,因此,SD算法中的通信要求,本質(zhì)上是局部性的。分配給每個處理器的盒子大小和形狀依據(jù)粒子數(shù)N和處理器數(shù)目P,以及實際模擬區(qū)域的長寬比,本文假定長寬比為長方體。在這些先決條件下,在每一方向上,用適當(dāng)?shù)奶幚砥鲾?shù)目以使每個盒子盡量為正方體。因為在粒子數(shù)N一定時,SD算法的通信開銷于盒子的表面積成正比。需要注意的一點是,盒子的長度可以大于或者小于受力計算的截斷半徑re和rs。在本文的SD算法中每一個處理器維持兩個數(shù)據(jù)結(jié)構(gòu),一個數(shù)據(jù)結(jié)構(gòu)表示其盒子內(nèi)的N/P個粒子,另一個表示其鄰近盒子內(nèi)的粒子。這些數(shù)據(jù)用鏈表存儲,以便粒子移動到新的盒子時插入和刪除。在每個時間步,處理器之間都靠通信以更新粒子信息。從鄰近盒子所屬的處理器獲取信息的通信方案如表1所示。數(shù)據(jù)正式傳遞前處理器之間有通信的握手過程?？v坐標(biāo)為發(fā)送方處理器ID,橫坐標(biāo)為接受方處理器ID,如果它們之間有通信,則用1表示,0表示不需要通信。則每行所有1的個數(shù)就表示該行需要發(fā)往各個其它處理器的消息總數(shù),1所對應(yīng)的列表示的是接受方處理器。同樣,每一列都表示一個接受序列,列中每個1所屬行的處理器即為發(fā)送方。每列1的個數(shù)即為該列需接受消息的處理器的總數(shù)。發(fā)送方和接受方進程之間的握手過程如下:步驟1.每個處理器都有一個維持全局每個盒子邊界的數(shù)據(jù)結(jié)構(gòu)。每個處理器檢查自己盒子內(nèi)已出邊界的粒子,此時檢查的邊界就是盒子的邊界。通過檢查其它所有處理器的盒子邊界,確定這些粒子應(yīng)該遷往哪些處理器。由此,發(fā)送方可計算以下幾個變量:粒子需要遷往的所有ID數(shù)組procs＿to＿,發(fā)送的消息總數(shù)nsends＿,發(fā)的消息內(nèi)包含的粒子總數(shù)數(shù)組lengths＿to＿。發(fā)送方的通信關(guān)系數(shù)組(由該進程需要與之通信的接受方ID構(gòu)成)很容易確定。通過MPI群集通信里提供的歸約函數(shù)MPI＿Reduce,所有處理器把其發(fā)送通信關(guān)系數(shù)組求和規(guī)約到0號處理器。步驟2.0號處理器通過MPI＿Scatter把規(guī)約后的結(jié)果散發(fā)給各處理器,則處理器得到的值,即為本次通信過程中需要接收的消息總數(shù)nrecvs＿。步驟3.由發(fā)送處理器根據(jù)其發(fā)送關(guān)系數(shù)組,向?qū)?yīng)的接受處理器發(fā)送二者信息交換的消息長度(這里指粒子數(shù)目)。步驟4.接收方根據(jù)Step2獲得的nrecvs＿,亂序接收對應(yīng)數(shù)目的消息數(shù)目。根據(jù)MPI提供的相應(yīng)機制,求得每一條接收到的消息對應(yīng)的發(fā)送處理器,以及該消息包含的粒子信息交換中的消息長度。由此,每個處理器都可以獲取以下幾個變量:需要接收來自于以下處理器的消息procs＿from＿,以及每個消息對應(yīng)的長度lengths＿from＿,以分配必要的接收緩沖區(qū);將接收的消息總數(shù)nrecvs＿。通過以上的步驟1～步驟4描述的握手過程,可以計算確定以下兩點:(1)每個處理器作為發(fā)送方需要與哪些處理器進行通信,以及通信時消息的長度,以便分配適當(dāng)?shù)陌l(fā)送緩沖區(qū)。(2)每個處理器作為接受方需要與哪些處理器進行通信,以及通信時消息的長度,以便分配適當(dāng)?shù)慕邮站彌_區(qū)。MPI有4種通信模式:標(biāo)準(zhǔn)通信模式、緩存通信模式、同步通信模式和就緒通信模式。由于通信經(jīng)常需要較長的時間,在阻塞通信還沒有結(jié)束的時候,處理器只能等待,這樣浪費了處理器的計算資源。因此要設(shè)法使計算與通信重疊,非阻塞通信可以達到這一目的。在本文實現(xiàn)處理器之間的消息交換中,接收消息采用非阻塞通信以提高處理器的利用率。一次消息交換通過4個步驟完成:(1)收方執(zhí)行非阻塞接收;(2)收方進行阻塞同步,以確保所有的接收操作,都在相應(yīng)的發(fā)送操作前就緒;(3)發(fā)方執(zhí)行就緒阻塞發(fā)送;(4)收方執(zhí)行等待接收操作,以確保完成接收操作。3movd粒子粒子模擬中,不同進程之間需交換的粒子主要有兩類:一是需移動的,即經(jīng)計算,有些粒子已經(jīng)出了其原來的盒子,應(yīng)該把它們遷移到相應(yīng)的處理器中去,這樣的粒子稱為Move粒子;一些是需復(fù)制的,即這些粒子沒有離開其原來所屬的處理器盒子,但相鄰處理器需要這些粒子的信息,所以把他們的信息復(fù)制到需要它的處理器上,這樣的粒子稱為Copy粒子。3.1浮點型數(shù)據(jù)的通信按照上面介紹的粒子遷移通信方法,實現(xiàn)Move粒子的遷移(Migrate)的步驟如下:(1)由各處理器檢查自己盒子內(nèi)的粒子,哪些是需要Move遷移出去的,以及他們應(yīng)遷往哪些處理器,并統(tǒng)計數(shù)目。這時檢查的邊界就是各自的計算區(qū)域盒子。(2)通過第二節(jié)中步驟1～步驟4所述算法,找出各處理器需從哪里接收其需要的粒子信息,及對于每一個這樣的需要從之接收消息的處理器,計算要接收的粒子總數(shù)(長度)。接下來進行通信域內(nèi)交換信息的準(zhǔn)備工作:由于粒子模擬中每個粒子的整型數(shù)據(jù)信息個數(shù)對于同一種粒子而言是一定的,而浮點型數(shù)據(jù)的個數(shù)卻不一定,所以在進行粒子信息交換時,本文把整型數(shù)據(jù)和浮點型數(shù)據(jù)分開交換的方法,通過兩次通信完成粒子信息的交換。整型數(shù)據(jù)通信發(fā)送前需要打包,即把發(fā)往處理器的粒子按處理器ID順序排列,把每個待發(fā)粒子的整型數(shù)據(jù)都放入一個連續(xù)的發(fā)送緩沖區(qū)中,同時開辟對應(yīng)的接收緩沖區(qū)。按照第2節(jié)所述的非阻塞通信步驟(1)～步驟(4),處理器把其需要接收的粒子信息,收到接收緩沖區(qū)。(3)完成解包,各處理器需要從各自接收緩沖區(qū)把粒子的信息提出來,生成對應(yīng)的粒子對象。(4)浮點型數(shù)據(jù)交換前的準(zhǔn)備工作:由于同類粒子的不同對象,所包含的浮點型數(shù)據(jù)的個數(shù)都可能不一樣,為了開辟發(fā)送緩沖區(qū)、接收緩沖區(qū)以及解包的需要,就需要把每個粒子的浮點型數(shù)據(jù)個數(shù)都統(tǒng)計出來后再進行通信。同時還需要把這些每個粒子的浮點型數(shù)據(jù)個數(shù)信息通知給相應(yīng)接收處理器,并且每個處理器也需要知道其需要接收的每個粒子對象的包含的浮點型數(shù)據(jù)個數(shù)信息。接下來進行浮點型數(shù)據(jù)的通信,方法如步驟(2)中所述。(5)進行通信后浮點型數(shù)據(jù)的解包工作,要把這些浮點型數(shù)據(jù)對應(yīng)到相應(yīng)的粒子對象上去,然后把這些新接收到的遷移粒子插入到本地的粒子鏈表上去。完成遷移工作。3.2檢查節(jié)點的遷移Copy粒子的遷移過程基本上與Move粒子相同,不同之處有以下兩點:(1)檢查哪些是Copy粒子,這些Copy粒子應(yīng)該復(fù)制傳遞給需求這些Copy粒子的處理器時所用的邊界不同。(2)粒子遷移后,Copy粒子遷移之后在接收處理器上的處理方法不同。Copy粒子詳細的遷移步驟描述如下:由各處理器各自檢查自己盒子內(nèi)的粒子,哪些是需要Copy遷移出去的,以及它們應(yīng)該遷往哪些處理器,統(tǒng)計好處理器的粒子數(shù)。這時檢查的邊界其實是發(fā)方計算區(qū)域盒子內(nèi)一定范圍,對于判斷哪些是收方處理器時,檢查的邊界就是其余盒子外一定范圍。如圖4所示,圖4(a)外邊界表示處理器A,圖4(b)內(nèi)邊界表示B的計算區(qū)域盒子。作為發(fā)方處理器A,需要Copy出去的粒子,位于圖4(a)灰色區(qū)域內(nèi)。檢查粒子需Copy到哪些處理器時,即檢查位于圖4(a)灰色區(qū)域內(nèi)的粒子,是否也位于處理器B的深灰色區(qū)域內(nèi)(圖4(b)),是,則B是A的接收者,需要注意的是,其粒子可能有多個接收者,尤其是位于盒子角落的。Copy粒子的整型數(shù)據(jù)和浮點型數(shù)據(jù)在粒子遷移中,處理方法和Move粒子基本相同,不同在于新接收到的Copy粒子插入本地的粒子鏈表上以后,要注明為Copy粒子,以備計算后幫助刪除。4ccommex-perod的實現(xiàn)過程實際模擬中,粒子組合方式常有不同,例如,不同的模擬,可能需用不同的粒子模型;而同一模擬中,粒子可能有多種類型或者多種粒徑混合而成。計算節(jié)點之間交換粒子數(shù)據(jù)時,對每一種粒子,其步驟往往都很相似。但面對不同的粒子組合方式,寫出不同的并行計算通信代碼,顯然是一種就事論事的個案處理方法,沒有通用性,不僅代碼編寫的工作量大,而且容易出錯,也將極大增加調(diào)試的工作量。因此所需要采用一種方案,它能夠根據(jù)傳遞粒子的類型,自動生成并行數(shù)據(jù)交換的程序?qū)崿F(xiàn)代碼。采用C++的范型編程和一些適當(dāng)?shù)姆夯记煽梢詫崿F(xiàn)這個目標(biāo)。A112All的泛化主要涉及兩個問題:對于粒子遷移函數(shù)的泛化和粒子鏈表初始化的泛化。這兩個問題采用GenericProgramming的方法加以解決,程序從源代碼到運行的過程,分為3個階段:(1)preprocessingperiod,所有宏和包含頭文件,在此階段得到替換和擴展。(2)compiling-timeperiod,此階段把第一階段生成的代碼編譯成目標(biāo)代碼,最后由鏈接器鏈接各目標(biāo)文件,最后生成可執(zhí)行文件。(3)run-timeperiod,運行時,內(nèi)核加載可執(zhí)行文件到內(nèi)存,并加載需要的動態(tài)鏈接庫,從main函數(shù)開始順序執(zhí)行語句。由這3個階段的先后順序可以知道,編譯期常數(shù)是不能夠用于預(yù)處理期的。第一方面,遷移函數(shù)的泛化類CCommExchange是本文提出的All2All通信類定義的一部分,它有2個模板參數(shù),一是粒子型別鏈表,二是templatetemplateparameter,設(shè)置其缺省值為打包解包類。用戶使用時只要指定第一個參數(shù)。整個通信類CCommExchange繼承自GenScatterHierarchy,而GenScatterHierarchy繼承自用typelist中每類實例化后的CCommPackUnpack類。所以CCommExchange中就有了typelist中每類粒子的信息。對不同粒子的管理則通過GenScatterHierarchy進行。在這一點,本文參考Andrei對Tuples的實現(xiàn)。在類中,有3個針對Move粒子遷移函數(shù)泛化的重載函數(shù),(1)函數(shù)是針對只有一種粒子的情況;(2)函數(shù)是針對所有情況定義的一個類內(nèi)的template函數(shù),它會根據(jù)typelist的長度進行相應(yīng)的處理;(3)函數(shù)是給用戶留的接口,可以看到此接口已去掉型別相關(guān)信息,即模擬體系中有幾類粒子,在整個通信域中進行通信對用戶來說是透明的。這也是程序通用化設(shè)計要達到的目的。函數(shù)重載的解析,發(fā)生在編譯期(compiling-timeperiod),所以這里發(fā)生的一切,也是不能帶到預(yù)處理階段(preprocessingperiod)的。另外2個函數(shù)的泛化與此類似,一是針對copy粒子遷移的MigrateCopyParticle(),另一是為了提高通信效率而設(shè)計的MigrateCopyDouble(),該函數(shù)在計算時利用上次遷移中的Copy粒子檢查結(jié)果,只遷移對應(yīng)粒子部分以及更新的Double部分,省了判斷哪些粒子需要遷移的檢查、通信域的設(shè)定以及解包時生成對象,節(jié)省了大量資源。對粒子鏈表初始化函數(shù)的泛化,需要考慮在模擬體系中粒子種類數(shù)。粒子只有一種類型時,粒子鏈表初始化函數(shù)聲明是:模擬體系中有兩種粒子時的函數(shù)聲明是:對于上述函數(shù)的泛化,不能簡單地采用重載的方法。本文采用宏條件判斷的方法解決這個問題,如下面這段程序所示。用戶在使用All2All通信模式時,需要指定模擬體系中有幾種粒子的類型。All2All實現(xiàn)范型設(shè)計后,留給用戶的是簡潔明了的編程接口,