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

Wai-Kei Mak, D. F. Wong

Research output: Chapter in book/report/conference proceedingChapterpeer-review

11 Citations (Scopus)


In this paper, we consider a board-level routing problem which is applicable to FPGA-based logic emulation systems such as the Realizer system [3] and the Enterprise Emulation System [5] manufactured by Quickturn 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 inter-chip 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 iteratively finding Euler circuits in graphs. We also prove that the routing problem with multi-terminal nets is NP-complete.

Original languageEnglish
Title of host publication32nd ACM/IEEE Design Automation Conference - Proceedings 1995
PublisherAssociation for Computing Machinery (ACM)
Number of pages5
ISBN (Print)9780897917254, 0897917251
Publication statusPublished - Jan 1995
Event32nd ACM/IEEE Design Automation Conference, DAC 1995 - San Francisco, United States
Duration: 12 Jun 199516 Jun 1995
https://dl.acm.org/doi/proceedings/10.1145/217474 (Link to conference proceedings)

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0738-100X


Conference32nd ACM/IEEE Design Automation Conference, DAC 1995
Country/TerritoryUnited States
CitySan Francisco
Internet address

Scopus Subject Areas

  • Hardware and Architecture
  • Control and Systems Engineering


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

Cite this