Prediction of area and length complexity measures for binary decision diagrams

摘要

Measuring the complexity of functions that represent digital circuits in non-uniform computation models is an important area of computer science theory. This paper presents a comprehensive set of machine learnt models for predicting the complexity properties of circuits represented by binary decision diagrams. The models are created using Monte Carlo data for a wide range of circuit inputs and number of minterms. The models predict number of nodes as representations of circuit size/area and path lengths: average path length, longest path length, and shortest path length. The models have been validated using an arbitrarily-chosen subset of ISCAS-85 and MCNC-91 benchmark circuits. The models yield reasonably low RMS errors for predictions, so they can be used to estimate complexity metrics of circuits without having to synthesize them.