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) : Kipnis, Shlomo


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a256814.pdf


Report Date : Mar 1992


Pagination or Media Count : 123


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.


Descriptors :   *VERY LARGE SCALE INTEGRATION , *CIRCUIT INTERCONNECTIONS , *ARCHITECTURE , *PINS , *LOGIC CIRCUITS , *BINOMIALS , CONTROL , ORGANIZATIONS , MODELS , TIME , LOGIC , NUMBERS , PERMUTATIONS , STANDARDS , CONSTANTS , TRANSMISSION LINES , STRUCTURES , THESES


Subject Categories : Electrical and Electronic Equipment
      Command, Control and Communications Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE