Accounting for memory bank contention and delay in high-bandwidth multiprocessors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Accounting for memory bank contention and delay in high-bandwidth multiprocessors

Full text

Pdf (1.26 MB)

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: 84 - 94

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Guy E. Blelloch	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
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
Marco Zagha	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA

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): 4, Downloads (12 Months): 17, Citation Count: 4

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.215425 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.

	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
	Bai87	David H. Bailey, Vector computer memory bank contention, IEEE Transactions on Computers, v.36 n.3, p.293-298, March 1987 [doi>10.1109/TC.1987.1676901]
	BBDS94	D.H. Bailey, E. Barszcz, L. Dagum, and H. D. Simon. NAS parallel benchmark results 10-94. Technical Report NAS-94-001, NASA Ames Research Center, October 1994.
	BHZ93	Guy E. Blelloch , Michael A. Heroux , Marco Zagha, Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors, Carnegie Mellon University, Pittsburgh, PA, 1993
	Cal88	D.A. Calahan. Characterization of memory conflict loading on the CRAY-2. In Internatzonal Conference on Parallel Processzng, pages 299-302, August 1988.
	Cal89	D. A. Calahan, Some results in memory conflict analysis, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.775-778, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76351]
	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
	CS86	Tony Cheung , James E. Smith, A simulation study of the CRAY X-MP memory system, IEEE Transactions on Computers, v.35 n.7, p.613-622, July 1986 [doi>10.1109/TC.1986.1676802]
	CW79	L.J. Carter and M.N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143-154, 1979.
	DGMP92	Martin Dietzfelbinger , Joseph Gil , Yossi Matias , Nicholas Pippenger, Polynomial Hash Functions Are Reliable (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.235-246, July 13-17, 1992
	DHKP93	M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Technical Report Research Report 513, Universitat Dortmund, December 1993.
	EK93	Curd Engelmann , Jörg Keller, Simulation-based Comparison of Hash Functions for Emulated Shared Memory, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.1-11, June 14-17, 1993
	GMR94a	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
	GMR94b	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 [doi>10.1145/181014.181382]
	Gre94	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]
	Hoe63	W. H0effding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.
	HS93	W.-C. Hsu , J. E. Smith, Performance of cached DRAM organizations in vector supercomputers, Proceedings of the 20th annual international symposium on Computer architecture, p.327-336, May 16-19, 1993, San Diego, California, United States
	IC93	D. T. Harper, III , Y. Costa, Analytical Estimation of Vector Access Performance in Parallel Memory Architectures, IEEE Transactions on Computers, v.42 n.5, p.616-624, May 1993 [doi>10.1109/12.223682]
	JáJ92	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	Knu73	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	KU86	A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
	MV84	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
	OL85	Wilfried Oed , O. Lange, On the effective bandwidth of interleaved memories in vector processor systems, IEEE Transactions on Computers, v.34 n.10, p.949-957, Oct. 1985
	Rag88	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]
	Ran91	Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
	Rau91	B. Ramakrishna Rau, Pseudo-randomly interleaved memory, Proceedings of the 18th annual international symposium on Computer architecture, p.74-83, May 27-30, 1991, Toronto, Ontario, Canada
	RH90	Ram Raghavan , John P. Hayes, On randomly interleaved memories, Proceedings of the 1990 conference on Supercomputing, p.49-58, October 1990, New York, New York, United States
	RM94	Margaret Reid-Miller, List ranking and list scan on the Cray C-90, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.104-113, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181049]
	RV87	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
	She93	Thomas J. Sheffler, Implementing the multiprefix operation on parallel and vector computers, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.377-386, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.166115]
	Soh93	G. S. Sohi, High-Bandwidth Interleaved Memories for Vector Processors - A Simulation Study, IEEE Transactions on Computers, v.42 n.1, p.34-44, January 1993 [doi>10.1109/12.192212]
	ST91	J. E. Smith , W. R. Taylor, Accurate modelling of interconnection networks in vector supercomputers, Proceedings of the 5th international conference on Supercomputing, p.264-273, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109091]
	TS92	K. Thearling , S. Smith, An improved supercomputer sorting benchmark, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.14-19, November 16-20, 1992, Minneapolis, Minnesota, United States
	TTT+94	S. Tanoi, Y. Tanaka, T. Tanabe, A. Kite, T. inada, R. Hamazaki, Y. Ohtsuki, and M. Uesugi. A 32-bank 256-Mb DRAM with cache and tag. IEEE Journal of Solid-State Circuits, 29(11):1330-1335, Nov. 1994.
	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
	Zag95	M. Zagha. Effiicient irregular computation on pipelined-memory multiprocessors. Ph.D. Thesis (In Preparation), 1995.
	ZB91	Marco Zagha , Guy E. Blelloch, Radix sort for vector multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.712-721, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126164]

CITED BY 4

	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
	Gianfranco Bilardi , Kieran T. Herley , Andrea Pietracaprina , Geppino Pucci , Paul Spirakis, BSP vs LogP, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.25-32, June 24-26, 1996, Padua, Italy
	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
	Dimitrios S. Nikolopoulos, Quantifying contention and balancing memory load on hardware DSM multiprocessors, Journal of Parallel and Distributed Computing, v.63 n.9, p.866-886, September 2003