DYNAMICALLY ALLOCATED STORE QUEUE FOR A MULTITHREADED PROCESSOR

• US 20100299508A1
• Filed: 05/21/2009
• Published: 11/25/2010
• Est. Priority Date: 05/21/2009
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Luttrell, Mark A.
• Granted Patent: US 8,006,075 B2
• Time in Patent Office: Days
• US Class Current: 712/234
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

Systems and methods for storage of writes to memory corresponding to multiple threads. A processor comprises a store queue, wherein the queue dynamically allocates a current entry for a committed store instruction in which entries of the array may be allocated out of program order. For a given thread, the store queue conveys store data to a memory in program order. The queue is further configured to identify an entry of the plurality of entries that corresponds to an oldest committed store instruction for a given thread and determine a next entry of the array that corresponds to a next committed store instruction in program order following the oldest committed store instruction of the given thread, wherein said next entry includes data identifying the entry. The queue marks an entry as unfilled upon successful conveying of store data to the memory.

Claims

1. A store queue comprising:

an array comprising a plurality of entries, wherein each entry is configured to store data for a committed store instruction, and wherein the array is configured to;

dynamically allocate an entry of the array out of program order; and

convey store data of each entry of the plurality of entries in program order;

circuitry configured to;

identify a first entry of the entries that corresponds to an oldest committed store instruction for a given thread; and

determine a next entry of the array that corresponds to a next committed store instruction in program order following the oldest committed store instruction of the given thread, wherein said next entry includes data identifying the first entry.

2. The store queue as recited in claim 1, wherein said data identifying the first entry comprises a link value, and wherein to determine said next entry, the circuitry is configured to compare an identifier of the first entry with a link value stored in one or more of the plurality of entries.

3. The store queue as recited in claim 2, wherein the identifier of the first entry is an array entry number.

4. The store queue as recited in claim 2, wherein in response to allocation of a given entry of the array for a first store instruction that follows in program order a second store instruction of the given thread previously allocated in a prior entry, the circuitry is configured to store an identification of the prior entry in the given entry.

5. The store queue as recited in claim 4, wherein in response to allocation of the given entry, the circuitry is further configured to update a first pointer value that identifies the prior entry with an identification of the given entry.

6. The store queue as recited in claim 2, wherein in response to determining no entry of the plurality of entries comprises a value that identifies the first entry, the circuitry is configured to update a second pointer value that identifies the first entry with a second value that indicates the given thread does not have any other allocated entries in the array.

7. The store queue as recited in claim 5, wherein the first pointer value corresponds to the given thread.

8. The store queue as recited in claim 6, wherein the array is further configured to store, for a committed store instruction, at least one or more of the following:

a thread identifier (TID), a valid bit, and an address.

9. A method comprising:

storing data for a committed store instruction in an array comprising a plurality of entries;

dynamically allocating an entry of the array out of program order; and

conveying store data of each entry of the plurality of entries in program order;

identifying a first entry of the plurality of entries that corresponds to an oldest committed store instruction for a given thread; and

determining a next entry of the array that corresponds to a next committed store instruction in program order following the oldest committed store instruction of the given thread, wherein said next entry includes data identifying the first entry.

10. The method as recited in claim 9, wherein said data identifying the first entry comprises a link value, and wherein determining said next entry comprises comparing an identifier of the first entry with a link value stored in each entry of the plurality of entries.

11. The method as recited in claim 10, wherein the identifier of the first entry is an array entry number.

12. The method as recited in claim 10, wherein in response to allocation of a given entry of the array for a first store instruction that follows in program order a second store instruction of the given thread previously allocated in a prior entry, the method further comprises storing an identification of the prior entry in the given entry.

13. The method as recited in claim 12, wherein in response to allocation of the given entry, the method further comprises updating a first pointer value that identifies the prior entry with an identification of the given entry.

14. The method as recited in claim 10, wherein in response to determining no entry of the plurality of entries comprises a value that identifies the first entry, the method further comprises updating a second pointer value that identifies the first entry with a second value that indicates the given thread does not have any other allocated entries in the array.

15. The method as recited in claim 14, wherein the first pointer value corresponds to the given thread.

16. The method as recited in claim 14, further comprising storing, for a committed store instruction, at least one or more of the following:

a thread identifier (TID), a valid bit, and an address.

17. A computer readable storage medium storing program instructions operable to efficiently store pending writes to memory corresponding to multiple threads, wherein the program instructions are executable to:

store data for a committed store instruction in an array comprising a plurality of entries;

dynamically allocate an entry of the array for a committed store instruction, wherein entries of the array may be allocated out of program order; and

convey store data of committed store instructions of each entry of the plurality of entries in program order;

identify a first entry of the plurality of entries that corresponds to an oldest committed store instruction for a given thread; and

determine a next entry of the array that corresponds to a next committed store instruction in program order following the oldest committed store instruction of the given thread, wherein said next entry includes data identifying the first entry.

18. The storage medium as recited in claim 17, wherein said data identifying the first entry comprises a link value, and wherein determining said next entry comprises comparing an identifier of the first entry with a link value stored in one or more of the plurality of entries.

19. The storage medium as recited in claim 18, wherein in response to allocation of a given entry of the array for a first store instruction that follows in program order a second store instruction of the given thread previously allocated in a prior entry, the program instructions are executable to store an identification of the prior entry in the given entry.

20. The storage medium as recited in claim 19, wherein in response to allocation of the given entry, the program instructions are executable to update a first pointer value that identifies the prior entry with an identification of the given entry.