Logic synthesis is a procedure transforming circuit specification to a logically equivalent and supposedly optimal implementation at the gate level. For at least three decades, automated logic synthesis tools are used in industry.
Two serious problems with performance of logic synthesis tools were reported. The first one concerned parity predictors, i.e., a class of circuits with a parity tree at output. The second one was with artificial but realistic circuits. Those two cases were similar: the upper bound for circuit area was known, the resulting area was orders of magnitude larger than the upper bound, and the original structure of the circuit had been replaced by an artificial and possibly ineffective one.
The reports gained attention but no solutions appeared. The problems may have the implicit promise that the overall synthesis performance could greatly be improved; or, as the industry noted, they are possibly irrelevant. To solve this dilemma, investigation was performed.
To evaluate the practical relevance of such phenomenon, the evaluation procedure itself must be relevant. We found that the interface to logic synthesis and hence the requirements to logic synthesis are not well defined. Moreover, the authenticity of some popular benchmarks is at least questionable. We proved first that the problems with parity predictors are no coincidence, that they persist even after changes in the circuit. They are not linked to possible symmetries in the circuit. The discarded structure, however, can be rediscovered by decomposition tools, which are capable for efficient XOR circuit synthesis.
In the other problematic situation, the missing structure is also the key, since the procedures tested work with gradual improvements of the actual input structure. When the optimization fails to achieve a good structure, the output depends strongly on the input. This holds for any circuit transformation that discards the original structure. We quantitatively modeled such behaviors for different transformations. We conclude that any synthesis tools should not be evaluated outside their intended use, which implies that the intended use must have been specified. Artificially transformed circuits can discover the inner working of a procedure but are of little worth in practical evaluation. Circuits used for evaluation must be authentic, including their derivation from designer’s specification.