Can Recursive Bisection Alone Produce Routable Placements?

Can Recursive Bisection Alone Produce Routable Placements?

Supported by Cadence Can Can Recursive Recursive Bisection Bisection Alone Alone Produce Produce Routable Routable Placements? Placements? Andrew E. Caldwell Andrew B. Kahng Igor L. Markov http://vlsicad.cs.ucla.edu Outline Routability and the placement context Placement by recursive bisection UCLA Capo placer Empirical results Conclusions and open questions Routability is a Requirement For Placement VLSI placement is fixed-die, followed by routing Routing fails placement was not useful Algorithms that produce routable placements are more valuable (no fixes cleaner EDA) Timing-driven placement

does not excuse the routability requirement is a harder problem, not a different problem Question: can we achieve routability without increasing wirelength ? (via a better global placer) In This Work: WL-driven Placement Infeasible Given a circuit a [very good] black-box router Routing Definition a circuit placement is "100% auto-routable" the router automatically completes all nets without manual intervention OUR CRITERION: Less than 100% autoroutability == placement failure Sets the bar for placer evaluation Fixed-die vs Variable-die Fixed-die P&R (typically, N-layer metal)

cell sites and routing tracks are fixed cannot spread rows and insert routing tracks makes achieving routability much harder is implied by modern design techniques power/ground planning, hierarchical block methodology assumed by Cadence LEF/DEF formats assumed by most commercial EDA tools Variable-die P&R (typically, 2-layer metal) row geometries, utilization, area not known in advance

routability can be traded for area Routability Routability is not a purely 0-1 property router runtime explodes when routing gets harder May be harder with growing #nets need to use large benchmarks (10K cells and up) May be easier with increased # metal layers need to use very recent benchmarks Experimental question: Does decreasing overall WL improve routability and routed wirelength ? Recursive Bisection Placement etc. Recursive Bisection (RB) Placement Framework for leading commercial tools

fast and scalable can be extended to handle timing Key technologies balanced hypergraph bipartitioning UCLA MLPart (Caldwell/Kahng/Markov ASPDAC 2000) end-case processing optimal methods (Caldwell/Kahng/Markov ISPD `99) RB placement vastly improved in the last 2 years due to the multi-level partitioning breakthrough Experimental Q: does better RB improve routability? UCLA Capo Placement Tool Open-source: vlsicad.cs.ucla.edu, openeda.org Employs recent advances in recursive bisection This paper: nothing used beyond recursive bisection Improved flat Fiduccia-Mattheyses (FM) better performance for small partitioning tolerance VLSI Design 2000 Better Multi-Level Fiduccia-Mattheyses (MLFM) improves upon hMetis (DAC `97), faster ASP DAC 2000 New block splitting heuristics for vertical cuts

easier partitioning instances and increased solution space Hierarchical tolerance computation (UCLA TR-200002) Experimental Flow VLSI Circuit (LEF/DEF) Capo placer (Fast = 1/2 MLFM) Industry placer Legalization (~2sec) w/ industry placer Industry router from same vendor Computed: HPWL, WWL, routed WL and runtimes Test Cells Nets White #Metal case spaceLayers 1 + 11471 11828 24.30% 3

2 + 19832 22974 9.90% 6 3 + 20392 25634 14.20% 2 4 - 25995 28603 8.70% 3 5 33917 39152 29.40% - infty 4 6 + 35549 44121 0.10%

4 7 = 42352 44490 29.30% 5 Placer HPWL WWL Place Routed Route x1e6 x1e6 time WL x1e6 time Industrial UCLA Capo Capo-Fast Industrial UCLA Capo Capo-Fast Industrial UCLA Capo Capo-Fast Industrial UCLA Capo Capo-Fast Industrial UCLA Capo Capo-Fast Industrial UCLA Capo Capo-Fast Industrial UCLA Capo

Capo-Fast 2.8 2.68 2.72 1.24 1.28 1.31 5.93 5.6 5.76 10.8 10.3 10.2 5.89 5.73 5.67 9.67 9.3 9.43 37.1 36.2 34.8 3.22 3.05 3.03 2.53 2.36 2.12 7.7

7.18 7.25 13.6 12.8 12.5 7.29 6.88 6.73 12.3 11.4 11.5 47.7 45.5 45.1 182 3.43 269 3.3 131 3.38 520 2.49 473 2.16 270 2.22 414 7.9 471 7.52

239 unroutable! 427 17 837 17.9 394 17.8 990 7.9 1197 unroutable! 621 unroutable! 1765 11.8 1546 11.1 649 11.7 981 44.3 1154 44.5 657 46 223 293 336 833 500 502 613

579 3840 5382 6346 5558 3502 4196 7355 1120 1050 1055 624 615 701 What About MCNC Benchmarks? Too old for meaningful routability evaluation > 10 years old, no longer representative (Alpert 98) row-based layouts use variable-die Most published WLs are unreliable solutions not available different row configurations used

some placers place pads (on the boundary?) some assume given pad locations (which ones?) Capo runs on MCNC benchmarks (Bookshelf format) you can download Capo, run it and see solutions runtimes on a single Pentium III Xeon @550MHz avqlarge ( 25K cells, 33K nets) 4.5min golem3 (100K cells, 217K nets) 37 min What Did Not Work For Us Overlapping with bisections Fancy terminal propagation Explicit top-down look-ahead Improvements using analytical placement quadratic wirelength linear wirelength Using name-based hierarchies

improvement on one example out of many the circuit was unusually hard to partition possible interpretation: need to improve partitioner Placement Vcycling Conclusions Capo placer is scalable and competitive freely available for research and commercial use Better recursive bisection better routability improving RB still makes sense (e.g., as proposed) improving min-cut partitioning still makes sense Weighted wirelength is not a good objective better HPWL better routability - not clear! We draw conclusions only about min-cut

Folklore: analytical placements are hard to route Other WL minimization techniques may be better or worse Min-cut may be a better objective ! Open Questions Need transparent routability improvement not to affect wirelength of routable placements Is recursive bisection [done right] still the best method ? you can download Capo and compare http://vlsicad.cs.ucla.edu/GSRC/bookshelf/Slots/Pla cement

Recently Viewed Presentations

  • Diapositive 1 - belhenniche.com

    Diapositive 1 - belhenniche.com

    A et B12 contrôle l 'activité des ostéoblastes et ostéoclastes Fracture et réparation de l 'os Réparation d 'une fracture A : formation d 'un hématome (6 à 8 heures après la facture) B : formation d 'un cal fibro-...
  • Perspective & Quick Sketch Methods Student Samples Perspective

    Perspective & Quick Sketch Methods Student Samples Perspective

    Further quick sketch studies were done using the overlay method and developing pure tone drawings, using line & texture or marker only. The studies led to final composite sketches using marker and felt-tip to create line, tone, and texture. Above:...
  • Gynaecology SSG Sept 2015 Research Jenny Forrest, Sub

    Gynaecology SSG Sept 2015 Research Jenny Forrest, Sub

    Trust. Investigator Name. End Date. Target. Recruitment . 2015/2016 Recruitment . RTT. INTERLACE. 11775. ... NCRN - 2746 / ARIEL 3 - Rucaparib in platinum-sensitive high-grade gynaecological cancer. 2. ProGem2 - Acelarin(NUC1031) plus Carboplatin for recurrent ovarian cancer. 14.
  • Folie 1 - uni-freiburg.de

    Folie 1 - uni-freiburg.de

    Department of Empirical Research and Econometrics Macroeconometrics Winter Term 2007/2008 Course Outline Organizational Issues Dr. Sevtap Kestel Office hours: Mo.,Wed.,Thurs. 16:00-17:00 Room 2338 Exam date: 10th or 11th March 2008 Tutor: Mr. Anthony Strittmatter E-mails: [email protected] [email protected] Course Structure March...
  • Comparing Bonding - Nicks Class Site

    Comparing Bonding - Nicks Class Site

    Metallic Covalent Ionic State at room temperature Particles in structure Type of structure Bonding The type of bonding in a substance affects the structure of that substance. giant ionic millions of ions solid lattice simple few atoms usually liquid or...
  • Global Trade Liquidity Program - World Bank

    Global Trade Liquidity Program - World Bank

    GTLP mobilizes liquidity and guarantee public sector and the private sector. GTLP partners with global, regional or local banks to channel liquidity to banks in the developing world in two ways: i) a 40% risk funded participation, and ii) short...
  • UNLOCKING PROSPECTS IN NORTHERN ORIGIN VEGETABLES THROUGH PRIVATE

    UNLOCKING PROSPECTS IN NORTHERN ORIGIN VEGETABLES THROUGH PRIVATE

    "Professionalising" vegetable production (e.g., intensification vs. extensification) Addressing financing, information and coordination failures. Private technology and input companies' (e.g., seed companies) incentives to develop larger customer base and establish footprints. Buyers & category managers' incentive to diversify sourcing ...
  • Magnets & Electricity - Patterson Elementary School

    Magnets & Electricity - Patterson Elementary School

    Magnets & Electricity Vocabulary Magnets Magnet an object that can push or pick up materials made of iron, steel, or nickel Attract to cause to draw near or adhere by physical force. Magnetic poles are attracted to their opposites. Repel...