Optimizing synchronous systems
Charles E. Leiserson, James B. Saxe · Annual Symposium on Foundations of Computer Science · 1981
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.
Cited by 427 works. doi:10.1109/sfcs.1981.34
Authors
References
- Introduction to V.L.S.I. Systems
- Combinatorial optimization: networks and matroids
- Systolic Arrays for (VLSI).
- A Complexity Theory for VLSI
- Iterative Arrays of Logical Circuits
- Generalized Nested Dissection
- Let's Design Algorithms for VLSI Systems
- Area-Efficient VLSI Computation
- Area-Efficient Graph Layouts (for VLSI).
- The Design of Special-Purpose VLSI Chips