A Steiner Tree Algorithm in Unequal Grid of Maero Cell Gate Array

This paper studies the problem of Steiner tree algorithm in unequal grid of macro cell gate array, with the aim of speeding up the converge time and reducing complexity so as to obtain short length of Steiner tree. In this algorithm we improve the method of obtaining converge point and propose the concept of converge direction. Every special node goes torwards its converge point independently according to its converge direction. A Steiner tree is obrained through several merge and adjustment. This algorithm has been implemented in C on SUN4 work station and is utilized in double layer gate array of national 3 ICCAD system. The results shows this algorithm has lower complexity and the-length of Steiner tree is satisfactory.