**edith@ai.toronto.edu (Edith Fraser)** (03/01/90)

Department of Computer Science, University of Toronto (GB = Galbraith Building, 35 St. George Street) ------------------------------------------------------------- THEORY/SYSTEMS GB119, at 3:00 p.m., 15 March 1990 Shlomo Kipnis MIT Lab for Computer Science "Organization of Systems with Bussed Interconnections" In this talk, we investigate several aspects of the organization of digital systems with shared bus interconnections. We explore the organization of permutation architectures with bussed interconnections, and demonstrate how to efficiently utilize busses for implementing priority arbitration mechanisms. We first explore the problem of efficiently permuting data stored in 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. For example, we exhibit permutation architectures with sqrt{n} pins per chip that can realize any of the n cyclic shifts on n chips in one clock tick. When the set of permutations forms a group with p elements, any permutation in the group can be realized in one clock tick by an architecture with O(sqrt{p log p}) pins per chip. When the permutation group is abelian, we show that O(sqrt{p}) pins suffice. These results are all derived from a mathematical characterization of "uniform permutation architectures" based on the combinatorial notion of a "difference cover". We also consider uniform permutation architectures that realize permutations in several clock ticks, instead of one, and show that further savings in the number of pins per chip can be obtained. We continue by investigating priority arbitration schemes that employ busses to arbitrate among n modules in a digital system. We focus on distributed mechanisms that employ m busses, for log n <= m <= n, and use asynchronous combinational arbitration logic. A widely used distributed asynchronous mechanism is the "binary arbitration" scheme, which with m = log n busses arbitrates in t = log n units of time. We present a new asynchronous scheme - "binomial arbitration" - that by using m = log n + 1 busses reduces the arbitration time to t = (1/2) log n. Extending this result, we present the "generalized binomial arbitration" scheme that achieves a bus-time tradeoff of the form m = O(t n^{1/t}) between the number of arbitration busses m, and the arbitration time t (in units of bus-settling delay), for values of 1 <= t <= log n and log n <= m <= n. Our schemes are based on a novel analysis of data-dependent delays and generalize the two known schemes: "linear arbitration", which with m = n busses achieves t = 1 units of time, and "binary arbitration", which with m = log n busses achieves t = log n time units. Most importantly, our schemes can be adopted with no changes to existing hardware and protocols; they merely involve selecting a "good" set of priority arbitration codewords.