ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Elimination trees and the construction of pools and stacks: preliminary version
Full text PdfPdf (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): 3,   Downloads (12 Months): 21,   Citation Count: 15
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees


General Terms:
Algorithms, Performance, Theory, Verification

Collaborative Colleagues:
Nir Shavit: colleagues
Dan Touitou: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player