Please use this identifier to cite or link to this item:
doi:10.22028/D291-25835
Title: | Fast parallel permutation algorithms |
Author(s): | Hagerup, Torben Keller, Jörg |
Language: | English |
Year of Publication: | 1994 |
SWD key words: | Technische Informatik Paralleler Algorithmus |
Free key words: | fast parallel permutation algorithm |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
Abstract: | We investigate the problem of permuting n data items on an EREW PRAM with p processors using little additional storage. We present a simple algorithm with run time O((n/p)log n) and an improved algorithm with run time O(n/p+log nloglog(n/p)). Both algorithms require n additional global bits and O(1) local storage per processor. If prefix summation is supported at the instruction level, the run time of the improved algorithm is O(n/p). The algorithms can be used to rehash the address space of a PRAM emulation. , |
Link to this record: | urn:nbn:de:bsz:291-scidok-3979 hdl:20.500.11880/25891 http://dx.doi.org/10.22028/D291-25835 |
Date of registration: | 23-Jun-2005 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
sfb124-94-02.pdf | 177,37 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.