Obstacle-Avoiding X-Architecture Bounded-Skew Tree Algorithm Under Timing Slack Constraints
Genggeng Liu, Ren Lu, Yuhan Zhu, Zhifeng Lin, Chuandong Chen, Min Gan, Jianli Chen, Wenzhong Guo · IEEE Transactions on Systems Man and Cybernetics Systems · 2025
As interconnect delay increasingly becomes the primary source of chip delay, timing analysis in the very large-scale integration (VLSI) routing process is becoming more crucial. Concurrently, to maintain computational synchronization in the chip, the bounded-skew constraint must be introduced. Additionally, the issue of obstacle-avoiding has gained attention due to the presence of routing obstacles on the chip. Furthermore, the introduction of X-architecture enables more efficient utilization of routing resources. In this article, we propose an obstacle-avoiding X-architecture bounded-skew tree (BST) algorithm under timing slack constraints, which, for the first time, simultaneously considers timing slack, bounded-skew, obstacle-avoidance, and X-architecture in a unified framework. First, an effective preprocessing strategy is presented to support fast information retrieval for the subsequent strategies. Second, a BST construction strategy is developed to ensure compliance with skew constraints by consulting and updating a dedicated skew table. Third, a local worst negative slack (WNS) optimization strategy is designed to improve the WNS of critical paths by balancing wirelength (WL) and radius. Fourth, an obstacle-avoiding strategy is implemented to navigate around routing obstacles while minimizing unnecessary WL overhead. Finally, a path refinement strategy is designed to select routing structures with maximal edge sharing to replace the initial structure, thereby further optimizing WL. Experimental results demonstrate that the proposed algorithm significantly improves both WL and the key timing metric WNS, while satisfying obstacle-avoidance and bounded-skew constraints.