ECE 260B – CSE 241A /UCB EECS 244 1Kahng/Keutzer/NewtonRouting in Integrated CircuitsA. KahngK. KeutzerA. R. NewtonECE 260B – CSE 241A /UCB EECS 244 2Kahng/Keutzer/NewtonClass News Wednesday:Presentation of research topics in placement, routing, and timingEach group will do a short presentation at the whiteboard:- Introduce group members- Describe your research problem- Name mentors- Name resources you will need to do project and where you will get them- Describe your approach – methodologically and contentECE 260B – CSE 241A /UCB EECS 244 3Kahng/Keutzer/NewtonToday - ImagineYou have to plan transportation for a new city the size of ChicagoMany dwellings need direct roads that can’t be used by anyone elseYou can affect the layout of houses and neighborhoods but the architects and planners will complainAnd … you’re told that the time along any path can’t be longer than a fixed amountWhat are some of your considerations?ECE 260B – CSE 241A /UCB EECS 244 4Kahng/Keutzer/NewtonWhat are some of your considerations?How many levels do my roads need to go? Remember: Higher is more expensive.How do I avoid congestion?What basic structure do I want for my roads?Manhattan?Chicago?Boston?Automated route tools have to solve problems of comparable complexity on every leading edge chipECE 260B – CSE 241A /UCB EECS 244 5Kahng/Keutzer/NewtonRTL Design FlowRTLSynthesisHDLnetlistlogicoptimizationnetlistLibraryphysicaldesignlayoutabsq01dclkabsq01dclkModuleGeneratorsManualDesignCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 6Kahng/Keutzer/NewtonPhysical 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 7Kahng/Keutzer/NewtonRouting ApplicationsBlock-basedBlock-basedMixedCell and BlockMixedCell and BlockCell-basedCell-basedECE 260B – CSE 241A /UCB EECS 244 8Kahng/Keutzer/NewtonCell based placement leaves us with …(a) Global placement with 1 region (b) Global placement with 4 region (c) Final placementsD. Pan – U of TexasECE 260B – CSE 241A /UCB EECS 244 9Kahng/Keutzer/NewtonRouting AlgorithmsHard to tackle high-level issues like congestion and wire-planning and low level details of pin-connection at the same time Global routingIdentify routing resources to be usedIdentify layers (and tracks) to be usedAssign particular nets to these resourcesAlso used in floorplanning and placement Detail routingActually define pin-to-pin connectionsMust understand most or all design rulesMay use a compactor to optimize resultNecessary in all applicationsECE 260B – CSE 241A /UCB EECS 244 10Kahng/Keutzer/NewtonBasic Rules of Routing - 1Photo courtesy:Jan M. RabaeyAnantha ChandrakasanBorivoje Nikolic Wiring/routing performed in layers –5-9 (-11), typically only in “Manhattan”N/S E/W directions E.g. layer 1 – N/S 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 may have their own layersECE 260B – CSE 241A /UCB EECS 244 11Kahng/Keutzer/NewtonBasic Rules of Routing – Part 2Routing can be on a fixed grid –Case 1: Detailed routing only in channelsWiring can only go over a row of cells when there is a free track – can be inserted with a “feedthrough”Design may use of metal-1, metal-2Cells must bring signals (i.e. inputs, outputs) out to the channel through “ports” or “pins”ECE 260B – CSE 241A /UCB EECS 244 12Kahng/Keutzer/NewtonBasic Rules of Routing – Part 3Routing can be on a fixed or gridless (aka area routing)Case 1: Detailed routing over cellsWiring can go over cellsDesign of cells must try to minimize obstacles to routing – I.e. minimize use of metal-1, metal-2Cells do not need to bring signals (i.e. inputs, outputs) out to the channel – the route will come to themECE 260B – CSE 241A /UCB EECS 244 13Kahng/Keutzer/NewtonTaxonomy 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 14Kahng/Keutzer/NewtonGlobal Routing ObjectivesMinimize wire lengthBalance congestion Timing driven maintain timing constraintsNoise driven minimize cross-coupled capacitanceKeep buses togetherECE 260B – CSE 241A /UCB EECS 244 15Kahng/Keutzer/NewtonGlobal 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 largely use area routers for cell-based layoutCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 16Kahng/Keutzer/NewtonGlobal RoutingProvide guidance to detailed routing (why?)Objective function is application-dependentCourtesy K. Keutzer et al. UCBECE 260B – CSE 241A /UCB EECS 244 17Kahng/Keutzer/NewtonGraph 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 model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 18Kahng/Keutzer/NewtonChannel 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