(Publisher of Peer Reviewed Open Access Journals)

International Journal of Advanced Technology and Engineering Exploration (IJATEE)

ISSN (Print):2394-5443    ISSN (Online):2394-7454
Volume-5 Issue-42 May-2018
Full-Text PDF
DOI:10.19101/IJATEE.2018.542006
Paper Title : Implementation of VLSI interconnect design
Author Name : D.Sathyanarayanan and M.Mohamed
Abstract :

One of the key problems in VLSI interconnect design is the topology construction of signal nets with the minimum cost. The Steiner tree problem is to find the tree structure which connects all pins of the signal net such that the wire length (i.e., cost) can be minimized. If all edges of the tree are restricted to the horizontal and vertical directions as are the case in VLSI design, the problem is called rectilinear Steiner tree (RST).The problem of optimizing interconnections between microelectronic devices is an evolving area under VLSI architectures. Steiner tree is a fundamental problem in the automatic inter-connects optimization for VLSI design. Existing methodologies using a Steiner tree approach are not optimal in terms of path length.

Keywords : Rectilinear, Steiner, Graph, Topology and VLSI.
Cite this article : D.Sathyanarayanan and M.Mohamed, " Implementation of VLSI interconnect design " , International Journal of Advanced Technology and Engineering Exploration (IJATEE), Volume-5, Issue-42, May-2018 ,pp.96-98.DOI:10.19101/IJATEE.2018.542006
References :
[1]Hwang FK. An O (n log n) algorithm for rectilinear minimal spanning trees. Journal of the ACM. 1979; 26(2):177-82.
[Crossref] [Google Scholar]
[2]Hanan M. On Steiner s problem with rectilinear distance. SIAM Journal on Applied Mathematics. 1966; 14(2):255-65.
[Crossref] [Google Scholar]
[3]Mandoiu II, Vazirani VV, Ganley JL. A new heuristic for rectilinear Steiner trees. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2000; 19(10):1129-39.
[Crossref] [Google Scholar]
[4]Hwang FK. On Steiner minimal trees with rectilinear distance. SIAM Journal on Applied Mathematics. 1976; 30(1):104-14.
[Crossref] [Google Scholar]
[5]Hwang FK, Richards DS. Steiner tree problems. Networks. 1992; 22(1):55-89.
[Crossref] [Google Scholar]
[6]Tang Y, Yang W, Guo T. Definition and algorithms for reliable Steiner tree problem. Journal of Systems Science and Complexity. 2015; 28(4):876-86.
[Crossref] [Google Scholar]
[7]Cong J, He L, Koh CK, Madden PH. Performance optimization of VLSI interconnect layout. Integration, the VLSI Journal. 1996; 21(1-2):1-94.
[Crossref] [Google Scholar]
[8]Bienkowski M, Kraska A, Schmidt P. A deterministic algorithm for online Steiner tree leasing. In workshop on algorithms and data structures 2017 (pp. 169-80). Springer, Cham.
[Crossref] [Google Scholar]
[9]Gologranc T. Graphs with 4-Steiner convex balls. Taiwanese Journal of Mathematics. 2015; 19(5):1325-40.
[Crossref] [Google Scholar]