David A. Bader
IEEE Fellow
AAAS Fellow
College of Computing
Georgia Tech
Atlanta, GA 30332



An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs

We compare parallel algorithms for random permutation generation on symmetric multiprocessors (SMPs). Algorithms considered are the sorting-based algorithm, Anderson's shuffling algorithm, the dart-throwing algorithm, and Sanders' algorithm. We investigate the impact of synchronization method, memory access pattern, cost of generating random numbers and other parameters on the performance of the algorithms. Within the range of inputs used and processors employed, Anderson's algorithm is preferable due to its simplicity when random number generation is relatively costly, while Sanders' algorithm has superior performance due to good cache performance when a fast random number generator is available. There is no definite winner across all settings. In fact we predict our new dart-throwing algorithm performs best when synchronization among processors becomes costly and memory access is relatively fast.

We also compare the performance of our parallel implementations with the sequential implementation. It is unclear without extensive experimental studies whether fast parallel algorithms beat efficient sequential algorithms due to mismatch between model and architecture. Our implementations achieve speedups up to 6 with 12 processors on the Sun E4500.

Publication History

Versions of this paper appeared as:
  1. G. Cong, D.A. Bader, ``An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs,'' Proc. 18th ISCA International Conference on Parallel and Distributed Computing Systems (PDCS 2005), Las Vegas, NV, September 12-14, 2005.

Download this report in Adobe PDF


Last updated: July 19, 2005


Computational Biology

Parallel Computing