Fast and Mass Generation of Random Benchmark Circuits That Are Not Too Artificial

点击翻译按钮获取中文摘要

When evaluating the performance of logic optimization systems such as SIS using random instances, it is often said that random instances are too artificial and far from the real world. Thus, in this research, we do not develop "fully" random generators but we develop random generators which can control several attributes of circuits.First of all, we developed a basic type of generator. The algorithm starts with an initial circuit and then applies a sequence of transformation rules to make a circuit complicated. At each step, transformation is selected at random from the set of transformation rules. Each transformation rule is equivalent, namely, it does not change the logic function.Then we improved the original system. Our new generator can control the maximum fan-in of the logic gates, which was impossible in the original version The original system possibly outputs a circuit of extremely large fan-in, but the new system can generate a circuit of limited fan-in, say 4, which is a reasonable size.In the original version, we had to input an appropriate benchmark circuit as an initial circuit. However, our new system can generate initial circuits automatically. It can also control the parameters of initial circuits including the size of the on-set of the function and the degree of its complexity. Initial circuits are given by CNF formulas. To control the on-set, we need to count the number of satisfying assignments of the initial circuit, which usually takes great amount of time. However, we can compute it quickly using our original counring methods based on the inclusion-exclusion pronciple. Controlling the degree of complexity can be done by adjusting the number of clauses including a lot of literals.We also emplricall evaluated logic optimization systems, SIS and Transduction Method, using our test instances and found some difference between the performance of these two systems.