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

Wai-Kei Mak; D. F. Wong

doi:10.1109/ICCAD.1995.480138

Board-level multi-terminal net 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

4 Citations (Scopus)

Abstract

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 language	English
Title of host publication	1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995
Publisher	IEEE
Pages	339-344
Number of pages	6
ISBN (Print)	0818672137, 0818682000
DOIs	https://doi.org/10.1109/ICCAD.1995.480138
Publication status	Published - Aug 1995
Event	1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995 - San Jose, United States Duration: 5 Nov 1995 → 9 Nov 1995 https://ieeexplore.ieee.org/xpl/conhome/3472/proceeding (Link to conference proceedings)

Publication series

Name	Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

Conference

Conference	1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995
Country/Territory	United States
City	San Jose
Period	5/11/95 → 9/11/95
Internet address	https://ieeexplore.ieee.org/xpl/conhome/3472/proceeding (Link to conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1109/ICCAD.1995.480138

Cite this

@inbook{b50850c7fe3c4d62bd3856b3e7cf8e3a,

title = "Board-level multi-terminal net routing for FPGA-based logic emulation",

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

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

note = "Funding Information: {\textquoteleft}This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459, by a DAC Design Automation Scholarship, and by a grant from AT&T Bell Laboratories. Publisher Copyright: {\textcopyright} 1995 IEEE ; 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995 ; Conference date: 05-11-1995 Through 09-11-1995",

year = "1995",

month = aug,

doi = "10.1109/ICCAD.1995.480138",

language = "English",

isbn = "0818672137",

series = "Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995",

publisher = "IEEE",

pages = "339--344",

booktitle = "1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/3472/proceeding",

}

Mak, W-K & Wong, DF 1995, Board-level multi-terminal net routing for FPGA-based logic emulation. in 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995. Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995, IEEE, pp. 339-344, 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995, San Jose, California, United States, 5/11/95. https://doi.org/10.1109/ICCAD.1995.480138

Board-level multi-terminal net routing for FPGA-based logic emulation. / Mak, Wai-Kei; Wong, D. F.
1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995. IEEE, 1995. p. 339-344 (Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995).

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

TY - CHAP

T1 - Board-level multi-terminal net 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, by a DAC Design Automation Scholarship, and by a grant from AT&T Bell Laboratories. Publisher Copyright: © 1995 IEEE

PY - 1995/8

Y1 - 1995/8

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

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

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

U2 - 10.1109/ICCAD.1995.480138

DO - 10.1109/ICCAD.1995.480138

M3 - Chapter

AN - SCOPUS:0029516533

SN - 0818672137

SN - 0818682000

T3 - Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

SP - 339

EP - 344

BT - 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

PB - IEEE

T2 - 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

Y2 - 5 November 1995 through 9 November 1995

ER -

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

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this