Question

Difference between global routing and local routing

Answer 1

  Routing Routing Problem Routing Regions Types of Routing -Global Routing -Detailed Routing Conclusion References2. o The routing is to locate a set of wires in the routing space that connect all the nets in the net list. The capacities of channels, width of wires, and wire crossings often need to be taken into consideration .3.  Apply after placement Input:  Netlist  Timing budget for, typically, critical nets  Locations of blocks and locations of pins Output:  Geometric layouts of all nets Objective:  Minimize the total wire length, the number of vias, or just completing all connections without increasing the chip area.  Each net meets its timing budget.4.  For a multi-terminal net, we can construct a spanning tree to connect all the terminals together. But the wire length will be large. Better use Steiner Tree: Steiner A tree connecting all terminals and some Node additional nodes (Steiner nodes). Rectilinear Steiner Tree: Steiner tree in which all the edges run horizontally and vertically.5.  Minimum Steiner Tree Problem:  Given a net, find the steiner tree with the minimum length.  This problem is NP-Complete! May need to route tens of thousands of nets simultaneously without overlapping. Obstacles may exist in the routing region.6. Two phases:7. Divide the routing area into routing regions of simple shape(rectangular): Switchbox Channel• Channel: Pins on 2 opposite sides.• 2-D Switchbox: Pins on 4 sides.• 3-D Switchbox: Pins on all 6 sides.8. Gate-Array Standard-Cell Full-Custom Feedthrough Cell9. Routing Detailed Global routing routing Channel Switch BoxLine Routing Maze Routing Routing Routing10. Placement Global routingGenerate a loose route for each netAssign a list of routing region to each netwithout specifying the actual layout ofwires. Detailed routingFind the actual geometry layout of each net with in the assigned routing regions Compaction11. o Minimize the total overflowo Minimize the total wire lengtho Minimize running time12. Assign routing regions to each net. Need to consider timingbudget of nets and routing congestion of the regions.13. Assign pins on routing region boundaries for each net.(Prepare for the detailed routing stage for each region.)14. Sequential Approach:  Route the nets one at a time.  Order dependent on factors like criticality, estimated wire length, etc.  If further routing is impossible because some nets are blocked by nets routed earlier, apply Rip-up and Reroute technique.  This approach is much more popular.15. Concurrent Approach:  The major drawback of the sequential approach is that it suffers from the net ordering problem.  Consider all nets simultaneously.  Can be formulated as an integer program.