TY - GEN
T1 - GPU-accelerated Path-based Timing Analysis
AU - Guo, Guannan
AU - Huang, Tsung-Wei
AU - Lin, Yibo
AU - Wong, Martin
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021/12/5
Y1 - 2021/12/5
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
UR - http://www.scopus.com/inward/citedby.url?scp=85115143156&partnerID=8YFLogxK
U2 - 10.1109/DAC18074.2021.9586316
DO - 10.1109/DAC18074.2021.9586316
M3 - Conference contribution
AN - SCOPUS:85115143156
T3 - Proceedings - Design Automation Conference
SP - 721
EP - 726
BT - 2021 58th ACM/IEEE Design Automation Conference, DAC 2021
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 58th ACM/IEEE Design Automation Conference, DAC 2021
Y2 - 5 December 2021 through 9 December 2021
ER -