The Optimization Technology Of Parallel Graph Algorithms For Many-core Architecture

In the new era,computer integrated into every aspect of people's lives,and with it a tremendous amount of data to be processed.There is a need for massive data mining and processing in cloud computing,networking,physics,biology,ecology,environment and other areas,which indicates that we have entered the "big data" era.In �big data� era,the amount of data processing is large and the type of data is of very large variety,including text,audio,video,pictures,location information.Graph provides a natural expression of unstructured data and is a very effective big data forms.Graph traversal is a basic graphics algorithm in the field of social networking,business analysis,high-performance computing,which are widely used graphics algorithms.Graph traversal have been studied and optimized very well on a single node.Currently heterogeneous computing is becoming increasingly popular,and CPU + MIC is a typical heterogeneous architecture.Intel's MIC(Many Integrated Core)is a high-design many-core parallel computing coprocessor and it has up to 57 cores.In terms of graph traversal,MIC has not been well utilized.Also,because the graph has: structural properties of small-world,scale-free,community structure,which is part of the vertexes' degree is small and the other part of the vertexes' degree is very large.Therefore,when use MIC to traverse the graph,the degree of vertexes divided between the cores of MIC will differ so much,so there may be very serious load imbalance,which will adversely affect the performance of the system.This paper proposes an algorithm design and optimization techniques to improve load imbalances on the MIC.About this optimized design,its core idea is distinguishing the high degree vertexes and the low degree vertexes in the processing.In order to realize this idea,we propose an improved data structure to achieve the purposes of distinguish high degree vertexes and low degree vertexes.Through these optimization measures,compared to non-optimized algorithm we get a very high performance.We also believe that this new algorithm will be widely used,especially with multiple MIC massively parallel systems.This article includes research on the following aspects:(1)MIC is based on the ultra-multi-core processor architecture,containing nearly 60 cores,with each core can run four hardware threads simultaneously.And the vertexes of Graph 500 generated have different degrees,some differences of the degree are still very large and theoretically there will be some load imbalance between the various cores in MIC.Firstly,use the direction optimization strategies to achieve the parallel BFS in MIC then statistics the data finding that there is a serious imbalance between the cores of MIC.(2)This paper studies how to load imbalance between the cores in MIC when mitigate parallel BFS.The key to the optimization of MIC is to distinguish hub vertexes from light vertexes due to the difference of the degree of the vertexes which are produced by Graph 500.Select the high degree vertexes as the hub vertexes set and the others as the light vertexes set.Then evenly distribute the hub vertexes between cores in MIC before parallel BFS.During BFS,we use direction optimization strategy.That is to say that we both use direction optimization and the level synchronization algorithm which distinguish hub vertexes and light vertexes to optimize parallel BFS.(3)At the same time we put forward a design to extend this single node optimization algorithm to massively parallel systems.This design adopts the mainstream graph partitioning method,divided manner between nodes unchanged,and for the MIC in each node we use the above to optimize load balancing.In massively parallel systems,how to efficiently complete the communication is the key.After a review of relevant literature,we use the best communication optimization of existing technology to enable massively parallel system performance is maximized.