Logic optimization of interacting components in synchronous digital systems
Yosinori Watanabe, Robert K. Brayton · 1994
In optimizing digital systems, manual designs sometimes use information derived from other components to identify a functional flexibility at a particular component. This thesis addresses how to identify such a flexibility as well as how to use it in the optimization of synchronous digital systems. We first focus on the case where the system realizes a combinational logic behavior, and propose a procedure for computing a set of permissible functions at each component, i.e. the set of functions that can be realized there while preserving the behavior of the entire system. The identified set of functions is represented by a single relation between the inputs and the outputs of the component. We then address the problem of finding an optimum permissible function. The problem is reduced to the minimization of relations, and we develop a heuristic procedure for the problem. The second half of the thesis performs an analogous investigation for sequential logic behaviors. We consider a synchronous system in which the behavior of each component is modeled by a finite state machine, and show that the complete set of its permissible sequential behaviors can be represented by a single non-deterministic finite state machine, which we call the scE-machine. We give a fixed point computation for deriving the scE-machine. We then consider the problem of finding an optimum sequential behavior, which is achieved by minimizing the scE-machine. We show that the scE-machine is a special type of non-deterministic finite state machine, and use this property effectively in the minimization. We develop both exact and heuristic procedures for the problem.