A novelmulti–graphics processing unit parallel optimizationrnframework for the sparsematrix-vectormultiplication

摘要

The sparse matrix-vector multiplication (SpMV) is of great importance in scientific computations.rnGraphics processing unit (GPU)-accelerated SpMVs for large-sized problems have attractedrnconsiderable attention recently. We observe that on a specific multi-GPU platform, the SpMVrnperformance can usually be greatly improved when a matrix is partitioned into several blocksrnaccording toa predetermined rule andeach block is assigned toaGPUwithanappropriate storagernformat. This motivates us to propose a novel multi-GPU parallel SpMV optimization framework,rnwhich involves the following parts: (1) a simple rule is defined to divide any given matrix amongrnmultiple GPUs; (2) a performance model, which is independent of the problems and dependentrnon the resources of devices, is proposed to accurately predict the execution time of SpMV kernels;rnand (3) a selection algorithm is suggested to automatically select the most appropriate onernfrom the storage formats that are involved in the framework for the matrix block that is assignedrnto each GPU on the basis of the performance model. The objective of our framework does notrnconstruct a new storage format or algorithm but automatically and rapidly generates an optimallyrnparallel SpMV for any sparse matrix on a specific multi-GPU platform by integrating the existingrnstorage formats and their corresponding kernels.We take 5 popular storage formats, for example,rnto present the idea of constructing the framework. Theoretically, we validate the correctness ofrnour proposed SpMV performance model. This model is constructed only once for each type ofrnGPU. Moreover, this framework is general and easy to be extensible. For a storage format that isrnnot included in our framework, once the performance model of its corresponding SpMV kernelrnis successfully constructed, it can be incorporated into our framework. The experiments validaternthe efficiency of our proposed framework.