臺灣博碩士論文加值系統

因應運算雲端化的使用需求，如何提升平行程式在雲端平台上的執行效率是一個熱門的話題，運行於雲端平台的應用程式分成兩種類型: 計算密集型和通訊密集型。在運行計算密集型的程式中，節點間的效能差異會影響工作運作的並行度，而在運行通訊密集型的程式中，工作之間通訊速度會影響資料交換的效率，為了減少通訊延遲，將具有高資料量交換的工作們分配到高網路效能的處理單元，此技術稱為通訊感知實現工作映射(communication-aware task mapping)。
　　本論文以探討通訊感知實現工作映射的雲端運算為出發點，以減少通訊延遲為目標，由於網際網路的速度充滿了不確定性，而實際分析底層網路拓樸與硬體效能是相當耗費資源的，於是我們提出一個針對建構雲端連線類型實現工作映射的方法，透過使用者以分離的方式調度雲端運算資源以集中具有高資料量交換的程序於相同的節點，最後根據運算節點異質性定義負載指標與提出節點過載的解決方案。為了有效分析雲端工作之間的複雜通訊與統一管理及分配運算資源，我們參考Chiu和Guo提出的MPI Kernel Cluster裝載於Kernel Distributed Computing Management，借助KDCM分析運算工作並分派工作給節點的能力，和我們改良MPIKC分散式運算叢集的Communication System以建構足以應付複雜資料傳遞拓樸的通訊管道。MPIKC與KDCM緊密的配合，提供使用者以管線化考量而設計的應用程式的適切性，大幅優化通訊密集類型程式的執行效能。
　　最後，我們以兩個通訊密集型程式實驗，分別是訓練類神經網路與進階加密標準的加密程式，比較程序在各種分配狀況下的運行時間，結果顯示本論文的方法最多可省下12倍的運行時間，證實本論文所提出的設計可有效減少平行程式的運行時間。

In order to meet the operational requirements of cloud computing, how to improve the performance of parallel applications on a cloud platform is a hot topic. There are two types of applications running on the cloud platform: computation-intensive and communication-intensive. In running a computation-intensive program, the difference in performance of hardware between nodes can affect the parallelism of the work; and in the communication-intensive program, the communication speed within tasks can affect the efficiency of data exchange. To optimize communication, tasks that exchange lots of data should be mapped to processing units that have a high network performance. This technique is called communication-aware task mapping.
In this paper, we explore the communication-aware task mapping as the starting point to reduce the communication latency as the goal. Because the speed of the Internet is full of uncertainty, and it is impractical to actually analyze the underlying network topology and hardware performance, so we propose a method to implement task mapping based on building a cloud connection type. The user can dispatch the cloud computing resources as the separated way to collect processes with high data communication rates at the same node. Finally, we also define the load status of different node according to the heterogeneity of node. In order to analyze the complex communication within tasks effectively and allocate computing resources more easily, we adopt MPI Kernel Cluster on Kernel Distributed Computing Management, proposed by Chiu and Guo. By its ability to analyze and dispatch tasks, and we improved MPIKC''s Communication System to build a communication channel that is sufficient to handle complex data transfer topology. As MPIKC and KDCM fit tightly, they provide the feasibility of the program to be designed in a pipeline and significantly optimize the performance of communication-intensive types of programs.
At the end, we experimented with two communication-intensive programs, respectively, training Neural Network and Advanced Encryption Standard encryption program. We compare the running time of the process under various distribution conditions and the results show that the method of our purpose can save up to 12 times running time. We confirm that our purpose can effectively reduce the running time of parallel program.

論文審定書 i
論文公開授權書 ii
誌謝 iii
摘要 iv
Abstract v
目錄 vii
圖次 x
表次 xiii
第1章 簡介 1
1.1 研究動機 1
1.2 研究目的 1
1.3 論文架構 2
第2章 背景知識與相關研究 3
2.1 MPI程式運行於異質節點 3
2.1.1 定義節點效能方式 3
2.1.2 運行process的數量與完成時間研究 4
2.1.3 結論 6
2.2 平行程式的設計與排程 7
2.2.1 平行程式 7
2.2.2 工作排程 8
2.3 Communication-aware task mapping 10
2.3.1 Clustering-based method 10
2.3.2 CloudMap method 13
2.3.3 通訊感知平台分析 18
2.4 建構於核心環境之MPI雲端運算平台分析討論 19
2.4.1 MPIKC系統架構 19
2.4.2 MPI Launcher 21
2.4.3 Communication System 23
2.4.4 MPIKC on KDCM 24
2.4.5 MPI雲端運算平台效能分析 27
第3章 運行於雲端運算平台KDCM之最佳化MPI應用程式設計機制 28
3.1 雲端平台服務 28
3.1.1 運算服務請求 28
3.1.2 KDCM server 29
3.2 MPIKC系統建構機制改良 30
3.2.1 MPIKC 建構流程 30
3.2.2 Communication peer system 34
3.3 Task mapping implemented in KDCM 37
3.3.1 目標方程式與限制式 38
3.3.2 ReGroup 機制 40
3.3.3 Task mapping總結 48
第4章 實現成果與分析 49
4.1 MPI應用程式工作分配與資料切割方式 49
4.1.1 類神經網路(Neural Network) 49
4.1.2 進階加密標準(Advanced Encryption Standard) 51
4.2 工作分配與實驗結果 51
4.2.1 測試環境 52
4.2.2 程序數負載不平衡 52
4.2.3 程序數負載平衡 55
4.2.4 ReGroup機制驗證 60
4.3 實現成果總結 64
第5章 總結 65
參考文獻 66

[1]A. Saad and A. El-Mahdy, “Network Topology Identification for Cloud Instances,” in International Conference on Cloud and Green Computing, 2013, pp. 92–98.
[2]M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia, “A view of cloud computing,” Commun. ACM, vol. 53, no. 4, pp. 50–58, April 2010.
[3]B. Hayes, “Cloud computing,” Commun. ACM, vol. 51, no. 7, pp. 9–11, 2008.
[4]A. Iosup, S. Ostermann, and M. Yigitbasi, “Performance analysis of cloud computing services for many-tasks scientific computing,” IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. June, pp. 931–945, 2011.
[5]A. Bhatele, A. R. Titus, J. J. Thiagarajan, N. Jain, T. Gamblin, P.-T. Bremer, M. Schulz, and L. V. Kale, Identifying the Culprits Behind Network Congestion,” in IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2015, pp. 113–122.
[6]Emmanuell D. Carre˜no, Matthias Diener, Eduardo H. M. Cruz, Philippe O. A. Navaux.“Automatic Communication Optimization of Parallel Applications in Public Clouds, ”in 2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, 2016.
[7]W. Gropp, E. Lusk, and A. Skjellum, Using MPI: portable parallel programming with the message-passing interface. Cambridge, MA, USA: MIT Press, 1994.
[8]Nayandeep Sran, Navdeep kaur , Comparative Analysis of Existing Load balancing techniques in cloud computing, International Journal of Engineering Science Invention, Vol-2 Issue-1 2013.
[9]Sun Nian, Liang Guangmin, "Dynamic Load Balancing Algorithm for MPI Parallel Computing", 2009 International Conference on New Trends in Information and Service Science (NISS ''09), 2009, pp. 95-99.
[10]Kunz T, “The Influence of Different Workload Descriptions on a Heuristic Load Balancing Scheme [J]. IEEE Trans. on Software Eng”, 1991, 17(7): 725-730.
[11]Igor Grudenic, Stjepan Gros, Nikola Bogunovic, “Load Balancing MPI algorithm for high throughput Applications”, Faculty of Electrical Engineering and Computing, University of Zagreb Unska 3,10000 Zagreb Croatia.
[12]P. Fan, J. Wang, Z. Zheng, and M. R. Lyu, “Toward optimal deployment of communication-intensive cloud applications,” in Proc. 4th Int’l Conf. On Cloud Computing (CLOUD’ 11), 2011, pp. 460–467.
[13]L. Yin, J. Sun, L. Zhao, C. Cui, J. Xiao, and C. Yu, “Joint Scheduling of Data and Computation in Geo-Distributed Cloud Systems” , in 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 2015, pp. 657–666.
[14]林信良.(2016, July 1). 關注平行程式設計. Retrieved July 4, 2017, from http://www.ithome.com.tw/voice/106886
[15]Garlan D, Shaw M. Software Architecture: Perspectives on an Emerging Discipline. Prentice Hall; 1996
[16]Jih-Ching Chiu, Bao-Ren Guo, Chao-Chih Hsun, “Message-Passing Interface Cluster Build upon System Kernel Environment”, in 2016 International Computer Symposium, 2016
[17]F. Pellegrini, “Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs,” in Scalable High-Performance Computing Conference (SHPCC), 1994, pp. 486–493.
[18]張藝瀚. (2014, April). Retrieved July 4, 2017. From http://programmermagazine.github.io/201404/htm/focus4.html
[19]MogerWu. (2011,January 5). Retrieved July 4, 2017. From http://mogerwu.pixnet.net/blog/post/27893873