Directional bias and non-uniformity in FPGA global routing architectures

ABSTRACT

This paper investigates the effect of the prefabricated routing track distribution on the area-efficiency of FPGAs. The first question we address is whether horizontal and vertical channels should contain the same number of tracks (capacity), or if there is a density advantage with a directional bias. Secondly, should the channels have a uniform capacity, or is there an advantage when capacities vary from channel to channel? The key result is that the most area-efficient global routing architecture is one with uniform (or very nearly uniform) channel capacities across the entire chip in both the horizontal and vertical directions. Several non-uniform and directionally-biased architectures, however, are fairly area-efficient provided that appropriate choices are made for the pin positions on the logic blocks and the logic array aspect ratio.

REFERENCES

• 1: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 2: Xilinx Inc., The Programmable Logic Data Book, 1994.
• 3: AT & T Inc., ORCA Datasheet, 1994.
• 4: Actel Inc., FPGA Data Book and Design Guide, 1994.
• 5: Altera Inc., Data Book, 1993.
• 6: B.K. Britton, et al., "Second Generation ORCA Architecture Utilizing 0.5~t Process Enhances the Speed and Usable Gate Capacity of FPGAs," IEEE Int. ASIC Conf., Sept. 1994, pp. 474-478.
• 7: D. Tavana, W. Yee, S. Young, and B. Fawcett, "Logic Block and Routing Considerations for a New SRAM-Based FPGA Architecture," CICC, 1995, pp. 24.6.1 - 24.6.4.
• 8: S. Yang, "Logic Synthesis and Optimization Benchmarks, Version 3.0, Tech. Report, Microelectronics Centre of North Carolina, 1991.
• 9: E.M. Sentovich et al, "SIS: A System for Sequential Circuit Analysis," Tech. Report No. UCB/ERL M92/41, University of California, Berkeley, 1992.
• 10: J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup- Table Based FPGA Designs," IEEE Trans. Computer- Aided Design, Jan. 1994, pp. 1-12.
• 11: S. Kirkpatrick, C. D. Gelatt, Jr., and M. E Vecchi, "Optimization by Simulated Annealing," Science, May 13, 1983, pp. 671 - 680.
• 12: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• 13: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 14: C. Y. Lee, "An Algorithm for Path Connections and its Applications," IRE Trans. Electron. Comput., Vol. EC-10, 1961, pp. 346 - 365.
• 15: V. Betz and J. Rose, "On Biased and Non-uniform Global Routing Architectures and CAD Tools for FPGAs," Technical Report, University of Toronto, 1996.

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, Performance

Keywords:
Field-Programmable Gate Arrays (FPGAs), Global Routing, Placement