Minimal-cost pseudo-round-robin arbiter

1. An apparatus comprising:

a first register configured to store requests from a plurality of clients for a current cycle;

a second register configured to store an indicator value indicating which of the plurality of clients received a grant in a previous cycle; and

a control logic configured to determine which of the plurality of clients having a request in the current cycle receives a grant in the current cycle based upon a comparison involving (i) a pointer value indicating which of the plurality of clients is first in line to receive the grant in the current cycle and (ii) said indicator value indicating which of the plurality of clients received the grant in the previous cycle, wherein the grant in the current cycle is given to one of the plurality of clients having a request in the current cycle that did not receive the grant in the previous cycle unless the client that received the grant in the previous cycle is the only client having a request in the current cycle.

2. The apparatus according to claim 1 , wherein said requests are for access to a shared resource.

3. The apparatus according to claim 2 , wherein the shared resource comprises a memory.

4. The apparatus according to claim 3 , wherein said apparatus is part of a memory interface coupling said plurality of clients to said memory.

5. The apparatus according to claim 1 , wherein said first register comprises a shift register configured to shift in response to said pointer value.

6. The apparatus according to claim 1 , wherein said first register comprises a N-bit shift register, where the plurality of clients comprises N clients.

7. The apparatus according to claim 6 , wherein said second register comprises a log(2)N bit register.

8. The apparatus according to claim 1 , wherein said first register is (i) shifted from an original position based upon said pointer value to determine which of the plurality of clients having a request in the current cycle receives the grant and (ii) shifted back to the original position to store requests from the plurality of clients for a next cycle.

9. The apparatus according to claim 1 , wherein said apparatus performs per cycle pseudo-round-robin arbitration of the requests from the plurality of clients and utilizes said indicator value to maintain fairness.

10. The apparatus according to claim 1 , wherein said control logic comprises a counter configured to generate said pointer value.

11. The apparatus according to claim 10 , wherein said counter keeps track of which of said plurality of clients is first in line for receiving a grant each cycle.

12. An apparatus comprising:

a first storage means configured to store requests from a plurality of clients for a current cycle;

a second storage means configured to store an indicator value indicating which of the plurality of clients received a grant in a previous cycle; and

means for determining which of the plurality of clients having a request in the current cycle receives a grant in the current cycle based upon a comparison involving (i) a pointer value indicating which of the plurality of clients is first in line to receive the grant in the current cycle and (ii) said indicator value indicating which of the plurality of clients received the grant in the previous cycle, wherein the grant in the current cycle is given to one of the plurality of clients having a request in the current cycle that did not receive the grant in the previous cycle unless the client that received the grant in the previous cycle is the only client having a request in the current cycle.

13. A method for allocating access to a shared resource comprising:

storing requests from a plurality of clients in a current cycle;

storing an indicator value indicating which of the plurality of clients received a grant in a previous cycle; and

determining which of the plurality of clients having a request in the current cycle receives a grant in the current cycle based upon a comparison involving (i) a pointer value indicating which of the plurality of clients is first in line to receive the grant in the current cycle and (ii) said indicator value indicating which of the plurality of clients received the grant in the previous cycle, wherein the grant in the current cycle is given to one of the plurality of clients having a request in the current cycle that did not receive the grant in the previous cycle unless the client that received the grant in the previous cycle is the only client having a request in the current cycle.

14. The method according to claim 13 , wherein determining which of the plurality of clients having a request in the current cycle receives the grant comprises:

selecting which client is initially allocated a round-robin slot during the current cycle;

determining whether the client allocated the round-robin slot is requesting access to the shared resource;

if the client is not requesting access, reallocating the round-robin slot to a next client that is requesting access;

determining whether the client that is currently allocated the round-robin slot was granted in the previous cycle;

if the client was granted in the previous cycle, reallocating the round-robin slot to a next client that is requesting access; and

when the client that is currently allocated the round-robin slot was not granted in the previous cycle, granting the client that is currently allocated the round-robin slot access to the shared resource.

15. The method according to claim 13 , wherein said requests are for access to a shared resource.

16. The method according to claim 15 , wherein the shared resource comprises a memory.

17. The method according to claim 16 , further comprising providing the client that receives the grant access to a common memory interface coupled to said memory.

18. The method according to claim 13 , further comprising storing said requests from said plurality of clients in the current cycle in a shift register, wherein said shift register is configured to shift in response to said pointer value.

19. The method according to claim 18 , further comprising:

shifting said shift register from an original position based upon said pointer value to determine which of the plurality of clients having a request in the current cycle receives the grant; and

shifting said shift register back to the original position and storing requests from the plurality of clients for a next cycle.

20. The method according to claim 13 , further comprising using a counter to generate said pointer value in response to a cycle clock.