Iterative statistical kernels on contemporary GPUs. (1st January 2013)

• Record Type: Journal Article
• Authors: Gunarathne, Thilina; Salpitikorala, Bimalee; Chauhan, Arun; Fox, Geoffrey
• Is Part Of: International journal of computational science and engineering. Volume 8:Number 1(2013)
• Page Start: 58
• Page End: 77
• Publication Date: 2013-01-01
• Subjects: GPUs -- OpenCL -- multi-dimensional scaling -- MDS -- PageRank -- K-means clustering -- iterative statistical applications -- cloud GPUs -- sparse matrix-vector multiplication -- computational science -- Amazon EC2 GPU instances; Computer science -- Mathematics -- Periodicals; Computer simulation -- Mathematical aspects -- Periodicals; Computational intelligence -- Periodicals; 004.015105
• Languages: English
• ISSNs: 1742-7185

Abstract

We present a study of OpenCL implementations of three important kernels that occur frequently in iterative statistical applications: multi-dimensional scaling (MDS), PageRank and K-means clustering. We evaluated their performance on NVIDIA Tesla and Fermi GPGPU cards using dedicated hardware, and in the case of Fermi, also on the Amazon EC2 cloud-computing environment. We explored the optimisation of these kernels by four main techniques: 1) caching invariant data in GPU memory across iterations; 2) selectively placing data in different memory levels; 3) rearranging data in memory; 4) dividing the work between the GPU and the CPU. We also implemented a novel algorithm for MDS and a novel data layout scheme for PageRank. Our optimisations resulted in performance improvements of up to 5× to 6×, compared to naïve OpenCL implementations and up to 100× improvement over single-core CPU. We believe that these categories of optimisations are also applicable to other similar kernels.