Title :
An exact algorithm for single-layer wire length minimization
Author :
Ho, J.-M. ; Suzuki, A. ; Sarrafzadeh, M.
Author_Institution :
Northwestern Univ., Evanston, IL, USA
fDate :
1/1/1993 12:00:00 AM
Abstract :
An arbitrary single-layer detailed routine L of a set of two-terminal nets is considered. The necessary and sufficient condition for a layout to have minimum length under homotopic transformations (i.e. without changing the given global routing) is presented. Based on the proposed classification and the motion of line-segment visibility, an exact algorithm that minimizes the total wire length of L is given. The proposed algorithm runs in O(n2) time, where n is the number of bends in L
Keywords :
circuit layout CAD; minimisation; homotopic transformations; line-segment visibility; single-layer detailed routine; total wire length; two-terminal nets; wire length minimization; Computational modeling; Computer science; Euclidean distance; Minimization methods; Neural networks; Notice of Violation; Polynomials; Routing; Simulated annealing; Wire;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
