Lune

DAC2025Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. REST: Constructing Rectilinear Steiner Minimum Tree via Reinforcement LearningJinwei Liu, Gengjie Chen, Evangeline F. Y. YoungDAC 2021 · 29 citations
  2. DGR: Differentiable Global RouterWei Li, Rongjian Liang, Anthony Agnesina, Haoyu Yang et al.DAC 2024 · 15 citations

Related papers

  1. Toward Controllable Hierarchical Clock Tree Synthesis with Skew-Latency-Load TreeWeiguo Li, Zhipeng Huang, Bei Yu, Wenxing Zhu et al.DAC 2024 · 7 citations
  2. Time-Division Multiplexing Based System-Level FPGA Routing for Logic VerificationPeng Zou, Zhifeng Lin, Xiao Shi, Yingjie Wu et al.DAC 2020 · 18 citations
  3. 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
  4. TDP-ADMM: A Timing Driven Placement Approach for Superconductive Electronic Circuits Using Alternating Direction Method of MultipliersSoheil Nazar Shahsavani, Massoud PedramDAC 2020 · 8 citations
  5. Fast and Accurate Wire Timing Estimation on Tree and Non-Tree Net StructuresHsien-Han Cheng, Iris Hui-Ru Jiang, Oscar OuDAC 2020 · 35 citations
Dusk over the sea between two cliffs drawn in fine vertical lines