Random methods for rectilinear steiner tree problem with applications in VLSI design

DSpace/Manakin Repository

Random methods for rectilinear steiner tree problem with applications in VLSI design

Show full item record


Title: Random methods for rectilinear steiner tree problem with applications in VLSI design
Author: Randhawa, Reet Singh
Abstract: The design of VLSI chips involves many phases which can be automated using CAD software. One of these phases is to determine optimal routes for global routing, inter-connecting nodes on the chip. This problem can be represented as the shortest rectilinear Steiner spanning tree (SRSST) problem. To solve this problem two random methods. Simulated Annealing (SA) and Stochastic Evolution (SE) were investigated and implemented using an object oriented design. Both Simulated Annealing and Stochastic Evolution are tunable algorithms and their performance is highly dependent on the particular problem being solved. Two programs were implemented for each algorithm: both original algorithms and both algorithms with some modifications. The modified algorithms were less sensitive to specifics of the problems and thus required less tuning and worked well for most problems. Using these algorithms we were able to obtain solutions for SRSST problems containing up to 100 vertices. The modified SE gave the best results, followed by the modified SA.
URI: http://hdl.handle.net/2346/14819
Date: 1995-05

Files in this item

Files Size Format View
31295009253187.pdf 2.155Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Browse

My Account