Timing-Driven Octilinear Steiner Tree Construction Based on Steiner-Point Reassignment and Path Reconstruction

摘要

It is well known that the problem of constructing a timing-driven rectilinear Steiner tree for any signal net is important in performance-driven designs and has been extensively studied. Until now, many efficient approaches have been proposed for the construction of a timing-driven rectilinear Steiner tree. As technology process advances, +45° and -45° diagonal segments can be permitted in an octilinear routing model. To our knowledge, no approach is proposed to construct a timing-driven octilinear Steiner tree for any signal net. In this gaper, given a rectilinear Steiner tree for any signal net, we propose an efficient transformation-based approach to construct a timing-driven octilinear Steiner tree based on the computation of the octilinear distance and the concept of Steiner-point reassignment and path reconstruction in an octilinear routing model. The experimental results show that our proposed transformation-based approach can use reasonable CPU time to construct a TOST, and a 10%-18% improvement in timing delay and a 5%-14% improvement in total wire length in the original RSTs are obtained in the construction of TOSTs for the tested signal nets.