PathGen：一种高效的并行关键路径生成算法.pdf

1、PathGen:An Efficient Parallel Critical Path Generation AlgorithmASPDAC25Che Chang,Boyang Zhang,Cheng-Hsiang Chiu,Dian-Lun Lin,Yi-Hua Chung,Wan-Luan Lee,Zhizheng Guo,Yibo Lin,and Tsung-Wei HuangUniversity of Wisconsin,Madison Peking University,Beijing 2What is Critical Path Generation?Why?What is Cri

2、tical Path Generation(CPG)?Given a directed-acyclic circuit graph,report the top-k critical paths in ascending order of path slack/delay Why is CPG important?Crucial for optimizing and verifying circuit timing Increasing design complexity makes CPG runtime a bottleneck in STA engines3Sequential CPG

3、Algorithms iTimerC1,iitRace2,and OpenTimer3demonstrated good performance However,large CPG queries can be slow,impacting the performance of STA applications e.g.,a CPG query of 1M paths takes 2.5 seconds,where STA applications typically issue thousands of CPG queries1P.-Y.Lee,I.H.-R.Jiang,C.-R.Li,W.

4、-L.Chiu and Y.-M.Yang,iTimerC 2.0:Fast incremental timing and CPPR analysis,2015 IEEE/ACM International Conference on Computer-Aided Design(ICCAD),Austin,TX,USA,2015,pp.890-894,doi:10.1109/ICCAD.2015.7372665.2C.Peddawad,A.Goel,Dheeraj B and N.Chandrachoodan,iitRACE:A memory efficient engine for fast

5、 incremental timing analysis and clock pessimism removal,2015 IEEE/ACM International Conference on Computer-Aided Design(ICCAD),Austin,TX,USA,2015,pp.903-909,doi:10.1109/ICCAD.2015.7372667.3T.-W.Huang,G.Guo,C.-X.Lin and M.D.F.Wong,OpenTimer v2:A New Parallel Incremental Timing Analysis Engine,in IEE

6、E Transactions on Computer-Aided Design of Integrated Circuits and Systems,vol.40,no.4,pp.776-789,April 2021,doi:10.1109/TCAD.2020.3007319.4Multi-threaded CPG Algorithms Existing GPU-parallel CPG algorithm(Guo et al.4)Substantial runtime speedup(50)GPU support requires significant investment and cod