Can shared-memory model serve as a bridging model for parallel computation?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Can shared-memory model serve as a bridging model for parallel computation?

Full text

Pdf (1.62 MB)

Source

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

Newport, Rhode Island, United States

Pages: 72 - 83

Year of Publication: 1997

ISBN:0-89791-890-8

Authors

Phillip B. Gibbons	Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJ
Yossi Matias	Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJ
Vijaya Ramachandran	Dept. of Computer Sciences, University of Texas at Austin, Austin, TX

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): 2, Downloads (12 Months): 16, Citation Count: 13

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/258492.258500 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	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258502]
	2	Alok Aggarwal , Ashok K. Chandra , Marc Snir, Communication complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 [doi>10.1016/0304-3975(90)90188-N]
	3	Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215427]
	4	Amotz Bar-Noy , Shlomo Kipnis, Designing broadcasting algorithms in the postal model for message-passing systems, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.13-22, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140903]
	5	Armin Baumker , Wolfgang Dittrich, Fully dynamic search trees for an extension of the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.233-242, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237562]
	6	A. Baumker, W. Dittrich, and F. Meyer auf der Heide. Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model. Technical report, University of Paderborn, 1996.
	7	Paul Beame , Johan Hastad, Optimal bounds for decision problems on the CRCW PRAM, Journal of the ACM (JACM), v.36 n.3, p.643-670, July 1989 [doi>10.1145/65950.65958]
	8	Guy E. Blelloch, Programming parallel algorithms, Communications of the ACM, v.39 n.3, p.85-97, March 1996 [doi>10.1145/227234.227246]
	9	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for memory bank contention and delay in high-bandwidth multiprocessors, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.84-94, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215425]
	10	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	11	Pilar de la Torre , Clyde P. Kruskal, Towards a single model of efficient computation in real parallel machines, Future Generation Computer Systems, v.8 n.4, p.395-408, Sept. 1992 [doi>10.1016/0167-739X(92)90071-I]
	12	Pilar de la Torre , Clyde P. Kruskal, Submachine Locality in the Bulk Synchronous Setting (Extended Abstract), Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.352-358, August 26-29, 1996
	13	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	14	Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct bulk-synchronous parallel algorithms, Journal of Parallel and Distributed Computing, v.22 n.2, p.251-267, Aug. 1994 [doi>10.1006/jpdc.1994.1085]
	15	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72953]
	16	P. B. Gibbons. What good are shared-memory models? In Proc. 1996 ICPP Workshop on Challenges .for Parallel Processing, pages 103-114, August 1996. Invited position paper.
	17	Phillip B. Gibbons , Yossi Matias, Efficient low-contention parallel algorithms, Journal of Computer and System Sciences, v.53 n.3, p.417-442, Dec. 1996 [doi>10.1006/jcss.1996.0079]
	18	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The Queue-Read Queue-Write Asynchronous PRAM Model, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.279-292, August 26-29, 1996
	19	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Can a Shared-Memory Model Serve as a Bridging Model for Parallel Computation, University of Texas at Austin, Austin, TX, 1997
	20	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
	21	John Greiner, A comparison of parallel algorithms for connected components, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.16-25, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181021]
	22	David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
	23	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	24	Joseph F. JáJá , Kwan Woo Ryu, The block distributed memory model, University of Maryland at College Park, College Park, MD, 1994
	25	B H. H. Juurlink. Ph.D. Thesis, Leiden University, 1996.
	26	Ben H. H. Juurlink , Harry A. G. Wijshoff, The E-BSP Model: Incorporating General Locality and Unbalanced Communication into the BSP Model, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.339-347, August 26-29, 1996
	27	Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165250]
	28	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
	29	Ken Kennedy, A research agenda for high performance computing software, Developing a computer science agenda for high-performance computing, ACM Press, New York, NY, 1994 [doi>10.1145/197912.197957]
	30	C. E. Leiserson and B. M. Maggs. Communicationefficient parallel algorithms for distributed random-access machines. AIgorithmica, 3(1):53-77, 1988.
	31	B. M. Maggs , L. R. Matheson , R. E. Tarjan, Models of parallel computation: a survey and synthesis, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.61, January 04-07, 1995
	32	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195199]
	33	W. F. McColl. A BSP realization of Strassen's algorithm. Technical report, Oxford University Computing Laboratory, May 1995.
	34	Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
	35	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	36	John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	37	B. Smith. Invited lecture, 7th A CM Syrup. on Parallel Algorithms and Architectures, July 1995.
	38	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	39	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	40	Uzi Vishkin, A parallel-design distributed-implementation (PDDI) general-purpose computer, Theoretical Computer Science, v.32 n.1-2, p.157-172, July 1984 [doi>10.1016/0304-3975(84)90028-8]
	41	Ben H. H. Juurlink , Harry A. G. Wijshoff, A quantitative comparison of parallel computation models, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.13-24, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.241604]

CITED BY 13

	Vijaya Ramachandran , Brian Grayson , Michael Dahlin, Emulations between QSM, BSP, and LogP: a framework for general-purpose parallel algorithm design, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.957-958, January 17-19, 1999, Baltimore, Maryland, 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
	Philip D. MacKenzie , Vijaya Ramachandran, Computational bounds for fundamental problems on general-purpose parallel models, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.152-163, June 28-July 02, 1998, Puerto Vallarta, Mexico
	David A. Bader , Guojing Cong, Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs, Journal of Parallel and Distributed Computing, v.66 n.11, p.1366-1378, November 2006
	Alexandros V. Gerbessiotis , Seung-Yeop Lee, Remote memory access: A case for portable, efficient and library independent parallel programming, Scientific Programming, v.12 n.3, p.169-183, August 2004
	Ka Wong Chong , Yijie Han , Tak Wah Lam, Concurrent threads and optimal parallel minimum spanning trees algorithm, Journal of the ACM (JACM), v.48 n.2, p.297-323, March 2001
	Micah Adler , Wolfgang Dittrich , Ben Juurlink , Mirosław Kutyłowski , Ingo Rieping, Communication-optimal parallel minimum spanning tree algorithms (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.27-36, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Rezaul Alam Chowdhury , Vijaya Ramachandran, Cache-efficient dynamic programming algorithms for multicores, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Alessio Bechini , Cosimo Antonio Prete, Performance-steered design of software architectures for embedded multicore systems, Software—Practice & Experience, v.32 n.12, p.1155-1173, October 2002
	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997
	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
	Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas, Portable and Efficient Parallel Computing Using the BSP Model, IEEE Transactions on Computers, v.48 n.7, p.670-689, July 1999

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:
B. Hardware
B.3 MEMORY STRUCTURES
B.3.2 Design Styles
Subjects: Shared memory

C. Computer Systems Organization

D. Software
D.1 PROGRAMMING TECHNIQUES

G. Mathematics of Computing
G.4 MATHEMATICAL SOFTWARE
Subjects: Algorithm design and analysis
G.m MISCELLANEOUS
Subjects: Queueing theory**

I. Computing Methodologies
I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification

Collaborative Colleagues:

Phillip B. Gibbons: colleagues

Yossi Matias: colleagues

Vijaya Ramachandran: 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