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

当使用随机实例评估逻辑优化系统（如SIS）的性能时，人们经常说随机实例太人工，离现实世界太远。因此，在本研究中，我们不开发“完全”随机发生器，而是开发可以控制电路多个属性的随机发生器。首先，我们开发了一种基本类型的发电机。该算法从一个初始电路开始，然后应用一系列变换规则使电路变得复杂。在每一步中，从一组转换规则中随机选择转换。每个变换规则都是等价的，即不改变逻辑函数。然后我们对原来的系统进行了改进。我们的新发生器可以控制逻辑门的最大扇入，这在原来的版本中是不可能的。原来的系统可能输出一个非常大的扇入电路，但新系统可以产生一个有限的扇入电路，比如4，这是一个合理的尺寸。在最初的版本中，我们必须输入一个合适的基准电路作为初始电路。然而，我们的新系统可以自动生成初始电路。它还可以控制初始电路的参数，包括函数的on-set的大小及其复杂程度。初始电路由CNF公式给出。为了控制on-set，我们需要计算初始电路的满意赋值次数，这通常需要花费大量的时间。然而，我们可以使用基于包容-排斥原理的原始计数方法快速计算出它。控制复杂程度可以通过调整包含大量字面量的子句的数量来实现。我们还使用我们的测试实例对逻辑优化系统SIS和Transduction Method进行了实证评估，并发现了这两个系统在性能上的一些差异。

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.