ROAD: Routability Analysis & Diagnosis Based on SAT Techniques SLIP 2018 (Published) ISPD 2019 (Accepted) CK Cheng CSE Department UC San Diego 1 PHYSICAL DESIGN GETTING HARDER Keep Scaling Technologies Design Rule Complexity Rising More and more complex of Place & Routing in Physical Design !! 2/47 INTRODUCTION: DESIGN PROCEDURE OF PHYSICAL DESIGN Efforts to improve pin accessibility Failure to produce routable (or routed) design in each step loop-back of PD procedure undesired additional design cost BEOL-aware cell layout design Gate Netlist routing-driven placement Migration, congestion Placement by (1) or (2) Yes Routing ECO (Engineering Change Order) No IF Unroutable Routable? New detailed routing algorithm pin-access planning DRC violations
manufacturability Routed Layout 3/47 INTRODUCTION : DESIGN RULES Performance Design Rule Interconnect parasites Electronic migration Geometry Design Rules Minimum area rule End of line spacing rule: minimal distance between two ends of wire segments Via rules: minimal spacing between two vias, and stacked via rule. Design Processes to mitigate ProcessDesign Gap LELE (litho-etch-litho-etch) SADP (self-aligned double patterning) SAQP (self-aligned quadruple patterning) 4/47 INTRODUCTION : NEXT GEN LITHO. (EUV) Resource Requirement Utility Electrical power (kW) Cooling water flow (L/min) Gas lines https://en.wikipedia.org/wiki/Extreme_ultraviolet_lithography 90 W output ArF immersion double patterning 200 W output EUV 532 1600 6 49 75 3 5/47 DESIGN RULE-CORRECT ROUTABILITY ANALYSIS ILP: Optimal but 1048s (~18min) !
Gate Netlist Placement Given Pin-Layout SAT : Not Optimized but 2s !!!!! Power Rail Pin 16 15 14 11 4 6 2 19 8 9 17 21 23 22 20 Routable? SAT Method Quick go/no-go Decision 18 Pin 12 13 0 Via3-4 M1-2 1 M2-3 5 3 M3-4
7 10 6/47 WHAT IS SAT (BOOLEAN SATISFIABILITY) ? SAT (Boolean Satisfiability) Find an assignment so that the formula is true (1) (Satisfiable) , or prove that no such assignment exists (0) (Unsatisfiable) 1, 1, 1() ( ) ( ) Usually, Product of Sum (i.e. CNF) is normal representation for SAT formula Truth Table X Y F(x,y) 0 0 1 0 1 0 1 0 0 1 1 1 Product of Sum (CNF)
Sum of Product (DNF) ( ) ( ) ( ) ( ) Equivalent Representations 7/47 SAT-BASED FRAMEWORK FOR ROUTABILITY ANALYSIS ILP-based routability optimization SAT-based routability analysis Fast and Precise Routability Analysis wit Our Proposed Framework Routability Analysis Flow Logic Simplification ILP Patterns per ILP Formula Testcase (i.e., Switchbox) Generation SAT-Friendly ILP Formulation Logic Minimizer ILP-to-SAT Conversion Espresso  Solvers Results of Routability Analysis ILP Solver SAT Solver CPLEX  plingeling  by ILP
 IBM ILOG CPLEX, http://www.ilog.com/products/cplex/.  plingeling, Multi-Threading SAT Solver, http://fmv.jku.at/lingeling/. by SAT Inputs - #Vertical and Horizontal Tracks - Pin Density - Switchboxes 3D Routing Graph Source-Sink Definition ILP Inputfiles SAT Inputfiles Reduced SAT Inputfiles ILP Result: Routing Feasibility, Wirelength, Metal Cost, etc. SAT Result: Routing Feasibility, SAT Solution if Satisfiable 8/47 NEXT STEP : ROUTABILITY DIAGNOSIS AND ESTIMATION Conflict Diagnosis in Unroutable Case using SAT Technique Exact Location of Conflict Fast Trouble-shooting for Designer Exact Conflict Relation Guideline for Design Rule Manager Routability Quantification Estimate the routing possibility upon given switch-box go/no-go decision for revision of switch-boxgo/no-go decision for revision of switch-box 9/47 RODE : ROUTABILITY DIAGNOSIS & ESTIMATION Routability Analysis Using SAT Formulation Estimation Diagnosis
Unroutable Layout Node : U (variable) MUS MUS Extraction (Minimal Unsatisfiable Subset) Clause Minimization Initial Propagation Ub Edge : D (clause) (Geometric Information of Switch-Box) Conflict Region Decision (DLS) Us (Decision with Longest-Path Search) Propagation (PTA/PFA) BCP Iteration PIG Up (Propagation with True/False Assignment) No Conflict? Yes Conflict Information (Conflict Geometry / Design Rule) DAG : H(U,D) 10/47 RODE : NOTATION & PIN-LAYOUT CONFIGURATION
M1 in G M2 in G 2 1 2 1 2 1 2 2 M3 in G 1 PIN #1 V-Track Power Rail Grid M4 in G H-Track Outer-Pin Connection 11/47 PROPOSED SAT FORMULATION DIAGRAM The Multi-commodity network flow formulation (F) Conditional Design Rule (D) () Commodity Flow Conservation (CFC) Exclusiveness
Use of Vertex (EUV) ( , ) Conditional Design Rules (D) 1. End-of-Line Space Rule (EOL) 2. Minimum Area Rule (MAR) 3. Via Rule (VR) , Edge Assignment (EA) Metal Segment (MS) , Geometry Variable (GV) , Flow Formulation (F) 12/47 SAT FORMULATION FLOW FORMULATION (F) Commodity Flow Conservation (CFC) Vertex is not a source or sink 1) Only one incoming/outgoing pair is allowable for all commodities. 2) This commodity dont use this vertex.
Vertex is a source or sink Exactly-One (EO) Constraint 13/47 SAT FORMULATION FLOW FORMULATION (F) Exclusiveness Use of Vertex (EUV) Vertex is not a source or sink 1) Only n net flow can be assigned if a certain edge is occupied by the n net 2) This net dont use this vertex.
Vertex is a source or sink At-Most-One (AMO) Net Constraint 14/47 SAT FORMULATION FLOW FORMULATION (F) Edge Assignment (EA) ( , ) , Logical Imply. : edge is used by n net if m commodity of n net use this edge It requires for multi-commodity flow Metal Segment (and Exclusiveness Use of Edge) (MS) AMO Constraint 15/47
SAT FORMULATION DESIGN RULE FORMULATION (D) Geometric Variable (GV) End-of-Line indicator of each vertex for geometric conditional design rule. ,( , 2) =1 ( , 2) ,(1, ) =1 ,(2, ) =1 (0, ) (1, ) (2, ) ( , 3) ,( ,1) =1 ( ,1) 16/47 SAT FORMULATION DESIGN RULE FORMULATION (D) Minimum Area Rule (MAR) A metal segment must cover at least three vertices (AMO) , + , + , + , 1, True Table Karnaugh Map CNF conversion by Espresso (Logic Minimizer) Violation , = , =1 , = , =0 No Violation , =1 , = , = , =0
17/47 SAT FORMULATION DESIGN RULE FORMULATION (D) End-of-Line (EOL) Space Rule The minimum distance between tips must be larger than 2 Manhattan distance (AMO) Violation Violation No Violation 18/47 SAT FORMULATION DESIGN RULE FORMULATION (D) Via Rule (VR) The distance between two vias should be larger sqrt(2) Euclidean Distance (AMO) + 2
+ 2 +1 Violation +1 No Violation 19/47 SAT FORMULATION DESIGN RULES ARE ALWAYS MIXED Mixed Design Rule Violation
1 2 VIA(M1M2) (a) Violation (VR OK, EOL Fail) 1 2 (b) Violation (VR OK, EOL Fail) VIA(M2M3) No Violation Violation No Violation No Violation 20/47 DESIGN RULE-CORRECT ROUTABILITY ANALYSIS Flow Feasibility (F) Conjunction of each subsets Design Rule Formulation (D) Design Rule-correct Routability ( R ) L : Layout Structure Map the geometry information of the switch box 21/47 (1) MINIMAL UNSATISFIABLE SUBSET (MUS) 22/47 (2) BOOLEAN CONSTRAINT PROPAGATION (BCP)
BCP The procedure is based on Unit Clauses If a set of clauses contains the unit clause , the other clauses are simplified by the application of the two following rules Every clause containing is removed In every clause that contains this literal is deleted * BCP Iteration Example Clause set: https://en.wikipedia.org/wiki/Unit_propagation 23/47 (3) PARTIAL IMPLICATION GRAPH (PIG) PIG in Our Framework Directed Acyclic Graph which Nodes are Variables, Edges are Clauses. The implication relation between variable assignment from constraint clause PIG of the propagation Clause set: a c d https://en.wikipedia.org/wiki/Unit_propagation 24/47 AFTER INITIAL PROPAGATION The intersection range between GV and MS Estimated Conflict Range Power Rail 0 1 2 7 9 12 4 3
8 25/47 DLS (DECISION WITH LONGEST-PATH SEARCH) Longest-path search is most comprehensive explanation about failure Via Position / Direction of Element are determined at DLS phase Blocked via (M1 M2) 0 1 2 7 9 12 4 Selected ! 1 3 2 7 9 12 4 3 1 2 7 9 12 4 3 1 2 3 4
With One Row of Pins With Two Row of Pins 32/47 ROUTABILITY ESTIMATION UNROUTABILITY TREND U n ro u ta b ility (a vg .) Unroutability Comparison vs. the number of pin row 90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 50 60 70 80 90 100 avg. The Number of Grid 33/47 ROUTABILITY DIAGNOSIS ROOT CAUSES The Root causes of routing failure Conflict Pin-shape (CP) : Pin-Accessibility Problem! Simple-CP : Intrinsic Pattern in given Pin-layout Propagated-CP : Simple-CP appears after some propagations Routing Congestion The lack of routing resources such as #Track and #Layer 34/47 UNROUTABLE LAYOUT CLASSIFICATION SIMPLE-CP
Diagnosis Performance (Complexity and Execution Time) depends on the root causes of routing failure CP Pattern Case is less than 30 seconds to get the result. Routing Congestion Case is relatively hard to find the failure causes. 38/47 ROUTABILITY DIAGNOSIS ROOT CAUSE CONFIGURATION Same Grid Number with different number of pins row 39/47 PUBLICATIONS WITH THIS PROJECT 1. Ilgweon Kang, Dongwon Park, Changho Han, Chung-Kuan Cheng. Fast and Precise Routability Analysis with Conditional Design Rules. SLIP 2018 2. Dongwon Park, Ilgweon Kang, Yeseong Kim, Sicun Gao, Bil Lin and Chung-Kuan Cheng. RODE: Efficient Routability Diagnosis and Estimation Framework Based on SAT Techniques. ISPD 2019 (Will Published at 2019/April) 3. Journal Extension will be prepared soon. 40/47 SAT Solving Performance Improvement 41 CSP TO SAT Converting Encoding Method Direct Encoding (Sparse Encoding) Ordering Encoding Log Encoding CSP (Constraint Satisfaction Problem) Constraint Optimization Constraint Simplification ABC (AIGs) MIG Techniques SAT (Boolean Satisfiability) CNF Optimization Preprocessing (BCP) Encoding Techniques for EO / AMO SAT Encodings of Finite CSPs
42/47 ROAD IMPROVEMENT (1) SUPER OUTER NODE (SON) Super Outer Node : Representation Simplifying Conventional Super Node Super Outer Node (SON) 43/47 ROAD IMPROVEMENT (2) ENCODING TECHNIQUES FOR AMO/EO Commodity Flow Conservation (CFC) Exclusiveness Use of Vertex (EUV) 1. End-of-Line Space Rule (EOL) 2. Minimum Area Rule (MAR) Conditional Design Rules 3. Via Rule (VR) Edge Assignment (EA) Metal Segment (MS) Layout Structure Map Type Formulation CFC (Commodity Flow Conservation) Flow Design Rule
EUV (Exclusiveness Use of Vertex) Geometry Variable (GV) CSP Side (Constraints) (Case I) EO (Exactly-one) (Case II) Neither(0) or Flow(2) (Case I) AMO (At-Most-One) Net SAT Side (CNF Representation) Bimander or Commander AMO Net Variable (Commander Encoding) Bimander or Commander AMO (Case II) Neither (0) or Flow (2) MIG Technique can be a candidate - EA (Edge Assignment) Logically Imply - MS (Metal Segment) AMO Net GV (Geometric Variable) See the variable hierarchy MAR (Minimum Area Rule) AMO Pairwise AMO (Only 4 variables) EOL (End-of-Line Rule) AMO Pairwise AMO (Only 3 variables)
VR (Via Rule) AMO Pairwise AMO (Only 4 variables) Metal Variable (Commander Encoding) Bimander or Commander AMO - 44/47 ROAD IMPROVEMENT (3) PREPROCESSING : BCP BCP The procedure is based on Unit Clauses If a set of clauses contains the unit clause , the other clauses are simplified by the application of the two following rules Every clause containing is removed In every clause that contains this literal is deleted * BCP Iteration Example Clause set: 45/47 SIMPLIFIED SAT FORMULATION In Largest Case (20x19 x 90% Density) of SLIP 2018 29.4% of #Variable / 0.9% of #Literal / 0.7% of #Clause are acquired using simplification techniques ( SON , Commander Encoding for AMO/EO , BCP Preprocessing ) #Net = Number of Net , #Pin = Number of Pin, #OTP = Number of outer directional pin SLIP 2018 IDX #VT #HT Density #Net #Pin #OTP #Var (Reduced) 01 05 06 07 08 20
SON / Commander Encoding / BCP #Cla #Lit (Reduced) (Reduced) RA Runtime #Var(Cmd) Ratio (s) 96,473,257 48,337,366 UR 85,526,509 42,952,726 R 68,799,905 34,618,703 R 162,026,012 80,580,373 R 62,627,649 31,494,496 R 95,090,666.4 47,596,732.8 32,451,956.3 16,009,097.1 94,972,296 47,453,133 UR 193,827,142 96,163,509 UR 406,276,249 201,309,416 UR 116,477,593 58,134,373 UR 69,318,982 34,868,818 UR 176,174,452.4 87,585,849.8 111,679,639.3 55,172,057.6 122,322,363 61,035,488 UR 309,764,276 153,877,808 UR 87,443,954 43,751,284 UR 148,568,883 74,077,401 UR 206,410,613 102,454,952 UR 174,902,017.8 87,039,386.6 71,048,794.6 35,173,593.0 173,294,545 86,233,255 UR 292,560,379 145,452,322 UR 221,727,502 110,385,191 UR 274,654,058 136,427,298 UR 312,811,632 154,873,505 UR 255,009,623.2 126,674,314.2 46,407,773.9 22,890,112.3 16.3 26.7 23.3 34.7 23.1 24.8 5.5 18.5 31.2 65.0 20.0 22.8
Develop a thesis statement that could focus an argument in response to each of the following prompts. Discuss why you think that the structure (open, closed, counterargument) you chose would be appropriate or effective. You need a thesis statement and...
Liz Rankin. Constantinos Regas. 3rd CPA Westminster Workshop: The Public Accounts Committee. 26 June 2013. The Scrutiny UnitMaking numbers talk. Agenda. About the Scrutiny Unit. How we support scrutiny in the Commons. Challenges. Examples of the work we do. 2.
OGS Contract NYPA Energy Efficiencies Services Program Master Services Agreement A team from the Office for Capital Facilities together with the Office of University Counsel, has executed a master agreement with the New York State Power Authority, for Construction and...
At the 2008 Beijing Olympic Games, David Davies won the silver medal in the swimming 10 kilometre marathon event, in a time of 1 hour 51 minutes and 53.1 seconds.Explain how the majority of energy used during the race would...
The strength one can accumulate from being led or by holding the hands of those who care, can empower and enable one's mind to utilize their own two hands for the better. Although the characters in the film "Two Hands"...
Dynamite (TNT) 를 개발한 . 노벨급의. 모기퇴치 기술 모기퇴치와 설치 기술 (Korean Traditional Culture Technology) 전통 생활문화 지혜: Korean Traditional Culture Technology - 모기불(Mosquito repellent burn) - 모기 차단의 지혜 (거주지역 외 20~30M 멀리 설치) - 초저녁 설치 지혜 (해지기...
Four Futures for the ArcticUnpacking the Food, Water, Energy Nexus. ... Four Futures for the Arctic. Two Narratives. Vulnerability&Adaptation. A Frontier. ... University of New Hampshire. Richard Lammers, University of New Hampshire.
Ready to download the document? Go ahead and hit continue!