Topology-aware buffer insertion and GPU-based massively parallel rerouting for ECO timing optimization

Yen Hung Lin*, Yun Jian Lo, Hian Syun Tong, Wen Hao Liu, Yih-Lang Li

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Conventional buffer insertion in timing ECO involves only minimizing the arrival time of the most critical sink in one multi-pin net and neglects the obstacles and the topology of routed wire segments, which may worsen the arrival times of other sinks and burden subsequent timing ECO. This work develops a topology-aware ECO timing optimization (TOPO) flow that comprises three phases - buffering pair scoring, edge breaking and buffer connection, and topology restructuring. TOPO effectively improves the arrival times of violation sinks without worsening those of other sinks. Experimental results indicate that TOPO improves the worst negative slack (WNS) and total negative slack (TNS) of benchmarks by an average of 79.2% and 84.3%, respectively. The proposed algorithm improves the arrival time that is achieved using conventional two-pin net-based buffer insertion by an average of 40.4%, at the cost of consuming 19x runtime. To speed up routing and further improve sink slack, a highly scalable massively parallel maze routing on Graphics Processing Unit (GPU) platform is also developed to enable the proposed flow to explore more solution candidates. High scalability and parallelism are realized by block partitioning and staggering. Experiments reveal that the proposed GPU-based parallel maze routing can achieve near 12x runtime speedup for two-pin routings. With parallelized maze routing, WNS violations in four out of five cases can be resolved.

Original languageEnglish
Title of host publicationASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference
Pages437-442
Number of pages6
DOIs
StatePublished - 26 Apr 2012
Event17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 - Sydney, NSW, Australia
Duration: 30 Jan 20122 Feb 2012

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

Conference17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
CountryAustralia
CitySydney, NSW
Period30/01/122/02/12

Fingerprint Dive into the research topics of 'Topology-aware buffer insertion and GPU-based massively parallel rerouting for ECO timing optimization'. Together they form a unique fingerprint.

  • Cite this

    Lin, Y. H., Lo, Y. J., Tong, H. S., Liu, W. H., & Li, Y-L. (2012). Topology-aware buffer insertion and GPU-based massively parallel rerouting for ECO timing optimization. In ASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference (pp. 437-442). [6164988] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2012.6164988