Board-level multi-terminal net routing for FPGA-based logic emulation

Wai Kei Mak, D. F. Wong

Research output: Contribution to journalConference articlepeer-review


We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System and the Enterprise Emulation System manufactured by Quickturn Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets. In this paper, we show how multi-terminal nets can be handled by decomposition into two-terminal nets. We show that the multi-terminal net decomposition problem can be modelled 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)339-344
Number of pages6
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - 1995
Externally publishedYes
EventProceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design - San Jose, CA, USA
Duration: Nov 5 1995Nov 9 1995

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


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

Cite this