Title: 分散式記憶體平行電腦上適應性資料平行計算之研究
Adaptive Data-Parallel Computations on Distributed-Memory Multicomputers
Authors: 黃國展
Huang, Kuo-Chan
王豐堅
Feng-Jian Wang
資訊科學與工程研究所
Keywords: 資料平行計算;分散式記憶體平行電腦;動態性平行系統;適應性計算;軟體設計模式;物件導向技術;data-parallel computation;distributed-memory multicomputer;dynamic parallel system;adaptive computation;software design pattern;object-oriented technology
Issue Date: 1997
Abstract: 本論文描述在分散式記憶體平行電腦上關於資料平行計算之適應性排程
的研究成果。此研究著重在平行系統的動態行為及其對執行效能的影響上
。我們發展了一個適應性資料平行計算模型(ADPCM),用來有效地描述程
式及系統的動態行為。奠基於ADPCM,我們探討了適應性資料平行計算中
兩個重要的課題:適應性處理器配置(APA)及資料分割與發送(DPD) 。本
論文採用解析與實驗並重的方式來探討這兩個問題。實驗結果顯示適應性
計算的技術能夠有效地增進動態性平行系統的執行效能。根據這些實驗,
我們發展出一個確定性效能模擬方法(DPSM),以量化的方式來有效地分析
及評估不同的處理器配置及資料分割與發送的方法。藉由DPSM的輔助,我
們發展出一組高效率的演算法及經驗法則,可用來解決ADPCM模式之平行
系統上的適應性處理器配置及資料分割與發送的問題。此外,適應性平行
程式的發展遠比一般平行程式來得複雜,為了幫助程式發展者有效地開發
適應性平行程式,本論文也提出了兩個軟體設計模式(software design
pattern),用來輔助平行程式發展中工作管理(task management)及資料
分割與發送(data partition and distribution)的問題。這兩個模式採
用物件導向的技術,可降低軟體複雜度並促進設計層次的軟體再利用(
software reuse)。 總而言之,本論文中的解析性與實驗性研究促進
了對動態性平行系統行為模式的了解。由於奠基於實際計算環境中的實際
平行系統,所發展出來的方法可有效地改進寬鬆性同步系統(loosely-
synchronous systems) 的執行效能,並可被擴充應用至其他種類的平行
系統上。
This thesis presents adaptively scheduling data-parallel
computation onto distributed-memory multicomputers. An Adaptive
Data-Parallel Computation Model (ADPCM) developed provides
abstract representation of program and system behavior. Based on
ADPCM, two important issues in adaptive data-parallel
computation, the Adaptive Processor Allocation (ADP) and Data
Partition and Distribution (DPD) problems, are addressed. A
combination of both analytical and experimental techniques is
applied to the problems. Experimental results indicate that
adaptive computation can effectively improve the runtime
performance of dynamic parallel systems. A deterministic
performance simulation method (DPSM) developed provides
qualitative insight as well as efficient quantitative evaluation
of different APA and DPD methods. Based on DPSM, a set of
efficient algorithms and heuristics have been developed to solve
the APA and DPD problems for ADPCM based systems. To effectively
develop adaptive programs, this thesis presents two object-
oriented software design patterns addressing the issues of task
management and data partition and distribution in parallel
programming. In summary, the analytical and experimental
results in the thesis contribute towards the understanding of
fundamental behaviors of dynamic parallel systems. Based on real
applications running on real computing environments,the
developed approaches can improve runtime performance of loosely-
synchronous systems, and can be easily extended for other kinds
of parallel systems.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT860392006
http://hdl.handle.net/11536/62733
Appears in Collections:Thesis