Research And Implementation Of Logical Synthesis Algorithm Based On Precompiled

Deriving a circuit for a Boolean function or improving an available circuit are typical tasks solved by logic synthesis. Numerous algorithms in this area have been proposed and implemented over the last50years. This paper reaches two conclusion based on previous work and several experiments:(a) optimal or near-optimal circuits for many practical functions are already derived by the tools, making it unnecessary to implement new algorithms or even run the old ones repeatedly;(b) larger circuits are composed of smaller ones, which are often isomorphic up to a permutation/negation of inputs/outputs.Based on the conclusions above, this paper proposes a new logic synthesis method based on pre-computed libraries. This algorithm can collect logic structures generated by other logic synthesis algorithms used on a variety of benchmarks, then create a structure library, and use the library for logic synthesis, other than generating these optimal structures during runtime.This paper also proposed a semi-canonical form to quickly classify, store and reuse Boolean functions. This semi-canonical form is totally different from the NPN form, though it may not as accurate as NPN; it has a much lower complicity and much better efficiency.Based on the semi-canonical form, a6-input AIG structure library has been constructed in this paper. There are millions logic structure stored in this library, which can be used in different scenarios. This paper also counted the frequency of functions appeared in the benchmarks. Both the library and the results are made public on the Internet.As a case-study, the algorithm proposed in this paper is applied to AIG level minimization as a way to improve delay after FPGA mapping. For industrial benchmarks, the delay after LUT mapping was reduced by17%(18%) for LUT4(LUT6) with the area penalty of2%(5%), compared to the recent work on SOP balancing. This is a remarkable result, given the fact that SOP balancing is a high-effort delay-optimization algorithm. It clearly shows that the "lazy" approach often finds better logic structures than SOP balancing.