Coherence protocol for hardware transactional memory in shared memory using non volatile memory with log and no lock

Abstract

The invention relates to a data processing system and a date processing method. The data processing system is configured to perform a hardware transactional memory (HTM) transaction. The data processing system comprises a byte-addressable nonvolatile memory for persistently storing data and a processor being configured to execute an atomic HTM write operation in connection with committing the HTM transaction by writing an indicator to the nonvolatile memory indicating the successful commit of the HTM transaction.

Claims

1. A multiprocessor system for performing a hardware transactional memory (HTM) transaction, the multiprocessor system comprising: a byte-addressable nonvolatile memory for persistently storing data; and a processor communicatively coupled to the byte-addressable nonvolatile memory, the processor configured to: execute an atomic HTM write operation in connection with committing the HTM transaction by writing an indicator to the nonvolatile memory, the indicator indicating a successful commit of the HTM transaction, the indicator comprising a commit record; create a log record of the HTM transaction in the nonvolatile memory, wherein a data structure of the log record comprises: (1) the commit record, (2) a unique identifier of the HTM transaction, (3) data and an address of a cache memory associated with the HTM transaction, and (4) a size of the log record; log a write operation associated with the HTM transaction in the nonvolatile memory prior to the successful commit of the HTM transaction; flush operational data written by the HTM operation from the cache memory to the nonvolatile memory without aborting the HTM transaction; set the HTM transaction to an unlogged state by unsetting the indicator, after the successful commit of the HTM transaction; and evict the flushed address from the cache memory.

2. The multiprocessor system of claim 1, wherein the processor is coupled to the cache memory by a plurality of cache lines, with the cache memory configured to be used by the processor for caching data using a cache coherence protocol.

3. The multiprocessor system of claim 1, wherein the multiprocessor system is further configured to log the write operation associated with the HTM transaction in the nonvolatile memory by transparently flushing the log of the write operation associated with the HTM transaction to the nonvolatile memory prior to the successful commit of the HTM transaction.

4. The multiprocessor system of claim 1, wherein the multiprocessor system further comprises a recovery unit configured to redo the log upon a restart of the multiprocessor system, if the log of the write operation associated with the HTM transaction is present in the nonvolatile memory and the HTM transaction is in a logged state, in particular the indicator is set; and set the HTM transaction to the unlogged state by unsetting the indicator if the redo of the transaction is completed.

5. A method for performing a hardware transactional memory (HTM) transaction in a multiprocessor system, the method comprising: executing an atomic HTM write operation in connection with committing the HTM transaction by writing an indicator to a nonvolatile memory, the indicator indicating a successful commit of the HTM transaction, the indicator comprising a commit record; creating a log record of the HTM transaction in the nonvolatile memory, wherein a data structure of the log record comprises: (1) the commit record, (2) a unique identifier of the HTM transaction, (3) data and an address of a cache memory associated with the HTM transaction, and (4) a size of the log record; logging a write operation associated with the HTM transaction in the nonvolatile memory prior to the successful commit of the HTM transaction; flushing operational data written by the HTM operation from the cache memory to the nonvolatile memory without aborting the HTM transaction; setting the HTM transaction to an unlogged state by unsetting the indicator, after the successful commit of the HTM transaction; and evicting the flushed address from the cache memory.

6. The method of claim 5 further comprising executing a write operation associated with the HTM transaction in the nonvolatile memory by transparently flushing the log of the write operation associated with the HTM transaction to the nonvolatile memory prior to the successful commit of the HTM transaction.

7. The method of claim 5 further comprising redoing the log upon a restart of the multiprocessor system, if the log of the write operation associated with the HTM transaction is present in the nonvolatile memory and the HTM transaction is in a logged state, in particular setting the indicator and setting the HTM transaction to the unlogged state by unsetting the indicator if the redoing of the transaction is completed.

8. The method of claim 5, wherein the logging the write operation associated with the HTM transaction in the nonvolatile memory comprises transparently flushing a log of the write operation associated with the HTM transaction to the nonvolatile memory.

9. A non-transitory computer readable medium having stored thereon computer-executable instructions that when executed by a processor cause the processor to perform operations for performing a hardware transactional memory (HTM) transaction in a multiprocessor system, the operations comprising: executing an atomic HTM write operation in connection with committing the HTM transaction by writing an indicator to a nonvolatile memory, the indicator indicating a successful commit of the HTM transaction, the indicator comprising a commit record; create a log record of the HTM transaction in the nonvolatile memory, wherein a data structure of the log record comprises: (1) the commit record, (2) a unique identifier of the HTM transaction, (3) data and an address of a cache memory associated with the HTM transaction, and (4) a size of the log record; logging a write operation associated with the HTM transaction in the nonvolatile memory prior to the successful commit of the HTM transaction; flushing operational data written by the HTM operation from the cache memory to the nonvolatile memory without aborting the HTM transaction; setting the HTM transaction to an unlogged state by unsetting the indicator, after the successful commit of the HTM transaction; and evicting the flushed address from the cache memory.

10. The non-transitory computer readable medium of claim 9, wherein the logging the write operation associated with the HTM transaction in the nonvolatile memory comprises transparently flushing a log of the write operation associated with the HTM transaction to the nonvolatile memory.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Further embodiments of the invention will be described with respect to the following figures, in which:

(2) FIG. 1 shows a schematic diagram of a data processing system according to an embodiment;

(3) FIG. 2 shows a schematic diagram of a data processing method according to an embodiment.

(4) FIG. 3 shows a state diagram of a data processing system according to an embodiment; and

(5) FIG. 4 shows a schematic diagram illustrating different aspects of a data processing system according to an embodiment and providing details about the implementation of each step.

DETAILED DESCRIPTION OF EMBODIMENTS

(6) It is an object of the invention to provide an improved data processing system and method.

(7) This object is achieved by the subject matter of the independent claims.

(8) Further implementation forms are provided in the dependent claims, the description and the figures.

(9) The present invention is based on the general idea to add a persistent indication atomically within a HTM commit and logging each HTM write, and flushing each HTM write after commit, to allow the hardware transactional memory (HTM) to maintain consistency and persistency in a non-volatile memory even through system failures.

(10) In the following detailed description, reference is made to the accompanying drawings, which form a part of the invention, and in which are shown, by way of illustration, specific aspects in which the invention may be practiced. It is understood that other aspects may be utilized and structural or logical changes may be made without departing from the scope of the present invention. The following detailed description, therefore, is not to be taken in a limiting sense, and the scope of the present invention is defined by the appended claims.

(11) It is understood that a invention in connection with a described method may also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if a specific method step is described, a corresponding device or system may include a unit to perform the described method step, even if such unit is not explicitly described or illustrated in the figures. Further, it is understood that the features of the various exemplary aspects described herein may be combined with each other, unless specifically noted otherwise.

(12) FIG. 1 shows a schematic diagram of a data processing system 100 according to an embodiment. The data processing system 100 is configured to perform a hardware transactional memory (HTM) transaction. The data processing system 100 comprises a byte-addressable nonvolatile memory 101 for persistently storing data and a processor 103. The processor 103 is configured to execute an atomic HTM write operation in connection with committing the HTM transaction by writing an indicator to the nonvolatile memory indicating the successful commit of the HTM transaction. In an embodiment, the indicator can be a non-volatile bit in the commit of the HTM transaction.

(13) Nonvolatile memory (NVM or NVRAM) is a byte-addressable memory which is durable, i.e. the data in the memory is persistent across power failures. According to the embodiment, the log records (including successful commit indicator) and application data are maintained in NVM.

(14) According to an embodiment the HTM transaction needs to write log records and flush both log records and application data in the NVM without aborting itself or other live transactions. This requires a special type of flush instructions which are transparent to the HTM system, which we name transparent flushes (TF). Current architectures of major vendors employ flush instructions that do not evict the flushed address from the cache, which can potentially implement TF mechanism. For an example, a thread running an HTM transaction with the TSX block in X86 microarchitecture, writes a log record to the cache and then uses a CLWB instruction to flush the log record to the Log Records area in the NVM.

(15) A recovery process reads the commit indicator from NVM after the machine restarts and if the commit indicator is set to true, which means the transaction was successful but is still logged, it reads the log records and writes to the Application Data area accordingly.

(16) According to an embodiment the indicator can be implemented by the commit record from FIG. 4. A successful commit is the point where the transaction writes are made visible atomically to all processing units in the system.

(17) In an embodiment, the processor 103 is coupled to a cache memory 105 by a plurality of cache lines 106 and the cache memory 105 is configured to be used by the processor 103 for caching data using a cache coherence protocol.

(18) In an embodiment, the data processing system 100 is further configured to create a log record in the Log Records area of the nonvolatile memory 101, and log the write operation of cached data associated with the HTM transaction into the Log Records area. The data structure of Log Records could be referred to FIG. 4, which, for example, includes Commit Record, Self_id, Size and <DATA, ADDR>tuples. Commit Record is the persistent successful commit indicator. Self id is the unique identifier of the transaction. <DATA, ADDR>tuple: A log record of the data and address of a single cache line as written by the transaction. Size is the number of log records in one transaction.

(19) In an embodiment, the data processing system 100 is configured to log the write operation of cached data associated with the HTM transaction into the Log Records area by transparently flushing the log of the write operation of cached data associated with the HTM transaction to the nonvolatile memory 101 prior to the commit of the HTM transaction. A transparent flush is invisible to the cache memory 105 and to the HTM system.

(20) In an embodiment, the data processing system 100 further comprises a recovery unit 107 configured to redo the log upon a restart of the data processing system 100, if the Commit Record is set to true and the log record data, associated with the HTM operation is present in the nonvolatile memory 101. Redo the log means rewriting application data area from Log Records area that is still in logged state and may not have been flushed to the nonvolatile memory 101 before a system failure, for instance, a power failure.

(21) In an embodiment, the data processing system 100 is further configured to flush the modified application data associated with the HTM operation from the cache to the Application Data area in nonvolatile memory 101 after the commit of the HTM transaction.

(22) In an embodiment, the data processing system 100 is further configured to transparently flush the modified application data associated with the HTM operation from the cache to the Log Records area in nonvolatile memory as in FIG. 4 101 before the commit of the HTM transaction and to the Application Data area in nonvolatile memory as in FIG. 4 101 after the commit of the HTM transaction without aborting a HTM transaction.

(23) In an embodiment, the indicator indicating the successful commit of the HTM transaction comprises a HTM transaction commit record. The commit record can be a Boolean variable where a value true means the transaction is successfully committed. As long as the commit record is set, the writes of the transaction are in logged state and will be recovered in a restart.

(24) FIG. 2 is a flow chart of the main stages of a persistent HTM transaction according to an embodiment.

(25) It shows all the stages of a successful persistent HTM transaction:

(26) Start an HTM transaction.

(27) Write application data in cache and log it in log records in the Log Records area in NVM.

(28) Commit the transaction successfully and at the same time, set the indicator to true in the commit record in the Log Records area in NVM.

(29) If no failure—flush the modified application data from the cache to Application Data area in NVM.

(30) If there was a failure, and the indicator is true, in restart, copy the modified application data from Log Records area in NVM to application data in Application Data area in NVM otherwise if the indicator is false, ignore the transaction.

(31) Set the indicator to false in the commit record in the Log Records area in NVM.

(32) In the following, further embodiments and implementation forms of the data processing system 100 and the data processing method 200 are described in more detail using the following notation and definitions.

(33) A HTM transaction executed, for instance, by the processor 103, is denoted as T.sub.k. A restart of the data processing system 100 brings the data to a consistent state, removing effects of uncommitted transactions and applying the missing effects of the committed ones (Restart). A transaction is finalized (Finalization) if it is committed successfully, and all its writes in cache are flushed to the Application Data area in the NVM 101 and the commit record is set to false and therefore the transaction is ignored if a subsequent restart happens. If a is a memory address in the cache 105, TF(α), referred to as a Transparent Flush, will write a to the nonvolatile memory, either in the Application Data area or the Log Records area, but will not invalidate it and will not affect the cache coherency in any way.

(34) In an embodiment, the state of a data item x (an addressable word) in the NVM 101, which is written by an HTM transaction T, is defined by the following three characteristics shown in FIG. 3. (1) “Private”/“Shared”: “Private” means x is only in the L1 cache of one thread, and is not visible to other threads. When x is “Shared”, the cache coherence makes its new value visible. (2) “Persistent”/“Volatile”: “Persistent” means that the last write of x is in the NVM 101; otherwise the new value of x is “Volatile” in the cache 105 and will disappear on a power failure. (3) “Logged”/“Clear”: When x is “Logged”, a restart will recover x from the non-volatile log. If x is “Clear”, the restart will not touch x, because its log record has been finalized or its transaction has not been successfully committed.

(35) FIG. 3 shows the state machine of a single write in a HTM transaction that can be executed by a data processing system according to the present application, for instance the data processing system 100 shown in FIG. 1. According to an embodiment the mechanism makes the transition <“Private”, “Clear”> to <“Shared”, “Logged”>atomic, and allows the transition <“Volatile”> to <“Persistent”> to not abort a concurrent HTM transaction that reads the item. Generally, the “Logged” characteristic is for the entire HTM transaction. Turning all writes of a single transaction from “Clear” to “Logged” requires a single persistent write. In a HTM commit according to an embodiment of the present application, all writes are exposed by the HTM and are simultaneously logged. In an embodiment, each write generates a persistent log record, but until a successful commit, the write is not logged in the sense that it will not be replayed by a restart process. FIG. 4 is a detailed flow chart of the actions in the different stages.

(36) When the HTM transaction T.sub.k writes to a variable x, x is marked as transactional in the L1 cache, for instance, the cache 105 shown in FIG. 1, of the processor 103 and is “private”, i.e., exclusively in the L1 cache 105 of the processor 103. It is “volatile”, as it is only in the cache 105, and “clear”, i.e., not “logged”, as the transaction is not yet committed. Not logged implies that x will not be written by the restart process. Upon an abort or a power failure of the data processing system 100, the “volatile” and “private” value of x will be discarded and it will revert to its previous “shared” and “persistent” value.

(37) In an embodiment, in the HTM commit the state of x changes twice. It becomes “shared”, i.e. visible, and at the same time it is also “logged”. In an embodiment, both changes happen atomically at a successful commit. After a successful commit, the HTM flushes the new value of x transparently to the NVM 101 and clears x. Clearing is first setting the commit record (indicator) to false, and in a second step unsetting the log mark. The log mark role is to verify an address is logged only by one transaction in the system and the restart process writes an address at most once by the last value that was written to the address by an HTM transaction. The log marks are an embodiment and not part of the claims in this patent. If there is a failure of the system 100 and restart thereof when x is “logged”, the processor 103 is configured to write the committed value of x in the log record of x to the Application Data area in the NVM and then to clear x.

(38) In an embodiment, the log record in the NVM 101 is not a typical sequential log. Instead, it can hold log records only for transactions that are either in-flight, or are committed by the HTM and their log records have not been recycled yet.

(39) As the person skilled in the art will appreciate, if the L1 cache 105 was non-volatile, HTM would be persistent as is without any further modifications. A restart event could abort the in-flight transactions, and a committed HTM transaction, while in the cache 105, would be instantly persistent and not require any logging. However, due to hardware limitations, e.g. fast wear out and slow writes of the NVM 101, the cache hierarchy will stay in volatile SRAM for the foreseeable future.

(40) As shown in FIG. 3, in an embodiment the successful commit of the transaction T.sub.k automatically sets the indicator, i.e. commit record of T.sub.k to true, as shown in FIG. 4. In an embodiment, this can be implemented by the processor 103 using a “tx_end_log(T.sub.k)” instruction. This instruction performs an HTM commit and sets the commit record of T.sub.k. FIG. 4 shows schematically the layout of the persistent footprint of the transaction T.sub.k in the NVM 101 according to an embodiment. It includes the “logged” indicated which can serve as the commit record of T.sub.k. The instruction “tx_end_log(T.sub.k)” writes the commit record in the NVM 101 and in addition sets the status of the writes of T.sub.k to “logged”.

(41) In an embodiment, the processor 103 is configured to flush modified data from the cache 105 to the NVM 103 by live transactions without aborting those transactions. During finalization of the transaction T, for instance, after the instruction “tx_end_log(T)”, i.e. after HTM commit, flushing of the application data, written by T from the cache 105 to the Application Data area in NVM 103 does not abort ongoing concurrent transactions that read this value. In an embodiment, these flushes do not generate any coherency request and do not invalidate the data in the case 105. Such operations are herein referred to as transparent flushes (TF) as they have no effect on the cache hierarchy and the HTM subsystem.

(42) In an embodiment, the processor 103 can provide an API for a HTM transaction including a “tx_start( )” and a “tx_end( )” function which start and commit an HTM transaction. Non-persistent HTM realizations include such functions. In persistent HTM “tx_start( )” is starting an HTM transaction, as in the volatile case, while “tx_end( )” is extended to flushing the transaction log records from the cache to the Log Records area in NVM, followed by a simultaneous HTM commit and indicator setting, called from an API such as “tx_end_log(T)” instruction, followed by flushing of the application data itself from cache to the Application Data area in NVM. In an embodiment, the machine store instructions can be replaced by a preprocessor with a function such as “tx_write(address, data, size)” function. The tx_write( )function creates a log record in the Log Records area in NVM, e.g. by non-temporal writes, and writes the application data to cache of the application data.

(43) In an embodiment, the log records and the size field that appear in the HTM transaction shown in FIG. 4 are flushed as part of the transaction, but not as part of the commit instruction. However, multiple writes to the same cache line can write to the same log record. Thus, in an embodiment, the log records are flushed only once before commit to prevent multiple flushes of the same data.

(44) In an embodiment, the processor 103 is configured to follow a best effort policy in the sense that the processor 103 does not supply a progress guarantee. As a result, after a certain number of aborts in the conventional volatile HTM, the transaction must take a global lock and commit. However with a NVM, a global lock is not enough as the tentative writes may have already contaminated memory. Therefore, in an embodiment an undo log entry is created for every volatile HTM write. In an alternative embodiment, a full redo log is created before the first value is written to the NVM 101. The first embodiment reduces read after write overhead.

(45) As already described above, with a volatile cache, such as the cache 105 shown in FIG. 1, and committed HTM transactions that accommodate all their writes in cache, in an embodiment the processor 103 is configured to log the writes in order to allow recovery in case a restart happened after HTM commit, when the writes were still volatile. In an embodiment, the processor 103 is configured such that all writes to the log reach the NVM 101 before an HTM commit, while all transactional writes stay in the cache 105. In an embodiment, the processor 103 is configured to flush the log to the NVM 101 without aborting the executing transaction, i.e. transparently, as already described above.

(46) In an embodiment, the processor 103 is configured such that logging can provide a restart process with the last committed value for each logged variable x. In an embodiment, the processor 103 is configured to attach a version to x. In an embodiment, the processor 103 is configured to verify that x is logged only once in the system 100. If the appearance of x in multiple logs is allowed, then the latest version of the log of x should be kept.

(47) In an embodiment, each address is allowed to appear at most in one log. To avoid instances of the same address in multiple logs, in an embodiment a volatile array of log marks, is added in which each memory address is mapped to one mark. In an embodiment, when a transaction is about to write x, it also marks x as logged. In an embodiment, until x is flushed, no other transaction is allowed to write it. The reason marks or indicators are used in an embodiment is to prevent a write to a variable that was already written to another transaction, but not yet flushed, so it is still logged. All other conflicts can be handled directly by the HTM. In an embodiment, the array of marks or indicators can be volatile, as in case of a restart it is known that the logged addresses are unique, and that the restart and recovery process do not create any new log records. After restart, a new and empty array of marks or indicators can be allocated according to an embodiment.

(48) In an embodiment, the writing of the marks or indicators is a part of a transaction, i.e. if the transaction T.sub.k writes x, it also marks x and in committing, the writing and the marking will take effect simultaneously as they are both transactional writes, while at abort, they are both canceled. In an embodiment, as long as the mark is set, the value of x, which appears in the log of T.sub.k, cannot be changed. Therefore, after x is flushed from the cache to the Application Data area in the NVM 101 and the commit record is set to false, the mark can be unset. It is important to emphasize that the transactional load instructions can ignore the marks and execute in full speed, which is a key advantage of HTM according to the present application as read transactions are processed in hardware speed.

(49) FIG. 4 shows the persistent structure of the log records of a transaction T according to an embodiment. In an embodiment, T has a Boolean commit record as shown in FIG. 4, which is set in tx_end_log. In an embodiment, the commit record is written by the HTM commit microcode, thus it should reside on the fastest available nonvolatile memory. In an embodiment, the transaction also has a unique ID which is stored in self_id. In an embodiment, the transaction has a set of log records. In an embodiment, each log record, as shown in FIG. 4, consists from the data in a modified cache line and the address of that line in system memory. In an embodiment, the maximal total size of the data is equal to the size of the L1 cache 105, which is the maximal size of written and, thus, logged, data. In an embodiment, the size field is the number of log records in the log of the transaction. In an embodiment, logged and size can be united, assuming if size is zero the transaction is not logged. However, for the sake of clarity here they are treated separately. In an embodiment, all of the Log Records area from FIG. 4, of T is flushed to the NVM 101 only once, so if a cache line is written multiple times in the same transaction, the data of this line is flushed to the log only once before the commit of T.

(50) In an embodiment, the DATA.ADDR field in the log record, which is the address and corresponding data of the application data in NVM, allows a restart process or a finalization to know which address and application data to write or flush. In an embodiment, the address is in a separate array, and not appended to the data, to avoid fragmentation of the cache. In an embodiment, a mapping of the address itself is used to occupy and free the mark in write instrumentation and finalization.

(51) While a particular feature or aspect of the invention may have been disclosed with respect to only one of several implementations or embodiments, such feature or aspect may be combined with one or more other features or aspects of the other implementations or embodiments as may be desired and advantageous for any given or particular application. Furthermore, to the extent that the terms “include”, “have”, “with”, or other variants thereof are used in either the detailed description or the claims, such terms are intended to be inclusive in a manner similar to the term “comprise”. Also, the terms “exemplary”, “for example” and “e.g.” are merely meant as an example, rather than the best or optimal. The terms “coupled” and “connected”, along with derivatives may have been used. It should be understood that these terms may have been used to indicate that two elements cooperate or interact with each other regardless whether they are in direct physical or electrical contact, or they are not in direct contact with each other.

(52) Although specific aspects have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that a variety of alternate and/or equivalent implementations may be substituted for the specific aspects shown and described without departing from the scope of the present invention. This application is intended to cover any adaptations or variations of the specific aspects discussed herein.

(53) Although the elements in the following claims are recited in a particular sequence with corresponding labeling, unless the claim recitations otherwise imply a particular sequence for implementing some or all of those elements, those elements are not necessarily intended to be limited to being implemented in that particular sequence.

(54) Many alternatives, modifications, and variations will be apparent to those skilled in the art in light of the above teachings. Of course, those skilled in the art readily recognize that there are numerous applications of the invention beyond those described herein. While the present invention has been described with reference to one or more particular embodiments, those skilled in the art recognize that many changes may be made thereto without departing from the scope of the present invention. It is therefore to be understood that within the scope of the appended claims and their equivalents, the invention may be practiced otherwise than as specifically described herein.