Tech Report CS-93-14

A Practical Constructive Scheme for Deterministic Shared-Memory Acess

A. Pietracaprina and F.P. Preparata

April 1993


We present an explicit memory organization scheme for distributing $M$ data items among $N$ memory modules where $M \in \Theta(N^{1.5-O(1/\log N)})$. Each datum is replicated into a constant number of copies assigned to distinct modules. Assuming that $N$ processors are connected to the memories through a complete graph, we provide an access protocol so that the processors can read/write any set of $N' \leq N$ distinct data in $O((N')^{1/3} \log^{*} N'+\log N)$ worst-case time. The address computation can be carried out efficiently without resort to a complete memory map and using $O(1)$ internal storage per processor.

(complete text in pdf or gzipped postscript)