Practical constructive schemes for deterministic shared-memory access

We present three explicit schemes for distributingM variables amongN memory modules, whereM=Θ(N ^1.5),M = Θ(N ²), andM=Θ(N ³), respectively. Each variable is replicated into a constant number of copies stored in distinct modules. We show thatN processors, directly accessing the memories through a complete interconnection, can read/write any set ofN variables in worst-case timeO (N ^1/3),O(N ^1/2), andO(N ^2/3), respectively for the three schemes. The access times for the last two schemes are optimal with respect to the particular redundancy values used by such schemes. The address computation can be carried out efficiently by each processor without recourse to a complete memory map and requiring onlyO(1) internal storage.