JUCS - Journal of Universal Computer Science 5(5): 288-306, doi: 10.3217/jucs-005-05-0288
The Average Case Performance of an Algorithm for Demand-Driven Evaluation of Boolean Formulae
expand article infoPaul E. Dunne, Paul H. Leng
‡ University of Liverpool, United Kingdom
Open Access
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.
simulation, logic design, average-case analysis of algorithms