Research On Sparse Matrix-Vector Multiplication And Convex Hull Algorithm Based On GPU

The GPU is gradually enhanced in function and performance,and its floating-point capability and memory bandwidth is far superior to that of the CPU.Nowadays GPUs are not limited to traditional graphics rendering,but have become a popular general-purpose computing device.Since CUDA was created by NVIDIA,CUDA-based high-performance parallel computing has become a research hotspot in various fields.This paper starts with the traditional problems and chooses typical algorithms to improve the execution efficiency on the GPU.The paper mainly chooses sparse matrix-vector multiplication(SpMV)and convex hull algorithm for planar sets.SpMV is often used in algorithms for network data mining,which plays critical roles in invulnerability and robustness analysis as well as rumor propagation control of Internet.The storage format of sparse matrix has a great impact on the performance of SpMV.In order to improve its computing performance,it is very important to optimize the storage format of sparse matrix.The convex hull algorithm is an important component of computational geometry,and is widely used in information security systems in the non-image domain.QuickHull uses a typical divide and conquer approach,but there is no general efficient way to map divide-and-conquer algorithms to the GPU architecture.In view of the above problems,this paper attempts to optimize the SpMV and convex hull algorithms on GPU based on CUDA high performance computing platform.Based on the BRC format,this paper proposes an improved data structure for storing sparse matrices in order to achieve accurate and efficient computation on the GPU.Using a two-dimensional blocking strategy and a GPU kernel based on fast segmented sum,our storage format greatly reduces the computational error of the BRC format in a parallel environment.The method is evaluated on the GPU across a variety of real-world matrix data.For SpMV and PageRank using the operation,the experimental results prove that SpMV using our proposed method achieves higher accuracy and reproducibility than the BRC format,while maintaining good computing performance.Based on a parallelized divide-and-conquer strategy for modern GPU,this paper proposes an improved parallel convex hull algorithm for fast convex hull construction for large-scale point sets.The algorithm implements the divide-and-conquer process by introducing the concept of segment,which helps directly operate the input data initially assigned,and divide it into several segments.Our GPU-based parallel QuickHull is proposed with two data-parallel operations—segmented divide and segmented compact.We conduct extensive experiments based on several widely used benchmarking datasets.The experimental results show that our solution is significantly less time-consuming and makes better use of the GPU performance,compared against state-of-the-art Qhull library.