Enabling maximum concurrency in a hybrid transactional memory system

Background

In parallel programming computing environments, sharing access to the same memory locations requires proper management and synchronization, which can be relatively difficult to perform. Traditionally, synchronization between threads accessing shared memory has been realized using locks to protect shared data from simultaneous access. However, locks are often overly conservative in their serialization to shared data, which might not always be necessary at run-time, but is often challenging or impossible to determine when code is written.

Transactional memory has been proposed as an alternative solution, to allow threads to speculatively execute critical sections, called transactions, in parallel. If a conflict occurs at run-time, threads stall or roll back their transactions and execute them again to resolve the conflict. In transactional memory systems, threads can speculatively execute transactions without altering the contents of shared memory locations until the transactions subsequently commit. If a conflict is detected between two transactions, one of the transactions may be aborted so that the other transaction can commit, at which time the committed transaction may alter the contents of the shared memory locations.

Brief description of the drawings

FIG. 1 is a block diagram of a system in accordance with an embodiment.

FIG. 2 is a high level flow diagram of execution of a transaction in accordance with an embodiment.

FIG. 3 shows possible timings between a hardware transaction and a software transaction in accordance with an embodiment.

FIG. 4 is a block diagram of a hybrid transactional memory system flow in accordance with an embodiment of the present invention.

FIG. 5 is a flow diagram of execution of a first hardware transaction in accordance with an embodiment.

FIG. 6 illustrates details of the phases of a first hardware transaction in accordance with an embodiment.

FIG. 7 is a flow diagram of execution of a second transaction in accordance with an embodiment.

FIG. 8 illustrates details of a basic Bloom filter-based hardware transaction in accordance with an embodiment.

FIG. 9 illustrates details of an optimized Bloom filter-based hardware transaction in accordance with an embodiment.

FIG. 10 is a flow diagram of execution of a speculative software transaction in accordance with an embodiment.

FIG. 11 illustrates details of a software transaction execution in accordance with an embodiment.

FIG. 12 is a flow diagram of execution of an irrevocable software transaction in accordance with an embodiment.

FIG. 13 illustrates details of an irrevocable software transaction in accordance with an embodiment.

FIG. 14 is a block diagram of a system in accordance with another embodiment.

Detailed description

In various embodiments implementing a transactional memory system, conflicts may be determined between one or more hardware transactions running concurrently with one or more software transactions using information regarding accessed memory locations. In certain implementations this information may be maintained by way of filter sets associated with threads executing the transactions. More particularly, embodiments may implement these filter sets as so-called Bloom filters in which information regarding accessed memory locations may be stored.

In general, a Bloom filter may be implemented as a bit vector including a plurality of fields each providing a value associated with one or more memory locations. In operation, an accessed memory location address (or a portion thereof) is hashed with one or more hash values. The hash results are used to populate corresponding entries of the bit vector. More specifically, upon an access and hash computation, the indicated fields of the bit vector may be set at a logical one or active value to indicate that the corresponding address has been accessed. Similarly, any field having a logical zero or inactive value indicates that one or more given addresses of the memory have not been accessed.

Conflict detection may be performed at least in part using multiple Bloom filter values. More specifically, a Bloom filter for a first thread may have its contents compared with the contents of a Bloom filter for a second thread having a concurrently executing transaction. If the intersection comparison indicates that the access memory locations intersect in one or more positions, a conflict is detected and various operations to rollback or abort one or more of the transactions may occur. Instead if the intersection comparison indicates that accessed memory locations do not intersect, one or both of the transactions may proceed with commitment without conflict detection.

Embodiments may be used to determine conflicts between the hardware transactions running concurrently with a software transaction. Using an embodiment with a Bloom filter provided for each thread, hardware transactions that finish execution while a software global lock is held by a software transaction may be forced to abort only if a conflict is found. Bloom filters can sometimes allow false positives, so spurious aborts can still occur. Nonetheless, use of Bloom filters can improve the commit rate of the hardware transactions.

Embodiments may be used in a hybrid transactional memory (HTM) providing for both software transactions and hardware transactions using a single global lock to be acquired by a given software transaction. The hardware transactional memory may be implemented solely in processor hardware, which uses best efforts to complete a transaction to commitment. The software transactional memory is implemented entirely in software to synchronize shared memory in multithreaded programs.

At the end of a hardware transaction, the hardware transaction consults the single global lock. If the lock is free, the hardware transaction can successfully commit. In cases where the single global lock is not free, conflict detection may be performed using per thread Bloom filters that represent read and write sets of each transaction. In this way, non-conflicting hardware transactions can commit even if the single global lock is taken by a software transaction.

Embodiments thus enable an increase in the amount of concurrency realized in a hybrid transactional memory system. In order to detect conflicts between the software transaction and hardware transactions, each thread is associated with a Bloom filter. During execution of a transaction within a thread, each read and write is annotated to add the memory location to the Bloom filter. In an embodiment, this annotation may be done by a library call. However, other embodiments may in-line such annotations with read and write memory accesses. Alternately, a compiler may insert instructions to handle the Bloom filter insertions.

Upon completion of a hardware transaction (namely the critical section of the transaction), the transaction consults the global lock before committing and, if it is free, the transaction can commit successfully. However, if the lock is taken, the Bloom filter contents of the hardware transaction and the software transaction (that owns the global lock) are compared in an intersection operation to determine if there are conflicts. The Bloom filter allows false positives, but not false negatives. Therefore, a conflict may be detected despite the transactions not having an actual conflict, but the intersection comparison will not report zero conflicts if the transactions accessed the same memory location. As such, hardware transactions can commit successfully even if the lock is taken so long as the Bloom filters do not report conflicts.

In one particular hybrid transactional memory system, a single software transaction may concurrently execute with one or more hardware transactions. At a beginning of the software transaction, it acquires the single global lock to ensure exclusivity. Each hardware transaction reads this lock at the end of the critical section to determine if it can try to commit or it is to consult the Bloom filters. In an embodiment, the single global lock can store an identifier of the owner thread, thus indicating to a hardware transaction which Bloom filter to check for conflicts.

In an embodiment, the Bloom filters may be implemented as software Bloom filters. Using these filters, each transaction (hardware or software) adds each memory location read or written to its own Bloom filter as it reads/writes that location. At the end of a hardware transaction, the Bloom filter is used to identify conflicts with the software transaction currently holding the single global lock, if any.

Note that hardware transactions execute mostly in hardware, but have read and write accesses annotated so that they the locations read/written are entered into a per thread software Bloom filter. At commit time, hardware transactions check the global lock and if it is free they can commit, otherwise they compute the set intersection between their own Bloom filter and the software Bloom filter. If there are no conflicts, the hardware transaction can successfully commit. At commitment (after confirming no conflicts or filter intersections) updates performed by the hardware transaction become visible to the other threads by writing the updated values to memory (such that all updates become visible at once). If the transaction aborts, all updates are restored to their initial state.

A hardware transaction that aborts is retried multiple times. After N (which is a configurable parameter) retries, the hardware transaction is transitioned to a software transaction and seeks to acquire the single global lock. This transition ensures forward progress in an embodiment in which software transactions do not abort.

Only one software transaction can execute at any given time, in this embodiment. A software transaction can execute when its thread owns the single global lock. It acquires the lock by writing its thread identifier (ID) in the lock location and begins executing its critical section. All updates performed by the software transaction are in place (stated another way, the software transaction directly updates memory). Moreover, the software transaction also stores locations read/written in its thread's Bloom filter, to allow any concurrent hardware transactions to check for conflicts. A software transaction can never abort, in an embodiment.

A hybrid transactional memory approach may be used to realize the faster transaction execution and reduced overhead associated with hardware transactional memory while ensuring forward progress for handled transactions. According to a hybrid transactional memory approach, each transaction is initially handled in hardware, and subsequently handled in software if forward progress cannot be achieved in hardware. In various embodiments, a hybrid transactional memory system is provided in which a global lock is used to enable concurrent execution of a software transaction and one or more hardware transactions.

FIG. 1 is a block diagram of an apparatus 100 . As shown in FIG. 1 , apparatus 100 includes multiple elements including processor element 102 , a memory element 104 , and a transaction management module 106 . The embodiments, however, are not limited to the type, number, or arrangement of elements shown.

In various embodiments, processor element 102 may be implemented using any processor or logic device capable of implementing task-level parallelism. In some embodiments, processor element 102 may be a multi-core processor. In another example embodiment, processor element 102 may be multiple processors arranged to perform tasks in parallel. Memory element 104 may be implemented using any machine-readable or computer-readable media capable of storing data, including both volatile and non-volatile memory. In some embodiments, memory element 104 may include a cache for processor element 102 . In various embodiments, memory element 104 may additionally or alternatively include other types of data storage media, such as read-only memory (ROM), random-access memory (RAM), dynamic RAM (DRAM), Double-Data-Rate DRAM (DDRAM), synchronous DRAM (SDRAM), static RAM (SRAM), programmable ROM (PROM), erasable programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), flash memory, polymer memory such as ferroelectric polymer memory, ovonic memory, phase change or ferroelectric memory, silicon-oxide-nitride-oxide-silicon (SONOS) memory, magnetic or optical cards, or any other type of media suitable for storing information. Some or all of memory element 104 may be included on the same integrated circuit as processor element 102 , or alternatively some or all of memory element 104 may be disposed on an integrated circuit or other medium, for example a hard disk drive, that is external to the integrated circuit of processor element 102 .

In some embodiments, transaction management module 106 may include circuitry, logic, other hardware and/or instructions to manage the performance of transactions according to a transactional memory paradigm. In various embodiments, transaction management module 106 may cause performance of both hardware transactions and software transactions. Hardware transactions may be transactions executed directly by logic device circuitry within processor element 102 . Software transactions may be transactions executed indirectly by programming logic running on processor element 102 .

As further shown in FIG. 1 , a system 140 is provided including apparatus 100 and a transceiver 144 . Transceiver 144 may include one or more radios capable of transmitting and receiving signals using various suitable wireless communications techniques. Such techniques may involve communications across one or more wireless networks. Exemplary wireless networks include (but are not limited to) wireless local area networks (WLANs), wireless personal area networks (WPANs), wireless metropolitan area network (WMANs), cellular networks, and satellite networks.

In some embodiments, processor element 102 may host one or more threads 108 . Each thread 108 may correspond to an application or program running on processor element 102 , and any particular application or program may have more than one associated thread 108 . An application or program may use a particular thread 108 to request performance of one or more transactions 110 . Transactions 110 may cause execution of various calculations or other tasks to be performed by processor element 102 .

In various embodiments, when a thread 108 requests execution of a transaction, transaction management module 106 manages the transaction according to a hybrid transactional memory algorithm. In some embodiments, the hybrid transactional memory algorithm may implement multiple execution phases or modes during which attempts are made to execute and commit the transaction. In various embodiments, the hybrid transactional memory algorithm may include a hardware phase and a software phase. In some embodiments, transaction management module 106 may use the software phase for a transaction only after the hardware phase has been unsuccessful.

In some embodiments, transaction management module 106 may utilize a global lock 112 in order to enable the concurrent execution of a software transaction and one or more hardware transactions. In various embodiments, transaction management module 106 may cause global lock 112 to be set or active when a software transaction is undergoing execution, and cause global lock 112 to be cleared or inactive when no software transaction is undergoing execution. In some embodiments, global lock 112 may be a spin lock. In other embodiments, a Mellor-Crummey-Scott (MCS) lock may be used for global lock 112 in order to reduce contention on the lock cache line. In various such embodiments, the “MCS acquire” and “MCS release” methods may be utilized to take advantage of hardware transactions to speed up the performance of compare-and-swap (CAS) instructions. Still further, in some embodiments this global lock may be implemented using a filter mechanism as described herein.

In some embodiments, transaction management module 106 may enable a hardware transaction to commit if global lock is inactive 112 at the conclusion of the transaction and no other conflicts occurred during transaction execution. Instead if global lock 112 is active or taken when a hardware transaction seeks to commit, transaction management module 116 may determine whether a conflict exists between the hardware transaction and the pending software transaction by reference to information stored in Bloom filters associated with the threads initiating the transactions.

In various embodiments, transaction management module 106 may include execution logic 114 . In some embodiments, execution logic 114 may be circuitry, other hardware and/or instructions to execute transactions 110 . In various embodiments, each time a thread 108 requests execution of a new transaction, execution logic 114 may perform one or more executions of the transaction. In some embodiments, execution logic 114 may initially execute the transaction one or more times as a hardware transaction, and subsequently execute the transaction as a software transaction if it is unable to commit when executed in hardware. As such, in some embodiments the software transaction mode may be a fallback execution phase during which the transaction is assigned top priority to ensure that it will commit and that forward progress will be achieved. In some embodiments, execution logic 114 also may check global lock 112 at a conclusion of a hardware transaction.

In some embodiments, transaction management module 106 may include tracking logic 116 . In various embodiments, tracking logic 116 may include circuitry, other hardware and/or instructions to manage global lock 112 , a retry counter 118 , and a retry threshold 120 . In some embodiments, tracking logic 116 may set global lock 112 based on instructions from execution logic 114 . For example, execution logic 114 may instruct tracking logic 116 to set global lock 112 when execution logic 114 begins execution of a transaction in the software phase. In various embodiments, retry counter 118 may include a running total number of attempts that have been made to perform a transaction in the hardware transaction mode. In some embodiments, retry threshold 120 may include a number of attempts after which execution logic 114 should proceed from execution as a hardware transaction to execution as a software transaction. In various embodiments, when a new transaction is received, tracking logic 116 may reset retry counter 118 (corresponding to the transaction) to zero. In some embodiments, after each unsuccessful execution of the transaction, tracking logic 116 may increment retry counter 118 .

As further shown in FIG. 1 , memory element 104 includes per thread read set storages 126 and per thread write set storages 128 . In an embodiment, the storages may store information regarding values read or written during transactions. In addition, each thread may have associated with it a corresponding Bloom filter 134 and 136 , each associated with a given read set storage or write set storage (and thread). As will be described further herein, during execution of a transaction, each read and write may be annotated into corresponding Bloom filter to indicate that a given memory address has been accessed during the transaction. This information may later be used to determine whether at least a potential conflict exists between concurrently executing transactions.

In various embodiments, transaction management module 106 may include finalization logic 128 . In some embodiments, finalization logic 128 may include circuitry, other hardware and/or instructions to determine whether to commit or abort transactions after they are executed by execution logic 114 . In various embodiments, finalization logic 128 may determine that any particular transaction is to be aborted when the transaction conflicts or potentially conflicts with another transaction. In some embodiments, finalization logic 128 may determine whether a transaction may potentially conflict with a concurrent software transaction by checking global lock 112 . In various embodiments, if global lock 112 is set and the transaction is a hardware transaction, finalization logic 128 may then reference intersection logic 124 to determine whether at least a potential conflict exists between the hardware transaction and the software transaction. To this end, intersection logic 124 may access respective Bloom filters 134 and 136 of the threads initiating the transactions to determine whether filter sets intersect. If so, at least a potential conflict is present and as such, intersection logic 124 may report the active intersection to finalization logic 128 . If instead the filter sets do not indicate an intersection, this inactive intersection is reported to finalization logic 128 .

In turn, finalization logic 128 may cause the hardware transaction to be aborted if the intersection is found, and otherwise enable the hardware transaction to commit (assuming no other conflicts are detected).

In some embodiments, if global lock 112 is set and the transaction is a software transaction, finalization logic 128 may commit the transaction and instruct tracking logic 116 to release global lock 112 . In various embodiments, if global lock 112 is not set, finalization logic 128 may commit a hardware transaction and instruct tracking logic 116 to clear retry counter 118 , without a need for interaction with intersection logic 124 to determine whether filter sets indicate a potential conflict.

In some embodiments, transaction management module 106 may include abort handler logic 130 . In various embodiments, abort handler logic 130 may include circuitry, other hardware and/or instructions to handle aborts of transactions indicated by finalization logic 128 . In some embodiments, abort handler logic 130 may determine whether a next attempted performance of an aborted transaction should occur as a hardware transaction or as a software transaction. In various embodiments, abort handler logic 130 may determine whether the transaction is to be aborted due to a conflict or potential conflict with another transaction or for another reason. If the transaction was aborted for another reason, such as due to an illegal instruction, a capacity overflow, or a cache associativity overflow due to irregular memory access patterns, abort handler logic 130 may determine that execution logic 114 should proceed directly to the software phase. If the transaction was aborted due to a conflict or potential conflict with another transaction, abort handler logic 130 may determine whether the transaction should be retried the current phase or in a next phase, e.g., based on a number of retries.

In various embodiments, to determine whether a next attempted performance of an aborted transaction should be handled as a hardware transaction or a software transaction, abort handler logic 130 may compare retry counter 118 to retry threshold 120 . In some embodiments, if retry counter 118 is less than retry threshold 120 , abort handler logic 130 may instruct execution logic 114 to retry the transaction as a hardware transaction. Otherwise, abort handler logic 130 may instruct execution logic 114 to retry the transaction as a software transaction. In various embodiments, tracking logic 116 may adaptively determine a value for retry threshold 120 based on numbers of successful and/or unsuccessful commits for attempted transactions. Although shown at this high level in the FIG. 1 embodiment, understand the scope of the present invention is not limited in this regard, and hybrid transactional memory systems may take many different forms and have numerous variations.

Referring now to FIG. 2 , shown is a high level flow diagram of execution of a transaction in accordance with an embodiment. As seen in FIG. 2 , according to method 200 , all transactions begin execution in hardware as a hardware transaction (block 210 ). During execution (block 215 ) on each read or write, a transaction records each location read or written in a software Bloom filter for the corresponding thread. After a hardware transaction finishes execution of its critical section (block 220 ), it attempts to commit by checking for conflicts with the software transaction, if there is one. The hardware transaction first checks whether the global lock is taken (diamond 225 ). If this lock is free, then the hardware transaction can successfully commit (assuming no abort has occurred, as determined at diamond 240 ). If the lock is taken, the value of the lock indicates the index or identifier of the thread holding the lock, which is thus executing a software transaction.

In this case, the hardware transaction passes to diamond 230 to access the Bloom filter of the thread executing the software transaction to determine if there are any conflicts. More specifically, at diamond 230 an intersection operation may be performed between the 2 filters to determine whether any entries or fields of the 2 Bloom filters intersect (e.g., both have an active or logical one value). If so, the hardware transaction aborts, and control passes to diamond 270 to determine whether the number of retries of the given hardware transaction has reached the configurable number N. Note that various steps may be taken upon aborting transaction, including flushing out any updated values in a buffer or other storage associated with the thread.

If instead it is determined that there is no intersection between the Bloom filters, control passes to diamond 240 to determine whether the transaction has aborted, e.g., for another reason. If not, control passes to block 250 where the transaction is committed. For commitment, the hardware transaction may update memory with any updated values, which are previously stored in a buffer visible only to the given thread during the hardware transaction execution.

Also understand that although a determination as to whether a transaction aborts is shown at diamond 240 in the particular location in the FIG. 2 embodiment, it is possible for a hardware transaction to abort at any time during its execution by way of conflict detection logic, which may detect other types of conflicts or other reasons for aborting during the transaction. However for ease of illustration understand that diamond 240 is represented in the location shown in FIG. 2 .

Still referring to FIG. 2 , if it is determined at diamond 270 that the number of retries has not reached a threshold number N, control passes to block 280 where the number of retries is incremented, and then control passes back to block 210 for beginning the hardware transaction again. Otherwise, if the number of retries has reached the retry threshold of N, control instead passes from diamond 270 to block 260 , where execution may switch to a software transaction mode. More specifically, in this implementation where only a single software transaction is permitted, the transaction may thus execute in the software transaction mode to completion, allowing the transaction to commit at block 250 .

The Bloom filters ensure conflict detection between the software transaction and the hardware transactions. Conflict detection and resolution between hardware transactions is ensured by the hardware transactional memory system. The single global lock ensures there is only one software transaction running at any time, and as such no additional conflict detection mechanism is provided for software transactions, in an embodiment.

FIG. 3 shows possible timings between a hardware transaction and a software transaction in accordance with an embodiment. In case 310 , a software transaction first updates a variable X and later a hardware transaction updates the same variable X to a different value. When the hardware transaction attempts to commit, a filter set intersection is performed which identifies the dual accesses and thus a conflict is raised and the hardware transaction is aborted. Similar operation occurs in case 320 . However in cases 330 and 340 , at the point that the hardware transactions commit, the software thread has already committed and released the single global lock. As such, when the hardware thread checks this lock, it finds it released and thus the transactions can successfully commit.

In cases 330 and 340 , the lock is free when the hardware transaction tries to commit, meaning there is no software transaction running concurrently. Even if there was an overlapping software transaction, it has already committed by this point, being serialized before the hardware transaction. If the software transaction would have performed any conflicting operations that serialized after the hardware transaction, the hardware transaction would have been aborted at the time of the conflict (because of the hardware conflict detection mechanism). Therefore enabling the hardware transaction to commit when the lock is free provides for correct behavior.

If instead the lock is taken when the hardware transaction tries to commit (as in cases 310 and 320 ), then a concurrent software transaction is executing. The committing hardware transaction is serialized before this software transaction because of possible future conflicting operations executed by the software transaction. However, the software transaction could have performed conflicting operations on one or more memory locations before the hardware transaction started tracking those locations, and thus serializing the hardware transaction before the software transaction would be incorrect behavior. Therefore, embodiments use the Bloom filters to determine this case.

Note that the software Bloom filters do not contain all the locations that the software transaction will access in the future, just the locations that the transaction has already accessed. Nevertheless, future accesses will be correctly serialized after the committed hardware transaction. Therefore, if the Bloom filters do not intersect, the hardware transaction can be correctly serialized before the software transaction and it can be allowed to commit. If the Bloom filter identifies conflicts, then the conflicting operations first occurred in the software transaction and then in the hardware transaction, otherwise the hardware transaction would have aborted. In this case, the hardware transaction cannot be serialized before the software transaction and is to be aborted. As such, embodiments correctly identify these conflicts and abort the hardware transaction. Note that it is possible for a Bloom filter to incorrectly report conflicts (as an undistinguishable false positive), so the hardware transaction will abort in these cases too, in an embodiment. However, Bloom filters do not cause false negatives, and as such all conflicts are identified and prevented

In an embodiment, an efficient Bloom filter implementation allows insertion and set intersection in O

time, minimizing overhead. Moreover, hardware transactions only read the global lock and the software Bloom filter just prior to commitment, decreasing the window when hardware transactions could be aborted because of a software transaction modifying these locations. In an embodiment, reading the lock and the Bloom filter may only add two additional cache lines to a read set of the transaction. In some embodiments, this can be optimized so that a bit of the Bloom filter is used to indicate whether to lock is taken and the rest of the Bloom filter is used as a Bloom filter. In such implementation, the lock location can serve both purposes, reducing the read set size of the hardware transaction to just one additional location. The transaction's own Bloom filters add additional cache lines to a write set, but in an implementation, this could be as low as only one cache line, depending on the Bloom filter size.

Using an embodiment, many small hardware transactions that access disjoint memory accesses from themselves and concurrently executing large software transactions can commit. As one such example, consider an array representing an open addressing hash-table. Threads can perform lookup(x) operations and insert(x) operations in this hash table. Once a threshold of occupancy is achieved, a thread decides to double the size of the hash table by allocating a new array and re-hashing elements from the old array to the new array. Lookup and insert operations are short transactions and can succeed in hardware most of the time. Re-hashing may instead be executed as a software transaction (and the thread performing the re-hashing acquires the single global lock). In this case with precise conflict detection between the software transaction and the concurrent hardware transactions, lookup operations executed as hardware transactions can commit using data from the old array while re-hashing to the new array is taking place. Moreover, insert operations executed as hardware transactions that occur to the end of the old array (namely in the part that has not been re-hashed yet) can also commit during re-hashing. Therefore, embodiments improve throughput by allowing small hardware transactions to commit concurrently with long executing software transactions.

While providing a Bloom filter conflict detection technique as described above improves parallelism, there still can be inefficiencies given use of a single global lock in the above embodiments. In other embodiments, a transactional memory system may be provided that enables multiple hardware transactions and multiple software transactions to execute and commit in parallel. In general, a cache-based hardware transactional memory system may be used for the hardware component and an invalidation-based software transactional memory system may be used for the software component. These embodiments provide a hybrid transactional memory system that allows multiple hardware transactions to execute concurrently with multiple software transactions, while still guaranteeing forward progress.

Referring now to FIG. 4 , shown is a block diagram of a hybrid transactional memory system in accordance with an embodiment of the present invention. As shown in FIG. 4 , a HTM system 400 provides for multiple hardware transaction modes and multiple software transaction modes. In the implementation shown in FIG. 4 , transactions begin in a first hardware transaction mode 410 , referred to herein as a light hardware (LiteHW) transaction mode. If an overflow or unsupported instruction occurs, the transaction is immediately upgraded to another type of transaction mode. Instead, if the transaction aborts for another reason (e.g., due to conflict), the transaction retries a number of times before being upgraded to a second hardware transaction mode 420 , referred to herein as a Bloom filter hardware (BFHW) mode. Similar retries occur and then the transaction is updated to a first software transaction mode 430 , referred to herein as a speculative software (SpecSW) mode, if it does not commit. Again in this mode, a transaction may be retried a number of times before the transaction is upgraded to a second software transaction mode 440 , referred to herein as an irrevocable software (IrrevocSW) mode. Understand that while shown with the particular modes and interactions in FIG. 4 , embodiments are not limited in this regard.

If most transactions are short, access memory that can fit within the TM-supported cache space, and contain no unsupported instructions, they can succeed directly in hardware, without the need to synchronize with software transactions. The most lightweight type of transaction is the first hardware transaction mode (LiteHW). This transaction type executes without any annotations for reads and writes and can commit successfully if there are no software transactions running at the time it tries to commit. This type of transaction is simple and fast, but it allows for little concurrency with software transactions.

The second hardware transaction mode, BFHW, uses software Bloom filters to record the locations read and written by the hardware transaction, to enable detection of conflicts with software transactions that execute concurrently. This transaction type adds extra overhead compared to the LiteHW transaction, but can commit even in the presence of concurrently executing software transactions. Hardware transactions are fast, but can fail in best-effort HTMs because of unsupported instructions or overflow, and thus software fallback is provided.

In turn, the first software transaction mode, SpecSW, performs a speculative software transaction in which the transaction records locations read and written in Bloom filters for conflict detection with other software and hardware transactions and stores all writes in a hash table for deferred updates during a commit phase. Invalidation occurs post-commitment to abort in-flight conflicting transactions and per transaction locks are used to ensure opacity. In this first software transaction mode, each read is validated to prevent zombie transactions (transactions that will abort) from reaching an inconsistent state.

Finally, the second software transaction mode, IrrevocSW, performs all updates in place (directly to memory) and cannot be aborted. Because of this quality, only one IrrevocSW transaction can execute at any given time. However, multiple SpecSW and BFHW transactions can execute concurrently with an IrrevocSW transaction.

Conflict detection between multiple software transactions is realized using the Bloom filters, as discussed above. Conflict detection between software and hardware transaction also uses the Bloom filters, however, using best-effort HTMs that do not have escape actions generally leads to aborting the hardware transactions upon conflict detection. This behavior is due to the hardware transactions' strong isolation: any memory location that is tracked by the hardware will cause a conflict, thereby aborting the hardware transaction when a software transaction performs a conflicting access to that location. Moreover, hardware updates do not become visible to the other threads until the hardware transaction commits.

Embodiments postpone conflict detection between hardware and software transactions until after the hardware transaction has committed. The hardware transaction then performs a post commit phase in which it invalidates all in-flight conflicting software transactions. Because the hardware transaction has already committed, sharing Bloom filter information with other threads cannot cause it to abort.

Each transaction, whether it is software or hardware, goes through a plurality of phases. The behavior in each of these phases depends on the type of transaction. The first phase is a beginning phase in which a transaction is started. A hardware transaction calls a start hardware transaction instruction, while a software transaction records information about the starting address and notifies other threads of its presence via an indicator such as a flag (e.g., a sw_exists flag) indicating existence of at least one software transaction.

During an execution phase, read and write operations are annotated and the behavior is decided by the type of transaction executing. All transaction types record accessed locations in Bloom filters, except for LiteHW transactions.

During an abort phase, hardware aborts are dealt with automatically by the hardware. For a software transaction, software clears information recorded during the transaction execution and restarts from the address stored during the begin phase.

During a commit phase, conflict detection is performed and memory updates are made if the transaction can commit. Its implementation is dependent on the transaction type.

The description continues in the full USPTO document.