分散式記憶體平行電腦上適應性資料平行計算之研究

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.