EXPLOITING STORAGE REDUNDANCY TO SPEED-UP RANDOMIZED SHARED-MEMORY SIMULATIONS

Citation
Fm. Aufderheide et al., EXPLOITING STORAGE REDUNDANCY TO SPEED-UP RANDOMIZED SHARED-MEMORY SIMULATIONS, Theoretical computer science, 162(2), 1996, pp. 245-281
Citations number
22
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
ISSN journal
03043975
Volume
162
Issue
2
Year of publication
1996
Pages
245 - 281
Database
ISI
SICI code
0304-3975(1996)162:2<245:ESRTSR>2.0.ZU;2-7
Abstract
Assume that a set U of memory locations is distributed among n memory modules, using some number a of hash functions h(1),...,h(a), randomly and independently drawn from a highperformance universal class of has h functions. Thus, each memory location has a copies. Consider the tas k of accessing b out of the a copies for each of given keys x(1),...,x (n) epsilon U, b < a. The paper presents and analyses a simple process executing the above task on distributed memory machines (DMMs) with n processors. Efficient implementations are presented, implying a simul ation of an n-processor PRAM on an n-processor optical crossbar DMM wi th delay O(log log n), a simulation as above on an arbitrary-DMM with delay O(log log n/log log log n), an implementation of a static dictio nary on an arbitrary-DMM with parallel access time O(logn + log log n /log a), if a hash functions are used. In particular, an access time o f O(log n) can be reached if (log n)(1/log)*(n) hash functions are us ed. We further prove a lower bound for executing the above process by any so-called simple access protocol, showing that our implementations are optimal.