Efficient Parallel Random Rearrange

摘要

Classic shuffling algorithms have linear complexity, but they have the disadvantage of accessing memory with unpredictable patterns, which cause a large numbers of cache misses. In consequence, their execution times are not determined by computation complexity, but by the latency of the memory system. For parallel systems, this penalty gets worse, because of the overheads associated to atomic accesses to data that must be rearranged. This paper gives an overview of the best known serial and parallel shuffling algorithms, and proposes a new one that minimizes the number of memory accesses and thus, the processors' power consumption. Comparisons among these algorithms and some results are presented for graphic architectures.