The QRQW PRAM

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The QRQW PRAM: accounting for contention in parallel algorithms

Full text

Pdf (1.28 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms table of contents

Arlington, Virginia, United States

Pages: 638 - 648

Year of Publication: 1994

ISBN:0-89871-329-3

Authors

Phillip B. Gibbons	AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ
Yossi Matias	AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ
Vijaya Ramachandran	Dept. of Computer Sciences, University of Texas, Austin, TX

Sponsors

SIAM : Society for Industrial and Applied Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

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

Warning: The download time has expired please click on the item to try again.

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.

	ACC+90	Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
	AKP91	F. Abolhassan, J. Keller, and W. J. Paul. On the cost-effectiveness of PRAMs. In Proc. 3rd IEEE Sltmp. on Parallel and Distributed Processing, pages 2- 9, December 1991.
	Bel92	Gordon Bell, Ultracomputers: a teraflop before its time, Communications of the ACM, v.35 n.8, p.26-47, Aug. 1992 [doi>10.1145/135226.135227]
	BKK93	P. Beame, M. Kik, and M. Kutylowski. Information broadcasting by exclusive-write PRAMs. Parallel Processing Letters, 1993. To appear.
	CDR86	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	CKP+93	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
	Col88	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	CZ89	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72954]
	DHW93	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.174-183, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167145]
	DK92	Susan R. Dickey , Richard Kenner, Hardware combining and scalability, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.296-305, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141893]
	DKR90	M. Dietzfelbinger , M. Kutylowski , R. Reischuk, Exact time bounds for computing boolean functions on PRAMs without simultaneous writes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.125-135, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97678]
	DM90	M. Dietzfelbinger , F. Meyer auf der Heide, How to distribute a dictionary in a complete network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.117-127, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100229]
	FBR93	S. Frank, H. Burkhardt III, and J. Rothnie. The KSRI: Bridging the gap between shared memory and MPPs. In Proc. Compcon '93, pages 285-294, February 1993.
	FKL+92	Faith E. Fich , Miroslaw Kowaluk , Krzysztof Lorys , Miroslaw Kutylowski , Prabhakar Ragde, Retrieval of scattered information by EREW, CREW and CRCW PRAMs, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.30-41, July 08-10, 1992
	GGK+83	A. Gottlieb, R. Grishman, C. P. Kruskal, K. P. McAuliffe, L. Rudolph, and M. Snir. The NYU Ultracomputer - designing an MIMD shared memory parallel computer. 1EEE Trans. on Computers, C- 32(2):175-189, 1983.
	Gib89	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]
	GMR93	P. B. Gibbons, Y. Matins, and V. Ramachandran. QRQW: Accounting for concurrency in PRAMs and Asynchronous PRAMs. Technical report, AT&T Bell Laboratories, Murray Hill, NJ, March 1993. Revised version.
	GMV91	Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
	Gre82	Albert G. Greenberg, On the time complexity of broadcast communication schemes (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.354-364, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802211]
	Hoe63	W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.
	JáJ92	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	KR90	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
	KRS90	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
	LAB93	Pangfeng Liu , William Aiello , Sandeep Bhatt, An atomic model for message-passing, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.154-163, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165251]
	Lei92a	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129721]
	Lei92b	Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong , Shaw-Wen Yang , Robert Zak, The network architecture of the Connection Machine CM-5 (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.272-285, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141883]
	LLG+92	Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
	Mas91	MasPar Computer Corporation, 749 North Mary Avenue, Sunnyvale, CA 94086. MasPar System Overview, document 9300-0100, revision A3, March 1991.
	Mat92	Y. Matins. Highly Parallel Randomized Algorithmics. PhD thesis, Tel Aviv University, Israel, December 1992.
	MPS92	Charles Martel , Arvin Park , Ramesh Subramonian, Work-optimal asynchronous algorithms for shared memory parallel computers, SIAM Journal on Computing, v.21 n.6, p.1070-1099, Dec. 1992 [doi>10.1137/0221063]
	MV91	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
	MV92	Y. Matias and U. Vishkin. A note on simulations and integer sorting. Manuscript, 1992.
	Nis90	N. Nishimura, Asynchronous shared memory parallel computation, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.76-84, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97672]
	Pre92	L. Prechelt. Measurements of MasPar MP-1216A communication operations. Technical report, Institut ffir Programmstrukturen und Datenorganisation, Universit~t Karlsruhe, Karlsruhe, Germany, November 1992.
	Ran89	Abhiram Gorakhanath Ranade, Fluent parallel computation, 1989
	Rei93	John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	RR89	S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
	Val90a	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]
	Val90b	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	Val92	L. G. Valiant. A combining mechanism for parallel computers. Technical Report TR-24-92, Harvard University, Cambridge, Massachusetts, November 1992.
	Yao77	A. C.-C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. of the 18th IEEE Annual Syrup. on Foundation of Computer Science, pages 222-227, 1977.

CITED BY 15

	Matthew I. Frank , Anant Agarwal , Mary K. Vernon, LoPC: modeling contention in parallel algorithms, ACM SIGPLAN Notices, v.32 n.7, p.276-287, July 1997
	Artur Czumaj , Przemka Kanarek , Mirosław Kutyłowski , Krzyztof Loryś, Delayed path coupling and generating random permutations via distributed stochastic processes, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 17-19, 1999, Baltimore, Maryland, United States
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Efficient low-contention parallel algorithms, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.236-247, June 27-29, 1994, Cape May, New Jersey, United States
	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
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Asynchrony versus bulk-synchrony in QRQW PRAM models, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.176, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Nir Shavit , Eli Upfal , Asaph Zemach, A wait-free sorting algorithm, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.121-128, August 21-24, 1997, Santa Barbara, California, United States
	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
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Can shared-memory model serve as a bridging model for parallel computation?, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.72-83, June 23-25, 1997, Newport, Rhode Island, United States
	Micah Adler, Asynchronous shared memory search structures, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.42-51, June 24-26, 1996, Padua, Italy
	Uzi Vishkin, From algorithm parallelism to instruction-level parallelism: an encode-decode chain using prefix-sum, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.260-271, June 23-25, 1997, Newport, Rhode Island, United States
	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
	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
	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
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Distributed Computing, v.8 n.1, p.1-17, August 1994
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993