Organization of Systems with Bussed Interconnections

摘要

This thesis explores using busses in communication architectures and controlstructures. 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 arbitrates among n modules. We investigate schemes that use lg n < m < n busses and asynchronous combinationa arbitration logic. The standard binary arbitration scheme uses m = lg n busses and arbitrates in t = lg n time. We present the binomial arbtration scheme that uses m = lg n + 1 busses and arbitrates in t = 1/2 lg n time. We generalize binomial arbitration to achieve a bus-time tradeoff m = 0(tn1/t). 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 line bus model. We show that arbitration time depends on the arrangement of modules. For general arrangements, arbitration time grows linearly with number of busses, while for linear arrangements, arbitration time is constant. Arbitration with busses, Binomial arbitration, Bussed interconnections, Busses, Difference cover, Generalized binomial, Arbitration, Permutation architecture, Priority arbitration.