Optimum Standard Cell Layout Using Weighted Cycle Linear Placement

Introduction

Placement and routing problems for integrated circuits are inherently interrelated and extremely complex from the algorithmic point of view. This complexity grows exponentially as the scale of integration increases. To cope with their complexity within fully automated design methodologies, a common approach is to restrict the design framework both in terms of the structure of the target circuit and design algorithms.

A widely used approach is standard cell design (Fig. 1), in which almost all layout cells are of the same height, so it is convenient to arrange them in rows. If there some cells can be grouped in such a way that interconnects between the groups may be ignored or accounted for in some hierarchical way, then a locally-optimal placement of cells within each group may be approximated by the model of linear placement as shown in Figure 2. The quality of placement is estimated by some measure of interconnectivity provided that all wires run horizontally.