VLSI Physical Design AutomationYoshimura and Kuh’s MethodCharacterizing Channel Routing ProblemZone RepresentationSlide 5Merging of NetsScanning the ZonesScanning of ZonesMerging VCGAssigning TracksSlide 11Shortcomings of the First ApproachProcessing ZoneSimultaneous MergingCyclic ConflictsSlide 16An Example of Algorithm AASlide 18Slide 19Slide 20CommentsRouting Examples by Y-K’s AlgorithmRouting Examples by Y-K’s Algorithm (Cont’d)Deutsch’s Difficult ExampleSummary of Yoshimura and Kuh’s AlgorithmGreedy Channel RouterOverview of Greedy RouterOperations at Each Column(A) Make Minimal Feasible Top/Bottom Connections( B ) Collapse Split Nets( C ) Move Split Nets CloserPowerPoint PresentationSlide 33Slide 34Comments on Greedy Router (Rivest&Fiduccia 1982)Parameters to Greedy RouterExperimental Results01/13/191VLSI Physical Design AutomationProf. David [email protected]: ACES 5.434Detailed Routing (II)201/13/19Yoshimura and Kuh’s MethodSource: “Efficient Algorithms for Channel Routing”by T. Yoshimura and E. KuhIEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems.Vol. CAD-1, pp25-35, Jan 1982301/13/19Characterizing Channel Routing Problem1358926710413548910762Vertical constraint graph GvHorizontal constraint graph0 1 4 5 1 6 7 0 4 9 10 102 3 5 3 5 2 6 8 9 8 7 921543678910401/13/19Zone Representation001144551166770044991010101022335533552266889988779922112233112233445511223344551122445522446644667744778844778899778899779910109910101122334455Zone:Zone:Remarks: A new zone appears when some Remarks: A new zone appears when some intervals begin after some intervals end.intervals begin after some intervals end.501/13/19Zone Representation221122331122334455112233445511224455224466446677447788447788997788997799101099101011223344556677889910101122334455Zone:Zone:601/13/19Merging of Nets1144553399881010776622112233445566778899101011445,65,633998810107722112233445,65,67788991010701/13/19Scanning the Zones1122334455667788991010Left = {1, 3, Left = {1, 3, 55}}Right = {Right = {66}}112233445,65,67788991010Left = {Left = {11, 2, 3}, 2, 3}Right = {Right = {77}}1,71,722334488991010Left = {2, Left = {2, 33, , 5.65.6}}Right = {Right = {88, , 99}}5,65,6801/13/19Scanning of Zones1,71,7223,83,8441010Left = {2, 3.8, Left = {2, 3.8, 44}}Right = {Right = {1010}}5,6,95,6,91,71,7223,83,84,104,105,6,95,6,9901/13/19Merging VCG114455339988101077662211445,65,6339988101077221,71,74,104,105,6,95,6,93,83,8221,71,7445,6,95,6,93,83,81010221,71,7445,65,63399881010221001/13/19Assigning Tracks1,71,74,104,105,6,95,6,93,83,822Track 1Track 1Track 2Track 2Track 3Track 3Track 4 (or 5)Track 4 (or 5)Track 5 (or 4)Track 5 (or 4)1101/13/19Merging of Nets•Make sure that the VCG remains acyclic•There are two approaches:–First approach: Merge the pairs sequentially. Select pairs to minimize the increase in the length of the longest path in the VCG.–Second approach: Merge all pairs simultaneously. Select pairs to maximize the total no. of matches.•We will focus on the second approach: “simultaneous merging”.1201/13/19Shortcomings of the First ApproachObservation: Merging of two nodes may block subsequent mergingNet f cannot be merged with either c or g. But, if we merged a with d, c with e then f can be merged with net babcgh4dekf321a.db.ecgh4kf321agcebkhfda.dgcb.ekhf1301/13/19Processing ZoneabcghdekfagcebkhfdProcessing Zone 1Bipartite graphLEFT={a,b,c}RIGHT={d,e}abcdeDelay merging!!(Both d and e do not terminate at zone 2Processing Zone 2abcdefgabcdefgModify matchingCyclic conflict!!Merge a&d, b&f, delay merging c&eLEFT={a.d, b.f,c,g}RIGHT={h,k,e}Merge two nets when both of them terminate!1401/13/19Simultaneous MergingUse the maximum cardinality matching inUse the maximum cardinality matching inbipartite graph:bipartite graph:1122334455667788991010Left = {1, 3, 5}Left = {1, 3, 5}Right = {6}Right = {6}11336655Find the maximum matchingFind the maximum matchingin this bipartite graph such thatin this bipartite graph such thatthe resultant VCG is still acyclic.the resultant VCG is still acyclic.1501/13/19Cyclic ConflictsSimultaneous merging can produce cyclic conflicts:Simultaneous merging can produce cyclic conflicts:221133442211443311223344Bipartite graph, GBipartite graph, GVCGVCG221144331,31,32,42,4Cyclic!Cyclic!1601/13/19Cyclic ConflictsBipartite graphBipartite graphG(V,E)G(V,E)Algorithm AAAlgorithm AAA set of edges E’A set of edges E’TheoremTheorem: Any matching in G(V,E-E’) is feasible.: Any matching in G(V,E-E’) is feasible.1701/13/19An Example of Algorithm AAaabbccddgghhiiggbbccaaddiihhN = set of nodes thatN = set of nodes thathave in-degree 0have in-degree 0ggbbccaaiihhaabbccddgghhiiisolatedisolatedRemove edges betweenRemove edges betweenvertices in Nvertices in N1801/13/19An Example of Algorithm AAaabbccgghhiiggbbccaaiihhaabbccgghhiiggbbcciihhNo isolated node. ThenNo isolated node. Thenselect among N the nodeselect among N the nodewith the smallest degree inwith the smallest degree inthe bipartite graph. Removethe bipartite graph. Removeand and put its edges to E’put its edges to E’..NNbbccgghhiiaaisolatedisolated1901/13/19An Example of Algorithm AAbbccgghhiiggbbcciihhNNbbhhggcciiisolatedisolatedbbcciihhNNcciibbhhisolatedisolatedbbcchh2001/13/19An Example of Algorithm AAccbbhhAt the end, all edges are removed, andAt the end, all edges are removed, andE’ = {(a,h)}E’ = {(a,h)}Since E’ Since E’  , according to the corollary, any, according to the corollary, anymatching in the bipartite graph G(V, E-E’) ismatching in the bipartite graph G(V, E-E’) isfeasible. We will find a matching in G(V, E-E’)feasible. We will find a matching in G(V, E-E’)ccbbhhbbcchhNN Why does it work?2101/13/19CommentsAvoid unnecessary introduction of dogleg, use a process “merging of subnets”subnet i and subnet j can be merged merging subnet i and subnet j will not increase the longest path length passing through HReduce CPU time by:# of edges/nodes in the bipartite graph is limited by a parameter(e.g. =3 in the program)Need not start at zone 1In general, can obtain better results by starting at the max density zoneMax density zone2201/13/19Routing Examples by Y-K’s Algorithmnumber of tracks=18maximum density =18number of tracks=17maximum density =17Example 3cExample 4b2301/13/19Routing Examples by Y-K’s Algorithm