一個適用於分散式記憶體多處理機系統的自動資料切割技術

Abstract

自動決定程式中一個合適的資料切割方式對於分散式記憶體機器來說是一 個急需要解決的問題。目前大部分的論文研究皆將此困難的問題留給使用 者去做。在本篇論文中，我們提出了一個兼顧平行度及通訊次數的啟發式 方法來解決自動資料切割問題。首先，我們提出動態資料對齊演算法而偵 測出資料重新對齊的最佳時機。在決定程式中不同區段的資料對齊方式後 ，我們提出分配演算法去找出每個區段合適的資料分配方式。此外，我們 亦分析出我們方法的複雜度在多分項式時間內。最後展示我們的方法對於 實際科學應用程式的模擬結果而驗証我們方法的有效性。 Automatic determining a suitable data partitioning (data alignment and data distribution) scheme for a program is a critical important problem on parallelizing compilers for distributed memory machines. Most of the current research projects leave this tedious problem almost entirely to the user. In this thesis, we prsent a heuristic approach, which considers both parallelism and communication overhead, to the problem of automatic data partitioning on multicomputers. First, we propose dynamic alignment algorithms that can detect beneficial situations for realignment. After determining the alignment schemes in different phases of program, we propose distribution algorithms to find a suitable data distribution scheme for each phase. We also analyze the complexity of our method, which is within polynomial time. Finally, we present the simulation results and demonstrate the effectiveness of our approach for real-life scientific application Fortran programs.