Load/store ordering in a threaded out-of-order processor
Systems and methods for efficient load-store ordering. A processor comprises a store buffer that includes an array. The store buffer dynamically allocates any entry of the array for an out-of-order (o-o-o) issued store instruction independent of a corresponding thread. Circuitry within the store buffer determines a first set of entries of the array entries that have store instructions older in program order than a particular load instruction, wherein the store instructions have a same thread identifier and address as the load instruction. From the first set, the logic locates a single final match entry of the first set corresponding to the youngest store instruction of the first set, which may be used for read-after-write (RAW) hazard detection.
1. A store buffer comprising:
an array configured to dynamically allocate an entry of a plurality of entries for an issued store instruction, wherein each entry of said entries is configured to store a thread identifier (TID), an address, and age information relative to other issued store instructions; and
circuitry configured to:
determine a first set of entries of the plurality of entries that have store instructions older in program order than a load instruction, wherein the store instructions have a same TID and address as the load instruction; and
identify an entry of the first set of entries that corresponds to a youngest store instruction of the first set.
2. The store buffer as recited in claim 1 , wherein the age information stored in a given entry of the plurality of entries comprises an age vector, wherein the age vector comprises a plurality of bits including a bit for each entry of the plurality of entries, wherein each bit of the bits indicates whether the given entry is associated with a store instruction that is older in program order than store instructions associated with other entries of the plurality of entries.
3. The store buffer as recited in claim 2 , wherein the circuitry is further configured to interpret a value of an identity bit position of an age vector of the given entry as a different binary value depending on a current operation being performed, wherein the identity bit is a bit position corresponding to a position of the given entry within the plurality of entries.
4. The store buffer as recited in claim 3 , wherein the circuitry is further configured to decode into a one-hot bit vector an identifier associated with said load instruction, wherein the identifier indicates an entry of the plurality of entries storing a most recent store instruction to issue prior to said load instruction in program order.
5. The store buffer as recited in claim 4 , wherein for each entry of the plurality of entries, the circuitry is further configured to:
interpret the identity bit as a value that indicates whether a store instruction corresponding to another entry of the entries is younger; and
perform a first AND-OR reduction with said age vector and said one-hot vector to generate a pre-qualified older match bit.
6. The store buffer as recited in claim 5 , wherein for each entry of the plurality of entries the circuitry is further configured to generate a set qualified older match bit, responsive to determining a corresponding pre-qualified older match bit is set, a valid bit stored in the entry indicates a valid entry, and the entry has a same TID and address as the load instruction, wherein a first set is a bit vector comprising the plurality of qualified older match bit values.
7. The processor as recited in claim 6 , wherein for each entry of the plurality of entries the circuitry is further configured to:
interpret the identity bit as a value that indicates whether a store instruction corresponding to another entry is older; and
perform a second AND-OR reduction with said age vector corresponding to an entry and said first set to generate a kill bit value, wherein said second set is a bit vector comprising the plurality of kill bit values.
8. The processor as recited in claim 7 , wherein the circuitry is further configured to perform a binary AND operation on a bit-by-bit basis with said first set and an inverted said second set to generate a final match vector, wherein the final match vector has a single set bit corresponding to an entry having the youngest store instruction of said first set.
9. A method comprising:
dynamically allocating an entry of a plurality of entries of an array, said plurality of entries being configured to store information associated with an issued store instruction;
storing in an entry of the array a thread identifier (TID), an address, and age information relative to other issued store instructions;
determining a first set of entries of the plurality of entries that have store instructions older in program order than a load instruction, wherein the store instructions have a same TID and address as the load instruction; and
identifying an entry of the first set of entries that corresponds to a youngest store instruction of the first set.
10. The method as recited in claim 9 , wherein the age information stored in a given entry of the plurality of entries comprises an age vector, wherein the age vector comprises a plurality of bits including a bit for each entry of the plurality of entries, wherein each bit of the bits indicates whether the given entry is associated with a store instruction that is older in program order than store instructions associated with other entries of the plurality of entries.
11. The method as recited in claim 10 , further comprising interpreting a value of an identity bit position of an age vector of the given entry as a different binary value depending on a current operation being performed, wherein the identity bit is a bit position corresponding to a position of the given entry within the plurality of entries.
12. The method as recited in claim 11 , further comprising decoding into a one-hot bit vector an identifier associated with said load instruction, wherein the identifier indicates an entry of the plurality of entries storing a most recent store instruction to issue prior to said load instruction in program order.
13. The method as recited in claim 12 , further comprising for each entry of the plurality of entries:
interpreting the identity bit as a value that indicates whether a store instruction corresponding to another entry of the entries is younger; and
performing a first AND-OR reduction with said age vector and said one-hot vector to generate a pre-qualified older match bit.
14. The method as recited in claim 13 , further comprising, for each entry of the plurality of entries, generating a set qualified older match bit, responsive to determining a corresponding pre-qualified older match bit is set, a valid bit stored in the entry indicates a valid entry, and the entry has a same TID and address as the load instruction, wherein a first set is a bit vector comprising the plurality of qualified older match bit values.
15. The method as recited in claim 14 , further comprising for each entry of the plurality of entries:
interpreting the identity bit as a value that indicates whether a store instruction corresponding to another entry is older; and
performing a second AND-OR reduction with said age vector corresponding to an entry and said first set to generate a kill bit value, wherein said second set is a bit vector comprising the plurality of kill bit values.
16. The method as recited in claim 15 , further comprising performing a binary AND operation on a bit-by-bit basis with said first set and an inverted said second set to generate a final match vector, wherein the final match vector has a single set bit corresponding to an entry having the youngest store instruction of said first set.
17. A computer readable storage medium storing program instructions operable to perform load-store ordering, wherein the program instructions are executable to:
dynamically allocate an entry of a plurality of entries of an array, said plurality of entries being configured to store information associated with an issued store instruction;
store in an entry of the array a thread identifier (TID), an address, and age information relative to other issued store instructions;
determine a first set of entries of the plurality of entries that have store instructions older in program order than a load instruction, wherein the store instructions have a same TID and address as the load instruction; and
identify an entry of the first set of entries that corresponds to a youngest store instruction of the first set.
18. The storage medium as recited in claim 17 , wherein the age information stored in a given entry of the plurality of entries comprises an age vector, wherein the age vector comprises a plurality of bits including a bit for each entry of the plurality of entries, wherein each bit of the bits indicates whether the given entry is associated with a store instruction that is older in program order than store instructions associated with other entries of the plurality of entries.
19. The storage medium as recited in claim 18 , wherein the instructions are further executable to interpret a value of an identity bit position of an age vector of the given entry as a different binary value depending on a current operation being performed, wherein the identity bit is a bit position corresponding to a position of the given entry within the plurality of entries.
20. The storage medium as recited in claim 19 , wherein the program instructions are further executable to decode into a one-hot bit vector an identifier associated with said load instruction, wherein the identifier indicates an entry of the plurality of entries storing a last store instruction to issue prior to said load instruction in program order.