Efficient and consistent software transactional memory

• US 8,060,482 B2
• Filed: 12/28/2006
• Issued: 11/15/2011
• Est. Priority Date: 12/28/2006
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chen, Wei-Yu, Wu, Youfeng, Saha, Bratin, Wang, Cheng, Adl-Tabatabai, Ali-Reza
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): MINCEY, JERMAINE A
• Application Number:
  US11/648,012
• Publication Number:
  US 20080163220A1
• Time in Patent Office: 1,783 Days
• Field of Search: 707/203
• US Class Current: 707/703
• 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. A method comprising:

storing a global transaction value, which is to represent a most recent committed transaction, in a first local transaction value associated with a first transaction, in response to starting execution of the first transaction;

maintaining a current version value for a data address in a meta-data location associated with the data address, the current version value being based on the global transaction value that is associated with a most recent transaction to update the data address;

in response to encountering a current read operation, which is included in the first transaction and references the data address,

reading the current version value from the meta-data location associated with the data address,

checking if the current version value indicates the data address is unlocked, and

validating a plurality of previous read operations from the first transaction responsive to the current version value from the meta-data location associated with the data address being greater than the local transaction value to indicate a more recent transaction than the first transaction has updated the data address;

performing the current read operation;

after performing the current read operation,

loading a subsequent version value from the meta-data location associated with the data address, and

aborting the first transaction in response to the subsequent version value from the meta-data location being different from the logged version value;

in response to encountering a write operation referencing the data address, acquiring a lock in the meta-data location associated with the data address; and

attempting to commit the transaction in response in response to encountering an end of the transaction.

2. The method of claim 1, wherein in response to encountering the current read operation further logging the current version value as a logged version value in response to the first address being unlocked.

3. The method of claim 1, wherein attempting to commit the first transaction comprises:

validating each read operation in the first transaction including the plurality of previous read operations and the current read operation, in response to the first local transaction value being less than the global transaction value;

incrementing the global transaction value to an incremented global transaction value to represent the first transaction is the most recent committed transaction; and

updating the meta-data location to at least the incremented global timestamp value to indicate the first transaction is the most recent transaction to have updated the meta-data location.

4. The method of claim 1, wherein validating a plurality of previous read operations in the first transaction comprises:

determining the plurality of previous read operations are valid in response to a plurality of logged versions associated with the plurality of previous read operations correspond to a plurality of current versions associated with the plurality of previous read operations.

5. A tangible storage medium including program code which, when executed by a machine, causes the machine to perform the operations of:

copying a global timestamp that represents a most recent committed transaction to a local timestamp for a transaction;

determining a current version from a meta-data location associated with an address referenced by a load operation in the transaction before the load operation is performed, wherein the transaction comprises a plurality of grouped operations, and wherein updates from the plurality of grouped operations are not made globally visible outside of the transaction until the transaction is committed;

logging the current version as a logged version;

determining if the current version is greater than the local timestamp;

validating a plurality of previous reads in the transaction in response to determining if the current version is greater than the local timestamp;

after performing the load operation and before an attempted commit of the transaction;

determining a subsequent version from the meta-data location associated with the address, and

aborting the transaction in response to the subsequent version being different from the logged version indicating a transaction wrote to the address since determining the current version from the meta-data location.

6. The tangible storage medium of claim 5, wherein the program code includes:

a read barrier function, when executed, to cause the machine to perform the operations of determining the current version and logging the current version;

a version check barrier function, when executed, to cause the machine to perform the operations of determining the subsequent version; and

an abort function, when executed, to cause the machine to perform the operations of aborting the transaction.

7. The tangible storage medium of claim 6, wherein the version check barrier function includes:

a first version check barrier operation, when executed, to cause the machine to perform the operations of determining the subsequent version;

a second version check barrier operation, when executed, to cause the machine to perform the operations of determining if the subsequent version is different from the logged version; and

a call to the abort function, when executed, in response to the subsequent version being different from the logged version, to cause the machine to perform the operations of aborting the transaction.

8. The tangible storage medium of claim 5, wherein the program code further comprises:

a main section including the transaction, a call to the read barrier function before the load operation in the transaction, the load operation in the transaction, a call to the version check barrier function after the load operation in the transaction.

9. The tangible storage medium of claim 8, wherein the read barrier function includes:

a first read barrier operation, when executed, to cause the machine to perform the operations of determining the current version;

a second read barrier operation, when executed, to cause the machine to perform the operations of determining if the current version is greater than the local timestamp; and

validation operations, when executed in response to the current version being greater than the local timestamp, to cause the machine to perform the operations of validating a plurality of previous reads in the transaction.

10. The tangible storage medium of claim 9, wherein the read barrier function further includes:

a third read barrier operation, when executed in response to the current version being greater than the local timestamp, to cause the machine to perform the operations of copying the global timestamp to the local timestamp; and

a fourth read barrier operation, when executed, to cause the machine to perform the operations of logging the current version in a read log as the logged version.

11. The tangible storage medium of claim 8, wherein the program code further comprises:

a commit function including

a first commit operation, when executed, to determine if the local timestamp is less than the global timestamp; and

validation operations, when executed in response to the current version being greater than the local timestamp, to validate a plurality of previous reads in the transaction.

12. The tangible storage medium of claim 11, wherein the commit function further includes:

a second commit operation, when executed, to cause the machine to perform the operations of incrementing the global timestamp to an incremented global timestamp;

a third commit operation, when executed, to cause the machine to perform the operations of setting a most recent version associated with the address to the incremented global timestamp in response to a lock being acquired for the address during execution of the transaction.

13. A system comprising:

a device to hold program code; and

a processor associated with the memory device, wherein the program code, when executed by the processor, is to cause the processor to perform the operations of;

loading a global timestamp into a local timestamp associated with the first transaction, wherein the global timestamp is to be based on a most recent local timestamp value of a most recent committed transaction;

determining if a first version held in a version location associated with an address referenced by a load operation within the first transaction is greater than the local timestamp before performing the load operation;

aborting the first transaction in response to determining a previous read in the first transaction is not valid responsive to determining the first version is greater than the local timestamp;

determining a second version held in the version location associated with the address after performing the load operation; and

aborting the first transaction in response to determining the second version is different from the first version.

14. The system of claim 13, wherein the program code comprises:

a read barrier function, when executed, to cause the processor to perform the operations of determining if a first version is greater than the local timestamp and calling an abort function;

a version check function, when executed, to cause the processor to perform the operations of determining the second version; and

an abort function, when executed, to cause the processor to perform the operations of aborting the first transaction.

15. The system of claim 14, wherein the program code, when executed, is further to cause the processor to perform the operations of responsive to the first version being greater than the local timestamp, further:

reloading the global timestamp into the local timestamp; and

logging the first version before performing the load operation.

16. The system of claim 15, wherein the version location includes a metadata location referenced by a hash value of the address.

17. The system of claim 14, wherein the program code further includes a write barrier function, when executed, is to cause the processor to perform the operations of acquiring a lock with the metadata location for the address before performing a write operation to the address.

18. The system of claim 14, wherein the program code further includes a commit function, when executed, is to cause the processor to perform the operations of:

determining if the local timestamp is less than the global timestamp;

in response to the local timestamp being less than the global timestamp,

determining if a plurality of previous reads in the first transaction are valid; and

aborting the first transaction in response to one of the plurality of previous reads in the first transaction not being valid;

incrementing the global timestamp to an incremented global timestamp;

modifying the version location associated with the address to the incremented global timestamp.

19. A tangible storage medium including compiler code which, when executed by a machine, causes the machine to perform the operations of:

detecting a transaction in program code held in the machine;

inserting a first instruction at the start of the transaction, the first instruction, when executed, to initialize a local variable, which is to be associated with the transaction, to a value of a global variable that is to represent a value of a most recent committed transaction;

detecting a load operation referencing an address in the first transaction;

inserting a call to a read barrier function before the load operation, wherein the read barrier function, when executed by a machine, causes the machine to perform the operations of;

determining a first version held in a meta-data location associated with the address, determining if the first version is greater than the local timestamp, and in response to the first versions being greater than the local timestamp;

reloading the global timestamp into the local timestamp,

determining if a plurality of previous reads in the first transaction are valid;

aborting the first transaction in response to one of the plurality of previous reads in the first transaction not being valid; and

logging the first version; and

inserting a call to a version check function after the load operation and before a commit point of the transaction, wherein the version check function, when executed by a machine, causes the machine to further perform the operations of;

determining a second version held in the version location associated with the address, determining if the second version is different from the first version; and

aborting the first transaction, in response to the second version being different from the first version.

20. The tangible storage medium of claim 19, wherein the read barrier function is included within additional code held in the machine.

21. The tangible storage medium of claim 20, wherein the version check function is included within the additional code.

22. The tangible storage medium of claim 21, wherein the compiler code, when executed, causes the machine to further perform the operations of:

detecting a store operation referencing the address in the first transaction;

inserting a call to a write barrier function before the store operation, the write barrier function, when executed, to acquire a lock for the address.

23. The tangible storage medium of claim 22, wherein the compiler code, when executed, causes the machine to further perform the operations of:

detecting a commit instruction in the first transaction;

inserting a call to a commit function in response to detecting the commit instruction, wherein the commit function, when executed, is to;

determine if the local timestamp is less than the global timestamp;

in response to the local timestamp being less than the global timestamp, determine if the plurality of previous reads in the first transaction are valid; and

abort the first transaction in response to one of the plurality of previous reads in the first transaction not being valid;

increment the global timestamp to an incremented global timestamp;

modify the version location associated with the address to the incremented global timestamp.

24. A tangible storage medium including code which, when executed by a machine, causes the machine to perform the operations of:

storing a global transaction value, which is to represent a most recent committed transaction, in a first local transaction value associated with a first transaction, in response to starting execution of the first transaction;

maintaining a current version value for a data address in a meta-data location associated with the data address, the current version value being based on the global transaction value that is associated with a most recent transaction to update the data address; and

in response to encountering a current read operation, which is included in the first transaction and references the data address, reading the current version value from the meta-data location associated with the data address, checking if the current version value indicates the data address is unlocked, logging the current version value as a logged version value in response to the first address being unlocked, validating a plurality of previous read operations from the first transaction responsive to the current version value from the meta-data location associated with the data address being greater than the local transaction value to indicate a more recent transaction than the first transaction has updated the data address; and

performing the current read operation; and

after performing the current read operation,

loading a subsequent version value from the meta-data location associated with the data address, and

aborting the first transaction in response to the subsequent version value from the meta-data location being different from the logged version value.

25. The tangible storage medium of claim 24, wherein the code, when executed, further causes the machine to perform the operations of:

in response to encountering a write operation referencing the data address, acquiring a lock in the meta-data location associated with the data address.

26. The tangible storage medium of claim 25, wherein the code, when executed, further causes the machine to perform the operations of:

committing the first transaction, wherein committing the first transaction comprises;

validating each read operation in the first transaction including the plurality of previous read operations and the current read operation, in response to the first local transaction value being less than the global transaction value;

incrementing the global transaction value to an incremented global transaction value to represent the first transaction is the most recent committed transaction; and

updating the meta-data location to at least the incremented global timestamp value to indicate the first transaction is the most recent transaction to have updated the meta-data location.

27. The tangible storage medium of claim 24, wherein validating a plurality of previous read operations in the first transaction comprises:

determining the plurality of previous read operations are valid in response to a plurality of logged versions associated with the plurality of previous read operations correspond to a plurality of current versions associated with the plurality of previous read operations.