ECE 260B – CSE 241A /UCB EECS 244 1 Andrew B. Kahng, UCSDRouting in Integrated CircuitsA. KahngK. KeutzerA. R. NewtonECE 260B – CSE 241A /UCB EECS 244 2 Andrew B. Kahng, UCSDRTL Design FlowRTLSynthesisHDLnetlistlogicoptimizationnetlistLibraryphysicaldesignlayoutabsq01dclkabsq01dclkModuleGeneratorsManualDesignCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 3 Andrew B. Kahng, UCSDPhysical Design FlowRead NetlistInitial PlacementPlacementImprovementCost EstimationRouting RegionDefinitionGlobal RoutingInputPlacementRoutingOutputCompaction/clean-upRouting RegionOrderingDetailed RoutingCost EstimationRoutingImprovementWrite Layout DatabaseFloorplanningFloorplanningCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 4 Andrew B. Kahng, UCSDRouting ApplicationsBlock-basedBlock-basedMixedCell and BlockMixedCell and BlockCell-basedCell-basedECE 260B – CSE 241A /UCB EECS 244 5 Andrew B. Kahng, UCSDRouting Algorithms Global routingz Guide the detailed router in large designz May perform quick initial detail routingz Commonly used in cell-based design, chip assembly, and datapath designz Also used in floorplanning and placement Detail routingz Connect all pins in each netz Must understand most or all design rulesz May use a compactor to optimize resultz Necessary in all applicationsCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 6 Andrew B. Kahng, UCSDBasic Rules of Routing - 1Photo courtesy:Jan M. RabaeyAnantha ChandrakasanBorivoje Nikolic Wiring/routing performed in layers –5-9, typically only in “Manhattan” N/S E/W directionsz E.g. layer 1 – N/Sz Layer 2 – E/W A segment cannot cross another segment on the same wiring layer or …? Wire segments cancross wires on other layers Power and ground typically have their own layersCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 7 Andrew B. Kahng, UCSDBasic Rules of Routing – Part 2 Routing can be on a fixed grid – or gridless Case 1: Detailed routing over cellsz Wiring can go over cellsz Design of cells must try to minimize obstacles to routing – I.e. minimize use of metal-1, metal-2z Cells do not need to bring signals (i.e. inputs, outputs) out to the channel – the route will come to themCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 8 Andrew B. Kahng, UCSDBasic Rules of Routing – Part 3 Routing can be on a fixed grid – or gridless Case 2: Detailed routing only in channelsz Wiring can only go over a row of cells when there is a free track – can be inserted with a “feedthrough”z Design may use of metal-1, metal-2z Cells must bring signals (i.e. inputs, outputs) out to the channel through “ports” or “pins”Courtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 9 Andrew B. Kahng, UCSDTaxonomy of VLSI RoutersGraph SearchSteinerIterativeHierarchical Greedy Left-EdgeRiverSwitchboxChannelMazeLine ProbeLine ExpansionRestricted General PurposePower & GroundClockGlobal Detailed SpecializedRoutersCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 10 Andrew B. Kahng, UCSDGlobal Routing Objectivesz Minimize wire lengthz Balance congestion z Timing drivenz Noise drivenz Keep buses togetherFrameworksz Steiner treesz Channel-based routingz Maze routingECE 260B – CSE 241A /UCB EECS 244 11 Andrew B. Kahng, UCSDGlobal Routing FormulationGiven (i) Placement of blocks/cells(ii) channel capacitiesDetermineRouting topology of each netOptimize(i) max # nets routed(ii) min routing area(iii) min total wirelengthClassic terminology: In general cell design or standard cell design, we are able to move blocks or cell rows, so we can guarantee connections of all the nets (“variable-die” + channel routers). Classic terminology: In gate-array design, exceeding channel capacity is not allowed (“fixed-die” + area routers).Since Tangent’s Tancell (~1986), and > 3LM processes, we use area routers for cell-based layoutCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 12 Andrew B. Kahng, UCSDGlobal Routing Provide guidance to detailed routing (why?) Objective function is application-dependentCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 13 Andrew B. Kahng, UCSDGraph Models for Global Routing Global routing problem is a graph problem Model routing regions, their adjacencies and capacities as graph vertices, edges and weights Choice of model depends on algorithm Grid graph modelz Grid graph represents layout as a hXw array, vertices are layout cells, edges capture cell adjacencies, zero-capacity edges represent blocked cells Channel intersection graph model for block-based designCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 14 Andrew B. Kahng, UCSDChannel Intersection Graph Edges are channels, vertices are channel intersections (CI), v1 and v2 are adjacent if there exists a channel between (CI1and CI2). Graph can be extended to include pins.Courtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 15 Andrew B. Kahng, UCSDGlobal Routing Approaches Can route nets:z Sequentially, e.g. one at a timez Concurrently, e.g. simultaneously all nets Sequential approachesz Sensitive to orderingz Usually sequenced by- Criticality- Number of terminals Concurrent approachesz Computationally hardz Hierarchical methods usedCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 16 Andrew B. Kahng, UCSDSequential Approaches Solve a single net routing problem Differ depending on whether net is two- or multi-terminal Two-terminal algorithmsz Maze routing algorithmsz Line probingz Shortest-path based algorithms Multi-terminal algorithmsz Steiner tree algorithmsCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 17 Andrew B. Kahng, UCSDTaxonomy of VLSI RoutersGraph SearchSteinerIterativeHierarchical Greedy Left-EdgeRiverSwitchboxChannelMazeLine ProbeLine ExpansionRestricted General PurposePower & GroundClockGlobal Detailed SpecializedRoutersCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 18 Andrew B. Kahng, UCSDTwo-Terminal Routing: Maze Routing Maze routing finds a path between source (s) and target (t) in a planar graph Grid graph model is used to represent block placement Available routing areas are unblocked vertices, obstacles are blocked vertices Finds an optimal path Time and space complexity O(height Xwidth)Courtesy K. Keutzer et al.