Multi-level arbitration system for decentrally allocating resource priority among individual processing units

Claim 1

Apparatus for decentrally allocating resource priority among the individual processing units in a multi-processor system, each unit being assigned to a processing level and an individual position within that level, said apparatus including a plurality of arbitration means, each one coupled to a corresponding unit and to all other arbitration means in said system, each arbitration means comprising: first logic means for receiving at each of a plurality of first inputs, each input being coupled to all arbitration means of a given processing level, a first indicating signal indicating whether a request for resource access has been made by a unit of said given level, and for producing a first output signal at one of a plurality of first outputs, each output being coupled to arbitration means of one of said levels, said first output signal indicating which level will be granted priority in accordance with said first indicating signal and priority data stored in said first logic means, level priority being granted sequentially to all requesting levels; second logic means for receiving at each of a plurality of second inputs, each second input being coupled to a given unit with a same level as said corresponding unit, a second indicating signal indicating whether a request for resource access has been made by said given unit, and for producing a second output signal at one of a plurality of second outputs, said second output signal indicating which unit will be granted priority in accordance with said second indicating signal and priority data stored in said second logic means, unit priority being granted sequentially to all requesting units, and level priority having priority over unit priority; third logic means connected to one of said first outputs and to one of said second outputs for producing a signal granting resource access to said corresponding unit when said first and second output signals indicate that level and unit priority are to be granted to said corresponding unit; and means responsive to a request for resource access by said corresponding unit for producing a third output signal to be applied to one of said second inputs of said second logic means and to second inputs of said second logic means of other arbitration means on said given level, and for producing a fourth output to a applied to one of said first inputs of arbitration means of other levels.