Priority Arbitration with Busses
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 16, 1989
- Accession Number
- ADA216392
Entities
People
- Shlomo Kipnis
Organizations
- Massachusetts Institute of Technology