Priority control in resource allocation for low request rate, latency-sensitive units

• US 20070101033A1
• Filed: 10/27/2005
• Published: 05/03/2007
• Est. Priority Date: 10/27/2005
• Status: Active Grant

• Current Assignee: Daedalus Blue LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Raghavan, Ram, Johns, Charles, Wottreng, Andrew, Chen, Wen-Tzer
• Granted Patent: US 7,631,131 B2
• Time in Patent Office: Days
• US Class Current: 710/241
• CPC Class Codes: G06F 13/362 with centralised access control

Abstract

A mechanism for priority control in resource allocation for low request rate, latency-sensitive units is provided. With this mechanism, when a unit makes a request to a token manager, the unit identifies the priority of its request as well as the resource which it desires to access and the unit'"'"'s resource access group (RAG). This information is used to set a value of a storage device associated with the resource, priority, and RAG identified in the request. When the token manager generates and grants a token to the RAG, the token is in turn granted to a unit within the RAG based on a priority of the pending requests identified in the storage devices associated with the resource and RAG. Priority pointers are utilized to provide a round-robin fairness scheme between high and low priority requests within the RAG for the resource.

Claims

1. A method, in a data processing system, for controlling access to a resource, comprising:

generating and granting a token to a resource allocation group, wherein the resource allocation group comprises one or more operational units within the data processing system;

obtaining request information from a group of request storage devices associated with the resource allocation group and the resource, wherein the group of request storage devices is separated into a first sub-group of first priority request storage devices and a second sub-group of second priority request storage devices;

selecting an operational unit from the one or more operational units to receive the token based on the request information obtained from the group of request storage devices; and

granting the token to the selected operational unit, wherein the selected operational unit uses the token to access the resource.

2. The method of claim 1, wherein the token is generated and granted to the resource allocation group in response to a counter associated with the resource allocation group reaching a predetermined value.

3. The method of claim 1, wherein the resource allocation group is allocated a portion, less than a full amount, of the resource to be shared by the one or more operational units.

4. The method of claim 1, wherein obtaining request information from a group of request storage devices associated with the resource allocation group and the resource comprises:

obtaining a value of a first pointer associated with the first sub-group of first priority request storage devices;

obtaining a value of a second pointer associated with a second sub-group of second priority request storage devices;

determining if there is a pending first priority request for access to the resource based on the value of the first pointer; and

determining if there is a pending second priority request for access to the resource based on the value of the second pointer.

5. The method of claim 4, wherein selecting an operational unit from the one or more operational units to receive the token based on the request information obtained from the group of request storage devices, comprises:

selecting an operational unit associated with the first priority request if a pending first priority request is identified by the value of the first pointer; and

selecting an operational unit associated with the second priority request if a pending second priority request is identified by the value of the second pointer and the value of the first pointer indicates that a first priority request is not pending.

6. The method of claim 4, wherein the first sub-group of first priority request storage devices may contain a pending first priority request yet the first pointer may indicate that a first priority request is not pending if the first pointer points to an empty first priority request storage device.

7. The method of claim 4, further comprising:

incrementing the value of the first pointer to point to a next first priority request storage device in the first sub-group of first priority request storage devices if a request associated with a current value of the first pointer is dispatched; and

incrementing the value of the second pointer to point to a next second priority request storage device in the second sub-group of first priority request storage devices if a request associated with a current value of the second pointer is dispatched.

8. The method of claim 4, further comprising:

incrementing the value of the first pointer to point to a next non-empty first priority request storage device in the first sub-group of first priority request storage devices if a request associated with a current value of the first pointer is dispatched; and

incrementing the value of the second pointer to point to a next non-empty second priority request storage device in the second sub-group of first priority request storage devices if a request associated with a current value of the second pointer is dispatched.

9. The method of claim 1, wherein the data processing system supports a plurality of resource allocation groups and a plurality of managed resources, wherein each resource allocation group has a set of request storage devices, and wherein the set of request storage devices for each resource allocation group is organized into a group of request storage devices for each managed resource, and wherein each group of request storage devices for each managed resource is organized into a first sub-set of request storage devices associated with first priority requests and a second sub-set of request storage devices associated with second priority requests.

10. The method of claim 9, wherein each combination of resource allocation group and managed resource has an associated counter for determining when to allocate a token for accessing the managed resource to the particular resource allocation group.

11. The method of claim 1, wherein the resource allocation group comprises one or more operational units within the data processing system that have a same resource allocation identifier.

38. The method of claim 1, wherein the data processing system is a multiprocessor system-on-a-chip having at least two heterogeneous processors.

12. A computer program product comprising a computer usable medium having a computer readable program, wherein the computer readable program, when executed on a computing device, causes the computing device to:

generate and grant a token to a resource allocation group, wherein the resource allocation group comprises one or more operational units within a data processing system;

obtain request information from a group of request storage devices associated with the resource allocation group and the resource, wherein the group of request storage devices is separated into a first sub-group of first priority request storage devices and a second sub-group of second priority request storage devices;

select an operational unit from the one or more operational units to receive the token based on the request information obtained from the group of request storage devices; and

grant the token to the selected operational unit, wherein the selected operational unit uses the token to access a resource.

13. The computer program product of claim 12, wherein the token is generated and granted to the resource allocation group in response to a counter associated with the resource allocation group reaching a predetermined value.

14. The computer program product of claim 12, wherein the resource allocation group is allocated a portion, less than a full amount, of the resource to be shared by the one or more operational units.

15. The computer program product of claim 12, wherein the computer readable program causes the computing device to obtain request information from a group of request storage devices associated with the resource allocation group and the resource by:

obtaining a value of a first pointer associated with the first sub-group of first priority request storage devices;

obtaining a value of a second pointer associated with a second sub-group of second priority request storage devices;

determining if there is a pending first priority request for access to the resource based on the value of the first pointer; and

determining if there is a pending second priority request for access to the resource based on the value of the second pointer.

16. The computer program product of claim 15, wherein the computer readable program causes the computing device to select an operational unit from the one or more operational units to receive the token based on the request information obtained from the group of request storage devices, by:

selecting an operational unit associated with the first priority request if a pending first priority request is identified by the value of the first pointer; and

selecting an operational unit associated with the second priority request if a pending second priority request is identified by the value of the second pointer and the value of the first pointer indicates that a first priority request is not pending.

17. The computer program product of claim 15, wherein the first sub-group of first priority request storage devices may contain a pending first priority request yet the first pointer may indicate that a first priority request is not pending if the first pointer points to an empty first priority request storage device.

18. The computer program product of claim 15, wherein the computer readable program further causes the computing device to:

increment the value of the first pointer to point to a next first priority request storage device in the first sub-group of first priority request storage devices if a request associated with a current value of the first pointer is dispatched; and

increment the value of the second pointer to point to a next second priority request storage device in the second sub-group of first priority request storage devices if a request associated with a current value of the second pointer is dispatched.

19. The computer program product of claim 15, wherein the computer readable program further causes the computing device to:

increment the value of the first pointer to point to a next non-empty first priority request storage device in the first sub-group of first priority request storage devices if a request associated with a current value of the first pointer is dispatched; and

increment the value of the second pointer to point to a next non-empty second priority request storage device in the second sub-group of first priority request storage devices if a request associated with a current value of the second pointer is dispatched.

20. The computer program product of claim 12, wherein the data processing system supports a plurality of resource allocation groups and a plurality of managed resources, wherein each resource allocation group has a set of request storage devices, and wherein the set of request storage devices for each resource allocation group is organized into a group of request storage devices for each managed resource, and wherein each group of request storage devices for each managed resource is organized into a first sub-set of request storage devices associated with first priority requests and a second sub-set of request storage devices associated with second priority requests.

21. The computer program product of claim 20, wherein each combination of resource allocation group and managed resource has an associated counter for determining when to allocate a token for accessing the managed resource to the particular resource allocation group.

22. The computer program product of claim 12, wherein the resource allocation group comprises one or more operational units within the data processing system that have a same resource allocation identifier.

39. The computer program product of claim 12, wherein the computing device is part of a multiprocessor system-on-a-chip having at least two heterogeneous processors.

23. An apparatus, comprising:

a processor;

a plurality of operational units coupled to the processor;

a resource coupled to the plurality of operational units;

a memory coupled to the processor; and

a plurality of request storage devices coupled to the processor, wherein the memory stores instructions which, when executed by the processor, cause the processor to;

generate and grant a token to a resource allocation group, wherein the resource allocation group comprises one or more operational units, from the plurality of operational units;

obtain request information from a group of request storage devices, in the plurality of request storage devices, associated with the resource allocation group and the resource, wherein the group of request storage devices is separated into a first sub-group of first priority request storage devices and a second sub-group of second priority request storage devices;

select an operational unit from the one or more operational units to receive the token based on the request information obtained from the group of request storage devices; and

grant the token to the selected operational unit, wherein the selected operational unit uses the token to access the resource.

24. The apparatus of claim 23, wherein the processor generates and grants the token to the resource allocation group in response to a counter associated with the resource allocation group reaching a predetermined value.

25. The apparatus of claim 23, wherein the resource allocation group is allocated a portion, less than a full amount, of the resource to be shared by the one or more operational units.

26. The apparatus of claim 23, wherein the processor obtains request information from a group of request storage devices associated with the resource allocation group and the resource by:

obtaining a value of a first pointer associated with the first sub-group of first priority request storage devices;

obtaining a value of a second pointer associated with a second sub-group of second priority request storage devices;

determining if there is a pending first priority request for access to the resource based on the value of the first pointer; and

determining if there is a pending second priority request for access to the resource based on the value of the second pointer.

27. The apparatus of claim 26, wherein the instructions cause the processor to select an operational unit from the one or more operational units to receive the token based on the request information obtained from the group of request storage devices, by:

selecting an operational unit associated with the first priority request if a pending first priority request is identified by the value of the first pointer; and

selecting an operational unit associated with the second priority request if a pending second priority request is identified by the value of the second pointer and the value of the first pointer indicates that a first priority request is not pending.

28. The apparatus of claim 26, wherein the first sub-group of first priority request storage devices may contain a pending first priority request yet the first pointer may indicate that a first priority request is not pending if the first pointer points to an empty first priority request storage device.

29. The apparatus of claim 26, wherein the instructions further cause the processor to:

increment the value of the first pointer to point to a next first priority request storage device in the first sub-group of first priority request storage devices if a request associated with a current value of the first pointer is dispatched; and

increment the value of the second pointer to point to a next second priority request storage device in the second sub-group of first priority request storage devices if a request associated with a current value of the second pointer is dispatched.

30. The apparatus of claim 26, wherein the instructions further cause the processor to:

increment the value of the first pointer to point to a next non-empty first priority request storage device in the first sub-group of first priority request storage devices if a request associated with a current value of the first pointer is dispatched; and

increment the value of the second pointer to point to a next non-empty second priority request storage device in the second sub-group of first priority request storage devices if a request associated with a current value of the second pointer is dispatched.

31. The apparatus of claim 23, wherein the apparatus is part of a data processing system, and wherein the data processing system supports a plurality of resource allocation groups and a plurality of managed resources, wherein each resource allocation group has a set of request storage devices, and wherein the set of request storage devices for each resource allocation group is organized into a group of request storage devices for each managed resource, and wherein each group of request storage devices for each managed resource is organized into a first sub-set of request storage devices associated with first priority requests and a second sub-set of request storage devices associated with second priority requests.

32. The apparatus of claim 31, wherein each combination of resource allocation group and managed resource has an associated counter for determining when to allocate a token for accessing the managed resource to the particular resource allocation group.

33. The apparatus of claim 23, wherein the apparatus is part of a data processing system, and wherein the resource allocation group comprises one or more operational units within the data processing system that have a same resource allocation identifier.

34. The apparatus of claim 23, wherein the apparatus is a system-on-a-chip.

35. The apparatus of claim 34, wherein the system-on-a-chip is part of an information handling system.

36. The apparatus of claim 35, wherein the information handling system is one of a desktop data processing system, a server, a portable data processing system, a laptop data processing system, a notebook data processing system, a personal digital assistant, a gaming device, a gaming console, a portable telephone device, or a communication device.

37. The apparatus of claim 23, wherein the apparatus is a multiprocessor system-on-a-chip having at least two heterogeneous processors.