PatLabor: Pareto Optimization of Timing-Driven Routing Trees
Zhiyang Chen, Hailong Yao, Xia Yin
Abstract
Wirelength is the fundamental metric for VLSI routing. With the advancement of new technologies, wire delay has also become a significant factor for timing performances. It is thus necessary to consider both wirelength and delay in routing tree construction, i.e., timing-driven routing trees. Prior methods propose various heuristics to balance wirelength and delay with a tunable parameter, which cannot compute the full Pareto frontier. In this work, we propose PatLabor, a practical method for timing-driven routing. PatLabor directly optimizes the Pareto set, which obtains tighter Pareto curves than prior methods and does not require parameter tuning. PatLabor obtains all Paretooptimal solutions on small-degree nets up to 9 pins and is theoretically guaranteed by provable time complexity and approximation bounds. Experimental results verify our theoretical findings and show that PatLabor obtains tighter Pareto curves than state-of-the-art methods on ICCAD-15 benchmarks. For example, PatLabor obtains up to 58.5% more Pareto-optimal solutions than prior methods for degree-9 nets.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Toward Controllable Hierarchical Clock Tree Synthesis with Skew-Latency-Load TreeWeiguo Li, Zhipeng Huang, Bei Yu, Wenxing Zhu et al.DAC 2024 · 7 citations
- Time-Division Multiplexing Based System-Level FPGA Routing for Logic VerificationPeng Zou, Zhifeng Lin, Xiao Shi, Yingjie Wu et al.DAC 2020 · 18 citations
- Routing Topology and Time-Division Multiplexing Co-Optimization for Multi-FPGA SystemsTung-Wei Lin, Wei-Chen Tai, Yu-Cheng Lin, Iris Hui-Ru JiangDAC 2020 · 12 citations
- TDP-ADMM: A Timing Driven Placement Approach for Superconductive Electronic Circuits Using Alternating Direction Method of MultipliersSoheil Nazar Shahsavani, Massoud PedramDAC 2020 · 8 citations
- Fast and Accurate Wire Timing Estimation on Tree and Non-Tree Net StructuresHsien-Han Cheng, Iris Hui-Ru Jiang, Oscar OuDAC 2020 · 35 citations
