[發明專利]均衡非結構網格單元計算量的并行負載均衡方法

有效

• 申請號: 201910853409.0
• 申請日: 2019-09-10
• 公開（公告）號: CN110633149B
• 公開（公告）日: 2021-06-04
• 發明（設計）人: 熊敏;徐傳福;劉雍;高翔;李大力;車永剛;吳誠堃;郭曉威;張翔;李超;藍龍;王思齊;王正華
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 長沙中科啟明知識產權代理事務所(普通合伙) 43226
• 代理人: 任合明

1.一種均衡非結構網格單元計算量的并行負載均衡方法，其特征在于包括以下步驟：

第一步，生成二維非結構網格，方法是：

1.1將非結構網格工程應用需要計算的二維空間進行網格化處理，生成非結構網格并輸出二維非結構網格相關文件；二維非結構網格相關文件包括網格單元文件、網格點文件、網格邊文件、網格單元的鄰接單元文件、網格點的鄰接單元文件、網格邊的鄰接單元文件；

1.2根據非結構網格相關文件初始化相關數據結構，方法是：

1.2.1令網格單元文件為網格單元數組cs，其中N_c為網格單元總數，C_kc為第kc個網格單元；網格單元采用網格點編號數組表示，C_kc＝{kp₁,...,kp_w,...,kp_W}表示第kc個網格單元由第kp₁,...,kp_w,...,kp_W個網格點構成，是一個W邊形網格單元，W為正整數，1≤w≤W；

1.2.2令網格點文件為網格點數組pts，其中N_pt為網格點總數，Pt_kp為第kp個網格點；網格點采用笛卡爾坐標數組表示，Pt_kp＝(x,y)表示第kp個網格點的坐標為(x,y)，x,y為實數；

1.2.3令網格單元的鄰接單元文件為數組cCells，其中CC_kc表示網格單元C_kc的鄰接網格單元編號組成的數組；

1.2.4令網格點的鄰接單元文件為數組pCells，其中PC_kp表示網格點Pt_kp的鄰接網格單元編號組成的數組；

第二步，使用非結構網格結構化處理方法對非結構網格相關文件進行局部化，生成非結構網格局部方向數組和關鍵元素數組，方法是：

2.1根據非結構網格相關數據結構，定義并初始化非結構網格單元的關鍵元素數組和非結構網格局部方向數組，方法是：

2.1.1定義關鍵元素數組其中El_kc為C_kc的關鍵元素編號組成的數組；三角形網格單元的關鍵元素為3條網格邊和1個網格點，四邊形網格單元的關鍵元素為4條網格邊，初始化均為{0,0,0,0}；

2.1.2根據keyEl定義非結構網格局部方向數組locDir，其中LD_kc表示網格單元C_kc的局部方向向量組成的數組，LD_kc包含4個數據項，分別表示C_kc的4個局部方向向量，由El_kc確定：

LD_kc[1]為El_kc[3]邊中點指向El_kc[1]邊中點構成的向量；

若C_kc為四邊形，LD_kc[2]為El_kc[4]邊中點指向El_kc[2]邊中點構成的向量；若C_kc為三角形，LD_kc[2]為El_kc[4]網格點指向El_kc[2]邊中點構成的向量；

LD_kc[3]為El_kc[1]邊中點指向El_kc[3]邊中點構成的向量；

若C_kc為四邊形，LD_kc[4]為El_kc[2]邊中點指向El_kc[4]邊中點構成的向量；若C_kc為三角形，LD_kc[4]為El_kc[2]邊中點指向El_kc[4]網格點構成的向量；

將的每一項都初始化為零向量；

2.2采用陣面推進確定非結構網格的關鍵元素和局部方向，即進行非結構網格結構化處理，方法是：

2.2.1定義并初始化陣面推進相關數據結構，方法是：

2.2.1.1定義并初始化陣面數組fronts，fronts為動態數組，數據項個數記為N_f，每一項表示已進行訪問的網格點的編號；fronts初始化為位于壁面邊界即物體表面的網格點的編號數組，N_f初始化為位于壁面邊界的網格點的總數；

2.2.1.2定義并初始化下一陣面數組nextFronts，nextFronts為動態數組，表示需要加入fronts的網格點的編號，nextFronts的數據項個數記為N_nf；nextFronts初始化為空集，N_nf初始化為0；

2.2.1.3初始化陣面層數組frontsLevel，其中Fl_kp表示網格點Pt_kp的陣面層值；若kp在數組fronts中，初始化Fl_kp＝0，否則令Fl_kp＝-1；

2.2.1.4定義陣面層變量n，表示frontsLevel中所有數據項的最大值，n初始化為0；

2.2.1.5初始化fronts的三個索引：令頭索引head＝0、令尾索引tail＝N_f、令最終尾索引finalTail＝N_f；

2.2.2以head為fronts索引，獲取網格點的編號front[head]，記front[head]＝j,1≤j≤N_pt；

2.2.3以j為網格點的鄰接單元數組pCells的索引，獲取所有與網格點Pt_j相鄰的網格單元編號組成的數組PC_j，記PC_j的數據項總數為PCnum；

2.2.4初始化網格單元索引i＝1；

2.2.5以i為PC_j的索引，獲取第i個與Pt_j相鄰的網格單元編號PC_j[i]，令o＝PC_j[i],1≤o≤N_c；若El_o[1]＝0，則C_o的關鍵元素和局部方向還沒有確定，轉2.2.6；若El_o[1]≠0，轉2.2.9；

2.2.6根據網格單元數組cs判斷C_o的形狀，若C_o包含三個數據項，說明C_o為三角形，轉2.2.7；否則C_o包含四個數據項，轉2.2.8；

2.2.7確定三角形網格單元C_o的關鍵元素，得到El_o，根據El_o計算得到局部向量LD_o，并更新nextFronts，轉2.2.9；

2.2.8確定四邊形網格單元C_o的關鍵元素，得到El_o，根據El_o計算得到局部向量LD_o，并更新nextFronts，轉2.2.9；

2.2.9令i＝i+1，若iPCnum+1，轉2.2.5；否則轉2.2.10；

2.2.10令head＝head+1，若headtail+1，轉2.2.2；否則轉2.2.11；

2.2.11根據nextFronts更新fronts、frontsLevel、n、tail及finalTail，具體步驟為：

2.2.11.1將nextFronts的數據項加入到fronts中，更新N_f＝N_f+N_nf；

2.2.11.2更新frontsLevel中數據項Fl_kp＝n+1，其中kp為nextFronts的數據項；

2.2.11.3更新n＝n+1；

2.2.11.4更新nextFronts為空集，令N_nf＝0；

2.2.11.5更新tail＝finalTail＝N_f；

2.2.12若headfinalTail+1，轉2.2.2；否則所有網格單元的關鍵元素和局部方向都已確定，得到關鍵元素數組keyEl和局部方向數組locDir，轉第三步；

第三步，基于非結構網格局部方向數組，采用遞歸選擇模板的方式進行網格單元之間計算量層面的負載均衡，方法是：

3.1根據第一步生成的非結構網格相關文件初始化網格邊數組，令網格邊文件為網格邊數組eds，其中N_e為網格邊總數，E_ke為第ke條網格邊；網格邊采用頂點即網格邊兩端的網格點編號數組表示，E_ke＝{kp₁,kp₂}表示第ke條網格邊的兩個頂點分別為第kp₁,kp₂個網格點；

3.2根據第一步生成的非結構網格相關文件初始化網格邊的鄰接單元數組，令網格邊的鄰接單元文件為數組eCells，其中EC_ke表示網格邊E_ke的鄰接網格單元數組；

3.3定義并初始化模板單元個數N，N為正整數，表示需要為每個網格單元選擇的模板單元個數，也為4個方向的總模板單元個數，N與網格單元的計算量成正比；

3.4定義并初始化模板單元數組stencil，其中S_kc是C_kc的模板單元編號組成的數組，S_kc有N個數據項；將S_kc的每個數據項都初始化為0；

3.5初始化網格單元遞歸的單元索引kc＝1；

3.6以kc為局部方向數組locDir和關鍵元素數組keyEl的索引，分別獲取C_kc的4個局部方向向量：LD_kc[1]、LD_kc[2]、LD_kc[3]、LD_kc[4]，以及4個局部方向對應的4個關鍵元素：El_kc[1]、El_kc[2]、El_kc[3]、El_kc[4]；

3.7初始化局部方向索引j＝1；

3.8若C_kc為三角形網格且j＝4，LD_kc[j]對應的關鍵元素El_kc[4]為網格點，轉3.9進行按點模板選擇；若C_kc不為三角形網格或j≠4，LD_kc[j]對應的關鍵元素El_kc[j]為網格邊，轉3.10進入按邊模板選擇；

3.9沿局部方向LD_kc[j]進行按點模板選擇，具體步驟為：

3.9.1初始化遞歸次數n＝N/4；

3.9.2定義并初始化遞歸相關參數，對按點選擇的遞歸參數進行初始化：令方向向量參數dirA＝LD_kc[j]，單元參數cellA＝kc，點參數poiA＝El_kc[j]；

3.9.3根據遞歸相關參數dirA,cellA,poiA以及網格點的鄰接單元數組pCells進行模板單元選擇，具體步驟如下：

3.9.3.1以poiA為pCells的索引，獲取與網格點Pt_poiA鄰接的單元的編號數組pCells[poiA]；

3.9.3.2從數組pCells[poiA]的網格單元中，選出C_kc的模板單元C_tmp，其中tmp是pCells[poiA]的數據項，使得向量與dirA的夾角最小，指以C_cellA中心為起點，C_tmp中心為終點的向量；

3.9.3.3根據C_tmp更新模板單元數組stencil，方法是將數組S_kc中第一個為0的數據項更新為C_tmp；

3.9.4令n＝n-1，若n0，轉3.9.5；若n≤0，轉3.11；

3.9.5根據遞歸相關參數dirA,cellA,poiA和選出的模板單元C_tmp更新下一次遞歸的相關參數，并確定下一次遞歸的模板選擇方式，dirA,cellA,poiA更新方法是：

3.9.5.1令cellA＝tmp，即將C_cellA更新為C_tmp以保證遞歸沿局部方向LD_kc[j]進行；

3.9.5.2若poiA＝El_tmp[4]，轉3.9.5.3；若poiA≠El_tmp[4]，轉3.9.5.4；

3.9.5.3優先按C_tmp的局部方向更新dirA，并確定下一次遞歸的模板選擇方式，方法是令dirA＝LD_tmp[2]；令邊參數edgA＝El_tmp[2]，轉3.10.3；

3.9.5.4按網格拓撲信息更新dirA，并確定下一次遞歸的模板選擇方式：以tmp為網格單元數組cs的索引，獲取C_tmp的三個頂點，三個頂點分別為Pt_poiA、Pt_kp1和Pt_kp2，其中1≤kp1≤N_pt,1≤kp2≤N_pt；從Pt_kp1、Pt_kp2以及它們構成的網格邊E_ke的中點midPt這三個點中選出點selPt，使得向量與dirA的夾角最小，是以Pt_poiA為起點，以selPt為終點的向量；基于這樣的網格拓撲信息，令若selPt＝Pt_kp1或Pt_kp2，則令poiA＝kp1或kp2，轉3.9.3按點選擇；否則selPt＝midPt，指向的關鍵元素為網格邊E_ke的中點，則初始化新的遞歸相關參數：令邊參數edgA＝ke，轉3.10.3按邊選擇；

3.10沿局部方向LD_kc[j]進行按邊模板選擇，方法為：

3.10.1初始化遞歸次數n＝N/4；

3.10.2定義并初始化遞歸相關參數，對按邊選擇的遞歸參數進行初始化：令方向向量參數dirA＝LD_kc[j]，單元參數cellA＝kc，邊參數edgA＝El_kc[j]；

3.10.3根據遞歸相關參數dirA,cellA,edgA以及網格邊的鄰接單元數組eCells進行模板單元選擇，具體方法為：

3.10.3.1以edgA為eCells的索引，獲取網格邊E_edgA的鄰接單元數組eCells[edgA]；

3.10.3.2根據eCells[edgA]選擇按邊選擇的模板單元：選擇C_tmp為本次按邊選擇的C_kc的模板；

3.10.3.3根據C_tmp更新模板單元數組stencil，方法是將數組S_kc中第一個為0的數據項更新為C_tmp；

3.10.4令n＝n-1，若n0，轉3.10.5；若n≤0，轉3.11；

3.10.5根據遞歸相關參數dirA,cellA,poiA和選出的模板單元C_tmp更新下一次遞歸的相關參數并確定其模板選擇方式，dirA,cellA,poiA更新方法如下：

3.10.5.1令cellA＝tmp；

3.10.5.2按C_tmp的局部方向更新dirA，并確定下一次遞歸的模板選擇方式：

若edgA＝El_tmp[1]則更新dirA＝LD_tmp[3]，更新邊參數edgA＝El_tmp[3]，轉3.10.3按邊選擇；

若edgA＝El_tmp[3]則更新dirA＝LD_tmp[1]，更新邊參數edgA＝El_tmp[1]，轉3.10.3按邊選擇；

若edgA＝El_tmp[2]則更新dirA＝LD_tmp[4]，點參數poiA＝El_tmp[4]，轉3.9.3按點選擇；

3.11令j＝j+1，若j4，則C_kc的4個局部方向都已進行模板選擇，轉3.12；若j≤4，轉3.8；

3.12令kc＝kc+1，若kcN_c，則所有網格單元都已選擇N個模板單元，即模板單元數組stencil中每個數據項都已生成完畢，轉3.13；若kc≤N_c，轉3.6；

3.13將模板單元數組stencil輸出到模板單元文件，通過為每個非結構網格單元分配相同個數模板單元的方式，為每個非結構網格單元分配相同的計算量；模板單元數組其中數組S_kc中包含N個數據項，即每個網格單元都具有N個模板單元；

第四步，根據處理器信息、模板單元文件、網格相關數據結構以及網格鄰接關系數據結構，采用網格剖分方法進行處理器之間網格量層面的負載均衡，生成子網格區域的非結構網格相關文件和子網格區域的模板單元文件，采用子網格區域分配的方式將計算量分配給處理器，方法是：

4.1根據處理器總數及各處理器計算能力，初始化處理器計算能力數組Ps，其中N_p為處理器總數，P_i為第i個處理器的計算能力；

4.2根據處理器計算能力數組Ps及N_p,N_c，計算各處理器的最優網格量：第i個處理器的最優網格量其中1≤k≤N_p且k為整數；

4.3剖分非結構網格：按照M_i將第一步生成的非結構網格剖分成N_p個子網格區域，第i個子網格區域的網格量等于最優網格量M_i，其中1≤i≤N_p；剖分后生成子網格區域的非結構網格相關文件，剖分后還生成子網格區域的模板單元文件，子網格區域的模板單元文件是第3.13步生成的模板單元文件的子集；子網格區域的模板單元文件中每個網格單元的計算量仍然相等，記為N_com；

4.4采用子網格區域分配的方式將計算量分配給處理器：將第i個子網格區域的網格量及模板單元文件分配給第i個處理器，其中1≤i≤N_p，第i個處理器獲得M_i個網格單元，即獲得的計算量為N_com·M_i。