Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 1Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.1EE244: Design Technology for Integrated Circuits and SystemsOutlineLecture 3.2◆Introduction to Routing◆Area Routers◆Channel Routing▲Greedy▲Left-Edge Algorithm▲Yoshimura & Kuh▲YACREE244 Fall 97 1.2.2Taxonomy of VLSI RoutersGraph SearchSteinerIterativ eHierarchical Greedy Left-Edg eRiverSwitchbo xChann elMazeLine ProbeLine ExpansionRestricted General PurposePower & GroundClockGlobal Detailed SpecializedRoutersImplications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 2Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.3Maze Route: Lee Path Connection AlgorithmABPoint-to-point, single layer43234567891011321234 891011122 1 A 1 5 9 10 111 2 6 7 8 9 10 11 124323 7 1254 8910 B6 5 6 10 9 10 11 12767891011128 9 10 119 10111212 11 10 11 1212 11 12Wavefront propagation234A1 56789101112BBacktracking5678234 8910A 1 5 9 10 1112 67891011323 7 1248910B5 6 10 9 101112789Prioritizing the search: A*EE244 Fall 97 1.2.4Line Probe: Hightower & TabuchiAB•Also called “Ray”, “Line search”, “Gridless router”•Usually implemented on a gridImplications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 3Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.5Line Search: Hightower & TabuchiAB•Note order-dependence A-B versus B-AEE244 Fall 97 1.2.6Pattern Route: SoukupAB123 456Use line-search to blockage and then revert tomaze-routerImplications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 4Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.7Channel Routing◆Basic Terminology:◆Fixed pin positions on top and bottom edges◆Classical channel: no nets leave channel◆Three-sided channel possiblechannelpinstracksendviatrunknet111branchEE244 Fall 97 1.2.8Routing Region Definition6254137•Use of Slicing Structure for ordering (Otten)Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 5Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.9Channel Routing14 61784 9 10 1032526 9879355•Graph representations:•Vertical Constraint Graph (VSG)•Horizontal Interval Graph (HIG)EE244 Fall 97 1.2.10Channel Routing14 61784 9 10 1032526 98793551 4 103589 762VCG14103589762HIGImplications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 6Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.11Vertical Constraint Graph1 4 103589 762VCG14 61784 9 10 1032526 987935521435678910EE244 Fall 97 1.2.12Greedy Router: Rivest & Fiduccia◆Proceed column by column (left to right)◆Make connections to all pins in that column◆Free up tracks by collapsing as many tracks as possible tocollapse nets◆Shrink range of rows occupied by a net by using doglegs◆If a pin cannot enter a channel, add a track◆O(pins) time14 61784 9 10 1032526 9879355Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 7Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.13Greedy Router◆Three Parameters Control Algorithm:▲ Initial_Channel_Width, Minimum_Jog_length,Steady_Net_Constant◆Rule-Based Approach▲Rule 1: Make feasible top and bottom connections in minimal manner▲Rule 2: Free up as many tracks as possible by collapsing split nets▲Rule 3: Add jogs to minimize distance between split nets (but noshorter than minimum_jog_length)▲Rule 4: Add jogs where possible to raise rising nets and lower fallingnets▲Rule 5: Widen channel if needed to make top or bottom connections.Add tracks in the middle of the channel▲Rule 6: Extend the channel to a new column to completeunconnected net segments.EE244 Fall 97 1.2.14Greedy Routing Example14 61784 9 10 1032526 9879355Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 8Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.15Left-Edge Algorithm (LEA)(Hashimoto & Stevens)◆Process horizontal tracks in order from top tobottom of channel and assign nets to tracks at eachstage (assuming no cyclic constraints in VCG)For track i, choose the “left-most net” of those who have noancestors in the VCGRepeat process until no additional nets can be assigned tothe trackMove to track i+1◆Guarantees a solution since there are no cyclicconstraints permitted in VCG◆In example, VCG permits (1,4,10) in first track, butonly (1,10), (4,10) based on HIG; choose (1,10)EE244 Fall 97 1.2.16Left-Edge Algorithm (LEA)(Hashimoto & Stevens)VCG14 61784 9 10 1032526 98793554358976243589762HIG•Choose 4 or 7; choose 4 since left-mostImplications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 9Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.17“Merging of Nets”(Yoshimura & Kuh)◆On the assumption of no cyclic constraints, netsthat can be placed on the same track can be mergedin the VCG, simplifying the VCG.14103589762HIGZone12 34512345679108EE244 Fall 97 1.2.18Merging of Nets◆Definition: Let i and j be nets for which the followingholds:(a) i and j are not adjacent in the HIG(b) There is no direct path between i and j in the VCGThen these nets can be assigned to the same trackand hence they can be merged in the VCG◆Merging Operation:(1) Combine nodes i and j into node i•• j in VCG(2) Update zone representation such that i••j occupies zonesof i and j and all zones in betweenImplications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 10Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.19Merging of Nets: Example1 4 103589 7621 41035•68972mer ge(5,6)1•741035•6892mer ge(1,7)1•74103 •85 •6 •92mer ge(5,6,9)(3,8)1•710 •43 •85 •6 •92(1)(2)(3)(4)(5)mer ge(4,10)EE244 Fall 97 1.2.20Introducing DoglegsFinding the optimal locations for doglegs is an NP-Complete problem1132231231132231232Implications of Deep SubmicronSimplex SolutionsProf. A. Richard NewtonUniversity of California at BerkeleyPage 11Copyright © 1997, A. Richard NewtonEE244 Fall 97 1.2.21Cyclic Constraints◆VCG may contain a “cyclic constraint” andtherefore cannot be routed with algorithms above◆The use of “doglegs” (a net using two or