Organization of Systems with Bussed Interconnections

This thesis explores using busses in communication architectures and control structures. First, we investigate the organization of permutation architectures with bussed interconnections. We explore how to efficiently permute data among VLSI chips in accordance with a predetermined set of permutations. By connecting chips with shared bus interconnections, as opposed to point-to-point interconnections, we show that the number of pins per chip can often be reduced. The results are derived from a mathematical characterization of uniform permutation architectures based on the combinatorial notion of a difference cover. Second, we explore priority arbitration schemes that use busses to arbitrate among n modules. We investigate schemes that use Ig n < m < n busses and asynchronous combinationa arbitration logic. The standard binary arbitration scheme uses m = Ig n busses and arbitrates in t = Ig n time. We present the binomial arbitration scheme that uses m = Ig n + 1 busses and arbitrates in t = 1/2 Ig n time. We generalize binomial arbitration to achieve a bus-time tradeoff m = O(In"'/). The new schemes are based on data-dependent analysis and can be adopted with no changes to existing protocols. Third, we examine the performance of binary arbitration in a digital transmission lin