On the communication throughput of buffered multistage interconnection networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the communication throughput of buffered multistage interconnection networks

Full text

Pdf (1.00 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: 152 - 161

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Ralf Rehrmann	Department of Mathematics and Computer Science, University of Paderborn, Germany
Burkhard Monien	Department of Mathematics and Computer Science, University of Paderborn, Germany
Reinhard Lüling
Ralf Diekmann

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): 13, 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/237502.237521 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	K. Batcher, Sorting networks and their appticattons, Proc. of the AFIPS Spring Joint Computing Conference, vol. 32, 1968, pp. 307-314
	2	William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
	3	N.G. de Bruijn, Asymptotic Methods in Analys#s, North Holland, 1958,, pp. 153 ff
	4	S. Felperin, P. Raghavan, E. Upfal, A Theory of Wormhole Routing in Parallel Computers, ACM Symposium on Foundations of Computer Science, 1992, pp. 563-572
	5	L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973
	6	Y.C. Jenq, Performance analysis of a packet switch based on a single-buffered banyan network, IEEE J. on Selected Areas of Comm., vol. SAC-3, 1983, pp. 1014-1021
	7	R.R. Koch, Increasing the Size of a Network by a Constant Factor Can lncrease Performance by More Than a Constant Factor, IEEE Syrup. on Found. of Comp. Sc. (FOCS '88), pp. 221-231
	8	D. Krizanc , S. Rajasekaran , T. Tsantilas, Optimal routing algorithms for mesh-connected processor arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	9	C. P. Kruskal , M. Snir , A. Weiss, The Distribution of Waiting Times in Clocked Multistage Interconnection Networks, IEEE Transactions on Computers, v.37 n.11, p.1337-1352, November 1988 [doi>10.1109/12.8700]
	10	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	11	F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97448]
	12	T. Leighton , F. Makedon , I. G. Tollis, A 2n-2 step algorithm for routing in an nxn array with constant size queues, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.328-335, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72970]
	13	Bruce M. Maggs , Ramesh K. Sitaraman, Simple algorithms for routing on butterfly networks with bounded queues, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.150-161, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129728]
	14	Arif Merchant, A Markov chain approximation for the analysis of banyan networks, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.60-67, May 21-24, 1991, San Diego, California, United States
	15	Youngsong Mun , Hee Yong Youn, Performance Analysis of Finite Buffered Multistage Interconnection Networks, IEEE Transactions on Computers, v.43 n.2, p.153-162, February 1994 [doi>10.1109/12.262120]
	16	Burkhard Monien , Reinhard Lüling , Falk Langhammer, A Realizable Efficient Parallel Architecture, Proceedings of the First Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use, p.93-109, November 11-13, 1992
	17	Burkhard Monien , Ralf Diekmann , Reinhard Lüling, Communication Throughput of Interconnection Networks, Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994, p.72-86, August 22-26, 1994
	18	J.H. Patel, Performance of processor-memory #nterconnections for multzprocessors, IEEE Trans. on Computing, vol C-30, 1981, pp. 771-780
	19	R.Rehrmann, B. Monlen, R. Liiling, R. Diekmann Throughput Analysis o.f Buffered Multzstage lnterconnect#on Networks- The Relaxed Blocking Model, S~nderf~rsctmngs" bereich 376, Technical Report, 1996
	20	Reza Rooholamini , Vladimir Cherkassky , Mark Garver, Finding the right ATM switch for the market, Computer, v.27 n.4, p.16-28, April 1994 [doi>10.1109/2.274995]
	21	Christian Scheideler , Berthold Vöcking, Universal continuous routing strategies, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.142-151, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237519]
	22	George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113402]
	23	T.H. Theimer, E.P. Rathgeb, M.N. Huber, Performance analys#s of buffered banyan networks, IEEE Trans. on Communication, vol. C-39, 1991, pp. 269-277
	24	L.G. Valiant, A scheme for fast parallel communication, SIAM J. Computing 11(2), 1982, pp. 350-361
	25	Hyunsoo Yoon, Performance Analysis of Multibuffered Packet-Switching Networks in Multiprocessor Systems, IEEE Transactions on Computers, v.39 n.3, p.319-327, March 1990 [doi>10.1109/12.48863]

CITED BY 4

	Suprakash Datta , Ramesh Sitaraman, The performance of simple routing algorithms that drop packets, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.159-169, June 23-25, 1997, Newport, Rhode Island, United States
	Christian Scheideler , Berthold Vöcking, Universal continuous routing strategies, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.142-151, June 24-26, 1996, Padua, Italy
	Analytically Modeling a Fault-Tolerant Messaging Protocol, IEEE Transactions on Computers, v.53 n.7, p.870-878, July 2004
	Martin Dietzfelbinger , Anna Gambin , Sławomir Lasota, On Different Models for Packet Flow in Multistage Interconnection Networks, Fundamenta Informaticae, v.46 n.4, p.287-314, December 2001