Optimizing Synchronous Systems

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.

Authors

• Charles E. Leiserson
• James B. Saxe

Keywords

• Broadcasting
• Clocks
• Design methodology
• Circuits
• Costs
• Signal processing
• Signal processing algorithms
• Logic
• Laboratories
• Computer science
• Synchronization Of Systems
• Time Step
• Greater Than Or Equal
• Shortest Path
• Functional Elements
• Edge Weights
• Pathfinding
• Weak Connections
• Vertices
• Integrated Circuit
• Negative Cycle
• Combinational Logic
• Communication Graph
• Clock Period
• Clock Generator
• Ticking Clock