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

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.