Efficient synchronization of multiprocessors with shared memory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient synchronization of multiprocessors with shared memory

Full text

Pdf (897 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fifth annual ACM symposium on Principles of distributed computing table of contents

Calgary, Alberta, Canada

Pages: 218 - 228

Year of Publication: 1986

ISBN:0-89791-198-9

Authors

Clyde P Kruskal	Department of Computer Science, University of Maryland, College Park, Maryland
Larry Rudolph	Institute of Mathematics and Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel
Marc Snir	Institute of Mathematics and Computer Science, The Hebrew University of Jerusalem, Jerusalem, Israel

Sponsor

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 31, Citation Count: 25

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/10590.10609 What is a DOI?

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.

	ABB	G. M. Amdahl, G. A. Blaauw, and F. P. Brooks, Architecture of the IBM System/360, IBM J. Research and Development, pp. 87-101, April 1964.
	CH	Roy H. Campbell , A. Nico Habermann, The specification of process synchronization by path expressions, Operating Systems, Proceedings of an International Symposium, p.89-102, April 23-25, 1974
	DKS	Dickey, S., R. Kenner, and M. Snir, An Implementation of a Combining Network for the NYU Ultracomputer, Ultracomputer Note #93, NYU, Jan. 1988.
	DKSS	Dickey, S:, R. Kenner, M. Snir, and J. Solworth, A VLSI Combining Network for the NYU Ultracomputer, IEEE Proc. of the Intl. Conf. on Computer Design,. pp. 110-113, Oct. 1985.
	Di	Dijkstra, E. W., Hierarchical ordering of sequential processes, Acta Infformat@a, vol. 1, pp. 115.-138, 1971.
	DGSS	Draughon, E., R. Grishman, J. Schwartz, and A. Stein, Programming Considerations for Parallel Computers, Rep. IMM 362, Courant Inst. of Mathematical Sciences, New York Univ., New York, N. Y., 1967.
	GGK	Gottlieb, A., R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir, The NYU Ultras computer -- Designing an MIMD Parallel Computer, IEEE Transactions on Computers, vol. C-82, pp. 75- 89, 1984.
	GK	Allan Gottlieb , Clyde P. Kruskal, Coordinating parallel processors: a partial unification, ACM SIGARCH Computer Architecture News, v.9 n.6, p.16-24, October 1981 [doi>10.1145/859515.859517]
	GLR	Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
	GP	Cajski, D. D. and J.-K. Peir, Essential Issues in Multiprocessor Systems, IEEE Computer, pp. 9-28, June 1985.
	Ho	C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
	La1	Lamport, L., How To Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, IEEE Transactions on Computers, vol. C-28, pp. 690-691, 1979.
	La2	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	La3	Lamport, L., On Interprocess Communication, to appear in Distributed Computing.
	LaF	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	LyF	Lynch, N. and M. Fisher, On Describing the Behavior and Implementation of Distributed Systems, Theoretical Computer Science vol. 18, pp. 17-43, 1981.
	MM	George Milne , Robin Milner, Concurrent Processes and Their Syntax, Journal of the ACM (JACM), v.26 n.2, p.302-321, April 1979 [doi>10.1145/322123.322134]
	PG	Peir, J.-K. and Gajski D. D., Data Flow Execution of Fortran Loops, Proc. 1st Intl. Conf. on Supercomputing Systems, Dec. 16-20, 1985.
	PET	James L. Peterson , Abraham Silberschatz, Operating system concepts (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
	PBH	Pfister, G. H., et al., The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture, 1985 Intl. Conf. on Parallel Processing, pp. 764- 772.
	PN	Pfister G. H., and A. Norton, 'Hot Spot' Contention and Combining in Multistage Interconnection Networks, IEEE Transactions on Computers vol. C-34, pp, 933-938, 1985.
	Ru	Lawrence S. Rudolph, Software structures for ultraparallel computing, 1982
	SBK	Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977
	Se	Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
	Sm	Smith, B. J., Architectures and Applications of the HEP Multiprocessor Computer System, Real-Time Signal Processing IV, SPIE, pp. 241-248, 1981.
	SS	D. Shasha and M. Snir, Efficient and Correct Execution of Frograms That Share Memory, Ultracomputer Tech. Rep., NYU, Feb. 1986.
	ZY	Zhu and Ycw, A Synchronization Scheme and Its Applications for Large Scale Multiprocessor Systems, Proc. Conf. on Distributed Computing Systems, pp. 486-491, 1984.

CITED BY 25

	M. Herlihy , Mark R. Tuttle, Lower bounds for wait-free computation in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.347-362, August 22-24, 1990, Quebec City, Quebec, Canada
	Nir Shavit , Asaph Zemach, Combining funnels: a new twist on an old tale…, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.61-70, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada
	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991
	Nir Shavit , Asaph Zemach, Scalable concurrent priority queue algorithms, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.113-122, May 04-06, 1999, Atlanta, Georgia, United States
	David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993
	Robert Cypher, The communication requirements of mutual exclusion, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.147-156, June 24-26, 1995, Santa Barbara, California, United States
	John M. Mellor-Crummey , Michael L. Scott, Scalable reader-writer synchronization for shared-memory multiprocessors, ACM SIGPLAN Notices, v.26 n.7, p.106-113, July 1991
	Tushar Deepak Chandra , Prasad Jayanti , King Tan, A polylog time wait-free construction for closed objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.287-296, June 28-July 02, 1998, Puerto Vallarta, Mexico
	John M. Mellor-Crummey , Michael L. Scott, Synchronization without contention, ACM SIGARCH Computer Architecture News, v.19 n.2, p.269-278, Apr. 1991
	Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Journal of the ACM (JACM), v.43 n.5, p.794-839, Sept. 1996
	John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991
	David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, ACM SIGPLAN Notices, v.33 n.5, p.258-268, May 1998
	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks and multi-processor coordination, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.348-358, May 05-08, 1991, New Orleans, Louisiana, United States
	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994
	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990
	Costas Busch , Marios Mavronicolas, A combinatorial treatment of balancing networks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.206-215, August 14-17, 1994, Los Angeles, California, United States
	M. Takesue, A Family of Parallel Prefix Algorithms Embedded in Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.10, p.1179-1184, October 1993
	Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada
	Panagiota Fatourou , Maurice Herlihy, Read-modify-write networks, Distributed Computing, v.17 n.1, p.33-46, February 2004
	David F. Bacon , Ravi Konuru , Chet Murthy , Mauricio J. Serrano, Thin locks: featherweight Synchronization for Java, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Maurice Herlihy , Nir Shavit , Orli Waarts, Linearizable counting networks, Distributed Computing, v.9 n.4, p.193-203, February 1996
	Theordore Johnson , Krishna Harathi, A Prioritized Multiprocessor Spin Lock, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.926-933, September 1997
	G. Lee, A Performance Bound of Multistage Combining Networks, IEEE Transactions on Computers, v.38 n.10, p.1387-1395, October 1989
	Costas Busch , Marios Mavronicolas , Paul Spirakis, The cost of concurrent, low-contention Read&Modify&Write, Theoretical Computer Science, v.333 n.3, p.373-400, 3 March 2005