Switch-matrix architecture and routing for FPDs

ABSTRACT

An FPD 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 routable through M [8]. Chang, Wong, and Wong have identified a class of universal switch blocks [8]. In this paper, we consider the design and routing problems for another popular model of switch modules called switch matrices. Unlike switch blocks, we prove that there exist no universal switch matrices. Nevertheless, we present quasi-universal switch matrices which have the maximum possible routing capacities among all switch matrices of the same size, and show that their routing capacities converge to those of universal switch blocks. Each of the quasi-universal switch matrices of size w has a total of only 14w - 20 (14w - 21) switches if w is even (odd), w > 1, compared to a fully populated one which has 3w2 - 2w switches. We prove that no switch matrix with less than 14w - 20 (14w - 21) switches can be quasi-universal. Experimental results demonstrate that the quasi-universal switch matrices improve routabilty at the chip level.

REFERENCES

• 1: Actel Corp., FPGA Data Book and Design GsJde, 1996.
• 2: Altera Corp., FLBX lOKHandbook, 1996.
• 3: Aptix Inc., PPIC AXIO24D, Preliminary Data Sheet, Aug., 1992.
• 4: AT&T Microelectronlcs, AT~T Field.ProgrammaMe Gate Arrayl Data Book, Apr. 1995.
• 5: 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
• 6: S.D. Brown, 3. Rose, and Z. G. Vraneslc, UA stochastic model to predict the rontability of field-programmable gate arrays," IEBB Trans. CompateroAided Design, vol. 12, no. 12, pp. 1827"-1838, Dec. 1993.
• 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 , 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]
• 9: A. El Gamal, ~t at., nAn architecture for electrically configurable gate arrays," IBBB J. Solid.State Circuits, vol. 24, no. 2, pp. 394-398, Apr. 1989.
• 10: 3- L. Hen,easy and D. A. Patterson, Compxfcr Arch,lactate: A Qsanfitofie~ Ap. prva~l~, 2nd Ed., Morgan Kaufmann Pub., 1996.
• 11: H.C. Hsieh, et nL, UThird-generatlon architecture boosts speed and density of field-programmable gate arrays,n in Pro~~ IBBB Csstor~ Integrated C,rcslts Cony., pp. 31.2.1-31.2.7, May 1990.
• 12: Richard M. Karp, Combinatorics, complexity, and randomness, Communications of the ACM, v.29 n.2, p.98-109, Feb. 1986 [doi>10.1145/5657.5658]
• 13: C. Y. Lee, "An algorithm for path connections and its applications," IRB Tran,. Bittern,los Camp=far., vol. EC-10, pp. 346-365, Sept. 1961.
• 14: G- G. Lemienx and S. D. Brown, "A detailed routing algorithm for allocating wire segments in fleld-programmable gate arrays," in Pro~. ACM/SIGDA P&~s,caIDelign Workshop, pp. 215-216, Lake Arrowhead, CA, 1993.
• 15: J. Rose and S. Brown, "Flexibility of {nterconnection structures for fieldprogrammable gate axrays," IBBB J. Solid State C~rcsmfJ, vol. 26, no.3, pp. 277- 282, Mar. 1991.
• 16: 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
• 17: 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
• 18: Xilinx Inc., T&e Pr~ammable Z, ogle Data Book, 1996.
• 19: 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
  B.8 Performance and Reliability

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

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