PLACEMENT

Placement is the process of arranging a set of modules on the layout surface.Each module has fixed shape and fixed terminal locations. A subset of modules may have pre-assigned positions(e.g.,I/O pads,which are located adjacent to the external pins).Depending on the placement wire length might increase so one of the main objectives of placement is to reduce the overall wire length.A good placement can lead to much neater network much shorter wire lengths.

Inputs:

• A set of modules with well-defined shapes,and fixed pin locations
• A netlist

Requirements:

• Find locations for each module so that no two modules overlap
• The placement is routable

Objective:

• Minimize layout area
• Reduce length of critical nets
• Completion of routing

Placement Problem at Different levels

1. System-Level : Place all the PCBs together such that area occupied is minimum,heat dissipation is within limits
2. Board-level : All the chips have to be placed on a PCB, are fixed and all modules of rectangular shape.The objective here is to minimize the number of routing layers(there will be multiple layers on which metal layers are running to compute the routing, so less the number of layers less will be the cost of PCB, more will be reliability), meet system performance requirements.
3. Chip-Level : Normally floorplanning/placement carried out along with pin assignment. Limited number of routing layer(2-4),bad placement may be unroutable and can be detected only later, costly delays in design cycle.Minimization of area.

The Problem:

Find rectangular regions R={R1,R2,...} for each of the blocks such that

-Block Bi can be placed in region Ri

-No two rectangles overlap

-Placement is routable

-Total area of rectangle bounding R and Q is minimized

-Total wire length Li is minized

-For high performance circuits, max {Li | i=1,2,...} is minimized

Interconnection Toplogies

The actual wiring paths are not visible during placement. For making an estimation, a placement algorithm needs to be model the topology of the interconnection nets, for this an interconnection graph structure is used,vertices are terminals and edges are interconnections.Estimation of wire length is important.

Estimation of wirelength

The speed and quality of estimation has a drastic effect on the performance of placement algorithm.For two terminal nets, we can use Manhattan distance as an estimate.If the end co-ordinates are (x1,y1) and (x2,y2), the wire length ,

L = |x1-x2| + |y1-y2|

How to estimate length of multi-terminal nets?

1. Complete Graph:

- nC2=n(n-1)/2 edges for n-pin set, so 4x3/2

-A tree has (n-1) edges which is 2/n times the number of edges of the complete graph

-Length is estimated as 2/n times the sum of the edge

1. Minimum Spanning Tree:

-Commonly used structure

-Branching allowed only at pin locations

-Easy to compute

1. Rectangular Steiner Tree:

-A steiner tree is the shortest route for connecting a set of pins

-A wire can branch from any point along its length

-Problem of finding steiner tree is NP-complte

1. Semi Perimeter:

-Efficient and most widely used

-Finds the smallest bounding rectangle that encloses all the pins to be connected

-Estimated wire length is half the perimeter of this rectangle

-Always underestimates the wire length for congested nets

#vlsi#semiconductor#backend#pd#physicaldesign#placement