Page 548 - DSP Integrated Circuits

12.2 Layout of VLSI Circuits 533

Constraints on the estimated area and aspect ratio of the chip
Constraints on the aspect ratios of the modules
Constraints on the positions of the pins
A net list specifying which pins have to be interconnected
Constraints on power dissipation and maximum temperature
Estimated delay per unit length of interconnection
Constraints on delays at the chip level

The algorithms needed for solving this problem are NP-complete. Computa-
tion time therefore increases exponentially with the number of modules. This
forces us to revert to heuristic methods. In practice heuristic or statistical algo-
rithms may be efficiently combined with hints and guidance by the designer.
Ultimately, the goal is to automatically generate a good floor plan, do the
placement, as well as automatically route the wires. The placement problem is
defined as the problem of determining the locations of all modules so that all the
constraints, given shortly, are satisfied and so that a weighted sum of the total
area, net length, delay, and power dissipation is minimized.
The placement constraints are
A set of modules with fixed geometry, pin positions, delays, and power
consumption
Constraints on the positions of some of the modules
Constraints on area and on the aspect ratio of the chip
A net list specifying which pins have to be interconnected
Constraints on the power dissipation and maximum temperature
Estimated delay per unit length of interconnection
Constraints on delays at the chip level

12.2.2 Floor Plans
The problem of determining the optimal positions of the modules so that the total
area of the chip is minimized, is an NP-complete problem. Of similar complexity is
the problem of determining the aspect ratios of the modules such as the ones
involved in the floor planning phase. However, there are some constrained place-
ments that yield a simple and elegant algorithm to determine the optimal area
and corresponding orientations and aspect ratios of the components: the so-called
slicing structures. It is useful to classify floor planning and placement algorithms
according to the structure of the layout generated by the algorithm—i.e., slicing
structures or unconstrained placement. In order to simplify the problem, the mod-
ules are often assumed to have rectangular shapes. The area of all modules is fixed
while the dimensions of some of the modules may be either fixed or flexible within
a range of possible aspect ratios. Some of the modules may have fixed positions
and orientations.
A floor plan is a slicing floor plan if it only contains a single rectangle or if
there exists a vertical or a horizontal cut that divides the slicing structure into two
parts, each of which is a slicing floor plan. A slicing floor plan can be recursively
partitioned by repeated use of the following rule:

Cutting a rectangle is defined as dividing it into two rectangles by either a
horizontal or a vertical line.