Memory and I/O Optimized Rectilinear Steiner Minimum Tree Routing For VLSI

Memory and I/O Optimized Rectilinear Steiner Minimum Tree Routing For VLSI

Latha N R (B.M.S. College of Engineering, Bengaluru, India) and G R. Prasad (B.M.S. College of Engineering, Bengaluru, India)
DOI: 10.4018/IJECME.2020010104
OnDemand PDF Download:
No Current Special Offers


As the size of devices are scaling down at rapid pace, the interconnect delay play a major part in performance of IC chips. Therefore minimizing delay and wire length is the most desired objective. FLUTE (Fast Look-Up table) presented a fast and accurate RSMT (Rectilinear Steiner Minimum Tree) construction for both smaller and higher degree net. In this paper, FLUTE presented an optimization technique that reduces time complexity for RSMT construction for both smaller and larger degree nets. However for larger degree net this technique induces memory overhead, as it does not consider the memory requirement in constructing RSMT. Since availability of memory is very less and is expensive, it is desired to utilize memory more efficiently which in turn results in reducing I/O time (i.e. reduce the number of I/O disk access). The proposed work presents a Memory Optimized RSMT (MORSMT) construction in order to address the memory overhead for larger degree net. The depth-first search and divide and conquer approach is adopted to build a Memory optimized tree. Experiments are conducted to evaluate the performance of proposed approach over existing model for varied benchmarks in term of computation time, memory overhead and wire length. The experimental results show that the proposed model is scalable and efficient.
Article Preview

1. 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 ofIJECME.2020010104.m01. 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 ofIJECME.2020010104.m02. 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.

Complete Article List

Search this Journal:
Open Access Articles
Volume 11: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 10: 2 Issues (2021)
Volume 9: 2 Issues (2020)
Volume 8: 2 Issues (2019)
View Complete Journal Contents Listing