Exact multi-level benchmark circuit generation for logic synthesis evaluation

Abstract

Electronic design automation (EDA) tools provide a highly automated flow for integrated circuit (IC) design. This flow may be roughly divided into three main steps: high-level synthesis, logic synthesis and physical synthesis. The logic synthesis step has as goal circuit logic optimization and circuit implementation in a given technology. Usually, the logic synthesis is performed over a multiple-level network, which implements the combinational logic of a given circuit. The problem of synthesizing a multi-level network is a complex task, where exact synthesis is just practical for functions with a few inputs, and the vast majority of algorithms are heuristic. While validating and evaluating new heuristic methods, benchmarks are of great importance. Usually, when a new method emerges, it is compared to the previous best-known results for a similar set of circuits, showing the relative efficiency of this new method over the previous one. However, with such an evaluation it is not possible to assess if current approaches are producing a nearoptimal solution or if there is still room for improvement. To address this issue, it is of great interest have circuits with an exact known solution. In this work, a novel method to generate exact multi-level logic circuits is presented. The proposed method is based on reversible logic and creates circuits acting as the identity function f(x) = x. It means that the generated circuits can be reduced to wires, with no gate instantiation. The proposed approach can generate exact benchmark circuits with up to 40 millions of ANDinverter graph (AIG) nodes in a few seconds. Furthermore, with the proposed method, it is possible to derive exact circuits in two different ways: (i) from real designs and (ii) building synthetic circuits. Both approaches are discussed, and logic synthesis results are presented running the state-of-art academic tools and a commercial tool for each. From results, it is possible to note that the generated circuits are challenging to logic synthesis tools and that there is a gap between the solutions found by these tools and the optimal circuit implementation. Finally, we present and discuss the flexibility of the proposed method, and how it can be further explored and applied in areas other than logic synthesis.