Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
RANDOM PERMUTATIONS ON DISTRIBUTED, EXTERNAL AND HIERARCHICAL MEMORY
Autore:
SANDERS P;
Indirizzi:
MAX PLANCK INST INFORMAT,STADTWALD D-66123 SAARBRUCKEN GERMANY
Titolo Testata:
Information processing letters
fascicolo: 6, volume: 67, anno: 1998,
pagine: 305 - 309
SICI:
0020-0190(1998)67:6<305:RPODEA>2.0.ZU;2-M
Fonte:
ISI
Lingua:
ENG
Keywords:
PARALLEL RANDOM PERMUTATION GENERATION; RANDOMIZED ALGORITHM; EXTERNAL MEMORY; HIERARCHICAL MEMORY; CACHE; INSTRUCTION LEVEL PARALLELISM; COMPUTATIONAL COMPLEXITY;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
CompuMath Citation Index
Science Citation Index Expanded
Citazioni:
11
Recensione:
Indirizzi per estratti:
Citazione:
P. Sanders, "RANDOM PERMUTATIONS ON DISTRIBUTED, EXTERNAL AND HIERARCHICAL MEMORY", Information processing letters, 67(6), 1998, pp. 305-309

Abstract

A simple randomized algorithm for generating a uniformly distributed random permutation of size n is investigated. It works in time O(n/P T-comm(n/P, P) + T-prefix (P)) on P processors with high probability,where T-comm(k, P) is the time for randomly sending or receiving k elements on each processor and T-prefix(P) is the time for computing a prefix sum. The algorithm can be directly translated into an optimal external memory algorithm if fast memory for root nB(1 + o(1)) + O(B) elements is available where B is the page size. Due to its simplicity, the same algorithm even outperforms the straightforward method on mainstream workstations if the cache is taken to be the fast memory and themain memory is treated like external memory. The algorithm is almost four times faster on a MIPS R10000 machine. (C) 1998 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 14/07/20 alle ore 11:03:58