GPU-accelerated Path-based Timing Analysis

Guannan Guo; Tsung-Wei Huang; Yibo Lin; Martin Wong

doi:10.1109/DAC18074.2021.9586316

GPU-accelerated Path-based Timing Analysis

Guannan Guo, Tsung-Wei Huang, Yibo Lin, Martin Wong

Office of the Provost

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

24 Citations (Scopus)

Abstract

Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by 543× on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by 25-45×.

Original language	English
Title of host publication	58th ACM/IEEE Design Automation Conference - Proceedings 2021
Publisher	IEEE
Pages	721-726
Number of pages	6
ISBN (Electronic)	9781665432740
ISBN (Print)	9781665432757
DOIs	https://doi.org/10.1109/DAC18074.2021.9586316
Publication status	Published - 13 Dec 2021
Event	58th ACM/IEEE Design Automation Conference, DAC 2021 - Online and , San Francisco, United States Duration: 5 Dec 2021 → 31 Dec 2021 https://www.dac.com/About/Conference-Archive/58th-DAC-2021 (Conference website) https://www.dac.com/Portals/0/Documents/Conference/DAC58%20Onsite%20Guide_v3.pdf?ver=PzAzrEcD9k-zkYioncfDUw%3d%3d (Conference programme ) https://ieeexplore.ieee.org/xpl/conhome/9585997/proceeding (Conference proceedings)

Publication series

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

Conference

Conference	58th ACM/IEEE Design Automation Conference, DAC 2021
Country/Territory	United States
City	San Francisco
Period	5/12/21 → 31/12/21
Internet address	https://www.dac.com/About/Conference-Archive/58th-DAC-2021 (Conference website) https://www.dac.com/Portals/0/Documents/Conference/DAC58%20Onsite%20Guide_v3.pdf?ver=PzAzrEcD9k-zkYioncfDUw%3d%3d (Conference programme ) https://ieeexplore.ieee.org/xpl/conhome/9585997/proceeding (Conference proceedings)

Scopus Subject Areas

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

Access to Document

10.1109/DAC18074.2021.9586316

Cite this

@inproceedings{dcf474a1c30a445baadfb3d73d34f130,

title = "GPU-accelerated Path-based Timing Analysis",

abstract = "Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by 543× on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by 25-45×.",

author = "Guannan Guo and Tsung-Wei Huang and Yibo Lin and Martin Wong",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 58th ACM/IEEE Design Automation Conference, DAC 2021 ; Conference date: 05-12-2021 Through 31-12-2021",

year = "2021",

month = dec,

day = "13",

doi = "10.1109/DAC18074.2021.9586316",

language = "English",

isbn = "9781665432757",

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

publisher = "IEEE",

pages = "721--726",

booktitle = "58th ACM/IEEE Design Automation Conference - Proceedings 2021",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/58th-DAC-2021, https://www.dac.com/Portals/0/Documents/Conference/DAC58%20Onsite%20Guide_v3.pdf?ver=PzAzrEcD9k-zkYioncfDUw%3d%3d, https://ieeexplore.ieee.org/xpl/conhome/9585997/proceeding",

}

Guo, G, Huang, T-W, Lin, Y & Wong, M 2021, GPU-accelerated Path-based Timing Analysis. in 58th ACM/IEEE Design Automation Conference - Proceedings 2021. ACM/IEEE Design Automation Conference - Proceedings, vol. 2021-December, IEEE, pp. 721-726, 58th ACM/IEEE Design Automation Conference, DAC 2021, San Francisco, California, United States, 5/12/21. https://doi.org/10.1109/DAC18074.2021.9586316

TY - GEN

T1 - GPU-accelerated Path-based Timing Analysis

AU - Guo, Guannan

AU - Huang, Tsung-Wei

AU - Lin, Yibo

AU - Wong, Martin

PY - 2021/12/13

Y1 - 2021/12/13

N2 - Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by 543× on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by 25-45×.

AB - Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by 543× on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by 25-45×.

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

U2 - 10.1109/DAC18074.2021.9586316

DO - 10.1109/DAC18074.2021.9586316

M3 - Conference proceeding

AN - SCOPUS:85115143156

SN - 9781665432757

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 721

EP - 726

BT - 58th ACM/IEEE Design Automation Conference - Proceedings 2021

PB - IEEE

T2 - 58th ACM/IEEE Design Automation Conference, DAC 2021

Y2 - 5 December 2021 through 31 December 2021

ER -

GPU-accelerated Path-based Timing Analysis

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this