An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs

K. K. Lee; D. F. Wong

doi:10.1109/ICCD.1999.808428

An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs

K. K. Lee
, D. F. Wong

Office of the Provost

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

2 Citations (Scopus)

Abstract

We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs. We show that if the CLB has b bases, a tree network with n nodes call be mapped in O(C·n^2b-1) time, where C is a function dependent on b. b is fixed for a given CLB architecture. In particular, this algorithm runs in O(n⁵) time when mapping a circuit of n nodes onto the Xilinx XC4000. To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any non-trivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n³) algorithm. The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.

Original language	English
Title of host publication	Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999
Publisher	IEEE
Pages	216-221
Number of pages	6
ISBN (Print)	076950406X
DOIs	https://doi.org/10.1109/ICCD.1999.808428
Publication status	Published - 10 Oct 1999
Event	17th IEEE International Conference on Computer Design, ICCD 1999 - Austin, United States Duration: 10 Oct 1999 → 13 Oct 1999 https://ieeexplore.ieee.org/xpl/conhome/6554/proceeding (Conference proceedings)

Publication series

Name	Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors
ISSN (Print)	1063-6404
ISSN (Electronic)	2576-6996

Conference

Conference	17th IEEE International Conference on Computer Design, ICCD 1999
Country/Territory	United States
City	Austin
Period	10/10/99 → 13/10/99
Internet address	https://ieeexplore.ieee.org/xpl/conhome/6554/proceeding (Conference proceedings)

Access to Document

10.1109/ICCD.1999.808428

Cite this

Lee, K. K., & Wong, D. F. (1999). An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs. In Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999 (pp. 216-221). (Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors). IEEE. https://doi.org/10.1109/ICCD.1999.808428

@inproceedings{d46b5c2d3e164ad8af0d478c9085b422,

title = "An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs",

abstract = "We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs. We show that if the CLB has b bases, a tree network with n nodes call be mapped in O(C·n2b-1) time, where C is a function dependent on b. b is fixed for a given CLB architecture. In particular, this algorithm runs in O(n5) time when mapping a circuit of n nodes onto the Xilinx XC4000. To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any non-trivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n3) algorithm. The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.",

author = "Lee, \{K. K.\} and Wong, \{D. F.\}",

note = "This work was partially supported by the Texas Advanced Research Program under Grant No. 003658288; 17th IEEE International Conference on Computer Design, ICCD 1999 ; Conference date: 10-10-1999 Through 13-10-1999",

year = "1999",

month = oct,

day = "10",

doi = "10.1109/ICCD.1999.808428",

language = "English",

isbn = "076950406X",

series = "Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors",

publisher = "IEEE",

pages = "216--221",

booktitle = "Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999",

address = "United States",

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

}

Lee, KK & Wong, DF 1999, An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs. in Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999. Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors, IEEE, pp. 216-221, 17th IEEE International Conference on Computer Design, ICCD 1999, Austin, Texas, United States, 10/10/99. https://doi.org/10.1109/ICCD.1999.808428

An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs. / Lee, K. K.; Wong, D. F.
Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999. IEEE, 1999. p. 216-221 (Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors).

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

TY - GEN

T1 - An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs

AU - Lee, K. K.

AU - Wong, D. F.

N1 - This work was partially supported by the Texas Advanced Research Program under Grant No. 003658288

PY - 1999/10/10

Y1 - 1999/10/10

N2 - We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs. We show that if the CLB has b bases, a tree network with n nodes call be mapped in O(C·n2b-1) time, where C is a function dependent on b. b is fixed for a given CLB architecture. In particular, this algorithm runs in O(n5) time when mapping a circuit of n nodes onto the Xilinx XC4000. To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any non-trivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n3) algorithm. The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.

AB - We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs. We show that if the CLB has b bases, a tree network with n nodes call be mapped in O(C·n2b-1) time, where C is a function dependent on b. b is fixed for a given CLB architecture. In particular, this algorithm runs in O(n5) time when mapping a circuit of n nodes onto the Xilinx XC4000. To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any non-trivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n3) algorithm. The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.

UR - https://www.scopus.com/pages/publications/0033300642

U2 - 10.1109/ICCD.1999.808428

DO - 10.1109/ICCD.1999.808428

M3 - Conference proceeding

AN - SCOPUS:0033300642

SN - 076950406X

T3 - Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors

SP - 216

EP - 221

BT - Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999

PB - IEEE

T2 - 17th IEEE International Conference on Computer Design, ICCD 1999

Y2 - 10 October 1999 through 13 October 1999

ER -

An exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this