Accession Number : ADA132368

Title :   Trade-Offs in VLSI for Bus Communication Networks.

Descriptive Note : Preliminary rept.,

Corporate Author : ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s) : Peterson,Gary L. ; Ting,Yu-Hua

Report Date : SEP 1982

Pagination or Media Count : 30

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)

Descriptors :   *Bus conductors, *Communications networks, Trade off analysis, Models, Nodes, Multiplexing, Graphs, Polygons, Orthogonality, Boundaries, Grids

Subject Categories : Electrical and Electronic Equipment
      Non-radio Communications

Distribution Statement : APPROVED FOR PUBLIC RELEASE