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

Wai-Kei Mak; D.F. Wong

doi:10.1109/43.594833

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

Wai-Kei Mak, D.F. Wong

Office of the Provost

Research output: Contribution to journal › Journal article › peer-review

11 Citations (Scopus)

Abstract

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(n²)-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 language	English
Pages (from-to)	282-289
Number of pages	8
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	16
Issue number	3
DOIs	https://doi.org/10.1109/43.594833
Publication status	Published - Mar 1997

Scopus Subject Areas

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

Access to Document

10.1109/43.594833

Cite this

@article{9f02464d6ce24802b0c97e8cf9cd90c4,

title = "On optimal board-level routing for FPGA-based logic emulation",

abstract = "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.",

author = "Wai-Kei Mak and D.F. Wong",

note = "Publisher copyright: {\textcopyright} 1997 IEEE",

year = "1997",

month = mar,

doi = "10.1109/43.594833",

language = "English",

volume = "16",

pages = "282--289",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "IEEE",

number = "3",

}

TY - JOUR

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

AU - Mak, Wai-Kei

AU - Wong, D.F.

PY - 1997/3

Y1 - 1997/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031100299&partnerID=8YFLogxK

U2 - 10.1109/43.594833

DO - 10.1109/43.594833

M3 - Journal article

AN - SCOPUS:0031100299

SN - 0278-0070

VL - 16

SP - 282

EP - 289

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 3

ER -

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

Abstract

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this