An analysis of dag-consistent distributed shared-memory algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An analysis of dag-consistent distributed shared-memory algorithms

Full text

Pdf (1.76 MB)

Source

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

Padua, Italy

Pages: 297 - 308

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Robert D. Blumofe	Department of Computer Sciences, The University of Texas at Austin, Austin, Texas
Matteo Frigo	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts
Christopher F. Joerg	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts
Charles E. Leiserson	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts
Keith H. Randall	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts

Sponsors

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): 30, Citation Count: 29

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/237502.237574 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	Sarita V. Adve , Mark D. Hill, Weak ordering—a new definition, Proceedings of the 17th annual international symposium on Computer Architecture, p.2-14, May 28-31, 1990, Seattle, Washington, United States
	2	Mustaque Ahamad, Phillip W. Hutto, and Ranjit John, implementing and programming causal distributed shared memory. In Proceedings of the 111h International Conference on Distributed Computing systems, pages 274-281, Arlington, Texas, May I991.
	3	Monica Beltrametti , Kenneth Bobey , John R. Zorbas, The control mechanism for the Myrias parallel computer system, ACM SIGARCH Computer Architecture News, v.16 n.4, p.21-30, Sept. 1988 [doi>10.1145/54331.54333]
	4	Brian N. Bershad, Matthew J. Zekauskas, and Wayne A. Sawdon. The Midway distributed shared memory system. In Digest of Papers from the Thirty-Eighth IEEE Computer Society International Conference (Spring COMPCON), pages 528-537, San Francisco, California, February 1993.
	5	Guy E. Blelloch, Programming parallel algorithms, Communications of the ACM, v.39 n.3, p.85-97, March 1996 [doi>10.1145/227234.227246]
	6	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215403]
	7	Robert D. Blumofe, Executing multithreaded programs efficiently, Massachusetts Institute of Technology, Cambridge, MA, 1996
	8	Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, Dag-Consistent Distributed Shared Memory, Proceedings of the 10th International Parallel Processing Symposium, p.132-141, April 15-19, 1996
	9	Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
	10	Robert D. Blumofe and Charles E. Leiserson. Scheduling multithreaded computations by work stealing. In Proceedings of the 35th Annual Sympostum on Foundations of Computer Sctence, pages 356- 368, Santa Fe, New Mexico, November 1994.
	11	John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
	12	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	13	M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
	14	Guang R. Gao and Vivek Sarkar. Location consistency: Stepping beyond the barriers of memory coherence and serializability. Technical Report 78, McGiI1 University, School of Computer Science, Advanced Compilers, Architectures, and Parallel Systems (ACAPS) Laboratory, December 1993
	15	Kourosh Gharachorloo , Daniel Lenoski , James Laudon , Phillip Gibbons , Anoop Gupta , John Hennessy, Memory consistency and event ordering in scalable shared-memory multiprocessors, Proceedings of the 17th annual international symposium on Computer Architecture, p.15-26, May 28-31, 1990, Seattle, Washington, United States
	16	James R, Goodman, Cache consistency and sequential consistency. Technical Report 61, IEEE Scalable Coherent Interface (SCI) Working Group, March 1989.
	17	Christopher F. Joerg, The cilk system for parallel multithreaded computing, Massachusetts Institute of Technology, Cambridge, MA, 1996
	18	K. L. Johnson , M. F. Kaashoek , D. A. Wallach, CRL: high-performance all-software distributed shared memory, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.213-226, December 03-06, 1995, Copper Mountain, Colorado, United States
	19	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	20	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	21	Pete Keleher, Alan L. Cox, Sandhya Dwarkadas, and Willy Zwaenepoel. TreadMarks: Distributed shared memory on standard workstations and operating systems. In USENIX Wmter 1994 Conference Proceedings, pages 115-132, San Francisco, California, January 1994.
	22	Leslie Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9).690-691, September 1979.
	23	James R. Larus , Brad Richards , Guhan Viswanathan, LCM: memory system support for parallel language implementation, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.208-218, October 05-07, 1994, San Jose, California, United States
	24	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	25	Piyush Mehrotra and John Van RosendaIe. The BLA77F# language: A parallel language for scientific programming. Parallel Computmg, 5:339-361, 1987,
	26	S. K. Reinhardt , J. R. Larus , D. A. Wood, Tempest and typhoon: user-level shared memory, Proceedings of the 21ST annual international symposium on Computer architecture, p.325-336, April 18-21, 1994, Chicago, Illinois, United States
	27	Daniel J. Scales and Monica S. Lam. The design and evaluation of a shared object system for distributed memory machines, In Proceedings of the First Symposium on Operating Systems Design and Implementation, pages 101- I 14, Monterey, California, November 1994.
	28	Volker Strassen. Gaussian elimination is not optimal. Numertsche Mathematik, 14(3):354-356, 1969,

CITED BY 29

	Rezaul Alam Chowdhury , Vijaya Ramachandran, The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Xin Li , Marc Moreno Maza, Multithreaded parallel implementation of arithmetic operations modulo a triangular set, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada
	Kang Su Gatlin , Larry Carter, Architecture-cognizant divide and conquer algorithms, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.25-es, November 14-19, 1999, Portland, Oregon, United States
	Guang R. Gao , Vivek Sarkar, Location Consistency-A New Memory Model and Cache Consistency Protocol, IEEE Transactions on Computers, v.49 n.8, p.798-813, August 2000
	Matteo Frigo, A fast Fourier transform compiler, ACM SIGPLAN Notices, v.34 n.5, p.169-180, May 1999
	Girija J. Narlikar , Guy E. Blelloch, Space-efficient implementation of nested parallelism, ACM SIGPLAN Notices, v.32 n.7, p.25-36, July 1997
	Mingdong Feng , Charles E. Leiserson, Efficient detection of determinacy races in Cilk programs, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.1-11, June 23-25, 1997, Newport, Rhode Island, United States
	Rezaul Alam Chowdhury , Vijaya Ramachandran, Cache-oblivious dynamic programming, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.591-600, January 22-26, 2006, Miami, Florida
	Girija J. Narlikar , Guy E. Blelloch, Space-efficient scheduling of nested parallelism, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.1, p.138-173, Jan. 1999
	Matteo Frigo , Victor Luchangco, Computation-centric memory models, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.240-249, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Xiaowei Shen , Arvind , Larry Rudolph, Commit-reconcile & fences (CRF): a new memory model for architects and compiler writers, ACM SIGARCH Computer Architecture News, v.27 n.2, p.150-161, May 1999
	Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999
	Nimar S. Arora , Robert D. Blumofe , C. Greg Plaxton, Thread scheduling for multiprogrammed multiprocessors, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.119-129, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Girija J. Narlikar, Scheduling threads for low space requirement and good locality, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.83-95, June 27-30, 1999, Saint Malo, France
	Umut A. Acar , Guy E. Blelloch , Robert D. Blumofe, The data locality of work stealing, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.1-12, July 09-13, 2000, Bar Harbor, Maine, United States
	Matteo Frigo , Volker Strumpen, The cache complexity of multithreaded cache oblivious algorithms, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Shimin Chen , Phillip B. Gibbons , Michael Kozuch , Vasileios Liaskovitis , Anastassia Ailamaki , Guy E. Blelloch , Babak Falsafi , Limor Fix , Nikos Hardavellas , Todd C. Mowry , Chris Wilkerson, Scheduling threads for constructive cache sharing on CMPs, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Panagiota Fatourou, Low-contention depth-first scheduling of parallel computations with write-once synchronization variables, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.189-198, July 2001, Crete Island, Greece
	Matteo Frigo , Volker Strumpen, The memory behavior of cache oblivious stencil computations, The Journal of Supercomputing, v.39 n.2, p.93-112, February 2007
	Guy E. Blelloch , Phillip B. Gibbons, Effectively sharing a cache among threads, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Marc Snir , David A. Bader, A Framework for Measuring Supercomputer Productivity, International Journal of High Performance Computing Applications, v.18 n.4, p.417-432, November 2004
	Mark W. Goudreau , Kevin Lang , Girija Narlikar , Satish B. Rao, BOS is boss: a case for bulk-synchronous object systems, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.115-125, June 27-30, 1999, Saint Malo, France
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999
	Matteo Frigo, A fast Fourier transform compiler, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.29-38, January 06-08, 2002, San Francisco, California
	Lars Arge , Michael A. Bender , Erik D. Demaine , Bryan Holland-Minkley , J. Ian Munro, Cache-oblivious priority queue and graph algorithm applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Guy E. Blelloch , Rezaul A. Chowdhury , Phillip B. Gibbons , Vijaya Ramachandran , Shimin Chen , Michael Kozuch, Provably good multicore cache performance for divide-and-conquer algorithms, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.501-510, January 20-22, 2008, San Francisco, California
	Qing Yi , Vikram Adve , Ken Kennedy, Transforming loops to recursion for multi-level memory hierarchies, ACM SIGPLAN Notices, v.35 n.5, p.169-181, May 2000

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.2 Modes of Computation
Subjects: Parallelism and concurrency

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Languages, Performance, Theory, Verification

Collaborative Colleagues:

Robert D. Blumofe: colleagues

Matteo Frigo: colleagues

Christopher F. Joerg: colleagues

Charles E. Leiserson: colleagues

Keith H. Randall: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player