Wire segmenting for buffer insertion based on RSTP-MSP

This paper presents an approximation algorithm for simultaneously constructing a rectilinear Steiner tree and buffer insertion points into the tree. The objective of the algorithm is to divide each wire into multiple smaller segments and minimize the number of the buffer insertion points (Steiner points) which are only located at the end of each segment. We show that (a) the Steiner ratio is 1 3, that is, the rectilinear minimum spanning tree yields a polynomial-time approximation with a performance ratio exactly 3; (b) there exists a polynomial-time approximation with a performance ratio 2.

Authors

• Bing Lu
• Jun Gu
• Xiaodong Hu
• Eugene Shragowitz

Keywords

• VLSI
• Wire segment
• Buffer insertion
• Rectilinear Steiner tree
• Minimum spanning tree
• Approximation algorithm