SSTT: Efficient Local Search for GSI Global Routing

In this paper, a novel global routingalgorithm is presented for congestion optimization based on efficientlocal search, named SSTT (search space traversing technology). Thismethod manages to traverse the whole search space. A hybrid optimizationstrategy is adopted, consisting of three optimization sub-strategies:stochastic optimization, deterministic optimization and localenumeration optimization, to dynamically reconstruct the problemstructure. Thus, "transition" can be made from a local minimum point toreach other parts of thesearch space, traverse the whole search space, and obtain the global(approximate) optimal routing solution. Since any arbitrary initialrouting solution can be used as the start point of the search, theinitialization in SSTT algorithm is greatly simplified. SSTTalgorithm has been tested on both MCNC benchmark circuits and industrialcircuits, and the experimental results were compared with those oftypical existing algorithms. The experimental results show that SSTTalgorithm can obtain the global (approximate) optimal routing solutioneasily and quickly. Moreover, it can meet the needs of practicalapplications. The SSTT global routing algorithm gives a general-purposerouting solution.