An efficient algorithm for layout compaction problem with symmetry constraints

An efficient algorithm is presented for the symbolic layout compaction problem with symmetry constraints. The symmetry constraint maintains the geometric symmetry of the circuit components during the layout compaction. It is indispensable to the symbolic layout for analog LSIs where the geometric symmetry between the components is important. However, it makes the compaction problem so complicated that no efficient algorithm has ever been shown except for the time-consuming linear programming algorithm. The proposed algorithm uses both the graph-based technique and the linear programming technique, and takes advantage of the high speed of the former and the generality of the latter. The authors implemented the proposed algorithm in a layout compaction program. The experimental results show that the proposed algorithm is fast enough for practical use.<>