臺灣博碩士論文加值系統

自谷歌推出pregel 以來，許多的大規模圖形處理系統也相繼被提
出，這些系統都基於整體同步並行計算模型或其他類似的模型以及多
樣化的最佳化策略來提升系統效能。例如：Mizan 藉由監控每個伺服
器的工作量並以執行時間來判斷每個伺服器的工作量是否平衡。如果
伺服器間的工作量不平衡，Mizan 會藉由移動節點的方式，將節點自
負載較重的伺服器搬移至負載較輕的伺服器上，藉此平衡每個伺服器
的工作量及降低系統執行時間。我們基於Mizan 的節點搬移計畫，實
作一個有效率的重新切圖計畫的圖形處理系統，稱為GPSer。我們的
系統使用統計學的工具，例如: 變異係數及相關係數，來改造搬移計
畫並判斷目前伺服器間的工作量是否平衡。我們的系統可以精確判斷
出目前每個伺服器的工作量，並決定是否透過搬移節點來達工作量平
衡。如伺服器間工作量不平衡，可快速地將每個伺服器的工作量收斂
在平衡狀態來提升系統效能。透過實驗，可觀察出我們的系統表現比
現有的動態負載平衡圖形處理系統(如:Mizan) 更佳。

Since the introduction of pregel by Google, several large-scale graphprocessing systems have been introduced. These systems are based on the bulk synchronous parallel model or other similar models and use various strategies to optimize system performance. For example, Mizan monitors
the workload of each worker to determine whether the workload between the workers is balanced with respect to the execution time. If the workload is unbalanced among workers, Mizan migrates nodes from overloaded workers to
under-loaded workers to balance the load among workers and minimize the total execution time. On the basis of Mizan’s migration plan, we implement a graph-processing system called GPSer with an efficient re-partitioning graph scheme. Our system uses statistical tools, e.g., coefficient of variation and correlation coefficient, to modify the migration plan and determine whether the workloads are balanced among all workers. Our system can accurately monitor current workloads and decide whether to migrate nodes among workers to balance the load. When imbalance arises, the workload of all workers can quickly converge to a balanced state, thereby enhancing the system performance. In experiment our system outperforms the state-of-the-art dynamic load-balancing graph processing-system, such as Mizan.

致謝 i
中文摘要 ii
Abstract iii
Contents iv
List of Figures vi
List of Tables viii
1 Introduction 1
2 Related Work 4
3 Dynamic Load Balancing 8
3.1 Determine imbalance 8
3.2 Select Migration Criteria 9
3.3 Pair workers 10
3.4 Determine nodes to migrate 11
3.5 Migrate nodes 11
4 Architecture 12
4.1 BSP engine 12
4.2 Storage Manager 13
4.3 Communicator 13
4.4 Migration planner 14
5 Experimental 15
5.1 Experimental Setup 15
5.2 Experimental Design 16
5.2.1 Partitioning Strategies 16
5.2.2 Overall Performance 22
6 Conclusion 26
Bibliography 27

[1] Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: A system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pages 135–146. ACM, 2010.
[2] Apache giraph. http://giraph.apache.org/.
[3] Apache hama. https://hama.apache.org/.
[4] Leslie G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103–111, August 1990.
[5] Zuhair Khayyat, Karim Awara, Amani Alonazi, Hani Jamjoom, Dan Williams, and Panos Kalnis. Mizan: A system for dynamic load balancing in large-scale graph processing. In Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys ’13, pages 169–182. ACM, 2013.
[6] Ron Larson and Besty Farber. Elementary statistics - picturing the world. In Elementary Statistics - Picturing the World, chapter 2, pages 98,499. Pearson Prentice Hall, 2009.
[7] Goldenorb, a cloud-based open source project for massive- scale graph analysis. https://github.com/jzachr/goldenorb.
[8] Phoebus. https://github.com/xslogic/phoebus.
[9] Li-Yung Ho, Tsung-Han Li, Jan-Jan Wu, and Pangfeng Liu. Kylin: An efficient and scalable graph data processing system. In Proceedings of the 2013 IEEE Inter-national Conference on Big Data, 6-9 October 2013, Santa Clara, CA, USA, pages 193–198, 2013.
[10] Rishan Chen, Mao Yang, Xuetian Weng, Byron Choi, Bingsheng He, and Xiaoming Li. Improving large graph processing on partitioned graphs in the cloud. In Proceedings of the Third ACM Symposium on Cloud Computing, SoCC ’12, pages 3:1–3:13, New York, NY, USA, 2012. ACM.
[11] Apache hadoop. http://hadoop.apache.org/.
[12] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, January 2008.
[13] Yucheng Low, Danny Bickson, Joseph Gonzalez, Carlos Guestrin, Aapo Kyrola, and Joseph M. Hellerstein. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8):716–727, April 2012.
[14] Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. Graphchi: Large-scale graph computation on just a pc. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, pages 31–46, Berkeley, CA, USA, 2012. USENIX Association.
[15] Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin.
Powergraph: Distributed graph-parallel computation on natural graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, pages 17–30, Berkeley, CA, USA, 2012. USENIX Association.
[16] Semih Salihoglu and Jennifer Widom. Gps: A graph processing system. In Proceedings of the 25th International Conference on Scientific and Statistical Database Management, SSDBM, pages 22:1–22:12, New York, NY, USA, 2013. ACM.
[17] Apache mina. https://mina.apache.org/.
[18] Standard score. https://en.wikipedia.org/wiki/Standard_score.
[19] Hadoop distributed file system. https://hadoop.apache.org/ docs/ r1.2.1/hdfs_design.html.
[20] C api libhdfs. https://hadoop.apache.org/docs/r1.2.1/libhdfs.html.
[21] Mpich. http://www.mpich.org/.
[22] Mizan source code. https://code.google.com/archive/p/mizan-graph-bsp/downloads.
[23] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. In Proceedings of the 7th International World Wide Web Conference, pages 161–172, 1998.
[24] U. Kang, Charalampos E. Tsourakakis, Ana Paula Appel, Christos Faloutsos, and Jure Leskovec. Hadi: Mining radii of large graphs. ACM Transactions on Knowledge Discovery from Data, 5(2):8:1–8:24, February 2011.
[25] SNAP: Stanford network analysis platform. https://snap.stanford.edu/snap/.
[26] George Karypis and Vipin Kumar. Multilevelk-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96–129, 1998.