Many design styles used for automatic cell generation need a linear placement of their components. The authors present a novel two-phase algorithm for that task. In a first step, the net length is globally minimized by quadratic programming with an iterative weight update. Its results are as good as a minimization of the net length by linear programming but are obtained by significantly shorter CPU times. In a second step, track count, net length, and possibility of abutment between components are optimized simultaneously by means of a branch and bound algorithm applied to local subproblems. A comparison to previously published algorithms shows that the results of the proposed algorithm are superior.>

A novel approach to the automatic layout synthesis of dynamic CMOS circuits is presented. A set of logic expressions is realized in a row of cells. Taking multi-level Boolean expressions as input, logic transistors are placed and routed. Efficient solutions are achieved by permuting the variables of the expressions and by row folding. The layout is designed on a coarse grid taking timing requirements into account and afterwards adapted to the geometric design rules by a compactor. A comparison to handcrafted layouts shows that the results of PALACE are nearly equivalent. At the same time the design productivity is increased significantly.

A point-to-point routing algorithm with three new features is presented. First, the router makes optimal use of oversized, rectangular contacts. Second, it allows different wire width on different layers, with the layers having complete freedom as to routing direction. These two features make the algorithm attractive for MOS layout applications. Finally it is able to realize all-angle routing and to accept all-angle obstacles, a feature interesting for hybrid and PCB routing. The router is gridless and guarantees a solution if one exists. Since it is based on computational geometry algorithms, it offers a low run-time complexity. The ideas have been implemented in a prototype version for 45° routing. The results indicate that the router performs well, even on large designs.

This paper describes a plowing procedure which moves and modifies cells and routing. The plow pushes aside all obstacles one by one, thus penetrating into the layout. The process leads to a compaction at the front side of the plow. The compaction is performed in accordance with the minimum spacing rules and with automatic jog insertion. Objects of the layout representation are cells, contacts, and wires. A wire is represented by a path of segments which lie in one of two layers, at angles of multiples of 45°. The generated blank space is used for adding new objects or resizing geometries.