Incremental evaluation of computational circuits

Abstract

The incremental circuit value problem arises in diverse interactive computational problems, including the semantic checking done by structure-based editors and such tasks as timing analysis performed by computeraided design systems. An efficient incremental algorithm for updating the values of gates in a circuit (after a change in circuit parameters and/or topology) would have many uses. Ideally, the time to process the change should be polynomially bounded in terms of the size of the change rather than the size of the entire circuit. This ideal has been obtained by others in special cases, but this paper shows that the general problem is Ω(2delta;) under one reasonable model of incremental computation, where δ is an appropriate measure of the size of the change. On the other hand, this paper also shows that there is an O(γ2 logγ) algorithm for the related problem of maintaining a correct assignment of priorities to nodes in a directed acyclic graph, where γ is an appropriate measure of the size of the priority change. This leads to an O(γ2logγ + δ log δ) algorithm for the incremental circuit value problem. The algorithm solves the problem without restricting the circuits or how they may change; it even tests for the accidental introduction of cycles when changing topology.