Name
Abstract | ||
|---|---|---|
The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computation on CUDA-enabled GPUs. The offline permutation is a task to copy numbers stored in an array a of size n to an array b of the same size along a permutation P given in advance. A conventional algorithm can complete the offline permutation by executing b[p[i]]<- a[i] for all i in parallel, where an array p stores the permutation P. We first present that the conventional algorithm runs D-w(P) + 2 n/w + 3L - 3 time units using n threads on the HMM with width w and latency L, where D-w(P) is the distribution of P. We next show that important regular permutations including transpose, shuffle, and bit-reversal permutations run 2 n/w + 2 n/kw + 2L - 2 time units on the HMM with k DMMs. We have implemented permutation algorithms for these regular permutations on GeForce GTX 680 GPU. The experimental results show that these algorithms run much faster than the conventional algorithm. We also present an offline permutation algorithm for any permutation running in 16 n/w + 16 n/kw + 16L - 16 time units on the HMM with k DMMs. Quite surprisingly, our offline permutation algorithm on the GPU achieves better performance than the conventional algorithm in random permutation, although the running time has a large constant factor. We can say that the experimental results provide a good example of GPU computation showing that a complicated but ingenious implementation with a larger constant factor in computing time can outperform a much simpler conventional algorithm. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1587/transinf.2014PAP0010 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
memory machine models, offline permutation, GPU, CUDA | Computer science,CUDA,Permutation,Parallel computing | Journal |
Volume | Issue | ISSN |
E97D | 12 | 1745-1361 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akihiko Kasagi | 1 | 28 | 4.29 |
| Koji Nakano | 2 | 1165 | 118.13 |
| Yasuaki Ito | 3 | 511 | 60.47 |