Elimination trees and the construction of pools and stacks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Elimination trees and the construction of pools and stacks: preliminary version

Full text

Pdf (941 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures table of contents

Santa Barbara, California, United States

Pages: 54 - 63

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Nir Shavit	MIT and Tel-Aviv University
Dan Touitou	Tel-Aviv University

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 23, Citation Count: 15

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/215399.215419 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.

	1	T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
	2	A. Agarwal et al. The MIT Alewife Machine: A Large- Scale Distributed-Memory Multiprocessor. In Proceedings of Workshop on Scalable Shared Memory Multiprocessors. Kluwer Academic Publi,her#, 1991. An extended version of this paper has been submitted for publication, and appears as MIT/LCS Memo TM-454, 1991.
	3	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994 [doi>10.1145/185675.185815]
	4	James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
	5	Maurice Herlihy , Beng-Hong Lim , Nir Shavit, Low contention load balancing on large-scale multiprocessors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.219-227, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140924]
	6	R.D. Blumofe, and C.E. Leiserson. Sheduling Multithreaded Computations by Work Stealing. In Proceeding of the 35th Symposium on Foundations of Computer Science, pages 365-368, November 1994.
	7	E. A. Brewer , C. N. Dellarocas , A. Colbrook , W. E. Weihl, PROTEUS: A HIGH-PERFORMANCE PARALLEL-ARCHITECTURE SIMULATOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
	8	John M. Mellor-Crummey , Michael L. Scott, Synchronization without contention, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.269-278, April 08-11, 1991, Santa Clara, California, United States
	9	G.H. Pfister and A. Norton. 'Hot Spot' contention and combining in multistage interconnection networks. 1NEE Transactions on Computers, C-34(11):933-938, November 1985.
	10	D. Gawlick. Processing 'hot spots' in high performance systems. In Proceedings COMPCON'85, 1985.
	11	Nancy A. Lynch , Mark R. Tuttle, Hierarchical correctness proofs for distributed algorithms, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.137-151, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41852]
	12	Reinhard Lüling , Burkhard Monien, A dynamic distributed load balancing algorithm with provable good performance, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.164-172, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165252]
	13	Larry Rudolph , Miriam Slivkin-Allalouf , Eli Upfal, A simple load balancing scheme for task allocation in parallel machines, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.237-245, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113401]
	14	Krithi Ramamritham , Calton Pu, A Formal Characterization of Epsilon Serializability, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.997-1007, December 1995 [doi>10.1109/69.476504]
	15	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 [doi>10.1145/78969.78972]
	16	Nir Shavit , Asaph Zemach, Diffracting trees (preliminary version), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.167-176, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181326]
	17	Kenjiro Taura , Satoshi Matsuoka , Akinori Yonezawa, An efficient implementation scheme of concurrent object-oriented languages on stock multicomputers, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.218-228, May 19-22, 1993, San Diego, California, United States

CITED BY 15

	Costas Busch , Marios Mavronicolas, The strength of counting networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.311, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Guy E. Blelloch , Perry Cheng , Phillip B. Gibbons, Room synchronizations, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.122-133, July 2001, Crete Island, Greece
	Leonidas Hadjimitsis , Marios Mavronicolas, Contention in balancing networks resolved (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.41-50, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Giovanni Della-Libera , Nir Shavit, Reactive diffracting trees, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.24-32, June 23-25, 1997, Newport, Rhode Island, United States
	Nir Shavit , Asaph Zemach, Diffracting trees, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.385-428, Nov. 1996
	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
	Phillip B. Gibbons , John L. Bruno , Steven Phillips, Post-mortem black-box correctness tests for basic parallel data structures, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.44-53, June 27-30, 1999, Saint Malo, France
	Nir Shavit , Eli Upfal , Asaph Zemach, A steady state analysis of diffracting trees (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.33-41, June 24-26, 1996, Padua, Italy
	Nancy Lynch , Nir Shavit , Alex Shvartsman , Dan Touitou, Counting networks are practically linearizable, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.280-289, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Roger Wattenhofer , Peter Widmayer, The counting pyramid: an adaptive distributed counting scheme, Journal of Parallel and Distributed Computing, v.64 n.4, p.449-460, April 2004
	William N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Kunal Agrawal , Yuxiong He , Charles E. Leiserson, Adaptive work stealing with parallelism feedback, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Phuong Hoai Ha , Marina Papatriantafilou , Philippas Tsigas, Self-tuning reactive diffracting trees, Journal of Parallel and Distributed Computing, v.67 n.6, p.674-694, June, 2007
	William N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Communications of the ACM, v.52 n.5, May 2009