Research For Key Techniques Of Sparse Graph Algorithms Optimization For SIMD Architectures

Recent years,data mining has been developed into an important field in academia and industry research,in which data mining based on the sparse graph structure,represented by social networks and literature references,is an important branch.With the further deepening of the big data era,the scale of data is growing rapidly,and the need for the execution efficiency of graph data mining algorithms is much more urgent.As the improvement of general processor performance encounters bottleneck,the coprocessor with much wider SIMD parallel efficiency and better performance power ratio has become a research hotspot.Due to the large scale and the strong sparseness of data,the distribution of the vertex degree following the power law rule,it is challenging to conduct graph applications efficiently based on the heterogeneous architecture of the processor +coprocessor.Pre-processing by dividing data with the two-level hierarchical tiling(Tiling and Blocking)mechanism in advance,to improve data access locality and prevent data write conflicts,is an important step to efficiently implement the parallelism of graph applications in SIMD computing mode.In this study,the optimization technologies of sparse graph algorithms for SIMD architecture are studied deeply,and the hierarchical tiling strategy is optimized to improve the efficiency and resource utilization,specific contributions of which include:1.The optimal grouping strategy of graph data based on bucket structure is designed and implemented.In this strategy,the existing method to construct the data conflict-free group is changed to implementation by selecting one element from each bucket structure directly,by which the efficiency of SIMD execution graph algorithm is improved,and the optimality of bucket grouping strategy is proved in detail.Aiming at the problem of leading to a large time overhead when selecting a bucket with the largest number of non-zero elements,the time complexity of data packets is reduced to O(n*log(b))by introducing the Max-heap mechanism.2.In order to solve the problem that frequently cache miss is occurred when the large-scale sparse data is used for the implementation of graph applications,an auto-tuning tiling method for sparse graph data is designed based on a decision tree classification model for SIMD architecture.This method can well combine the characters of graph applications and data,it can recommend an(approximately)optimized tile size,the performance of graph applications based on which is around 90% of what is conducted by the optimal tile size.Simultaneously,it greatly improves the resource utilization and efficiency of computation.3.Combined with two optimization strategies proposed above,a sparse graph application system prototype is conducted based on Central Process Unit + Many Integrated Cores heterogeneous architecture in this study.It simplifies the deployment of graph algorithms on heterogeneous architectures by the modular implementation of the data preprocessing and graph execution stages.Additionally,the efficiency of the above two strategies has been verified through experiments.According to the results of the experiments,after preprocessing the data based on the auto-tuning data tiling size,the efficiency of graph algorithms has been improved with up to 1.29 × when compared to the state-of the art method.