Placement in VLSI Design

1. PLACEMENT IN PHYSICAL DESIGN Pragya M.Tech - VLSI 13VLP008

2. AGENDA B ack end process What is placement and its types Placement problem formulation Algorithms Simulated based placement Partitioning based placement

3. BACK END PROCESS Placement in physical design 3

4. Partitioning Goal: partition of a system into number of ASIC’s(application specific integrated chip) Objective: minimise the number of external connections between each ASIC. Keep each ASIC smaller than max size . 2. Floorplanning Goal: calculate the size of blocks and assign them locations. Objective: keep highly connected blocks physically close to each other . 3. Placement Goal: assign the interconnect areas and the locations of all the logic cells within the flexible block Objective: minimise the ASIC area and the interconnects

5. 4. Global routing Goal: determine the location of all the interconnects Objective: minimise the total interconnect area . 5. Detailed routing Goal: completely route all the interconnects on the chip Objective: minimise the total interconnect length used. Placement in physical design 5

6. PLACEMENT AND ITS TYPES Placement in physical design 6

7. Placement is the problem of automatically assigning correct positions to predesigned cells on the chip with no overlapping such that some objective function is optimized. Placement is design state after logic synthesis and before routing.

8. Types of placement 1. Standard cell placement –Standard cells have been designed in such a way that power and clock connections run horizontally through the cell and other I/O leaves the cell from the top or bottom sides.

9. 2. Building block placement Cells to be placed have arbitrary shape.

10. Placement is done in three steps: Global placement generate a rough placement that may violate some placement constraints (e.g., there may be overlaps among modules) Legalization makes the rough solution from global placement legal (no placement constraint violation) by moving modules around locally. Detailed placement further improves the legalized placement solution in an iterative manner by rearranging a small group of modules in a local region while keeping all other modules fixed. Placement in physical design 10

11. Out of the three steps important one is global placement Approaches for global placement are : Partitioning based approach (min cut partitioning) Simulated annealing approach Analytical approach (best) Placement in physical design 11

12. PLACEMENT PROBLEM FORMULATION Placement in physical design 12

13. Input: Placement region, a set of modules, and a set of nets. The widths and heights of the placement region and all modules are given. The locations of I/O pins on the placement region and on all modules are fixed. Output: A set of location on the chip : one location for each cell. Placement in physical design 13

14. Placement in physical design 14 Objective: minimize the ASIC area and the interconnects Goal: Arrange all the logic cells within flexible blocks The cells are placed to produce a routable chip that meets timing and other constraints (e.g., low-power, noise, etc.) Challenge: The number of cells in a design is very large (> 1 million).

15. The placement problems for common design styles are: Standard cell placement Gate array/FPGA placement Macro block placement Mixed size placement. all about placement.pdf Placement in physical design 15

16. Global and Detailed Placement In global placement , the approximate locations for cells is decided by placing cells in global bins. In detailed placement, cells are Placed without over lapping.

17. Good and bad placement Good placement Bad placement Minimize area (total wiring area) Ensure routability Avoid signal interference Distribute heat Maximize performance Consumes large areas Results in performance degradation Results in difficult and sometimes impossible tasks (Routing) An ill-placed layout cannot be improved by high quality routing. Placement in physical design 17

18. Placement in physical design 18

19. PLACEMENT ALGORITHMS Placement in physical design 19

20. Optimisation of the following is done using placement algorithm Total area Total wirelength Heuristics are used in the algorithms.

21. Constructive once the position of the cell is fixed , it can not be modified Constructive algorithms are used to obtain an initial placement. Iterative intermediate placements are modified in an attempt to improve the cost function. The initial placement is followed by an iterative improvement phase. Placement in physical design 21

22. Techniques for initial placement A top-down method : min-cut partitioning and placement (bisect the circuit recursively) Min-Cut Placement method 1. Cut placement area into two pieces 2. Swap logic cells to minimize cut cost 3.Repeat process from step 1, cutting smaller pieces until all logic cells are placed

23. Placement in physical design 23

24. A bottom-up method: cluster growth (select cells with strongest connections one by one)

25. Simulated Annealing Placement Initial placement improved through swaps and moves Accept a swap/move if it improves the cost

26. Pros and cons of SA Pros: Can Reach Globally Optimal Solution (given “enough” time) Can Optimize Simultaneously all Aspects of Physical Design Can be Used as a End Case Placement Cons Extremely slow process of reaching a good solution.

27. Placement in physical design 27 Thank you