Read and write sets for ranges of instructions of transactions

• US 10,725,900 B2
• Filed: 06/29/2016
• Issued: 07/28/2020
• Est. Priority Date: 05/03/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gschwind, Michael K., Salapura, Valentina, Shum, Chung-Lung K.
• Primary Examiner(s): Li, Aimee
• Assistant Examiner(s): Alli, Kasim
• Application Number:
  US15/196,976
• Publication Number:
  US 20170322875A1
• Time in Patent Office: 1,490 Days
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/507 using speculative control
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

Transactional memory accesses are tracked using read and write sets based on actual program flow. A read and write set is associated with a range of instructions of a transaction. When execution follows a predicted branch, loads and stores are marked as being of selected read and write sets. Then, when a misprediction is processed, and execution is rewound, speculatively added read and write set indications are removed from the read and write sets.

Claims

1. A computer-implemented method of facilitating processing in a computing environment, said computer-implemented method comprising:

allocating a plurality of ranges of read and write sets assigned to instructions of a particular transaction, wherein a range of read and write sets for the particular transaction corresponds to one or more instructions of the particular transaction and includes multiple read and write sets for the one or more instructions, the multiple read and write sets of the range of read and write sets corresponding to multiple cache lines of a cache of the computing environment and used to track transactional memory accesses based on actual program flow, the transactional memory accesses including read accesses and write accesses of the particular transaction including non-speculative read accesses and write accesses;

determining that there is a mispredicted branch within the particular transaction; and

deallocating a subset of ranges of read and write sets of the plurality of ranges of read and write sets assigned to instructions of the particular transaction, based on determining the mispredicted branch, wherein at least one range of read and write sets assigned to one or more instructions of the particular transaction remains allocated,

wherein a cache line of the multiple cache lines comprises a plurality of pairs of read and write sets across multiple ranges of instructions of the particular transaction, and each pair of read and write sets of the plurality of pairs of read and write sets for the cache line is for a different range of instructions of the particular transaction, and wherein each different range of instructions includes instructions between a transaction begin instruction to begin the particular transaction and a branch instruction of the particular transaction or between one branch instruction of the particular transaction and another branch instruction of the particular transaction.

2. The computer-implemented method of claim 1, wherein the subset of ranges of read and write sets comprises one or more ranges of read and write sets allocated based on or after the mispredicted branch.

3. The computer-implemented method of claim 1, wherein the allocating for one range of read and write sets of the plurality of ranges of read and write sets comprises allocating the one range of read and write sets based on processing a selected branch instruction.

4. The computer-implemented method of claim 3, wherein the allocating the one range of read and write sets comprises assigning an identifier to the one range of read and write sets.

5. The computer-implemented method of claim 4, wherein the identifier comprises a branch tag, the branch tag being associated with the selected branch instruction.

6. The computer-implemented method of claim 1, wherein the plurality of ranges of read and write sets is implemented as a circular queue, and wherein deallocating a range of read and write sets of the subset of ranges of read and write sets comprises resetting a head pointer of the circular queue to point to one range of read and write sets associated with a branch instruction prior to the mispredicted branch.

7. The computer-implemented method of claim 1, further comprising:

detecting an interference associated with the particular transaction; and

processing the interference that is detected based on one or more ranges of read and write sets of the plurality of ranges of read and write sets.

8. The computer-implemented method of claim 7, wherein the processing the interference that is detected comprises:

determining whether the interference has been resolved by a branch misprediction flush, the branch misprediction flush deallocating at least one range of read and write sets of the subset of ranges of read and write sets; and

based on determining the interference has not been resolved by the branch misprediction flush, deferring handling of the interference.

9. The computer-implemented method of claim 8, wherein the processing the interference that is detected further comprises based on determining the interference has been resolved by the branch misprediction flush, continuing execution of one or more instructions of the particular transaction.

10. The computer-implemented method of claim 8, wherein the determining whether the interference has been resolved by the branch misprediction flush comprises checking active read and write sets for the particular transaction, the active read and write sets determined from the plurality of ranges of read and write sets.

11. The computer-implemented method of claim 1, wherein the one or more instructions of the particular transaction for which the range of read and write sets is allocated includes the one or more instructions between a transaction begin instruction to begin the particular transaction and a branch instruction of the particular transaction or between one branch instruction of the particular transaction and another branch instruction of the particular transaction.