Transactional block conflict resolution based on the determination of executing threads in parallel or in serial mode

• US 8,539,486 B2
• Filed: 07/17/2009
• Issued: 09/17/2013
• Est. Priority Date: 07/17/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cain, Harold W. III, Cascaval, Gheorghe C., Michael, Maged M.
• Primary Examiner(s): To, Jennifer
• Assistant Examiner(s): Arcos, Caroline H
• Application Number:
  US12/504,925
• Publication Number:
  US 20110016470A1
• Time in Patent Office: 1,523 Days
• Field of Search: None
• US Class Current: 718/100
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

Mechanisms are provided for handling conflicts in a transactional memory system. The mechanisms execute threads in a data processing system in a first conflict resolution mode of operation in which threads execute conflicting transactional blocks speculatively. The mechanisms determine, for a transactional block, if the first conflict resolution mode of operation is to be transitioned to a second conflict resolution mode of operation in which threads accessing conflicting transactional blocks are executed serially and non-speculatively. Moreover, the mechanisms execute a thread that accesses the transactional block using the second conflict resolution mode of operation in response to the determination indicating that the first conflict resolution mode of operation is to be transitioned to the second conflict resolution mode of operation.

Claims

1. A method, in a data processing system having a plurality of processors and a memory, for handling conflicts in a transactional memory system, comprising:

executing, by the plurality of processors, threads in the data processing system in a first conflict resolution mode of operation in which the threads execute conflicting transactional blocks speculatively;

determining, by a processor of the plurality of processors, for a transactional block, whether the first conflict resolution mode of operation is to be transitioned to a second conflict resolution mode of operation in which the threads accessing the conflicting transactional blocks are executed serially and non-speculatively;

executing, by the processor, a thread that accesses the transactional block using the second conflict resolution mode of operation in response to the determination indicating that the first conflict resolution mode of operation is to be transitioned to the second conflict resolution mode of operation; and

determining whether or not to transition the transactional block back from the second conflict resolution mode of operation to the first conflict resolution mode of operation, wherein the determining whether or not to transition the transactional block back from the second conflict resolution mode of operation to the first conflict resolution made of operation comprises;

maintaining, in the transactional block profile entry, a transition counter identifying a number of accesses to transactional blocks having a same classification associated with the transactional block that have occurred since the transactional block was transitioned to the second conflict resolution mode of operation;

determining whether the transition counter has a value that meets or exceeds a predetermined threshold; and

transitioning the transactional block from the second conflict resolution mode of operation to the first conflict resolution mode of operation in response to the transition counter having the value that meets or exceeds the predetermined threshold.

2. The method of claim 1, further comprising:

receiving a first request for access to the transactional block from a first thread executing on a first processor; and

generating a transactional block profile entry in a profile data structure, for the transactional block, wherein the transactional block profile entry comprises a transactional block identifier and one or more abort counters for counting a number of times a thread executing the transactional block has had to be aborted due to a conflict with another thread executing the transactional block, or accessing a same portion of data as the transactional block, at substantially a same time.

3. The method of claim 2, further comprising:

detecting a conflict between the first thread or a second thread, wherein the conflict is due to a second request attempting to either access the same transactional block as the first thread or modify a same portion of data as the first thread;

resolving the conflict by selecting one of the first thread or the second thread to allow to persist first state changes or first modifications to the same portion of data while second state changes or second modifications to the same portion of data made by a non-selected one of the first thread or the second thread are not persisted; and

incrementing an abort counter, in the one or more abort counters of the transactional block profile entry, based on the resolution of the conflict.

4. The method of claim 3, further comprising:

storing in the transactional block profile entry, a transactional block identifier of a conflicting transactional block executed by the second thread responsive to the transactional block executed by the second thread is different from the transactional block executed by the first thread.

5. The method of claim 3, wherein the determining for the transactional block, whether the first conflict resolution mode of operation is to be transitioned to the second conflict resolution mode of operation comprises:

comparing at least one abort counter value of the one or more abort counter values to a predetermined threshold; and

transitioning the first conflict resolution mode of operation to the second conflict resolution mode of operation in response to the at least one abort counter value being equal to or greater than the predetermined threshold.

6. The method of claim 2, further comprising:

assigning a classification having a classification identifier to the transactional block in response to the first conflict resolution mode of operation being transitioned to the second conflict resolution mode of operation;

storing the classification identifier in the transactional block profile entry.

7. The method of claim 6, wherein the classification and classification identifier assigned to the transactional block is the same classification and classification identifier of a conflicting transactional block responsive to the conflicting transactional block already having an associated classification and classification identifier, or is a new unique classification and new unique classification identifier responsive to the conflicting transactional block does not already having an associated classification and classification identifier.

8. The method of claim 6, wherein, under the second conflict resolution mode of operation, transactional blocks having the same classification and a same classification identifier are executed serially with regard to one another.

9. The method of claim 8, wherein for threads accessing transactional blocks having the same classification and the same classification identifier, the threads must obtain a lock associated with the same classification and the same classification identifier before being permitted to access a corresponding transactional block, and wherein once a thread obtains the lock associated with the same classification and the same classification identifier, the thread may access any transactional block having that same classification and the same classification identifier.

10. The method of claim 9, wherein the lock is released by an active thread to be obtained by a waiting thread, in a thread queue associated with the same classification and same classification identifier, in response to the active thread completing execution of its corresponding transactional block, and wherein a priority of threads in the thread queue is determined according to at least one of a physical locality or temporal locality of the threads in the thread queue.

11. The method of claim 10, wherein the at least one of a physical locality or a temporal locality of the threads is determined based on information stored in a configuration data structure.

12. The method of claim 10, wherein the at least one of a physical locality or a temporal locality of the threads is determined according to one of

whether or not processors executing the threads share a same cache level;

bus speeds associated with processors executing the threads;

processor speeds of processors executing the threads;

a number of clock domain crossings between the threads;

a number of chip boundary crossings between the threads;

a distance in network hops between the threads;

or

a proximity to a shared memory controller or coherence directory between the threads.

13. The method of claim 1, wherein the determining whether or not to transition the transactional block back from the second conflict resolution mode of operation to the first conflict resolution mode of operation comprises:

monitoring the programmatic changes in execution of code by the plurality of processors; and

transitioning the transactional block back from the second conflict resolution mode of operation to the first conflict mode of operation in response to a programmatic change in execution code by the plurality of processors being detected.

14. The method of claim 13, wherein the programmatic changes in execution of code by the plurality of processors comprises a change in execution phase of code, wherein the change in execution phase of code is identified by one of annotations inserted into the code by a programmer or compiler to denote phases of computation, or runtime hardware performance monitors identifying one of a number of cache misses, instructions complete, or branching behavior.

15. A computer program product comprising a non-transitory computer readable storage medium having a computer readable program recorded thereon, wherein the computer readable program, when executed on a data processing system, causes the data processing system to:

execute threads, in the data processing system, in a first conflict resolution mode of operation in which the threads execute conflicting transactional blocks speculatively;

determine, for a transactional block, whether the first conflict resolution mode of operation is to be transitioned to a second conflict resolution mode of operation in which the threads accessing the conflicting transactional blocks are executed serially and non-speculatively;

execute a thread that accesses the transactional block using the second conflict resolution mode of operation in response to the determination indicating that the first conflict resolution mode of operation is to be transitioned to the second conflict resolution mode of operation; and

determine whether or not to transition the transactional block back from the second conflict resolution mode of operation to the first conflict resolution mode of operation, wherein the computer readable program to determine whether or not to transition the transactional block back from the second conflict resolution mode of operation to the first conflict resolution mode of operation further causes the data processing system to;

maintain, in the transactional block profile entry, a transition counter identifying a number of accesses to transactional blocks having a same classification associated with the transactional block that have occurred since the transactional block was transitioned to the second conflict resolution mode of operation;

determine whether the transition counter has a value that meets or exceeds a predetermined threshold; and

transition the transactional block from the second conflict resolution mode of operation to the first conflict resolution mode of operation in response to the transition counter having the value that meets or exceeds the predetermined threshold.

16. The computer program product of claim 15, wherein the computer readable program further cause the computing device to:

receive a first request for access to the transactional block from a first thread executing on a first processor;

generate a transactional block profile entry in a profile data structure, for the transactional block, wherein the transactional block profile entry comprises a transactional block identifier and one or more abort counters for counting a number of times a thread executing the transactional block has had to be aborted due to a conflict with another thread executing the transactional block, or accessing a same portion of data as the transactional block, at substantially a same time;

detecting a conflict between the first thread and a second thread, wherein the conflict is due to a second request attempting to either access the same transactional block as the first thread or modify a same portion of data as the first thread;

resolve the conflict by selecting one of the first thread or the second thread to allow to persist first state changes or first modifications to the same portion of data while second state changes or second modifications to the same portion of data made by a non-selected of the first thread or the second thread are not persisted;

increment an abort counter, in the one or more abort counters of the transactional block profile entry, based on the resolution of the conflict; and

store in the transactional block profile entry, a transactional block identifier of a conflicting transactional block executed by the second thread responsive to the transactional block executed by the second thread is different from the transactional block executed by the first thread, wherein the determining for the transactional block, whether the first conflict resolution mode of operation is to be transitioned to the second conflict resolution mode of operation comprises;

comparing at least one abort counter value of the one or more abort counter values to a predetermined threshold; and

transitioning the first conflict resolution mode of operation to the second conflict resolution mode of operation in response to the at least one abort counter value being equal to or greater than the predetermined threshold.

17. The computer program product of claim 15, wherein the computer readable program further cause the computing device to:

receive a first request for access to the transactional block from a first thread executing on a first processor;

generate a transactional block profile entry in a profile data structure, for the transactional block, wherein the transactional block profile entry comprises a transactional block identifier and one or more abort counters for counting a number of times a thread executing the transactional block has had to be aborted due to a conflict with another thread executing the transactional block, or accessing a same portion of data as the transactional block, at substantially a same time;

assign a classification having a classification identifier to the transactional block in response to the first conflict resolution mode of operation being transitioned to the second conflict resolution mode of operation;

store the classification identifier in the transactional block profile entry, wherein;

under the second conflict resolution mode of operation, transactional blocks having the same classification and a same classification identifier are executed serially with regard to one another,

for threads accessing transactional blocks having the same classification and the same classification identifier, the threads must obtain a lock associated with the same classification and the same classification identifier before being permitted to access a corresponding transactional block,

once a thread obtains the lock associated with the same classification and the same classification identifier, the thread may access any transactional block having the same classification and the same classification identifier,

the lock is released by an active thread to be obtained by a waiting thread, in a thread queue associated with the same classification and same classification identifier, in response to the active thread completing execution of its corresponding transactional block, and

a priority of threads in the thread queue is determined according to at least one of a physical locality or temporal locality of the threads in the thread queue.

18. An apparatus, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

execute threads in a first conflict resolution mode of operation in which the threads execute conflicting transactional blocks speculatively;

determine, for a transactional block, whether the first conflict resolution mode of operation is to be transitioned to a second conflict resolution mode of operation in which the threads accessing the conflicting transactional blocks are executed serially and non-speculatively;

execute a thread that accesses the transactional block using the second conflict resolution mode of operation in response to the determination indicating that the first conflict resolution mode of operation is to be transitioned to the second conflict resolution mode of operation; and

determine whether or not to transition the transactional block back from the second conflict resolution mode of operation to the first conflict resolution mode of operation, wherein the instructions to determine whether or not to transition the transactional block back from the second conflict resolution mode of operation to the first conflict resolution mode of operation further causes the processor to;

maintain, in the transactional block profile entry, a transition counter identifying a number of accesses to transactional blocks having a same classification associated with the transactional block that have occurred since the transactional block was transitioned to the second conflict resolution mode of operation;

determine whether the transition counter has a value that meets or exceeds a predetermined threshold; and

transition the transactional block from the second conflict resolution mode of operation to the first conflict resolution mode of operation in response to the transition counter having the value that meets or exceeds the predetermined threshold.