class: nord-dark, middle, center # 🔴 Redundant Via Insertion + MP @luk036 👨‍💻 · 2026 📅 --- ### 📋 Agenda .pull-left[ **Part 1: Background** 🧠 - Via Insertion Flow - RVI-aware Routing **Part 2: Formulations** 📐 - Max Bipartite Matching - Max Independent Set ] .pull-right[ **Part 3: New Approach** 🔬 - Combined Formulation - RVI + DP + DSA ] --- ### 🔄 Via Insertion Flow .mermaid[ <pre> flowchart LR A["Layout"] --> B["Identify Via Positions"] B --> C["Redundant Via Check"] C --> D["Insert"] D --> E["Verify"] style A fill:#4caf50 style B fill:#2196f3 style C fill:#ff9800 style D fill:#9c27b0 style E fill:#4caf50 </pre> ] --- class: center, middle # 👋 Introduction <!--  --> --- ### 🔴 Redundant Via Insertion - 🔄 Also known as double via insertion. - 💡 Original idea is simple: if one via fails, another one still can work.  --- ### 🛠️ RVI-aware routing vs. Post-routing RVI - 📌 Post-routing RVI was popular (many EDA tools have this feature) - 🎯 Main goal of RVI: improve yield (nice-to-have) - ⏱️ Main goal of routing: timing (must satisfy) - 🔄 RVI consumes very little routing resource. - ⚡ Reduce via resistance. No negative impact on the timing. - ✅ RVI-aware routing has better result. --- ### 🖨️ Lithography effect - 🔬 In sub-10nm, the issue become complicated. - 🌀 Via could be generated by multiple patterning, complementary e-beam, Directed Self-Assembly, or EUV. --- ### 🎨 Lithography-aware RVI vs. RVI-aware lithography - ⚠️ In reality, if not address the lithographic coloring conflict, both primal via and redundant via will fail. - 🖌️ Lithography-aware RVI at routing stage has been proposed [@yuan2009double, @ding2017self]. - 🤯 However, it will complicate the router. - 🔄 Another possible way is to generate as many as RV candidates as possible during the routing stage, and then select the candidates later during the lithography optimization. - ✅ It is possible because the RVI consumes very little routing resource and does not induce any negative impact to the timing. 'Double patterning lithography friendly detailed routing with redundant via consideration' --- ### 🔄 Maximum Bipartite Matching Formulation - 📜 Historically, the pure RVI problem was formulated as maximum bipartite matching problem. - ⚡ Can be solved in polynomial time by using a max-flow algorithm. - 📊 Can be formulated in an ILP form. - 🎯 The objective is "correct": - ✅ each primal via (PV) matches at least one redundant via (RV). - ⚠️ However, the formulation does not take care of conflicts between RV's. - 📌 In [?], the problem was formulated as min-cost max-flow problem. --- ### 🧩 Maximum Independent Set Formulation - 🔄 Later, the problem was formulated as a _maximum independent set_ problem (MIS) - ✅ Can take care of conflicts between RV's. - 📊 Can be formulated in ILP form. - ⚠️ However, the objective is "wrong": - 🔄 some PV's may get more than one RV, while some others may get none of RV. - 🧠 MIS is NP-hard for general graphs. --- ### 🆕 New formulation - 🔄 Combine of two formulations is what we want (Yes!). - 🤝 Matching PV and RV as many as possible with independent set constraints. - 📊 Can be formulated in ILP form. - ❓ NP-hard? If yes, any good heuristic? --- ### ✂️ Minimum Vertex Cover Formulation - 🔄 MIS is equivalent to minimum vertex cover problem (MVCP) - 📈 Maximizing #RV inserted is equivalent to minimizing #RV removed. - 📊 ILP form of MVCP: $$\begin{array}{ll} \text{minimize} & \sum_{v \in {\color{salmon}V} } x_v \\ \text{subject to} & x_u + x_v \geq 1 \; \forall (u,v) \in {\color{lime}E} \\ & x_v \in \{0,1\} \; \forall v \in {\color{salmon}V} \end{array}$$ - 🔄 We only keep the constraint part. --- ### 🎨 Considering RVI + DP - 🖌️ Assume the original design already has a valid coloring solution, i.e., odd-cycle free. - 🔄 However, reassign the coloring of PV may help to resolve the conflicts between RV's and PV's - ✂️ Vertex Cover constraint is replaced with Odd Cycle Cover constraint. - 🎯 The objective is unchanged. - ❓ NP-hard? If yes, any good heuristic? - 🤔 How about Triple Patterning? --- ### 🌀 Considering RVI + DSA + DP - 🧪 Directed self-assembly is still not mature. - 🔳 2x2 four-hole pattern for 1PV+2RV+1Dummy may not be a good idea. Better than 1PV alone? - 🧩 The template assignment problem can be formulated as a set packing problem. - 🔄 One possible way is to generate different sets of maximal set packing solution and then solve the RVI + DP problems. Choose the best one as the final solution. Better than ILP if the problem size is small? --- class: nord-dark, middle, center .pull-left[ # Q&A 🎤 ] .pull-right[  ]