Optimizing synchronous systems
- 1 October 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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.Keywords
This publication has 5 references indexed in Scilit:
- The Design of Special-Purpose VLSI ChipsComputer, 1980
- Generalized Nested DissectionSIAM Journal on Numerical Analysis, 1979
- Mathematical Approach to Computational NetworksPublished by Defense Technical Information Center (DTIC) ,1978
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State MachinesIEEE Transactions on Computers, 1969
- Iterative Arrays of Logical CircuitsPublished by MIT Press ,1961