Deriving circuits from programs

J.L.A. Snepscheut, van de

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    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.
    Original languageEnglish
    Title of host publicationThird Caltech Conference on Very Large Scale Integration
    EditorsR. Bryant
    Place of PublicationBerlin
    PublisherSpringer
    Chapter14
    Pages241-256
    Number of pages16
    ISBN (Electronic)978-3-642-95432-0
    ISBN (Print)978-3-540-12369-9
    DOIs
    Publication statusPublished - 1983
    Event3rd Caltech Conference - Pasadena, United States
    Duration: 21 Mar 198323 Mar 1983

    Conference

    Conference3rd Caltech Conference
    CountryUnited States
    CityPasadena
    Period21/03/8323/03/83

    Fingerprint Dive into the research topics of 'Deriving circuits from programs'. Together they form a unique fingerprint.

    Cite this