Bus-based priority arbitration system with optimum codewords

Claim 1

In a digital system having a plurality of modules coupled to a plurality of arbitration busses, an arbitration system comprising: means for assigning binary codewords to modules of the digital system, each codeword having a different binary value for indicating a different priority of a module than that indicated by the other codewords, successively higher-valued binary codewords indicating successively higher priorities, different codewords being assigned to different modules such that different modules have different priorities as indicated by respective codewords of the modules, and during arbitration, resolution of each codeword producing data-dependent delays sufficiently small to reduce, by a factor of s, time required to resolve the codewords during arbitration such that arbitration time t, in units of bus-settling delay, one unit being the amount of time required for an arbitration buss to stabilize, satisfies t≦ log.sub.2 n /s where s>1, and n is maximum number of modules supportable by the digital system, the codewords being selected from a set of optimal codewords which (i) minimize arbitration time t when number of modules n and number of arbitration busses m are known, (ii) maximize number of modules n when arbitration time t and number of arbitration busses m are known, and (iii) minimize number of arbitration busses m when arbitration time t and number of modules n are known; and an arbitration circuit for providing to the modules an arbitration protocol performed by modules involved in an arbitration, the arbitration protocol enabling each module involved in an arbitration to (a) apply its binary codeword to arbitration busses of the digital system, (b) continuously monitor arbitration busses, and (c) conditionally disable application of a portion of its binary codeword according to binary values of portions of codewords applied to arbitration busses by other modules in a manner such that final logic values on the arbitration busses provide the binary value of the codeword of highest binary value involved in the arbitration, the respective module assigned to that codeword being determined as the highest priority module involved in the arbitration with respect to the other modules involved in the arbitration as indicated by the codewords of the modules.

Claim 18

A method of arbitrating among a plurality of modules in a digital system, the method comprising the steps of: providing a plurality of multi-bit binary priority codewords for indicating different priorities of different modules, each codeword having a different binary value, codewords of successively higher binary values indicating successively higher priorities, each priority codeword being selected from a set of optimal codewords as a function of arbitration time t, in units of bus-settling delay, one unit of bus-settling delay being the amount of time for an arbitration bus to stabilize, and as a function of a number of arbitration busses m required for arbitration, including having a length of m bits and at most t intervals of consecutive same binary digits when disregarding consecutive leading 0 digits, where t<m such that resolution of codewords during arbitration exhibits controlled data-dependent delays; assigning different priority codewords to different modules supportable in the desired digital system; and during arbitration among contending modules of the desired digital system, performing on the contending modules an arbitration protocol which enables each contending module to (a) apply its binary priority codeword to the arbitration busses of the desired digital system, (b) continuously monitor arbitration busses, and (c) conditionally disable application of a portion of the codeword of the contending module according to binary values of portions of codewords applied to arbitration busses by other contending modules, in a manner such that final logic values on the arbitration busses provide the binary value of the codeword of highest binary value involved in the arbitration, the contending module assigned to that codeword being determined as the module of highest priority involved in the arbitration.

Claim 19

A method of arbitrating among a plurality of modules in a digital system, the method comprising the steps of: providing a plurality of multi-bit binary priority codewords for indicating different priorities of different modules, each codeword having a different binary value, codewords of successively higher binary values indicating successively higher priorities, each priority codeword being selected from a set of optimal codewords as a function of arbitration time t, in units of bus-settling delay, one unit of bus-settling delay being the amount of time for an arbitration bus to stabilize, and as a function of a number of arbitration busses m required for arbitration, including having a length of m bits and at most t intervals of consecutive same binary digits when disregarding consecutive leading 0 digits, where t<m such that resolution of codewords during arbitration exhibits controlled data-dependent delays; assigning different priority codewords to different modules supportable in the desired digital system; and during arbitration among contending modules of the desired digital system, performing on the contending modules an arbitration protocol which enables each contending module to (a) apply its binary priority codeword to the arbitration busses of the desired digital system, (b) continuously monitor arbitration busses, and (c) conditionally disable application of a portion of the codeword of the contending module according to binary values of portions of codewords applied to arbitration busses by other contending modules, in a manner such that final logic values on the arbitration busses provide the binary value of the codeword of highest binary value involved in the arbitration, the contending module assigned to that codeword being determined as the module of highest priority involved in the arbitration.

Claim 23

A method of arbitrating on a set of arbitration busses in a digital system comprising the steps of: given two of three parameters: (a) m, number of arbitration busses in a desired digital system, (b) t, arbitration time in units of bus-settling delay of the desired digital system, a unit of bus-settling delay being the amount of time required for an arbitration buss to stabilize and (c) n, maximal number of modules supportable by the desired digital system, optimizing the remaining parameter such that ##EQU16## selecting from a set of possible binary priority codewords a plurality of optimum binary priority codewords for indicating different priorities of different modules, each codeword having a different binary value, codewords of successively higher binary values indicating successively higher priorities, said selecting being performed such that (i) m is minimized when t and n are given, (ii) n is maximized when m and t are given, or (iii) t is minimized when m and n are given, each optimum binary priority codeword having a length of m-bits and having at most t intervals of consecutive same binary digits when disregarding consecutive leading zero digits; assigning different selected optimum priority codewords of successively higher binary values to different modules of successively higher desired priority in the desired digital system; and during arbitration among contending modules of the desired digital system, performing an arbitration protocol on the contending modules such that each contending module applies its binary priority codeword to the arbitration busses, monitors the arbitration busses, and conditionally disables application of a portion of its codeword according to binary values of portions of codewords applied to arbitration busses by other contending modules, such that final logic values on the arbitration busses provide the binary value of the codeword of highest binary value involved in the arbitration, the contending module assigned to that codeword being determined as the module of highest priority involved in the arbitration.

Claim 24

A method of arbitrating on a set of arbitration busses in a digital system comprising the steps of: given two of three parameters: (a) m, number of arbitration busses in a desired digital system, (b) t, arbitration time in units of bus-settling delay of the desired digital system, a unit of bus-settling delay being the amount of time required for an arbitration buss to stabilize and (c) n, maximal number of modules supportable by the desired digital system, optimizing the remaining parameter such that ##EQU16## selecting from a set of possible binary priority codewords a plurality of optimum binary priority codewords for indicating different priorities of different modules, each codeword having a different binary value, codewords of successively higher binary values indicating successively higher priorities, said selecting being performed such that (i) m is minimized when t and n are given, (ii) n is maximized when m and t are given, or (iii) t is minimized when m and n are given, each optimum binary priority codeword having a length of m-bits and having at most t intervals of consecutive same binary digits when disregarding consecutive leading zero digits; assigning different selected optimum priority codewords of successively higher binary values to different modules of successively higher desired priority in the desired digital system; and during arbitration among contending modules of the desired digital system, performing an arbitration protocol on the contending modules such that each contending module applies its binary priority codeword to the arbitration busses, monitors the arbitration busses, and conditionally disables application of a portion of its codeword according to binary values of portions of codewords applied to arbitration busses by other contending modules, such that final logic values on the arbitration busses provide the binary value of the codeword of highest binary value involved in the arbitration, the contending module assigned to that codeword being determined as the module of highest priority involved in the arbitration.