Research Of Synchronization Mechanism And Graph Matching Method On GPU

In recent years,massive multi-source heterogeneous data has grown dramatically.The forms of data are becoming more and more complicated.Because of the ever-increasing data size,the storage and computing capabilities of traditional CPU hardware platforms are far from meeting application requirements.The emergence of GPU can solve these problems to some extent.However,for GPU low-level hardware,it is difficult to achieve global synchronization.Representation of Graph data is flexible and powerful.As a basic operation on graph,graph matching is widely used in various fields.The research of threads synchronization and accurate graph matching method on GPU many-core platform have important theoretical research significance and practical application value.Based on the GPU many-core platform,this thesis studies on non-strict synchronization mechanism between thread blocks,and graph matching methods under different evaluation criteria.The main research contents are as follows:(1)Research on the threads synchronization problem on GPU.At present,synchronization operation on different blocks on GPU have been realized with the aid of CPU,which has a lot of data transmission between CPU and GPU.This method has less efficient and can not meet the needs of some of the more strict time-demanding practical applications.To solve this problem,this thesis proposes a non-strict synchronization mechanism based on semaphores on GPU device to achieve direct synchronous operation between blocks on GPU,reduce the frequent data transmission between CPU and GPU and improve overall computing efficiency.For the single-source shortest path problem,the validity of non-strict synchronization mechanism was verified.(2)Research on graph matching method based on graph editing distance evaluation.Based on the introduction of graph editing distance and permutation matrix,two kinds of graph matching methods are studied: enumeration graph matching method and EM-based graph matching method.The latter is the improvement of the former.The solution processes and parallelizable parts of these two methods are analyzed respectively,and parallel processing is adopted.On the premise of ensuring the correct calculation result,the computational efficiency of the two methods is analyzed.(3)Research on graph matching method based on similarity matrix evaluation.Based on the classical consR method,this thesis has explored KM-consR graph matching method.This method uses the original consR to obtain the global similarity matrix of the graph data.Instead of finding the key point pair in the classic method,the KM algorithm is used to calculate the maximum matching of the two graph data.Based on GPU platform,the KM-consR method is implemented in parallel.Experiments show that the parallel method is more efficient.