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.

Abstract: Proceedings of the 7th Joint Conference of the Austrian Computer Society (OCG) and the John von Neumann Society for Computing Sciences (NJSZT), Klagenfurt, 1992.

1992
[3]	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.
[2]	Laszlo Böszörmenyi, Informatik und Wissenschaftsgeschichte, In Informatik in der Schule - Informatik für die Schule, Böhlau, vol. 10, Vienna, Austria, pp. not available, 1992. [bib] [abstract] Abstract: Informatik in der Schule - Informatik für die Schule.
[1]	Laszlo Böszörmenyi, A Comparison of Modula-3 and Oberon-2, In Proceedings of the 7th Joint Conference of the Austrian Computer Society (OCG) and the John von Neumann Society for Computing Sciences (NJSZT), Klagenfurt, 1992 (Roland Mittermeir, ed.), Springer, Berlin, Heidelberg, New York, pp. 126-137, 1992. [bib] [abstract] Abstract: Proceedings of the 7th Joint Conference of the Austrian Computer Society (OCG) and the John von Neumann Society for Computing Sciences (NJSZT), Klagenfurt, 1992.