VLSI Physical Design AutomationAfter Global Routing: Detailed RoutingChannel Routing for Different StylesChannel OrderingSlide 5Routing Grid ModelsChannel Routing TerminologyRouting Layer ModelsChannel Routing ProblemChannel Routing ProblemConstraint GraphsLower Bound on Channel WidthLeft-edge Channel Routing AlgorithmFeatures of Left-edge AlgorithmLeft-edge AlgorithmChannel DensityInterval PackingLeft-Edge Algorithm for Interval PackingLeft-edge Algorithm: ExampleVertical Constraint ConsiderationSlide 21Slide 22Constrained Left-edge AlgorithmSlide 24Cycles in Vertical Constraint GraphReduce Channel Width by DoglegDeutch’s Dogleg AlgorithmSlide 28Slide 29Drawbacks of the Constrained Left-edge AlgorithmSlide 3101/14/191VLSI Physical Design AutomationProf. David [email protected]: ACES 5.434Detailed Routing (I)201/14/19 After Global Routing: Detailed Routing The routing regions are divided into channels and switchboxes. So only need to consider the channel routing problem and the switchbox routing problem.AABB301/14/19Channel Routing for Different Styles•For Gate-array design, channel widths are fixed. The goal is to finish routing of all the nets.•For Standard-cell and Full-custom design, channels are expandable. The goal is to route all nets using the minimum channel width.•We will consider the case when the channels are expandable.401/14/19Channel OrderingAABBThe width of A is not known untilThe width of A is not known untilA is routed, we must route A first.A is routed, we must route A first.AABBCCDDWhat should be the routingWhat should be the routingorder for this example?order for this example?501/14/19Channel OrderingCCDDBBAANo feasible No feasible channel order!channel order!CCDDBBAANeed to use switchboxNeed to use switchbox1. Fix the terminals between A & B1. Fix the terminals between A & B2. Route B, C, then D (channel)2. Route B, C, then D (channel)3. Route A (switchbox)3. Route A (switchbox)601/14/19Routing Grid Models•Grid-based model is the most commonly used.•We will focus on it in this course.Grid-based RoutingGrid-based RoutingGridless RoutingGridless Routing701/14/19Channel Routing TerminologyUpper boundaryUpper boundaryLower boundaryLower boundaryTracksTracksTerminalsTerminalsViaViaTrunksTrunksBranchesBranchesDoglegDogleg801/14/19Routing Layer ModelsHV modelHV modelVH modelVH modelHVH modelHVH modelVHV modelVHV modelLayer 1Layer 1Layer 2Layer 2Layer 3Layer 3ViaVia1 layer1 layer2 layers2 layers3 layers3 layers901/14/19Channel Routing Problem •Input: –Two vectors of the same length to represent the pins on two sides of the channel.–Number of layers and layer model used.•Output:–Connect pins of the same net together.–Minimize the channel width.–Minimize the number of vias.1001/14/19Channel Routing Problem11330000221111003300112200330000Example: (13002110) (30120300)where 0 = no terminal1101/14/19Constraint Graphs0011661122335566335544002244Vertical constraint graphVertical constraint graph0011661122335566335544002244112233445566Horizontal constraint graphHorizontal constraint graph1122334455661122335544661201/14/19Lower Bound on Channel Width00116611223355663355440022440011661122335566335544002244112233554466LocalLocaldensitydensity11334444444422Channel density =Channel density =Maximum local densityMaximum local densityLower bound = 4Lower bound = 4Lower bound on channel width = Channel density01/14/1913Left-edge Channel Routing Algorithm “Wire Routing by Optimizing ChannelAssignment within Large Apertures”, A. Hashimoto and J. Stevens, DAC 1971, pages 155-169.1401/14/19Features of Left-edge Algorithm•Assumptions:–One horizontal routing layer–No vertical constraint, e.g., VHV model•Always gives a solution with channel width equal channel density, i.e., optimal solution.00000022001100001100000022002211 Vertical constraintVertical constraintmay occur here.may occur here.1501/14/19Left-edge Algorithm 1. Sort the horizontal segments of the nets in increasing order of their left end points. 2. Place them one by one greedily on the bottommost available track.1601/14/19Channel DensityLocal density at column Cld(C) = # nets split by column CChannel Densityd = max ld( C ) all CEach net spans over an intervalHorizontal Constraint Graph(HCG)node : netedge: two intervals intersectSize of max clique in HCG= channel densityA lower bound:# tracks channel densitya aacabdefld(x)eadcbf1701/14/19Thm: If the density of a set of intervals is d, then they can be packed into d tracks.Proof: I1=(a,b) I2=(c,d)Define: I1<I2 iff b<c or I1=I2reflective: I1<I1anti-symmetric: I1<I2, I2<I1 I1=I2transitive: I1<I2, I2<I3 I1<I3The interval set with binary relation < forms a partially ordered set (POSET)!! Intervals in a track they form a chain Intervals intersecting a common column anti-chainDilworth’s theorem (1950): If the max anti-chain of a POSET is d, then the POSET can be partitioned into d chainsInterval PackingI6ca b dI4I3I1I2I5I1I5I2I3I4I61801/14/19Left-Edge Algorithm for Interval PackingRepeatcreate a new track tRepeatput leftmost feasible interval to tuntil no move feasible intervaluntil no move intervalInterval are sorted according to their left endpointsO(nlogn) time algorithm. Greedy algorithm works!I6I4I3I1I2I5I6I4I3I1I2I51901/14/19Left-edge Algorithm: Example001166112233556633554400224400116611223355663355440022441122335544661. Sort by left end points.1. Sort by left end points.001166112233556633554400224411662. Place nets greedily.2. Place nets greedily.335544222001/14/19Vertical Constraint Consideration0011661122335566335544002244•The Left-edge algorithm ignores vertical constraints.•When there is only one vertical layer, the algorithm will produce overlapping of vertical wire segments.2101/14/19Lower Bound on Channel Width0011661122335566335544002244112233445566Lower bound = 3Lower bound = 3Length of the longestpath in the vertical con-straint graph2201/14/19Lower Bound on Channel Widthdensity ChannelVCG in thepath longest theofLength max widthchannelon boundLower2301/14/19Constrained Left-edge Algorithm•Consider vertical constraints.•Similar to the Left-edge algorithm.•Modifications: Place a horizontal segment only if it does not have any unplaced descendants in the vertical constraint graph Gv. Place it on the bottommost available track above all its descendents in Gv.2401/14/19Constrained Left-edge
View Full Document