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.