Routing and Algorithms For VLSI design.pptx

Routing algorithms of VLSI Design

1. Routing and Algorithms By Prateek Tripathi VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

2. Basic Idea Global Routing: Global routes assign nets to particular metal layers and global routing cells . in an approximate manner. Detailed Routing: For detailed routing, the router decides the actual physical interconnections of nets by allocating wires on each metal layer and vias for switching between metal layers. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

3. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

4. Some points to remember Vertical and horizontal tracks are laid out on different layers The junctions are connected by a “via”. There can be multiple layers of tracks depending upon the complexity of the routing problem. As a conventional routing method we label the two or more pins with the same name to specify the program that a connection is to be form between them. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

5. Optimization goal of Global Routing Seeks to determine whether a given placement is routable Seeks to determine a coarse routing for all nets within available routing regions. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

6. Grid Graph Model Illustration VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

7. Channel connectivity graph VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig For horizontal channel, draw a line parallel to x-axis along the block edges which are parallel to x-axis, unless stopped by a block. 2. For vertical channel, draw a line parallel to y-axis along the block edges which are parallel to y-axis., unless stopped by a block.

8. Switch-box VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

9. Single net routing(rectilinear routing) then the tree is a rectilinear minimum spanning tree(RMST) VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

10. Further points The total edge length LRSMT of the RSMT is at least half the perimeter of the minimum bounding box of the net: LRSMT >= LMBB/2 VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

11. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

12. Hanan grid VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig For each points draw a lines perpendicular to y and x axis which passes through the points Mark all the intersections of those lines as Hannan points

13. A sequential steiner tree heuristic VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig T: Tree

14. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

15. Steps to global routing in connectivity graph 1. Define the routing regions 2. Define the connectivity graph 3. Determine the net order( can be prioritised based on no. of pins, criticality, size of bounding box ) 4. Assigning tracks for all pin connections( for each pin a horizontal and a vertical track are reserved ) 5. Global routing of all nets VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

16. Step 1 Step 2

17. Illustration of assigning capacities to the nodes VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

18. Final graph for previous slide VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

19. Now coming to global routing(step 5) VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

20. Soln.

21. Try yourself

22. Routing by Integer Linear Programming A linear program of a set of constraints and an optional objective function. Objective function is maximised or minimised Constraints and objective must be linear. Constraints form a system of linear equation and inequalities An ILP is a linear program where every variable assume integer value. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

23. Routing by Integer Linear Programming VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

24. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng , Jens Lienig

25. Horizontal Constraint Graph Draw all the horizontal Connections, each on a Single line

26. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

27. These graphs are used to detect conflict between routing paths and minimum number of routing paths VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

28. Vertical constraint graph VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

29. Vertical constraint graph VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

30. Vertical constraint graph VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng , Jens Lienig

31. CYCLE CONFLICT VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

32. Left edge algorithm VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

33. Left edge algorithm Soln. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng , Jens Lienig

34. Soln continued From horizontal constraint graph we figured out that we need at least 5 tracks VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

35. Final soln. VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

36. Dogleg algorithm VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

37. Dogleg Algorithm After splitting of the net, it follows the left edge algorithm Example: Solve the given figure with dogleg algorithm VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng , Jens Lienig

38. Solution VLSI Physical Design: From Graph Partitioning to Timing Closure; Andrew B. Kahng, Jens Lienig

39. END