An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/14385

Title: An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs
Author: Cong, Guojing ; Bader, David A.
Abstract: 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.
Type: Technical Report
URI: http://hdl.handle.net/1853/14385
Date: 2006-02-25
Relation: CSE Technical Reports; GT-CSE-06-06
Publisher: Georgia Institute of Technology
Subject: Parallel algorithms
Random permutation
Symmetric multiprocessors (SMPs)
Synchronization

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
GT-CSE-06-06.pdf 617.8Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record