Trade-offs in VLSI for bus communication networks

The Thompson model for VLSI networks is extended to model buses of varying sizes and physical widths. We consider the problem of minimizing the area for networks which use buses to emulate a complete conununication graph. 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 Iunction 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 conununicate 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