Patent application number | Description | Published |
20080256074 | EFFICIENT IMPLICIT PRIVATIZATION OF TRANSACTIONAL MEMORY - Apparatus, methods, and program products are disclosed that provide a technology that implicitly isolates a portion of a transactional memory that is shared between multiple threads for exclusive use by an isolating thread without the possibility of other transactions modifying the isolated portion of the transactional memory. | 10-16-2008 |
20090031309 | System and Method for Split Hardware Transactions - A split hardware transaction may split an atomic block of code to be executed using multiple hardware transactions, while logically taking effect as a single atomic transaction. A split hardware transaction may use software to combine the multiple hardware transactions into one logically atomic operation. In some embodiments, a split hardware transaction may allow execution of atomic blocks including non-hardware-transactionable (NHT) operations without resorting to exclusively software transactions. A split hardware transaction may maintain a thread-local buffer logs all memory accesses performed by the split hardware transaction. A split hardware transaction may use a hardware transaction to copy values read from shared memory locations into a local memory buffer. To execute a non-hardware-transactionable operation, the split hardware transaction may commit the active hardware transaction, execute the non-hardware-transactionable operation, and then initiate a new hardware transaction to execute the rest of the atomic block. | 01-29-2009 |
20090031310 | System and Method for Executing Nested Atomic Blocks Using Split Hardware Transactions - Split hardware transaction techniques may support execution of serial and parallel nesting of code within an atomic block to an arbitrary nesting depth. An atomic block including child code sequences nested within a parent code sequence may be executed using separate hardware transactions for each child, but the execution of the parent code sequence, the child code sequences, and other code within the atomic block may appear to have been executed as a single transaction. If a child transaction fails, it may be retried without retrying the parent code sequence or other child code sequences. Before a child transaction is executed, a determination of memory consistency may be made. If a memory inconsistency is detected, the child transaction may be retried or control may be returned to its parent. Memory inconsistencies between parallel child transactions may be resolved by serializing their execution before retrying at least one of them. | 01-29-2009 |
20090125548 | System and Method for Implementing Shared Scalable Nonzero Indicators - A Scalable NonZero Indicator (SNZI) object in a concurrent computing application may include a shared data portion (e.g., a counter portion) and a shared nonzero indicator portion, and/or may be an element in a hierarchy of SNZI objects that filters changes in non-root nodes to a root node. SNZI objects may be accessed by software applications through an API that includes a query operation to return the value of the nonzero indicator, and arrive (increment) and depart (decrement) operations. Modifications of the data portion and/or the indicator portion may be performed using atomic read-modify-write type operations. Some SNZI objects may support a reset operation. A shared data object may be set to an intermediate value, or an announce bit may be set, to indicate that a modification is in progress that affects its corresponding indicator value. Another process or thread seeing this indication may “help” complete the modification before proceeding. | 05-14-2009 |
20090132563 | SIMPLE OPTIMISTIC SKIPLIST - Apparatus, methods, and computer program products are disclosed for concurrently searching a memory containing a skiplist data structure. The method locates the skiplist data structure in the memory. The skiplist data structure includes a plurality of linked lists related by a skiplist invariant. Furthermore, the plurality of linked lists includes a first-level linked list and one or more higher-level linked lists. The skiplist data structure also includes a plurality of nodes, each of which includes a key field, at least one pointer field, and a lock field, respectively. Each of the plurality of nodes is linked to the first-level linked list through the at least one pointer field and ordered responsive to the key field. The method performs a search operation on the skiplist data structure, while the skiplist data structure is subject to concurrent alteration of the plurality of nodes by a plurality of execution threads that are configured to maintain the skiplist invariant and returns a result of the search operation. | 05-21-2009 |
20100042584 | CONCURRENT LOCK-FREE SKIPLIST WITH WAIT-FREE CONTAINS OPERATOR - Apparatus, methods, and computer program products are disclosed for performing a wait-free search of a concurrent, lock-free skiplist to determine existence of a sought-after key. | 02-18-2010 |
20100042997 | CONDITIONED SCALABLE NON-ZERO INDICATOR - Apparatus, methods, and computer-program products are disclosed for performing an Arrive operation on a concurrent hierarchical Scalable Non-Zero Indicator (SNZI) object wherein the concurrent hierarchical SNZI object is a conditioned-SNZI (CSNZI) object that includes a parent CSNZI node. The method invokes a parent Arrive operation on the parent CSNZI node and returns an arrive failure status if the CSNZI object is disabled. | 02-18-2010 |
20100241774 | SCALABLE READER-WRITER LOCK - A reader-writer lock is provided that scales to accommodate multiple readers without contention. The lock comprises a hierarchical C-SNZI (Conditioned Scalable Non-Zero Indicator) structure that scales with the number readers seeking simultaneous acquisition of the lock. All readers that have joined the C-SNZI structure share concurrent acquisition, and additional readers may continue to join until the structure is disabled. The lock may be disabled by a writer, at which time subsequent readers will wait (e.g., in a wait queue) until the lock is again available. The C-SNZI structure may be implemented in a lockword or in reader entries within a wait queue. If implemented in reader entries of a wait queue, the lockword may be omitted, and new readers arriving at the queue may be able join an existing reader entry even if the reader entry is not at the tail of the queue. | 09-23-2010 |
20110078385 | System and Method for Performing Visible and Semi-Visible Read Operations In a Software Transactional Memory - The software transactional memory system described herein may implement a revocable mechanism for managing read ownership in a shared memory. In this system, write ownership may be revoked by readers or writers at any time other than when a writer transaction is in a commit state, wherein its write ownership is irrevocable. An ownership record associated with one or more locations in the shared memory may include an indication of whether the memory locations are owned for writing, and an identifier of the latest writer. A read ownership array may record data indicating which, if any, threads currently own the memory locations for reading. The system may provide an efficient read-validation operation, in which a full read-set validation is avoided unless a change in a global read-write conflict counter value indicates a potential conflict. The system may support a wide range of contention management policies, and may provide implicit privatization. | 03-31-2011 |