|
ABSTRACT
The memory coherence problem in designing and implementing a shared virtual memory on loosely coupled multiprocessors is studied in depth. Two classes of algorithms, centralized and distributed, for solving the problem are presented. A prototype shared virtual memory on an Apollo ring based on these algorithms has been implemented. Both theoretical and practical results show that the memory coherence problem can indeed be solved efficiently on a loosely coupled multiprocessor.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
APOLLO COMPUTER. Apollo DOMAIN Architecture. Apollo Computer, Inc., Chelmsford, Mass., 1981.
|
 |
3
|
|
 |
4
|
|
 |
5
|
|
| |
6
|
BOLT, BERANEK, AND NEWMAN. Butterfly Parallel Processor Overview. Bolt, Beranek, and Newman, Advanced Computers Inc., Cambridge, Mass., 1985.
|
| |
7
|
|
 |
8
|
|
| |
9
|
CENSIER, L. M., AND FEAUTRIER, P. A new solution to coherence problems in multicache systems. IEEE Trans. Comput. C-27, 12 (Dec. 1978), 1112-1118.
|
| |
10
|
CHERITON, D.R. The VMP multiprocessor: Initial experience, refinements and performance evaluation. In Proceedings of the 14th Annual Symposium on Computer Architecture (Pittsburgh, Pa., June 1987).
|
| |
11
|
CHERITON, D. R., AND STUMM, M. The multi-satellite star: Structuring parallel computations for a workstation cluster. J. Distributed Comput. To appear.
|
| |
12
|
Cox, A. L., AND FOWLER, R.J. The implementation of a coherent memory abstraction on a NUMA multiprocessor: Experiences with PLATIMUM. Tech. Rep. 263, Dept. of Computer Science, University of Rochester, Rochester, N.Y., Mar. 1989.
|
 |
13
|
|
| |
14
|
DEMINET, J. Experience with multiprocessor algorithms. IEEE Trans. Comput. C-31, 4 (Apr. 1982).
|
 |
15
|
|
| |
16
|
DENNING, P.J. On modeling program behavior. In Proceedings on the Spring Joint Computer Conference (Atlantic City, N.J., May 16-18, 1972). AFIPS Press, Montudle, N.J., 1972, pp. 937-944.
|
| |
17
|
DENNING, P.J. Working sets past and present. IEEE Trans. Softw. Eng. HE-6, 1 (Jan. 1980), 64-84.
|
 |
18
|
|
| |
19
|
FINKEL, R., AND MANBER, U. BIB--A distributed implementation of backtracking. In The 5th International Conference on Distributed Computing Systems (Denver, Colo., May 1985).
|
 |
20
|
|
 |
21
|
|
| |
22
|
|
| |
23
|
FRANK, S.J. Tightly coupled multiprocessor system speeds memory-access times. Electronics 57, 1 (Jan. 1984), 164-169.
|
| |
24
|
FULLER, S., OUSTERHOUT, J., RASKIN, L., RUBINFELD, P., SINDHU, P., AND SWAN, R. Multimicroprocessors: An overview and working example. In Proceedings of the IEEE 66, 2 (Feb. 1978) pp. 214-228.
|
 |
25
|
|
| |
26
|
HOARE, C. A.R. Quicksort. Comput. J. 5, i (1962), 10-15.
|
 |
27
|
|
 |
28
|
|
 |
29
|
Anita K. Jones , Robert J. Chansler, Jr. , Ivor Durham , Karsten Schwans , Steven R. Vegdahl, StarOS, a multiprocessor operating system for the support of task forces, Proceedings of the seventh ACM symposium on Operating systems principles, p.117-127, December 10-12, 1979, Pacific Grove, California, United States
[doi> 10.1145/800215.806579]
|
| |
30
|
KARLIN, A. R., MANASSE, M. S., RUDOLPH, L., AND SLEATOR, D. D. Competitive snoopy caching. In Proceedings of the 27th Symposium on Foundation of Computer Science (Toronto, 1986). pp. 244-254.
|
 |
31
|
R. H. Katz , S. J. Eggers , D. A. Wood , C. L. Perkins , R. G. Sheldon, Implementing a cache consistency protocol, Proceedings of the 12th annual international symposium on Computer architecture, p.276-283, June 17-19, 1985, Boston, Massachusetts, United States
|
 |
32
|
Paul J. Leach , Bernard L. Stumpf , James A. Hamilton , Paul H. Levine, UIDs as internal names in a distributed file system, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.34-41, August 18-20, 1982, Ottawa, Canada
[doi> 10.1145/800220.806679]
|
| |
33
|
LEACH, P. J., LEVINE, P. H., DOUROS, B. P., HAMILTON, J. A., NELSON, D. L., AND STUMPF, B.L. The architecture of an integrated local network. IEEE J. Selected Areas in Commun. SAC-I, 5 (1983).
|
| |
34
|
|
| |
35
|
LI, K. IVY: A shared virtual memory system }:or parallel computing. In Proceedings of the 1988 International Conference on Parallel Processing (Aug. 1988). Pennsylvania State University Press, 1988, pp. 94-101.
|
 |
36
|
|
| |
37
|
LI, K., AND SCHAEFER, R. A hypercube shared virtual memory. In Proceedings of the 1989 International Parallel Processing Conference (Dufage, Ill., Aug. 1989).
|
 |
38
|
|
 |
39
|
|
 |
40
|
|
| |
41
|
|
 |
42
|
|
| |
43
|
TANG, C.K. Cache system design in the tightly coupled multiprocessor system. In Proceedings of AFIPS National Computer Conference (New York, N.Y., June 7-10, 1976). AFIPS Press, Montvale, N.J. 1976, pp. 749-753.
|
 |
44
|
|
| |
45
|
|
| |
46
|
YEN, W. C., YEN, D. W. L., AND FU, K. Data coherence problem in a multicache system. IEEE Trans. Comput. C-34, 1 (jan. 1985), 56-65.
|
CITED BY 213
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Hicks , Suresh Jagannathan , Richard Kelsey , Jonathan T. Moore , Cristian Ungureanu, Transparent communication for distributed objects in Java, Proceedings of the ACM 1999 conference on Java Grande, p.160-170, June 12-14, 1999, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Henri E. Bal , Raoul Bhoedjang , Rutger Hofman , Ceriel Jacobs , Koen Langendoen , Tim Rühl , M. Frans Kaashoek, Performance evaluation of the Orca shared-object system, ACM Transactions on Computer Systems (TOCS), v.16 n.1, p.1-40, Feb. 1998
|
|
|
|
|
|
Koray Öner , Luiz A. Barroso , Sasan Iman , Jaeheon Jeong , Krishnan Ramamurthy , Michel Dubois, The design of RPM: an FPGA-based multiprocessor emulator, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.60-66, February 12-14, 1995, Monterey, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
M. J. Feeley , W. E. Morgan , E. P. Pighin , A. R. Karlin , H. M. Levy , C. A. Thekkath, Implementing global memory management in a workstation cluster, ACM SIGOPS Operating Systems Review, v.29 n.5, p.201-212, Dec. 3, 1995
|
|
|
|
|
|
Mark W. MacBeth , Keith A. McGuigan , Philip J. Hatcher, Executing Java threads in parallel in a distributed-memory environment, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, p.16, November 30-December 03, 1998, Toronto, Ontario, Canada
|
|
|
Arvind Krishnamurthy , Klaus E. Schauser , Chris J. Scheiman , Randolph Y. Wang , David E. Culler , Katherine Yelick, Evaluation of architectural support for global address-based communication in large-scale parallel machines, ACM SIGOPS Operating Systems Review, v.30 n.5, p.37-48, Dec. 1996
|
|
|
|
|
|
|
|
|
Steven K. Reinhardt , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , David A. Wood, The Wisconsin Wind Tunnel: virtual prototyping of parallel computers, ACM SIGMETRICS Performance Evaluation Review, v.21 n.1, p.48-60, June 1993
|
|
|
|
|
|
|
|
|
Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 conference on Supercomputing, p.380-389, December 1994, Washington, D.C., United States
|
|
|
J. K. Bennett , J. B. Carter , A. L. Cox , E. N. Elnozahy , D. B. Johnson , P. Keleher , W. Zwaenepoel, Distributed shared memory: experience with Munin, Proceedings of the 5th workshop on ACM SIGOPS European workshop: Models and paradigms for distributed systems structuring, September 21-23, 1992, Mont Saint-Michel, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Manhoi Choy , Hong V. Leong , Man Hon Wong, On distributed object checkpointing and recovery, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.64-73, August 20-23, 1995, Ottowa, Ontario, Canada
|
|
|
Honghui Lu , Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, Message passing versus distributed shared memory on networks of workstations, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, December 04-08, 1995, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
Leonidas Kontothanassis , Galen Hunt , Robert Stets , Nikolaos Hardavellas , Michał Cierniak , Srinivasan Parthasarathy , Wagner Meira, Jr. , Sandhya Dwarkadas , Michael Scott, VM-based shared memory on low-latency, remote-memory-access networks, ACM SIGARCH Computer Architecture News, v.25 n.2, p.157-169, May 1997
|
|
|
|
|
|
Matthias A. Blumrich , Richard D. Alpert , Yuqun Chen , Douglas W. Clark , Stefanos N. Damianakis , Cezary Dubnicki , Edward W. Felten , Liviu Iftode , Kai Li , Margaret Martonosi , Robert A. Shillner, Design choices in the SHRIMP system: an empirical study, ACM SIGARCH Computer Architecture News, v.26 n.3, p.330-341, June 1998
|
|
|
|
|
|
Divyakant Agrawal , Manhoi Choy , Hong Va Leong , Ambuj K. Singh, Mixed consistency: a model for parallel programming (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.101-110, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rohit Chandra , Kourosh Gharachorloo , Vijayaraghavan Soundararajan , Anoop Gupta, Performance evaluation of hybrid hardware and software distributed shared memory protocols, Proceedings of the 8th international conference on Supercomputing, p.274-288, July 11-15, 1994, Manchester, England
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Aman Singla , Umakishore Ramachandran , Jessica Hodgins, Temporal notions of synchronization and consistency in Beehive, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.211-220, June 23-25, 1997, Newport, Rhode Island, United States
|
|
|
|
|
|
A. L. Cox , S. Dwarkadas , P. Keleher , H. Lu , R. Rajamony , W. Zwaenepoel, Software versus hardware shared-memory implementation: a case study, ACM SIGARCH Computer Architecture News, v.22 n.2, p.106-117, April 1994
|
|
|
|
|
|
N. R. Soparkar , P. Krzyzanowski , H. V. Jagadish , A. Asthana, Run-time parallelization of sequential database programs, Proceedings of the fourth international conference on Information and knowledge management, p.74-81, November 29-December 02, 1995, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cortés E. Pérez , Alonso G. Román , Barradas H. Ruíz, Using CSP to derive a sequentially consistent DSM system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.280, May 04-06, 1999, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, ACM SIGPLAN Notices, v.29 n.11, p.297-306, Nov. 1994
|
|
|
J. K. Bennett , S. Dwarkadas , J. Greenwood , E. Speight, Willow: a scalable shared memory multiprocessor, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.336-345, November 16-20, 1992, Minneapolis, Minnesota, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lionel Brunie , Laurent Lefèvre , Olivier Reymann, Execution analysis of DSM applications: a distributed and scalable approach, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.51-60, May 22-23, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Vijaykumar Krishnaswamy , Ivan B. Ganev , Jaideep M. Dharap , Mustaque Ahamad, Distributed object implementations for interactive applications, IFIP/ACM International Conference on Distributed systems platforms, p.45-70, April 03-07, 2000, New York, New York, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cristiana Amza , Alan L. Cox , Sandhya Dwarkadas , Pete Keleher , Honghui Lu , Ramakrishnan Rajamony , Weimin Yu , Willy Zwaenepoel, TreadMarks: Shared Memory Computing on Networks of Workstations, Computer, v.29 n.2, p.18-28, February 1996
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Leonidas Kontothanassis , Robert Stets , Galen Hunt , Umit Rencuzogullari , Gautam Altekar , Sandhya Dwarkadas , Michael L. Scott, Shared memory computing on clusters with symmetric multiprocessors and system area networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.301-335, August 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Legond L. Burge, III , Mitchell L. Neilsen, A decentralized communication efficient distributed shared memory, Proceedings of the 1996 ACM symposium on Applied Computing, p.358-365, February 17-19, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sotiris Ioannidis , Umit Rencuzogullari , Robert Stets , Sandhya Dwarkadas, CRAUL: Compiler and run-time integration for adaptation under load[1]This work was supported in part by NSF grants CDA-9401142, CCR-9702466, and CCR-9705594; and an external research grant from Compaq., Scientific Programming, v.7 n.3-4, p.261-273, August 1999
|
|
|
Christof Krick , Friedhelm Meyer auf der Heide , Harald Räcke , Berthold Vöcking , Matthias Westermann, Data management in networks: experimental evaluation of a provably good strategy, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.165-174, June 27-30, 1999, Saint Malo, France
|
|
|
|
|
|
|
|
|
Miguel Castro , Nuno Neves , Pedro Trancoso , Pedro Sousa, MIKE: a distributed object-oriented programming platform on top of the Mach micro-kernel, Proceedings of the 3rd conference on USENIX MACH III Symposium, p.6-6, April 19-21, 1993, Santa Fe, New Mexico
|
|
|
Douglas P. Ghormley , David Petrou , Steven H. Rodrigues , Thomas E. Anderson, SLIC: an extensibility system for commodity operating systems, Proceedings of the Annual Technical Conference on USENIX Annual Technical Conference, 1998, p.4-4, June 15-19, 1998, New Orleans, Louisiana
|
|
|
|
|
|
Alexander Ya-Li Wong , Margo Seltzer, Operating system support for multi-user, remote, graphical interaction, Proceedings of the Annual Technical Conference on 2000 USENIX Annual Technical Conference, p.16-16, June 18-23, 2000, San Diego, California
|
|
|
R. Kordale , M. Ahamad , M. Devarakonda, Object caching in a CORBA compliant system, Proceedings of the 2nd conference on USENIX Conference on Object-Oriented Technologies (COOTS), p.6-6, June 17-21, 1996, Toronto, Ontario, Canada
|
|
|
|
|
|
Vijaykumar Krishnaswamy , Dan Walther , Sumeer Bhola , Ethendranath Bommaiah , George Riley , Brad Topol , Mustaque Ahamad, Efficient implementations of java remote method invocation (RMI), Proceedings of the 4th conference on USENIX Conference on Object-Oriented Technologies and Systems (COOTS), p.2-2, April 27-30, 1998, Santa Fe, New Mexico
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael J. Feeley , Jeffrey S. Chase , Vivek R. Narasayya , Henry M. Levy, Integrating coherency and recoverability in distributed systems, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.16-es, November 14-17, 1994, Monterey, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jean Botev , Alexander Hohfeld , Hermann Schloss , Ingo Scholtes , Peter Sturm , Markus Esch, The HyperVerse: concepts for a federated and Torrent-based '3D Web', International Journal of Advanced Media and Communication, v.2 n.4, p.331-350, December 2008
|
|
|
|
|
|
|
|
|
|
|
|
Katsumi Hosoya , Akihisa Kawanobe , Susumu Kakuta , Munish Sharma, Interactive cooperative learning system based on virtual shared space: HyCLASS, Proceedings of the 2nd international conference on Computer support for collaborative learning, p.106-113, December 10-14, 1997, Toronto, Ontario, Canada
|
REVIEWS
"Edward A. Feustel : Reviewer"
The title of this paper is slightly misleading. A better title
would be “Memory Coherence in Shared Virtual Memory Systems for a
Small Number of Loosely Coupled Multiprocessors.” The alternate
title gives a better description of wh
more...
"Roger Raymond Schell : Reviewer"
Li and Hudak define a memory as
coherent if a read operation returns
the most recently written value. They carefully analyze several
techniques for a shared virtual memory on loosely coupled
multiprocessors i
more...
|