Research On Graph Calculation Based On Xeon Phi Coprocessor

Graph is a kind of general data structure,we can abstract out a lot of problems in the real world as graph problems to analysis and compute.Consider a large number of individual nodes as vertexes,and each of the nodes may have relationships with other nodes.These nodes and the relationships between them can be seen as graph problems.Such as social networking,web links,logistics path and so on,these are all use graph data to analysis the problems in reality.Graphs are not only used widely,but also their scales are more and more lager.Now,most of the graph computing systems are distributed systems.Thus we need to pay a higher price.How to solve the graph problems effectively under the stand-alone system is an urgent and valuable problem.To solve this problem,we design a stand-alone graph compute system based on Intel Xeon Phi co-processor,which can take advantage of the advantages of Intel Xeon Phi multi-core multi-thread to solve the graph computation problems.The graph calculation is a problem that requires a high degree of parallelism and multiple iterations between vertices,and there is research on graph computation for Intel Xeon Phi coprocessors.The main work and innovation points are as follows.Firstly,we apply graph computation to Xeon Phi co-processor,we design and realized an graph computation system name PhiCom which uses the multi-core and multi-thread to solve graph problems.Secondly,we launched a graph computation model LCUVector based vector.This model has better performance in using Xeon Phi vector processing capacity,and can raise the graph computation speed.Thirdly,we research the influence of the data alignment and instruction prefetch and stream storage,through which we get the optimal result of our system.The experimental results show that the proposed system based on Intel Xeon Phi coprocessor is superior to other single graph calculation system.When the scale of the graph is relatively small,the speed is at least twice as high as that of the other stand-alone calculation system,and when the graph data is relatively large,it is possible to obtain more than twice the speed increase.