A graph-based simplex algorithm for minimizing the layout size and the delay on timing critical paths

The layout compaction problem with performance consideration is studied. In our approach, the delay upper-bound on the timing critical paths is reduced first, then the layout size is minimized without increasing that delay bound. Either step is formulated as a linear programming problem, and we propose a graph-based simplex algorithm, which replaces most of the matrix operations with graph operations, to solve the problem. Both theoretical analysis and experimental results show that this algorithm is quite efficient.