Board-level multiterminal net routing for FPGA-based logic emulation

ABSTRACT

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System [Varghese et al. 1993] and the Enterprise Emulation System [Maliniak 1992] manufactured by Quickturn Design Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets [Chan and Schlag 1993; Mak and Wong 1995]. We show how multiterminal nets can be handled by decomposition into two-terminal nets. We show that the multiterminal net decomposition problem can be modeled as a bounded-degree hypergraph-to-graph transformation problem where hyperedges are transformed to spanning trees. A network flow-based algorithm that solves both problems is proposed. It determines if there is a feasible decomposition and gives one whenever such a decomposition exists.

REFERENCES

• 1: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 2: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 3: CHAN, P. K., AND SCHLAG, M. D.F. 1993. Architectural tradeoffs in field-programmabledevice-based computing systems. In Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines (April 1993), 138-141.
• 4: Nan-Chi Chou , Lung-Tien Liu , Chung-Kuan Cheng , Wei-Jin Dai , Rodney Lindelof, Circuit partitioning for huge logic emulation systems, Proceedings of the 31st annual conference on Design automation, p.244-249, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196365]
• 5: FORD, L. R., JR., AND FULKERSON, D.R. 1962. Flows in Networks, Princeton University Press, Princeton, NJ.
• 6: Wai-Kei Mak , D. F. Wong, On optimal board-level routing for FPGA-based logic emulation, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.552-556, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217586]
• 7: SLIMANE-KADI, M., BRASEN, D., AND SAUCIER, G. 1994. A fast-FPGA prototyping system that uses inexpensive high-performance FPIC. In Proceedings of the ACM/SIGDA International Workshop on Field-Programmable Gate Arrays (Feb 1994). ACM, New York, NY.
• 8: MALINIAK, L. 1992. Multiplexing enhances hardware emulation. Electronic Des. (Nov.), 76-78.
• 9: Stephen M. Trimberger, Field-Programmable Gate Array Technology, Kluwer Academic Publishers, Norwell, MA, 1994
• 10: VARGHESE, g., BUTTS, M., AND BATCHELLER, g. 1993. An efficient logic emulation system. IEEE Trans. VLSI 1, (June), 171-174.
• 11: Stephen Walters, Computer-Aided Prototyping for ASIC-Based Systems, IEEE Design & Test, v.8 n.2, p.4-10, April 1991 [doi>10.1109/54.82034]
• 12: YAMADA, K., NAKADA, H., TSUTSUI, A., AND OHTA, N. 1994. High-speed emulation of communication circuits on a multiple-FPGA system. In Proceedings of the ACM/SIGDA International Workshop on Field-Programmable Gate Arrays (Feb 1994). ACM, New York, NY.
• 13: Honghua Yang , D. F. Wong, Circuit clustering for delay minimization under area and pin constraints, Proceedings of the 1995 European conference on Design and Test, p.65, March 06-09, 1995

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays
      B.7.2 Design Aids
          Subjects: Verification

General Terms:
Algorithms, Verification

Keywords:
board-level routing, crossbars, field programmable gate arrays, logic emulation, multi-terminal net decomposition