The Average Case Performance of an Algorithm for Demand-Driven Evaluation of Boolean Formulae

Paul E. Dunne (University of Liverpool, UK)

Paul H. Leng (University of Liverpool, UK)

Abstract: Demand-driven simulation is an approach to the simulation of digital logic circuits that was proposed, independently, in the work of several authors. Experimental studies of the paradign have indicated that this approach may reduce the time required for simulation, when compared with event-driven techniques. In this paper we present some analytic support for these experimental results by analysing the average number of gates evaluated with a naive demand-driven algorithm for formula evaluation.

Keywords: average-case analysis of algorithms, logic design, simulation

Categories: B.6.3, F.2.m