Sun Microsystems, Inc.

Microsoft Technology Licensing, LLC

Oracle America, Inc.

Microsoft Corporation

Hewlett-packard Development Company, L.p.

Computer Computer Corporation

David L Detlefs

Michael M Magruder

John Joseph Duffy

Vinod Grover

Goetz Graefe

Yosseff Levanoni

Antonios Printezis

Alexander T Garthwaite

Ole Agesen

Lingli Zhang

Weirong Zhu

Steven K Heller

Christine H Flood

Guy Lewis Steele, Jr

Paul A Martin

Mark S Moir

Nir N Shavit

Timothy Lawrence Harris

Ross Charles Knippel

Vance Palmer Morrison

David S Callahan

Brian M Grunkemeyer

Eric Dean Tribble

Sukhdeep S Sodhi

Fabio Rojas

Dana D Groff

Charles Gregory Nelson

James Benjamin Saxe

Derek R White

Xiaolan Zhang

Alex Garthwaite

Y Srinivas Ramakrishna

Jan Stephen Gray

Stephen Harris Toub

Victor M Luchangco

Martin Abadi

Maurice P Herlihy

Raja Krishnaswamy

Charles David Callahan, Ii

Peter B Kessler

David P Stoutamire

Alexander Dadiomov

Kenneth B Russell

Jon A Masamitsu

Simon Doherty

Surupa Biswas

Matthew B Tolton

Christopher William Dern

Carol Thompson Eidt

Kevin Bradley Frei

John W Coomes

V Krishna Nandivada

Y Srinivas Ramakrisha

William D Clinger

Bruce T Forstall

Vinod K Grover

A software transactional memory system implements a lightweight key-based action framework. The framework includes a set of unified application programming interfaces (APIs) exposed by an STM library that allow clients to implement actions that can be registered, queried, and updated using specific keys by transactions or transaction nests in STM code. Each action includes a key, state information, and a set of one or more callbacks that can be hooked to the validation, commit, abort, and/or re-execution phases of transaction execution. The actions extend the built-in concurrency controls of the STM system with customized control logics, support transaction nesting semantics, and enable integration with garbage collection systems.

Action framework in software transactional memory

Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. Multiple closed nested transactions are created for a single parent transaction, and the closed nested transactions are executed concurrently as parallel nested transactions. Various techniques are used to ensure effects of the parallel nested transactions are hidden from other transactions outside the parent transaction until the parent transaction commits. For example, retry is allowed to work correctly with parallel nested transactions. When a transaction that is a parallel nested transaction or a child transaction of the parallel nested transaction executes a retry, a read set of the transaction is registered for the retry. When a decision is made to propagate the retry past a parallel nested transaction parent of the transaction, keeping the read set registered and making the read set part of a parent read set.

Parallel nested transactions in transactional memory

A software transactional memory system is provided that creates an array of transactional locks for each array object that is accessed by transactions. The system divides the array object into non-overlapping portions and associates each portion with a different transactional lock. The system acquires transactional locks for transactions that access corresponding portions of the array object. By doing so, different portions of the array object can be accessed by different transactions concurrently. The system may use a shared shadow or undo copy for accesses to the array object.

Array object concurrency in STM

Software transactional memory (STM) primitives are provided that allow the results of prior open calls to be used by subsequent open calls either as-is or through another STM primitive that consumes the results of the previous invocation. The STM primitives are configured to ensure that the address of a shadow copy representing a memory location will not changed across a wide range of operations and thereby enable re-use of the shadow copy.

Primitives for software transactional memory

Embodiments are directed to implementing a generic SIMD data type in software code. In an embodiment, a computer system accesses a portion of software code that includes an algorithm with a generic SIMD data type that includes a variable number of elements. The algorithm with the generic SIMD data type is to be processed by a specific processor that includes various specific hardware features. The computer system determines at runtime a portion of customized processor-specific code that is to be used with the specified processor based on the generic SIMD data type, wherein the runtime determination resolves the number of elements that are to be used with the specified processor. The computer system also processes the software code including the algorithm with the generic SIMD data type using the determined, customized processor-specific code.

Type and length abstraction for data types

A hosted pre-compilation system is described herein that provides a way to enable ahead-of-time compilation for managed code running inside a host. The host triggers ahead-of-time compilation at application runtime, after any configuration settings are available. The host can choose which modules to compile, when to compile them, and where to persist the generated images. Upon detecting a module load, the host can trigger pre-compilation, provide the loader an existing pre-compiled image of the module, or do nothing. The runtime/platform validates the integrity of any host-supplied pre-compiled image and provides application programming interfaces (APIs) to inform the host when an image becomes invalid and fails to load. The platform also provides APIs to let the host trigger compilation of binaries at any time relevant to the host, and to generate the images either synchronously or in a background process.

Pre-compiling hosted managed code

A compiler is provided that determines when the use of software transactional memory (STM) primitives may be optimized with respect to a set of collectively dominating STM primitives. The compiler analysis coordinates the use of variables containing possible shadow copy pointers to allow the analysis to be performed for both direct write and buffered write STM systems. The coordination of the variables containing the possible shadow copy pointers ensures that the results of STM primitives are properly reused. The compiler analysis identifies memory accesses where STM primitives may be eliminated, combined, or substituted for lower overhead STM primitives.

Optimizing primitives in software transactional memory

A dynamic race detection system is provided that detects race conditions in code that executes concurrently in a computer system. The dynamic race detection system uses a modified software transactional memory (STM) system to detect race conditions. A compiler converts portions of the code that are not configured to operate with the STM system into pseudo STM code that operates with the STM system. The dynamic race detection system detects race conditions in response to either a pseudo STM transaction in the pseudo STM code failing to validate when executed or an actual STM transaction failing to validate when executed because of conflict with a concurrent pseudo STM transaction.

Detecting race conditions with a software transactional memory system

A software transactional memory (STM) system allows the composition of traditional lock based synchronization with transactions in STM code. The STM system acquires each traditional lock the first time that a corresponding traditional lock acquire is encountered inside a transaction and defers all traditional lock releases until a top level transaction in a transaction nest commits or aborts. The STM system maintains state information associated with traditional lock operations in transactions and uses the state information to eliminate deferred traditional lock operations that are redundant. The STM system integrates with systems that implement garbage collection.

Composition of locks in software transactional memory

A software transactional memory system is provided with overflow handling. The system includes a global version counter with an epoch number and a version number. The system accesses the global version counter prior to and subsequent to memory accesses of transactions to validate read accesses of the transaction. The system includes mechanisms to detect global version number overflow and may allow some or all transactions to execute to completion subsequent to the global version number overflowing. The system also provides publication, privatization, and granular safety properties.

STM with global version overflow handling

Various technologies and techniques are disclosed that provide software transactional protection of managed pointers. A software transactional memory system interacts with and/or includes a compiler. At compile time, the compiler determines that there are one or more reference arguments in one or more code segments being compiled whose source cannot be recovered. The compiler executes a procedure to select one or more appropriate techniques or combinations thereof for communicating the sources of the referenced variables to the called code segments to ensure the referenced variables can be recovered when needed. Some examples of these techniques include a fattened by-ref technique, a static fattening technique, a dynamic ByRefInfo type technique, and others. One or more combinations of these techniques can be used as appropriate.

Software transactional protection of managed pointers

Various technologies and techniques are disclosed for providing type stability techniques to enhance contention management. A reference counting mechanism is provided that enables transactions to safely examine states of other transactions. Contention management is facilitated using the reference counting mechanism. When a conflict is detected between two transactions, owning transaction information is obtained. A reference count of the owning transaction is incremented. The system ensures that the correct transaction was incremented. If the owning transaction is still a conflicting transaction, then a contention management decision is made to determine proper resolution. When the decision is made, the reference count on the owning transaction is decremented by the conflicting transaction. When each transaction completes, the reference counts it holds to itself is decremented. Data structures cannot be deallocated until their reference count is zero. Dedicated type-stable allocation pools can be reduced using an unstable attribute.

Using type stability to facilitate contention management

Handling parallelism in transactions. A method includes beginning a cache resident transaction. The method further includes encountering a nested structured parallelism construct within the cache resident transaction. A determination is made as to whether the transaction would run faster serially in cache resident mode or faster parallel in software transactional memory mode for the overall transaction. In the software transactional memory mode, cache resident mode is used for one or more hierarchically lower nested transactions. The method further includes continuing the transaction in the mode determined.

Accelerating parallel transactions using cache resident transactions

Growing community of inventors

Westford, MA, United States of America

David L Detlefs