System and method for out-of-order resource allocation and deallocation in a threaded machine

• US 9,690,625 B2
• Filed: 06/16/2009
• Issued: 06/27/2017
• Est. Priority Date: 06/16/2009
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Golla, Robert T.
• Primary Examiner(s): Lee, James J
• Application Number:
  US12/485,608
• Publication Number:
  US 20100318998A1
• Time in Patent Office: 2,933 Days
• Field of Search: 718104
• 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:

performing, by a computer processor core;

allocating two or more of a plurality of downstream resources of the computer processor core to one or more of a plurality of threads, wherein the plurality of downstream resources comprise two or more elements of a branch predictor structure, an instruction issue structure, a register mapping table, a translation lookaside buffer, a reorder buffer, a load buffer, a store buffer or a pick queue downstream from pre-execution instruction buffer within an instruction processing pipeline of the computer processor core and are dynamically shared between the plurality of threads, wherein allocating the two or more of the plurality of downstream resources of the computer processor core includes allocating each respective one of the two or more of the plurality of downstream resources of the computer processor core to a respective instruction of a respective thread of said one or more of the plurality of threads, said allocating comprising, for individual ones of the respective instructions;

examining contents of individual elements of a data structure in a sequential order of the data structure until a first element in the sequential order of the data structure is located that indicates a corresponding one of the downstream resources is available, wherein the examination is performed before the respective downstream resource for the respective instruction is requested;

updating the located element of the data structure to indicate that the respective downstream resource has been allocated to the respective instruction of the respective thread, wherein the data structure comprises a plurality of sequentially addressable elements, each element mapped to a respective downstream resource of the plurality of downstream resources for indicating allocation of the respective downstream resource, wherein the two or more updated elements corresponding to the two or more downstream resources are updated in an order; and

deallocating at least one of the plurality of downstream resources after the at least one downstream resource has been released for the respective instruction of the respective thread of said one or more of the plurality of threads, said deallocating comprising updating the data structure to indicate that the at least one of the plurality of downstream resources has been deallocated, wherein the deallocated downstream resource is available for allocation to an instruction of a different thread of the plurality threads;

wherein said deallocating updates at least one element of the data structure in a different order than the order for said allocating.

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 respective element of the data structure to indicate that the respective downstream resource has been allocated to the respective instruction comprises updating a data structure element associated with the one of the plurality of downstream resources such that the updated data structure element comprises a value indicating that the one of the plurality of downstream resources has been allocated.

4. The method of claim 1, wherein said updating the respective element of the data structure to indicate that the respective downstream resource has been allocated to the respective instruction 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 downstream resources.

5. The method of claim 1, further comprising:

performing, by the computer processor core;

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

wherein the value returned by the search result indicates the one of the plurality of downstream resources to be allocated to 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 the downstream 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 at least one of the plurality of downstream resources has been deallocated comprises updating a respective data structure element associated with each of the deallocated downstream resources.

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

9. The method of claim 1, further comprising:

performing, by the computer processor core;

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

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

10. A processor, comprising:

a plurality of downstream resources of the processor accessible to a plurality of threads executing on the processor, wherein the plurality of downstream resources comprise two or more elements of a branch predictor structure, an instruction issue structure, a register mapping table, a translation lookaside buffer, a reorder buffer, a load buffer, a store buffer or a pick queue downstream from pre-execution instruction buffer within an instruction processing pipeline of the processor and are dynamically shared between the plurality of threads; and

a select unit configured to;

allocate two or more of the plurality of downstream resources of the processor to a respective instruction of a respective thread of one or more of the plurality of threads, wherein to allocate two or more of the plurality of downstream resources the select unit is further configured to, for individual ones of the respective instructions;

examine contents of individual elements of a data structure in a sequential order of the data structure until a first element in the sequential order of the data structure is located that indicates a corresponding one of the downstream resources is available, wherein the examination is performed before the respective downstream resource for the respective instruction is requested;

update the located respective element of the data structure instantiated in a memory accessible to the processor to indicate that the respective downstream resource has been allocated to the respective instruction of the respective thread, wherein the data structure comprises a plurality of sequentially addressable elements, each element mapped to a respective downstream resource of the plurality of downstream resources for indicating allocation of the respective downstream resource, wherein two or more updated elements corresponding to the two or more allocated downstream resources are updated in an order; and

deallocate at least one of the plurality of downstream resources after the at least one downstream resource has been released for the respective instruction of the respective thread of said one or more of the plurality of threads, wherein to deallocate at least one of the plurality of downstream resources the select unit is further configured to;

update the data structure to indicate that the at least one of the plurality of downstream resources has been deallocated, wherein the deallocated downstream resource is available for allocation to an instruction of a different thread of the plurality threads;

wherein said deallocating updates at least one element of the data structure in a different order than the order for said allocating.

11. The processor of claim 10, wherein to update the data structure to indicate that the respective downstream resource has been allocated to the respective instruction, the select unit is configured to:

update a data structure element associated with the respective downstream resource such that the updated data structure element comprises a value indicating that the respective downstream resource has been allocated or store an identifier of the respective thread in a data structure element associated with the respective downstream resource.

12. The processor of claim 10, wherein the select unit is further configured to:

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

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

wherein to allocate two or more of the plurality of downstream resources to the respective instruction of one or more of the plurality of threads executing on the processor, the select unit is configured to allocate the particular downstream resource indicated by the value returned by the search result.

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

deallocate a plurality of downstream 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 at least one of the plurality of downstream resources has been deallocated, the select unit is configured to update a respective data structure element associated with each of the deallocated downstream resources.

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

15. The processor of claim 10, wherein the select unit is further configured to:

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

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

16. A system, comprising:

a processor; and

a memory coupled to the processor;

wherein the processor comprises a select unit configured to;

allocate two or more of a plurality of downstream resources of the processor to a respective instruction of a respective thread of one or more of a plurality of threads, wherein the plurality of downstream resources comprise two or more elements of a branch predictor structure, an instruction issue structure, a register mapping table, a translation lookaside buffer, a reorder buffer, a load buffer, a store buffer or a pick queue downstream from pre-execution instruction buffer within an instruction processing pipeline of the processor and are dynamically shared between the plurality of threads, said allocating comprising, for individual ones of the respective instructions;

examining contents of individual elements of a data structure in a sequential order of the data structure until a first element in the sequential order of the data structure is located that indicates a corresponding one of the downstream resources is available, wherein the examination is performed before the respective downstream resource for the respective instruction is requested;

updating the located element of the data structure instantiated in the memory to indicate that the respective downstream resource has been allocated to the respective instruction of the respective thread, wherein the data structure comprises a plurality of sequentially addressable elements, each element mapped to a respective downstream resource of the plurality of downstream resources for indicating allocation of the respective downstream resource, wherein the two or more updated elements corresponding to the two or more downstream resources are updated in an order; and

deallocate at least one of the plurality of downstream resources after the at least one downstream resource has been released for the respective instruction of the respective thread of said one or more of the plurality of threads; and

update the data structure to indicate that the at least one of the plurality of downstream resources has been deallocated, wherein the deallocated downstream resource is available for allocation to an instruction of a different thread of the plurality threads;

wherein said deallocating updates at least one element of the data structure in a different order than the order for said allocating.

17. The system of claim 16, wherein to update the data structure to indicate that the respective downstream resource has been allocated to the respective thread, the select unit is configured to:

update a data structure element associated with the respective downstream resource such that the updated data structure element comprises a value indicating that the respective downstream resource has been allocated or store an identifier of the respective thread in a data structure element associated with the respective downstream resource.

18. The system of claim 16, wherein the select unit is further configured to:

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

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

wherein to allocate two or more of the plurality of downstream resources to the respective instruction, the select unit is configured to allocate the particular downstream resource indicated by the value returned by the search result.

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

deallocate a plurality of downstream 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 at least one of the plurality of downstream resources has been deallocated, the select unit is configured to update a respective data structure element associated with each of the deallocated downstream resources; and

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