LCS Publication Details
Publication Author: Kipnis, Shlomo
Additional Authors:
LCS Document Number: MIT-LCS-TM-408
Publication Date: 10-1-1989
LCS Group: No Group Specified
Additional URL: No URL Given
This paper explores 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 lg n m n, and use asynchronous combinational arbitration logic. A widely used distributed asynchronous mechanism is the binary arbitration scheme, which with m = lg n busses arbitrates in t = lg n units of time. We present a new asynchronous scheme -- binomial arbitration -- that by using m = lg n + 1 busses reduces the arbitration time to t = lg n. Extending this result, we present the generalized binomial arbitration scheme that achieves a bus-time tradeoff of the form m = Q( ) between the number of arbitration busses m and the arbitration time t (in units of bus-settling delay), for values of 1 t lg n and lg 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 time, and binary arbitration, which with m = lg n busses achieves t = lg n time. 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 code words.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.