Circuit Minimization with QBF-Based Exact Synthesis
Authors: Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Results In an experimental evaluation, the minimization strategy described above achieved substantial size reductions compared to state-of-the-art methods on the following two sets of benchmarks: The EPFL combinational benchmark suite... The IWLS 22 programming contest... Experiments The primary goal of the empirical evaluation is to assess the effectiveness of the presented techniques for exact synthesis and of circuit reduction. |
| Researcher Affiliation | Academia | Franz-Xaver Reichl, Friedrich Slivovsky, Stefan Szeider Algorithms and Complexity Group, TU Wien, Vienna, Austria {freichl,fs,sz}@ac.tuwien.ac.at |
| Pseudocode | No | The paper describes its encoding and algorithms in prose, but it does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | We implemented the presented synthesis method in Python.5 (Footnote 5 points to 'https://github.com/fxreichl/ciops') |
| Open Datasets | Yes | The EPFL combinational benchmark suite was designed to test logic optimization and synthesis tools (Amar u, Gaillardon, and Micheli 2015). An online repository2 maintains the smallest implementations found so far. and The IWLS 22 programming contest3 asked participants to synthesize small circuits for single and multi-output Boolean functions given as truth tables. (Footnote 2: 'https://github.com/lsils/benchmarks', Footnote 3: 'https://github.com/alanminko/iwls2022-ls-contest') |
| Dataset Splits | No | The paper discusses the use of the EPFL and IWLS benchmarks but does not specify any training, validation, or test dataset splits in terms of percentages, counts, or explicit splitting methodologies for their experiments. |
| Hardware Specification | Yes | All experiments were conducted on a cluster with Intel Xeon E5649 processors at 2.53 GHz running 64-bit Linux. Additionally, we used a memory limit of 4 GB. |
| Software Dependencies | No | The paper mentions 'Python' and 'QFUN (Janota 2018)' as the backend QBF solver, but it does not provide specific version numbers for these or other software components used in the experiments. |
| Experiment Setup | Yes | A time budget is allocated for individual solver calls to keep overall running time within reason. This timeout is adjusted dynamically based on previously observed running times. and In our evaluation setup, we run our reduction tool for one hour, then we apply ABC as an inprocessing step using ABCcommands that turned out useful in preliminary tests. When we apply ABC, we repeat its application until no further improvements can be achieved. The combination of our tool and ABC is applied 10 times. |