Massively Parallel AIG Resubstitution

Yang Sun; Tianji Liu; Martin D.F. Wong; Evangeline F.Y. Young

doi:10.1145/3649329.3655987

Massively Parallel AIG Resubstitution

Yang Sun, Tianji Liu, Martin D.F. Wong, Evangeline F.Y. Young

Department of Computer Science

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

1 Citation (Scopus)

Abstract

Resubstitution is a flexible algorithmic framework for circuit restructuring that has been incorporated into many high-effort logic optimization flows. It is thus important to speed up resubstitution in order to obtain high-quality realizations of large-scale designs. This paper proposes a massively parallel AIG resubstitution algorithm targeting GPUs, with effective approaches to addressing cyclic dependencies and restructuring conflicts. Compared with ABC and mockturtle, our algorithm achieves 41.9× and 50.3× acceleration on average without quality degradation. When combining our resubstitution with other GPU algorithms, a GPU-based resyn2rs sequence obtains 46.4× speedup over ABC with 0.8% and 5.8% smaller area and delay respectively.

Original language	English
Title of host publication	Proceedings of the 61st ACM/IEEE Design Automation Conference, DAC 2024
Place of Publication	New York
Publisher	Association for Computing Machinery (ACM)
Number of pages	6
ISBN (Print)	9798400706011
DOIs	https://doi.org/10.1145/3649329.3655987
Publication status	Published - 7 Nov 2024
Event	61st ACM/IEEE Design Automation Conference, DAC 2024 - San Francisco, San Francisco, United States Duration: 23 Jun 2024 → 27 Jun 2024 https://dl.acm.org/doi/proceedings/10.1145/3649329 (Conference proceedings) https://www.dac.com/

Publication series

Name	Proceedings of the ACM/IEEE Design Automation Conference
Publisher	Association for Computing Machinery

Conference

Conference	61st ACM/IEEE Design Automation Conference, DAC 2024
Abbreviated title	DAC 2024
Country/Territory	United States
City	San Francisco
Period	23/06/24 → 27/06/24
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3649329 (Conference proceedings) https://www.dac.com/

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1145/3649329.3655987Licence: CC BY

Cite this

@inproceedings{fa1c7afb691b4c3caed78bb20c7b34a5,

title = "Massively Parallel AIG Resubstitution",

abstract = "Resubstitution is a flexible algorithmic framework for circuit restructuring that has been incorporated into many high-effort logic optimization flows. It is thus important to speed up resubstitution in order to obtain high-quality realizations of large-scale designs. This paper proposes a massively parallel AIG resubstitution algorithm targeting GPUs, with effective approaches to addressing cyclic dependencies and restructuring conflicts. Compared with ABC and mockturtle, our algorithm achieves 41.9× and 50.3× acceleration on average without quality degradation. When combining our resubstitution with other GPU algorithms, a GPU-based resyn2rs sequence obtains 46.4× speedup over ABC with 0.8% and 5.8% smaller area and delay respectively.",

author = "Yang Sun and Tianji Liu and Wong, {Martin D.F.} and Young, {Evangeline F.Y.}",

note = "This research was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CUHK14210923). Publisher Copyright: {\textcopyright} 2024 Copyright held by the owner/author(s).; 61st ACM/IEEE Design Automation Conference, DAC 2024, DAC 2024 ; Conference date: 23-06-2024 Through 27-06-2024",

year = "2024",

month = nov,

day = "7",

doi = "10.1145/3649329.3655987",

language = "English",

isbn = "9798400706011",

series = "Proceedings of the ACM/IEEE Design Automation Conference",

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

booktitle = "Proceedings of the 61st ACM/IEEE Design Automation Conference, DAC 2024",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/3649329, https://www.dac.com/",

}

Sun, Y, Liu, T, Wong, MDF & Young, EFY 2024, Massively Parallel AIG Resubstitution. in Proceedings of the 61st ACM/IEEE Design Automation Conference, DAC 2024., 157, Proceedings of the ACM/IEEE Design Automation Conference, Association for Computing Machinery (ACM), New York, 61st ACM/IEEE Design Automation Conference, DAC 2024, San Francisco, United States, 23/06/24. https://doi.org/10.1145/3649329.3655987

Massively Parallel AIG Resubstitution. / Sun, Yang; Liu, Tianji; Wong, Martin D.F. et al.
Proceedings of the 61st ACM/IEEE Design Automation Conference, DAC 2024. New York: Association for Computing Machinery (ACM), 2024. 157 (Proceedings of the ACM/IEEE Design Automation Conference).

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

TY - GEN

T1 - Massively Parallel AIG Resubstitution

AU - Sun, Yang

AU - Liu, Tianji

AU - Wong, Martin D.F.

AU - Young, Evangeline F.Y.

N1 - This research was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CUHK14210923). Publisher Copyright: © 2024 Copyright held by the owner/author(s).

PY - 2024/11/7

Y1 - 2024/11/7

N2 - Resubstitution is a flexible algorithmic framework for circuit restructuring that has been incorporated into many high-effort logic optimization flows. It is thus important to speed up resubstitution in order to obtain high-quality realizations of large-scale designs. This paper proposes a massively parallel AIG resubstitution algorithm targeting GPUs, with effective approaches to addressing cyclic dependencies and restructuring conflicts. Compared with ABC and mockturtle, our algorithm achieves 41.9× and 50.3× acceleration on average without quality degradation. When combining our resubstitution with other GPU algorithms, a GPU-based resyn2rs sequence obtains 46.4× speedup over ABC with 0.8% and 5.8% smaller area and delay respectively.

AB - Resubstitution is a flexible algorithmic framework for circuit restructuring that has been incorporated into many high-effort logic optimization flows. It is thus important to speed up resubstitution in order to obtain high-quality realizations of large-scale designs. This paper proposes a massively parallel AIG resubstitution algorithm targeting GPUs, with effective approaches to addressing cyclic dependencies and restructuring conflicts. Compared with ABC and mockturtle, our algorithm achieves 41.9× and 50.3× acceleration on average without quality degradation. When combining our resubstitution with other GPU algorithms, a GPU-based resyn2rs sequence obtains 46.4× speedup over ABC with 0.8% and 5.8% smaller area and delay respectively.

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

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

U2 - 10.1145/3649329.3655987

DO - 10.1145/3649329.3655987

M3 - Conference proceeding

AN - SCOPUS:85211160412

SN - 9798400706011

T3 - Proceedings of the ACM/IEEE Design Automation Conference

BT - Proceedings of the 61st ACM/IEEE Design Automation Conference, DAC 2024

PB - Association for Computing Machinery (ACM)

CY - New York

T2 - 61st ACM/IEEE Design Automation Conference, DAC 2024

Y2 - 23 June 2024 through 27 June 2024

ER -

Massively Parallel AIG Resubstitution

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this