Software assisted nested hardware transactions

FIELD

0001This invention relates to the field of processor execution and, in particular, to providing for efficient execution of nested transactions.

BACKGROUND

0002Related technology can be found in <patcit id="pcit0001" dnum="US6219666B1"><text>US Patent No. 6,219,666 B1</text></patcit>, which discloses a method of recovery that involves maintaining a stack of transactions. A PUSH command causes data identifying the currently executing transaction to be placed at the top of the stack. New transactions, autonomous in scope, are created at the first transactional statement subsequent to the PUSH command. This is repeated for statements executed after the new transaction commits or rolls back, but before a POP command is executed. The latter restores the transaction identified by the topmost data in the stack. Also disclosed is a method involving the association of a lexical scope with an autonomous transaction scope to enable control of the transactions stack. This is used to automatically keep track of nested sequences of autonomous transactions and rapidly detect deadlocks. These techniques are used in the management of transactions in general.

0003Further related technology is found in <patcit id="pcit0002" dnum="US4164017A"><text>US Patent No. 4,164,017</text></patcit> entitled "Computer Systems", which discloses a data processor that has provision for error recovery by the division of a program into a set of program blocks. The apparatus has a main store and a cache store that preserves the states that have previously been taken up by items of information prior to commencing each block so that the states of the items of information prevailing at the beginning of a block can be restored if required.

0004Advances in semi-conductor processing and logic design have permitted an increase in the amount of logic that may be present on integrated circuit devices. As a result, computer system configurations have evolved from single or multiple integrated circuits in a system to multiple cores and multiple logical processors present on individual integrated circuits. An integrated circuit typically comprises a single processor die, where the processor die may include any number of cores or logical processors.

0005As an example, a single integrated circuit may have one or multiple cores. The term core usually refers to the ability of logic on an integrated circuit to maintain an independent architecture state, where each independent architecture state is associated with at least some dedicated execution resources. As another example, a single integrated circuit or a single core may have multiple logical processors for executing multiple software threads, which is also referred to as a multi-threading integrated circuit or a multi-threading core. Multiple logical processors usually share common data caches, instruction caches, execution units, branch predictors, control logic, bus interfaces, and other processor resources, while maintaining a unique architecture state for each logical processor.

0006The ever increasing number of cores and logical processors on integrated circuits enables more software threads to be executed. However, the increase in the number of software threads that may be executed simultaneously has created problems with synchronizing data shared among the software threads. One common solution to accessing shared data in multiple core or multiple logical processor systems comprises the use of locks to guarantee mutual exclusion across multiple accesses to shared data. However, the ever increasing ability to execute multiple software threads potentially results in false contention and a serialization of execution.

0007Another solution is using transactional execution to access shared memory to execute instructions and operate on data. Often transactional execution includes speculatively executing a grouping of a plurality of micro-operations, operations, or instructions. During speculative execution of a transaction by a processor, core, or thread, the memory locations read from and written to are tracked to see if another processor, core, or thread accesses those locations. If another thread does alter those locations, the transaction is restarted and it is re-executed from the beginning. Currently, values of memory locations to be changed in a transaction are saved elsewhere, so if the transaction needs to be re-executed the original state of all memory/registers may be restored.

0008However, as transactional execution has progressed, software programmers have begun to use nested transactions, i.e. a grouping of instructions/operations to be executed within and part of another outer/enclosing group of instructions/operations. As a consequence, current hardware for support for nested transactions has resulted in inefficient execution of nested transactions.

0009For example, assume an outer transaction and an inner transaction nested within the outer transaction is to be executed. Current hardware support typically saves values of memory locations to be changed before entering the outer transaction. Yet, when executing in the inner transaction, if an abort or invalidating event occurs, the state of memory locations is usually rolled-back to the original state of the memory locations requiring a re-execution of both the outer and the inner transaction. This simple example is magnified where more nested transactions exist within each other. Specifically, if an abort occurs within a nested transaction deep in a hierarchy of transactions, numerous nested transactions that were not associated with the abort would have to be re-executed for no reason.

BRIEF DESCRIPTION OF THE DRAWINGS

0010The present invention, which is defined in detail in the appended independent claims 1 and 12, is illustrated by way of example and not intended to be limited by the figures of the accompanying drawings.

0011<figref idref="f0001">Figure 1</figref> illustrates an embodiment of a processor to efficiently execute nested transactions.

0012<figref idref="f0002">Figure 2</figref> illustrates an embodiment of a logging module at different points in pseudo-code including nested transactions.

0013<figref idref="f0003">Figure 3</figref> illustrates another embodiment of a processor to efficiently execute nested transactions.

0014<figref idref="f0004">Figure 4</figref> illustrates an embodiment of a flow diagram for executing a current level nested transaction within a previous level transaction.

0015<figref idref="f0005">Figure 5</figref> illustrates an embodiment of a flow diagram for executing a nested transaction.

DETAILED DESCRIPTION

0016In the following description, numerous specific details are set forth such as examples of specific hardware support for transactional execution, specific types of local memory in processors, and specific types of memory locations, etc. in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that these specific details need not be employed to practice the present invention. In other instances, well known components or methods, such as coding of transactions in software, demarcation of transactions in hardware, architectures of multi-core and multi-threaded processors, and specific operational details of microprocessors, have not been described in detail in order to avoid unnecessarily obscuring the present invention.

0017The method and apparatus described herein are for providing software assistance for nested hardware transactions in processors. However, the methods and apparatus for providing software assistance for nested hardware transactions are not so limited, as they may be implemented on or in association with any integrated circuit device or system, such as cell phones, personal digital assistants, embedded controllers, mobile platforms, desktop platforms, and server platforms.

PROCESSORS

0018Referring to <figref idref="f0001"><b>Figure 1</b></figref>, an embodiment of processing element <b><i>100</i></b>, which is capable of transactional execution, is illustrated. Processing element <b><i>100</i></b> may be any element for executing instructions or operating on data. Examples of processing element <b><i>100</i></b> include a processor, microprocessor, multi-resource host processor, a microprocessor, a processing core, a logical processor, and an embedded processor, a multi-threaded processor, and a multi-core processor.

0019In one of the examples, reference to a multi-resource processor is made. Often a resource is referred to as a processor core, logical processor, or threaded processor. Consequently, a multi-resource processor includes a processor with multiple cores, logical processors, threads, or any combination thereof. A core, as used herein, refers to any logic located on an integrated circuit capable to maintain an independent architecture state, wherein each independently maintained architecture state is associated with at least some dedicated execution resources. In contrast, a logical processor typically refers to any logic located on an integrated circuit capable to maintain an independent architecture state, wherein the independently maintained architecture states share access to execution resources

0020Processor <b><i>100</i></b> may include any combination of cores or threads, such as a multi-core processor where each core supports execution of multiple software threads. Note that processor <b><i>100</i></b> is capable of individual execution within a system or may be combined with other processing elements in a multiple physical processor system. In one embodiment, to support speculative execution of transactions, processor <b><i>100</i></b> is capable of speculative execution. Other potential execution capabilities of processor <b><i>100</i></b> include in-order execution, out-of-order execution, serial execution, parallel execution, fixed point execution, floating-point execution, or other well-known types of execution. Specific examples of execution logic and resources are discussed below in reference to the execution resources section.

TRANSACTIONS/INVALIDATING EVENTS

0021Transactional execution usually includes grouping a plurality of instructions or operations into a transaction or a critical section of code. In some cases, use of the word instruction refers to a macro-instruction which is made up of a plurality of micro-operations. There are commonly two ways to identify transactions. The first example, includes demarcating the transaction in software. Here, some software demarcation is included in code to be identified during execution. In another embodiment, which may be implemented in conjunction with the foregoing software demarcation, transactions are grouped by hardware or recognized by instructions indicating a beginning of a transaction and an end of a transaction. Begin transaction and end transaction instructions are discussed in more detail in reference to <figref idref="f0004"><b>Figures 4</b></figref><b>and</b><figref idref="f0005"><b>5</b></figref> below.

0022In a processor, a transaction is either executed speculatively or non-speculatively. In the second case, a grouping of instructions is executed with some form of lock or guaranteed valid access to shared memory locations to be accessed. In the alternative, speculative execution of a transaction is more common, where a transaction is speculatively executed and only committed upon verification that no invalidating events occurred during execution of the transaction.

0023An invalidating event refers to an event generated by the system, a user, or another resource, not associated with the execution of the current transaction, that requires re-execution of the transaction or invalidation of the transaction. For example, assume processor <b><i>100</i></b> is a two-core processor. The first core is executing a transaction accessing shared memory, which includes a read from the shared memory and a write-back to the shared memory. During speculative execution of a current transaction by the first core, if the second core writes to the shared memory location that the first core read from an invalidating event has occurred. The current transaction is invalid, because a shared memory location read from was written to by the second core; therefore, the location read from is potentially bad/outdated data.

0024Another example includes the write to a shared memory location, where the second core reads from the same memory location. Here, the write is potentially invalid as it invalidates the read the second core just completed. In these examples, the second core was "another resource" not associated with the transaction, such as not assigned to execute the transaction or not executing the transaction, that made an invalidating access.

0025However, other examples of invalidating events include system generated interrupts, user-generated interrupts, an access by another resource to a memory location to be read from or written to during pendancy of a current transaction, or any other event that cause a manipulation of a shared memory location that a current transaction is reading from or writing to. A current transaction is considered "pending" when it is being executed, i.e. a begin transaction instruction has been executed, but an end transaction has not been executed and the data from the transaction has not been committed or retired. In addition, another resource or other resource is not limited to a core, but may also include a logical processor, a hardware thread, a software thread, as well as another remote agent/resource.

EXECUTION RESOURCES

0026<figref idref="f0001">Figure 1</figref> also illustrates execution resources <i>105</i>, which are to execute transactions. Execution resources <i>105</i> may also refer to hardware, logic, or modules to support transactional execution. As an example, execution resources <i>105</i> are to execute a first transaction and a second transaction nested in the first transaction. A transaction is nested within another transaction, when either in software or hardware, a begin transaction demarcation for an inner transaction is within a transaction demarcation for an outer transaction.

0027Quickly turning to <figref idref="f0002"><b>Figure 2</b></figref>, an embodiment of pseudo code nested transactions is illustrated. A begin_transaction call identifies either a software construct or a hardware execution of a begin transaction instruction, while an end_transaction call identifies also in software or hardware an end transaction instruction. Here first begin_transaction instruction <b><i>212</i></b> and first end_transaction instruction <b><i>232</i></b> illustrates the bounds of a first transaction. Second begin_transaction instruction <b><i>217</i></b> and second end_transaction instruction <b><i>227</i></b> outline the bounds a second transaction that is included in the bounds of the first transaction. In other words, the second transaction is nested within the first transaction. <figref idref="f0002"><b>Figure 2</b></figref> is discussed in more detail below in the logging module section.

0028Note that a reference to a first and second transaction herein is arbitrary, in that, a first transaction references only a starting point within a hierarchy of nested transactions to view the interplay of operations between an outer transaction and inner transaction nested within an outer transaction. Reference to a first and second transaction does not necessarily refer to a numerical first and second transaction, but rather, may refer to the order/nesting of transactions, i.e. the second within the first. In fact, the first transaction may be a nested transaction, as well as the 100^th transaction executed in an execution flow. For example, a first transaction may refer to a nested transaction nested three levels down from a top-level transaction, and the second transaction may refer to the fourth level transaction nested within the first transaction.

0029Referring back to <figref idref="f0001"><b>Figure 1</b></figref><b>,</b> in one embodiment execution resource <b><i>105</i></b> includes logic to execute a begin transaction instruction at the start of a transaction, as well as execute an end transaction instruction at the end of a transaction, such as the instructions shown in <figref idref="f0002"><b>Figure 2</b></figref>. Execution resources <b><i>105</i></b> may also include logic to retire transactions or instructions associated with transactions, as well as logic to buffer writes and commit writes to memory. Other well-known transactional execution resources and logic may also be included. A few examples include logic to detect data conflicts, to buffer speculative updates, to make updates atomically visible at transaction commit, to execute instructions, and to operate on data.

0030Other common modules, logic, and functional units not illustrated in <figref idref="f0001"><b>Figure 1</b></figref> may also be included, but are not required to be included, in processor <b><i>100</i></b>, such as any one or any combination of the following: a data path, an instruction path, a virtual memory address translation unit (a translation buffer), an arithmetic logic unit (ALU), a floating point calculation unit capable of executing a single instruction or multiple instructions, as well as capable to operate on single or multiple data operands in serial or in parallel, a register, an interrupt controller, an advanced programmable interrupt controller (APIC), a pre-fetch unit, a fetch unit, a decode unit, a cache, an instruction retirement unit, an instruction re-order unit, and any other logic that is be used for fetching, executing, or operating on instructions and/or data.

MEMORY

0031Memory <b><i>125</i></b> includes any memory location to be accessed by execution resources <b><i>105</i></b>, processing resources, such as cores, logical processors, or threads. In one embodiment, memory <b><i>125</i></b> is a shared memory shared by at least one other processing resource, such as a core, thread, logical processor, or remote agent. Examples of memory <b><i>125</i></b> include a cache, a plurality of registers, a register file, a static random access memory (SRAM), a plurality of latches, or other storage element. Note that processor <b><i>100</i></b> or any processing resources on processor <b><i>100</i></b> may be addressing a system memory location, a virtual memory address, a physical address, or other address when reading from or writing to a memory location. Memory <b><i>125</i></b> will be discussed in more detail in reference to the exemplary embodiments below, when discussing memory location to be written to or read from, states of memory locations, or rolling-back/restoring states/values of memory locations.

0032As a specific illustrative example, assume that memory <b><i>125</i></b> is a cache memory, such as a trace cache, a first-level cache, a second-level cache, or a higher-level cache. Cache <b><i>125</i></b> includes cache lines <b><i>126,127</i>,</b> and <b><i>128,</i></b> which may also be referred to as memory locations within memory <i>1<b>25.</b></i> As another example, assume memory <b><i>125</i></b> is a plurality of registers used by a processing element or resource as execution space or scratch pad to store variables, instructions, or data. Memory locations in grouping of registers <b><i>125</i></b> are registers <b><i>126,127</i>,</b> and <b><i>128</i>,</b> in this example.

MONITOR MODULE

0033In <figref idref="f0001"><b>Figure 1</b></figref>, monitoring module <b><i>110</i></b> is illustrated coupled to memory <b><i>125</i>;</b> however, monitor module <b><i>110</i></b> may be wholly or partially implemented in memory <b><i>125</i>,</b> as well as implemented elsewhere in processor <b><i>100</i>.</b> A module may be implemented in hardware, software, firmware, or any combination thereof. Commonly, module boundaries vary and functions are implemented together, as well as separately in different embodiments. As an example, which is discussed in more detail below, a cache coherency protocol is used to monitor/track invalidating accesses to memory <b><i>125</i>,</b> where bits in the cache are used to represent invalidating accesses and other hardware, software, or firmware determines that an invalidating event has occurred based on the value of those bits. Here, monitoring module varies across boundaries, as parts are implemented in memory <b><i>125</i></b>, as well as in other hardware or firmware in processor <b><i>100</i>,</b> as well as software executed on processor <b><i>100</i>.</b>

0034Monitoring module <b><i>110</i></b> is to detect an invalidating event during execution of a transaction. In one embodiment, monitor module <b><i>110</i></b> is part of the hardware support for executing transactions, as discussed above. Here, monitor module <b><i>110</i></b> is implemented in hardware to detect/monitor invalidating accesses to locations memory <b><i>125</i></b> to be changed/written to during execution of a transaction. As stated above an invalidating event refers to an event generated by the system, a user, or another resource, not associated with the execution of the current transaction, that requires re-execution of the transaction or invalidation of the transaction. For example, assume a current transaction writes to memory locations <b><i>126</i></b> and <b><i>127</i>.</b> A write to memory location <b><i>126</i></b> or <b><i>127</i></b> by another resource is monitored/detected by monitoring module <b><i>110</i></b> as an invalidating access.

0035As a first example, monitoring module <b><i>110</i></b> includes a cache coherency protocol to detect invalidating accesses to memory <b><i>125</i>.</b> In one embodiment of a cache coherency protocol there is a bit/flag for every line of the cache/memory location, such as lines <b><i>126-128</i>,</b> to represent if an invalidating access occurred to a corresponding memory location during execution of a transaction.

0036To simplify the example, assume that a transaction is executing and is to write to line <b><i>127</i></b> of cache <b><i>125</i>.</b> If a predetermined flag/bit in cache line <b><i>127</i></b> or a bit/flag associated with cache line <b><i>127</i></b> represents a first logical value, such as a high logical value, then there has been no invalidating access. However, upon an access to cache line <b><i>127</i></b> that would invalidate the current transaction, the flag/bit is flipped to represent that an invalidating access has occurred. Essentially, monitoring module <b><i>110</i></b> has detected an invalidating access and represented that in cache <b><i>125</i>.</b> Detecting of an invalidating access may include any known-method, such as comparing a resource ID, such as a thread ID or core ID, with that of the ID executing the current transaction.

0037Note that specific reference to a high logical value for one implementation was used in the example above; however, conversely, a low logic level may represent that there was no invalidating access. Often, the use of logic levels or logical values is also referred to as 1's and 0's, which simply represents binary logic states. For example, a 1 refers to a high logic level and 0 refers to a low logic level. In many older systems a high voltage level was represented by a voltage, e.g. 5V, and a low voltage level, e.g. 0V. As another specific example, a high logic level is at 1.2V and a low logic level is at .3V. However, a high logic/voltage level may refer to any voltage level above a threshold value, and inversely, a low logic level may refer to any voltage level below the threshold value. In addition, there may be more than two logical levels in a cell or waveform. As an example, a single waveform may represent four different logical values at different voltage levels.

0038Other methods of using hardware or software to monitor/track invalidating accesses to a memory, such as memory <b><i>125</i></b> may be used. One example of tracking invalidating accesses using at least in part tracking logic, such as an advanced load address table (ALAT), is discussed in, "Transaction based shared data operations in a multiprocessor environment," with serial no. <patcit id="pcit0003" dnum="US11027623B"><text>11/027,623</text></patcit>. Other standard hardware support may also be used. Two examples of standard hardware support for transactions are discussed in the following articles: (1) "<nplcit id="ncit0001" npl-type="s"><text>Transactional Memory: Architectural support for lock-free data structures," by Maurice Herlihy and J. Eliot B. Mossand in "Proceedings of the 20th Annual International Symposium on Computer Architecture," May 1993, pp. 289-300</text></nplcit>; (2) "<nplcit id="ncit0002" npl-type="s"><text>Virtualizing Transactional Memory," by Ravi Rajwar and Maurice Herlihy and Konrad Lai in "Proceedings of the 32nd Annual International Symposium on Computer Architecture," June 2005, pp. 494-505</text></nplcit>.

LOGGING MODULE

0039Also illustrated in <figref idref="f0001"><b>Figure 1</b></figref> is logging module <b><i>115</i></b> and rollback module <b><i>120</i></b>, which may be implemented together, separately, or vary across each other's boundaries. As stated above, a module may be implemented in hardware, software, firmware, or any combination thereof. Commonly, module boundaries vary and functions are implemented together, as well as separately in different embodiments. Logging module is to take a snapshot of values in memory, record states of memory locations, store handlers, store stacks of values in memory, store stacks of abort handlers, and/or perform other functions to enable roll-back/restore of memory locations to values immediately preceding a nested transaction.

0040Turning to <figref idref="f0002"><b>Figure 2</b></figref>, an embodiment of a log at different points in pseudo-code is illustrated. <figref idref="f0002"><b>Figure 2</b></figref> illustrates pseudo code on the left, and at checkpoints through the pseudo code, such as checkpoints <i><b>210, 215, 220, 225, 230</b>,</i> and <b><i>235</i></b>, log <b><i>200'</i></b>s operation is illustrated. At the highest level, instruction <b><i>205</i></b> is shown, i.e. X = 0, which represents a store, write, or other representation of setting a memory location X or a memory location referenced by address X to a simple numerical value, 0. In addition, further calls to variable, address, or memory location X operate in a similar manner. As stated above, X may be any memory location such as a cache location, register, variable space, system memory, etc.

0041First, it is worth noting that a first transaction, which is a top-level transaction as it is not nested within another transaction, begins at begi_transaction_1 instruction <b><i>212</i></b> and ends at end_transaction_1 instruction <b><i>232.</i></b> Consequently, a second transaction, which is a nested transaction being within the bounds of the first transaction, starts at begin_transaction_2 <b><i>217</i></b> and ends at end_transaction_2 <b><i>227.</i></b> Finally, a third transaction, which is nested within the second transaction, starts at begin_transaction_3 <b><i>222</i></b> instruction and ends at end_transaction_3 instruction <b><i>224.</i></b> Labeling of begin and end of transactions is shown as separate instructions with different reference numerals to illustrate that matching of the beginning and ending of transactions. However, begin_transaction_1 instruction <b><i>212,</i></b> begin_transaction_2 instruction <b><i>217,</i></b> begin_transaction_3 instruction <b><i>232</i></b> may be the same instruction to be executed at three different periods of time during execution. The same applies to the end_transaction instructions.

0042Starting at line <b><i>205</i></b> memory location X gets a value 0. At checkpoint <b><i>210,</i></b> before entering the first transaction, there are two options to begin logging. In a first option, where all addresses written to/changed are enumerated, i.e. known, then log <b><i>200</i></b> stores a first set of values/takes a snapshot of memory locations, such as X, to be changed in the first transaction. Here, before entering the first transaction or at the start of the transaction before executing a first instruction in the transaction, the current value/snapshot of memory location X is taken and stored in log <b><i>200,</i></b> as represented by entry <b><i>211</i></b> including X = 0.

0043As a second option, where not all addresses to be written to are known, executing of the first transaction begins, and during the transaction but immediately before changing/writing to a memory location, the snapshot or storing of a state of the memory location to be changed/written to is then stored in entry <b><i>211</i>.</b>

0044Therefore, upon execution of the first transaction, if an abort, failure, or invalidating access occurs, the memory location X that was changed is able to be rolled-back/restored to its original state immediately before the first transaction from entry <b><i>211</i></b> in log <b><i>200.</i></b> However, assuming execution continues to checkpoint <b><i>215</i></b> memory location X now has a value of 1 from operation/execution of instruction <b><i>213.</i></b> Now, in one embodiment a logging module, which includes log <b><i>200,</i></b> is to take a second-level snapshot of a second-level value in a memory location to be changed during execution of the second transaction.

0045To illustrate, assume that the program flow is at checkpoint <b><i>215,</i></b> before entering the second transaction, which is at a second-level and nested within the first transaction. At this point there the same two options for logging exist: (1) log before any locations are written to or (2) log as execution goes along immediately before any writes. Here, the second-level value is the value written to X at line/instruction <b><i>213,</i></b> as it is the value at the same level as the second transaction. The second transaction is at a second-level as it is nested within another transaction, which is deemed the first-level. As a result, a second-level snapshot of a second-level value, i.e. 1 from line <b><i>213,</i></b> in a memory location to be changed during execution of the second transaction, such as X which is changed/written to in line <b><i>218.</i></b> Here, the second level-snapshot includes the storing of the second-level value, <b><i>1,</i></b> in log <b><i>200,</i></b> which is seen at entry <b><i>216.</i></b>

0046It is worth noting at this point, that log <b><i>200</i></b> may be implemented in any manner to track values, such as regular storage in a stack configuration. In this example, the second-level value of 1 is stacked on the first-level value of 0. To illustrate this functionality, assume an abort occurs at line <b><i>218.</i></b> Instead of previous transactional execution that would flatten nested transactions and restore X to its first-level original state of 0, the state of X is able to be rolled-back to just checkpoint <b><i>215</i></b> where X has a value of 1, from the assistance of log <b><i>200.</i></b> Additionally, if execution had to be rolled back again to checkpoint <b><i>210</i></b> and the value 1 had been popped off a stack configuration to roll-back previously, then the state of X may further be rolled-back to 0 at checkpoint <b><i>210</i></b> based on log <b><i>200.</i></b>

0047It should also be apparent that reference to a first transaction and a second transaction nested within a first transaction does not necessarily refer to a top-level transaction, such as the first transaction in <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> and the second transaction does not necessarily refer to the first nested transaction, as in <figref idref="f0002"><b>Figure 2</b></figref><b>.</b> For example, a first transaction may be the second transaction in <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> which is a nested transaction already, while the second transaction nested within the first transaction may be the third transaction that is nested in the second transaction of <figref idref="f0002"><b>Figure 2</b></figref><b>.</b> Basically, the first and second transaction may be viewed at any level in a hierarchy of nested transactions.

0048Continuing the example, from above, assume that execution has continued to checkpoint <b><i>220.</i></b> At this point, the third transaction is a current-level transaction or an inner transaction, while the second transaction is the outer transaction, enclosing transaction, or previous-level transaction. Once again, X is to be changed in the inner-level transaction, so a state of the previous-level or second-level memory location to be changed during execution of the transaction is stored in log <b><i>200.</i></b> Here, X has a value of 2, so the value 2 is pushed onto a stack in entry <b><i>221</i></b> including 0, 1, and 2. Similarly, if an abort occurs at this point, memory location X is restored to the previous-level value of 2 and the third transaction may be re-executed without re-executing both the first and second transactions.

0049Upon end-transaction_3 instruction <b><i>224</i></b> when the third transaction is to be ended, retired, and/or committed a write log is merged into the write log of the enclosing or previous level transaction. In the embodiment above, values were appended or popped onto the entries store in log <b><i>200.</i></b> As a result upon executing an end_transaction instruction, the nested transaction is to be committed, so the log pops, merges, or removes the value appended for the current-level transaction that is being ended. Therefore, upon an abort at this point the second transaction is able to be re-executed and the original state of the memory location X is able to be restored from the log to the value before entering the second transaction of 1. This embodiment is illustrated in entry <b><i>226.</i></b>

0050However, any other implementation of storing the values may be used. In fact, an implementation is tailored to an abort handler that rolls-back or restores the values, as discussed below. Similar merging operations are done at checkpoints <b><i>230</i></b> and <b><i>235,</i></b> as illustrated in entries <b><i>231</i></b> and <b><i>236,</i></b> respectively.

0051Returning to <figref idref="f0001"><b>Figure 1</b></figref> briefly, roll-back module <b><i>120</i></b> is illustrated and is to roll-back the memory location to the second-level snapshot, upon the monitor module detecting an invalidating event during execution of the second transaction. In the example, above it is apparent, that roll-back module <b><i>120</i></b> restores values of memory locations to be changed during execution of a nested transaction to their states immediately before executing the nested transaction. Examples of roll-back module <b><i>120</i></b> are discussed below in reference to default handlers and abort handlers.

0052Turning over to <figref idref="f0003"><b>Figure 3</b></figref><b>,</b> an embodiment of a processor to efficiently execute nested transactions is illustrated. Similar to <figref idref="f0001"><b>Figure 1</b></figref><b>,</b> processor <b><i>300</i></b> includes execution logic <b><i>305,</i></b> memory <b><i>315</i></b> including memory locations <b><i>316,</i></b> and monitoring logic <b><i>310.</i></b> In one embodiment, processor <b><i>300</i></b> is a multi-resource processor, such as a multi-core, multi-threaded, or multi-logical processor with monitoring logic <b><i>310</i></b> including cache coherency logic. However, any of the foregoing examples of a processor and its contents may be included in processor <b><i>300.</i></b>

0053In addition, processor <b><i>300</i></b> includes local memory <b><i>320.</i></b> Local memory <b><i>320</i></b> includes any memory associated with processor <b><i>320.</i></b> In one embodiment, local memory consists of memory that is only accessible by one processor or one processing resource; however, local memory is not so limited. In another embodiment local memory includes a globally shared memory that is partitioned among processors or resources. In this case, a thread Id, core Id, or other way of identifying a resource is used to allow access to a section of memory, and inversely, to deny access to other resources not assigned to the section of memory. Specific examples of local memory <b><i>320</i></b> include a Random Access Memory (RAM), a Static RAM (SRAM), a Dynamic RAM (DRAM), a plurality of registers, a plurality of latches, a cache, or any storage element in processor <b><i>300.</i></b>

0054In one embodiment, log <b><i>325</i></b> is illustrated stored in local memory <b><i>320.</i></b> As an example, log <b><i>325</i></b> operates in a similar manner to log <b><i>200</i></b> illustrated in <figref idref="f0002"><b>Figure 2</b></figref><b>.</b> In this case, notice that log <b><i>325</i></b> illustrates the state of log <b><i>200</i></b> at entry <b><i>220</i></b> in a stack format. Assuming that operation is at checkpoint <b><i>220</i></b> in <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> the third nested transaction is the current-level transaction and the second transaction is the previous-level transaction. Therefore, upon an invalidating event occurring during execution of the current-level transaction, the memory location to be changed during execution of the current-level transaction, i.e. memory location X, is restored to the previous-level value/state of 2, which is on the top of the stack in log <b><i>325</i></b> at entry <b><i>326.</i></b>

0055Moreover, handler module <b><i>330,</i></b> which may also be referred to as a roll-back module, is shown stored in local memory <b><i>320,</i></b> but as illustrated in <figref idref="f0001">Figure 1</figref> handler module <b><i>330</i></b> may be stored in other memory or implemented in other logic/modules of processor <b><i>300.</i></b> Handler module <b><i>330</i></b> is to restore the memory locations to be written to during execution of a second transaction nested within a first transaction to a second set of values or a plurality of previous-level values logged before writing to the memory locations to be written to , if an invalidating access occurs during execution of the second transaction.

0056A specific simplified embodiment of handler module <b><i>330</i></b> is discussed to illustrate its potential operation. Upon an invalidating access/event occurring during execution of a nested transaction, a default handler is initially invoked/executed. A default handler, although not specifically depicted, may be stored in local memory <b><i>320,</i></b> memory <b><i>315,</i></b> system memory <b><i>340,</i></b> or other memory in processor <b><i>300</i></b> not depicted. A default handler is to transfer control of processor <b><i>300</i></b> to an abort handler associated with the current-level transaction, if an invalidating access occurs during execution of the current level-transaction.

0057For example, assume that upon execution of the first transaction in <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> an abort handler associated with the first transaction, such as abort handler <b><i>331</i></b> in <figref idref="f0003"><b>Figure 3</b></figref><b>,</b> is pushed onto a stack of abort handlers, as in handler module <b><i>330.</i></b> In addition, a first set of values of memory locations to be written to during execution of the first transaction are stored in log <b><i>325,</i></b> which in this case includes only memory location X getting a value 0 in entry <b><i>328</i></b> of log <b><i>325.</i></b> Next, upon entering the second transaction in <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> second abort handler <b><i>332</i></b> associated with the second transaction is pushed onto handler module <b><i>330's</i></b> stack and a second set of values is logged in entry <b><i>327,</i></b> i.e. second/previous-level value 1, for X.

0058Now assume, that an invalidating access or event occurs during execution of the second transaction. The default handler, when executed, is to initiate execution and/or control to the top abort handler on the stack, which is abort handler <b><i>332</i></b> that is associated with the second transaction. Abort handler <b><i>332,</i></b> when executed by the execution unit, is to restore memory location X to the previous-level, i.e. the second set of values, logged in log <b><i>325.</i></b> At this point the value 1 is at the top of the stack and is loaded into memory location X by abort handler <b><i>332</i></b> to allow for re-execution of the second nested transaction.

0059However, if normal execution were to continue, then upon entering the third transaction in <figref idref="f0002"><b>Figure 2</b></figref><b><i>,</i></b> abort handler 333 associated with the third transaction is pushed onto the handler stack and previous-level value <b><i>326</i></b> is pushed onto log <b><i>325's</i></b> stack.

AN EMBODIMENT OF A SYSTEM

0060Referring still to <figref idref="f0003"><b>Figure 3</b></figref><b>,</b> an embodiment of a system is illustrated. Processor <b><i>300</i></b> is coupled to system memory <b><i>340.</i></b> Although not shown, system memory <b><i>340</i></b> may be coupled to processor <b><i>300</i></b> through other components or devices, such as a memory controller hub. System memory includes any memory for storage in a system such as a SRAM, DRAM, double data rate (DDR) RAM, non-volatile (NV) RAM, EDO RAM, or other memory device. System memory <b><i>340</i></b> is to store elements, such as instructions and data operands to be executed by processor <b><i>300.</i></b> In one embodiment, system memory stores a plurality of instructions that are to be grouped into transactions, such as a first transaction and a second transaction to be nested in the first transaction.

AN EMBODIMENT OF A METHOD FOR EXECUTING A NESTED TRANSACTION

0061Turning to <figref idref="f0004"><b>Figure 4</b></figref><b>,</b> an embodiment of a flow diagram for a method of executing a current level transaction nested within a previous level transaction is illustrated. In flow <b><i>405,</i></b> a current level transaction nested within a previous-level transaction is executed. Here, as above, a begin transaction instruction or demarcation may establish the starting points of both the current level and previous level transactions. In one embodiment, the transaction is executed with hardware support for determining bounds of transaction, detecting data conflicts, and other hardware support functions mentioned above.

0062In flow <b><i>410</i></b> a log including a first state of a memory location at the previous level, which is to be written to during execution of the current-level transaction, is maintained. Although, the flow diagram in <figref idref="f0004"><b>Figure 4</b></figref><b>,</b> illustrates an arrowed flow, the flows shown, such as flow <b><i>410</i></b> and <b><i>405</i></b> may occur in any order. As stated above, storing to the log may be done either before entering and executing the transaction, as well as during execution of the transaction and immediately before the memory location to be written to is changed, written to, or a write to is buffered. As illustrated, in the foregoing examples, the log may be stored in a local memory.

0063In one embodiment, local memory also maintains a stack of a first abort handler associated with the current level transaction stacked on a second abort handler associated with the previous level transaction. Similar in operation, to handler module <b><i>330</i></b> in <figref idref="f0003"><b>Figure 3</b></figref><b>,</b> a stack or other general configuration of abort handlers is stored in local memory. In another embodiment, the stack of handlers is stored in a different memory at random locations, not in a stack configuration. In this case, a group of pointers or other association device associates the handlers with their respective transaction.

0064In decision box <b><i>415,</i></b> it is determined if an invalidating event occurs during execution of the current level transaction. Examples of invalidating events are discussed above, in the transactions/invalidating events sections. In one embodiment, a cache coherency protocol or other hardware support is used to determine if the invalidating event occurs during execution of the current-level transaction.

0065In flow <b><i>420,</i></b> the memory location is restored to the first state of the memory location at the previous level, if an invalidating event is detected during execution of the current level transaction. As an example restoring includes popping the first abort handler off the stack, transferring control to the first abort handler, executing the first abort handler, wherein upon execution, the first abort handler restores the memory location with the first state of the memory location maintained in the log.

0066Finally, in flow <b><i>425,</i></b> the log is merged with a second state of the memory location at the current level, if no invalidating event occurs during execution of the current level transaction. In a first embodiment, merging includes appending the second state on the end of the log. In another example, merging may include discarding the last log entry to ensure a potential abort within the previous-level transaction is correctly rolled-back to an original state before its execution. In addition, upon committing or ending the previous-level transaction the log may be discarded completely, if the previous-level transaction is a top-level transaction, which is not nested within another transaction.

ANOTHER EMBODIMENT OF A METHOD FOR EXECUTING A NESTED TRANSACTION

0067Turning finally to <figref idref="f0005"><b>Figure 5</b></figref>, another embodiment of a flow diagram for a method of executing a nested transaction is illustrated. In flow <b><i>505,</i></b> an abort handler associated with a current nested transaction is pushed onto a stack of abort handlers. In one embodiment, the stack of abort handlers is stored in a local memory.

0068In flow <b><i>510,</i></b> a first value of a first memory location, which is to be changed during execution of the current nested transaction, is logged in a local memory before changing the value of the first memory location. As a first example, logging a first value of the first memory location includes storing/logging the first value of the first memory location in a local memory before executing a first instruction in the current nested transaction. In another embodiment, logging a first value of the first memory locations includes storing/logging the first value of the first memory location in a local memory during execution of the current execution and immediately before the first memory location is changed/written to.

0069In decision box <b><i>515,</i></b> it is determined with hardware if an invalidating event occurs during execution of the current nested transaction. In an illustrative example, a functional unit of a microprocessor such as a cache, an advanced load address table (ALAT), and invalidating access tracking unit is at least partially used to determine if an invaliding event occurs during execution of the current nested transaction. A cache coherency protocol or other hardware based protocol may also be used.

0070In flow <b><i>520</i></b> and <b><i>525,</i></b> control is transferred to the abort handler associated with the current nested transaction and the first memory location is restored with the first value, if an invalidating event occurs during execution of the current nested transaction. In one embodiment, control is transferred by execution of a default handler to pop the abort handler associated with the current nested transaction off the stack of handlers to be executed by a processor. Restoring the location includes writing the first value to the first memory location before re-execution of the current transaction. The abort handler associated with the current transaction may accomplish this, when executed.

0071In decision box, <b><i>530</i></b> it is determined if an enclosing transaction is a top-level transaction, if no invalidating event occurs during execution of the current nested transaction. Essentially, here, the transaction is ended successfully with no invalidating access or event, such as a write or interrupt. If the transaction is not an enclosing transaction, but rather a nested transaction, a log associated with the current nested transaction including the first value is merged with an enclosing transaction log. In contrast, if the transaction is an enclosing transaction then a log associated with the current nested transaction including the first value is discarded.

0072As illustrated above, nested transaction may be executed efficiently. Previous nested transaction execution, typically, flattened the nested transaction. As a result, in a nested transaction hierarchy, like the transactions shown in <figref idref="f0002"><b>Figure 2</b></figref><b>,</b> if there was a failure, abort, or invalidating access during execution of the third transaction, then both the first and the second transaction would also have to be re-executed. However, by providing hardware support of the execution of transactions, and assistance through modules such as a logging module and handler module, only the failed third transaction is potentially re-executed, which saves precious execution time and allows for efficient execution of nested transactions.

0073The embodiments of methods, software, firmware or code set forth above may be implemented via instructions or code stored on a machine-accessible or machine readable medium which are executable by a processing element. A machine-accessible/readable medium includes any mechanism that provides (i.e., stores and/or transmits) information in a form readable by a machine, such as a computer or electronic system. For example, a machine-accessible medium includes random-access memory (RAM), such as static RAM (SRAM) or dynamic RAM (DRAM); ROM; magnetic or optical storage medium; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals); etc.

0074In the foregoing specification, a detailed description has been given with reference to specific exemplary embodiments. It will, however, be evident that various modifications and changes may be made thereto without departing from the scope of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative sense rather than a restrictive sense. Furthermore, the foregoing use of embodiment and other exemplarily language does not necessarily refer to the same embodiment or the same example, but may refer to different and distinct embodiments, as well as potentially the same embodiment.