Article Preview
Top1. Introduction
Rectilinear Steiner Minimal Tree (RSMT) is composed of small set of connected pins through Steiner nodes with minimal cumulative edge size in Manhattan distance for a given set of pins. The construction of RSMT is a major issue in designing Very Large Scale Integration (VLSI) such as interconnects design, placement and floor planning. It has been adopted in computing transmission delay, interconnect delay and in workload computation. It is also adopted in some global routing strategies to build a routing topography of all nets.
The construction of RSMT for VLSI is considered a Non-deterministic polynomial problem (Garey & Johnson, 1979), as a result rectilinear minimum spanning tree (RMST) has been adopted in some earlier design by exploring space dimensional design. RMST construction requires fast tree computing strategy and since the RMST does not allow Steiner nodes in tree construction the resulting RMST length is longer than that of RSMT. In (Hwang, 1976) showed that RMST is one and half times greater than that of RSMT with less than 50% in terms of accuracy, which is tolerable in earlier design. However, the later design requires good wire length accuracy for which the construction of RSMT is required. In (Hwang et al., 1992) presented a wide range characteristic of RSMT construction. In (Warme et al., 2000) and (Geosteiner, n.d.) presented an optimal strategy for RSMT construction, which is said to have least computation time. In (Mandoiu et al., 1999) presented a near optimal solution for RSMT construction. However, they are computationally very heavy and are not suitable for applications, specifically for VLSI design.
Many approaches have been presented to reduce time complexity in constructing RSMT. In (Zhou, 2003) adopted spanning graph (Zhou et al., 2002) to aid in building the primary set of spanning tree and obtain finest sets for the edge-which are computed iteratively to eliminate longest edge. In (Kahng et al., 2003) presented a greedy batched technique, which improved efficiency and reduced the computation time. The Single Trunk Steiner Tree (STST) is built to connect a set of pins to individual trunks, which traverse vertically or horizontally through set of all pins, but is not efficient for medium size pins. In (Chen et al., 2002) presented refined single-trunk tree for degree up to 5 nets and it is optimally accurate for medium degree nets with fair run time complexity.
In (Chu, 2004) and (Chu and Wong, 2005) presented Lookup table based fast and accurate optimal solution for RSMT construction namely FLUTE. In this technique, the nets are recursively broken into sub set of nets. FLUTE is evaluated for low degree nets and it is suitable for VLSI design. FLUTE is also efficient for high degree nets with runtime complexity of
. However, for higher degree nets the accuracy of RSMT construction is severely affected. This is due to the error induced during net breaking technique. To address this issue in (Wong et al., 2008) presented a scalable net partitioning technique, where the nets are broken into smaller subset of nets and again merged by adding Steiner nodes. This technique could handle both smaller and larger degree nets with slight reduction in accuracy but it induced a runtime complexity of
. In (Chu et al., 2008) presented a fast lookup table based RSMT construction, which brings a good tradeoff between accuracy and the runtime complexity. Both (Wong et al., 2008) and (Chu et al., 2008) did not consider the memory constraint in building a Look up table. The future VLSI design consists of fixed blocks such as IP blocks, macros, and so on and FLUTE is adopted by these researchers (Zhanga et al., 2016) and (Saha et al., 2013). In such design minimizing wire, length and reducing memory overhead is most desired. To address these issues the proposed work presents a Memory optimized RSMT construction that reduces wire length and computational overhead complexities.