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

Wai-Kei Mak; D. F. Wong

doi:10.1145/217474.217586

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

Wai-Kei Mak, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Chapter › peer-review

11 Citations (Scopus)

Abstract

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(n²)-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 language	English
Title of host publication	32nd ACM/IEEE Design Automation Conference - Proceedings 1995
Publisher	Association for Computing Machinery (ACM)
Pages	552-556
Number of pages	5
ISBN (Print)	9780897917254, 0897917251
DOIs	https://doi.org/10.1145/217474.217586 https://doi.org/10.1109/DAC.1995.250008
Publication status	Published - Jan 1995
Event	32nd ACM/IEEE Design Automation Conference, DAC 1995 - San Francisco, United States Duration: 12 Jun 1995 → 16 Jun 1995 https://dl.acm.org/doi/proceedings/10.1145/217474 (Link to conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/10575/proceeding

Publication series

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

Conference

Conference	32nd ACM/IEEE Design Automation Conference, DAC 1995
Country/Territory	United States
City	San Francisco
Period	12/06/95 → 16/06/95
Internet address	https://dl.acm.org/doi/proceedings/10.1145/217474 (Link to conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/10575/proceeding

Scopus Subject Areas

Hardware and Architecture
Control and Systems Engineering

Access to Document

Cite this

@inbook{0b59e20e03874db086cb9a16b8913814,

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

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

note = "Funding Information: This work was partially supported by the Texas Advanced Research Program under Grant No.003658459, byaDAC Design Automation Scholarship, and by a grant from AT&T Bell Laboratories. Publisher Copyright: {\textcopyright} 1995 IEEE ; 32nd ACM/IEEE Design Automation Conference, DAC 1995 ; Conference date: 12-06-1995 Through 16-06-1995",

year = "1995",

month = jan,

doi = "10.1145/217474.217586",

language = "English",

isbn = "9780897917254",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "552--556",

booktitle = "32nd ACM/IEEE Design Automation Conference - Proceedings 1995",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/217474, https://ieeexplore.ieee.org/xpl/conhome/10575/proceeding",

}

Mak, W-K & Wong, DF 1995, On optimal board-level routing for FPGA-based logic emulation. in 32nd ACM/IEEE Design Automation Conference - Proceedings 1995. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 552-556, 32nd ACM/IEEE Design Automation Conference, DAC 1995, San Francisco, California, United States, 12/06/95. https://doi.org/10.1145/217474.217586, https://doi.org/10.1109/DAC.1995.250008

TY - CHAP

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

AU - Mak, Wai-Kei

AU - Wong, D. F.

N1 - Funding Information: This work was partially supported by the Texas Advanced Research Program under Grant No.003658459, byaDAC Design Automation Scholarship, and by a grant from AT&T Bell Laboratories. Publisher Copyright: © 1995 IEEE

PY - 1995/1

Y1 - 1995/1

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

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

UR - https://dl.acm.org/doi/10.1145/217474.217586

UR - https://ieeexplore.ieee.org/document/1586764

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

U2 - 10.1145/217474.217586

DO - 10.1145/217474.217586

M3 - Chapter

AN - SCOPUS:0029224151

SN - 9780897917254

SN - 0897917251

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 552

EP - 556

BT - 32nd ACM/IEEE Design Automation Conference - Proceedings 1995

PB - Association for Computing Machinery (ACM)

T2 - 32nd ACM/IEEE Design Automation Conference, DAC 1995

Y2 - 12 June 1995 through 16 June 1995

ER -

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

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this