Accession Number : ADA113916

Title :   Optimixing Synchronous Systems.

Descriptive Note : Memorandum rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Leiserson,Charles E ; Saxe,John B

PDF Url : ADA113916

Report Date : Mar 1982

Pagination or Media Count : 32

Abstract : The complexity of integrated-circuit chips produced today makes it feasible to build inexpensive, special-purpose subsystems that rapidly solve sophisticated problems on behalf of a general-purpose host computer. This paper contributes to the design methodology of efficient VLSI algorithms. We present a transformation that converts synchronous systems into more time-efficient, systolic implementations by removing combinational rippling. The problem of determining the optimized system can be reduced to the graph-theoretic single-destination-shortest-paths problem. More importantly from an engineering standpoint, however, the kinds of rippling that can be removed from a circuit at essentially no cost can be easily characterized. For example, if the only global communication in a system is broadcasting from the host computer, the broadcast can always be replaced by local communication. (Author)

Descriptors :   *Parallel processors, *Computer architecture, *Microcomputers, Integrated circuits, Chips(Electronics), Synchronism, Circuit analysis, Methodology, Graphs, Computations, Paths, Algorithms, Real time, Problem solving, Combinatorial analysis, Transformations

Subject Categories : Electrical and Electronic Equipment
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE