EDA Logic Synthesis Engine

TL;DR

Built a complete logic synthesis engine in Python from scratch — no external EDA APIs. The engine processes Verilog netlists up to 112K gates, achieves 13.8% average area reduction across 40 ICCAD benchmarks, and validates results 15.3× faster than naive simulation using a bit-parallel simulator. An LLM agent explores the optimization search space with automated graph-level safety guarantees.

The Problem

Logic synthesis sits between high-level HDL and physical gates. The goal: take a Verilog netlist and make it smaller (fewer gates) and faster (shorter critical path) while preserving functional equivalence.

For the ICCAD 2026 CADC Contest, the challenge was to build an engine that could:

• Parse arbitrary Verilog gate-level netlists
• Apply AIG (And-Inverter Graph) local rewriting
• Verify equivalence against the original design
• All within a strict evaluation framework

Architecture

┌─────────────┐    ┌──────────────┐    ┌─────────────────┐
│  Verilog     │───▶│  Netlist     │───▶│  Optimization   │
│  Parser      │    │  Graph       │    │  Pipeline       │
└─────────────┘    └──────────────┘    └────────┬────────┘
                                                │
                                    ┌───────────┴───────────┐
                                    │                       │
                              ┌─────▼─────┐          ┌──────▼──────┐
                              │  Constant  │          │  AIG Local  │
                              │  Folding   │          │  Rewriting  │
                              └─────┬─────┘          └──────┬──────┘
                                    │                       │
                              ┌─────▼─────┐          ┌──────▼──────┐
                              │  ODC       │          │  Equiv      │
                              │  Pruning   │          │  Check      │
                              └─────┬─────┘          └──────┬──────┘
                                    │                       │
                                    └───────────┬───────────┘
                                                │
                                    ┌───────────▼───────────┐
                                    │  LLM ReAct Agent      │
                                    │  (search space guide)  │
                                    └───────────────────────┘

The pipeline is modular — each stage operates on the same NetlistGraph data structure, making it easy to compose and debug.

Hardware → Software Mapping

The core insight was treating the synthesis problem as a graph optimization problem rather than a traditional EDA tool problem:

This mapping let us apply standard graph algorithms (topological sort, DFS, BFS) directly to hardware problems.

Performance

Area Reduction (40 ICCAD benchmarks):

• Average: 13.8% gate count reduction
• Best case: 44.6% (circuit test15)
• 13 out of 40 circuits achieved above 10% reduction

🔗 Deep Dive: Read how 4-cut enumeration and NPN matching achieve 13.8% area reduction →

Verification Speed:

• Bit-Parallel Simulator: 15.3× average speedup over naive per-vector simulation
• Peak speedup: 28.7× on larger circuits
• Equivalence check: 0.01–0.24 seconds per circuit

🔗 Deep Dive: Read how 64-bit wordwise operations squeeze 15× performance from CPU cache locality →

Parse & Memory:

• Average parse time: 76 ms across 569K total gates
• Peak memory: 51 MB for the largest circuit (112K gates)
• __slots__-based node layout achieves ~8% memory savings vs plain objects

LLM Integration

Rather than using LLM to generate synthesis code (which would be fragile), the LLM acts as a heuristic search guide:

1. Context Injection — Automatically extract fan-in cone statistics for the requested signal
2. Action Validation — Pre-execution topological check before any graph mutation
3. Loop Detection — BFS-based combinational loop detection catches cyclic dependencies
4. Transactional Rollback — Clone-and-restore on any failure, guaranteeing graph integrity

The LLM suggests which signals to optimize and which strategies to apply. The engine handles all execution and safety.

🔗 Deep Dive: Read why the hard part isn’t the LLM — it’s building a bulletproof defense layer →

Lessons Learned

• NPN dictionary size is a trade-off: Full 4-input NPN has 222 equivalence classes. We used 6 common ones (MUX, XOR3, MAJ3, etc.) — good enough for 13.8% average reduction, but there’s room for more.
• AIG rewrite scales poorly: Cut enumeration is O(n²) per node. Effective on circuits under 500 gates, times out on larger ones. Future work: hierarchical decomposition.
• LLM latency is negligible for offline synthesis: The 200ms LLM call is irrelevant compared to the seconds-long optimization loop. But for interactive use, it would matter.

Tech Stack

Python · Graph Algorithms · AIG Rewriting · Bit-Parallel Simulation · LLM Agent (ReAct) · SQLite (transaction log)