A tutorial on sticks compaction and assembly.

This paper reviews the work done in the past decade on one- dimensional sticks compaction - the automatic generation of compact, correct layouts from symbolic layouts. We concentrate on graph-based algorithms for compaction which model electrical connectivity and technology-dependent separation relations as directed graphs. We first discuss algorithms for compacting leaf cells, which contain only primitive components such as transistors. We then show how the algorithms used to compact leaf cells can be extended to the assembly of composite cells, which can include subcells as well as primitive components and wires. The resulting layouts are small and are guaranteed to satisfy the manufacturing design rules. Compaction is simplified because the design is specified in symbolic form, which contains information about the locations of components and electrical connectivity.