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

Wai Kei Mak, D. F. Wong

Research output: Contribution to journalArticlepeer-review


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 (US)
Pages (from-to)151-167
Number of pages17
JournalACM Transactions on Design Automation of Electronic Systems
Issue number2
StatePublished - 1997
Externally publishedYes


  • Board-level routing
  • Crossbars
  • Field-programmable gate arrays
  • Logic emulation
  • Multi-terminal net decomposition

ASJC Scopus subject areas

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


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

Cite this