Organization of Systems with Bussed Interconnections
Abstract
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 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1992
- Accession Number
- ADA256814
Entities
People
- Shlomo Kipnis
Organizations
- Massachusetts Institute of Technology