Research Assistant: H.-Y. Tu
The objective of circuit compaction is reducing the layout area by allowing modules and wires to slide horizontally or vertically without violating constraints imposed by technology and design. We investigate 1-dimensional circuit compaction when the layout area contains forbidden regions whose positions cannot be altered during the compactions process. Modules are not allowed to overlap with forbidden regions, but can "slide over" the forbidden regions. We also study circuit compaction when the wires are not rigid, but flexible components of the layout. Most conventional compaction algorithms minimizing the area contain unnecessarily long wires. Keeping the wires as short as possible is, next to minimizing the area, a crucial criterion in chip design. We have developed new approaches that have led to efficient algorithms for minimizing the total wire length, the longest wire length, and tradeoff functions between area and wire length.