Introduction
In modern digital logic design, logic optimization is a critical step for reducing the number of gates in a circuit, which directly translates to savings in power consumption, physical area, and manufacturing costs. While "exact synthesis"—the process of finding the mathematically smallest possible implementation of a Boolean function—is highly effective for tiny circuits, it is computationally intractable for designs exceeding approximately 10 gates.
To optimize large-scale industrial circuits, engineers typically employ "peephole optimization," where small sub-sections (windows) of a larger design are isolated and replaced with optimized versions. However, traditional SAT-based methods often require the new subcircuit to be logically identical to the original one in isolation. This constraint ignores "don't care" conditions—input patterns that never occur or whose outputs are ignored by the rest of the system—limiting the potential for significant gate reduction.
The QBF-Based Rewriting Method
This paper introduces a novel approach to logic optimization using Quantified Boolean Formulas (QBF). Unlike standard SAT solvers that check for local equivalence, a QBF solver can evaluate a more complex global condition: "Does there exist a smaller subcircuit such that, for all possible primary inputs, the entire system's output remains unchanged?"
By encoding the synthesis task as a QBF problem, the authors achieve several technical advantages:
- Implicit Don't Cares: The QBF encoding naturally incorporates the surrounding circuit's logic. The solver automatically exploits input patterns that are unreachable or unobservable, removing the need for expensive pre-calculation of "don't care" sets.
- Multi-Output Optimization: The method can optimize subcircuits with multiple outputs simultaneously. This allows the solver to identify opportunities for gate sharing that single-output optimizers would miss.
- Acyclicity Constraints: To prevent the replacement from introducing logical loops (cycles), the authors developed specific encoding constraints that ensure the resulting design remains a valid directed acyclic graph (DAG).
Key Insights: Global Correctness vs. Local Equivalence
The fundamental shift in this research is prioritizing global correctness over local equivalence. A subcircuit replacement does not need to behave identically to the original when tested in a vacuum; it only needs to preserve the integrity of the final outputs of the entire chip. This flexibility allows the solver to explore a much larger space of potential implementations.
Experimental data highlights the impact of this shift. When the optimization was restricted to strictly equivalent replacements, the average gate reduction was only 8.4%. By allowing non-equivalent replacements that leverage global context via QBF, the reduction nearly tripled to 24.3%.
Results and Benchmarks
The researchers validated their tool on the EPFL Combinational Benchmark Suite and the IWLS ’22 Programming Contest dataset. The results were record-breaking:
- State-of-the-Art Reductions: The tool discovered the smallest known implementations for several standard benchmarks, including the
Int to float converterandCoding-cavlc, some of which had not seen improvements in years. - Contest Performance: In the IWLS '22 contest, the QBF-based method outperformed all other entries by finding the smallest And-Inverter Graphs (AIGs) for the highest number of functions.
While QBF solvers are computationally more intensive than SAT solvers—often taking significantly longer to solve individual windows—the authors argue that the superior quality of the resulting hardware justifies the increased compute time, especially for high-performance or mass-produced chips.
Conclusion and Future Work
By leveraging the expressive power of QBF, this method overcomes the limitations of local equivalence in logic synthesis. While currently limited to subcircuit windows of roughly 10-15 gates due to the complexity of QBF solving (which is PSPACE-complete), the approach demonstrates a clear path toward more efficient hardware design. Future research will focus on parallelizing the synthesis tasks and utilizing machine learning to identify the most promising subcircuits for optimization, potentially scaling these gains to even larger designs.
Summary updated