A Depth-First-Search Controlled Gridless Incremental Routing ...

A Depth-First-Search Controlled Gridless Incremental Routing ...

A Depth-First-Search Controlled Gridless Incremental Routing Algorithm for VLSI Circuits Hasan Arslan and Shantanu Dutt Electrical & Computer Eng. University of Illinois at Chicago ICCD 2004 Outline Introduction Importance of Incremental Routing Previous work Our Goals A DFS-Based Incr. Routing Alg. Non-Uniform Grids DSR (Depth first search controlled Segment bump and Refit) Algorithm Experimental Results Conclusion Introduction In current VLSI Chip The size gets smaller High clock frequency Interconnections on chip very important Technical Problems Wire-congestion and routability Crosstalk / noise Power consumption Terminal distribution Incremental Routing

After a chip layout is completed Time/noise violation One or more optimization metrics Technology constraints Make changes to the circuit/system Engineering Change Order (ECO) process Time to meet market requirements Enormous resources and time already spent. Need a time-efficient & effective incremental routing algorithm Incremental Routing (Cont.) Incremental Routing Problem Set of existing routed nets R Set of new nets S (due to timing violation, noise) Quality metrics for an Incr. Routing Near-optimal incr. solutions in a short amount of time Preserve previous routing results as much as possible Complete the required incremental routing in the available channel area if such a solution exists Prior work on Incremental Routing 1) Emmert and Bhatia, Incremental Routing in FPGA , IEEE Int. ASIC Conference, 1998. 2) Cong and Sarrafzadeh, Incremental Physical Design , ISPD 2000. 3) Dutt, Shanmugavel and Trimberger, Efficient Incremental Rerouting for Fault Reconfiguration in FPGAs, ICCAD 1999. 4) Dutt, Verma and Arslan A Search-Based Bump and Refit Approach to Incremental Routing for ECO Applications in FPGAs, TODAES 2002 5) Xiang, Chao, Wong An ECO Algorithm for Eliminating Crossalk Violations, ISPD 2004 Emmert-Bhatia (ASIC98)

Nets connected to faulty PLB, deleted and rerouted A graph is built, from source pin to target pin Standard single-net routing mode (global then detailed) Do not perturb or move existing nets Cong-Sarrafzadeh (ISPD00) Single Net Routing : Route new nets without removing any existing nets. Rip & Reroute : If some nets cannot be routed, rip-up the existing nets which occupy the resources of new nets. Reroute the ripped up nets. Dutt, Shanmugavel and Trimberger (ICCAD99) Used incremental rerouting for dynamic fault reconfiguration in FPGAs Does not rip-up and reroute Shift them (or their subnets) to other track positions --Bump-&-Refit (B&R) No change in topology, length of existing nets Optimal: Finds a detailed route if exists Dutt, Verma and Arslan (TODAES02) Extended basic B&R significantly for: full incremental routing (global + detailed) complex switchboxes much better results than Std and R&R (routing succ within avail res, HP of failed nets, speed under certain conditions) Our Goals Incremental routing for VLSI (ASIC) circuits Gridless framework for non-uniform width & spacing req. and memory & time efficiency Address the quality metrics of incr. routing Near-optimal incr. solutions (min. WL and vias) in a short amt. of time Preserve previous routing results as much as possible Complete the required incremental routing in the available channel area if such a solution exists = min. # of metal layers = max. routing success in given layers

Approach: Allow bumping of existing nets for near-optimal solns to new nets However, to obtain an overall good solution control the amount of perturbation of existing nets or their routing failures by retracting their bumpings using an overall DFS control DFS-Based Incr. Routing Alg. (Incr. Routing Concepts) Adjacent-via n2 n1 R-BBox n2 n1 DFS-Based Incr. Routing Alg. (Incr. Routing Concepts) If there is an edge between two nets in OG, they might bump each other during shifting one of them. CG of n 1 n1.v 1 ob1 n2. h1 n1. h1 n2.v 1 n2 n1.v1 n1

n1. h1 possible overlapping ob1 n2.v 1 n2. h1 CG of n2 For net ni in OG higher degree (more adj. net in OG) might bump more nets, passing through in dense area Check only adj. nets/blocks in OG to create non-uniform grid for n i DFS-Based Incr. Routing Alg. Do-DFS-Routing(ni) Route-with-Bumping(ni) Generate grid line in R-BB Cp=Get-Candidate-Paths Route-without-Bumping(ni) All paths in Cp tested? return(succ.) YES return(fail) Soln? NO Route-with-Bumping(ni) YES For each bumped net nk

Do-DFS-Routing(nk) return(succ.) YES Soln? NO Soln? NO return(fail) Retract curr. bumping-causing routing path Non-Uniform Grid Extraction Variable width/spacing rule . T . W ir e W id th K K T 2 2 D W ir e S p a c in g

W =4 W s=4 Width / space req. of new net D C e n te r L in e . _ d w = w /2 + w s= 6 K _ K 1 . Z e r o W id th P a th K _ 3 K 3 1 To route new net Create obstruction zone around existing nets Find zero width path for new net

Non-Uniform Grid Extr. & Routing t BGLs (Boundary Grid Lines) s t t s VGLs (Vacant Grid Lines) OGLs (Occupied Grid Lines) Use VGLs to get solution without bumping . Use VGLs and OGLs to do B&R type routing (OGLs has higher cost than VGLs). DFS-Based Incr. Routing Alg. Do-DFS-Routing(ni) Route-with-Bumping(ni) Cp=Get-Candidate-Paths Generate grid line in R-BB Route-without-Bumping(ni) return(succ.) YES All paths in Cp tested? return(fail) NO Soln? NO

Route-with-Bumping(ni) YES YES Get-Next-Path(CP) For each bumped net nk Do-DFS-Routing(nk) return(succ.) Soln? NO return(fail) YES Soln? NO Retract curr. bumping-causing Routing path Finding Solution without Bumping Use the 4via Algorithm (Carothers,Lee,T-CS,1999) 1-via routing 2-via routing Adj-via Adj-via n1 nj n2 n3 n1 Adj-via

Bumped seg. n2 n1 Adj-via If 3-via 1-via path cannot be found due to obstacles 2-via 3-via routing 4-via routing Adj-via n 1 Adj-via n 1 cv n1 Adj-via n1 Adj-via cv DFS-Based Incr. Routing Alg. Do-DFS-Routing(ni) Route-with-Bumping(ni) Cp=Get-Candidate-Paths Generate grid line in R-BB Route-without-Bumping(ni) return(succ.) YES All paths of Cp tested?

return(fail) NO solution NO Route-with-Bumping(ni) YES YES Get-Next-Path(Cp) For each bumped net nk Do-DFS-Routing(nk) return(succ.) Soln? NO return(fail) YES Soln? NO Retract curr. bumping-causing Routing path Selecting Paths to Route Bumped Seg. Adj-via n1 Adj-via n1 n1 n1

Adj-via Adj-via Equal distance m paths Random m paths Adj-via n1 n1 The first m paths The randomized initial path set selection gave the best solutions in terms of both quality and runtime. Seq. Rnd. Equ. 10% new net Unr. HP of F. F. Net. Nets. nets Width Time(sec) 3.56% 1647.6 3.69 32.65 3.43% 1451.57 3.47 34.37 4.08% 1631.33 3.57 49.45 DFS-Based Incr. Routing Alg. Do-DFS-Routing(ni) Route-with-Bumping(ni) Cp=Get-Candidate-Paths Generate grid line in R-BB Route-without-Bumping(ni)

return(succ.) YES Have all path of CP tested return(failed) Soln? NO Route-with-Bumping(ni) YES YES Get-Next-Path(CP) For each bumped net nk Do-DFS-Routing(nk) return(succ.) Soln? NO return(failed) NO YES solution NO Retract previous bumping-causing routing DFS-Controlled Routing with Bump & Refit n3..v1 nj

n2 n3 nj nj n2..h1 n1 n1..b-seg n3..h1 n1..b-seg n2..h2 Pi= i-via path is explored P1 n2.pin or obs n1.b-seg DFS-Controlled Routing with Bump & Refit n3..v1 nj n2 n3 nj nj n2..h1 n1 n2..h2 n3..h1 n1..b-seg

n2..h2 Pi= i-via path is explored n1.b-seg P1 P2 n2.pin or obs n2.h2 P1 n3.v1 DFS-Controlled Routing with Bump & Refit n3..v1 nj n2 n3 nj nj n2..h1 n1 n2..h2 n3..h1 n2..h2 P1 P2 n2.pin

or obs n1..b-seg Pi= i-via path is explored n1.b-seg n2.h2 P1 P1 obs n3.v1 P1 anc P2-P4 obs or anc.n1 or anc.nj DFS-Controlled Routing with Bump & Refit n3..v1 nj n2 n3 nj nj n2..h1 n1 P1 n3..h1 n2..h2 n1..b-seg

Pi= i-via path is explored n1.b-seg P2 n2.pin or obs n2.h2 P2-P3 P1 P1 obs n3.v1 P1 anc P2-P4 P1 obs or obs anc.n1 or anc.nj n3.h1 P2-P4 obs or anc.n1 or anc.nj DFS-Controlled Routing with Bump & Refit n3..v1 nj n2

n3 nj nj n2..h1 n1 P1 n3..h1 n2..h2 n1..b-seg n2..h2 Pi= i-via path is explored n1.b-seg P2 n2.pin or obs n2.h2 P2-P3 P1 P1 obs n3.v1 P1 anc P2-P4 P1 obs or obs anc.n1 or anc.nj

n3.h1 P2-P4 obs or anc.n1 or anc.nj DFS-Controlled Routing with Bump & Refit n3..v1 nj n2 n3 nj nj n2..h1 n1 n1..b-seg n3..h1 Pi= i-via path is explored n1.b-seg P1 n2.h1 P2 n2.pin or obs n1..b-seg n2..h2 P2 n2.h2

P1 obs P2-P3 P1 P1 obs n3.v1 P1 anc P2-P4 P1 obs or obs anc.n1 or anc.nj n3.h1 P2-P4 obs or anc.n1 or anc.nj DFS-Controlled Routing with Bump & Refit n3..v1 nj n2 n3 nj nj n1 n2.h1

P2 n2.pin or obs n2..h2 Pi= i-via path is explored n1.b-seg P1 n3..h1 P2 n2.h2 P1 obs P2-P3 P1 P1 obs n3.v1 P1 anc P2-P4 P1 obs or obs anc.n1 or anc.nj

P2 VGL n3.h1 P2-P4 obs or anc.n1 or an.nj Characteristics of Benchmark Circuits Circuit net-97 net-102 net-103 net-115 net-247 10% 20% 10% 20% New N. New N. Circuit New N. New N. net-282 10 19 28 56 net-391 10 20 39 78 net-413 10 20 41 82 net-557 11 23 55

111 net-700 24 49 70 140 Average number of new nets Circuit net-797 net-829 net-961 net-968 10% 20% New N. New N. 79 159 82 164 96 192 82 165 46.36 93.21 Width of net 2 -15 unit Space req. btw. nets 1 - 8 unit Base 2x2 tile of Mcc1 benchmark is replicated with diff. cell sizes and diff. # of pins Nets connected to pins randomly generated routed by using max 4-via routing Experiment involved routing as many nets as possible under the constraint of 2 metal layers only routing succ. rate = efficacy of router Experimental Results 12.0

Comparison of Runtimes (sec.) 10.8 10.0 8.5 8.0 6.0 Std 4.6 R&R 4.0 2.4 Runtime (sec.) Failure factor with respect to DSR Comparison of Avr. Unrouted Nets (Base-DSR) 2.0 0.0 10% Ne w Ne t 50.0 45.0 40.0 35.0 30.0 25.0 20.0 15.0

10.0 5.0 0.0 15.00 10.00 5.00 0.00 5.60 0.00 10% New Net 3.24 0.00 20% New Net Std R&R DSR Avr. # of modified net # of Rerouted Nets 14.75 Std R&R 15.61 12.08 DSR 4.19 3.09 20% New Net

Comp. of modified existing nets for each new net 21.98 20.00 34.37 10% New Net 20% Ne w Ne t # of Rerouting Exiting Nets Tried for Each New Net (Search Space) 25.00 45.51 3.00 2.50 2.59 2.04 2.00 1.50 1.00 0.50 0.00 1.51 0.00 1.25 0.00 10% New Net

Std 20% New Net R&R DSR Experimental Results (Comparison of Failed Nets) Com parison of Width of Failed Nets 40.00 35.00 30.00 25.00 20.00 15.00 10.00 5.00 0.00 36.75 5.11 10% New Net Std 6.59 2.15 20% New Net R&R Width factor with respect to DSR Total HP factor with respect to DSR

Com parison of Total HP of Failed Nets 2.50 2.00 2.06 1.60 1.52 1.50 1.29 1.00 0.50 0.00 10% New Net Std 20% New Net R&R Unrouted nets are longer and wider when Std. and R&R used DSR gets more compact layout by routing more and wider nets Experimental Results (Comparison of Modified Nets) Comp. of via incr. of modified nets 3.00 2.50 2.00 1.50 1.00 0.50 0.00

2.59 2.04 1.51 0.00 1.25 0.00 10% New Net Std 20% New Net R&R DSR Via increment (%) Avr. # of modified net Comp. of modified existing nets for each new net 140.00% 120.00% 100.00% 80.00% 60.00% 40.00% 20.00% 0.00% 116.68% 88.32% 30.25% 23.17%

0.00% 0.00% 10% New Net Std 20% New Net R&R DSR Experimental Results (Global Nets) Com parison of Width of Failed Nets 70.00 60.00 50.00 40.00 30.00 20.00 10.00 0.00 60.62 42.96 9.15 3.23 10% New Net Std 20% New Net R&R Width factor with respect to DSR

Total HP factor with respect to DSR Com parison of Total HP of Failed Nets 3.50 3.28 2.94 3.00 2.50 2.23 1.75 2.00 1.50 1.00 0.50 0.00 10% New Net 20% New Net Std R&R Experimental Results # of Rerouting Existing Nets Tried for Each New Net Routing (Search Space) Comp. of modified existing nets for each new net 2.50 2.21 1.50

1.28 1.18 # of Rerouted Nets 2.00 1.14 1.00 0.50 0.00 0.00 10% New Net Std 0.00 25.00 19.52 20.00 15.00 11.99 10.00 5.20 5.00 0.00 0.00 20% New Net R&R

DSR 0.00 10% New Net Comp. of via incr. of modified nets Via increment (%) Avr. # of modified net (Global Nets) 120.00% 100.00% 97.42% 93.25% 80.00% 60.00% 35.76% 40.00% 20.00% 0.00% 17.21% 0.00% 0.00% 10% New Net Std 20% New Net R&R

DSR 2.98 20% New Net Std R&R DSR Conclusions New Incremental Routing Algorithm DSR gridless routing variable width/space Produces significant impr. over Std. R&R Via incr. of modified nets (3 (5) times less than R&R, 10% and 20%, respectively) Higher routing success rate (Std.=10.8 (8.5) R&R= 4.6 (2.4) times worse) Wire length (HPBB) of failed nets: Std. = 36.7 (6.59) R&R = 5.1 (2.15) times worse) Degree of modification (~20% less modification than R&R) Future Work Tile-based approach to avoid congestion Timing-driven DSR algorithm THANK YOU

Recently Viewed Presentations

  • Being an Awesome Auditor! - Institute of Internal Auditors

    Being an Awesome Auditor! - Institute of Internal Auditors

    Beware of horizontal and vertical scope creep. Managers- Note the volume of a staff member's working papers, looking for information that is just "padding", dilutes the main objective, or wastes time. Hiring Managers- Look for ways to evaluate a candidate's...
  • WaytogoRI ILP Kick Off Webinar 2014-15 Copyright  2013

    WaytogoRI ILP Kick Off Webinar 2014-15 Copyright 2013

    ILP = Individual Learning Plan. ILPs provide students with a road map to the future and a record of the past. The ILP is a dynamic tool that maps academic plans, and reflects each student's unique set of interests, needs,...
  • YOUR dental PLAN OPTIONS

    YOUR dental PLAN OPTIONS

    The Cigna Dental Oral Cancer Awareness Quiz is available on our websites in both English and Spanish: - www.cigna.com - on the Dental tab, under "Related Topics" - itstimetofeelbetter.com - on the "Interactive Tools" page, under "Dental Health" - myCigna.com...
  • Chapter 2 "Comparing Political Systems" - Mr. M's

    Chapter 2 "Comparing Political Systems" - Mr. M's

    Interest Articulation - expressing interests to the government. Interest Aggregation - overall views of people; combination of demands. Interest Adjudication - justification of policies (consequences, order, decree) Process functions are performed by political parties, legislatures, executives and courts
  • Title with Background Master, Arial 24 pt

    Title with Background Master, Arial 24 pt

    Types of Rollover Collisions. Lateral Force Rollovers - Occur when a driver attempts to make a turn while traveling too fast. Excessive speed while turning causes the vehicle to continue on it's original path and the vehicle rolls.
  • Model Refinement from Planar Parallax Anthony Dick Roberto

    Model Refinement from Planar Parallax Anthony Dick Roberto

    Model acquisition Model refinement We concentrate on approximately planar models of architectural scenes Planar parallax Two projections of a planar scene are related by a 2D homography H Points not belonging to the plane do not obey this homography displaced...
  • Conventional method/ Standard Method - PBworks

    Conventional method/ Standard Method - PBworks

    Conventional cakes Shortened cakes-contain fat (shortening, margarine or oil) Leavening agents are baking powder or soda. Includes pound cake. Unshortened/foam cakes-do not use fat or oil. Angel food and sponge cakes. Leavening agent is air beaten into egg whites. Tips...
  • Quick LaTeX Tutorial

    Quick LaTeX Tutorial

    Referencing in LaTex Recall the following method of referencing Making references in LaTeX (fish.tex) \documentclass{article} \begin{document} \emph{My mother} is a \underline{fish} \cite{WF}. \begin{thebibliography}{99} \bibitem{WF} William Falkner, \emph{As I Lay Dying} \end{thebibliography} \end{document} Need to compile the document twice Because we...