Patent ID: 8892801

Claim:
Arbitration circuitry for arbitrating between a plurality W of requests R for access to a shared resource, comprising: state bits storage configured to store I state bits Q and to generate 2I output bits comprising the true and compliment values of each stored state bit; routing circuitry configured to generate a set of mask signals M from the output bits, the set of mask signals encoding a priority ordering amongst the plurality of requests, with the mask signal M xy encoding whether the request R y has greater priority than the request R x ; grant circuitry configured to receive the set of mask signals and the plurality of requests, and to grant access to the shared resource to an asserted request from said plurality of requests that, having regard to the priority ordering encoded by the set of mask signals, has a higher priority than any other asserted request amongst said plurality of requests; state bit update circuitry configured in response to a trigger condition to perform an update operation to alter the value of at least one of the stored state bits thereby causing a change in the priority ordering encoded by the set of mask signals; the routing circuitry providing a pattern of connections such that each mask signal in the set is directly connected to one of said output bits; the pattern of connections being determined by a process at least equivalent to: (i) for each of the I state bits, forming an associated request grouping where the plurality of requests are split into a first group and a second group, such that for every combination of request x and request y, where x is not equal to y, there is at least one request grouping where request x and request y are not in the same group; and (ii) when determining the connections for the mask signals M xy and M yx , selecting one of the at least one request grouping where request x and request y are not in the same group, identifying the two output bits comprising the true and compliment values of the state bit associated with that selected request grouping, connecting the mask signal M xy to that one of those two output bits comprising the true value of the state bit if request x is in said first group, connecting the mask signal M xy to that one of those two output bits comprising the compliment value of the state bit if request x is in said second group, and connecting the mask signal M yx to the other of those two output bits not connected to the mask signal M xy .