layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 🦀 Porting netlistx from Python to Rust ### Bringing EDA Algorithms to Systems Programming @luk036 👨‍💻 · 2026 📅 · Network Optimization --- #### 📋 Agenda .pull-left[ #### 1️⃣ Motivation - Why Rust for EDA? 🦀 - Project architecture 🏗️ #### 2️⃣ Core Data Structures - Netlist representation 📊 - Hypergraph model 🔗 #### 3️⃣ Cover Algorithms - Primal-dual framework 🎯 - Vertex / Cycle / Odd-cycle cover ] .pull-right[ #### 4️⃣ Advanced Algorithms - Hadlock's MAX-CUT ✂️ - Christofides TSP 🗺️ - Randomized cover 🎲 - **GPU-accelerated** Pitt trials 🎮 #### 5️⃣ I/O & Testing - Yosys JSON reader 📄 - Factory functions 🏭 - **194 tests** — all passing ✅ #### 6️⃣ Conclusion - Achievements 🏆 - Future work 🔮 ] --- class: nord-light, middle, center ## 🦀 Why Rust for EDA Algorithms? --- ### ❓ The Problem Python is great for **prototyping** but has limitations in production EDA: .pull-left[ #### 🐍 Python Issues - **GIL** limits parallelism 🧵 - **High memory** overhead 💾 - **No zero-cost** abstractions 💸 - **Dynamic typing** → runtime errors 💥 - **C extension** complexity 🔧 ] .pull-right[ #### 🦀 Rust Advantages - **Zero-cost** abstractions ⚡ - **No GC**, no GIL 🚀 - **Memory safety** at compile time 🛡️ - **Fearless concurrency** with Rayon 🧵 - **C FFI** interoperability 🔄 - **Strong typing** → fewer bugs ✅ ] --- ### 📊 Performance Comparison | Feature | Python 🐍 | Rust 🦀 | |---------|-----------|---------| | Loop overhead | ~50-100 ns/iter | ~0 ns (LLVM opt) | | Memory per graph node | ~200+ bytes (PyObject) | ~32-64 bytes | | Parallel speedup | GIL-bound | Near-linear (Rayon) | | Type safety | Runtime | Compile-time | | Package distribution | pip install | cargo build | > 🎯 **Goal**: Port all features from Python `netlistx` to Rust `netlistx-rs` while maintaining algorithmic correctness --- class: nord-light, middle, center ## 🏗️ Architecture Overview --- ### 📦 Project Structure .mermaid[ <pre> graph TD subgraph Python["Python netlistx 🐍"] P1[netlist.py] --> P2[netlist_algo.py] P1 --> P3[cover.py] P1 --> P4[graph_algo.py] P1 --> P5[hadlock.py] P1 --> P6[tsp.py] P1 --> P7[rand_cover.py] end subgraph Rust["Rust netlistx-rs 🦀"] R1[netlist.rs] --> R2[netlist_algo.rs] R1 --> R3[cover.rs] R1 --> R4[graph_cover.rs] R1 --> R5[graph_algo.rs] R1 --> R6[hadlock.rs] R1 --> R7[tsp.rs] R1 --> R8[rand_cover.rs] R1 --> R9[factory.rs] R1 --> R10[io.rs] R1 --> R11[rand_cover_gpu.rs 🎮] end Python -->|"Port"| Rust R3 -->|"extends"| R4 R10 -->|"read/write"| R1 R9 -->|"factory"| R1 style Python fill:#4caf50 style Rust fill:#2196f3 style P1 fill:#4caf50 style R1 fill:#2196f3 </pre> ] --- ### 🔗 Core Dependency Graph .mermaid[ <pre> graph LR N["netlist.rs\nNetlist, NetlistBuilder"] --> NA["netlist_algo.rs\nmin_vertex_cover\nmin_maximal_matching"] N --> C["cover.rs\nmin_hyper_vertex_cover"] N --> RC["rand_cover.rs\nrand_hyper_vertex_cover"] N --> P["partitioning.rs\nFM, KL algorithms"] N --> S["statistics.rs\nNetlistStats"] N --> F["factory.rs\ncreate_inverter\ndrawf, test\nrandom_hgraph"] N --> IO["io.rs\nread_yosys_json\nread_node_link_json"] subgraph Algorithm["Algorithm Modules"] GA["graph_algo.rs\nmin_vertex_cover_fast\nmin_maximal_independent_set"] GC["graph_cover.rs\nmin_cycle_cover\nmin_odd_cycle_cover"] H["hadlock.rs\nsolve_hadlock_max_cut"] T["tsp.rs\nchristofides_tsp\ntwo_opt"] end GA -.->|"uses petgraph\nGraph directly"| PET[petgraph] GC -.-> PET H -.-> PET T -.-> PET N --- PET style N fill:#ff9800 style GA fill:#2196f3 style GC fill:#2196f3 style H fill:#9c27b0 style T fill:#4caf50 style F fill:#e91e63 style IO fill:#00bcd4 </pre> ] --- class: nord-light, middle, center ## 📊 Core Netlist Data Structure --- ### 🏛️ Netlist Representation A **netlist** is a bipartite hypergraph connecting **modules** (cells) to **nets** (wires): $$\begin{aligned} \text{Netlist} &= (V_m \cup V_n, E) \\ V_m &= \{\text{modules}\} \\ V_n &= \{\text{nets}\} \\ E &\subseteq V_n \times V_m \quad \text{(edges connecting net→module)} \end{aligned}$$ ```rust pub struct Netlist { pub grph: Graph<String, (), Undirected>, // petgraph pub modules: IndexSet<String>, pub nets: IndexSet<String>, pub module_weight: Option<IndexMap<String, i32>>, pub module_fixed: HashSet<String>, pub num_pads: i32, pub max_degree: u32, } ``` --- ### 🎯 Key Design Decisions .pull-left[ #### ✅ Python's approach - `networkx.Graph` with integer node IDs - `modules: List[int]`, `nets: List[int]` - `RepeatArray` for uniform weights - Dict-based module weights ] .pull-right[ #### 🦀 Rust's approach - `petgraph::Graph` with `IndexSet<String>` names - `IndexMap<String, NodeIndex>` for O(1) lookups - `Option<IndexMap<String, i32>>` for weights - Builder pattern for construction ] **Key difference**: Rust uses **string names** for modules/nets instead of integer indices, making the API self-documenting and type-safe. --- ### 🔨 Builder Pattern ```rust let netlist = NetlistBuilder::new() .add_module("cell_a") .add_module("cell_b") .add_net("net1") .add_net("net2") .add_edge("net1", "cell_a") .add_edge("net1", "cell_b") .add_edge("net2", "cell_b") .add_edge("net2", "cell_c") .with_pads(2) .build() .unwrap(); ``` > 🧩 Fluent API matches Python's flexibility with Rust's type safety --- class: nord-light, middle, center ## 🎯 Cover Algorithms --- ### 📐 Primal-Dual Framework The **primal-dual** method iteratively builds a cover: $$\begin{array}{lll} \min & \sum_{v \in V} w_v \cdot x_v \\ \text{s.t.} & \sum_{v \in S} x_v \ge 1 & \forall S \in \mathcal{S} \\ & x_v \in \{0, 1\} \end{array}$$ **Key insight**: Maintain a "gap" $g_v$ for each element. When a constraint $S$ is violated, pick the element with minimum gap and add it to the cover. ```rust pub fn pd_cover<F, W>( mut violate: F, // Returns violating sets weight: &HashMap<String, W>, soln: &mut HashSet<String>, ) -> (HashSet<String>, W) ``` --- ### 🎯 Three Covering Problems .mermaid[ <pre> graph TD PD["pd_cover()\nGeneric Primal-Dual"] --> VC["min_vertex_cover()\nCover every edge"] PD --> CC["min_cycle_cover()\nCover every cycle"] PD --> OC["min_odd_cycle_cover()\nCover every odd cycle"] VC --> VC1["Pick min-gap endpoint\nper uncovered edge"] CC --> CC1["BFS cycle detection\n→ cover one vertex per cycle"] OC --> OC1["BFS with bipartite coloring\n→ find odd cycles only"] style PD fill:#ff9800 style VC fill:#4caf50 style CC fill:#2196f3 style OC fill:#9c27b0 </pre> ] --- ### 🧪 Reverse-Delete Post-Processing After the primal-dual phase, we **remove redundant** elements: ```text Phase 1 — Forward: For each violation S: v* = argmin gap[v] for v in S add v* to solution update gap for all v in S Phase 2 — Reverse-Delete: For v in added_order (reversed): remove v from solution if solution is still valid → keep removed else → restore v ``` > ✅ Guarantees the cover is **minimal** — no vertex is redundant --- ### 🔍 Cycle Detection via BFS For cycle/odd-cycle cover, we need to find cycles efficiently: .mermaid[ <pre> graph TD subgraph BFS["BFS Tree"] A --> B A --> C B --> D C --> D end D -.->|"Back edge!\nCycle detected"| A style A fill:#4caf50 style B fill:#2196f3 style C fill:#2196f3 style D fill:#f44336 </pre> ] - **BFS** from each unvisited source node - When we encounter an already-visited neighbor (not parent): **cycle found** - Track depth to distinguish cycles from tree edges - For **odd cycles**: use bipartite coloring (same color → odd length) --- class: nord-light, middle, center ## ⚡ Graph Algorithms --- ### 🏃 Min Vertex Cover — Fast Variant Without post-processing, a simpler greedy approach: ```python def min_vertex_cover_fast(ugraph, weight, coverset): gap = copy.copy(weight) for (u, v) in ugraph.edges(): if u in coverset or v in coverset: continue if gap[u] < gap[v]: u, v = v, u # ensure gap[u] >= gap[v] coverset.add(v) gap[u] -= gap[v] gap[v] = 0 return coverset, total_cost ``` **Rust port** uses generics for any weight type `W: Add + Sub + PartialOrd`: ```rust pub fn min_vertex_cover_fast<W>( grph: &Graph<String, (), Undirected>, weight: &HashMap<String, W>, coverset: &mut HashSet<String>, ) -> (HashSet<String>, W) ``` --- ### 🔗 Maximal Independent Set Find a minimal-weight set of vertices with no edges between them: .mermaid[ <pre> graph LR A((A)) --- B((B)) B --- C((C)) A --- C C --- D((D)) D --- E((E)) style A fill:#4caf50,color:#fff style D fill:#4caf50,color:#fff style B fill:#999 style C fill:#999 style E fill:#999 </pre> ] **Algorithm**: For each uncovered vertex, pick the one with minimum gap among it and its neighbors, add to independent set, then cover all neighbors. ```rust pub fn min_maximal_independent_set<W>( grph: &Graph<String, (), Undirected>, weight: &HashMap<String, W>, indset: &mut HashSet<String>, dep: &mut HashSet<String>, // dependent (covered) vertices ) -> (HashSet<String>, W) ``` --- class: nord-light, middle, center ## ✂️ Hadlock's MAX-CUT --- ### 🧮 Maximum Cut on Planar Graphs **Hadlock's algorithm** solves MAX-CUT on planar graphs in polynomial time: .mermaid[ <pre> graph TB subgraph Steps["Hadlock's Algorithm"] S1["1. Find planar embedding"] --> S2["2. Build dual graph"] S2 --> S3["3. Identify odd faces"] S3 --> S4["4. MWPM on odd faces"] S4 --> S5["5. Excluded edges → Max Cut"] end S3 -.->|"Odd face = boundary\nhas odd length"| F1(("👻")) S4 -.->|"Minimum Weight\nPerfect Matching"| DP["DP over subsets\nO(n·2ⁿ)"] style Steps fill:#9c27b0 style DP fill:#ff9800 </pre> ] --- ### 🔷 How It Works **Key insight**: For a planar graph, the maximum cut corresponds to the **minimum-weight set of edges whose removal makes the graph bipartite**. $$\text{Max-Cut weight} = \sum_{e \in E} w_e - \sum_{e \in X} w_e$$ Where $X$ is the minimum-weight set of edges breaking all **odd cycles**. In the dual graph, odd cycles correspond to paths between **odd faces**. We find a minimum-weight perfect matching on odd faces, then the dual edges on shortest paths are the excluded primal edges. --- ### 🏗️ Rust Implementation ```rust pub fn solve_hadlock_max_cut( grph: &Graph<String, f64, Undirected>, ) -> HashSet<String> { // 1. Decompose into biconnected components let components = biconnected_components(grph); // 2. For each component: // - Find planar embedding → faces // - Build dual graph // - Find odd faces → MWPM via DP over subsets // - Excluded edges = shortest-path primal edges // 3. Max cut = all edges \setminus excluded } ``` ✅ Includes `validate_max_cut()` to verify bipartiteness --- class: nord-light, middle, center ## 🗺️ Christofides TSP --- ### 🧮 3/2-Approximation for Metric TSP **Christofides algorithm** (1976) guarantees a tour within **1.5× optimal**: .mermaid[ <pre> graph TB subgraph Christofides["Christofides Algorithm"] MST["1. Minimum Spanning Tree"] --> ODD["2. Odd-degree vertices"] ODD --> MWPM["3. Min-Weight Perfect\nMatching on odds"] MST --> COMB["4. Combine MST + Matching\n→ Eulerian multigraph"] MWPM --> COMB COMB --> EULER["5. Eulerian circuit"] EULER --> SHORT["6. Shortcut →\nHamiltonian cycle"] end style Christofides fill:#4caf50 style MWPM fill:#ff9800 style EULER fill:#2196f3 </pre> ] **Why it works**: Adding the matching makes all degrees even → Eulerian circuit exists → shortcutting yields Hamiltonian cycle ≤ $\frac{3}{2} \cdot \text{OPT}$ --- ### 🛠️ Rust Implementation Three key sub-algorithms implemented from scratch: | Component | Implementation | Complexity | |-----------|---------------|------------| | **MST** | Prim's algorithm | $O(\|V\|^2)$ | | **MWPM** | DP over subsets | $O(k \cdot 2^k)$ | | **Eulerian circuit** | Hierholzer's algorithm | $O(\|E\|)$ | | **2-Opt** | Local search refinement | $O(\|V\|^2)$ per pass | ```rust pub fn solve_christofides_2opt_tsp( grph: &Graph<String, f64, Undirected>, ) -> Vec<usize> // Hamiltonian cycle ``` > 🧪 Tested on up to 50-city instances with approximation bound verified --- class: nord-light, middle, center ## 🎲 Randomized Cover Algorithms --- ### 🎯 Pitt's Randomized Algorithm For each uncovered edge $(u, v)$, pick an endpoint with probability **inversely proportional to weight**: $$\Pr(\text{pick } u) = \frac{w(v)}{w(u) + w(v)}, \quad \Pr(\text{pick } v) = \frac{w(u)}{w(u) + w(v)}$$ - **Lighter** vertices are more likely to be selected ✅ - Achieves **2-approximation** in expectation - Supports both regular graphs and **hypergraphs** ### 🧪 Reverse-Delete Post-Processing Same technique as `pd_cover`: remove redundant vertices in reverse order of addition. --- ### 🔄 Multi-Trial Parallel Version ```rust // Sequential multi-trial (best of N) pub fn rand_hyper_vertex_cover_mt_seq(..., num_trials: usize) -> (HashSet<String>, W) // Parallel multi-trial (requires rayon feature) 🧵 pub fn rand_hyper_vertex_cover_mt(..., num_trials: usize) -> (HashSet<String>, W) ``` .mermaid[ <pre> graph LR subgraph Trials["N Independent Trials"] T1["Trial 1\nseed = s+0"] --> R1["Cover 1\ncost = c1"] T2["Trial 2\nseed = s+1"] --> R2["Cover 2\ncost = c2"] TN["Trial N\nseed = s+N-1"] --> RN["Cover N\ncost = cN"] end R1 --> BEST["Best\n(min cost)"] R2 --> BEST RN --> BEST style Trials fill:#2196f3 style BEST fill:#4caf50 </pre> ] --- ### 🚀 GPU-Accelerated Pitt's Algorithm 🎮 Ported from Python `rand_cover_gpu.py` — uses Numba CUDA → Rust `cudarc`: ```cuda extern "C" __global__ void pitt_kernel( const int* edges, int num_edges, const float* weights, int num_vertices, unsigned int* covers, float* costs, unsigned long long* seeds, int num_trials ) { int tid = blockIdx.x * blockDim.x + threadIdx.x; if (tid >= num_trials) return; // ... each thread runs one independent Pitt trial } ``` .mermaid[ <pre> graph TB subgraph GPU["GPU Grid"] direction LR B0["Block 0\n64 threads"] --> T00["Trial 0"] B0 --> T01["Trial 1"] B0 --> T0N["...Trial 63"] B1["Block 1\n64 threads"] --> T10["Trial 64"] B1 --> T1N["...Trial 127"] end B0 --> COLLECT["min cost\ncover"] B1 --> COLLECT COLLECT --> RESULT["Best Cover\n+ total cost"] style GPU fill:#9c27b0 style B0 fill:#2196f3 style B1 fill:#2196f3 style COLLECT fill:#ff9800 style RESULT fill:#4caf50 </pre> ] --- ### ⚡ Rust GPU Wrapper ```rust pub fn rand_vertex_cover_gpu<W>( grph: &Graph<String, (), Undirected>, weight: &HashMap<String, W>, coverset: &HashSet<String>, num_trials: usize, // default 1024 seed: u64, ) -> (HashSet<String>, W) ``` **Three-tier fallback** — with diagnostic logging: | Tier | Backend | Feature Flag | Log Output | |------|---------|-------------|------------| | 🥇 **GPU** | CUDA via `cudarc` + NVRTC | `cuda` | `✅ GPU execution succeeded (N trials)` | | 🥈 **CPU parallel** | Rayon work-stealing | `rayon` | (silent) | | 🥉 **CPU sequential** | Single-threaded loop | (default) | (silent) | **CUDA C kernel** compiled at runtime from `&str` → PTX via NVRTC. 🎯 Build and test: `cargo test --features cuda` ### ✅ Verified GPU Execution GPU kernel **confirmed running** on CUDA 12.3 / Nsight Compute 2023: ``` [rand_cover_gpu] ✅ GPU execution succeeded (64 trials) ``` Profile with **`ncu`** (Nsight Compute, not deprecated `nvprof`): ``` ncu --kernel-name regex:pitt --set full \ target\debug\deps\netlistx_rs-*.exe \ rand_cover_gpu::tests::test_gpu_triangle --nocapture ``` ⚠️ Windows users must first enable GPU performance counters in NVIDIA Control Panel → Developer → "Allow access to GPU Performance Counters for all users" ### 🔍 Diagnosing GPU vs CPU Execution Watch stderr for the diagnostic prefix: | Message | Meaning | |---------|---------| | `✅ GPU execution succeeded` | CUDA kernel ran on GPU 🎮 | | `⚠️ CUDA failed: ...` | Error — falling back to CPU 🔄 | | (silent) | Running on CPU (no `cuda` feature) 💻 | --- class: nord-light, middle, center ## 🏭 Factory Functions & Testcases --- ### 🧪 Test Netlist Generators ```rust // Simple inverter circuit pub fn create_inverter() -> Netlist // 3 modules, 2 nets // Numeric ID variant pub fn create_inverter2() -> Netlist // Larger test circuit pub fn create_drawf() -> Netlist // 7 modules, 6 nets, 14 pins // Weighted test pub fn create_test_netlist() -> Netlist // weights 533, 543, 532 // Random bipartite hypergraph pub fn create_random_hgraph(N: u32, M: u32, eta: f64, seed: u64) -> Netlist ``` > 🎯 Used by **194 tests** to validate algorithm correctness --- ### 📁 Test Data Files Three node-link JSON files ported from Python `testcases/`: | File | Nodes | Edges | Description | |------|-------|-------|-------------| | `drawf.json` | 13 | 14 | Small test circuit | | `fix.json` | — | — | Medium test | | `p1.json` | 1735 | — | **833 modules, 902 nets, 81 pads** | Plus **3 Yosys JSON files** in `yosys_testcases/`: | File | Cells | Ports | Description | |------|-------|-------|-------------| | `sphere_netlist.json` | 56+ | 9 | Multiple modules | | `sphere3hopf_simple.json` | 180+ | 8 | Large circuit | | `sphere3hopf_full.json` | 180+ | 8 | Same, full version | --- class: nord-light, middle, center ## 📄 Yosys JSON Reader --- ### 🔄 Python → Rust Port The `read_yosys_json` function parses Yosys output format: ```rust pub fn read_yosys_json<P: AsRef<Path>>(path: P) -> IoResult<Netlist> ``` .mermaid[ <pre> graph LR Y["Yosys JSON\n{modules: {cells, ports}}"] --> PARSE["Parse Yosys JSON"] PARSE --> CELLS["Extract cells\n→ modules"] PARSE --> PORTS["Extract ports\n→ fixed modules (weight=0)"] PARSE --> NETS["Collect wire IDs\n→ nets"] CELLS --> EDGES["Add edges\ncell↔net\nport↔net"] PORTS --> EDGES NETS --> EDGES EDGES --> NL["Netlist\nwith weights\nand fixed flags"] style Y fill:#ff9800 style NL fill:#4caf50 style PORTS fill:#f44336 </pre> ] --- ### 🏛️ Key Design Differences | Aspect | Python 🐍 | C++ Port (io.rs) | **Python Port (new)** ✅ | |--------|-----------|-------------------|--------------------------| | Cell names | `cell_name` | `cell_{name}` | **`cell_name`** (matches Python) | | Port names | `PORT_{name}` | `port_{name}` | **`PORT_{name}`** (matches Python) | | Net names | Wire ID `str(id)` | `wire_{id}` | **`str(id)`** (matches Python) | | String constants | Skipped via `isinstance` | N/A | Skipped via `as_u64()` ✅ | | Fixed modules | `set(port_ids)` | `{port_{name}}` | **`{PORT_{name}}`** ✅ | | Error type | Exceptions | `IoResult` | **`IoResult`** ✅ | --- ### 📊 Node-Link JSON Reader Also ported `read_json()` → `read_node_link_json()`: ```rust pub fn read_node_link_json<P: AsRef<Path>>(path: P) -> IoResult<Netlist> ``` Handles **both** string IDs (`"a0"`) and integer IDs (`0`, `835`): ```rust let id = v.as_str() .map(|s| s.to_string()) .or_else(|| v.as_i64().map(|n| n.to_string())); ``` Auto-detects Yosys vs node-link format based on `"modules"` key presence. ✅ --- class: nord-light, middle, center ## 🧪 194 Tests — All Passing ✅ --- ### 📊 Test Coverage Map | Python Test File | Rust Tests | Status | |-----------------|------------|--------| | `test_netlist.py` | 10 tests | ✅ | | `test_graph_algo.py` | 4 tests | ✅ | | `test_cover.py` | 7 tests | ✅ | | `test_pd_cover.py` | (merged) | ✅ | | `test_netlist_algo.py` | 5 tests | ✅ | | `test_rand_cover.py` | 12 tests | ✅ | | `test_hadlock.py` | 4 tests | ✅ | | `test_tsp.py` | 18 tests | ✅ | | `test_stress.py` | 2 tests | ✅ | | `testcases/` | 4 tests | ✅ | | `yosys_testcases/` | 3 tests | ✅ | | GPU acceleration | 6 tests | ✅ | **Total: 194 tests, 0 failures** 🏆 --- ### 🐛 Bugs Found & Fixed During Port | Bug | Impact | Fix | |-----|--------|-----| | **Signed integer underflow** in `min_maximal_matching` | `u32` gap subtraction panics | Use `i32` or saturating arithmetic | | **Non-deterministic Eulerian circuit** | TSP results varied between runs | `HashMap` → deterministic start | | **Duplicate edges** in Yosys JSON | Pin count mismatched Python | `find_edge` guard → idempotent `add_edge` | | **Integer IDs** in node-link JSON | `p1.json` failed to parse | Support both string and integer `id` fields | | **JSON format detection** | All `.json` treated as Yosys format | Auto-detect via `"modules"` key | --- class: nord-light, middle, center ## 🏆 Key Achievements --- ### 🚀 What Was Accomplished .pull-left[ #### ✅ Full Feature Parity - **10 Python modules** → **14 Rust modules** - All algorithms ported with matching semantics - Same API conventions preserved #### 🧪 Comprehensive Testing - **185 tests** all passing - Matches Python test suite structure - Integration tests with real data files ] .pull-right[ #### 🦀 Rust Advantages Leveraged - **Generic weights** via trait bounds - **Zero-cost abstractions** (no runtime overhead) - **Memory safety** guaranteed at compile time - **Fearless concurrency** with Rayon - **No new dependencies** — only `petgraph` + `indexmap` #### 🔧 Bugs Fixed - 5 bugs discovered during port - Yosys JSON reader significantly improved - `add_edge` made idempotent ] --- ### 📈 Module Comparison .mermaid[ <pre> graph TB subgraph Python["Python netlistx 🐍"] direction TB P1["10 source files"] P2["~2,400 lines"] P3["21 test files"] P4["networkx\n(heavy dependency)"] end subgraph Rust["netlistx-rs 🦀"] direction TB R1["14 source files"] R2["~5,200 lines"] R3["4 test files\n(185 tests)"] R4["petgraph + indexmap\n(lightweight)"] end Python -->|"port + improve"| Rust style Python fill:#4caf50 style Rust fill:#2196f3 </pre> ] --- class: nord-light, middle, center ## 🔮 Future Work --- ### 🗺️ Roadmap .mermaid[ <pre> graph LR subgraph Done["✅ Done"] D1["All algorithms ported"] D2["185 tests passing"] D3["Yosys JSON reader"] D4["Factory functions"] D5["Test data files"] end subgraph Next["🔜 Next"] N1["Benchmark vs Python"] N2["CI pipeline with GitHub Actions"] N3["crates.io publish v0.2"] N4["Benchmark suite"] end subgraph Future["🔮 Future"] F1["Python bindings via PyO3"] F2["GPU-accelerated rand_cover"] F3["Multilevel partitioning"] F4["Rustdoc API documentation"] end Done --> Next --> Future style Done fill:#4caf50 style Next fill:#ff9800 style Future fill:#9c27b0 </pre> ] --- ### 🎯 Short-Term Goals 1. **📊 Benchmark**: Compare Rust vs Python runtime on large netlists (100K+ nodes) 2. **🤖 CI**: GitHub Actions with `cargo test`, clippy, and code coverage 3. **📦 Release**: Publish v0.2 to crates.io with full documentation 4. **⚡ Rayon**: Enable parallel cover algorithms as default ### 🔬 Long-Term Vision - **🔄 PyO3 bindings**: Use Rust algorithms from Python seamlessly - **🎮 GPU**: CUDA/OpenCL backend for randomized algorithms - **🏗️ Multilevel**: Hierarchical partitioning for million-cell designs --- class: nord-light, middle, center ## 🙏 Acknowledgments --- ### 📚 Key References | Reference | Topic | |-----------|-------| | Christofides (1976) | 3/2-approximation for Metric TSP | | Hadlock (1975) | Polynomial MAX-CUT for planar graphs | | Pitt (1985) | Randomized 2-approximation for vertex cover | | Fiduccia & Mattheyses (1982) | Linear-time circuit partitioning | | Kernighan & Lin (1970) | Graph partitioning heuristic | ### 🛠️ Tools - **petgraph** — Rust graph data structure library - **petgraph** — Minimum spanning tree, Dijkstra - **serde_json** — JSON parsing - **Rayon** — Data parallelism - **Remark.js** — Presentation framework --- ### 📦 Repositories | Package | Language | Repository | |---------|----------|------------| | `netlistx` | 🐍 Python | [luk036/netlistx](https://github.com/luk036/netlistx) | | `netlistx-rs` | 🦀 Rust | [luk036/netlistx-rs](https://github.com/luk036/netlistx-rs) | | `netlistx-cpp` | C++ | [luk036/netlistx-cpp](https://github.com/luk036/netlistx-cpp) | | `ckpttnpy` | 🐍 Python | [luk036/ckpttnpy](https://github.com/luk036/ckpttnpy) | --- count: false class: nord-dark, middle, center # 🦀 Thank You! ### Questions? 🙋 .mermaid[ <pre> graph LR P["Python 🐍\nnetlistx"] -->|"port"| R["Rust 🦀\nnetlistx-rs"] R -->|"185 tests ✅"| D["Done! 🏆"] style P fill:#4caf50,color:#fff style R fill:#2196f3,color:#fff style D fill:#ff9800,color:#fff </pre> ] @luk036 👨‍💻 · 2026 📅