Abstract
這篇論文是關於一個流體力學問題的平行化. 這個流體力學問題使用 Vortex Filament 方法去模擬三維噴射流在軸向擾動下的行為. Vortex Filament 方法的優點是它主要關心流場, 因此 Vortex 的結構可以容易 追蹤. 缺點是, 當 Vortex 的結構破壞後, 程式會變得沒有效率.我們先 敘述直接平行化的方法. 直接平行化的方法是將資料以BLOCK 方式在 processors 之間作平均分割 .這種直接分割方式當 vortex 的 circulation 的值較小時,程式運作良好. 當circulation 的值變大時, 程式的效率就會下降, 這是因為隨著 iteration 增加, 分佈在 processors 間的 vortex 數目會不平衡的成長. 不同的 processors 將 會擁有不同的資料數目, 因此造成負載不平衡的問題為了解決 vortex 數 目不平衡的問題, 我們提出一個適應式資料結構, 它可以分散在 processors 間, 而且可以動態的作負載平衡( load balance ). 我們用 這個可調式資料結構來做負載平衡的實驗, 顯示負載平衡在這個程式會增 加效率我們的實驗是在分散計憶體的機器( distributed memory machine) 下進行, nCUBE2, IBM SP2, 和DEC Farms.我們的實驗顯示用 適應式資料結構作load balance的程式的效率比沒有作 load balance 的 程式好. 我們也以實驗為基礎推導了一個分析模式, 來幫助我們瞭解何時 動態的執行負載平衡( load balance scheme ). This thesis concerns the parallelization of an application on the fluid mechanic problem. This fluid problem uses Vortex Filament method to simulate the evolution of three- dimensionally periodical jet under axial perturbation. We first present the direct parallelization scheme by partitioning data by "BLOCK" distributed among processors. The direct parallelization method works well when there is no circulation in the impact of the problem. The direct parallelization scheme suffer performance degeneration when the circulation is not small, as the vortex number will grow inbalancely among processors as iteration evolve. To solve the load inbalancing problem, We then propose an adaptive data structure which can be distributed and dynamically load balanced. Our experiment is conducted on distributed memory parallel system including, nCUBE/2, IBM SP-2, and 8-node DEC Farms. Our experiment demonstrates that the load balancing scheme with adaptive data structure significantly out performs the unbalanced version. In addition, we develop an analytical model based on the experiments to guide when the load-balancing work should be performed at run time.