Offline Permutation Algorithms on the Discrete Memory Machine with Performance Evaluation on the GPU

Akihiko KASAGI  Koji NAKANO  Yasuaki ITO  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.12   pp.2617-2625
Publication Date: 2013/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.2617
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
memory machine models,  data movement,  bank conflict,  shared memory,  GPU,  CUDA,  

Full Text: PDF(487.9KB)>>
Buy this Article

The Discrete Memory Machine (DMM) is a theoretical parallel computing model that captures the essence of the shared memory access of GPUs. Bank conflicts should be avoided for maximizing the bandwidth of the shared memory access. Offline permutation of an array is a task to copy all elements in array a into array b along a permutation given in advance. The main contribution of this paper is to implement a conflict-free permutation algorithm on the DMM in a GPU. We have also implemented straightforward permutation algorithms on the GPU. The experimental results for 1024 double (64-bit) numbers on NVIDIA GeForce GTX-680 show that the straightforward permutation algorithm takes 247.8 ns for the random permutation and 1684ns for the worst permutation that involves the maximum bank conflicts. Our conflict-free permutation algorithm runs in 167ns for any permutation including the random permutation and the worst permutation, although it performs more memory accesses. It follows that our conflict-free permutation is 1.48 times faster for the random permutation and 10.0 times faster for the worst permutation.