Obstacle aware delay optimized rectilinear steiner minimum tree routing

Shyamala G, G R Prasad


This work presents a method to solve the problem of constructing Rectilinear Steiner Minimum Tree (RSMT) for a group of pins in the presence of obstacles. In modern very large-scale integrated circuit (VLSI) designs, the obstacles, generally blocks the metal and the device layer. Therefore routing on top of blockage is a possible solution but buffers cannot be placed over the obstacle. Modern VLSI design OARSMT construction has long wire length, which results in signal violation. To address this issue a slew constraint interconnect need to be considered in routing over obstacle. This is called the Obstacle-Avoiding Rectilinear Steiner minimum trees (OARSMT) problem with slew constraints over obstacles. The drawback of traditional OARSMT is that they only consider slew constraint, and delay constraints are neglected. It induces high routing resources overhead due to buffer insertion and does not solve global routing solution. This work presents an Obstacle Aware Delay Optimized Rectilinear Steiner Minimum Tree (OADORSMT) Routing to address the delay, slew constraint and reduce the routing resources. Experiments are conduced to evaluate the performance of proposed approach over existing approach in term of wire length and worst negative slack. The experiments are conducted for small and large nets considering fixed and varied obstacles and outcome shows the proposed efficiency over existing approaches. The OADORSMT is designed in such a way where it can be parallelized to obtain better efficiency.


Obstacle-avoiding, Rectilinear Steiner tree, Slack and Slew constraint, VLSI

Full Text:


DOI: http://doi.org/10.11591/ijeecs.v16.i2.pp640-652


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

shopify stats IJEECS visitor statistics