Accelerated atomic resource allocation on a multiprocessor platform

• US 10,108,456 B2
• Filed: 02/02/2016
• Issued: 10/23/2018
• Est. Priority Date: 02/02/2016
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Jain, Harsh, Toukmaji, Abdulnour
• Primary Examiner(s): Cao, Diem
• Assistant Examiner(s): Do, Steven
• Application Number:
  US15/014,007
• Publication Number:
  US 20170220390A1
• Time in Patent Office: 994 Days
• Field of Search: None
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A method, system, and apparatus are provided for accelerated atomic resource allocation on a multiprocessor platform. In particular, a resource allocation engine (RAE) performs the following: counting available units for each of the one or more resources; parsing a multi-resource ticket (MRT) for a processor, wherein the parsing identifies one or more requested resource types, each resource type being paired with a requested resource units; comparing the multi-resource ticket to one or more resource queues for the requested resource types, wherein the comparing determines an availability status of at least one the requested resource types; and based on the availability status, calculating whether or not all of the requested resource types can be allocated for the processor, wherein the calculating is completed before allocating a next requested resource for a next processor.

Claims

1. A method, carried out by a resource allocation engine, for allocating one or more resources for a plurality of processors, the method comprising:

counting available units for each of the one or more resources;

parsing a multi-resource ticket (MRT) for a processor, wherein the parsing identifies one or more requested resource types, each resource type being paired with one or more requested resource units;

comparing the multi-resource ticket to one or more resource queues for the requested resource types, wherein the comparing determines an availability status of at least one the requested resource types; and

based on the availability status, calculating whether or not all of the requested resource types can be allocated for the processor, wherein the calculating is completed before allocating a next requested resource for a next processor wherein the calculating further includes determining all of the requested resource types can be allocated for the processor; and

allocating the requested resource types for the processor before allocating a next requested resource for a next processor wherein the allocating comprises;

pushing a pointer from a resource queue to the multi-resource ticket and then sending the multi-resource ticket to an allocation queue for the processor, wherein the allocation queue is a first-in-first-out;

executing, with the processor, the multi-resource ticket from the allocation queue.

2. The method of claim 1, further comprising:

after the allocating, notifying the processor that the requested resources types are allocated for the processor.

4. The method of claim 1, further comprising:

wherein the calculating further includes determining at least one of the requested resource types cannot be allocated for the processor; and

pushing a pointer for the multi-resource ticket to a retry queue before allocating a next requested resource for a next processor, wherein the retry queue is a first-in-first-out (FIFO) queue.

5. The method of claim 1, further comprising:

processing MRTs in a retry queue according to at least one of;

a maximum utilization of resources that are available to the resource allocation engine;

a quality of service (QoS) having a strict order of incoming requests to the resource allocation engine;

or

a more precisely calculated combination of the maximum utilization and the quality of service.

6. The method of claim 1, wherein each available resource unit is associated with a unique pointer in the resource queue.

7. The method of claim 6, wherein counting the available resource units further comprises:

counting a number of unique pointers in the resource queue.

8. The method of claim 1, wherein the multi-resource ticket is associated with a unique pointer in a request queue that includes pointers for a plurality of multi-resource tickets, and wherein the request queue is a first-in-first-out (FIFO) queue.

9. The method of claim 1, wherein the multi-resource ticket is a data structure of data fields, comprising at least one of:

an identifier for the multi-resource ticket;

a callback address;

an operation code;

the requested resource type;

or

the requested resource units.

3. The method of 1, further comprising:

receiving, from the processor, an updated multi-resource ticket having an operation code set to free, indicating the one or more requested resource types are free from allocation.

10. A resource allocation engine (RAE) for allocating one or more resources for a plurality of processors, the resource allocation engine comprising:

a processor to execute instructions; and

a memory device coupled to the processor, the memory device storing instructions for execution by the processor to cause the processor to perform;

counting available units for each of the one or more resources;

parsing a multi-resource ticket (MRT) for a processor, wherein the parsing identifies one or more requested resource types, each resource type being paired with one or more requested resource units;

comparing the multi-resource ticket to one or more resource queues for the requested resource types, wherein the comparing determines an availability status of at least one the requested resource types; and

based on the availability status, calculating whether or not all of the requested resource types can be allocated for the processor, wherein the calculating is completed before allocating a next requested resource for a next processor;

allocating the requested resource types for the processor before allocating a next requested resource for a next processor wherein the allocating comprises;

pushing a pointer from a resource queue to the multi-resource ticket and then sending the multi-resource ticket to an allocation queue for the processor, wherein the allocation queue is a first-in-first-out (FIFO) queue;

executing, with the processor, the multi-resource ticket from the allocation queue.

11. The resource allocation engine of claim 10, wherein the instructions further cause the processor to perform:

wherein the calculating further includes determining all of the requested resource types can be allocated for the processor; and

allocating the requested resource types for the processor before allocating a next requested resource for a next processor.

12. The resource allocation engine of claim 11, wherein the allocating comprises:

pushing a pointer for the multi-resource ticket to an allocation queue for the processor, wherein the allocation queue is a first-in-first-out (FIFO) queue.

13. The resource allocation engine of claim 11, wherein the instructions further cause the processor to perform:

after the allocating, notifying the processor that the requested resources types are allocated for the processor.

14. The resource allocation engine of claim 11, wherein the instructions further cause the processor to perform:

receiving, from the processor, an updated multi-resource ticket having an operation code set to free, indicating the one or more requested resource types are free from allocation.

15. A computer-readable product for allocating one or more resources for a plurality of processors, the computer-readable product including a non-transitory computer-readable storage medium storing instructions that when executed perform the functions comprising:

counting available units for each of the one or more resources;

parsing a multi-resource ticket (MRT) for a processor, wherein the parsing identifies one or more requested resource types, each resource type being paired with one or more requested resource units;

comparing the multi-resource ticket to one or more resource queues for the requested resource types, wherein the comparing determines an availability status of at least one the requested resource types; and

based on the availability status, calculating whether or not all of the requested resource types can be allocated for the processor, wherein the calculating is completed before allocating a next requested resource for a next processor wherein the functions further comprise;

wherein the calculating further includes determining all of the requested resource types can be allocated for the processor; and

allocating the requested resource types for the processor before allocating the next requested resource for the next processor wherein the allocating comprises;

pushing a pointer from a resource queue to the multi-resource ticket and then sending the multi-resource ticket to an allocation queue for the processor, wherein the allocation queue is a first-in-first-out (FIFO) queue;

executing, with the processor, the multi-resource ticket from the allocation queue.

16. The computer-readable product of claim 15, wherein the functions further comprise:

after the allocating, notifying the processor that the requested resources types are allocated for the processor.

17. The computer-readable product of claim 15, wherein the functions further comprise:

receiving, from the processor, an updated multi-resource ticket having an operation code set to free, indicating the one or more requested resource types are free from allocation.