Reduction design for generic universal switch blocks

ABSTRACT

A k-side switch block with W terminals per side is said to be a universal switch block ((k, W)-USB) if every set of the nets satisfying the routing constraint (i.e., the number of nets on each side is at most W) is simultaneously routable through the switch block. The (4, W)-USB was originated by designing better switch modules for 2-D FPGAs, such as Xilinx XC4000-type FPGAs, whereas the generic USBs can be applied in multidimensional or some nonconventional 2-D FPGA architectures. The problem we study in this article is to design (k, W)-USBs with the minimum number of switches for any given pair of (k, W). We provide graph models for routing requirements and switch blocks and develop a series of decomposition theorems for routing requirements with the help of a new graph model. The powerful decomposition theory leads to the automatic generation of routing requirements and a detailed routing algorithm, as well as the reduction design method of building large USBs by smaller ones. As a result, we derive a class of well-structured and highly scalable optimum (k, W)-USBs for k ≤ 6, or even Ws, and near-optimum (k, W)-USBs for k ≥ 7 and odd Ws. We also give routing experiments to justify the routing improvement upon the entire chip using the USBs. The results demonstrate the usefulness of USBs.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 4: Brown, S., Francise, R. J., Rose, J., and Vranesic, Z. G. 1992. Field-Programmable Gate Arrays. Kluwer-Academic, Boston.
• 5: Chang, Y. D., Wu, G. M., and Chang, Y. W. 1999. 3-dimensional switch box. In Proceedings of FPGA'99.
• 6: 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]
• 7: Hongbing Fan , Jiping Liu , Yu Liang Wu, General models for optimum arbitrary-dimension FPGA switch box designs, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: Fan, H., Liu, J., and Wu, Y. L. 2000. On decomposition of regular hypergraphs. In preparation.
• 9: 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]
• 10: Hongbing Fan , Yu-Liang Wu , Yao-Wen Chang, Comment on Generic Universal Switch Blocks, IEEE Transactions on Computers, v.51 n.1, p.93-96, January 2002 [doi>10.1109/12.980020]
• 11: Lovasz, L. and Plummer, M. D. 1986. Matching Theory. Elsevier Science, New York.
• 12: Milner, E. C. 1985. Basic wqo- and bqo-theory. Graphs and Order (Banff, 1984), NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci. 147, Reidel, Dordrecht, 487--502.
• 13: Jiaofeng Pan , Yu-Liang Wu , C. K. Wong , Guiying Yan, On the optimal four-way switch box routing structures of FPGA greedy routing architectures, Integration, the VLSI Journal, v.25 n.2, p.137-159, Nov. 1998 [doi>10.1016/S0167-9260(98)00011-X]
• 14: Rose, J. and Brown, S. 1991. Flexibility of interconnection structures for field-programmable gate arrays. IEEE J. Solid-State Circ. 26, 3, 277--282.
• 15: 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]
• 16: Wu, Y. L. and Marek-Sadowska, M. 1997. Routing for array type FPGAs. IEEE Trans. Comput. Aided Des. of Integrated Circ. Syst. 16, 5 (May), 506--518.
• 17: Wu, Y. L., Tsukiyama, S., and Marek-Sadowska, M. 1996. Graph based analysis of 2-D FPGA routing. IEEE Trans. Comput. Aided Des. 15, 1, 33--44.
• 18: Yang, S. 1991. Logic synthesis and optimization benchmarks, Version 3.0. Tech. Rep., Microelectronics Centre of North Carolina.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Theory

Keywords:
FPGA architecture design, decomposition, routing, routing requirement, switch module, universal switch block