System and Method for Out-of-Order Resource Allocation and Deallocation in a Threaded Machine

• US 20100318998A1
• Filed: 06/16/2009
• Published: 12/16/2010
• Est. Priority Date: 06/16/2009
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Golla, Robert T.
• Granted Patent: US 9,690,625 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/507 Low-level
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals

Abstract

A system and method for managing the dynamic sharing of processor resources between threads in a multi-threaded processor are disclosed. Out-of-order allocation and deallocation may be employed to efficiently use the various resources of the processor. Each element of an allocate vector may indicate whether a corresponding resource is available for allocation. A search of the allocate vector may be performed to identify resources available for allocation. Upon allocation of a resource, a thread identifier associated with the thread to which the resource is allocated may be associated with the allocate vector entry corresponding to the allocated resource. Multiple instances of a particular resource type may be allocated or deallocated in a single processor execution cycle. Each element of a deallocate vector may indicate whether a corresponding resource is ready for deallocation. Examples of resources that may be dynamically shared between threads are reorder buffers, load buffers and store buffers.

Claims

1. A method, comprising:

using a computer to perform;

allocating one of a plurality of resources on behalf of one of a plurality of threads;

updating a data structure to indicate that the one of the plurality of resources has been allocated to the one of the plurality of threads, wherein the data structure comprises a plurality of sequentially addressable elements;

deallocating the one of the plurality of resources after the resource has been released by the one of the plurality of threads; and

updating the data structure to indicate that the one of the plurality of resources has been deallocated;

wherein at least one of said allocating or said deallocating updates an element of the data structure other than an element sequentially adjacent to an element updated in a most recent previous allocation or deallocation operation.

2. The method of claim 1, wherein the data structure comprises a number of elements equal to a maximum number of available resources of a particular resource type.

3. The method of claim 1, wherein said updating the data structure to indicate that the one of the plurality of resources has been allocated to the one of the plurality of threads comprises updating a data structure element associated with the one of the plurality of resources such that the updated data structure element comprises a value indicating that the one of the plurality of resources has been allocated.

4. The method of claim 1, wherein said updating the data structure to indicate that the one of the plurality of resources has been allocated to the one of the plurality of threads comprises storing an identifier of the one of the plurality of threads in a data structure element associated with the one of the plurality of resources.

5. The method of claim 1, further comprising:

using the computer to perform;

searching the data structure to determine a next resource available for allocation, wherein a search result returns a value indicating a resource available for allocation;

wherein the value returned by the search result indicates the one of the plurality of resources to be allocated on behalf of one of a plurality of threads.

6. The method of claim 5, wherein said searching the data structure comprises performing two or more concurrent searches on the data structure.

7. The method of claim 1,

wherein said deallocating comprises deallocating a plurality of resources allocated to the one of the plurality of threads in a single execution cycle;

and

wherein said updating the data structure to indicate that the one of the plurality of resources has been deallocated comprises updating a respective data structure element associated with each of the deallocated resources.

8. The method of claim 7, wherein at least one of the respective data structure elements associated with the deallocated resources is not adjacent to any other ones of the respective data structure elements associated with the deallocated resources.

9. The method of claim 1, further comprising

using the computer to perform:

accessing a deallocate vector identifying one or more of the plurality of resources for deallocation;

wherein said deallocating comprises deallocating at least one of the one or more of the plurality of resources identified by the deallocate vector.

10. The method of claim 1, wherein the plurality of resources comprises one or more elements of a reorder buffer, a load buffer, a store buffer, or a pick queue.

11. A processor, comprising:

a plurality of resources accessible to a plurality of threads executing on the processor; and

a select unit configured to;

allocate one of the plurality of resources on behalf of one of the plurality of threads;

update a data structure instantiated in a memory accessible to the processor to indicate that the one of the plurality of resources has been allocated to the one of the plurality of threads, wherein the data structure comprises a plurality of sequentially addressable elements;

deallocate the one of the plurality of resources after the resource has been released by the one of the plurality of threads; and

update the data structure to indicate that the one of the plurality of resources has been deallocated;

wherein at least one of said allocate or said deallocate updates an element of the data structure other than an element sequentially adjacent to an element updated in a most recent previous allocation or deallocation operation.

12. The processor of claim 11, wherein to update the data structure to indicate that the one of the plurality of resources has been allocated to the one of the plurality of threads, the select unit is configured to:

update a data structure element associated with the one of the plurality of resources such that the updated data structure element comprises a value indicating that the one of the plurality of resources has been allocated or store an identifier of the one of the plurality of threads in a data structure element associated with the one of the plurality of resources.

13. The processor of claim 11, wherein the select unit is further configured to:

search the data structure to determine a next resource available for allocation;

wherein a search result returns a value indicating a resource available for allocation; and

wherein to allocate one of the plurality of resources on behalf of one of the plurality of threads executing on the processor, the select unit is configured to allocate a resource indicated by the value returned by the search result.

14. The processor of claim 11, wherein the select unit is further configured to:

deallocate a plurality of resources allocated to the one of the plurality of threads in a single execution cycle;

wherein to update the data structure to indicate that the one of the plurality of resources has been deallocated, the select unit is configured to update a respective data structure element associated with each of the deallocated resources.

15. The processor of claim 14, wherein at least one of the respective data structure elements associated with the deallocated resources is not adjacent to any other ones of the respective data structure elements associated with the deallocated resources.

16. The processor of claim 11, wherein the select unit is further configured to:

access a deallocate vector identifying one or more of the plurality of resources for deallocation;

wherein to deallocate the one of the plurality of resources, the select unit is configured to deallocate at least one of the one or more of the plurality of resources identified by the deallocate vector.

17. A system, comprising:

a processor; and

a memory coupled to the processor;

wherein the processor comprises a select unit configured to;

allocate one of a plurality of resources on behalf of one of a plurality of threads;

update a data structure instantiated in the memory to indicate that the one of the plurality of resources has been allocated to the one of the plurality of threads, wherein the data structure comprises a plurality of sequentially addressable elements;

deallocate the one of the plurality of resources after the resource has been released by the one of the plurality of threads; and

update the data structure to indicate that the one of the plurality of resources has been deallocated;

wherein at least one of said allocate or said deallocate updates an element of the data structure other than an element sequentially adjacent to an element updated in a most recent previous allocation or deallocation operation.

18. The system of claim 17, wherein to update the data structure to indicate that the one of the plurality of resources has been allocated to the one of the plurality of threads, the select unit is configured to:

update a data structure element associated with the one of the plurality of resources such that the updated data structure element comprises a value indicating that the one of the plurality of resources has been allocated or store an identifier of the one of the plurality of threads in a data structure element associated with the one of the plurality of resources.

19. The system of claim 17, wherein the select unit is further configured to:

search the data structure to determine a next resource available for allocation;

wherein a search result returns a value indicating a resource available for allocation; and

wherein to allocate one of the plurality of resources on behalf of one of the plurality of threads executing on the processor, the select unit is configured to allocate a resource indicated by the value returned by the search result.

20. The system of claim 17, wherein the select unit is further configured to:

deallocate a plurality of resources allocated to the one of the plurality of threads in a single execution cycle;

wherein to update the data structure to indicate that the one of the plurality of resources has been deallocated, the select unit is configured to update a respective data structure element associated with each of the deallocated resources; and

wherein at least one of the respective data structure elements associated with the deallocated resources is not adjacent to any other ones of the respective data structure elements associated with the deallocated resources.