Browse Prior Art Database

Using Coupled Transactions to Traverse Large Data Structures Disclosure Number: IPCOM000226377D
Publication Date: 2013-Apr-01
Document File: 3 page(s) / 28K

Publishing Venue

The Prior Art Database


A method for using coupled transactions to traverse large data structures is disclosed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 49% of the total text.

Page 01 of 3

Using Coupled Transactions to Traverse Large Data Structures

Disclosed is a method for using coupled transactions to traverse large data structures.

Although hardware implementations of transactional memory (TM) are likely to ease design and construction of shared-memory parallel software, these hardware implementations usually impose limitations in the amount of data that can participate in a given transaction as well as the types of operations that may be performed within a transaction. Although there are many schemes for extending hardware transactional memory's (HTM's) reach, these schemes have drawbacks including reduced concurrency, increased overhead, and increased complexity, particularly in retry/contention-manager semantics.

The current state of the TM art provides the following categories of TM usage:

Small memory-only HTM transactions that are guaranteed to eventually succeed,


though they might suffer ephemeral failures due to contention, pages faults, interrupts, and the like. This usage permits TM to be used to break deadlock cycles in large lock-based software artifacts, and enjoys high concurrency, low overhead, and reasonably contained complexity.

Moderate memory-only HTM transactions that have a high probability of eventually


succeeding, but which, if presented with a set of variables occupying an unfortunate set of memory locations, will deterministically fail. This usage requires a software-based fallback in case of repeated failure, usually a lock-based fallback. When the software fallback is based on locks, this usage absolutely cannot be used to break deadlock cycles. When the software fallback is not based on locks, this usage can suffer from increased overhead and increased complexity.

Arbitrarily large memory-only transactions, possibly with some hardware support.


This usage is guaranteed to eventually succeed, however, attaining the same level of high concurrency and low overhead that fine-grained locking can achieve is currently a research topic, though much progress has been made over the past few years. One approach is to designate ``inevitable'' transactions that cannot be aborted, but the current prototypes of this approach greatly reduce the level of attainable concurrency.

There is therefore a need for a mechanism that permits limited HTM implementations to perform small memory-only manipulations on unbounded multi-linked data structures, in order to gain the benefits of HTM on large structures, while either eliminating or reducing the severity of the drawbacks normally associated with use of TM on large data structures. Figure 1 depicts an approach utilizing multiple transactions coupled with a pending-transaction counter in the object being modified.


Page 02 of 3

Figure 1

An example is shown in Figure 1 where, a mapping data structure transforms a key into a pointer to an object. At the instant in time represented in the figure, it is possible to map to objects 1, 4, 7, and 8. It is...