Scalable random arbiter

A method for arbitration, comprising:

• receiving a vector of requests for a resource;
• applying a randomly-selected permutation to the vector of requests, so as to produce a permuted vector;
• selecting an element of the permuted vector;
• applying to the permuted vector an inverse of the randomly-selected permutation, so as to produce an inversely-permuted vector;
• identifying an element of the inversely-permuted vector to which the selected element of the permuted vector is mapped;
• and
• assigning the resource to a client corresponding to the identified element of the inversely-permuted vector,
• wherein applying the randomly-selected permutation comprises applying to the vector of requests a plurality of single-permutation blocks, each single-permutation block controlled by a respective bit of a randomly-selected control word that determines whether the single-permutation block applies a fixed respective permutation or applies no permutation.

An electronic apparatus, comprising:

• a permutation circuit, configured to apply to an input vector a permutation selected from a plurality of predefined permutations in response to a control word;
• and
• an arbitration circuit, configured to:
• receive a vector of requests for a resource;
• instruct the permutation circuit to apply a randomly-selected permutation to the vector of requests, by configuring the permutation circuit with a corresponding randomly-selected control word, so as to produce a permuted vector;
• select an element of the permuted vector;
• apply to the permuted vector an inverse of the randomly-selected permutation, so as to produce an inversely-permuted vector;
• identify an element of the inversely-permuted vector to which the selected element of the permuted vector is mapped;
• and
• assign the resource to a client corresponding to the identified element of the inversely-permuted vector,
• wherein the arbitration circuit is configured to:
• before applying the inverse of the randomly-selected permutation to the permuted vector, null the elements of the permuted vector other than the selected element;
• and
• identify the element of the inversely-permuted vector to which the selected element of the permuted vector is mapped, by identifying the element of the inversely-permuted vector that is not nulled.

A method for arbitration, comprising:

• receiving a vector of requests for a resource;
• applying a randomly-selected permutation to the vector of requests, so as to produce a permuted vector;
• selecting an element of the permuted vector;
• applying to the permuted vector an inverse of the randomly-selected permutation, so as to produce an inversely-permuted vector;
• identifying an element of the inversely-permuted vector to which the selected element of the permuted vector is mapped;
• assigning the resource to a client corresponding to the identified element of the inversely-permuted vector;
• and
• nulling the elements of the permuted vector other than the selected element before applying the inverse of the randomly-selected permutation to the permuted vector, wherein identifying the element of the inversely-permuted vector to which the selected element of the permuted vector is mapped comprises identifying the element of the inversely-permuted vector that is not nulled.