Accession Number:

ADA256814

Title:

Organization of Systems with Bussed Interconnections

Descriptive Note:

Doctoral thesis

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1992-03-01

Pagination or Media Count:

123.0

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 12 lg n time. We generalize binomial arbitration to achieve a bus-time tradeoff m 0tn1t. 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.

Subject Categories:

  • Electrical and Electronic Equipment
  • Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE