Algorithms for Logic Design Automation (Rtcad, Synthesis)

315 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985.As the complexity of logic circuits which may be placed on an integrated circuit grows, the complexity and length of the design process increases also. Consequently, there have been increased efforts in recent years directed at developing tools to ease design tasks, mostly the physical tasks such as layout and routing. For low volume applications of integrated circuits, where the design costs may greatly exceed the production costs for the production lifetime of the integrated circuit, and especially if the same basic architecture is needed for several designs, it is economically justifiable to develop design tools which are able to produce semi-automatically an integrated circuit which corresponds to a high level behavioral description of a logic circuit. This thesis describes a collection of algorithms that transform a graph data structure derived from a behavior description into a logic design at the register transfer level.The proposed design system creates register transfer level designs using numbers and types of resources controlled, for the most part, by the user of the system. The overall architecture of the data part (i.e. a multiple functional unit, multiple bus configuration) and the control part (i.e. microprogrammed) are fixed by the system. The user has control over the number and type of functional units, the number of buses, the length of the microword and the number and type of microcode sequencing instructions.The design process proceeds as follows: functional units are scheduled into microinstructions without violating precedence or resource constraints with the objective of minimizing schedule length i.e. the number of microinstructions required to execute the behavioral description. When scheduling is completed, actual register files are assigned to file uses determined during scheduling in such a way as to avoid file conflicts and minimize the total number of registers used to store intermediate results.Methods are presented to minimize the number of NOPs generated in microcode and to place those which are needed into low execution frequency locations in microcode. Finally, multiplexing between buses and functional units and at the output of the microword is heuristically minimized.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD