Exhaustive Circuit Partitioning via Middle-Levels Gray Code

---
count: false
class: nord-dark, middle, center

# 🧬 Exhaustive Circuit Partitioning via Middle-Levels Gray Code

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1: Background** 🧠
- Circuit Partitioning Problem
- FM Algorithm & Limitations
- The Key Insight

**Part 2: Gray Code Theory** 📐
- The Middle Levels Graph
- From Gray Code to Partitions
- Muetze-Nummenpalo Algorithm

**Part 3: Architecture** 🏗️
- System Design
- Adaptation Challenges
- Cost Tracking

]
.pull-right[

**Part 4: Multi-Level Integration** 🧩
- File Structure
- Integration Strategy

**Part 5: Testing & Scalability** 📊
- Test Suite
- Scalability of Gray Code

**Part 6: Design & Future** 💬
- Key Design Decisions
- Limitations & Future Work

]

---

## Abstract 📝

Circuit partitioning is a fundamental NP-hard problem in EDA. Traditional local-search methods like Fiduccia-Mattheyses (FM) can get stuck in suboptimal solutions. We present an **exhaustive enumeration** approach using the **middle-levels Gray code** — a Hamiltonian cycle traversing all balanced 2-way partitions by flipping one module at a time. The Gray code guarantees optimality for graphs with ≤ 10 modules, and we integrate it as the leaf-level solver in a **multi-level partitioning** framework. Experimental results on standard benchmarks demonstrate identical QoR to FM while providing a certifiable optimum at the coarsest level.

---

## 🧭 Background

---

### The Circuit Partitioning Problem ✂️

- **Input**: Hypergraph $G = (V, E)$ with module weights $w(v)$
- **Goal**: Split $V$ into $k$ parts, minimizing **cut cost** while satisfying **balance constraints**
- **Cut cost**: Sum of weights of nets spanning multiple partitions

$$\min \sum_{e \in E} w(e) \cdot \mathbb{1}[\text{net } e \text{ is cut}]$$

s.t. $\left|\sum_{v \in P_i} w(v) - \frac{W}{k}\right| \leq \epsilon W$

- **NP-hard** → heuristics dominate in practice
- **Fiduccia-Mattheyses (FM)**: Local search, moves one module at a time

---

### FM Algorithm 🔄

.mermaid[
<pre>
graph LR
    A["Initial Partition"] --> B["Compute Gains"]
    B --> C{"Select Best Move"}
    C --> D["Update Partition"]
    D --> E{"Stopping Rule?"}
    E -->|No| B
    E -->|Yes| F["Restore Best Snapshot"]
    F --> G["Output Partition"]

style A fill:#4caf50,color:#fff
    style G fill:#4caf50,color:#fff
    style C fill:#ff9800,color:#fff
    style E fill:#f44336,color:#fff
</pre>
]

- Each step: move one module with highest **positive gain**
- Can get trapped in **local minima** 🪤
- Quality depends heavily on **initial solution**

---

### The Key Insight 💡

> What if we could visit ALL balanced partitions, not just local ones?

- The middle-levels Gray code visits every balanced 2-way partition
- Each transition flips exactly **one bit** (= moves one module)
- **Same operation** as FM! But **exhaustive** instead of local

| | FM | Middle-Levels |
|---|---|---|
| Moves | Greedy local | All possible |
| Guarantee | Local optimum | **Global optimum** ✓ |
| States visited | ~$O(|V|)$ per pass | $2 \cdot \binom{2n+1}{n}$ |

---

## 🎯 Middle-Levels Gray Code

---

### The Middle Levels Graph $G_n$ 📐

- **Vertices**: All bitstrings of length $2n+1$ with weight $n$ or $n+1$
- **Edges**: Between vertices differing in exactly one bit
- This is a **subgraph** of the $(2n+1)$-dimensional hypercube

.mermaid[
<pre>
graph LR
    subgraph Level_n["Level n\n(2 ones)"]
        A["11000"] --- B["10100"] --- C["10010"]
        B --- D["01100"] --- E["01010"]
    end
    subgraph Level_np1["Level n+1\n(3 ones)"]
        F["11100"] --- G["11010"] --- H["11001"]
        G --- I["10110"] --- J["01110"]
    end
    A --- F
    B --- G
    C --- H
    D --- I
    E --- J

style A fill:#2196f3,color:#fff
    style J fill:#2196f3,color:#fff
</pre>
]

---

### Historical Context 🏛️

- 📅 **1982**: Problem proposed independently
- 📅 **2014**: Muetze proved the conjecture for sufficiently large $n$
- 📅 **2019**: Gregor, Muetze, & Nummenpalo — complete constructive proof
- 🏆 Solved a **40-year open problem** in combinatorics

> **Theorem (2019):** For every $n \geq 1$, the middle levels graph $G_n$ contains a **Hamiltonian cycle**.

---

### From Gray Code to Partitions 🔗

For $N$ modules with balanced 2-way partitioning:

| $N$ | Bitstring length $L$ | $n = \lfloor L/2 \rfloor$ | Dummy bits |
|-----|---------------------|--------------------------|------------|
| Odd ($2n+1$) | $L = N$ | $n = \frac{N-1}{2}$ | 0 |
| Even ($2n$) | $L = N+1$ | $n = \frac{N}{2}$ | 1 |

Each bit $i \in [0, N)$ = partition assignment of module $i$

- **0** → module in partition A
- **1** → module in partition B

The Gray code visits **every** $N$-bit pattern with $n$ or $n+1$ ones

$$\text{States visited} = \binom{L}{n} + \binom{L}{n+1}$$

---

### The Muetze-Nummenpalo Algorithm ⚙️

.mermaid[
<pre>
flowchart TD
    A["Start: Vertex x"] --> B["Initialization\n(to first vertex)"]
    B --> C["Build Tree Structure"]
    C --> D{"Main Loop"}
    D -->|"H_n ∘ 0"| E["Apply τ or τ⁻¹"]
    E --> F["Rotate Tree"]
    F --> G["Compute Flip Seq σ"]
    G --> H["Apply Flip Sequence"]
    H --> I["Flip Last Bit"]
    I -->|"\n rev(H_n) ∘ 1"| J["Compute Flip Seq σ'"]
    J --> K["Apply Flip Sequence"]
    K --> L["Flip Last Bit"]
    L --> D
    H -->|"Terminate?"| M["Done!"]

style A fill:#4caf50,color:#fff
    style M fill:#f44336,color:#fff
    style D fill:#ff9800,color:#fff
</pre>
]

- **Memoryless**: Each step depends only on current vertex
- **Tree-based**: Binary tree encodes Dyck path structure
- **Flip sequences**: Recursive divide-and-conquer

---

## 🔧 Implementation

---

### Architecture 🏗️

.mermaid[
<pre>
classDiagram
    class MidVertex {
        -vector<int> bits_
        +compute_flip_seq_0()
        +compute_flip_seq_1()
        +to_first_vertex()
        +to_last_vertex()
    }
    class MidTree {
        -int root_
        -vector<list<int>> children_
        +flip_tree()
        +rotate()
        +root_canonically()
    }
    class MidHamCycle {
        -MidVertex x_, y_
        -MidVisitFunc visit_f_
        +MidHamCycle(x, limit, visit)
    }
    class MidLvlPartMgr {
        -const Gnl& hyprgraph
        +int total_cost
        +optimize(part)
        +compute_total_cost(part)
    }
    class MLMidLvlPartMgr {
        -double bal_tol
        -size_t limitsize
        +run_Partition(hyprgraph, part)
    }
    MidHamCycle --> MidVertex : uses
    MidHamCycle --> MidTree : uses
    MidLvlPartMgr --> MidHamCycle : enumerates via
    MLMidLvlPartMgr --> MidLvlPartMgr : leaf optimization
</pre>
]

---

### Adaptation Challenges 🔧

**Original code** (GPL v2, Muetze-Nummenpalo 2018):
- Uses C99 VLAs → **incompatible with MSVC**
- Uses `g++` with `-std=c++11`
- Function pointer callback → no state capture

**Our adaptations**:

| Issue | Solution |
|-------|----------|
| VLAs | `std::vector<int>` with `.data()` |
| MSVC warnings | `static_cast<int>` for `size_t` |
| Overlapping `std::copy` | Manual loops (right-shift + left-shift) |
| Function pointer | `std::function` for lambda capture |
| Size limit test | Only 3- and 5-module test cases |

---

### Cost Tracking During Traversal 📊

```cpp
auto visit_fn = [&](const std::vector<int>& bits, int flipped_pos) {
    if (flipped_pos >= num_modules) return; // skip dummy bits
    auto to_part   = bits[flipped_pos];
    auto from_part = 1 - to_part;
    // Incremental delta: only re-evaluate nets touching flipped module
    int delta = 0;
    for (auto& net : hl.gr[flipped_pos]) {
        // count pins in from_part and to_part (before vs after move)
        bool before_cut = (count_to > 0);
        bool after_cut  = (count_from > 0);
        if (!before_cut && after_cut)  delta += weight;
        if (before_cut && !after_cut)  delta -= weight;
    }
    current_cost += delta;
    current_part[flipped_pos] = to_part;
    if (current_cost < best_cost) { best_cost = current_cost; best_part = current_part; }
};
```

- **O(degree)** per flip — incremental, not full recomputation
- Tracks `best_part` snapshot throughout the cycle

---

### Multi-Level Integration 🧩

.mermaid[
<pre>
flowchart TD
    A["Input: 833-module netlist"] --> B{"modules ≥ limitsize?"}
    B -->|"Yes (833 ≥ 50)"| C["Contract graph\n(matching-based)"]
    C --> D["~416 modules"]
    D --> E["Recurse"]
    E --> F{"modules ≤ 10?"}
    F -->|"Yes"| G["MidLvlPartMgr\n(exhaustive)"]
    F -->|"No"| H["FM optimize"]
    H --> D
    G --> I["Project up"]
    I --> J["FM optimize at this level"]
    J --> K["Output: cost=58"]
    B -->|"No"| F

style A fill:#2196f3,color:#fff
    style G fill:#4caf50,color:#fff
    style K fill:#f44336,color:#fff
</pre>
]

- `limitsize` = 10 → contract until ≤10 modules
- Leaf level: exhaustive enumeration guarantees **global optimum** for the coarsest graph
- Projection up: FM refinement at each level

---

### File Structure 📁

| File | Purpose |
|------|---------|
| `include/ckpttn/midlevel/vertex.hpp` | Adapted `MidVertex` class (MSVC-safe) |
| `include/ckpttn/midlevel/tree.hpp` | Adapted `MidTree` class |
| `include/ckpttn/midlevel/hamcycle.hpp` | Adapted `MidHamCycle` — `std::function` callback |
| `source/midlevel/vertex.cpp` | VLA→vector, manual copy loops |
| `source/midlevel/tree.cpp` | VLA→vector, `size_t` casts |
| `source/midlevel/hamcycle.cpp` | VLA→vector, signed casts |
| `include/ckpttn/MidLvlPartMgr.hpp` | Exhaustive partition manager template |
| `include/ckpttn/MLMidLvlPartMgr.hpp` | Multi-level with exhaustive leaf |
| `middle/` | **Untouched** original GPL code |

---

## 🧪 Experimental Results

---

### Test Suite ✅

| Test | Modules | Strategy | Time | Cost |
|------|---------|----------|------|------|
| default | 3 | Exhaustive | <1ms | ≥0 |
| n5 | 5 | Exhaustive | <1ms | 0 |
| n8 | 8 (+1 dummy) | Exhaustive | <1ms | 1 |
| n11 | 11 | Exhaustive | <1ms | 1 |
| p1 cost | 833 | Cost-only | <1ms | >0 |
| dwarf MLMidLvl | 7 | Multi-level | <1ms | ≥0 |
| n11 MLMidLvl | 11 | Multi-level | <1ms | 1 |

All tests pass. No regressions in FM tests.

---

### p1 Benchmark: limitsize Experiment 📈

| limitsize | Time | Cost |
|-----------|------|------|
| 10 | 24ms | 58 |
| 20 | 22ms | 58 |

- **Identical QoR** — contraction quality dominates for p1
- Exhaustive enumeration at leaf doesn't change the result when contraction is effective
- Both thresholds ~22ms → FM dominates runtime at higher levels

---

### Scalability of Middle-Levels Gray Code 🚀

For bitstring length $L = 2n+1$, states visited: $2 \cdot \binom{2n+1}{n}$

| $n$ | $L$ | Vertices visited | Time (g++, -O3) |
|-----|-----|------------------|-----------------|
| 2 | 5 | 20 | <1ms |
| 3 | 7 | 70 | <1ms |
| 4 | 9 | 252 | <1ms |
| 5 | 11 | 924 | ~1ms |
| 10 | 21 | 352,716 | ~0.5s* |
| 15 | 31 | ~601M | ~19s* |

\* Based on original `middle.exe` benchmark (Muetze-Nummenpalo 2018)

**For balanced partitioning** ($N = 2n$ modules): exhaustive is feasible up to $n \approx 6$ ($N = 12$, ~7,056 states)

---

## 📊 Analysis & Discussion

---

### Why $\le 10$ Modules? 🤔

$$\binom{11}{5} + \binom{11}{6} = 924 \text{ states}$$

$$\binom{13}{6} + \binom{13}{7} = 3,432 \text{ states}$$

$$\binom{21}{10} + \binom{21}{11} = 705,432 \text{ states}$$

- $\le$ 10 modules → at most $\binom{11}{5} \approx 924$ states (instant)
- 12 modules → ~7K states (fine)
- 20 modules → ~352K states (~0.5s)
- 30 modules → ~601M states (~19s) ⚠️

**Design choice**: $10$ as the pragmatic threshold — fast enough for the inner loop of multi-level partitioning.

---

### Key Design Decisions 🎯

| Decision | Rationale |
|----------|----------|
| `std::function` callback | Allows lambda capture of netlist + state |
| Manual copy loops | MSVC optimizes `std::copy` to `memcpy` for overlapping `int` arrays |
| Separate `exhaustive_limit` from `limitsize` | Exhaustive always at ≤10; contraction controlled independently |
| Start from known-good vertex | Avoids Dyck path issues with arbitrary initial partitions |
| `best_cost` starts at user's cost | Guarantees we never return worse than input |

---

### Limitations & Future Work 🚧

- **Exhaustive enumeration**: Exponential — only feasible for ≤10 modules
- **ibm benchmarks**: Contraction crashes at small `limitsize` (pre-existing issue)
- **MSVC vs g++**: Adapted code works on both, but g++ ~20% faster
- **K-way partitioning**: Currently 2-way only (middle levels is bipartite)
- **Balance tolerance**: Exhaustive assumes exactly $n$ or $n+1$ ones

---

## 🎓 Conclusion

---

### Summary 📋

1. 🧬 **Middle-levels Gray code** provides a natural enumeration of **all balanced 2-way partitions**
2. 🔄 Each step flips one bit — identical operation to **FM moves**, but exhaustive instead of local
3. 🏗️ **Multi-level integration**: FM for large graphs, Gray code at coarsest level (≤10 modules)
4. ✅ **All tests pass**, zero regressions, MSVC + g++ compatible
5. 📊 **p1 benchmark**: Identical QoR (cost=58) at limitsize 10 and 20

### Key takeaway 🎯

> When the contracted graph is small enough, exhaustive enumeration guarantees **global optimality** where local search cannot.

---

## Thank You! 🎉

@luk036 · github.com/luk036/ckpttn-cpp