Research On Key Techniques Of Parallel Processing System Based On Large Scale Sparse Graph Algorithm

Graph algorithms,including graph search and matrix factorization,play a funda-mental role in the application of big data.The existing high performance computing has the advantages of high power consumption,high cost,and can not be used in the mar-ket.When dealing with graph problems,many core processors has a poor scalability.It is of great practical significance to explore a distributed parallel processor suitable for processing graph algorithms.By analysing memory access and communication characteristics of Breadth First Search(BFS)algorithm and Cholesky algorithm,we proposed the scalability analysis mod-el and Cholesky parameterized model.We designed and implemented a address transla-tion which was based on binary search using a reconfigurable platform.We designed and implemented a distributed parallel processing system which was based on graph search.And we designed and implemented a sparse cholesky factorization on FPGA using pa-rameterized model.Through the scalability analysis model of BFS algorithm,the optimal value of com-munication buffer was derived,and the relationship between the scale of system and per-formance was obtained.The average performance of experiment in distributed processing system with 8 processors using testbench of Graph500 was 763MTEPS(million edges per second),The scale of the graph in testbench was 2~19 to 2~23.There were total 64 threads,the ratio of the performance and the bandwidth of memory was 9.54.We have the ad-vantages in ratio of the performance and the bandwidth of memory compared with the research of the state of arts.There was good consistency with the parameterized model and the implementation of Multi-Frontal-Cholesky factorization.It could be predicted that when the scale increases,the implementation can effective-ly improve performance.