Article

Free access

On the communication throughput of buffered multistage interconnection networks

Authors:

Ralf Rehrmann,

Burkhard Monien,

Reinhard Lüling,

Ralf DiekmannAuthors Info & Claims

SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and Architectures

Pages 152 - 161

https://doi.org/10.1145/237502.237521

Published: 24 June 1996 Publication History

PDF eReader

References

[1]

K. Batcher, Sorting networks and their appticattons, Proc. of the AFIPS Spring Joint Computing Conference, vol. 32, 1968, pp. 307-314

Digital Library

Google Scholar

[2]

W. Dally, Performance Analysis o.f k ary n cube interconnection networks, IEEE Transactions on Computers, vol. 39, 1990, pp. 775-785

Digital Library

Google Scholar

[3]

N.G. de Bruijn, Asymptotic Methods in Analys#s, North Holland, 1958, pp. 153 ff

Google Scholar

[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

Google Scholar

[5]

G.F. Goke, G.J. Lipovski, Banyan Networks for Partition,ng Multiprocessor Systems, Proc. 1st Ann. Syrup. on Computer Architecture, 1973, pp. 21-28

Digital Library

Google Scholar

[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

Digital Library

Google Scholar

[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

Digital Library

Google Scholar

[8]

D. Krizanc, S. Rajasekaran, T. Tsantilis, Optimal routing algorithms for mesh-connected processor arrays, Proc. of AWOC '88, Springer LNCS 319, 1988, pp. 411-422

Digital Library

Google Scholar

[9]

C.P. Kruskal, M. Snir, A. Weiss, The D#stribution o.f Waiting Times in Clocked Multistage lnterconnection Networks, IEEE Trans. on Computers, vol. 32, 1988, pp. 1337-1352

Digital Library

Google Scholar

[10]

F.T. Leighton, Introduction to Parallel Algomthms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann Publishers, 1992

Digital Library

Google Scholar

[11]

F.T. Leighton, Average Case Analysis of Greedy Routing Algorithms on Arrays, ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1990, pp. 2-10

Digital Library

Google Scholar

[12]

F.T. Leighton, F. Makedon, I. Tollis, A 2N-2 step algorithms for routing in an N z N mesh, Proc. 1st ACM Symp. on Par. Alg. and Architectures (SPAA), 1989, pp. 328-335

Digital Library

Google Scholar

[13]

B.M. Maggs, R.K. Sitaraman, Simple Algorithms for Routing on Butterfly Networks with Bounded Queues, Proc. 24th ACM Symp. on Theory of Comp., 1992, pp. 150-161

Digital Library

Google Scholar

[14]

A. Merchant, A Markov chain approzzmation for the analysis of Banyan networks, Proc. ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, 1991

Digital Library

Google Scholar

[15]

Y. Mun, H. Yong, Performance Analysis o.f Finite Buffered Multistage Interconnection Networks, IEEE Trans. on Computers, vol. C-43, 1994. pp. 153-162

Digital Library

Google Scholar

[16]

B. Monien, R. Liiling, F. Langhammer, A Realizable Efficient Parallel Architecture, 1st Int. Heinz Nixdorf Syrup., Springer LNCS 678, 1992, pp. 93-109

Digital Library

Google Scholar

[17]

B. Monien, R. Diekmann, R. Liiling, Communication Throughput of lnterconnection Networks, Proc. Math. Foundat. of Comp. Sc. (MFCS '94), Springer LNCS 841, 1994, pp. 72-86

Digital Library

Google Scholar

[18]

J.H. Patel, Performance of processor-memory #nterconnections for multzprocessors, IEEE Trans. on Computing, vol C-30, 1981, pp. 771-780

Google Scholar

[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

Google Scholar

[20]

R. Rooholaminiight, Finding the Right ATM Switch for #l#e Market, IEEE J. Comp., 1994, pp. 16-28

Digital Library

Google Scholar

[21]

C.Scheideler, B.V#;cking, Universal Continuous Rout,ng Strategies, 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996,

Digital Library

Google Scholar

[22]

G.D. Stamoulis, J.N. Tsitsiklis, The E1#ciency of Greedy Routing in Hypercubes and Butterflies, ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1991, pp. 248-259

Digital Library

Google Scholar

[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

Google Scholar

[24]

L.G. Valiant, A scheme for fast parallel communication, SIAM J. Computing 11(2), 1982, pp. 350-361

Crossref

Google Scholar

[25]

H.Y. Yoon, K.Y. Lee, M.T. Liu, Performance analysis of multibuffered packet-switching networks in multiprocessor systems, IEEE Trans. on Comp., C-39, 1990, pp. 319-327

Digital Library

Google Scholar

Cited By

View all

Vasiliadis DRizos GMargariti STsiantis L(2007)Comparative study of blocking mechanisms for packet switched Omega networksProceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications10.5555/1355643.1355647(18-22)Online publication date: 16-Feb-2007
https://dl.acm.org/doi/10.5555/1355643.1355647
Vasiliadis DRizos GMargariti STsiantis L(2007)Comparative study of blocking mechanisms for packet switched Omega networksProceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications10.5555/1353572.1353576(18-22)Online publication date: 16-Feb-2007
https://dl.acm.org/doi/10.5555/1353572.1353576
Gambin ALasota S(2005)On the semantics of multistage interconnection networksSOFSEM'96: Theory and Practice of Informatics10.1007/BFb0037418(359-368)Online publication date: 26-Jun-2005
https://doi.org/10.1007/BFb0037418
Show More Cited By

Index Terms

On the communication throughput of buffered multistage interconnection networks

Recommendations

Performance Analysis of Finite Buffered Multistage Interconnection Networks

Multistage interconnection networks (MIN's) have a number of applications in the areas of computer and communication. While several analytical models have been proposed for the performance evaluation of MIN's, they are either not very accurate or too ...
Design and Analysis of Cache Coherent Multistage Interconnection Networks

A directory of state information is introduced into a multistage interconnection network (MIN) switch, and a multiple copy cache coherence protocol is developed. It is shown that the protocol is better than a single copy protocol on this MIN with ...
Accelerating communication in on-chip interconnection networks

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and Architectures

June 1996

337 pages

ISBN:0897918096

DOI:10.1145/237502

Chairman:
Guy E. Blelloch
CMU

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 June 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

8SPAA96

Sponsor:

8SPAA96: 8th Annual ACM Symposium on Parallel

June 24 - 26, 1996

Padua, Italy

Acceptance Rates

SPAA '96 Paper Acceptance Rate 39 of 106 submissions, 37%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
241
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)6

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Vasiliadis DRizos GMargariti STsiantis L(2007)Comparative study of blocking mechanisms for packet switched Omega networksProceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications10.5555/1355643.1355647(18-22)Online publication date: 16-Feb-2007
https://dl.acm.org/doi/10.5555/1355643.1355647
Vasiliadis DRizos GMargariti STsiantis L(2007)Comparative study of blocking mechanisms for packet switched Omega networksProceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications10.5555/1353572.1353576(18-22)Online publication date: 16-Feb-2007
https://dl.acm.org/doi/10.5555/1353572.1353576
Gambin ALasota S(2005)On the semantics of multistage interconnection networksSOFSEM'96: Theory and Practice of Informatics10.1007/BFb0037418(359-368)Online publication date: 26-Jun-2005
https://doi.org/10.1007/BFb0037418
Grossman J(2004)Analytically Modeling a Fault-Tolerant Messaging ProtocolIEEE Transactions on Computers10.1109/TC.2004.1953:7(870-878)Online publication date: 1-Jul-2004
https://dl.acm.org/doi/10.1109/TC.2004.19
Dietzfelbinger MGambin ALasota S(2001)On Different Models for Packet Flow in Multistage Interconnection NetworksFundamenta Informaticae10.5555/2372173.237217546:4(287-314)Online publication date: 1-Dec-2001
https://dl.acm.org/doi/10.5555/2372173.2372175
Dietzfelbinger MGambin ALasota S(2001)On Different Models for Packet Flow in Multistage Interconnection NetworksFundamenta Informaticae10.5555/1220001.122000346:4(287-314)Online publication date: 15-Aug-2001
https://dl.acm.org/doi/10.5555/1220001.1220003
Luling RCortes Gomez F(1998)Communication scheduling in a distributed memory parallel interactive continuous media server systemProceedings of the 1998 ICPP Workshop on Architectural and OS Support for Multimedia Applications Flexible Communication Systems. Wireless Networks and Mobile Computing (Cat. No.98EX206)10.1109/ICPPW.1998.721874(58-65)Online publication date: 1998
https://doi.org/10.1109/ICPPW.1998.721874
Bouras CGarofalakis JSpirakis PTriantafillou V(1998)An analytical performance model for multistage interconnection networks with finite, infinite and zero length buffersPerformance Evaluation10.1016/S0166-5316(98)00035-234:3(169-182)Online publication date: 19-Nov-1998
https://dl.acm.org/doi/10.1016/S0166-5316%2898%2900035-2
Datta SSitaraman RLeiserson CCuller D(1997)The performance of simple routing algorithms that drop packetsProceedings of the ninth annual ACM symposium on Parallel algorithms and architectures10.1145/258492.258508(159-169)Online publication date: 1-Jun-1997
https://dl.acm.org/doi/10.1145/258492.258508
Scheideler CVöcking BBlelloch G(1996)Universal continuous routing strategiesProceedings of the eighth annual ACM symposium on Parallel Algorithms and Architectures10.1145/237502.237519(142-151)Online publication date: 24-Jun-1996
https://dl.acm.org/doi/10.1145/237502.237519

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Performance Analysis of Finite Buffered Multistage Interconnection Networks

Design and Analysis of Cache Coherent Multistage Interconnection Networks

Accelerating communication in on-chip interconnection networks