Abstract: Our work explores the practical relevance of Randomized Shared Memory (RSM), a theoretical concept that has been proven to enable an (asymptotically) optimally efficient implementation of scalable and universal shared memory in a distributed-memory parallel system. RSM (address hashing) pseudo-randomly distributes global memory addresses throughout the nodes' local memories. High memory access latencies are masked through massive parallelism. This paper introduces the basic principles and properties of RSM and analyzes its practical efficiency in terms of constant factors through simulation studies, assuming a state-of-the-art parallel architecture. Bottlenecks in the architecture are pointed out, and improvements are being made and their effects assessed quantitatively. The results show that RSM efficiency is encouragingly high, even in a non-optimized architecture. We propose architectural features to support RSM and conclude that RSM may indeed be a feasible shared-memory implementation in future massively parallel computers.

Abstract: This paper analyzes the efficiency of Randomized Shared Memory (RSM) in terms of constant factors. RSM or memory hashing, that is, pseudorandom distribution of global memory addresses throughout local memories in a distributed-memory parallel system, has been proven to enable an (asymptotically) optimally efficient implementation of scalable and universal shared memory. High memory access latencies are hidden through massive parallelism. Our work examines the practical relevance and feasibility of this potentially significant theoretical result. After an introduction of the background, principles, and desirable properties of RSM and an outline of the approach to determine RSM efficiency, the major results of our simulations are presented. The results show that RSM efficiency is encouragingly high (up to 20% efficiency of idealized shared memory), even in an architecture modelled on the basis of state-of-the-art technology. Performance-limiting factors are identified from the results and architectural features to increase efficiency are proposed, most notably extremely fast process switching and a combining network. Several novel machine designs document the increased interest in RSM and hardware support.

[4]	Arndt Bode, Michael Gerndt, R Hackenberg, Hermann Hellwagner, High-Level Programming Models and Supportive Environments (HIPS´96), In Proceedings of IPPS '96, The 10th International Parallel Processing Symposium (A N, ed.), IEEE Computer Society, N, A, pp. -, 1996. [bib]
1994
[3]	Günter Böckle, Hermann Hellwagner, Systematic Assessment of Computer Systems Architectures, In Innovationen bei Rechen- und Kommunikationssystemen, Eine Herausforderung für die Informatik (Bernd E Wolfinger, ed.), Springer Verlag, N, A, pp. 310-317, 1994. [bib]
1993
[2]	Hermann Hellwagner, Randomized Shared Memory - Concept and Efficiency of a Scalable Shared Memory Scheme, In Parallel Computer Architectures: Theory, Hardware, Software, Applications (Bode Arndt, Mario Dal Cin, eds.), Springer Verlag, London, UK, pp. 102-117, 1993. [bib] [abstract] Abstract: Our work explores the practical relevance of Randomized Shared Memory (RSM), a theoretical concept that has been proven to enable an (asymptotically) optimally efficient implementation of scalable and universal shared memory in a distributed-memory parallel system. RSM (address hashing) pseudo-randomly distributes global memory addresses throughout the nodes' local memories. High memory access latencies are masked through massive parallelism. This paper introduces the basic principles and properties of RSM and analyzes its practical efficiency in terms of constant factors through simulation studies, assuming a state-of-the-art parallel architecture. Bottlenecks in the architecture are pointed out, and improvements are being made and their effects assessed quantitatively. The results show that RSM efficiency is encouragingly high, even in a non-optimized architecture. We propose architectural features to support RSM and conclude that RSM may indeed be a feasible shared-memory implementation in future massively parallel computers.
1992
[1]	Hermann Hellwagner, On the Practical Efficiency of Randomized Shared Memory, In Parallel Processing: CONPAR 92 - VAPP V, Second Joint International Conference on Vector and Parallel Processing (Luc Bougé, Michel Cosnard, Yves Robert, Denis Trystram, eds.), Springer, Berlin-Heidelberg, pp. 429-440, 1992. [bib] [abstract] Abstract: This paper analyzes the efficiency of Randomized Shared Memory (RSM) in terms of constant factors. RSM or memory hashing, that is, pseudorandom distribution of global memory addresses throughout local memories in a distributed-memory parallel system, has been proven to enable an (asymptotically) optimally efficient implementation of scalable and universal shared memory. High memory access latencies are hidden through massive parallelism. Our work examines the practical relevance and feasibility of this potentially significant theoretical result. After an introduction of the background, principles, and desirable properties of RSM and an outline of the approach to determine RSM efficiency, the major results of our simulations are presented. The results show that RSM efficiency is encouragingly high (up to 20% efficiency of idealized shared memory), even in an architecture modelled on the basis of state-of-the-art technology. Performance-limiting factors are identified from the results and architectural features to increase efficiency are proposed, most notably extremely fast process switching and a combining network. Several novel machine designs document the increased interest in RSM and hardware support.