On optimal board-level routing for FPGA-based logic emulation

Wai Kei Mak, D. F. Wong

Research output: Contribution to journalArticlepeer-review


In this paper, we consider a board-level routing problem which is applicable to field-programmable gate arrays (FPGA)-based logic emulation systems such as the Realizer System [3] and the Enterprise Emulation System [5] manufactured by Quickturn Design Systems. For the case where all nets are two-terminal nets, we present an O(n2)-time optimal algorithm where n is the number of nets. Our algorithm guarantees 100% routing completion if the number of interchip signal pins on each FPGA chip in the logic emulation system is less than or equal to the number of I/O pins on the chip. Our algorithm is based on iterative computation of Euler circuits in graphs. We also prove that the routing problem with multiterminal nets is NP-complete. And we suggest one way to handle multiterminal nets using some additional resources.

Original languageEnglish (US)
Pages (from-to)282-289
Number of pages8
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number3
StatePublished - Dec 1 1997
Externally publishedYes


  • Design automation
  • Field-programmable gate arrays
  • Logic emulation
  • Routing

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'On optimal board-level routing for FPGA-based logic emulation'. Together they form a unique fingerprint.

Cite this