Efficient and consistent software transactional memory

• US 9,519,467 B2
• Filed: 09/27/2011
• Issued: 12/13/2016
• Est. Priority Date: 12/28/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wang, Cheng, Wu, Youfeng, Chen, Wei-Yu, Saha, Bratin, Adl-Tabatabai, Ali Reza
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): MINCEY, JERMAINE A
• Application Number:
  US13/246,678
• Publication Number:
  US 20120016853A1
• Time in Patent Office: 1,904 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/458 Synchronisation, e.g. post-wait, barriers, locks synchronisation among tasks G06F9/52
• 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/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/38585 with result invalidation, e.g. nullification
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

A method and apparatus for efficient and consistent validation/conflict detection in a Software Transactional Memory (STM) system is herein described. A version check barrier is inserted after a load to compare versions of loaded values before and after the load. In addition, a global timestamp (GTS) is utilized to track a latest committed transaction. Each transaction is associated with a local timestamp (LTS) initialized to the GTS value at the start of a transaction. As a transaction commits it updates the GTS to a new value and sets versions of modified locations to the new value. Pending transactions compare versions determined in read barriers to their LTS. If the version is greater than their LTS indicating another transaction has committed after the pending transaction started and initialized the LTS, then the pending transaction validates its read set to maintain efficient and consistent transactional execution.

Claims

1. One or more tangible machine readable storage medium storing code, which when executed, causes the machine to perform the operations of:

maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions;

starting a new transaction, wherein starting the new transaction comprises copying the global most recent transaction timestamp to a first local timestamp of the new transaction;

in response to executing a current read in the new transaction, comparing a version number of a metadata location associated with the current read to the first local timestamp to determine whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read, wherein the global most recent transaction timestamp being updated is indicative of a transaction of the plurality of transactions having committed between starting the new transaction and executing the current read;

executing one or more prior reads in the new transaction between starting the new transaction and executing the current read, wherein executing the one or more prior reads comprises adding a version number of a metadata location associated with each of the prior reads to a current read set of the new transaction;

determining whether the current read set for the new transaction including the one or more prior reads executed between starting the new transaction and the current read is valid in response to determining that the global most recent transaction timestamp has been updated, wherein determining whether the current read set is valid comprises comparing each of the one or more version numbers of the current read set to a version number of the metadata location associated with the corresponding prior read;

continuing execution of the new transaction in response to determining that the global most recent transaction timestamp has not been updated;

continuing execution of the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is valid, wherein continuing execution of the new transaction comprises performing the current read; and

aborting the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is not valid, wherein aborting the new transaction comprises reversing changes to memory made by the new transaction.

2. The one or more tangible machine readable storage medium of claim 1, wherein in response to executing the current read in the new transaction, determining whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read comprises:

determining that the global most recent transaction timestamp has been updated in response to the comparing indicating the version number of the metadata location associated with the current read is different than the first local timestamp.

3. The one or more tangible machine readable storage medium of claim 1, wherein maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions comprises:

incrementing the global most recent transaction timestamp in response to a commit of any transaction of the plurality of transactions.

4. A method comprising:

maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions;

starting a new transaction, wherein starting the new transaction comprises copying the global most recent transaction timestamp to a first local timestamp of the new transaction;

executing one or more prior reads in the new transaction in response to starting the new transaction, wherein executing the one or more prior reads comprises adding a version number of a metadata location associated with each of the prior reads to a current read set of the new transaction;

executing a current read in the new transaction in response to executing the one or more prior reads;

in response to executing the current read in the new transaction, comparing a version number of a metadata location associated with the current read to the first local timestamp to determine whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read, wherein the global most recent transaction timestamp being updated is indicative of a transaction of the plurality of transactions having committed between starting the new transaction and executing the current read;

determining whether the current read set for the new transaction including the one or more prior reads executed between starting the new transaction and the current read is valid in response to determining that the global most recent transaction timestamp has been updated, wherein determining whether the current read set is valid comprises comparing each of the one or more version numbers of the current read set to a version number of the metadata location associated with the corresponding prior read;

continuing execution of the new transaction in response to determining that the global most recent transaction timestamp has not been updated;

continuing execution of the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is valid, wherein continuing execution of the new transaction comprises performing the current read; and

aborting the new transaction in response to determining the current read set including the one or more prior reads executed from starting the new transaction to the current read is not valid, wherein aborting the new transaction comprises reversing changes to memory made by the new transaction.

5. The method of claim 4, wherein in response to executing the current read in the new transaction, determining whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read comprises:

determining that the global most recent transaction timestamp has been updated in response to the comparing indicating the version number of the metadata location associated with the current read is different than the first local timestamp.

6. The method of claim 4, wherein maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions comprises:

incrementing the global most recent transaction timestamp in response to a commit of any transaction of the plurality of transactions.

7. A system comprising:

a processor adapted to execute code; and

a memory to hold the code, the code, when executed by the processor, adapted to perform the operations of;

maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions;

starting a new transaction, wherein starting the new transaction comprises copying the global most recent transaction timestamp to a first local timestamp of the new transaction;

in response to executing a current read in the new transaction, comparing a version number of a metadata location associated with the current read to the first local timestamp to determine whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read, wherein the global most recent transaction timestamp being updated is indicative of a transaction of the plurality of transactions having committed between starting the new transaction and executing the current read;

executing one or more prior reads in the new transaction between starting the new transaction and executing the current read, wherein executing the one or more prior reads comprises adding a version number of a metadata location associated with each of the prior reads to a current read set of the new transaction;

determining whether the current read set for the new transaction including the one or more prior reads executed between starting the new transaction and the current read is valid in response to determining that the global most recent transaction timestamp has been updated, wherein determining whether the current read set is valid comprises comparing each of the one or more version numbers of the current read set to a version number of the metadata location associated with the corresponding prior read;

continuing execution of the new transaction in response to determining that the global most recent transaction timestamp has not been updated;

continuing execution of the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is valid, wherein continuing execution of the new transaction comprises performing the current read; and

aborting the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is not valid, wherein aborting the new transaction comprises reversing changes to memory made by the new transaction.

8. The system of claim 7, wherein in response to executing the current read in the new transaction, determining whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read comprises:

determining that the global most recent transaction timestamp has been updated in response to the comparing indicating the version number of the metadata location associated with the current read is different than the first local timestamp.

9. The system of claim 7, wherein maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions comprises:

incrementing the global most recent transaction timestamp in response to a commit of any transaction of the plurality of transactions.

10. One or more tangible machine readable storage medium storing compiler code, which when executed, causes the machine to perform the operations of:

detecting a new transaction in program code and inserting code, which when executed, causes a machine to perform the operations of;

maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions;

starting a new transaction, wherein starting the new transaction comprises copying the global most recent transaction timestamp to a first local timestamp of the new transaction;

in response to executing a current read in the new transaction, comparing a version number of a metadata location associated with the current read to the first local timestamp to determine whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read, wherein the global most recent transaction timestamp being updated is indicative of a transaction of the plurality of transactions having committed between starting the new transaction and executing the current read;

executing one or more prior reads in the new transaction between starting the new transaction and executing the current read, wherein executing the one or more prior reads comprises adding a version number of a metadata location associated with each of the prior reads to a current read set of the new transaction;

determining whether the current read set for the new transaction including the one or more prior reads executed between starting the new transaction and the current read is valid in response to determining that the global most recent transaction timestamp has been updated, wherein determining whether the current read set is valid comprises comparing each of the one or more version numbers of the current read set to a version number of the metadata location associated with the corresponding prior read;

continuing execution of the new transaction in response to determining that the global most recent transaction timestamp has not been updated;

continuing execution of the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is valid, wherein continuing execution of the new transaction comprises performing the current read; and

aborting the new transaction in response to determining that the current read set including the one or more prior reads executed from starting the new transaction to the current read is not valid, wherein aborting the new transaction comprises reversing changes to memory made by the new transaction.

11. The one or more tangible machine readable storage medium of claim 10, wherein in response to executing the current read in the new transaction, determining whether the global most recent transaction timestamp has been updated between starting the new transaction and executing the current read comprises:

determining that the version number of the metadata location associated with the current read has been updated in response to the comparing indicating the global most recent transaction timestamp is different than the first local timestamp.

12. The one or more tangible machine readable storage medium of claim 10, wherein maintaining a global most recent transaction timestamp to be updated in response to a commit of any transaction of a plurality of transactions comprises:

incrementing the global most recent transaction timestamp in response to a commit of any transaction of the plurality of transactions.