Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-25835
Titel: | Fast parallel permutation algorithms |
VerfasserIn: | Hagerup, Torben Keller, Jörg |
Sprache: | Englisch |
Erscheinungsjahr: | 1994 |
Kontrollierte Schlagwörter: | Technische Informatik Paralleler Algorithmus |
Freie Schlagwörter: | fast parallel permutation algorithm |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
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 zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-3979 hdl:20.500.11880/25891 http://dx.doi.org/10.22028/D291-25835 |
Datum des Eintrags: | 23-Jun-2005 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
sfb124-94-02.pdf | 177,37 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.