Improved Compaction by Minimized Length of Wires

The compaction of IC or hybrid layouts by means of the "longest path" method yields a slack in the placement of part of the elements, which, in its turn, can be used to reduce the overall wire-length. The result is an improved electrical performance and a smaller layout. The optimization problem was transformed to a graph-theoretical problem in a way similar to the compaction problem itself. Our procedure starts by adding pieces of information out of the connectivity of the layout to the constraint graph. The succeeding heuristic algorithms generate a new tree of longest paths, taking the linear inequalities and the result of the longest path calculation into consideration. A few examples demonstrate the significant reduction of wire-length and sometimes even an additional reduction of layout area achieved with low computational effort.