
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Offline Permutation Algorithms on the Discrete Memory Machine with Performance Evaluation on the GPU
Akihiko KASAGI Koji NAKANO Yasuaki ITO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.12
pp.26172625 Publication Date: 2013/12/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.2617
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking) Category: Keyword: memory machine models, data movement, bank conflict, shared memory, GPU, CUDA,
Full Text: PDF>>
Summary:
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 conflictfree permutation algorithm on the DMM in a GPU. We have also implemented straightforward permutation algorithms on the GPU. The experimental results for 1024 double (64bit) numbers on NVIDIA GeForce GTX680 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 conflictfree 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 conflictfree permutation is 1.48 times faster for the random permutation and 10.0 times faster for the worst permutation.

