Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis

Daniil Averkov, Tatiana Belova, Gregory Emdin, Mikhail Goncharov, Viktoriia Krivogornitsyna, Alexander S. Kulikov, Fedor Kurmazov, Daniil Levtsov, Georgie Levtsov, Vsevolod Vaskin, Aleksey VorobievAAAI 2025 · DOI

TL;DR

This paper introduces "Cirbo," a new open-source Python tool for Boolean circuit analysis and synthesis. Cirbo implements efficient algorithms to tackle frequently used circuit tasks, achieving significant size reductions on benchmark circuits and winning the IWLS 2024 Programming Contest.

What Problem Does This Paper Address?

Boolean circuits are a fundamental model in computer science, with two core computational problems: circuit analysis (checking circuit properties like satisfiability) and circuit synthesis (designing small circuits for a given function). Circuit analysis is crucial for tasks like verification and is closely related to the SAT problem. Circuit synthesis, particularly the Minimum Circuit Size Problem (MCSP), is notoriously difficult, and proving circuit lower bounds (that a function cannot be computed by a small circuit) remains a major challenge. Existing tools often focus on specific aspects or are implemented in lower-level languages, making them less accessible for rapid prototyping and experimentation.

Methods

Cirbo is a Python-based tool designed for efficiency and ease of use. It integrates a variety of algorithms, both existing and novel, for circuit analysis and synthesis. Key features include:

  • Circuit Analysis:
    • Function Analysis: Checks properties like monotonicity and symmetry for Boolean functions.
  • Circuit Analysis: Treats circuits as functions, allowing property checks. It also includes circuit satisfiability checking by transforming circuits to CNF and using SAT solvers.
  • Miter Construction: A technique for verifying if two circuits compute the same function by creating a "miter" circuit and checking its satisfiability.
  • Circuit Synthesis:
    • Manual Synthesis out of Presynthesized Blocks: Provides generators for common circuits (comparators, adders, multipliers) that can be combined to build larger circuits.
  • Automated SAT-based Synthesis: For small input sizes, it formulates the problem of finding a circuit of a given size as a SAT problem and solves it. This can also handle partially defined functions.
  • Hybrid Synthesis: Combines the block-based and SAT-based approaches.
  • Minimization:
    • Low Effort Minimization: Includes straightforward cleaning methods (removing dangling/duplicate gates) and integration with external tools like ABC.
  • High Effort Minimization: A more powerful but less efficient method that minimizes small subcircuits by re-synthesizing them using SAT-based approaches.
  • Database of (Nearly) Optimal Circuits: Stores pre-computed optimal circuits for functions with a small number of inputs/outputs, using NPN-classification to reduce the search space.

Datasets

The paper evaluates Cirbo on benchmarks from the IWLS 2024 Programming Contest. These benchmarks include various categories, such as symmetric and arithmetic functions, and "neuron" benchmarks from the LogicNets project. The authors note that the 2024 contest used the same datasets as the 2023 contest, allowing for direct comparison of size reduction progress.

Key Insights and Ideas

  • Python's Suitability for Circuit Tools: The paper demonstrates that Python can be used to build efficient and accessible tools for complex tasks like Boolean circuit manipulation, challenging the notion that such tools must be implemented in lower-level languages.
  • The Power of Hybrid Approaches: Combining different synthesis and minimization strategies (e.g., block-based with SAT-based, or using external tools like ABC) is crucial for achieving state-of-the-art results, especially for complex or less understood functions.
  • Circuit Satisfiability as a Unifying Problem: The paper highlights how many circuit analysis and synthesis problems, and even combinatorial problems like factorization, can be reduced to circuit satisfiability, underscoring its importance.
  • The Value of a Comprehensive Tool: Cirbo aims to provide a single, integrated platform for a wide range of circuit tasks, from basic analysis to advanced synthesis and minimization, facilitating research and development.

Key Results

Cirbo achieved significant improvements in circuit size reduction, particularly for arithmetic functions. The tool helped the authors win the IWLS 2024 Programming Contest. On average, they reduced the size of the best circuits from 2023 by 12%, with some individual circuits seeing reductions as large as 83%. Table 1 shows specific examples of these improvements for benchmarks like modulo8, square12, and div8 in both AIG and XAIG bases.

Limitations and Future Work

  • Scalability of Analysis: Function analysis (monotonicity, symmetry) is currently limited to small input sizes due to its enumerative nature.
  • Proof of Optimality: For some functions, especially in the AIG basis, the tool can find efficient circuits, but proving their absolute minimal size is still a difficult task.
  • Future Work: The authors suggest that further improvements can be made by exploring more advanced minimization techniques and potentially expanding the database of optimal circuits. The tool's open-source nature encourages community contributions and further development.

Summary updated

BibTeX
@inproceedings{averkov2025cirbo,
  author = {Daniil Averkov and Tatiana Belova and Gregory Emdin and Mikhail Goncharov and Viktoriia Krivogornitsyna and Alexander S. Kulikov and Fedor Kurmazov and Daniil Levtsov and Georgie Levtsov and Vsevolod Vaskin and Aleksey Vorobiev},
  title = {{Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33207},
}
Figure