A Database Dependent Framework for K-Input Maximum Fanout-Free Window Rewriting

Xuliang Zhu; Ruofei Tang; Lei Chen; Xing Li; Xin Huang; Mingxuan Yuan; Weihua Sheng; Jianliang Xu

doi:10.1109/DAC56929.2023.10247727

A Database Dependent Framework for K-Input Maximum Fanout-Free Window Rewriting

Xuliang Zhu, Ruofei Tang, Lei Chen^*, Xing Li, Xin Huang, Mingxuan Yuan, Weihua Sheng, Jianliang Xu

^*Corresponding author for this work

Department of Computer Science

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

1 Citation (Scopus)

Abstract

Rewriting is a widely used logic optimization approach incorporated in most commercial logic synthesis tools. In this paper, we present a new rewriting method based on AndInverted Graph (AIG). Rather than focusing on cut rewriting, it considers a novel sub-structure called Maximum Fanout-Free Window (MFFW) and rewrites with a more compact implementation. Both exact synthesis and heuristic methods can be adopted to optimize MFFWs. A database dependent framework is proposed to store the optimal sub-structures to accelerate the processing. We further propose the semi-canonicalization to reduce the scale of the database, which could reduce more than 98% of the 4-input MFFW database. Extensive experiments on benchmark datasets demonstrate both the effectiveness and efficiency of our proposed framework.

Original language	English
Title of host publication	60th ACM/IEEE Design Automation Conference - Proceedings 2023
Publisher	IEEE
Pages	1-6
Number of pages	6
ISBN (Electronic)	9798350323481
ISBN (Print)	9798350323498
DOIs	https://doi.org/10.1109/DAC56929.2023.10247727
Publication status	Published - Jul 2023
Event	60th ACM/IEEE Design Automation Conference, DAC 2023 - Moscone West, San Francisco, United States Duration: 9 Jul 2023 → 13 Jul 2023 https://www.dac.com/ https://60dac.conference-program.com/ https://ieeexplore.ieee.org/xpl/conhome/10247654/proceeding

Publication series

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

Conference

Conference	60th ACM/IEEE Design Automation Conference, DAC 2023
Country/Territory	United States
City	San Francisco
Period	9/07/23 → 13/07/23
Internet address	https://www.dac.com/ https://60dac.conference-program.com/ https://ieeexplore.ieee.org/xpl/conhome/10247654/proceeding

Scopus Subject Areas

Electrical and Electronic Engineering
Control and Systems Engineering
Computer Science Applications
Modelling and Simulation

Access to Document

10.1109/DAC56929.2023.10247727

Cite this

@inproceedings{662603fad80d4aa59e8e36ff4022a43a,

title = "A Database Dependent Framework for K-Input Maximum Fanout-Free Window Rewriting",

abstract = "Rewriting is a widely used logic optimization approach incorporated in most commercial logic synthesis tools. In this paper, we present a new rewriting method based on AndInverted Graph (AIG). Rather than focusing on cut rewriting, it considers a novel sub-structure called Maximum Fanout-Free Window (MFFW) and rewrites with a more compact implementation. Both exact synthesis and heuristic methods can be adopted to optimize MFFWs. A database dependent framework is proposed to store the optimal sub-structures to accelerate the processing. We further propose the semi-canonicalization to reduce the scale of the database, which could reduce more than 98% of the 4-input MFFW database. Extensive experiments on benchmark datasets demonstrate both the effectiveness and efficiency of our proposed framework.",

author = "Xuliang Zhu and Ruofei Tang and Lei Chen and Xing Li and Xin Huang and Mingxuan Yuan and Weihua Sheng and Jianliang Xu",

note = "Funding Information: This paper is supported by HK RGC Grant No. 12200021. Publisher Copyright: {\textcopyright} 2023 IEEE.; 60th ACM/IEEE Design Automation Conference, DAC 2023 ; Conference date: 09-07-2023 Through 13-07-2023",

year = "2023",

month = jul,

doi = "10.1109/DAC56929.2023.10247727",

language = "English",

isbn = "9798350323498",

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

publisher = "IEEE",

pages = "1--6",

booktitle = "60th ACM/IEEE Design Automation Conference - Proceedings 2023",

address = "United States",

url = "https://www.dac.com/, https://60dac.conference-program.com/, https://ieeexplore.ieee.org/xpl/conhome/10247654/proceeding",

}

Zhu, X, Tang, R, Chen, L, Li, X, Huang, X, Yuan, M, Sheng, W & Xu, J 2023, A Database Dependent Framework for K-Input Maximum Fanout-Free Window Rewriting. in 60th ACM/IEEE Design Automation Conference - Proceedings 2023. ACM/IEEE Design Automation Conference - Proceedings, vol. 2023-July, IEEE, pp. 1-6, 60th ACM/IEEE Design Automation Conference, DAC 2023, San Francisco, California, United States, 9/07/23. https://doi.org/10.1109/DAC56929.2023.10247727

A Database Dependent Framework for K-Input Maximum Fanout-Free Window Rewriting. / Zhu, Xuliang; Tang, Ruofei; Chen, Lei et al.
60th ACM/IEEE Design Automation Conference - Proceedings 2023. IEEE, 2023. p. 1-6 (ACM/IEEE Design Automation Conference - Proceedings; Vol. 2023-July).

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

TY - GEN

T1 - A Database Dependent Framework for K-Input Maximum Fanout-Free Window Rewriting

AU - Zhu, Xuliang

AU - Tang, Ruofei

AU - Chen, Lei

AU - Li, Xing

AU - Huang, Xin

AU - Yuan, Mingxuan

AU - Sheng, Weihua

AU - Xu, Jianliang

PY - 2023/7

Y1 - 2023/7

N2 - Rewriting is a widely used logic optimization approach incorporated in most commercial logic synthesis tools. In this paper, we present a new rewriting method based on AndInverted Graph (AIG). Rather than focusing on cut rewriting, it considers a novel sub-structure called Maximum Fanout-Free Window (MFFW) and rewrites with a more compact implementation. Both exact synthesis and heuristic methods can be adopted to optimize MFFWs. A database dependent framework is proposed to store the optimal sub-structures to accelerate the processing. We further propose the semi-canonicalization to reduce the scale of the database, which could reduce more than 98% of the 4-input MFFW database. Extensive experiments on benchmark datasets demonstrate both the effectiveness and efficiency of our proposed framework.

AB - Rewriting is a widely used logic optimization approach incorporated in most commercial logic synthesis tools. In this paper, we present a new rewriting method based on AndInverted Graph (AIG). Rather than focusing on cut rewriting, it considers a novel sub-structure called Maximum Fanout-Free Window (MFFW) and rewrites with a more compact implementation. Both exact synthesis and heuristic methods can be adopted to optimize MFFWs. A database dependent framework is proposed to store the optimal sub-structures to accelerate the processing. We further propose the semi-canonicalization to reduce the scale of the database, which could reduce more than 98% of the 4-input MFFW database. Extensive experiments on benchmark datasets demonstrate both the effectiveness and efficiency of our proposed framework.

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

UR - https://60dac.conference-program.com/presentation/?id=RESEARCH568&sess=sess135

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

U2 - 10.1109/DAC56929.2023.10247727

DO - 10.1109/DAC56929.2023.10247727

M3 - Conference proceeding

SN - 9798350323498

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 1

EP - 6

BT - 60th ACM/IEEE Design Automation Conference - Proceedings 2023

PB - IEEE

T2 - 60th ACM/IEEE Design Automation Conference, DAC 2023

Y2 - 9 July 2023 through 13 July 2023

ER -

A Database Dependent Framework for K-Input Maximum Fanout-Free Window Rewriting

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this