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

在使用随机实例评估SIS等逻辑优化系统的性能时，人们常说随机实例过于人为，与真实的世界相差甚远。因此，在这项研究中，我们不开发“完全”的随机发生器，但我们开发的随机发生器，可以控制电路的几个属性。首先，我们开发了一个基本类型的发生器。该算法从初始电路开始，然后应用一系列变换规则使电路复杂化。在每个步骤中，从变换规则集合中随机选择变换。每种变换规则都是等价的，即不改变逻辑函数。我们的新生成器可以控制逻辑门的最大扇入，这在原始版本中是不可能的。原始系统可能输出极大扇入的电路，但新系统可以生成有限扇入的电路，比如4，这是一个合理的大小。在原始版本中，我们必须输入适当的基准电路作为初始电路。然而，我们的新系统可以自动生成初始电路。它还可以控制初始电路的参数，包括函数的起始点的大小和函数的复杂程度。初始电路由CNF公式给出。为了控制起始，我们需要计算初始电路的满意分配的数量，这通常需要大量的时间。然而，我们可以快速计算它使用我们原来的计数方法的基础上的包含-排除principle。通过调整包含大量文字的子句的数目，可以控制复杂度。我们还对逻辑优化系统SIS和转换方法进行了测试，发现两种系统的性能存在一定的差异。

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.