CktSteiner is a routing tool that uses a simulation heuristic to solve for the minimum wirelength by solving for a Rectilinear Steiner Minimum Tree (RSMT). CktSteiner simulates the global routing grid (GRG) as an RC network with routing terminals as input ports and Hanan nodes as output ports. A major advantage of CktSteiner is that the GRG only needs to be solved once for a given topology. The voltage response of the Hanan nodes of the network is then ordered by the time the response reaches its peak. Reasoning in Section 3.1 from [1] shows the faster a node reaches its peak time, the more likely that the Hanan node is added to the RSMT. Then Iterated 1-Steiner [ref] is used to solve for the RSMT using the user specified number of Hanan nodes to check. 1-Steiner individually adds a Hanan node one point at a time and adds the point to the RSMT if the wirelength decreases, however the entire tree needs to be reconstructed whenever a point is added. Iterated 1-Steiner removes this inefficiency by only updating the wirelength of the nearby nodes of the newly input Hanan node. Additionally, Hanan nodes on the periphery are skipped to reduce the runtime as described in Section 3.2 from [1].
Address comments and questions to Prof. Lei He
References
This paper is partially supported by NSF CAREER award CCR-0093273/0401682.