layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # Multi-level Circuit Partitioning ✂️ @luk036 👨‍💻 · 2026 📅 <https://github.com/luk036/ckpttnpy> --- ### 📋 Agenda .pull-left[ **Part 1: Overview** 🎯 - Fundamental Problem 📋 - Features ✨ **Part 2: Strategy** 🛠️ - Restore Optimal Solution 💾 - Trade-offs ⚖️ ] .pull-right[ **Part 3: Contribution** 🚀 - Possible Contributions 🤏 ] --- class: nord-light, middle, center ## Part 1: Overview 🎯 --- ## Overview 📋 - Fundamental EDA problem - Bi-partition vs. K-way partitioning - Basic strategy: local search - Explore circuit locality 🏘️ - Incremental cost - FM algorithm: - Single Move => easy stuck to local minimum. - Integer cost => bucket sort. - Last-in-first-out (LIFO) - Multi-level extension: - Both cost and constraints are additive, implies - Coarse-grain hypergraph a good approximation of the fine-grain ancestor --- ### ✨ Features - Try to keep it simple but not simpler - Special handling for 2-pin nets and 3-pin nets - Primal-dual minimum maximal matching for clustering - Apply exhaustive search on top level 🔲 --- class: nord-light, middle, center ## Part 2: Strategy 🛠️ --- ### 💾 Choices of Restore Optimal Solution 1. Snapshot 📸 2. Re-apply 🔄 3. Roll-back 🔙 .mermaid[ <pre> graph LR S[Partition State] --> Strategy{Strategy} Strategy --> Snap[Snapshot 📸] Strategy --> Reap[Re-apply 🔄] Strategy --> Roll[Roll-back 🔙] Snap --> Copy[Store Copy] Reap --> Recomp[Recompute Moves] Roll --> Undo[Undo Moves] style S fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px style Snap fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px style Reap fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px style Roll fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px </pre> ] --- ### Trade-off ⚖️ - Early stop, or not - Ignore high-fanout nets, or not - Legalization vs. optimization --- class: nord-light, middle, center ## Part 3: Contribution 🚀 --- ### Possible contribution 🤏 - Testing - Porting to C++ - Documentation - Try Roll-back strategy --- count: false class: nord-dark, middle, center # 🙋 Q&A ### Questions? Discussion? 💬 --- count: false class: nord-dark, middle, center # 👏 Thank You ### Code: github.com/luk036/ckpttnpy 🐙 Slides built with Remark.js 🎉 | KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙