Memory and I/O optimized rectilinear steiner minimum tree routing for VLSI

Abstract

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. 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 terms of computation time, memory overhead and wire length. The experimental results show that the proposed model is scalable and efficient.