HIMALAYAS - a hierarchical compaction system with a minimized constraint set

Abstract

A new hierarchical compactor, Himalayas (HIerarchical MAcro LAYout ASsembler), has been developed for constructing big macro layouts. The hierarchical compaction problem is formulated as an integer linear programming (ILP) problem. In this paper, we present two novel algorithms to reduce the problem size, in order to make 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, ILP method can be used to solve the compaction problem for very big macros. Experimental results for MCNC benchmark examples are also given.