Priority arbitration with busses
Shlomo Kipnis · Conference on Advanced Research in VLSI · 1990
Abstract : 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 = or < than m = or < than 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 tha arbitration time to t = 1/2 lg n. Extending this result, we present the generalized binomial arbitration scheme that achieves a bus-time tradeoff of the form m = Theta(tn to the 1 over t power) between the number of arbitration busses m and the arbitration time t (in units of bus-settling delay), for values of 1 = or < than t = or less than lg n and lg n = or < than m = or less than 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 codewords.