Prediction of area and length complexity measures for binary decision diagrams

Azam Beg, P. W. Chandana Prasad

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)2864-2873
    Number of pages10
    JournalExpert Systems with Applications
    Volume37
    Issue number4
    DOIs
    Publication statusPublished - Apr 2010

    Keywords

    • Area complexity
    • Binary decision diagrams
    • Circuit complexity
    • Complexity prediction
    • Machine learning
    • Neural network modeling
    • Path length complexity

    ASJC Scopus subject areas

    • General Engineering
    • Computer Science Applications
    • Artificial Intelligence

    Fingerprint

    Dive into the research topics of 'Prediction of area and length complexity measures for binary decision diagrams'. Together they form a unique fingerprint.

    Cite this