A hybrid complete-graph partial-crossbar routing architecture for multi-FPGA systems

ABSTRACT

Multi-FPGA systems (MFSs) are used as custom computing machines, logic emulators and rapid prototyping vehicles. A key aspect of these systems is their programmable routing architecture; the manner in which wires, FPGAs and Field-Programmable Interconnect Devices (FPIDs) are connected. Several routing architectures for MFSs have been proposed [Arno92] [Butt92] [Hauc94] [Apti96] [Vuil96] and previous research has shown that the partial crossbar is one of the best existing architectures [Kim96] [Khal97]. In this paper we propose a new routing architecture, called the Hybrid Complete-Graph and Partial-Crossbar (HCGP) which has superior speed and cost compared to a partial crossbar. The new architecture uses both hard-wired and programmable connections between the FPGAs. We compare the performance and cost of the HCGP and partial crossbar architectures experimentally, by mapping a set of 15 large benchmark circuits into each architecture. A customized set of partitioning and inter-chip routing tools were developed, with particular attention paid to architecture-appropriate inter-chip routing algorithms. We show that the cost of the partial crossbar (as measured by the number of pins on all FPGAs and FPIDs required to fit a design), is on average 20% more than the new HCGP architecture and as much as 35% more. Furthermore, the critical path delay for designs implemented on the partial crossbar increased, and were on average 9% more than the HCGP architecture and up to 26% more. Using our experimental approach, we also explore a key architecture parameter associated with the HCGP architecture: the proportion of hard-wired connections versus programmable connections, to determine its best value.

REFERENCES

• Alte94: Altera Corporation, Reconfigurable Interconnect Peripheral Processor (RIPPI0) Users Manual, Version 1.0, 1994.
• Apti96: Aptix Corporation, Product brief: The System Explorer MP4, 1996. Available on Aptix Web site: http://www, aptix.com.
• Arno92: Jeffrey M. Arnold , Duncan A. Buell , Elaine G. Davis, Splash 2, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.316-322, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141896]
• Brow92: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• Butt92: Michael Butts , Jon Batcheller , Joseph Varghese, An Efficient Logic Emulation System, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.138-141, October 11-14, 1992
• Cass93: S. Casselman, "Virtual Computing and The Virtual Computer" Proceedings of IEEE Workshop on FPGAs for Custom Computing Machines, pp. 43-48, 1993.
• Chan93: P.K. Chan, M. D. E Schlag, "Architectural Tradeoffs in Field-Programmable-Device-Based Computing Systems,' Proceedings of IEEE Workshop on FPGAs for Custom Computing Machines, pp. 152- 161, 1993.
• Dray95: T. H. Drayer , J. G. Tront , W. E. King, IV , R. W. Conners, MORRPH: a modular and reprogrammable real-time processing hardware, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines, p.11, April 19-21, 1995
• Exem94: Exemplar Logic, VHDL Synthesis Reference Manual, 1994.
• Fidu82: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Papers on Twenty-five years of electronic design automation, p.241-247, June 1988 [doi>10.1145/62882.62910]
• FCCM: Proceedings of IEEE Workshops/Symposia on FPGAs for Custom Computing Machines, 1992 to 1996.
• Gall94: D. Galloway, D. Karchmer, P. Chow, D. Lewis, and J. Rose, "The Transmogfifier: The University of Toronto Field-Programmable System", CSRI Technical Report (CSRI-306), CSRI, University of Toronto, 1994.
• Gall95: D. Galloway, The Transmogrifier C hardware description language and compiler for FPGAs, Proceedings of the IEEE Symposium on FPGA's for Custom Computing Machines, p.136, April 19-21, 1995
• Hauc94: Scott Hauck , Gaetano Borriello , Carl Ebeling, Mesh Routing Topologies for Multi-FPGA Systems, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.170-177, October 10-12, 1994
• Hutt96: Michael Hutton , J. P. Grossman , Jonathan Rose , Derek Corneil, Characterization and parameterized random generation of digital circuits, Proceedings of the 33rd annual conference on Design automation, p.94-99, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240537]
• Icub97: I-Cube, Inc., The IQX Family Data Sheet, May 1997. Available at: www. icube.com.
• Icub94: I-Cube, Inc., "Using FPID Devices in FPGA-based Prototyping" Application note, Part number:D-22- 002, February 1994.
• Joup87: Norman P. Jouppi, "Timing Analysis and Performance Improvement of MOS VLSI Designs" ih-~E Trans. on CAD, vol. CAD-6, no. 4, pp. 650-665, July 1987.
• Khal95: M.A.S. Khalid and J. Rose, "The Effect of Fixed F O Pin Positioning on The Routability and Speed of FPGAs;' Proceedings of The Third Canadian Workshop on Field-Programmable Devices (FPD'95), pp. 92-104, 1995.
• Khal97: M.A.S. Khalid and J. Rose, "Experimental Evaluation of Mesh and Partial Crossbar Routing Architectures for Multi-FPGA Systems" Proceedings of the Sixth IFIP International Workshop on Logic and Architecture Synthesis (IWLAS'97), 1997.
• Khal98: M.A.S. Khalid, Routing Architecture and Layout Synthesis for Multi-FPGA Systems, Ph.D. Thesis, University of Toronto, in progress.
• Kim96: C. Kim, H. Shin, "A Performance-Driven Logic Emulation System: FPGA Network Design and Performance-Dfiven Partitioning" IEEE Trans. on CAD, vol. 15, no. 5, pp. 560-568, May 1996.
• Knap96: David W. Knapp, Behavioral synthesis: digital system design using the synopsys behavioral compiler, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• Lewi97: David M. Lewis , David R. Galloway , Marcus van Ierssel , Jonathan Rose , Paul Chow, The Transmogrifier-2: a 1 million gate rapid prototyping system, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.53-61, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258312]
• Lin97: S. Lin, Y. Lin, and T. Hwang, "Net Assignment for the FPGA-Based Logic Emulation System in the Folded-Clos Network Structure" IEEE Trans. on CAD, vol. 16, no. 3, pp. 316-320, March 1997.
• Mak97a: Wai-Kei Mak, D. E Wong, "On Optimal Board- Level Routing for FPGA-based Logic Emulation" IEEE Trans. on CAD, vol. 16, no. 3, pp. 282-289, March 1997.
• Mak97b: Wai-Kei Mak , D. F. Wong, Board-level multiterminal net routing for FPGA-based logic emulation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.2, p.151-167, April 1997 [doi>10.1145/253052.253136]
• Prep96: Programmable Electronics Performance Corporation, HDL models for different circuits (synthesis benchmarks) are available on their Web site: http// www. prep.org.
• Quic96: Quicktum Design Systems, Inc., System Realizer Data Sheet, 1996. Available on Quicktum Web site:http://www, quicktum.com.
• Shih92: M. Shih , E. S. Kuh , R.-S. Tsay, Performance-driven system partitioning on multi-chip modules, Proceedings of the 29th ACM/IEEE conference on Design automation, p.53-56, June 08-12, 1992, Anaheim, California, United States
• Syno97: Synopsys, Inc., Design Compiler(Version 3.4a), Behavioral Compiler (Version 3.4a), and Library Compiler (Version 3.4a), Reference Manuals. Documents available on-line.
• Van92: David E. Van den Bout , Joseph N. Morris , Douglas Thomae , Scott Labrozzi , Scot Wingo , Peter Hallman, AnyBoard: An FPGA-Based, Reconfigurable System, IEEE Design & Test, v.9 n.3, p.21-30, July 1992 [doi>10.1109/54.156155]
• Varg93: J. Vargese, M. Butts, and Jon Batcheller, "An Efficient Logic Emulation System", IEEE Trans. on VLSI Systems, vol. 1, no. 2, pp. 171-174, June 1993.
• Vuil96: Jean E. Vuillemin , Patrice Bertin , Didier Roncin , Mark Shand , Hervé H. Touati , Philippe Boucard, Programmable active memories: reconfigurable systems come of age, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.1, p.56-69, March 1996 [doi>10.1109/92.486081]
• Xili97: Xilinx, Inc., Product Specification: XC4000E and XC4000X Series FPGAs, Version 1.2, June 16, 1997. Available on Xilinx Web site: www. xilinx.com.
• Yang91: S. Yang, Logic Synthesis and Optimization Benchmarks User Guide, Version 3.0, Microelectronics Center of North Carolina, January 1991.

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Experimentation, Measurement