Methods and apparatus to implement parallel transactions

• US 7,496,716 B2
• Filed: 07/18/2006
• Issued: 02/24/2009
• Est. Priority Date: 02/22/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Shavit, Nir N., Dice, David
• Primary Examiner(s): Nguyen; Hiep T
• Application Number:
  US11/488,618
• Publication Number:
  US 20070198781A1
• Time in Patent Office: 952 Days
• Field of Search: None
• US Class Current: 711/147
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Cache logic associated with a respective one of multiple processing threads executing in parallel updates corresponding data fields of a cache to uniquely mark its contents. The marked contents represent a respective read set for a transaction. For example, at an outset of executing a transaction, a respective processing thread chooses a data value to mark contents of the cache used for producing a transaction outcome for the processing thread. Upon each read of shared data from main memory, the cache stores a copy of the data and marks it as being used during execution of the processing thread. If uniquely marked contents of a respective cache line happen to be displaced (e.g., overwritten) during execution of a processing thread, then the transaction is aborted (rather than being committed to main memory) because there is a possibility that another transaction overwrote a shared data value used during the respective transaction.

Claims

1. A method comprising:

for each of multiple processing threads that execute in parallel and that have access to a common set of shared data to produce corresponding transaction outcomes;

i) utilizing a hardware transactional memory implementation to track a status associated with a set of specific shared data utilized by a respective processing thread to produce a respective transaction outcome; and

ii) utilizing a software transactional memory implementation associated with the respective processing thread to maintain a respective set of local modifications to the set of specific shared data.

2. A method as in claim 1, wherein utilizing the hardware transactional memory implementation to track the status includes providing an indication when any portion of a cache used for storing the set of specific shared data has been previously written to during execution of the respective processing thread.

3. A method as in claim 2 further comprising:

foregoing a step of committing the respective set of local modifications to shared memory in response to detecting that at least a portion of the cache used for storing the specific shared data to produce the respective transaction outcome was displaced during execution of the respective processing thread.

4. A method as in claim 1, wherein utilizing the hardware transactional memory implementation includes:

providing a unique data value associated with a given processing thread;

for each read of data from memory initiated by the given processing thread, storing a respective data value read from memory into a cache; and

for each respective entry of a data value read from memory that is stored in the cache, marking a cache entry with the unique data value to indicate that the data value read from memory belongs to a respective read-set associated with the given processing thread.

5. A method as in claim 4 further comprising:

prior to marking the cache entry, verifying whether the cache entry was previously marked with the unique data value associated with the respective processing thread and, if so, initiating modification to a respective status register to indicate that the cache entry of data utilized by the given processing thread was overwritten during execution of the processing thread.

6. A method as in claim 5 further comprising:

in response to detecting the modification of the respective status register, aborting a process of committing the respective set of local modifications to the memory.

7. A method as in claim 1, wherein utilizing the hardware transactional memory implementation includes reserving a unique data value to mark at least a portion of cache entries that are not part of a respective read set associated with the respective processing thread.

8. A method as in claim 1, wherein utilizing the hardware transactional memory implementation includes:

maintaining a cache;

utilizing the cache to store copies of the set of specific shared data retrieved from memory; and

maintaining a storage location associated with the cache, the storage location being used to store a respective data value that is modified in response to detecting that contents of the cache have been displaced prior to committal of the set of local modifications to the memory.

9. A method as in claim 8, wherein execution of the respective processing thread includes:

at an outset of executing the respective processing thread, reading a data value from the storage location for later use;

initiating access to memory to produce the set of specific shared data;

storing the specific shared data in the cache; and

at an end of executing the processing thread and prior to committing the set of local modifications to memory, verifying whether the data value previously read from the storage location matches a current data value of the storage location.

10. A method as in claim 8 further comprising:

maintaining status information associated with the storage location, the status information indicating a respective reason for displacement of at least one cache entry during a course of executing the respective processing thread.

11. A method as in claim 10, wherein maintaining status information includes at least one of:

providing an indication that another processing thread modified a value in memory having a corresponding copy stored in the cache; and

providing an indication that the processing thread required so many accesses to memory that corresponding copies of the accesses stored in the cache caused cache entries of the cache to be overwritten.

12. A method as in claim 1, wherein utilizing the hardware transactional memory implementation includes:

enabling the processing thread to provide a unique data value to be used to mark multiple entries in a respective cache as belonging to the set of specific shared data associated with the respective processing thread.

13. A computer system including:

multiple processing threads executing in parallel;

memory to store shared data that is accessible to each of the multiple processing threads;

for each of the multiple processing threads;

i) a respective cache and corresponding hardware logic for storing and marking accessed shared data values from memory, the accessed shared data values used by a respective processing thread to produce a respective transaction outcome; and

ii) a buffer to store a write-set maintained by the respective processing thread to temporarily store values in a local buffer prior to committing the values to the shared data.

14. A computer system as in claim 13, wherein the respective cache and corresponding hardware logic include associated status information to enable the respective processing thread to identify whether any of the accessed shared data values have been modified over a course of executing the respective processing thread.

15. A computer system as in claim 14, wherein the corresponding hardware logic includes a first register and a second register accessible by the respective processing thread, the first register storing a unique data value provided by the respective processing thread to mark the accessed shared data values stored in the cache, the second register storing a respective data value that is modified by the corresponding hardware logic to indicate when contents of the cache have been overwritten.

16. A computer system as in claim 15, wherein the respective processing thread accesses contents of the second register to identify at least one of:

i) whether another processing thread modified a value of shared data during execution of the processing thread causing a corresponding copy of the value to be stored in the cache, and ii) whether the processing thread required so many accesses to shared data over a course of executing a respective transaction that at least a portion of corresponding copies of the accessed shared data in the cache have been overwritten.

17. A computer readable medium storing:

instructions for a respective processing thread of multiple processing threads executing in parallel to rely on use of a hardware transactional memory implementation to track a status associated with a set of specific shared data utilized by a respective processing thread to produce a respective transaction outcome; and

instructions to implement a transactional memory technique associated with the respective processing thread to maintain a respective set of local modifications to the set of specific shared data.

18. A computer readable medium as in claim 17 further storing:

instructions for the respective processing thread to access a respective register associated with a cache used for storing the set of specific shared data, the respective register indicating whether any portions of the cache have been displaced during execution of the respective processing thread.

19. A computer readable medium as in claim 18 further storing:

instructions to forego a step of committing the respective set of local modifications to shared memory in response to detecting that at least a portion of the cache used for storing the set of specific shared data to produce the respective transaction outcome was overwritten during execution of the respective processing thread.

20. A computer readable medium as in claim 17 further storing:

instructions to read an initial data value from a storage location for later use;

instructions to initiate access to the shared data in memory to produce the set of specific shared data; and

instructions to, at an end of executing the processing thread and prior to committing the set of local modifications to memory, verify whether the data value previously read from the storage location matches a current data value of the storage location, the current data value being different from the initial data value if any data values associated with reads performed by the respective processing thread changed during execution of the respective processing thread.