A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems

This technical report is prepared to record the preliminary work carried out in beginning a research project on the solution of a group of related problems by means of Genetic Algorithms (GA's). These problems include integrated circuit layout compaction, bin packing, and nesting. The principal problem is compaction, with the others serving to illuminate and guide the compaction work, as well as possibly receiving benefits from new tools developed. Efficient and near-optimal solution of the compaction problem will enhance the linkage between symbolic level modeling of the layout and the mask level design of hierarchical (fragment-based), ultra-fast, lowpower analog and logic circuits. The research goals are to develop new methodologies, abstractions, and theory that lead to more efficiently defined and utilized Computer-Aided Design (CAD) algorithms and tools for compaction, bin packing and nesting. These new methodologies will incorporate important improvements in the handling of the physical, technological, and optimization aspects of compaction. More effective solution of the bin packing and nesting problems can help to solve the compaction problem, as well as being valuable in their own right for many practical problems. This will be accomplished by defining a new approach to the use of Genetic Algorithms (GAs)--for the compaction, bin packing, and nesting problems. The research will concentrate mostly on the application area of high-speed, low-power analog and digital circuits with clock rates up to 20 GHz. In many applications in this high performance area, dramatically reduced chip area and signal delays are important design requirements. The technology area of interest is multi-chip modules (MCM) based on current or advanced silicon and GaAs technologies [1]. Th..