Compaction with incremental over-constraint resolution

Abstract

The occurrence and resolution of over-constraints in one-dimensional layout compaction will be discussed. A new algorithm is given which solves the longest path problem in the constraint graph and resolves all positive cycles either by constraint relaxation or by jog generation. The presented algorithm eliminates the positive cycles one at a time and reuses the intermediate results, which had been obtained up to the point when the cycle was detected. Thus, the amount of additional effort required for the over-constraint resolution is very low. Some typical over-constrained situations and their solutions are shown. The algorithm has been implemented in a mask compaction program that is currently in use for process migration and design rule error correction at SIEMENS. CPU-times gained during the process migration of a microcontroller layout are given.