Trade-Offs in VLSI for Bus Communication Networks.
Abstract
The Thompson model for VLSI(Very Large Scale Integration) networks is extended to model buses of varying sizes and physical widths. The problem of minimizing the area for networks which uses buses to emulate a complete communication graph is considered. Exact upper and lower bounds (to within constant factors) are proven for this problem. This results in a general area-size width trade-off as a function of the number of nodes in the network. Several fundamental techniques are derived for proving lower bounds for networks with buses. Other versions of the problem are studied where either the nodes must be collinear or bus-bus crossings are disallowed. The time for two nodes to communicate is studied and exact trade-offs are shown for different assumptions about the underlying technology. Methods are also presented for tightening the gap between the constants in the upper and lower bounds. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1982
- Accession Number
- ADA132368
Entities
People
- Gary L. Peterson
- Yu-hua Ting
Organizations
- University of Rochester