Efficient and consistent software transactional memory

• US 20080163220A1
• Filed: 12/28/2006
• Published: 07/03/2008
• Est. Priority Date: 12/28/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wu, Youfeng, Saha, Bratin, Chen, Wei-Yu, Wang, Cheng, Adl-Tabatabai, Ali-Reza
• Granted Patent: US 8,060,482 B2
• Time in Patent Office: Days
• US Class Current: 718/101
• 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 timestamp value in a first local timestamp associated with a first transaction, in response to starting execution of the first transaction;

in response to encountering a current read operation, which is included in the first transaction and references a first address, validating a plurality of previous read operations in the first transaction, if a current version associated with the first address is greater than the local time stamp.

2. The method of claim 1, wherein in response to encountering the current read operation further checking if the first address is unlocked and logging the current version in response to the first address being unlocked.

3. The method of claim 2, further comprising

performing the current read operation;

and

after performing the current read operation,

checking a subsequent version associated with the first address, and

aborting the first transaction, if the subsequent version is different from the current version.

4. The method of claim 3, further comprising:

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

5. The method of claim 4, further comprising:

committing the first transaction, wherein committing the 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 timestamp being less than the global timestamp;

incrementing the global timestamp value to an incremented global timestamp value; and

setting a write version in the meta-data location to at least the incremented global timestamp value.

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

determining the plurality of previous read operations are valid, if 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.

7. An article of manufacture including program code which, when executed by a machine, causes the machine to perform the operations of:

detecting a load operation referencing an address in a transaction;

inserting a group of read barrier operations to be executed before the load operation, the group of read barrier operations, when executed, to obtain a current version associated with the address;

inserting a group of version check barrier operations after the load operation, the group of version check barrier operations, when executed, to compare a subsequent version associated with the address to the current version.

8. The article of manufacture of claim 7, further comprising

inserting a call to a read barrier function before the load operation, wherein the read barrier function includes the group of read barrier operations;

and

inserting a call to a version check barrier function after the load operation, wherein the version check barrier function includes the group of version check barrier operations;

9. The article of manufacture of claim 7, wherein the group of version check barrier operations include:

a first version check barrier operation, when executed, to obtain the subsequent version;

a second version check barrier operation, when executed, to determine if the subsequent version is different from the current version; and

a call to an abort function, when executed in response to the subsequent version being different from the current version, to abort the transaction.

10. The article of manufacture of claim 7, further comprising:

detecting a start transaction instruction; and

inserting a copy operation to be executed at the start of the transaction, the copy operation, when executed, to copy a global time stamp to a local time stamp to be associated with the transaction.

11. The article of manufacture of claim 10, wherein the group of read barrier operations include:

a first read barrier operation, when executed, to obtain the current version;

a second read barrier operation, when executed, to determine if the current version greater than the local time stamp; and

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

12. The article of manufacture of claim 11, wherein the group of read barrier operations further include

a third read barrier operation, when executed in response to the current version being greater than the local time stamp, to copy the global time stamp to the local time stamp;

and

a fourth read barrier operation, when executed, to log the current version in a read log.

13. The article of manufacture of claim 10, further comprising:

detecting a commit transaction instruction;

inserting a group of commit operations to be executed in response to committing the transaction, the group of commit operations including;

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

a group of validation operations, when executed in response to the local time stamp being less than the global time stamp, to validate a plurality of previous reads in the transaction.

14. The article of manufacture of claim 13, wherein the group of commit operations further include:

a second commit operation, when executed, to increment the global time stamp to an incremented global time stamp;

a third commit operation, when executed, to set a most recent version associated with the address to the incremented global time stamp in response to a lock being acquired for the address during execution of the transaction.

15. A system comprising:

a memory device to store compiler code and program code; and

a processor associated with the memory device, the processor to execute the compiler code, wherein the compiler code, when executed, is to;

detect a first transaction in the program code;

insert a first instruction, when executed, to load a global time stamp into a local timestamp associated with the first transaction, wherein the global timestamp is to hold a most recent local timestamp value of a most recent committed transaction.

16. The system of claim 15, wherein the compiler code, when executed, is also to detect a load operation referencing an address in the first transaction;

insert a call to a read barrier function before the load operation; and

insert a call to a version check function after the load operation.

17. The system of claim 16, wherein the compiler code, when executed, is also to insert the read barrier function, the read barrier function, when executed, to determine a first version held in a version location associated with the address;

determine if the first version is greater than the local timestamp;

in response to the first versions being greater than the local timestamp;

reload the global timestamp into the local timestamp;

determine if a 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; and

log the first version.

18. The system of claim 17, wherein the compiler code, when executed, is also to insert the version check function, the version check function, when executed, to:

determine a second version held in the version location associated with the address;

determine if the second version is different from the first version; and

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

19. The system of claim 18, wherein the compiler code, when executed, is also to:

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

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

20. The system of claim 19, wherein the compiler code, when executed, is also to:

detect a commit instruction in the first transaction;

insert 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.