Patent ID: 7134102

Claim:
An automatic machine-implemented method of de-compacting a layout of a portion of an integrated circuit, comprising the steps of: (1) determining a critical path length (C) of the layout portion; (2) determining a minimum path length (MPL) for every path within the layout; (3) unlocking all branches of the layout; (4) determining any branches of the paths in the layout where the minimum path length (MPL) for that path is equal to the critical path length (C) and locking those branches of the layout; (5) determining whether any branches of the layout remain unlocked, if no branches remain unlocked then the method is complete; (6) determining which of the unlocked branches of the layout has the smallest actual spacing and designating that branch as the branch (K) for processing; (7) determining the width of the spacing between the neighbor branches on either side of branch (K); (8) determining whether the actual spacing of the branch (K) plus a predetermined incremental spacing amount is less than or equal to the larger of the spacing of that unlocked branch that is the predecessor branch and less than or equal to the spacing of the unlocked branch that is the successor branch, and if the spacing of the particular branch (K) plus the predetermined incremental spacing amount is not less than both the spacing of the predecessor branch and the spacing of the successor branch, locking the particular branch (K) and returning to the step (5); (9) determining whether the graph connectivity restrictions of the layout allow the spacing of the particular branch (K) to be increased by the predetermined incremental spacing, if the graph connectivity restrictions of the layout does not allow the spacing far the particular branch (K) to be increased, locking the particular branch and returning to the step (5); (10) increasing the spacing of the particular branch (K) by the predetermined incremental spacing amount; (11) updating the graph connectivity of the layout; and (12) returning to step (5).