Crossbar based design schemes for switch boxes and programmable interconnection networks

ABSTRACT

Crossbars have been considered one of the most standard switching modules in conventional communication networks due to its simplicity in routing algorithm and fabrication regularity. While in programmable on-chip interconnection networks such as the routing networks in field programmable gate arrays (FPGAs), switch boxes are often used for a better tradeoff between routability and area efficiency. Much work has been done on the topology design of switch boxes, e.g. universal switch boxes and hyper-universal switch boxes. However, the layout design of switch boxes tends to be difficult when the topology of switch boxes is less regular. In this paper we revisit the theoretical design aspects of the classic crossbar design schemes and further investigate a new design style, a so called meta-crossbar, which is obtained from a crossbar by adding the least number of switches and direct contacts to achieve the desired optimal routability. We show that a switch box can always be implemented by a meta-crossbar. This means that the layout design of switch boxes can be done almost like crossbars. As a result, we present a hyper-universal meta-crossbar design, and a three level meta-crossbar based interconnection network design, which is capable of routing all group communication requirements.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 2: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 3: Yao-Wen Chang , D. F. Wong , C. K. Wong, Universal switch modules for FPGA design, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.80-101, Jan. 1996 [doi>10.1145/225871.225886]
• 4: H. Fan, J. Liu, Y. Wu, and C. C. Cheung. On Optimal Hyper Universal and Rearrageable Switch Box Designs. IEEE Transactions on Computer Aided Designs, 22(12):1637--1648, Dec. 2003.
• 5: Hongbing Fan , Jiping Liu , Yu-Liang Wu , C. K. Wong, Reduction design for generic universal switch blocks, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.526-546, October 2002 [doi>10.1145/605440.605443]
• 6: Hongbing Fan , Jiping Liu , Yu-Liang Wu, General Models and a Reduction Design Technique for FPGA Switch Box Designs, IEEE Transactions on Computers, v.52 n.1, p.21-30, January 2003 [doi>10.1109/TC.2003.1159751]
• 7: Hongbing Fan , Jiping Liu , Yu-Liang Wu , Chak-Chung Cheung, On optimum switch box designs for 2-D FPGAs, Proceedings of the 38th conference on Design automation, p.203-208, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378464]
• 8: Guy Lemieux , David Lewis, Design of Interconnection Networks for Programmable Logic, Kluwer Academic Publishers, Norwell, MA, 2004
• 9: J. Rose and S. Brown. Flexibility of Interconnection Structures for Field-Programmable Gate Arrays. IEEE Journal of Solid State Circuits, 26(3):277--282, Mar. 1991.
• 10: Herman Schmit , Vikas Chandra, FPGA switch block layout and evaluation, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503051]
• 11: Michael Shyu , Guang-Ming Wu , Yu-Dong Chang , Yao-Wen Chang, Generic Universal Switch Blocks, IEEE Transactions on Computers, v.49 n.4, p.348-359, April 2000 [doi>10.1109/12.844347]
• 12: Guang-Ming Wu , Yao-Wen Chang, Quasi-Universal Switch Matrices for FPD Design, IEEE Transactions on Computers, v.48 n.10, p.1107-1122, October 1999 [doi>10.1109/12.805159]
• 13: Yuanyuan Yang, A New Conference Network for Group Communication, IEEE Transactions on Computers, v.51 n.9, p.995-1010, September 2002
• 14: Mao-Hsu Yen , Sao-Jie Chen , Sanko H. Lan, A Three-Stage One-Sided Rearrangeable Polygonal Switching Network, IEEE Transactions on Computers, v.50 n.11, p.1291-1294, November 2001 [doi>10.1109/12.966502]

INDEX TERMS

Keywords:
FPGA, crossbar, interconnection network, layout, routing, switch box, switch matrix