Task Scheduling And Synchronization Controlling In A BSP-based Large Scale Graph Processing System

With the rapid growth of emerging applications like social network analysis, semantic Web analysis, and bioinformatics network analysis, it is urgent to require the processing capability on large scale graphs with billions of vertices, which is the hot topic of the research and development in the current high performance computing field.In this thesis, we make a study of BSP model, Hadoop, Pregel, HAMA and large scale graph processing applications. The thesis designs and realizes the task scheduling and synchronization controlling in order to serve the prototype system based on BSP model for processing large scale graph. The thesis considers the task scheduling approach of Map-Reduce and the characteristics of the BSP model, proposes the pattern that it ensures all tasks of the same job can start in the same time. This thesis proposes a new concept—load balancing factor, using split-piece technology, data-localization technology and balance-load technology to optimize the performance of the BSP model system. Based on Zookeeper, this thesis considers completes the synchronization controlling process between adjacent supersteps using three synchronization barriers. To make full use of the convergence property of graph processing, this thesis designs an intelligent control mechanism to control supersteps in process, which can automatically determine whether to start the next superstep or not. That a work node may execute many tasks in the same time, this thesis puts forward the design of the synchronization controlling which can reduce the load of the cluster system.Finally, the whole system was deployed to real cluster environment and run the program. The results show how data-localization and balance-load influence the performance of the closer system, points the shortcomings in order to provide the basis for further optimization of this system.