有限元素法模擬問題的動態負載平衡之研究

Abstract

模擬是產品生命週期很重要的一個部份.藉著模擬我們可以預測實 際系統的行為卻不必建立一個真實的系統.模擬的例子有天氣預測,風動模 擬在模擬問題中,大部分需要利用偏微分方程的方法來模擬問題的區域.而 要得到精確的模擬結果必需花費很多的時間,平行模擬就是一種加速計算 的基本方法.但是要設計一個好的平行模擬演算法是相當困難的,因為我們 除了要平衡系統中所有處理器的負載之外,同時亦需使處理機間的通訊量 達最少. 因此在這篇論文裡我們設計了一個新的動態負載平衡方案. 以解決在動態與不均的環境下有限元素法的模擬問題.這個方案利用圖形 分割的技巧來確保整個系統在執行時的總通訊量很低.另一方面,藉著分群 編索引數的方式,大大降低了執行動態負載平衡所需要的時間.而系統初始 化時期所建立的分割資訊,亦能在往後系統的執行時再被使用.這使得花費 在動態負載平衡上的執行時間減少,但同時亦能維持系統中的低通訊量. Simulation is an important part of the product life cycle. Byusing simulation, we can predict the behavior of a real system withoutphysically building it. Examples of simulation computations include weather prediction, wind-tunnel simulation. Most simulation problemstake use of the technique to speed up computation. Parallel simulationis a fundamental technique to speed up computation. However, it is diffcult to design a good parallel simulation algorithmbecause we needto balance the load among processors while minimizing the amount of communication between processors. In this thesis, we develop a new dynamic load balancing scheme forfinite-element simulation problems in an adaptive and nonuniform environment.We take use of the technique of graph partitioning such that the total amountof communication bound is big-O (np)^1/2, where n represents the number ofvertices and p represents the number of processors. On the other hand, it hasgood efficiency by making use of the technique of graph mapping. The partitioninformation set up during the initialization period can be reused during runtime. This results in the decrease of time spent on the dynamic load balancingphase and the increase of processor utilization.