A practical constructive scheme for deterministic shared-memory access

We present an explicit memory organization scheme for ditributing M data items among N memory modules where M=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' <= N distinct data in O((N')^(1/3)log*N'+logN) worst-case time. The address computation can be carried out efficiently without resort to a complete memory map and using O(1) internal registers per processor.