HIMALAYAS-A hierarchical compaction system with a minimized constraint set

A hierarchical compactor, HIMALAYAS (HIerarchical MAcro LAYout ASsembler), developed for constructing big macro layouts, is discussed. The hierarchical compaction problem is formulated as an integer linear programming (ILP) problem. Two algorithms are presented to reduce the problem size, in order to make the ILP approach practical. The first algorithm reduces the number of variables to a small set of pitch variables, while the second algorithm reduces the number of equations by restricting the constraint generation within a small set of regions, called the minimum cover. These reductions bring in considerable saving in computation time for layouts with cell repetitions or cell alignments. As a result, the ILP method can be used to solve the compaction problem for very big macros. Experimental results for MCNC benchmark examples are also given.<>