A taxonomy-based comparison of several distributed shared memory systems

ABSTRACT

Two possible modes of Input/Output (I/O)are "sequential" and "random-access", and there is an extremely strong conceptual link between I/O and communication. Sequential communication, typified in the I/O setting by magnetic tape, is typified in the communication setting by a stream, e.g., a UNIX¹ pipe. Random-access communication, typified in the I/O setting by a drum or disk device, is typified in the communication setting by shared memory. In this paper, we study and survey the extension of the random-access model to distributed computer systems.A Distributed Shared Memory (DSM) is a memory area shared by processes running on computers connected by a network. DSM provides direct system support of the shared memory programming model. When assisted by hardware, it can also provide a low-overhead interprocess communication (IPC) mechanism to software. Shared pages are migrated on demand between the hosts. Since computer network latency is typically much larger than that of a shared bus, caching in DSM is necessary for performance. We use caching and issues such as address space structure and page replacement schemes to define a taxonomy. Based on the taxonomy we examine three DSM efforts in detail, namely: IVY, Clouds and MemNet.

REFERENCES

• 1: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 2: [Arch 86] J. Archibald and J. Baer. 'An Evaluation of Cache Coherence Solutions in Shared-Bus Multiprocessor'. ACM Transactions on Computer Systems, February 1986.
• 3: [Auban 88] J. B. Auban, P. Hutto, Y. Khalidi. 'The Architecture of the Ra Kernel' Technical Report GIT-ICS-87/35, Georgia Institute of Technology, Computer Science , 1988.
• 4: J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States
• 5: A. Bensoussan , C. T. Clingen , R. C. Daley, The Multics virtual memory: concepts and design, Communications of the ACM, v.15 n.5, p.308-318, May 1972 [doi>10.1145/355602.361306]
• 6: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 7: Roberto Bisiani , Alessandro Forin, Multilanguage Parallel Programming of Heterogeneous Machines, IEEE Transactions on Computers, v.37 n.8, p.930-945, August 1988 [doi>10.1109/12.2245]
• 8: [Chase 89] Jeffrey S. Chase, Franz G. Amador, Edward D. Lazowska, Henry M. Levy, and Richard J. Littlefield, "The Amber System: Parallel Programming on a Network of Multiprocessors", Technical Report 89-04-01, University of Washington, Department of Computer Science and Engineering, September 1989.
• 9: [Cheriton 86] D. Cheriton. 'Problem-Oriented Shared Memory : A Decentralized Approach to Distributed System Design" IEEE, Sixth International Conference on Distributed Computing Systems, 1986.
• 10: Robert C. Daley , Jack B. Dennis, Virtual memory, processes, and sharing in MULTICS, Communications of the ACM, v.11 n.5, p.306-312, May 1968 [doi>10.1145/363095.363139]
• 11: [Das 88] P. Dasgupta, R. LeBlanc, W. Appelbe. "The Clouds Distributed Operating System: Functional Description, Implementation Details and Related Work", International Conference on Distributed Computing System IEEE, 1988.
• 12: [Delp 86] G. Delp, D. Farber. 'MemNet : An Experiment on High-Speed Memory Mapped Network Interface'. Technical Report, 85-11-IR University of Delaware, Computer Science Department, 1986.
• 13: Gary Scott Delp, The architecture and implementation of MEMNET: a high--speed shared-memory computer communication network, University of Delaware, Newark, DE, 1988
• 14: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 15: [Farber 88] D. J. Farber. "Some Thoughts on the Impact of High Speed Network on Processors", DSL notes, Department of Computer and Information Science, University of Pennsylvania, 1988.
• 16: Robert Joseph Fowler, Decentralized object finding using forwarding addresses (object, network, distribution), University of Washington, 1985
• 17: [Hsu 89] M. Hsu, V. Tam, 'Transaction Synchronization in Distributed Shared Memory' Technical Report TR-05-89, Harvard University, Department of Computer Science 1989.
• 18: [Kessler 89] R. E. Kessler and Miron Livny, "An Analysis of Distributed Shared Memory Algorithms", Proceedings, 9th International Conference on Distributed Computing Systems, 1989, pp. 498-505.
• 19: Kai Li, Shared virtual memory on loosely coupled multiprocessors, Yale University, New Haven, CT, 1986
• 20: [Li 89] Kai Li and R. Schaefer, "A Hypercube Shared Virtual Memory System", Proceedings, International Conference on Parallel Processing, 1989, Volume I, pp. 125- 132.
• 21: [Libes 85] Don Libes, "User-Level Shared Variables", Proceedings, Tenth USENIX Conference , Summer 1985.
• 22: [Minnich 89] Ronald G. Minnich and David J. Farber, "The Mether System: A Distributed Shared Memory for SunOS 4.0", Proceedings, Summer 1989 USENIX Conference.
• 23: [Minnich 90] Ronald G. Minnich and David J. Farber, "Reducing Host Load, Network Load, and Latency in a Distributed Shared Memory" Proceedings, 10th International Conference on Distributed Computing Systems, Paris, France, June 1990.
• 24: [Mizrachi 89] H. E. Mizrachi, J. L. Baer, E. D. Lazowska, and J. Zahorjan, "Extending the Memory Hierarchy into Multiprocessor Interconnection Networks: A Performance Analysis", Proceedings, International Conference on Parallel Processing, 1989, Volume I, pp. 41-50.
• 25: [Nel 84] D. L. Nelson and P. J. Leach "The Architecture and Applications of the Apollo Domain", IEEE Computer Graphics, April 1984, pp. 58-66.
• 26: [Peterson 86] J. Peterson, A. Silberschatz. "Operating Systems Concepts", Addison-Wesley Publishing Company, 1986.
• 27: [Poplawski 87] D. A. Poplawski and D. O. Rich, "Code Paging on Hypercubes", International Conference on Parallel Processing, August 17-21, 1987.
• 28: Michael L. Powell , Barton P. Miller, Process migration in DEMOS/MP, Proceedings of the ninth ACM symposium on Operating systems principles, p.110-119, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 29: [Ram 88] U. Ramachandran, Y. Khalidi. 'An Implementation of Distributed Shared Memory'. Technical Report GIT-ICS-88/50, December, 1988.
• 30: David P. Reed , Rajendra K. Kanodia, Synchronization with eventcounts and sequencers, Communications of the ACM, v.22 n.2, p.115-123, Feb. 1979 [doi>10.1145/359060.359076]
• 31: [Scheurich 88] C. Scheurich and M. Dubois, "Dynamic Page Migration in Multiprocessors with Distributed Global Memory" 8th International Conference on Distributed Computing Systems, June 1988, pp. 162-169.
• 32: Jonathan M. Smith, A survey of process migration mechanisms, ACM SIGOPS Operating Systems Review, v.22 n.3, p.28-40, July 1988 [doi>10.1145/47671.47673]
• 33: [Smith 90a] Jonathan M. Smith, "Anticipation in Very High Speed Networks", Distributed Systems Laboratory Technical Report, Department of Computer and Information Science, University of Pennsylvania, 1990 (submitted for publication).
• 34: [Smith 90b] Jonathan M. Smith, "Security of Distributed Virtual Memory", Distributed Systems Laboratory Technical Report, Department of Computer and Information Science, University of Pennsylvania, 1990 (submitted for publication).
• 35: [Spector 82] Alfred Z. Spector, "Performing Remote Operations Efficiently on a Local Area Network", Communications of the ACM, April 1982.
• 36: Michael Stumm , Songnian Zhou, Algorithms Implementing Distributed Shared Memory, Computer, v.23 n.5, p.54-64, May 1990 [doi>10.1109/2.53355]
• 37: [Sur 90] S. Sureshchandran, Timothy A. Gonsalves. "Performance of the MemNet Distributed Shared Memory Architectures", TR-CSE-90-02 Department of Computer Science, Indian Institute of Technology, January 1990.
• 38: [Tam 90] Ivan Ming-Chit Tam and David J. Farber "CapNet - An Alternative Approach to Ultra High Speed Networks", Proceedings, International Communication Conference, 1990.
• 39: [Tam & Hsu 90] a-On Tam, M. Hsu "Fast Recovery in Distributed Shared Virtual Memory Systems", Tenth IEEE. International Conference on Distributed Computing Systems, May 1990.
• 40: Andrew S. Tanenbaum , Robbert Van Renesse, Distributed operating systems, ACM Computing Surveys (CSUR), v.17 n.4, p.419-470, Dec. 1985 [doi>10.1145/6041.6074]
• 41: Marvin M. Theimer , Keith A. Lantz , David R. Cheriton, Preemptable remote execution facilities for the V-system, Proceedings of the tenth ACM symposium on Operating systems principles, p.2-12, December 1985, Orcas Island, Washington, United States
• 42: [Wu 89] K. L. Wu, W. K. Fuchs. "Recoverable Distributed Shared Virtual Memory: Memory Coherence and Storage Structures". The Nineteenth International Symposium On Fault-Tolerant Computing, IEEE., 1989.
• 43: M. Young , A. Tevanian , R. Rashid , D. Golub , J. Eppinger, The duality of memory and communication in the implementation of a multiprocessor operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.63-76, November 08-11, 1987, Austin, Texas, United States
• 44: [Zhou 90] S. Zhou, M. Stumm, T. McInerney, "Extending Distributed Shared Memory to Heterogenous Environments", "Proc. 10th Int'l Conf. Distributed Computing Systems, 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Documentation, Management, Performance