The case for registered routing switches in field programmable gate arrays

ABSTRACT

FPGAs are characterized by a programmable interconnect that contains highly resistive and capacitive elements. While the configurable structure of the interconnect allows for the implementation of arbitrary circuits, it has also become a significant bottleneck for high-speed circuits. Even if there are only a few signal paths that run along long stretches of interconnect, it is these paths that may determine the maximum operating frequency of the circuit.In this paper we investigate architectural features that could allow us to automatically pipeline the delay associated with long routes without an excessive area penalty. The goal is to reschedule circuit operations in such a way that a signal may use multiple clock cycles to traverse a long route, rather than requiring a single long clock period. This rescheduling would not effect the timing of the visible outputs~(~no latency is added to the overall system~).Specifically, we analyze the effects of adding a small number of registered routing switches to an FPGA architecture with segmented routing resources. A parameterized FPGA architecture is studied where the percentage of registered routing switches is varied and the speed improvement and area penalty is evaluated. Novel algorithms are presented that allow a circuit to best utilize an architecture with a given percentage of registered switches. We believe that this is the first study that attempts to evauate the tradeoffs associated with switches required in FPGA architectures.Our experiments indicate that the architectural features introduced can produce significant speedup for high speed circuits without excessive area costs. We believe that these techniques will become increasingly important in the future as deep sub-micron process technologies shrink, and wire delays become even more significant.

REFERENCES

• 1: Altera. Altera 2000 Databook. Available from: http://www.altera.com/html/literature/lds.html.
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: J. Cong and Y. Ding. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Transactions on CAD, pages 1--12, Jan 1994.
• 4: C. Leiserson, F. Rose, and J. Saxe. Optimizing synchronous circuitry. Journal of VLSI and Computer Systems, pages 41-67, 1983.
• 5: C. Leiserson and J. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5-35, 1991.
• 6: N. Maheshwari and S. S. Sapatnekar. Efficient retiming of large circuits. IEEE Transactions on VLSI Systems, 6(1):74-83, 1998.
• 7: Alan Marshall , Tony Stansfield , Igor Kostarnov , Jean Vuillemin , Brad Hutchings, A reconfigurable arithmetic array for multimedia applications, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.135-143, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296444]
• 8: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 9: Marios C. Papaefthymiou, Understanding retiming through maximum average-weight cycles, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.338-348, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113410]
• 10: J. Rubinstein, P. Penfield, and M. Horowitz. Signal delay inRC tree networks. IEEE Transactions on CAD, 2(3):202-211, 1983.
• 11: Narendra Shenoy , Richard Rudell, Efficient implementation of retiming, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.226-233, November 06-10, 1994, San Jose, California, United States
• 12: William Tsu , Kip Macy , Atul Joshi , Randy Huang , Norman Walker , Tony Tung , Omid Rowhani , Varghese George , John Wawrzynek , André DeHon, HSRA: high-speed, hierarchical synchronous reconfigurable array, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.125-134, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296442]
• 13: Xilinx. Xilinx 2000 Databook. Available from: http://www.xilinx.com/partinfo/databook.htm.

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.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

General Terms:
Design, Performance