CN102741826A - Performing mode switching in an unbounded transactional memory (UTM) system - Google Patents

Abstract

In one embodiment, the present invention includes a method for selecting a first transaction execution mode to begin a first transaction in a unbounded transactional memory (UTM) system having a plurality of transaction execution modes. These transaction execution modes include hardware modes to execute within a cache memory of a processor, a hardware-assisted mode to execute using transactional hardware of the processor and a software buffer, and a software transactional memory (STM) mode to execute without the transactional hardware. The first transaction execution mode can be selected to be a highest performance of the hardware modes if no pending transaction is executing in the STM mode, otherwise a lower performance mode can be selected. Other embodiments are described and claimed.

Description

Executing Schema Switching in Unconstrained Transactional Memory (UTM) Systems

Background technique

In modern computing systems, there may be multiple processors, and each such processor may execute a different thread of code for a common application. In order to maintain consistency, a data synchronization mechanism can be used. One such technique involves the use of transactional memory (TM). Transactional execution often involves the execution of multiple micro-operations, operations, or groupings of instructions. Each of the plurality of threads can execute and access common data within the memory structure. If two threads both access/alter the same entry within the structure, conflict resolution can be performed to ensure data validity. One type of transactional execution includes software transactional memory (STM), where tracking memory accesses, conflict resolution, aborting tasks, and other transactional tasks are performed in software, generally without hardware support.

Another type of transactional execution includes hardware transactional memory (HTM) systems, where hardware is included to support access tracking, conflict resolution, and other transactional tasks. The actual memory data array is pre-extended with additional bits to hold information, such as hardware attributes to track reads, writes and buffering, and thus travel with the data, from the processor to the memory. Often, this information is said to be persistent, ie, it is not lost on cache evictions because the information propagates with the data through the entire memory hierarchy. However, this persistence imposes more overhead on the overall memory hierarchy.

Yet another type of TM model is known as Unconstrained Transactional Memory (UTM), which enables arbitrarily large transactions in terms of time and memory footprint to occur using a combination of hardware and software through hardware acceleration . Running and implementing UTM transactions typically requires specially compiled code to implement concurrency control mechanisms that interface with UTM hardware acceleration. Thus, UTM transactions can be complex and may not properly interface with existing hardware and STM transaction systems.

Description of drawings

FIG. 1 is a block diagram of a processor according to one embodiment of the invention.

Figure 2 is a block diagram of maintaining metadata of a data item in a processor according to one embodiment of the present invention.

FIG. 3 is a flowchart of a method for selecting a transaction mode for executing a TM transaction according to an embodiment of the present invention.

4 is a flowchart of a method of handling a mode switch as a result of a transaction executing in a particular mode failing.

5 is a flowchart of a method for concurrently processing hardware transactions and software transactions according to an embodiment of the present invention.

Figure 6 is a block diagram of a system according to an embodiment of the invention.

Detailed ways

In various embodiments, TM implementations are able to run different threaded transactions in different modes, and can switch modes for various reasons, including software conflict management or use of unsupported semantics or operations (such as nested transactions, retries, debugging or external transactions). A UTM system according to an embodiment of the present invention affords a large design space of execution modes with different performance, flexibility (semantic richness) and capacity considerations. These patterns are generally a combination of transactional, code generation, processor, and common language runtime (CLR) patterns. While this constitutes a large space, it is the specific patterns that are most relevant to this discussion that are presented.

Transactional memory code can execute in various transactional modes. Different transaction modes may require or at least benefit from different code generation strategies. Transaction execution modes include the following. Non-transactional (NT), which is a classical execution mode without isolation or failure atomicity, and thus does not require transactional logging or locking. Cache-Resident Non-Locking (CRNL) mode, also known as Cache-Resident Implicit Transaction Mode (CRITM), where the entire transaction read/write set is kept in cache memory and transaction conflicts are detected in hardware. In this mode, no login or other means are required, and no software compatibility lock is acquired. In one embodiment, CRNL thus only supports relatively small transactions whose data sets fit neatly in the processor's cache. Another mode is cache resident (CR) mode (also known as cache resident explicit transaction mode (CRETM)), where the entire transaction read/write set is stored in cache and transaction conflicts can be detected by hardware. In this mode, no login or other means are required, but a software compatibility lock is acquired. In various embodiments, CR (like the CRNL mode above) only supports relatively small transactions whose data sets fit perfectly in the processor cache.

Yet another mode is a software mode with Hardware Assisted Monitoring and Filtering (HAMF), which is a software mode that uses UTM monitoring facilities to detect transaction conflicts and for filtering. In this mode, a software compatibility lock is acquired. Another mode is the software mode with hardware assisted filtering (HAF), where UTM facilities are used for filtering only. Perform a software login in this mode and acquire a software compatibility lock. In general, these last two modes may be referred to as Hardware Assisted STM (HASTM) modes. Finally, Software Transactional Memory (STM) mode is a software-only mode that does not use UTM resources.

In order to support different transaction modes, specific chunks of source code can be converted into different binary code sequences. Naked (NK) refers to classic code that does not utilize specific transactional means. Transactional VTable (TV) is a code generation pattern that embeds indirect function calls for individual object field accesses to enable proper transactional logging and locking. A dispatch table (vtable) is used to dispatch different functions so that the generated code can be used to support various transaction modes.

The processor, in turn, can execute one of three basic modes with respect to the UTM nature of transaction-related monitoring and buffering. A first mode MB_ALL may be selected, where all loads and stores induce hardware monitoring and buffering. This is generally the easiest way to use UTM facilities, but can result in monitoring and buffering being applied to memory ranges that don't need it (like read-only state or the stack). A second mode, MB_DATA, may be selected where by default all loads and stores for which hardware transactions make memory accesses to segment registers are buffered/monitored. In this mode, all stack accesses have potentially unmonitored move (PUMOV) semantics, i.e., if a "load" reads a buffered cache line, it reads the buffered contents; if a "store" writes to If it writes to a non-buffered cache line, it behaves like a normal write; if it writes to a buffered cache line, both the buffered copy and the primary copy are updated. This mode provides fine-grained control over which the hardware buffers and monitors, and generally allows transactions to hold more useful data than MB_ALL mode, at the cost of more complex code generation decisions. A third mode MB_NONE may be selected, where no automatic buffering and monitoring of loads and stores takes place. Instead, the UTM ISA provides special instructions to induce buffering or monitoring of specific memory locations. Note that the execution mode only controls the instructions used to set the UTM state within the processor caches. Once a state is set in the cache, it is impossible to determine which mode was used to set that state.

Native code in the common language runtime (CLR) can be called in different modes including: non-transactional, which is the classic way in which native code from the CLR is called; implicit transactional mode, which occurs when calling the CLR code, while the current thread is executing a hardware transaction, and the processor is configured for MB_DATA; and explicit transaction mode, which occurs when calling CLR code while the current thread is executing a hardware transaction, and the processor is configured for MB_NONE, or While the current thread is executing a software transaction. Different ways of invoking the CLR determine what the native code needs to do in order to access the current state of the managed environment. In non-transactional and implicit modes, the CLR can directly read managed state without hindrance. In explicit transaction mode, the CLR can use helper functions to access managed state.

As an implementation background that can be used in an Unconstrained TM (UTM) system, it is instructive to look at example hardware that can be used for UTM transactions. In general, UTM transactions allow the use of hardware in conjunction with transactions that can be implemented entirely in hardware (ie, cache-resident transactions), as well as unconstrained transactions that are performed using a combination of hardware and software. Referring to FIG. 1 , an embodiment of a processor capable of executing multiple threads concurrently is illustrated. Note that processor 100 may include hardware support for hardware transactional execution. According to an embodiment of the present invention, combined with hardware transaction execution or independently, the processor 100 may also provide hardware support for the following: hardware acceleration of STM, separate execution of STM or a combination thereof, such as UTM. Processor 100 may be any type of processor, such as a microprocessor, embedded processor, digital signal processor (DSP), network processor, or other device that executes code. The illustrated processor 100 includes a plurality of processing units.

The physical processor 100 as illustrated in FIG. 1 includes two cores: cores 101 and 102 , which share access to a higher level cache 110 . Symmetric cores are illustrated, although processor 100 may include asymmetric cores, ie, cores having different configurations, functional units, and/or logic. Therefore, the core 102 exemplified as being the same as the core 101 will not be discussed in detail to avoid redundant discussion. Furthermore, core 101 contains two hardware threads 101a and 101b, while core 102 contains two hardware threads 102a and 102b. Thus, it is possible for a software entity, such as an operating system, to view processor 100 as four separate processors, ie four logical processors or processing units capable of executing four software threads concurrently.

Here, a first thread is associated with architectural state register 101a, a second thread is associated with architectural state register 101b, a third thread is associated with architectural state register 102a, and a fourth thread is associated with architectural state register 102b. As illustrated, the architectural state register 101a is replicated in the architectural state register 101b, so individual architectural states/contexts can be stored for both logical processor 101a and logical processor 101b. In one embodiment, the architectural status registers may include registers for implementing UTM transactions, such as the Transaction Status Register (TSR), Transaction Control Register (TCR), and Pop Instruction Pointer Register to identify the registers that can be used to process events accordingly during the transaction ( The location of pop handlers such as the abort of a transaction.

For threads 101a and 101b, other smaller resources such as instruction pointers and rename logic in rename allocator logic 130 may also be replicated. Some resources, such as reorder buffers in reorder/retirement unit 135, instruction translation lookaside buffer (ITLB) 120, load/store buffers, and queues, may be shared by partitioning. It is possible to fully share other resources, such as general internal registers, page table base registers, low-level data cache and data TLB 115, one or more execution units 140, and part of the out-of-order unit (out-of-order unit) 135.

As illustrated, processor 100 includes a bus interface module 105 to communicate with devices external to processor 100 , such as system memory 175 , a chipset, a north bridge, or other integrated circuits. Memory 175 may be dedicated to processor 100, or shared with other devices in the system. A higher-level or further-out cache 110 is to cache elements recently fetched from the higher-level cache 110 . Note that higher or further away refers to cache levels that increase or become farther away from one or more execution units. In one embodiment, higher level cache 110 is a second level data cache. However, higher level cache 110 is not so limited, as it may be associated with or contain an instruction cache. A trace cache, ie, a type of instruction cache, may instead be coupled after decoder 125 to store recently decoded traces. Module 120 may also contain a branch target buffer for predicting branches to be taken/fetched and an ITLB for storing address translation entries for instructions.

A decode module 125 is coupled to the fetch unit 120 to decode fetched elements. In one embodiment, processor 100 is associated with an ISA that defines/specifies instructions executable on processor 100 . Here, machine code instructions recognized by the ISA often contain parts of instructions called opcodes, which reference/specify instructions or operations to be performed.

In one example, the allocator and rename block 130 includes an allocator to reserve resources, such as register files, for storing instruction processing results. However, threads 101a and 101b may be capable of out-of-order execution, where allocator and renamer block 130 also reserves other resources, such as reorder buffers, in order to track instruction results. Unit 130 may also include a register renamer to rename program/instruction reference registers to other registers internal to processor 100 . Reorder/retirement unit 135 contains components such as the above-mentioned reorder buffer, load buffer, and store buffer to support out-of-order execution and subsequent in-order retirement of out-of-order executed instructions.

In one embodiment, scheduler and execution units block 140 includes a scheduler unit to schedule instructions/operations on execution units. For example, floating-point instructions are dispatched on execution unit ports that have floating-point execution units available. Also included are register files associated with the execution units to store information instruction processing results. Exemplary execution units include floating point execution units, integer execution units, jump execution units, load execution units, store execution units, and other known execution units.

A lower-level data cache and data translation buffer (D-TLB) 150 is coupled to one or more execution units 140 . A data cache is intended to store recently used/operated elements, such as data operands, which are likely to be kept in a memory coherent state. The D-TLB is to store recent virtual/linear to physical address translations. As a specific example, a processor may contain a page table structure to divide physical memory into multiple virtual pages.

In one embodiment, processor 100 is capable of hardware transactional execution, software transactional execution, or a combination or hybrid thereof. A transaction, which may also be referred to as a critical or atomic segment of code, contains a grouping of instructions, operations, or micro-operations to be executed as an atomic group. For example, instructions or operations may be used to demarcate transactions or critical segments. In one embodiment, these instructions are part of an instruction set, such as an ISA, that are recognizable by hardware of processor 100, such as the decoder described above. Often, these instructions contain operational codes (opcodes) or other portions of instructions that are recognized by the decoder during the decode stage, once compiled from the high-level language to hardware-recognizable assembly language.

Typically, during transaction execution, updates to memory are not made globally visible until the transaction is committed. As an example, a transactional write to a location may be visible to a local thread, however, in response to a read from another thread, the write data is not forwarded until the transaction containing the transactional write is committed. While the transaction is still pending, data items/elements loaded from and written to memory are tracked, as discussed in more detail below. Once a transaction reaches a commit point, if no conflicts are detected for the transaction, the transaction is committed and updates made during the transaction are made globally visible.

However, if the transaction is invalidated while it is pending, the transaction is aborted and possibly restarted without making the updates globally visible. Therefore, as used herein, pending transactions refer to transactions that have started to execute but have not yet been committed or aborted (ie, pending).

In one embodiment, processor 100 is capable of executing transactions using hardware/logic (ie, within a hardware transactional memory (HTM) system). When implementing HTM, there are many specific implementation details, both from an architectural and microarchitectural perspective; most of which are not discussed herein to avoid unnecessarily obscuring embodiments of the invention. However, some structures and implementations are disclosed for illustrative purposes. It should be noted, however, that these structures and implementations are not required, but may be supplemented and/or replaced by other structures with different implementation details.

In general, processor 100 may be capable of performing transactions within a UTM system that attempts to take advantage of both the STM system and the HTM system. For example, HTM is often fast and efficient for executing small transactions because it does not rely on software to perform all access tracking, conflict detection, validation, and transaction committing. However, HTMs are usually only capable of handling smaller transactions, while STMs are capable of handling transactions of unlimited size. Thus, in one embodiment, the UTM system utilizes hardware to perform smaller transactions and software to perform transactions that are too large for the hardware. As can be seen from the discussion below, hardware can be used to assist and accelerate software even when software is processing transactions. Pure STM systems can also be supported and accelerated using the same hardware.

As stated above, transactions involve transactional memory accesses to data items by local processing units within processor 100 and possibly by other processing units. In the absence of safety mechanisms in a transactional memory system, some of these accesses will likely result in invalid data and execution, ie, writes to data invalidate reads, or reads of invalid data. Accordingly, processor 100 may include logic that tracks or monitors memory accesses to and from data items in order to identify potential conflicts, such as read monitors and write monitors, as discussed below.

In one embodiment, processor 100 includes monitors to detect or track access and potential subsequent conflicts associated with data items. As one example, the hardware of processor 100 accordingly includes read monitors and write monitors to track loads and stores determined to be monitored. As an example, hardware read monitors and write monitors are to monitor data items at the granularity of data items regardless of the granularity of the underlying storage structure. In one embodiment, data items are constrained by a tracking mechanism associated at the granularity of the storage structure to ensure that at least the entire data item is properly monitored.

As a specific illustrative example, read monitors and write monitors include attributes associated with cache locations (such as locations within lower-level data cache 150) to monitor data from addresses associated with those locations. loads and stores to addresses associated with those cells. Here, upon a read event to an address associated with a cache location of data cache 150, the read attribute of the cache location is set to monitor for potentially conflicting writes to the same address. In this case, the write attribute operates in a similar manner to write events to monitor for potentially conflicting reads and writes to the same address. To facilitate this example, accordingly, the hardware is able to detect conflicts based on snooping of reads and writes to cache locations with read and/or write attributes set to indicate that these cache locations The location is monitored. Conversely, in one embodiment, setting read and write monitors or updating a cache location to a buffered state causes snoops, such as read requests or requests for read ownership, that take into account differences with monitored addresses in other caches to be detected. conflict.

Therefore, based on this design, different combinations of the monitored coherency state of the cache line and cache coherency requests lead to potential conflicts, such as the cache line holding the data item being in the shared read monitoring state, and the snoop indicating a write to the data item ask. Conversely, a cache line holding a data item in a buffered write state and an external snoop indicating a read request to that data item may be considered a potential conflict. In one embodiment, to detect this combination of access requests and attribute states, snoop logic is coupled to conflict detection/reporting logic (such as monitors and/or logic for conflict detection/reporting) and status registers to report these conflict.

However, any combination of conditions and situations may be considered invalid for a transaction, which may be defined by an instruction, such as a commit instruction. Examples of factors that may be considered for uncommitted transactions include detecting conflicts on memory locations accessed by the transaction, loss of monitor information, loss of buffered data, loss of metadata associated with data items accessed by the transaction, and detection of other invalid events such as interrupts, Ring transition or explicit user instruction (assuming restarted transaction cannot continue).

In one embodiment, the hardware of processor 100 is to store transactional updates in a buffered manner. As stated above, transactional writes are not made globally visible until the transaction is committed. However, native software threads associated with transactional writes can access transactional updates for subsequent transactional access. As a first example, a separate buffer structure is provided in the processor 100 to hold buffered updates that can be provided to local threads but not to other external threads. However, including separate buffer structures can be expensive and complex.

In contrast, as another example, a cache such as data cache 150 is used to buffer these updates while providing the same transactional functionality. Here, cache 150 is able to hold data items in a buffer coherency state; in one case, a new buffer coherency state is added to a cache coherency protocol, such as the Modified Exclude Shared Invalidation (MESI) protocol to form the MESIB protocol. In response to a local request for a cached data item, ie, to save the data item in a cache coherency state, the cache 150 provides the data item to the local processing unit to ensure internal transaction ordering. However, in response to external access requests, a miss response is provided to ensure that data items updated by a transaction are not made globally visible until committed. In addition, when a line of cache 150 remains in a buffer coherency state and is selected for eviction, buffered updates are not written back to higher-level caches—buffered updates are not diffused through the memory system, i.e., buffered updates are not Updates are globally visible until after committing. On commit, the buffered line is transitioned to the modified state to make the data item globally visible.

Note that the terms internal and external are often relative to the perspective of threads or processing units that share caches associated with transaction execution. For example, a first processing unit for executing a software thread associated with transactional execution is called a native thread. Thus, in the discussion above, if a store to or a load from an address previously written by the first thread is received (which causes the cache line for that address to remain at cache coherent state), the buffered version of the cache line is provided to the first thread because the first thread is a native thread. In contrast, a second thread may execute on another processing unit within the same processor, but the second thread is not associated with the transaction execution-external thread responsible for keeping the cache line in a buffered state; thus, from the second A thread's load or store to an address misses the buffered version of the cache line, and normal cache replacement is used to retrieve the unbuffered version of the cache line from higher-level memory.

Here, internal/local threads and external/remote threads execute on the same processor, and in some embodiments internal/local threads may execute on separate processing units within the same core of the processors that share access to the cache and external/remote threads. However, the use of these terms is not limited thereto. As stated above, local may refer to multiple threads that share access to the cache, rather than being specific to a single thread associated with transaction execution, while external or remote may refer to threads that do not share access to the cache thread.

As stated above initially with reference to FIG. 1 , the architecture of processor 100 is purely illustrative for purposes of discussion. For example, in other embodiments, UBT hardware may be implemented for a processor with a simpler in-order execution processor design, which may not include complex rename/allocators and reorder/retirement units. Similarly, the specific example of translating data addresses used to reference metadata is also exemplary, as any method of associating data with metadata in separate entries of the same memory may be utilized.

Turning to FIG. 2 , an embodiment of storing metadata of a data item in a processor is illustrated. As depicted, metadata 217 for data item 216 is stored locally in memory 215 . Metadata includes any properties or attributes associated with a data item 216 , such as transactional information related to the data item 216 . Some illustrative examples of metadata are included below; however, the disclosed metadata examples are purely illustrative. As such, metadata location 217 may hold any combination of information and other attributes of data item 216.

As a first example, the metadata 217 contains a reference to the backup or buffer location of the data item 216 if the transactionally written data item 216 has been previously accessed, buffered, and/or backed up within the transaction. Here, in some implementations, backup copies of previous versions of data items 216 are kept at different locations, and thus, metadata 217 includes addresses of backup units or other references to backup locations. Alternatively, metadata 217 itself may serve as a backup or buffer location for data item 216 .

As another example, metadata 217 includes filter values for expediting repeated transactional access to data item 216 . Often, access barriers are enforced on transactional memory accesses to ensure consistency and data validity during execution of transactions in software. For example, before a transaction load operation, a read barrier is performed to perform read barrier operations, such as testing whether the data item 216 is unlocked, determining whether the current read set of the transaction is still valid, updating the filter value, and logging the version value in the transaction's Read in the collection to allow subsequent validation. However, the same read barrier operation may not be necessary if a read at that location has already been performed during transaction execution.

Therefore, one solution consists of using a read filter to store a first default value to indicate that the data item 216 was not read during the transaction execution, or therefore the address was not read during the transaction execution, and also store a second access value to indicate that the data item 216 has been accessed while the transaction is pending, or therefore the address has been accessed while the transaction is pending. Essentially, the second access value indicates whether the read barrier should be accelerated. In this case, if a transactional load operation is received, and the read filter value in metadata location 217 indicates that data item 216 has been read, then in one embodiment omit-do not perform-read barrier to pass no Perform unnecessary redundant read barrier operations to speed up transaction execution. Note that write filter values can operate in the same manner with respect to write operations. However, the individual filter values are purely illustrative, as in one embodiment a single filter value is utilized to indicate whether an address has been accessed - whether writing or reading. Here, metadata access operations for metadata 217 that both load and store check 216 utilize a single filter value, as opposed to the above example (where metadata 217 contained separate read and write filter values) . As a specific illustrative embodiment, four bits of metadata 217 are assigned to read filters to indicate whether read barriers are to be accelerated with respect to the associated data item, and to write filters to indicate whether write barriers are to be accelerated with respect to the associated data item , assigned to undo filters to indicate that undo operations are to be accelerated, and to miscellaneous filters to be exploited in any way by software as filter values.

A few other examples of metadata include: an indication, representation or reference of a handler address (generic or specific to the transaction associated with the data item 216), irrevocable/difficult to cancel of the transaction associated with the data item 216 properties of data item 216, loss of monitoring information for data item 216, collision detected for data item 216, address of a read set associated with data item 216 or address of a read entry within a read set, data item 216 The previously logged version of the data item 216, the current version of the data item 216, the lock that allows access to the data item 216, the version value of the data item 216, the transaction descriptor of the transaction associated with the data item 216, and other known transaction-related descriptive information. Also, as mentioned above, the use of metadata is not limited to transactional information. As a corollary, metadata 217 may also include non-transactional information, properties, attributes, or states associated with data item 216 .

With this background for a UTM system, the next consideration of how to initiate a transaction will be discussed. When threads enter a transaction, they transition to one of the TM execution modes. If no thread is in any type of STM mode (in general, any STM mode is called *STM mode), the current thread can use the implicit mode CRITM. Many threads can thus be in CRITM mode. If the thread overflows the constrained capacity of the hardware or performs some semantic action that cannot be done in the current mode, the CRITM transaction will fall back and be re-executed in one of the *STM modes. Once any thread is in *STM mode, all other threads must leave CRITM mode (return) and re-execute in an STM lock-respecting mode (such as CRESTM). There are several possible implementation variant combinations such as CRITM and CRESTM. For discussion purposes, this article will use this combination of patterns.

Table 1 compares these two example transactional execution patterns to each other and to a modern common non-transactional pattern.

Table 1

execute variant describe transaction mode transaction compatible code generation mode CPU mode CLR mode ordinary Non-transactional NT N/A NK MB_NONE Non-transactional CRITM Cache resident, implicit mode, no software lock CRNL CRNL NK MB_DATA transaction implicit CRES™ cache-resident, explicit mode, using software locks and transactional vtables CR CR, HAMF, HAF, STM TV MB_NONE transaction explicit

Inevitably, some transactions will fail, eg due to loss of buffered data or conflicts, and such transactions will abort. In some cases, the mode of a transaction may change at re-execution time. Transactions may "fall back" to a lower performance mode or "upgrade" to a higher performance mode. That said, not all modes are equal from a performance standpoint. In general, CRITM is the best performing execution mode because it avoids the overhead of dealing with software locks. The next best mode for performance is CRESTM, then HASTM, and then STM. STM and HASTM schemas are equivalent in the functionality they provide, thus STM is used to represent both schemas in the following discussion.

However, all transactions cannot run in CRITM mode because it only operates on cache-resident transactions. Since CRESTM mode is also limited to cache-resident transactions, any transaction that is not cache-resident needs to run in STM mode. CRITM mode is not compatible with STM mode, therefore, once a transaction starts operating in STM mode, no transaction can run in CRITM mode. Thus, at this point, all cache-resident transactions are shifted to CRESTM mode.

Broad constraints on which mode to execute transactions in can be summarized as follows: all transactions start in CRITM mode, however, if STM transactions are running, all transactions start in CRESTM mode. If the transaction overflows the cache, it wraps around and resumes execution in STM mode. If a transaction is executing in STM mode, all CRITM transactions are destroyed and execution restarts in CRESTM mode.

In one embodiment, there are some additional constraints around support for the "retry" primitive: If a transaction uses the "retry" primitive, it can only execute in STM mode, because CRITM and CRESTM do not support waits Retry. If any transaction in the system is waiting for a "retry", then all other transactions need to execute in CRESTM mode or STM mode, this is because CRITM does not support notifications.

Referring now to FIG. 3 , there is shown a flowchart of a method for selecting a transaction execution mode for executing a TM transaction according to an embodiment of the present invention. In one embodiment, the method 300 can be implemented by the runtime of the UTM system. As seen, Figure 3 may begin by determining whether other transactions are active in the system (diamond 310). This is done because some hardware transaction modes are not compatible with STM transactions. If no other such transactions are active, control passes to block 320 where the transaction may begin in the highest performance mode available. In the context described here, the highest performing mode can be a hardware implicit transaction mode (such as CRITM). Of course, in different implementations different or modified modes may be available.

If instead at diamond 310 it is determined that other transactions are active, then control passes to diamond 325 where it can determine whether any of these transactions are in STM mode. If so, a new transaction may begin in the highest performing mode consistent with the STM mode (block 330). For example, in the implementations discussed herein, this highest compatibility mode may be a hardware-explicit mode (eg, CRES™) in which hardware-assisted transactions can reside entirely within processor caches, but obey software locks.

Accordingly, the transaction begins and the operation continues. However, it can be determined whether overflow has occurred (diamond 335). That is, since all transactions may begin in some type of cache-resident hardware-assisted mode, it is possible that there will not be enough cache space to handle a complete transaction. Accordingly, if it is determined at diamond 335 that an overflow has occurred, control may pass to block 375, which will be discussed further below. If instead the transaction does not overflow, it may next be determined whether the transaction has completed (diamond 340). If not, continuing execution may occur. If the transaction has completed, control passes to diamond 350 where it can be determined whether the hardware nature of the transaction has been maintained. That is, before a transaction commits, various hardware properties (such as buffering, monitoring, and UTM properties of metadata) can be checked to determine that they are still alive without penalty. If not, then some loss of a hardware nature has occurred and control passes to 360 where the transaction is aborted. Otherwise, if the transaction completes successfully, and the hardware properties remain unchanged, then control can pass to block 355 where the transaction is committed.

Still referring to FIG. 3 , if instead during execution of the cache resident transaction, the transaction overflows the cache (as determined at diamond 335 ), then control passes to block 375 . There, the transaction can be rolled back and re-executed in STM mode. While executing in STM mode, it may be determined whether a semantic has been violated (diamond 380). If so, control passes to block 382 where the transaction can be turned back and re-executed in a lower performance mode (eg, pure STM mode). Similar operations may occur (blocks 385, 390, 392, 395) relative to determining whether a transaction is complete and whether it can be successfully committed or needs to be aborted, as discussed with respect to hardware-assisted transactions. Although described with this particular implementation in the embodiment of FIG. 3, it is understood that the control of a given mode in which transactions are performed may vary in different implementations.

Thus, the method of FIG. 3 generally illustrates how to determine the appropriate mode to begin a transaction. However, during a transaction, failures may occur for other reasons than cache overflows or STM failures. In various embodiments, a back-off and upgrade mechanism may be implemented to determine in which mode a new (or re-executed) transaction should execute so that the constraints described above are met and the system achieves optimal performance. Table 2 below shows the set of reasons for destroying (terminating) a transaction. The first column in Table 2 describes the various reasons for a destructible transaction, and the second and third columns describe the new mode in which a previously pending CRITM or CRESTM transaction will be re-executed, respectively. A cell left blank indicates that the transaction will not be destroyed for the given reason.

Table 2

the reason CRITM CRES™ the Another transaction contains "retry" CRES™ the the Current transaction contains "retry" STM STM the Requires open nested transactions/full suppression STM STM the cache capacity exceeded STM STM the Closed nested flattened transaction throws exception STM STM the Code needs to be JITized CRITM CRI™, CRES™ the A transaction destroys itself (e.g. when modifying object headers while passthrough CAS is not available) CRITM, STM CRITM, CRESTM, STM the GC delays the thread executing the current transaction CRITM CRI™, CRES™ the One or more STM transactions started CRES™ the 0 All STM transactions are terminated the CRITM 1 loss monitoring CRITM CRI™, CRES™ 2 loss buffer CRITM CRI™, CRES™

Note with respect to Table 2 that the first priority will be to re-execute in CRTIM mode. However, if a transaction requires functionality not available in CRITM mode or an STM transaction is in progress, the transaction will be re-executed in CRESTM mode. The decision to terminate a CRESTM transaction for this reason will be based on heuristics. Also, no CRITM transactions should be running at this point.

Note that there may be leeway in the design options shown in Table 2. For example, it is possible to design patterns that are cache-resident but still provide software-based atomicity of failures. This pattern can be used to resolve nested transaction failures.

Referring now to FIG. 4 , shown is a flowchart of a method of handling a mode switch as a result of a failure of a transaction executing in a particular mode. In one embodiment, the method 400 of FIG. 4 may be implemented by a pop handler that receives control when a transaction in the first mode fails. As seen, method 400 may begin by determining why a transaction failed (block 410). This determination can be made based on various information received. As an example, the TCR and/or TSR information may indicate the reason for the failure. Similarly, the transaction control block can also indicate the reason for the failure. Still further, in other implementations, other ways of obtaining this information may be used.

Still referring to FIG. 4 , in general, different recovery paths, such as different paths to re-execute the transaction, may be selected based on the reason for destroying the transaction. Additionally, while described and shown in a specific order in the embodiment of FIG. 4, it is to be understood that this is for ease of discussion and that various determinations made in various implementations may occur in different orders (and in different ways) . As seen, at diamond 415, it can be determined whether the current transaction mode does not support the required functionality. Examples of such unsupported functionality are discussed below. If this is determined to be the cause of the transaction failure, control may pass to block 420 where selecting another mode to support this functionality may occur. Accordingly, the transaction can be re-executed after the mode switch to this new mode.

Yet another reason for destroying a transaction may be that the transaction destroys itself, as determined at diamond 425 . If so, the number of times the transaction has destroyed itself can also be determined. This number can be compared to a threshold (diamond 430). If the number is above this threshold, indicating that the transaction continues to destroy itself, the transaction may switch to a different mode (block 435). If the threshold is not met, re-execution may occur in the same mode (block 440).

Yet another reason for destroying a transaction may be whether external system activity caused the destruction. If this is determined (at diamond 450), it may be determined whether this external activity was an increase in the number of pending STM transactions (diamond 455). If so (and the current transaction is a hardware implicit mode transaction), the transaction may be re-executed in hardware explicit mode (block 460). If instead of an increase in the number of STM transactions, it is determined that there is actually a decrease in pending STM transactions (as determined at diamond 462), then a decision can be made as to whether to restart pending hardware explicit in hardware implicit mode. Formal transaction is determined because this is better in performance (block 465). The different considerations for making this determination are discussed further below. If the change in the STM transaction was not external system activity, the transaction can be re-executed in its current mode (block 470). Similarly, if there is some other reason for the transaction to fail, such as due to a conflict or other such reason, the transaction can be re-executed in the same mode (block 480). While shown with this particular implementation in the embodiment of FIG. 4, understand that the scope of the present invention is not limited in this respect.

The reasons described above in Table 2 and discussed in Figure 4 can be classified into four broad categories. For each category, fallback and upgrade mechanisms are described. The first failure cause category may be functionality not supported by a given execution mode. Reasons 1-5 fall into this bucket of CRITM. For CRESTM, reasons 2-5 fall into this bucket. These reasons are integral to transactions and expose limitations of the current execution model. Thus, a re-execution of a transaction should not be in the same mode in which it was executed earlier, and instead a switch to a mode with the required support may occur. To support this functionality, persistent writes can be performed on the transaction context (when the transaction is destroyed), specifying the mode that should be used when re-executing the transaction.

A second failure cause category may be where a transaction commits suicide (destroys itself). Reasons 6 and 7 fall into this category. For reason 6, the transaction can be rolled back, compilation of the required blocks can be performed (eg, just in time (JIT)), and then the transaction can then be re-executed in the same mode. This is because JIT'ing functions is very expensive, so the overhead of going back and re-executing will not be noticeable. For reason 7, the transaction can be re-executed in the same schema. This is done because first, the watched/buffered line may not contain the object header next time (next time around), and second, there is no way of knowing that a watch (or buffer) penalty occurred because of writing to the object header. In some implementations, precautions may be provided for the case where a transaction keeps destroying itself because of writing to an object header. As an example, a rule can be set that any CRITM/CRESTM transaction that is re-executed N (greater than some predetermined threshold) times will be re-executed in STM mode.

A third failure cause category may be that system activity outside the current transaction destroys it. Reasons 8-10 fall into this category. For reason 8, even if the transaction is rolled back due to a garbage collection (GC) stall, there is no reason not to retry in the same mode, and thus the transaction can be re-executed in the mode in which the transaction was executed earlier. For reason 9, a global counter of currently running STM transactions may be maintained in memory. Whenever a new STM transaction starts, this counter can be incremented (eg, using InterlockedIncrement), and when the STM transaction rolls over/aborts/commits, a corresponding decrement can occur on the counter (eg, using InterlockedDecrement). CRITM transactions can also perform watch reads on this global counter so that whenever an STM transaction starts, all CRITM transactions are destroyed and re-executed in CRESTM mode.

CRITM is the best performing mode, and thus attempts to avoid actively destroying CRITM transactions. One solution could be that whenever an STM transaction is about to start, it first checks to see if the system currently contains a running CRITM transaction. If the system does contain CRITM transactions, STM transactions can be controlled to wait a finite amount of time before starting. This wait time may allow currently running CRITM transactions to complete execution without delaying STM transactions too much.

For reason 10, whenever all STM transactions in the system are aborted, an implementation could be to destroy all CRESTM transactions and restart them in CRITM mode. However, if a CRESTM transaction is to complete before destroying it, a spin mechanism may be implemented. The final decision here will be based on CRESTM overhead vs. CRITM: if on average, CRESTM transactions are slower than 1/2 the speed of CRITM transactions, then it will be more performant to destroy CRESTM transactions and restart them in CRITM mode , otherwise, it will be more performant to continue in CRESTM mode. In yet other implementations, it may be possible to transition a running transaction from CRES™ mode to CRI™ mode.

Active read-write (r-w) or write-write (w-w) conflicts can occur on buffer/monitor blocks. Reasons 10 and 11 fall into this category. If a transaction is destroyed because it lost watch or buffer for a cache line, it can be retried in the same mode as earlier. One concern here is that if a new transaction accessing a cache line destroys an older transaction, the old transaction can destroy the new transaction when it restarts. This can lead to a ping-pong effect in which no transaction is completed. Contention management logic can be used to handle this situation.

In some implementations, when a transaction is about to start or restart execution, the optimization is: if the only reason a transaction needs to start in CRESTM mode is "the system contains one or more STM transactions", the spin mechanism can be used to retry before waiting. If after the wait, the STM transaction is still running, the current transaction can be started in CRESTM mode, otherwise the transaction can be started in CRITM mode and CRESTM overhead can be avoided. Similar logic can be applied to any CRES™ transaction that is restarted. Thus, in the above discussion, there is a caveat when a transaction should be restarted in the same mode: if that mode is CRESTM, it can first be determined whether the transaction can run in CRITM mode.

For exposition purposes, CRESTM uses TV code generation style with exception-based return, while CRITM uses NK code generation style with longjmp-based return.

原语取

，独特的小密集整数ID标识词汇事务(lexical transaction)。这个ID用于索引到含有关于词汇事务的竞争管理信息的全局数据结构中。这个结构也可用于存储指示在哪个执行模式开始事务的永久性信息。该原语可将这个信息设置为事务的属性。 Consider now how lexical atomic chunks (generally called "s") should be transformed. (For the purposes of this discussion, assume that all state about the transaction is maintained within the current transaction object, ignoring the transaction context.)

primitive fetch

, a unique small dense integer ID identifying a lexical transaction. This ID is used to index into a global data structure containing contention management information about lexical transactions. This structure can also be used to store persistent information indicating in which execution mode a transaction was started. This primitive can set this information as an attribute of the transaction.

The three conversions of code blocks to TM support codes are provided below in Table 3-5. The pseudocode of Table 3 assumes that CRESTM and STM are the only execution modes, the pseudocode of Table 4 assumes CRITM is the only execution mode, and the pseudocode of Table 5 attempts to consider all three possibilities.

If CRESTM and STM are the only modes of execution, the conversion is illustrated in the pseudocode of Table 3.

table 3

。

.

原语创建事务。其SiteID将确定一组初始属性，包括当前使用的事务vtable。在所有模式中，可将有效的(live)本地变量(或者就是可在事务中修改的那些)保存到堆栈位置(stack locations)。在那之后，如果当前执行模式正在使用硬件加速，则开始硬件事务。事务执行。如果它转返，则到达catch(捕获)语句，这是因为发出了基于处理机异常的转返。可首先恢复本地变量值。这是必要的，而无论处理机(HandleEx)判定重新执行(通过返回)还是整理并再次抛出中止用户执行-本地变量在捕获抛出的异常的捕获语句中可能是有效的。如果处理机判定重新执行，则它可改变事务的属性“curtx”。例如，它可将事务vtable改变成使用STM而不是CRESTM。 As seen in Table 3, one can use

Primitives create transactions. Its SiteID will determine an initial set of attributes, including the transaction vtable currently in use. In all modes, valid (live) local variables (or simply those that can be modified within a transaction) can be saved to stack locations. After that, a hardware transaction is started if the current execution mode is using hardware acceleration. Transaction execution. If it returns, a catch statement is reached because a return based on a handler exception was issued. Local variable values can be restored first. This is necessary regardless of whether the handler (HandleEx) decides to re-execute (by returning) or clean up and throw again to abort user execution - the local variable may be valid in the catch statement that catches the thrown exception. If the handler decides to re-execute, it may change the transaction's attribute "curtx". For example, it can change the transaction vtable to use STM instead of CRESTM.

If CRITM is the only execution mode, the conversion is illustrated in the pseudocode of Table 4.

Table 4

操作不仅保存堆栈指针、基本指针和指令指针(ESP)、(EBP)和(IP)，而且保存所有被调用者保存寄存器(callee-save register)。它保存的IP可就在对的调用之后，因此，就像setjmp/longjmp，操作可重新开始，就好像从该调用返回一样。收回器(ejector)将恢复保存的寄存器值，并跳到保存的IP。注意，S的“裸”变换不精确等于S，这是因为当控制流程离开S时，可能存在一些显式动作以提交事务。由于发生基于长跳的转返，因此仅正在抛出的用户级异常到达捕获语句。与在CRESTM中一样，恢复保存的本地变量(出于相同原因)。HandleEx将深度克隆该异常，中止硬件事务，并且然后重新抛出克隆的异常。在第一执行时，curtx.IsRexec()为假，因此不恢复本地变量。在给定事务实例的第二且随后的执行上，这个条件为真，并且由此每次都恢复本地变量。这是除恢复捕获语句中的本地变量之外还有的，这是由于利用longjmp的重新执行不通过捕获处理机。当收回器进入重新执行时，可在事务数据结构中记录有关应该在其中执行该重新执行的模式的判定。虽然这可在收回器中进行，但如果在此执行大量代码，则可发生堆栈溢出。另一备选是使收回器在事务数据结构中记录该判定将基于的相关数据，并在这个IsRexec()测试之后判定和安装新执行模式-表4中利用注释示出了这种可能性。 As seen in Table 4, for the reasons discussed above, assuming

The operation saves not only the stack pointer, base pointer, and instruction pointers (ESP), (EBP), and (IP), but also all callee-save registers. The IP it saves can be on the right So, like setjmp/longjmp, the operation can restart as if returning from that call. The ejector will restore the saved register value and jump to the saved IP. Note that the "naked" transformation of S is not exactly equal to S, since there may be some explicit action to commit the transaction when control flow leaves S. Because of the long-jump-based return, only the user-level exception being thrown reaches the catch statement. As in CRESTM, restore saved local variables (for the same reason). HandleEx will deep clone the exception, abort the hardware transaction, and then rethrow the cloned exception. On the first execution, curtx.IsRexec() is false, so local variables are not restored. On the second and subsequent executions of a given transaction instance, this condition is true, and thus the local variable is restored each time. This is in addition to restoring local variables in the capture statement, since re-execution with longjmp does not go through the capture handler. When the evictor enters re-execution, a determination can be recorded in the transaction data structure as to the mode in which the re-execution should be performed. While this can be done in a retractor, a stack overflow can occur if a large amount of code is executed there. Another alternative is to have the evictor record in the transaction data structure the relevant data on which this decision will be based, and after this IsRexec() test decide and install the new execution mode - this possibility is shown with comments in Table 4.

Combination transformations of the possibilities assuming CRITM, CRESTM and STM modes are illustrated in the pseudocode in Table 5.

table 5

Regarding the pseudocode of Table 5, consider starting in CRITM mode, encountering a contention or resource constraint, making a contention management decision to re-execute in CRESTM, encountering a contention or resource constraint again, and thus re-executing again in STM (this time successfully ) transaction execution.

相关联的信息将确定事务能首先在CRITM模式中执行。在所有模式中，有效并且修改的本地变量首先被保存到堆栈帧中的映像变量(shadow variables)(如果这是最高级事务则持久这样做)。可设置该事务使得LongjmpRollback返回真，因此它将进行setjmp-equivalent。如前面所论述的，如果这是重新执行(在这个示例中不是重新执行)，则可恢复保存的本地变量。然后开始硬件事务，并执行S的STM变换的CGSTYLE_NK版本。CRITM执行损失监视或缓冲，并进入收回器，以及当前硬件事务由此被中止。 and

The associated information will determine that the transaction can be executed first in CRITM mode. In all modes, valid and modified local variables are first saved to shadow variables in the stack frame (doing so persistently if this is a top-level transaction). This transaction can be set so that LongjmpRollback returns true, so it will be setjmp-equivalent. As previously discussed, if this is a re-execution (not a re-execution in this example), the saved local variables may be restored. The hardware transaction is then started, and the CGSTYLE_NK version of the STM transform of S is executed. The CRITM performs loss monitoring or buffering, and enters the evictor, and the current hardware transaction is thereby aborted.

The transaction may be subject to contention management decisions, which are re-executed in CRESTM mode. It changes some attributes of the transaction, including the transaction vtable. It then restores the saved register values and jumps to the saved IP, thus starting over, as if SaveSetjmpState just returned. (As discussed earlier, it could do less race management in the evictor if desired, and perform the setup of the new execution mode after the "IsRexec()" test.)

A new hardware transaction is started and a CGSTYLE_TV transformation of the code is performed. At some point, a loss of monitoring or buffering may be detected and an internal ReExecuteException raised, from which the exception handler is reached and the local variables restored from their mirrored copies. The saved local variable value is restored and HandleEx is called, which determines that the exception generated is a ReExecuteException. At some point, or earlier, before the exception is raised, or at this point, a race management decision is made that determines the next mode of execution, and the attributes of the current transaction are adjusted appropriately. In this case, it is assumed that the determination is re-executed in the STM mode. Since re-execution has occurred, HandleEx returns, rather than respawning, and thus control returns to label L again. On this execution, StartHWTx is a no-op, since hardware acceleration does not use the subject's CGSTYLE_TV transform, and STM barriers are performed. The transaction succeeds and is committed.

Table 6 below provides a comparison of various properties performed by a TM according to an embodiment of the invention.

Table 6

nature CRITM CRES™ HASTM Use hw metadata for filtering N N Y buffer write Y Y N monitor read Y Y Y keep a log N N Y Requires data to be cache resident Y Y N compatibility CRITM CRESTM, HASTM, STM CRESTM, HASTM, STM Support retry N N Y Support Notice N Y Y switchback mechanism long hop based exception based exception based Request TV code generation N Y Y

Thus, in various embodiments, a switching state machine can be used to execute transactions in multiple modes, including implicit cache-resident and explicit cache-resident HASTM and STM. For example, a transaction may start at CRITM, and then switch on overflow. In addition, when a thread enters the STM lock mode, other threads' transactions can be switched. Switching modes on rich semantics or features such as deterministic commit commands or retries can occur, and switching back to CRITM mode can occur when no STM threads remain.

Embodiments may use UTM support for explicit monitoring and buffering control instructions to efficiently perform smaller simple transactions without login and image copy buffering, while correctly aligning with unconstrained disclosure and privatization using software locking and login rules STM/HASTM transactions exist at the same time. Thus, the UTM system can allow fast cache-resident transactions to execute alongside STM transactions (even those on software threads that are not scheduled to the core). In the hardware implicit mode, accesses to internal run-time data structures and stacks may not necessarily be added to cache management transaction read and write sets, specifically for managed code. In CRESTM's non-implicit mode, using (by software) cache monitoring and buffering instruction facilities, transactions can monitor and buffer only user data that requires transactional semantics. The stack, data accesses that occur during sojourn in CLR helper code, or the CLR runtime itself do not use cache monitoring and buffering, and thus do not themselves act on eviction-based (capacity miss) caches. Cache resident transaction aborted.

As mentioned above, transactions are executed in various hardware accelerated modes like CRITM and CRESTM before falling back to HASTM or STM due to cache capacity or using semantics not implemented in hardware. For CRESTM, a cache-resident STM is provided that adheres to an explicit transactional memory model, which is interoperable with both STM transactions and CRITM transactions. Then, when a fallback to STM occurs for one transaction, the others can switch to CRESTM, but not all transactions necessarily go all the way to the most ineffective STM mode. Similarly, upgrades can occur gradually, with the first STM transaction completing while the rest of the system is working in CRESTM mode, and then the CRESTM transaction completing while the rest of the system is already in the most efficient CRITM mode.

In the case of using an accelerated memory barrier according to an embodiment of the present invention, by eliminating the overhead of writing logs, eliminating the need for hardware transactions to allocate timestamps from the global pool, increasing the number of transactions between CRESTM transactions and between CRESTM transactions and STM transactions Concurrency and adaptive response to competition between CRESTM transactions and STM transactions to improve execution characteristics.

Object headers (OH) can be used within the CRITM and CRESTM transaction modes. Because not all uses of OH can be switched to TM, and since the hardware cannot support open nested transactions, these modes can interact with the Compare and Save (CAS) protocol on OH used by other parts of the system. Certain changes to OH must be persistent. In this regard, hash codes (HC) are the most notable. The requirement for a stable HC of the object also implies that changes to the SyncBlockIndex (SBI) are also persistent. For CRESTM, suppression and re-entrancy are not required because transactions do not use transactional read or write access to SyncBlock management data structures. Objects created inside a transaction are not globally visible, therefore, modifications to their titles are also buffered.

The interoperability of CRESTM with STM provides a lock compliance hardware model in the global version clock system. The following primary assumptions are made. A global version clock scheme is used to provide public correctness, some form of commit ticket protocol and buffered writes are used to provide private correctness, a write lock is acquired at encounter time (e.g. via the OpenForWrite() function), and Favorable reads are verified at commit time after the commit ticket has been taken.

Global version clock integration can be achieved by having hardware transactions keep a write log and update metadata (such as transaction records or transaction metadata words (TMW)) with write variables (WV) during the appropriate phase of commit. The hardware algorithm is as follows: start a hardware transaction, and perform a write barrier before writing. In one embodiment, for o.tmw="locked by me", this barrier may be a buffered write, and the object's address is logged in the transaction local write log, and the TMW is monitored. A read barrier is performed before each read where the lock bit is checked and the transaction is aborted if there is a lock (unless "locked by me") and TMW can be monitored. After the body is complete, the WV for this transaction can be obtained using logic in the suppression area. Then, each o.tmw can be updated for WV with buffered writes using the list of written addresses, and the hardware transaction committed. Thus, after all write locks have been acquired, WV is acquired. In hardware mode, "obtaining a write lock" means that there is a watch on the appropriate TMW.

This scheme may have poor performance due to the need to keep a write log. In some embodiments, it may be possible for locks to be observed without a write log, and thus the need to keep a write log may be eliminated. The optimization of the global version numbering implementation can be made using two assumptions. First, assume that there will be far more CRESTM transactions than STM transactions; and second, assume that actual data collisions are rare. The first assumption is motivated by the fact that rolling back one transaction into STM does not force other transactions to move into STM. Fallbacks into STM are expected to be rare, and thus "victims" will be individual transactions while others continue to execute in CRESTM. In a sufficiently parallel system, this means that there will be many more CRESTM transactions than STM transactions. The second assumption is workload dependent, but generally a quality proof of good design and thus predominates in successful programs.

A CRESTM transaction uses a public version number, represented by a hardware global version number (HGV), to stamp any object it is modifying. STM transactions guarantee that HGV is strictly greater than the software-based global version number (GV), so that any "writes" made by concurrent CRESTM transactions correctly appear as conflicts. The HGV can be increased in batches so that maximum concurrency is guaranteed as long as no data conflicts occur. Data conflicts are handled by regressing to the most basic strategy and then gradually restarting again on a more aggressive path.

In order to be lock-observing without writing to the log, the following operations can occur in hardware transactions. Assume both GV and HGV start at 0. Each hardware transaction may first set a stamp value (SV)=HGV. HGV is read with watch, so any write to it will destroy all hardware transactions. A write barrier may be performed before writing, eg using buffered writing for o.tmw=SV, and monitoring TMW. A read barrier may be performed before each read, where the lock bit is checked and the function is aborted if a lock exists, the TMW is monitored, and the transaction commits with the ticket protocol. Thus, for hardware transactions, no log of temporarily changed objects is kept; instead, temporarily changed objects are stamped with HGV; and if the transaction commits, the timestamp becomes permanent along with the data change.

Each software transaction may set a read variable (RV) = GV. If (HGV<RV+1) compare and set (CAS)(HGV, RV /*predicted*/, GV+l/*new*/). Now, the hardware is being stamped into the future, and all current hardware affairs are destroyed. When a transaction is ready to commit, transaction execution is normal to STM, such as locks acquired at encounter time, etc. The write variable (WV) is set such that it is equal to GV after incrementing. The increment to the GV ensures that if this transaction is rolled back and then re-executed, any outstanding hardware transactions are destroyed and stamped into the future. Use RV to validate read sets, and then use WV to release all write locks. Write locks are not held, but the downside is that every time a software transaction starts after another software transaction has completed (for commit or rollback), then all hardware transactions are destroyed. This behavior can be mitigated by making the HGV advance more than 1 at a time. If it advances by 10, for example, after seeing some other software transaction complete, 10 more software transactions can start before all hardware transactions are destroyed.

Thus, when a software transaction starts, it samples GV and stores the retrieved value in local variable RV. It continues to read and write as specified by the program. When a transaction is ready to commit, GV is first checked to determine whether the increment will bring GV up to the value of HGV. If so, the HGV is incremented by an amount of B (its value will be discussed below).

These rules provide the security necessary to ensure that conflicts are always detected. In general, conflict detection can occur as follows: CRESTM-to-CRESTM conflicts are detected at the hardware level as conflicts on raw data accesses; CRESTM-to-CRITM conflicts are also detected at the hardware level as conflicts on raw data accesses; STM transactions with conflicting accesses to currently monitored and/or buffered objects will cause CRESTM transactions to roll back; CRESTM transactions that invalidate data accessed by the STM transaction will be detected by the STM transaction no later than during the STM validation phase, because The stamped HGV will have to be greater than the GV probed at the start of the STM transaction.

As described above, the value of B or "batch size" is the amount by which the HGV is allowed to deviate from the GV. As mentioned above, whenever GV reaches the value of HGV, HGV is incremented by B. Whenever this happens, all currently executing CRES™ transactions roll back because they are monitoring the HGV's location. Thus, the larger B is, the less frequently such invalidations occur. On the other hand, once an STM transaction observes an object with a version number higher than the current GV, it will have to advance the GV to that higher number in order to ensure that it will be able to successfully read the object on its next re-execution. This "jumping" through the version space can cause version space consumption to be faster if B is large, and this may be possible for systems where the version space is limited and wraparound costs are large (e.g. it may require renumbering all objects in the heap) is a matter of concern.

Embodiments may adjust the value of B such that B is allowed to be large as long as the data accessed by different transactions is disjoint, but the value of B is decreased whenever sharing is detected. The first factor in this mechanism is an effective detection method. That is, an STM transaction needs to be able to tell with high probability that it has indeed read a value produced by a hardware transaction with a "high" HGV number. To accomplish this, the transaction compares the version the object contains with the GV. If the object has a higher version, the object is stamped with HGV. In any case where a transaction observes an object with a version number higher than the current GV, the transaction advances the GV to at least the version number it sees.

As soon as a conflict situation is handled, reducing the value of B to ensure that this situation occurs again is cheap in terms of version space consumption (though, for systems with very large version spaces, this may not matter too much). Any strategy that allows for "fast shrinkage/slow growth" is acceptable. For example, whenever a collision situation is detected, the value of B is halved, but never less than 1, and whenever HGV is increased by B, the value of B is also incremented, but by a fixed amount, say 1, And only up to a predetermined cap value.

Referring now to FIG. 5 , there is shown a flowchart of a method for processing hardware and software transactions in accordance with an embodiment of the present invention. As shown in FIG. 5, method 500 may include code paths for hardware transactions and software transactions. First, for a hardware transaction, the stamp value may be set such that it is equal to the HGV (block 510). Also, for the location of this stamp value, monitoring may be set such that the hardware transaction is notified whether to update the HGV (block 515). During execution of a hardware transaction, various read and write operations may be performed, each of which may be implemented using a corresponding read or write barrier (block 520). For each such barrier, it may be determined whether the barrier operation failed, for example due to a lock on the location to be read or written (diamond 523). If so, the transaction can be aborted (block 535). If a given barrier operation is successful for a write operation, the write data may be updated in the buffer and associated with the current HGV (block 525). At the end of the transaction, it may be determined whether the HGV has changed (diamond 530). If so, this indicates that, for example, a conflict has occurred between this hardware transaction and the software transaction, and the hardware transaction may be aborted accordingly (block 535). Otherwise, control passes to block 540 where the updates can be committed so that each updated value can be stored to memory and can be associated with the HGV to indicate the version number when it was updated.

For software transactions, at startup, a read value corresponding to the current GVN may be set (block 550). It can then be determined whether incrementing this read value would result in a result greater than the current value of HGV (diamond 555). If so, the HGV can be updated, which causes all pending hardware transactions to be destroyed. More specifically, control passes from diamond 555 to block 560 where the HGV values can be updated with an adaptive batch size B. Note that the operations of diamond block 555 and block 560 may be performed atomically in hardware using atomic compare and swap instructions. From either diamond 555 or block 560, control passes to block 565 where these STM transactions are executed. In general, dongles can be used to take ownership of any value written to read various data, perform operations, and update values. At the conclusion of such operations, it may be determined whether the transaction is ready to commit (diamond 570). If so, control passes to block 575 where GVN is incremented (block 575). In one embodiment, this increment may be one. This updated GVN may be stored in a write value associated with the software transaction (block 580). Note that the operations of blocks 575 and 580 may be performed atomically in hardware, eg, using an atomic increment instruction that returns the new value of GVN into the write value. It can then be determined whether all read objects have version numbers less than or equal to the read value (diamond 585). If not, the transaction may be aborted (block 595). If the confirmation of diamond 585 succeeds instead, then control passes to block 590 where the transaction is committed and the write value can be used as a new version number for all objects in the write set. In other words, release the write lock on the object in the write set by giving the object in the write set a new version number equal to WV. Although shown in the embodiment of FIG. 5 with this particular implementation, the scope of the invention is not limited in this respect.

Code generation resolves to the two most unrelated decisions that together lead to the transactional execution mode. First, code generation style can be done using Naked (NK) schema or Transactional VTable (TV). Second, for the rollback mechanism, when a decision is made to re-execute a transaction, it can be determined how the modifications made roll back and how control goes to the beginning of the transaction.

For the code generation style, the transaction context structure (possibly shared by members nested in the same order) can be augmented with a substructure called a transaction vtable. This is a structure whose elements are function pointers, one for each kind of STM JIT helper for STM mode. Other schemas can be created such that code generated by the same TV can be used in multiple schemas by dynamically changing the transaction vtable.

When a transaction detects inconsistency or is explicitly aborted, all state changes are rolled back and control is returned to the beginning of the transaction. CRESTM and pure software exception-based mechanisms generate internal exceptions to complete the return. This exception cannot be caught by any handler other than one inserted as part of a transaction transition during code generation.

Transaction nesting can occur. A discussion of closed nested transactions is provided first, and suppression behavior is described in the context of open nested transactions because these concepts are related. A given hardware architecture may not support any form of nesting. Instead, a flat model can be supported, where touched cache lines are buffered and monitored, and can be atomically committed to memory, or rolled back, where their temporary effects disappear without trace. However, the atomicity of failure of nested transactions provides that if the nested transaction rolls back, only its effects are undone, and the effects of the parent transaction are preserved (still only temporarily, however).

Flattening is an advantageous technique that assumes that transaction rollback is impossible and therefore nested undo information collection does not occur. The general algorithm is as follows. When a nested atomic block is entered, the nested closure transaction is set, and a try/catch block is placed around its execution. If nested transactions commit (which is the common case), the execution of the parent is restarted, and the effects of the children are now contained in the parent, and will never cause the need to undo them selectively. If on the other hand the nested transaction code percolates the exception, in a system with real nesting support only the nested transaction will roll back and the exception will resurface in the parent's context. In implementations where subtransactions cannot be rolled back independently, the entire transaction nest may be rolled back and re-executed in a mode that supports true nesting.

Similar to other cases where cache resident transaction rollback occurs, the following mechanism may be employed. At the point of nested destruction determination, a persistent write can be made to the transaction context, essentially stating why the transaction rolled back and what kind of re-execution mode is required next. Then, a stack return is performed and an enclosing exception handler enclosing the entire nest may be executed, for example using a normal exception. Recovery from flattening failures can occur by re-executing in HASTM mode.

In a nutshell, CRESTM allows small and simple transactions to run without locking or logging, even in the presence of otherwise unconstrained STM transactions, thereby comprehensively providing fast and rich full-featured limited-weakly-atomically correct (limited-weakly- atomic-correct)TM programming model. Using explicit mode transactions allows software to optimize its use of the previously limited state of the privately cached UTM transaction facility, and thereby run longer and larger transactions before spilling over to the STM. For example, stack accesses and newly allocated objects do not require monitoring or buffering. Embodiments provide an efficient cache resident pattern to speed up the maximum overhead of bounded weak atomic correct implementations (buffering, logging, locking). In various embodiments, software instructions may explicitly transact only certain user program data accesses.

Embodiments can be implemented with many different system types. Referring now to FIG. 6, a block diagram of a system according to one embodiment of the present invention is shown. As shown in FIG. 6 , multiprocessor system 1000 is a point-to-point interconnect system and includes a first processor 1070 and a second processor 1080 coupled via a point-to-point interconnect 1050 . As shown in FIG. 6, each of the processors 1070 and 1080 may be a multi-core processor comprising a first processor core and a second processor core (ie, processor cores 1074a and 1074b and processor cores 1084a and 1084b), There may however be potentially many more cores in a processor. Processor cores may execute TM transactions using hardware, software, or a combination thereof to enable efficient unconstrained transactions.

Still referring to FIG. 6 , the first processor 1070 also includes a memory controller hub (MCH) 1072 and point-to-point (P-P) interfaces 1076 and 1078 . Similarly, second processor 1080 includes MCH 1082 and P-P interfaces 1086 and 1088. As shown in FIG. 6, MCHs 1072 and 1082 couple the processors to respective memories, memory 1032 and memory 1034, which may be main memory (e.g., dynamic random access memory (DRAM)) locally attached to the respective processors. part. First processor 1070 and second processor 1080 may be coupled to chipset 1090 via P-P interconnects 1052 and 1054, respectively. As shown in FIG. 6 , chipset 1090 includes P-P interfaces 1094 and 1098 .

Additionally, chipset 1090 includes interface 1092 to couple chipset 1090 with high performance graphics engine 1038 through P-P interconnect 1039 . Chipset 1090 may in turn be coupled to first bus 1016 via interface 1096 . As shown in FIG. 6 , various input/output (I/O) devices 1014 may be coupled to a first bus 1016 , along with a bus bridge 1018 coupling the first bus 1016 to a second bus 1020 . Various devices may be coupled to the second bus 1020 including, for example, a keyboard/mouse 1022 , communication devices 1026 , and data storage locations 1028 in one embodiment, such as disk drives or other mass storage devices that may contain code 1030 . Additionally, audio I/O 1024 may be coupled to second bus 1020.

Embodiments can be implemented in code and stored on a storage medium having stored thereon instructions that can be used to program a system to carry out the instructions. The storage medium may include, but is not limited to, any type of disk, including floppy disks, compact disks, optical disks, solid-state drives (SSD), compact disk read-only memory (CD-ROM), compact disk rewritable (CD-RW), and magneto-optical disks, Semiconductor devices such as Read Only Memory (ROM), Random Access Memory (RAM), such as Dynamic Random Access Memory (DRAM), Static Random Access Memory (SRAM), Erasable Programmable Read Only Memory (EPROM), Flash memory, electrically erasable programmable read-only memory (EEPROM), magnetic or optical cards, or any other type of medium suitable for storing electronic instructions.

While the invention has been disclosed with respect to a limited number of embodiments, those skilled in the art will appreciate various modifications and changes thereto. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of the invention.

Claims (20)

1. A method comprising: Selecting a first transactional execution mode to begin a first transaction in an unconstrained transactional memory (UTM) system having multiple transactional execution modes comprising a plurality of hardware for execution within a cache memory of a processor mode, at least one hardware-assisted mode for execution using transactional hardware and software buffers of said processor, and at least one software-transactional memory (STM) mode for execution without said transactional hardware, wherein if no pending transactions are executing in said at least one STM mode, said first transaction execution mode is selected as the highest performing of said plurality of hardware modes, and otherwise said first transaction execution mode is selected as said multiple hardware modes The mode with lower performance among the two hardware modes; begin executing the first transaction in the first transaction execution mode; committing the first transaction if the first transaction completes without overflowing the cache memory or violating transactional semantics; and Otherwise, the first transaction is aborted, and a new transaction execution mode is selected to execute the first transaction. 2. The method of claim 1, wherein the highest performing mode is an implicit mode in which no locking or versioning operations take place. 3. The method of claim 2, wherein the lower performance mode is an explicit mode in which locking operations occur. 4. The method of claim 1 , further comprising: selecting the new transaction execution mode as one of the at least one hardware-assisted mode if the first transaction overflows the cache memory. 5. The method of claim 1 , further comprising: while executing the first transaction in the highest performance mode, determining that a second transaction has started in the at least one STM mode, and returning to the The first transaction is re-executed in the lower performance mode, one of the plurality of hardware modes. 6. The method of claim 1 , further comprising aborting the first transaction in the first transaction execution mode if a loss of hardware properties of the first transaction occurs. 7. An article of manufacture comprising a machine-accessible storage medium containing instructions that, when executed, cause a system to: receiving an indication of a failure of a first transaction executing in a first transactional execution mode, the first transactional execution mode, one of a plurality of transactional execution modes, the plurality of transactional execution modes including a multiple hardware modes for execution within the processor, at least one hardware-assisted mode for execution using the transactional hardware and software buffers of the processor, and at least one software transactional memory (STM) for execution without the transactional hardware )model; determining why the first transaction failed; and Determining a new transaction execution mode for re-executing the first transaction based at least in part on the failure reason includes: determining whether the first transaction should be re-executed in the first transaction execution mode, and the second transaction execution mode has a lower performance level than said first transactional execution mode, or a third transactional execution mode has a higher performance level than said first transactional execution mode. 8. The article of claim 7 , wherein determining the cause of failure comprises accessing a transaction record received with the indication, the transaction record containing a transaction status register (TSR) at the point of the first transaction failure ) value. 9. The article of claim 8, further comprising instructions to enable the system to perform a persistent write to the transaction record to indicate the new transaction execution mode in which the first transaction is executed. 10. The article of claim 7 , further comprising enabling the system to perform just-in-time (JIT) compilation of a code block of the first transaction in response to the first transaction failure and after the JIT compilation in Instructions of the first transaction are re-executed in the first transaction execution mode. 11. The article of claim 7, further comprising enabling the system to re-execute the first transaction in the first transaction execution mode if the counter of the number of times the first transaction has failed is less than a threshold instruction. 12. The article of claim 7, further comprising enabling the system to re-execute the first transaction in a second transaction mode if the first transaction fails due to a change in the number of pending transactions operating in STM mode An instruction for a transaction. 13. The article of claim 12 , further comprising enabling the system to continue executing the first transaction in the first transaction execution mode and refraining from initiating transactions to execute in the at least one second transaction mode. Instructions for at least one other transaction predetermined period. 14. A method comprising: concurrently executing a first transaction using a hardware transaction execution mode and a second transaction using a software transaction execution mode; and Within the second transaction, determine whether incrementing the read value of the second transaction corresponding to the global version counter used in the second transaction would cause the read value to exceed the value used in the first transaction A hardware global version counter, and if so, updating said hardware global version counter with an adaptive batch size. 15. The method of claim 14 , further comprising: monitoring a stamp value corresponding to the hardware global version counter in the first transaction, and if the value of the hardware global version counter changes, aborting the A first transaction wherein said hardware global version counter change is detected by said monitoring. 16. The method of claim 14 , further comprising: performing the first transaction without maintaining a write log. 17. The method of claim 14, wherein the hardware global version counter is strictly greater than the global version counter. 18. The method of claim 17, further comprising reducing the adaptive batch size in response to a conflict between the first transaction and the second transaction. 19. The method of claim 18, further comprising adjusting the adaptive batch size in response to incrementing the hardware global version counter to the adaptive batch size. 20. The method of claim 19 , wherein the adaptive batch size is increased by a first amount, and the adaptive batch size is decreased by a second amount greater than the first amount quantity.

Images