Cache metadata for accelerating software transactional memory

• US 8,898,652 B2
• Filed: 06/08/2007
• Issued: 11/25/2014
• Est. Priority Date: 03/23/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gray, Jan, Harris, Timothy L., Larus, James, Smith, Burton
• Primary Examiner(s): MITCHELL, JASON D
• Application Number:
  US11/811,033
• Publication Number:
  US 20070245128A1
• Time in Patent Office: 2,727 Days
• Field of Search: None
• US Class Current: 717/149
• CPC Class Codes: G06F 9/30003 Arrangements for executing specific machine instructions
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

Various technologies and techniques are disclosed for providing a hardware accelerated software transactional memory application. The software transactional memory application has access to metadata in a cache of a central processing unit that can be used to improve the operation of the STM system. For example, open read barrier filtering is provided that uses an opened-for-read bit that is contained in the metadata to avoid redundant open read processing. Similarly, redundant read log validation can be avoided using the metadata. For example, upon entering commit processing for a particular transaction, a get-evictions instruction in an instruction set architecture of the central processing unit is invoked. A retry operation can be optimized using the metadata. The particular transaction is aborted at a current point and put to sleep. The corresponding cache line metadata in the metadata are marked appropriately to efficiently detect a write by another CPU.

Claims

1. A computer-readable medium storing computer-executable instructions for causing a computer to perform operations comprising:

providing a hardware accelerated software transactional memory application that has access to metadata in a central processing unit (CPU) cache;

determining that a retry operation should be used for a particular transaction of a processor;

aborting the particular transaction at a current point, the aborting comprising rolling back updates in the particular transaction;

putting the particular transaction to sleep in response to aborting the particular transaction by executing a pause instruction to enter a low power state;

after the particular transaction is aborted, marking cache line metadata in the metadata corresponding to watched cache lines in the aborted particular transaction;

waking up the particular transaction in response to another transaction evicting a marked cache line corresponding to the watched cache lines in the aborted transaction; and

retrying the particular transaction.

2. The computer-readable medium of claim 1, wherein the particular transaction sleeps by establishing an eviction handler and where the particular transaction marks the cache line metadata such that eviction will cause a control flow transfer to the eviction handler.

3. The computer-readable medium of claim 1, the operations further comprising:

providing a hardware acceleration mechanism to filter redundant execution of an operation used by the hardware accelerated software transactional memory application; and

providing write undo barrier filtering that uses a logged-for-undo bit that is contained in the metadata in the CPU cache, the write undo barrier filtering comprising;

starting a write field sequence for a data field to be overwritten; and

skipping a write undo logging sequence if the logged-for-undo bit contained in the metadata is set for a virtual address of the data field to be overwritten.

4. The computer-readable medium of claim 3, wherein the hardware accelerated software transactional memory application uses an opened-for-read bit wherein a first execution of an open-for-read operation enables a subsequent execution of an open-for-read operation to be filtered out as redundant.

5. The computer-readable medium of claim 3, wherein the write undo barrier filtering is operable to use the logged-for-undo bit to determine whether redundant logging can be avoided.

6. The computer-readable medium of claim 5, wherein if the logged-for-undo bit is not set for the particular virtual address, set the logged for undo bit to true.

7. The computer-readable medium of claim 6, wherein if the logged-for-undo bit is not set for the particular virtual address, also log data associated with the logged-for-undo bit.

8. The computer-readable medium of claim 3, wherein a first execution of an operation makes a subsequent execution of an operation redundant.

9. The computer-readable medium of claim 8, the operations further comprising:

accessing a metadata bit to determine whether or not an earlier execution of an operation may have been performed;

if the metadata bit is set, then avoiding a redundant operation;

if the metadata bit is not set, then executing the operation; and

if the operation makes a subsequent operation redundant, then setting the metadata bit to reflect this.

10. The computer-readable medium of claim 9, wherein the metadata bit is a cache metadata bit associated with an address on which an operation is being attempted.

11. The computer-readable medium of claim 1, wherein the CPU cache is associated with multiple logical processors.

19. The computer system of claim 1, wherein the software transactional memory application uses an opened-for-read bit wherein a first execution of an open-for-read operation enables a subsequent execution of an open-for-read operation to be filtered out as redundant.

12. A method for performing a retry operation using a hardware accelerated software transactional memory application comprising the operations of:

providing the hardware accelerated software transactional memory application that has access to metadata in a cache of a central processing unit;

determining that the retry operation should be used for a particular transaction of a processor;

aborting the particular transaction at a current point, the aborting comprising rolling back updates in the particular transaction;

putting the particular transaction to sleep in response to aborting the particular transaction by executing a pause instruction to enter a low power state;

after the particular transaction is aborted, marking cache line metadata in the metadata corresponding to watched cache lines in the aborted particular transaction;

waking up the particular transaction in response to another transaction evicting a marked cache line corresponding to the watched cache lines in the aborted transaction; and

retrying the particular transaction.

13. The method of claim 12, further comprising:

waiting until another processor changes something the particular transaction had read.

14. The method of claim 13, wherein the particular transaction sleeps by establishing an eviction handler and where the particular transaction marks the cache line metadata such that eviction will cause a control flow transfer to the eviction handler.

15. A computer system comprising:

a central processing unit (CPU) including a plurality of logical processors;

a CPU cache including;

a plurality of cache lines, and

cache line metadata corresponding to each cache line; and

a computer-readable medium storing computer-executable instructions for causing the CPU to perform operations comprising;

providing a hardware accelerated software transactional memory application that has access to the cache line metadata;

determining that a retry operation should be used for a particular transaction of the CPU;

aborting the particular transaction at a current point, the aborting comprising rolling back updates in the particular transaction;

putting the particular transaction to sleep in response to aborting the particular transaction by executing a pause instruction to enter a low power state;

after the particular transaction is aborted, marking cache line metadata in the metadata corresponding to watched cache lines in the aborted particular transaction;

waking up the particular transaction in response to another transaction evicting a marked cache line corresponding to the watched cache lines in the aborted transaction; and

retrying the particular transaction.

16. The computer system of claim 15, wherein the particular transaction sleeps by establishing an eviction handler and where the particular transaction marks the cache line metadata such that eviction will cause a control flow transfer to the eviction handler.

17. The computer system of claim 15, the operations further comprising:

providing a hardware acceleration mechanism to filter redundant execution of an operation used by the hardware accelerated software transactional memory application; and

providing write undo barrier filtering that uses a logged-for-undo bit that is contained in the cache line metadata, the write undo barrier filtering comprising;

starting a write field sequence for a data field to be overwritten; and

skipping a write undo logging sequence if the logged-for-undo bit contained in the cache line metadata is set for an address of the data field to be overwritten.

18. The computer system of claim 17, the operations further comprising:

accessing a metadata bit to determine whether or not an earlier execution of an operation may have been performed;

if the metadata bit is set, then avoiding a redundant operation;

if the metadata bit is not set, then executing the operation; and

if the operation makes a subsequent operation redundant, then setting the metadata bit to reflect that the subsequent operation is redundant.