Universal switch modules for FPGA design

ABSTRACT

A switch module M with W terminals on each side is said to be universal if every set of nets satisfying the dimensional constraint (i.e., the number of nets on each side of M is at most W) is simultaneously rout able through M. In this article, we present a class of universal switch modules. Each of our switch modules has 6Wswitches and switch-module flexibility three (i.e, Fs=3). We prove that no switch module with less than 6W switches can be universal. We also compare our switch modules with those used in the Xilinx XC4000 family FPGAs and the antisymmetric switch modules (with FS=3) suggested by Rose and Brown [1991]. Although these two kinds of switch modules also have FS=3 and 6W switches, we show that they are not universal. Based on combinatorial counting techniques, we show that each of our universal switch modules can accommodate up to 25% more routing instances, compared with the XC4000-type switch module of the same size. Experimental results demonstrate that our universal switch modules improve routability at the chip level. Finally, our work also provides a theoretical insight into the important observation by Rose and Brown [1991] (based on extensive experiments) that FS=3 is often sufficient to provide high routability.

REFERENCES

• 1: Michael J. Alexander , Gabriel Robins, New performance-driven FPGA routing algorithms, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.562-567, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217589]
• 2: Narasimha B. Bhat , Dwight D. Hill, Routable Technologie Mapping for LUT FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.95-98, October 11-14, 1992
• 3: BROWN, S., ROSE, J., AND VRANESIC, Z.G. 1993. A stochastic model to predict the routability of field-programmable gate arrays. IEEE Trans. Computer-Aided Des. 12, 12, 1827-1838.
• 4: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 5: BROWN, S., ROSE, J., AND VRANESIC, Z.G. 1992b. A detailed router for field-programmable gate arrays. IEEE Trans. Comput.-Aided Des. 11,620-627.
• 6: Yao-Wen Chang , D. F. Wong , C. K. Wong, FPGA global routing based on a new congestion metric, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.372, October 02-04, 1995
• 7: Yao-Wen Chang , D. F. Wong , C. K. Wong, Design and analysis of FPGA/FPIC switch modules, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.394-401, October 02-04, 1995
• 8: Yao-Wen Chang , Shashidhar Thakur , Kai Zhu , D. F. Wong, A new global routing algorithm for FPGAs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.356-361, November 06-10, 1994, San Jose, California, United States
• 9: CHEN, C.-D., LEE, Y.-S., WU, C.-H., AND LIN, Y.-L. 1995. TRACER-fpga: a router for RAM-based FPGAs. IEEE Trans. Comput.-Aided Des. 14, 3 (March), 371-374.
• 10: FUJIYOSHI, K., KAJITANI, Y., AND NIJTSU, H. 1994. Design of optimum totally perfect connection-blocks of FPGA. In Proceedings of the IEEE International Symposium on Circuits and Systems (London, May 30-June 6), 221-224.
• 11: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: HSIEH, H. C. ET AL., 1990. Third-generation architecture boosts speed and density of field-programmable gate arrays. In Proceedings of the IEEE Custom Integrated Circuits Conference (Boston, MA, May), 31.2.1-31.2.7.
• 13: LEMIEUX, G. AND BROWN, S. 1993. A detailed routing algorithm for allocating wire segments in field-programmable gate arrays. In Proceedings of the ACM/SIGDA Physical Design Workshop (Lake Arrowhead, CA), 215-226.
• 14: Chih-chang Lin , Malgorzata Marek-Sadowska , Duane Gatlin, Universal logic gate for FPGA design, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.164-168, November 06-10, 1994, San Jose, California, United States
• 15: M. Palczewski, Plane parallel a maze router and its application to FPGAs, Proceedings of the 29th ACM/IEEE conference on Design automation, p.691-697, June 08-12, 1992, Anaheim, California, United States
• 16: ROSE, J. AND BROWN, S. 1991. Flexibility ofinterconnection structures for field-programmable gate arrays. IEEE J. Solid-State Circuits. 26, 3, 277-282.
• 17: ROSE, J., FRANCIS, R., LEWIS, D., AND CHOW, P. 1990. Architecture of programmable gate arrays: The effect of logic block functionality on area efficiency. IEEE J. Solid-State Circuits 25, 1217-1225.
• 18: Yachyang Sun , C. L. Liu, Routing in a new 2-dimensional FPGA/FPIC routing architecture, Proceedings of the 31st annual conference on Design automation, p.171-176, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196327]
• 19: Yachyang Sun , Ting-Chi Wang , C. K. Wong , C. L. Liu, Routing for symmetric FPGAs and FPICs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.486-490, November 07-11, 1993, Santa Clara, California, United States
• 20: Shashidhar Thakur , D. F. Wong, On designing ULM-based FPGA logic modules, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.3-9, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201311]
• 21: Stephen M. Trimberger, Field-Programmable Gate Array Technology, Kluwer Academic Publishers, Norwell, MA, 1994
• 22: Steven Trimberger , Mon-Ren Chene, Placement-Based Partitioning for Lookup-Table-Based FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.91-94, October 11-14, 1992
• 23: Yu-Liang Wu , Douglas Chang, On the NP-completeness of regular 2-D FPGA routing architectures and a novel solution, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.362-366, November 06-10, 1994, San Jose, California, United States
• 24: Wu, Y.-L., TSUKIYAMA, S., AND MAREK-SADOWSKA, M. 1994. Computational complexity of 2-D FPGA routing for arbitrary switch box topologies. In Proceedings of the ACM International Workshop on FPGA (Berkeley, CA, Feb. 13-15).
• 25: XILINX INC. 1994. The Programmable Logic Data Book.
• 26: Kai Zhu , D. F. Wong , Yao-Wen Chang, Switch module design with application to two-dimensional segmentation design, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.480-485, November 07-11, 1993, Santa Clara, California, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory, Verification