---

[attachment=8483]

Rajesh Bathija, Mewar University

Physical Design Cycle
Partitioning
Floorplanning
Placement
Global & Detail Routing
Layout Compaction
Layout verification

Partitioning

Partitioning is the task of dividing a circuit into smaller parts . The objective is to partition the circuit into parts, so that the size of each component is within prescribed ranges and the number of connections between the components is minimized .
Different ways to partition correspond to different circuit implementations . Therefore, a good partitioning can significantly improve circuit performance and reduce layout costs .

Floorplanning

Floorplanning is the determination of the approximate location of each module in a rectangular chip area, given a circuit represented by a hypergraph the shape of each module and the location of the pins on the boundary of each module may also be determined in this phase . The floorplanning problem in chip layout is analogous to floorplanning in building design, where we have a set of rooms (modules) and wish to decide the approximate location of each room based on some proximity criteria . An important step in floorplanning is to decide the relative location of each module . A good floorplanning algorithm should achieve many goals, such as making the subsequent routing phase easy, minimizing the total chip area, and reducing signal delays .
Each module has a set of implementations, each of which has a different area, aspect ratio, delay, and power consumption, and the best implementation for each module should be obtained .

Placement

Placement, when each module is fixed, that is, has fixed shape and fixed terminals, is the determination of the best position for each module . Usually, some modules have fixed positions (e .g ., 1/O pads) . Although area is the major concern, it is hard to control it . Thus, alternative cost functions are employed . There are two prevalent cost functions : wire-length-based and cut-based.

Global routing

Global routing decomposes a large routing problem into small, manageable problems for detailed routing . The method first partitions the routing region into a collection of disjoint rectilinear subregions . This decomposition is carried out by finding a "rough" path (i .e., sequence of "subregions" it passes) for each net in order to reduce the chip size, shorten the wire length, and evenly distribute the congestion over the routing area .

Detailed routing

Detailed routing follows the global routing to effectively realize interconnections in VLSI circuits. The traditional model of detailed routing is the two-layer Manhattan model with reserved layers, where horizontal wires are routed on one layer and vertical wires are routed in the other layer. For integrated circuits, the horizontal segments are typically realized in metal while the vertical segments are realized in polysilicon . In order to interconnect a horizontal and vertical segment, a contact (via) must be placed at the intersection points . More recently, the unpreserved layer model has also been discussed, where vertical and horizontal wires can run in both layers .

Layout optimization & verification

Layout optimization is a post-processing step . In this stage the layout is optimized, for example, by compacting the area .
Layout verification is the testing of a layout to determine if it satisfies design and layout rules .

placement & routing problem

We shall refer to the problems related to location of modules (i .e ., partitioning, floorplanning, and placement) as the placement problem, and the problems related to interconnection of terminals (i .e ., global and detailed routing) as the routing problem . In addition, there are other post- processing problems, such as via and bend minimization,

Types of partitioning

The partitioning of a system into a group of PCBs is called the system level partitioning. The partitioning of a PCB into chips is called the board level partitioning while the partitioning of a chip into smaller subcircuits is called the chip level partitioning.
At each level, the constraints and objectives of the partitioning process are different as discussed below

System Level Partitioning

The circuit assigned to a PCB must satisfy certain constraints. Each PCB usually has a fixed area, and a fixed number of terminals to connect with other boards. The number of terminals available in one board (component) to connect to other boards (components) is called the terminal count of the board (component). For example, a typical board has dimensions 32 cm×15 cm and its terminal count is 64. Therefore, the subcircuit allocated to a board must be manufacturable within the dimensions of the board. In addition, the number of nets used to connect this board to the other boards must be within the terminal count of the board.

The reliability of the system is inversely proportional to the number of boards in the system. Hence, one of the objectives of partitioning is to minimize the number of boards. Another important objective is the optimization of the system performance. Partitioning must minimize any degradation of the performance caused by the delay due to the connections between components on different boards. The signal carried by a net that is cut by partitioning at this level has to travel from one board to another board through the system bus. The system bus is very slow as the bus has to adhere to some strict specifications so that a variety of different boards can share the same bus. The delay caused by signals traveling between PCBs (off-board delay) plays a major role in determining the system performance as this delay is much larger than the on-board or the on-chip delay.

Board Level Partitioning

The board level partitioning faces a different set of constraints and fulfills a different set of objectives as opposed to system level partitioning. Unlike boards, chips can have different sizes and can accommodate different number of terminals. Typically the dimensions of a chip range from 2 mm×2 mm to 25 mm×25 mm. The terminal count of a chip depends on the package of the chip. A Dual In-line Package (DIP) allows only 64 pins while a Pin Grid Array (PGA) package may allow as many as 300 pins. While system level partitioning is geared towards satisfying the area and the terminal constraints of each partition, board level partitioning ventures to minimize the area of each chip.

The shift of emphasis is attributable to the cost of manufacturing a chip that is proportional to its area. In addition, it is expedient that the number of chips used for each board be minimized for enhanced board reliability. Minimization of the number of chips is another important determinant of performance because the off-chip delay is much larger than the on-chip delay. This differential in delay arises because the distance between two adjacent transistors on a chip is a few while the distance between two adjacent chips is in mm. In addition to traversing a longer distance, the signal has to travel between chips, and through the connector. The connector used to attach the chip to the board typically has a high resistance and contributes significantly to the signal delay.

Chip Level Partitioning

The circuit assigned to a chip can be fabricated as a single unit, therefore, partitioning at this level is necessary. A chip can accommodate as many as three million or more transistors. The fundamental objective of chip level partitioning is to facilitate efficient design of the chip. After partitioning, each subcircuit, which is also called a block, can be designed independently using either full custom or standard cell design style. Since partitioning is not constrained by physical dimensions, there is no area constraint for any partition. However, the partitions may be restrained by user specified area constraints for optimization of the design process. The terminal count for a partition is given by the ratio of the perimeter of the partition to the terminal pitch. The minimum spacing between two adjacent terminals is called terminal pitch and is determined by the design rules. The number of nets which connect a partition to other partitions cannot be greater than the terminal count of the partition. In addition, the number of nets cut by partitioning should be minimized to simplify the routing task.

The minimization of the number of nets cut by partitioning is one of the most important objectives in partitioning. A disadvantage of the partitioning process is that it may degrade the performance of the final design. Thus, during partitioning, these critical components should be assigned to the same partition. If such an assignment is not possible, then appropriate timing constraints must be generated to keep the two critical components close together. Chip performance is determined by several components forming a critical path. Assignment of these components to different partitions extends the length of the critical path. Thus, a major challenge for improvement of system performance is minimization of the length of critical path. After a chip has been partitioned, each of the subcircuits has to be placed on a fixed plane and the nets between all the partitions have to be interconnected. The placement of the subcircuits is done by the placement algorithms and the nets are routed by using routing algorithms.

Objectives of Partition problem

At any level of partitioning, the input to the partitioning algorithm is a set of components and a netlist. The output is a set of subcircuits which when connected, function as the original circuit and terminals required for each subcircuit to connect it to the other subcircuits. In addition to maintaining the original functionality, partitioning process optimizes certain parameters subject to certain constraints. The constraints for the partitioning problem include area constraints and terminal constraints. The objective functions for a partitioning problem include the minimization of the number of nets that cross the partition boundaries, and the minimization of the maximum number of times a path crosses the partition boundaries. The constraints and the objective functions used in the partitioning problem vary depending upon the partitioning level and the design style used. The actual objective function and constraints chosen for the partitioning problem may also depend on the specific problem.

Parameter concern in partitioning

Interconnections between partitions: The number of interconnections at any level of partitioning have to be minimized. Reducing the interconnections not only reduces the delay but also reduces the interface between the partitions making it easier for independent design and fabrication. A large number of interconnections increase the design area as well as complicate the task of the placement and routing algorithms. Minimization of the number of interconnections between partitions is called the mincut problem. The minimization of the cut is a very important objective function for partitioning algorithms for any level or any style of design.
Delay due to partitioning: The partitioning of a circuit might cause a critical path to go in between partitions a number of times. As the delay between partitions is significantly larger than the delay within a partition, this is an important factor which has to be considered while partitioning high performance circuits. This is an objective function for partitioning algorithms for all levels of design.

Number of terminals: Partitioning algorithms at any level must partition the circuit so that the number of nets required to connect a subcircuit to other subcircuits does not exceed the terminal count of the subcircuit. In case of system level partitioning, this limit is decided by the maximum number of terminals available on a PCB connector which connects the PCB to the system bus. In case of board level partitioning, this limit is decided by the pin count of the package used for the chips. In case of chip level partitioning, the number of terminals of a subcircuit is determined by the perimeter of the area used by the subcircuit.

Area of each partition: In case of system level partitioning, the area of each partition (board) is fixed and hence this factor appears as a constraint for the system level partitioning problem. In case of board level partitioning, although it is important to reduce the area of each partition (chip) to a minimum to reduce the cost of fabrication, there is also an upper bound on the area of a chip, Hence, in this case also, the area appears as a constraint for the partitioning problem. At chip level, the size of each partition is not so important as long as the partitions are balanced.

Number of partitions: The number of partitions appears as a constraint in the partitioning problem at system level and board level partitioning. This prevents a system from having too many PCBs and a PCB from having too many chips. A large number of partitions may ease the design of individual partitions but they may also increase the cost of fabrication and the number of interconnections between the partitions. At the same time, if the number of partitions is small, the design of these partitions might still be too complex to be handled efficiently. At chip level, the number of partitions is determined, in part, by the capability of the placement algorithm. The constraint on the number of partitions can be stated as, Multiway partitioning is normally reduced to a series of two-way or bipartitioning problem. Each component is hierarchically bipartitioned until the desired number of components is achieved. In this chapter, we will restrict ourselves to bipartitioning. When the two partitions have the same size, the partitioning process is called bisectioning and the partitions are called bisections.

Partition for different design style

Full custom design style: In a full custom design style, partitions can be of different sizes and hence there are no area constraints for the partitioning algorithms. Thus, the partitioning in full custom design style has the most flexibility. During chip level partitioning, the number of terminals allowed for each partition is determined by the perimeter of the block corresponding to a partition. Since, the cost of manufacturing a circuit is directly proportional to the layout size, it is essential to keep the area of the layout to a minimum. The area of circuit layout is the sum of the areas occupied by components, areas used for routing the nets, and the unused areas. Since the areas occupied by the components are fixed, it is only possible to minimize the routing areas and unused areas. The routing area will be largely used by the nets that go across the boundaries of the blocks. The amount of unused areas will be determined by the placement. Therefore in addition to the terminal constraints, partitioning algorithms have to minimize the total number of nets that cross the partition boundaries.

Standard cell design style

The primary objective of the partitioning algorithms in standard cell design style is to partition the circuit into a set of disjoint subcircuits such that each subcircuit corresponds to a cell in a standard cell library. In addition, the partitioning procedure is nonhierarchical. The complexity of partitioning depends on the type of the standard cells available in the standard cell library. If the library has only a few simple cell types available, there are few options for the partitioning procedure and the partitioning problem has to satisfy constraints and However, if there are many cell types available, some of which are complex, then the partitioning problem is rather complicated. The objective function to be optimized by the partitioning algorithms for standard cell design is For high performance circuits, and are used as combined objective functions.

Gate array design style

The circuit is bipartitioned recursively until each resulting partition corresponds to a gate on the gate array. The objective for each bipartitioning is to minimize the number of nets that cross the partition boundaries.

Classification of Partitioning Algorithms

The mincut problem is NP-complete, it follows that general partitioning problem is also NP-complete [GJ79]. Partitioning algorithms can be classified in three ways. The first method of classification depends on availability of initial partitioning. There are two classes of partitioning algorithms under this classification scheme:
Constructive algorithms and
Iterative algorithms.
The input to a constructive algorithms is the circuit components and thenetlist. The output is a set of partitions and the new netlist. Constructive algorithms are typically used to form some initial partitions which can be improved by using other algorithms. In that sense, constructive algorithms are used as preprocessing algorithms for partitioning. They are usually fast, but the partitions generated by these algorithms may be far from optimal.
Iterative algorithms, on the other hand, accept a set of partitions and the netlist as input and generate an improved set of partitions with the modified netlist. These algorithms iterate continuously until the partitions cannot be improved further.

The partitioning algorithms can also be classified based on the nature of the algorithms. There are two types of algorithms:
Deterministic algorithms and
Probabilistic algorithms.
Deterministic algorithms produce repeatable or deterministic solutions. For example, an algorithm which makes use of deterministic functions, will always generate the same solution for a given problem.
On the other hand, the probabilistic algorithms are capable of producing a different solution for the same problem each time they are used, as they make use of some random functions.

The partitioning algorithms can also be classified on the basis of the process used for partitioning. Thus we have the following categories:
Group Migration algorithms,
Simulated Annealing and Evolution based algorithms and
Other partitioning algorithms.

Process Used For Partitioning Algorithm

The group migration algorithms [FM82, KL70] start with some partitions, usually generated randomly, and then move components between partitions to improve the partitioning. The group migration algorithms are quite efficient. However, the number of partitions has to be specified which is usually not known when the partitioning process starts. In addition, the partitioning of an entire system is a multi-level operation and the evaluation of the partitions obtained by the partitioning depends on the final integration of partitions at all levels, from the basic subcircuits to the whole system. An algorithm used to find a minimum cut at one level may sacrifice the quality of cuts for the following levels. The group migration method is a deterministic method which is often trapped at a local optimum and can not proceed further.
The simulated annealing/evolution algorithms carry out the partitioning process by using a cost function, which classifies any feasible solution, and a set of moves, which allows movement from solution to solution. Unlike deterministic algorithms, these algorithms accept moves which may adversely effect the solution. The algorithm starts with a random solution and as it progresses, the proportion of adverse moves decreases.These degenerate moves act as a safeguard against entrapment in local minima. These algorithms are computationally intensive as compared to group migration and other methods. Among all the partitioning algorithms, the group migration and simulated annealing or evolution have been the most successful heuristics for partitioning problems. The use of both these types of algorithms is ubiquitous and extensive research has been carried out on them.

---