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

Wai-Kei Mak, D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

11 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)151-167
Number of pages17
JournalACM Transactions on Design Automation of Electronic Systems
Issue number2
Publication statusPublished - Apr 1997

Scopus Subject Areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Algorithms
  • Verification
  • Field-programmable gate arrays,
  • Logic emulation
  • Boardlevel routing
  • Multi-terminal net decomposition
  • Crossbars


Dive into the research topics of 'Board-level multiterminal net routing for FPGA-based logic emulation'. Together they form a unique fingerprint.

Cite this