Method and apparatus for efficient implementation of round robin control unit
View Patent ↗An apparatus is described having a plurality of grant generation units. The plurality of grant generation units are arranged according to a round robin grant eligibility hierarchy, such that, one grant generation unit exists for each of a plurality of request agents. A grant generation unit is chosen to provide an output specifying which request agent, from the plurality of request agents is to receive a grant. The chosen grant generation unit is chosen because its corresponding request agent is the next request agent in the round robin grant eligibility hierarchy to be recognized as being eligible for a grant.
1. A method, comprising:
a) rolling a vector of request values to form a first rolled vector and a second rolled vector, said first rolled vector having a different amount of rolled request values than said second rolled vector, said request values provided by a plurality of request agents, a position within said first rolled vector being reserved for a request value that was provided by a first request agent, a position within said second rolled vector being reserved for a request value that was provided by a second request; and,
b) if said first request agent is eligible for a grant in a round robin grant eligibility hierarchy:
extracting a first active request value that is observed in said first rolled vector starting from said position within said first rolled vector and extending in a direction toward a request value provided by a next request agent to be recognized as being grant eligible within said eligibility hierarchy;
if said first request agent is not eligible for a grant in said round robin eligibility hierarchy:
extracting a first active request value that is observed in said second rolled vector starting from said position within said second rolled vector and extending in a direction toward a request value provided by a next request agent to be recognized as being grant eligible within said eligibility hierarchy.
2. The method of claim 1 wherein said position is the least significant position.
3. The method of claim 2 further comprising scanning said rolled vector for said first active request value, said scanning starting at said position.
4. The method of claim 3 further comprising issuing a grant to that request agent of said request agents whose request corresponds to said active request value.
5. The method of claim 1 wherein said position is the most significant position.
6. The method of claim 5 further comprising scanning said rolled vector for an active request value, said scanning starting at said position.
7. The method of claim 6 further comprising issuing a grant to that request agent of said request agents whose request corresponds to said active request value.
8. The method of claim 1 wherein said grant is a grant for bandwidth resources.
9. The method of claim 1 wherein said grant is a grant for routing resources.
10. The method of claim 1 wherein said grant is a grant for switching resources.
11. The method of claim 1 wherein said grant is a grant for processing resources.
12. The method of claim 1 wherein said extracted first active request value is first provided in an output vector arranged as said rolled vector is arranged.
13. The method of claim 12 further comprising un-rolling said output vector so as to produce a second output vector arranged as said vector of request values is arranged.
14. An apparatus, comprising:
a first bit extraction unit that receives a first rolled vector of request values, said request values provided by a plurality of request agents, said first bit extraction unit designed to extract a first active bit observed in said first rolled vector, if said first rolled vector has request value that was provided by a request agent that is to be recognized as being grant eligible positioned at an end position of said first rolled vector, starting from said end position and extending in a direction toward a request value that is to be recognized as a request from a next request agent to be recognized as being grant eligible within said eligibility hierarchy; and,
a second bit extraction unit that receives a second rolled vector of said request values, said second rolled vector having a different amount of rolled request values as compared to said first rolled vector, said second bit extraction unit designed to extract a first active bit observed in said second rolled vector, if said second rolled vector has a request value that was provided by a request agent that is to be recognized as being grant eligible positioned at an end position of said second rolled vector, starting from said end position of said second rolled vector and extending in a direction toward a request value that is to be recognized as a request from a next request agent to be recognized as being grant eligible within said eligibility hierarchy.
15. The apparatus of claim 14 wherein said end position of said first rolled vector is the least significant position.
16. The apparatus of claim 15 wherein said bit extraction unit scans said rolled vector for an active bit, said scanning starting at said end position of first rolled vector.
17. The apparatus of claim 14 wherein said end position of said first rolled vector is the most significant position.
18. The apparatus of claim 17 wherein said bit extraction unit scans said rolled vector for an active request value, said scanning starting at said end position of said first rolled vector.
19. A method, comprising:
choosing, from a plurality of grant generation units, a grant generation unit that is to provide an output specifying which request agent, from a plurality of request agents, is to receive a grant; wherein said plurality of grant generation units are arranged according to a round robin grant eligibility hierarchy, such that, one grant generation unit exists for each request agent; and wherein said chosen grant generation unit is chosen because its corresponding request agent is the next request agent in said round robin grant eligibility hierarchy to be recognized as being eligible for a grant.
20. The method of claim 19 further comprising providing an input vector of request values to said grant generation unit, said request values generated by said request agents.
21. The method of claim 20 further comprising rolling said input vector, said rolling of said vector resulting in a rolled vector that reflects said round robin grant eligibility hierarchy and wherein a position within said rolled vector is reserved for a request value that was provided by said corresponding request agent.
22. The method of claim 21 further comprising extracting a first active request value that is observed in said rolled vector, starting from said position and extending in a direction toward a request value that is to be recognized as a request from a next request agent to be recognized as being grant eligible within said eligibility hierarchy.
23. The method of claim 22 wherein said position is the least significant position.
24. The method of claim 23 further comprising scanning said rolled vector for said first active request value, said scanning starting at said position.
25. The method of claim 22 wherein said position is the most significant position.
26. The method of claim 25 further comprising scanning said rolled vector for an active request value, said scanning starting at said position.
27. The method of claim 22 further comprising issuing a grant to that request agent of said request agents whose request corresponds to said active request value.
28. The method of claim 27 wherein said grant is a grant for bandwidth resources.
29. The method of claim 27 wherein said grant is a grant for routing resources.
30. The method of claim 27 wherein said grant is a grant for switching resources.
31. The method of claim 27 wherein said grant is a grant for processing resources.
32. The method of claim 22 wherein said extracted first active request value is first provided in an output vector arranged as said rolled vector is arranged.
33. The method of claim 32 further comprising un-rolling said output vector so as to produce a second output vector arranged as said vector of request values is arranged.
34. An apparatus, comprising:
a plurality of grant generation units, wherein said plurality of grant generation units are arranged according to a round robin grant eligibility hierarchy, such that, one grant generation unit exists for each of a plurality of request agents; and wherein a grant generation unit is chosen to provide an output specifying which request agent, from said plurality of request agents is to receive a grant, said chosen grant generation unit being chosen because its corresponding request agent is the next request agent in said round robin grant eligibility hierarchy to be recognized as being eligible for a grant.
35. The apparatus of claim 34 wherein each of said grant generation units receive an input vector of request values.
36. The apparatus of claim 35 wherein each of said grant generation units roll said input vector to form a rolled vector, said rolled vector reflecting said round robin grant eligibility hierarchy and wherein a position within said rolled vector is reserved for a request value that was provided by the corresponding request agent for each of said grant generation units.
37. The apparatus of claim 36 wherein each of said grant generation units further comprise a bit extraction unit that extracts a first active request value that is observed in said rolled vector, starting from said position and extending in a direction toward a request value that is to be recognized as a request from a next request agent to be recognized as being grant eligible within said eligibility hierarchy.
38. The apparatus of claim 37 wherein said position is the least significant position.
39. The apparatus of claim 38 wherein said position is the most significant position.
40. The apparatus of claim 34 wherein said grant is for bandwidth resources.
41. The apparatus of claim 37 wherein each of said grant generation units provide their said extracted first active request value in an output vector arranged as said rolled vector is arranged.
42. The apparatus of claim 41 wherein each of said grant generation units un-roll their said output vector so as to produce a second output vector arranged as said vector of request values is arranged.
43. The apparatus of claim 34 wherein said grant is a grant for bandwidth resources.
44. The apparatus of claim 34 wherein said grant is a grant for routing resources.
45. The apparatus of claim 34 wherein said grant is a grant for switching resources.
46. The apparatus of claim 34 wherein said grant is a grant for processing resources.
47. A machine readable medium having stored thereon a description of a circuit, said circuit comprising:
a first bit extraction unit that receives a first rolled vector of request values, said request values provided by a plurality of request agents, said first bit extraction unit designed to extract a first active bit observed in said first rolled vector, if said first rolled vector has request value that was provided by a request agent that is to be recognized as being grant eligible positioned at an end position of said first rolled vector, starting from said end position and extending in a direction toward a request value that is to be recognized as a request from a next request agent to be recognized as being grant eligible within said eligibility hierarchy; and,
a second bit extraction unit that receives a second rolled vector of said request values, said second rolled vector having a different amount of rolled request values as compared to said first rolled vector, said second bit extraction unit designed to extract a first active bit observed in said second rolled vector, if said second rolled vector has a request value that was provided by a request agent that is to be recognized as being grant eligible positioned at an end position of said second rolled vector, starting from said end position of said second rolled vector and extending in a direction toward a request value that is to be recognized as a request from a next request agent to be recognized as being grant eligible within said eligibility hierarchy.
48. The machine readable medium of claim 47 wherein said end position of said first called vector is the least significant position.
49. The machine readable medium of claim 48 wherein said bit extraction unit scans said rolled vector for an active bit, said scanning starting at said end position of said first rolled vector.
50. The machine readable medium of claim 47 wherein said end position of said first rolled vector is the most significant position.
51. The machine readable medium of claim 50 wherein said bit extraction unit scans said rolled vector for an active request value, said scanning starting at said end position of said first rolled vector.
52. A machine readable medium having stored thereon a description of circuit, said description of a circuit comprising:
a plurality of grant generation units, wherein said plurality of grant generation units are arranged according to a round robin grant eligibility hierarchy, such that, one grant generation unit exists for each of a plurality of request agents; and wherein a grant generation unit is chosen to provide an output specifying which request agent, from said plurality of request agents is to receive a grant, said chosen grant generation unit being chosen because its corresponding request agent is the next request agent in said round robin grant eligibility hierarchy to be recognized as being eligible for a grant.
53. The machine readable medium of claim 52 wherein each of said grant generation units receive an input vector of request values.
54. The machine readable medium of claim 53 wherein each of said grant generation units roll said input vector to form a rolled vector, said rolled vector reflecting said round robin grant eligibility hierarchy and wherein a position within said rolled vector is reserved for a request value that was provided by the corresponding request agent for each of said grant generation units.
55. The machine readable medium of claim 54 wherein each of said grant generation units further comprise a bit extraction unit that extracts a first active request value that is observed in said rolled vector, starting from said position and extending in a direction toward a request value that is to be recognized as a request from a next request agent to be recognized as being grant eligible within said eligibility hierarchy.
56. An apparatus, comprising:
a round robin control unit having an input bus to receive a vector of requests from a plurality of request agents, said round robin control unit having an output bus to provide a vector that identifies which particular one of said request agents is to be considered as being provided a grant, said round robin control unit comprising a plurality of grant generation units, each grant generation unit uniquely coupled to said input bus so as to receive its own unique arrangement of said vector of requests, each grant generation output coupled to said output bus, the number of said grant generation units being equal to the number of said request agents.