Article

A practical fast parallel routing architecture for Clos networks

Authors:

Ashwin Gumaste,

Enyue LuAuthors Info & Claims

ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

Pages 21 - 30

https://doi.org/10.1145/1185347.1185351

Published: 03 December 2006 Publication History

Abstract

Clos networks are an important class of switching networks due to their modular structure and much lower cost compared with crossbars. For routing I/O permutations of Clos networks, sequential routing algorithms are too slow, and all known parallel algorithms are not practical. We present the algorithm-hardware codesign of a unified fast parallel routing architecture called distributed pipeline routing (DPR) architecture for rearrangeable nonblocking and strictly nonblocking Clos networks. The DPR architecture uses a linear interconnection structure and processing elements that performs only shift and logic AND operations. We show that a DPR architecture can route any permutation in rearrangeable nonblocking and strictly nonblocking Clos networks in O(√N) time. The same architecture can be used to carry out control of any group of connection/disconnection requests for strictly nonblocking Clos networks in O(√N) time. Several speeding-up techniques are also presented. This architecture is applicable to packet and circuit switches of practical sizes.

References

[1]

V. E. Benes. Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press, New York, 1965.

[2]

J. Bondy and U. Murty. Graph Theory with Applications. American Elsevier, MacMillan, New York, London, 1976.

Digital Library

[3]

J. Bondy and U. Murty. The Mathematical Theory of Nonblocking Switching Networks. World Scientific, River Edge, NJ, USA, 1998.

Digital Library

[4]

S. Z. C. Li and M. Yang. Scalable schedulers for high-performance switches. In Proceedings of Workshop on High Performance Switching and Routing, pages 198--202. IEEE, April 2004.

[5]

J. Carpinelli and A. Y. Oruc. Applications of matching and edge-coloring algorithms to routing in clos networks. Networks, 24:319--326, September 1994.

[6]

C. Chen and A. Frank. A study of non-blocking switching networks. Bell System Technical Journal, 32:406--424, March 1953.

[7]

C. Chen and A. Frank. On programmable parallel data routing networks via cross-bar switches for multiple element computer architectures. Lecture Notes In Computer Science, 24:338--369, 1974.

Digital Library

[8]

N. P. G. F. Lev and L. G. Valiant. A fast parallel algorithm for routing in permutation networks. IEEE Transactions on Comput., 30:93--100, February 1981.

Digital Library

[9]

J. Jaja. Introduction to Parallel Algorithms. Addison-Wesley, Reading, MA, 1992.

Digital Library

[10]

O. Kariv and H. Gabow. Algorithms for edge coloring bipartite graphs and multigraphs. SIAM J. Comput., 11(1):117--129, 1982.

[11]

T. Lee and S. Liew. Parallel routing algorithms in benes-clos networks. IEEE Trans. on Comm., 50:1841--1847, 2002.

[12]

E. Lu and S. Q. Zheng. Parallel routing algorithms for nonblocking electronic and photonic switching networks. IEEE Trans. on Parallel and Distributed Systems, 16(8):702--713, August 2005.

Digital Library

[13]

V. A. N. McKeown, A. Mekkittikul and J. Walrand. Achieving 100% throughput in an input queued switch. IEEE Trans. on Comm., 47:1260--1267, 1999.

[14]

N. Nassimi and S. Sahni. Parallel algorithms to set up the benes permutation network. IEEE Trans. on Comput., 31(2):148--154, February 1982.

Digital Library

[15]

K. O. R. Cole and S. Schirra. Edge coloring bipartite multigraphs in o(elog d) time. Combinatorica, 21(1):5--12, 2001.

Cited By

Koloko LMatsumoto TObara H(2021)Design and implementation of fast and hardware‐efficient parallel processing elements to set full and partial permutations in Beneš networksThe Journal of Engineering10.1049/tje2.120372021:6(312-320)Online publication date: 16-Apr-2021
https://doi.org/10.1049/tje2.12037
Kao YChao H(2014)Design of a Bufferless Photonic Clos Network-on-Chip ArchitectureIEEE Transactions on Computers10.1109/TC.2012.25063:3(764-776)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1109/TC.2012.250
Zhang ZYang Y(2014)NEOProceedings of the 2014 Brazilian Conference on Intelligent Systems10.1109/ICPP.2014.60(510-519)Online publication date: 18-Oct-2014
https://dl.acm.org/doi/10.1109/ICPP.2014.60
Show More Cited By

Index Terms

A practical fast parallel routing architecture for Clos networks

Recommendations

Design of a Bufferless Photonic Clos Network-on-Chip Architecture

On-chip photonic waveguides have been proposed as a feasible replacement for the long interconnects that cause speed and power bottlenecks. Along with recent advancements in nanophotonic technologies, we believe that combining on-chip waveguides with ...
A parallel self-routing rearrangeable nonblocking multi-log₂ N photonic switching network

A new rearrangeable nonblocking photonic multi-log₂ N network DM(N) is introduced. It is shown that DM(N) network possesses many good properties simultaneously. These good properties include all those of existing rearrangeable nonblocking photonic multi-...
An analytical model for wormhole routing in multicomputer interconnection networks
IPPS '93: Proceedings of the 1993 Seventh International Parallel Processing Symposium

The communication performance of the interconnection network is critical in a multicomputer system. Wormhole routing has been known to be more efficient than the traditional circuit switching and packet switching. To evaluate wormhole routing, a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

December 2006

202 pages

ISBN:1595935800

DOI:10.1145/1185347

General Chair:
Laxmi N. Bhuyan
University of California, Riverside, USA
,
Program Chairs:
Michel Dubois
University of Southern California, USA
,
Will Eatherton
Cisco, USA

Copyright © 2006 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 December 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ANCS06

Sponsor:

ANCS06: Symposium on Architecture for Networking and Communications Systems

December 3 - 5, 2006

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
352
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Koloko LMatsumoto TObara H(2021)Design and implementation of fast and hardware‐efficient parallel processing elements to set full and partial permutations in Beneš networksThe Journal of Engineering10.1049/tje2.120372021:6(312-320)Online publication date: 16-Apr-2021
https://doi.org/10.1049/tje2.12037
Kao YChao H(2014)Design of a Bufferless Photonic Clos Network-on-Chip ArchitectureIEEE Transactions on Computers10.1109/TC.2012.25063:3(764-776)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1109/TC.2012.250
Zhang ZYang Y(2014)NEOProceedings of the 2014 Brazilian Conference on Intelligent Systems10.1109/ICPP.2014.60(510-519)Online publication date: 18-Oct-2014
https://dl.acm.org/doi/10.1109/ICPP.2014.60
Xia YChao H(2013)On practical stable packet scheduling for bufferless three-stage Clos-network switches2013 IEEE 14th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2013.6602283(7-14)Online publication date: Jul-2013
https://doi.org/10.1109/HPSR.2013.6602283
Kao YChao HMarculescu RKishinevsky MGinosar RChatha K(2011)BLOCONProceedings of the Fifth ACM/IEEE International Symposium on Networks-on-Chip10.1145/1999946.1999960(81-88)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1145/1999946.1999960
Goldner Vendramini JFerreira R(2010)Parallel Routing Algorithm for Extra Level Omega Networks on Reconfigurable SystemsProceedings of the 2010 11th Symposium on Computing Systems10.1109/WSCAD-SCC.2010.19(1-8)Online publication date: 27-Oct-2010
https://dl.acm.org/doi/10.1109/WSCAD-SCC.2010.19
Ferreira RLaure MBeck AThiago Lo Rutzig MCarro L(2009)A low cost and adaptable routing network for reconfigurable systemsProceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing10.1109/IPDPS.2009.5161217(1-8)Online publication date: 23-May-2009
https://dl.acm.org/doi/10.1109/IPDPS.2009.5161217

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten