Deriving Circuits from Programs

Introduces a theory of traces and a notation for programs consisting of a hierarchy of components. The trace structures of components and programs are regular and, hence, one might construct a finite state machine accepting a program’s traces. The chip area required to implement a finite state machine is, in the worst case, proportional to the number of states of the trace structure, [1], The number of states of the composite of some trace structures is, in the worst case, the product of the numbers of states of the composing trace structures. Hence, the chip area grows exponentially with the number of components in the program, which is not very attractive. Another disadvantage of the traditional finite state machines is that accepting traces is not very interesting: the purpose of a machine is to receive inputs and to generate outputs. In this paper the latter problem is solved by distinguishing, in the trace structures, between input and output symbols. The former problem is then solved by constructing a Mealy- or Moore-like finite state machine per component and by introducing a communications protocol between these machines. Hence, the circuit implementing a program consists of two parts: one part for the finite state machines and one part for their interconnections. In the worst case, the chip areas required for these parts exhibit linear and quadratic growth respectively with the number of components in the program.