An exact gate decomposition algorithm for low-power technology mapping

Hai Zhou; D.F. Wong

doi:10.1109/ICCAD.1997.643597

An exact gate decomposition algorithm for low-power technology mapping

Hai Zhou, D.F. Wong

Office of the Provost

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

8 Citations (Scopus)

Abstract

With the remarkable growth of portable application and the increasing frequency and integration density, power is being given comparable weight to speed and area in IC designs. In technology mapping, how decomposition is done can have a significant impact on the power dissipation of the final implementation. In the literature, only heuristic algorithms are given for the low-power gate decomposition problem. In this paper, we prove many properties an optimal decomposition tree must have. Based on these optimality properties, we design an efficient exact algorithm to solve the low-power gate decomposition problem. Moreover, the exact algorithm can be easily modified to a heuristic algorithm which performs much better than the known heuristics.

Original language	English
Title of host publication	1997 IEEE International Conference on Computer Aided Design, ICCAD 1997
Publisher	IEEE
Pages	575-580
Number of pages	6
ISBN (Print)	0818682000
DOIs	https://doi.org/10.1109/ICCAD.1997.643597
Publication status	Published - Nov 1997
Event	1997 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1997 - San Jose, United States Duration: 9 Nov 1997 → 13 Nov 1997 https://ieeexplore.ieee.org/xpl/conhome/5191/proceeding (Link to conference proceedings)

Publication series

Name	Proceedings of IEEE International Conference on Computer Aided Design
Publisher	IEEE

Conference

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

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1109/ICCAD.1997.643597

Cite this

@inbook{071a248066e94f02a034b7a5ff6f5c8a,

title = "An exact gate decomposition algorithm for low-power technology mapping",

abstract = "With the remarkable growth of portable application and the increasing frequency and integration density, power is being given comparable weight to speed and area in IC designs. In technology mapping, how decomposition is done can have a significant impact on the power dissipation of the final implementation. In the literature, only heuristic algorithms are given for the low-power gate decomposition problem. In this paper, we prove many properties an optimal decomposition tree must have. Based on these optimality properties, we design an efficient exact algorithm to solve the low-power gate decomposition problem. Moreover, the exact algorithm can be easily modified to a heuristic algorithm which performs much better than the known heuristics.",

author = "Hai Zhou and D.F. Wong",

note = "Publisher Copyright: {\textcopyright} 1997 IEEE; 1997 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1997 ; Conference date: 09-11-1997 Through 13-11-1997",

year = "1997",

month = nov,

doi = "10.1109/ICCAD.1997.643597",

language = "English",

isbn = "0818682000",

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

publisher = "IEEE",

pages = "575--580",

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

address = "United States",

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

}

Zhou, H & Wong, DF 1997, An exact gate decomposition algorithm for low-power technology mapping. in 1997 IEEE International Conference on Computer Aided Design, ICCAD 1997. Proceedings of IEEE International Conference on Computer Aided Design, IEEE, pp. 575-580, 1997 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1997, San Jose, California, United States, 9/11/97. https://doi.org/10.1109/ICCAD.1997.643597

TY - CHAP

T1 - An exact gate decomposition algorithm for low-power technology mapping

AU - Zhou, Hai

AU - Wong, D.F.

PY - 1997/11

Y1 - 1997/11

N2 - With the remarkable growth of portable application and the increasing frequency and integration density, power is being given comparable weight to speed and area in IC designs. In technology mapping, how decomposition is done can have a significant impact on the power dissipation of the final implementation. In the literature, only heuristic algorithms are given for the low-power gate decomposition problem. In this paper, we prove many properties an optimal decomposition tree must have. Based on these optimality properties, we design an efficient exact algorithm to solve the low-power gate decomposition problem. Moreover, the exact algorithm can be easily modified to a heuristic algorithm which performs much better than the known heuristics.

AB - With the remarkable growth of portable application and the increasing frequency and integration density, power is being given comparable weight to speed and area in IC designs. In technology mapping, how decomposition is done can have a significant impact on the power dissipation of the final implementation. In the literature, only heuristic algorithms are given for the low-power gate decomposition problem. In this paper, we prove many properties an optimal decomposition tree must have. Based on these optimality properties, we design an efficient exact algorithm to solve the low-power gate decomposition problem. Moreover, the exact algorithm can be easily modified to a heuristic algorithm which performs much better than the known heuristics.

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

U2 - 10.1109/ICCAD.1997.643597

DO - 10.1109/ICCAD.1997.643597

M3 - Chapter

AN - SCOPUS:0031364693

SN - 0818682000

T3 - Proceedings of IEEE International Conference on Computer Aided Design

SP - 575

EP - 580

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

PB - IEEE

T2 - 1997 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1997

Y2 - 9 November 1997 through 13 November 1997

ER -

An exact gate decomposition algorithm for low-power technology mapping

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this