DOC PREVIEW
UT EE 382V - VLSI Physical Design Automation

This preview shows page 1-2-14-15-30-31 out of 31 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 DensityLocal density at column Cld(C) = # nets split by column CChannel Densityd = max ld( C ) all CEach net spans over an intervalHorizontal Constraint Graph(HCG)node : netedge: two intervals intersectSize of max clique in HCG= channel densityA 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=I2reflective: I1<I1anti-symmetric: I1<I2, I2<I1  I1=I2transitive: I1<I2, I2<I3  I1<I3The 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 Widthdensity 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

UT EE 382V - VLSI Physical Design Automation

Documents in this Course
Load more
Download VLSI Physical Design Automation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view VLSI Physical Design Automation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view VLSI Physical Design Automation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?