Joe Duffy

A method of providing access to a dataset in a type-safe manner includes storing a dataset including a plurality of data elements and a corresponding plurality of order keys for indicating an ordering of the data elements. Each order key is associated with one of the data elements. An interface to the dataset is generated that is parameterized by an element type parameter and a key type parameter. The interface is configured to provide access to the data elements and the order keys in the… Show more

A method of providing access to a dataset in a type-safe manner includes storing a dataset including a plurality of data elements and a corresponding plurality of order keys for indicating an ordering of the data elements. Each order key is associated with one of the data elements. An interface to the dataset is generated that is parameterized by an element type parameter and a key type parameter. The interface is configured to provide access to the data elements and the order keys in the dataset in a type-safe manner. Show less

Various technologies and techniques are disclosed for providing concurrent exception handling. When one or more exceptions are received from concurrent workers, one or more exception handler functions are supplied. For each respective exception in the exception results, determine if the respective exception is one of a kind of exceptions handled by the one or more exception handler functions. If the respective exception is one of a kind handled by the exception handler functions, then run a… Show more

Various technologies and techniques are disclosed for providing concurrent exception handling. When one or more exceptions are received from concurrent workers, one or more exception handler functions are supplied. For each respective exception in the exception results, determine if the respective exception is one of a kind of exceptions handled by the one or more exception handler functions. If the respective exception is one of a kind handled by the exception handler functions, then run a particular handler of the exception handler functions and mark the respective exception as handled. Any unhandled exceptions are then processed appropriately. In one implementation, a collection of input data is processed to produce a collection of output results, with the exceptions being interleaved with other output results. In another implementation, a particular exception is selected that represents the multiple exceptions. The selected one particular exception is then thrown. Show less

Transactional memory compatibility type attributes are associated with intermediate language code to specify, for example, that intermediate language code must be run within a transaction, or must not be run within a transaction, or may be run within a transaction. Attributes are automatically produced while generating intermediate language code from annotated source code. Default rules also generate attributes. Tools use attributes to statically or dynamically check for incompatibility between… Show more

Transactional memory compatibility type attributes are associated with intermediate language code to specify, for example, that intermediate language code must be run within a transaction, or must not be run within a transaction, or may be run within a transaction. Attributes are automatically produced while generating intermediate language code from annotated source code. Default rules also generate attributes. Tools use attributes to statically or dynamically check for incompatibility between intermediate language code and a transactional memory implementation. Show less

A method of analyzing a data parallel query includes receiving a user-specified data parallel query that includes a plurality of query operators. An operator type for each of the query operators is identified based on a type of parallel input data structure the operator operates on and a type of parallel output data structure the operator outputs. It is determined whether the query is a prohibited query based on the identified operator types.

The present invention extends to methods, systems, and computer program products for a structured task hierarchy for a parallel runtime. The parallel execution runtime environment permits flexible spawning and attachment of tasks to one another to form a task hierarchy. Parent tasks can be prevented from completing until any attached child sub-tasks complete. Exceptions can be aggregated in an exception array such that any aggregated exceptions for a task are available when the task completes… Show more

The present invention extends to methods, systems, and computer program products for a structured task hierarchy for a parallel runtime. The parallel execution runtime environment permits flexible spawning and attachment of tasks to one another to form a task hierarchy. Parent tasks can be prevented from completing until any attached child sub-tasks complete. Exceptions can be aggregated in an exception array such that any aggregated exceptions for a task are available when the task completes. A shield mode is provided to prevent tasks from attaching to another task as child tasks. Show less

A method includes creating a first task group. A plurality of task object representations are added to the first task group. Each representation corresponds to one task object in a first plurality of task objects. A wait operation is performed on the first task group that waits for at least one of the task objects in the first plurality of task objects to complete.

A method of providing lock-based access to nodes in a concurrent linked list includes providing a plurality of striped lock objects. Each striped lock object is configured to lock at least one of the nodes in the concurrent linked list. An index is computed based on a value stored in a first node to be accessed in the concurrent linked list. A first one of the striped lock objects is identified based on the computed index. The first striped lock object is acquired, thereby locking and providing… Show more

A method of providing lock-based access to nodes in a concurrent linked list includes providing a plurality of striped lock objects. Each striped lock object is configured to lock at least one of the nodes in the concurrent linked list. An index is computed based on a value stored in a first node to be accessed in the concurrent linked list. A first one of the striped lock objects is identified based on the computed index. The first striped lock object is acquired, thereby locking and providing protected access to the first node. Show less

Various technologies and techniques are disclosed for handling data parallel operations. Data parallel operations are composed together to create a more complex data parallel operation. A fusion plan process is performed on a particular complex operation dynamically at runtime. As part of the fusion plan process, an analysis is performed of a structure of the complex operation and input data. One particular algorithm that best preserves parallelism is chosen from multiple algorithms. The… Show more

Various technologies and techniques are disclosed for handling data parallel operations. Data parallel operations are composed together to create a more complex data parallel operation. A fusion plan process is performed on a particular complex operation dynamically at runtime. As part of the fusion plan process, an analysis is performed of a structure of the complex operation and input data. One particular algorithm that best preserves parallelism is chosen from multiple algorithms. The structure of the complex operation is revised based on the particular algorithm chosen. A nested complex operation can also be fused, by inlining its contents into an outer complex operation so that parallelism is preserved across nested operation boundaries. Show less

A parallel execution of a query is performed with a plurality of producers using a partitioned data source, thereby producing output data. The output data is consumed with at least one consumer. The at least one consumer is monitored. A determination is made whether to stop producing output data by at least one of the producers prior to completion of the execution of the query based on the monitoring.

Target data is allocated into caches of a shared-memory multiprocessor system during a runtime environment. The target data includes a plurality of data items that are allocated onto separate cache lines. Each data item is allocated on a separate cache line regardless of the size of the cache line of the system. The data items become members of a wrapper types when data items are value types. The runtime environment maintains a set of wrapper types of various sizes that are of typical cache… Show more

Target data is allocated into caches of a shared-memory multiprocessor system during a runtime environment. The target data includes a plurality of data items that are allocated onto separate cache lines. Each data item is allocated on a separate cache line regardless of the size of the cache line of the system. The data items become members of a wrapper types when data items are value types. The runtime environment maintains a set of wrapper types of various sizes that are of typical cache line sizes. Garbage data is inserted into the cache line in cases where data items are reference types and data is stored on a managed heap. The allocation also configures garbage collectors in the runtime environment not to slide multiple data items onto the same cache line. Other examples are included where a developer can augment the runtime environment to be aware of cache line sizes. Show less

Various technologies and techniques are disclosed for providing concurrent exception handling. Exceptions that occur in concurrent workers are caught. The caught exceptions are then forwarded from the concurrent workers to a coordination worker. The caught exceptions are finally aggregated into an aggregation structure, such as an aggregate exception object. This aggregation structure is rethrown and the individual caught exceptions may then be handled at a proper time.

Various technologies and techniques are disclosed for preserving input element ordering in data parallel operations. This ordering may be based on element ordinal position in the input or a programmer-specified key-selection routine that generates sortable keys for each input element. Complex data parallel operations are re-written to contain individual data parallel operations that introduce partitioning and merging. Each partition is then processed independently in parallel. The system… Show more

Various technologies and techniques are disclosed for preserving input element ordering in data parallel operations. This ordering may be based on element ordinal position in the input or a programmer-specified key-selection routine that generates sortable keys for each input element. Complex data parallel operations are re-written to contain individual data parallel operations that introduce partitioning and merging. Each partition is then processed independently in parallel. The system ensures that downstream operations remember ordering information established by certain other operations, using techniques that vary depending upon which categories the consumer operations are in. Data is merged back into one output stream using a final merge process that is aware of the ordering established among data elements. Show less

Various technologies and techniques are disclosed for transforming a sequential loop into a parallel loop for use with a transactional memory system. Open ended and/or closed ended sequential loops can be transformed to parallel loops. For example, a section of code containing an original sequential loop is analyzed to determine a fixed number of iterations for the original sequential loop. The original sequential loop is transformed into a parallel loop that can generate transactions in an… Show more

Various technologies and techniques are disclosed for transforming a sequential loop into a parallel loop for use with a transactional memory system. Open ended and/or closed ended sequential loops can be transformed to parallel loops. For example, a section of code containing an original sequential loop is analyzed to determine a fixed number of iterations for the original sequential loop. The original sequential loop is transformed into a parallel loop that can generate transactions in an amount up to the fixed number of iterations. As another example, an open ended sequential loop can be transformed into a parallel loop that generates a separate transaction containing a respective work item for each iteration of a speculation pipeline. The parallel loop is then executed using the transactional memory system, with at least some of the separate transactions being executed on different threads. Show less

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… Show more

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. Show less

Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. For example, pessimistic reads are supported. A pessimistic duplication detection data structure is created for a parallel nested transaction. An entry is made into the data structure for each pessimistic read in the parallel nested transaction. When committing the parallel nested transaction, new pessimistic read locks are passed to an immediate parent, and an entry… Show more

Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. For example, pessimistic reads are supported. A pessimistic duplication detection data structure is created for a parallel nested transaction. An entry is made into the data structure for each pessimistic read in the parallel nested transaction. When committing the parallel nested transaction, new pessimistic read locks are passed to an immediate parent, and an entry is made into a separate pessimistic duplication detection data structure of the immediate parent with synchronization between sibling transactions. The pessimistic duplication detection data structures can also be used for upgrades from pessimistic reads to write locks. Retry operations are supported with parallel nested transactions. Write abort compensation maps can be used with parallel nested transactions to detect and handle falsely doomed parent transactions. Show less

Various technologies and techniques are disclosed that support buffered writes and enforced serialization order in a software transactional memory system. A buffered write process is provided that performs writes to shadow copies of objects and writes content back to the objects after validating a respective transaction during commit. When a write lock is first obtained for a particular transaction, a shadow copy is made of a particular object. Writes are performed to and reads from the shadow… Show more

Various technologies and techniques are disclosed that support buffered writes and enforced serialization order in a software transactional memory system. A buffered write process is provided that performs writes to shadow copies of objects and writes content back to the objects after validating a respective transaction during commit. When a write lock is first obtained for a particular transaction, a shadow copy is made of a particular object. Writes are performed to and reads from the shadow copy. After validating the particular transaction during commit, content is written from the shadow copy to the particular object. A transaction ordering process is provided that ensures that an order in which the transactions are committed matches an abstract serialization order of the transactions. Transactions are not allowed to commit until their ticket number matches a global number that tracks the next transaction that should commit. Show less

Various technologies and techniques are disclosed for detecting falsely doomed parent transactions of nested children in transactional memory systems. When rolling back nested transactions, a release count is tracked each time that a write lock is released due to rollback for a given nested transaction. For example, a write abort compensation map can be used to track the release count for each nested transaction. The number of times the nested transactions releases a write lock is recorded in… Show more

Various technologies and techniques are disclosed for detecting falsely doomed parent transactions of nested children in transactional memory systems. When rolling back nested transactions, a release count is tracked each time that a write lock is released due to rollback for a given nested transaction. For example, a write abort compensation map can be used to track the release count for each nested transaction. The number of times the nested transactions releases a write lock is recorded in their respective write abort compensation map. The release counts can be used during a validation of a parent transaction to determine if a failed optimistic read is really valid. If an aggregated release count for the nested children transactions accounts for the difference in version numbers exactly, then the optimistic read is valid. Show less

Various technologies and techniques facilitate stack read and write operations in a software transactional memory system. If the compiler determines that an address for a variable in a code segment is a stack location, the stack location is live on entry, and the address of the variable has not been taken and passed to another thread, the code is changed to ensure failure atomicity. One example includes modifying the code so a shadow copy is saved for local variables that are live on entry. If… Show more

Various technologies and techniques facilitate stack read and write operations in a software transactional memory system. If the compiler determines that an address for a variable in a code segment is a stack location, the stack location is live on entry, and the address of the variable has not been taken and passed to another thread, the code is changed to ensure failure atomicity. One example includes modifying the code so a shadow copy is saved for local variables that are live on entry. If the same prior criteria are true except the stack location is not live on entry, the code is optimized by ensuring code for logging and software transactional memory operations are not included. If the compiler does not know the address is the stack location or that the address is not passed to another thread, the code is changed to ensure failure and concurrency atomicity.
Show less

Various technologies and techniques are disclosed for implementing retrying transactions in a transactional memory system. The system allows a transaction to execute a retry operation. The system registers for waits on every read in a read set of the retrying transaction. The retrying transaction waits for notification that something in the read set has changed. A transaction knows if notification is required in one of two ways. If the transactional memory word contained a waiters bit during… Show more

Various technologies and techniques are disclosed for implementing retrying transactions in a transactional memory system. The system allows a transaction to execute a retry operation. The system registers for waits on every read in a read set of the retrying transaction. The retrying transaction waits for notification that something in the read set has changed. A transaction knows if notification is required in one of two ways. If the transactional memory word contained a waiters bit during write lock acquisition, then during release the transactional memory word is looked up in an object waiters map, and waiting transactions are signaled. If a writing transaction finds a global count of waiting transactions to be greater than zero after releasing write locks, a transaction waiters map is used to determine which waiting transactions need to be signaled. In each case, the write lock is released using a normal store operation. Show less

Various technologies and techniques are disclosed for handling exceptions in sequential statements that are executed in parallel. A transactional memory system is provided with a contention manager. The contention manager is responsible for managing exceptions that occur within statements that were designed to be executed in an original sequential order, and that were transformed into ordered transactions for speculative execution in parallel. The contention manager ensures that any exceptions… Show more

Various technologies and techniques are disclosed for handling exceptions in sequential statements that are executed in parallel. A transactional memory system is provided with a contention manager. The contention manager is responsible for managing exceptions that occur within statements that were designed to be executed in an original sequential order, and that were transformed into ordered transactions for speculative execution in parallel. The contention manager ensures that any exceptions that are thrown from one or more speculatively executed blocks while the statements are being executed speculatively in parallel are handled in the original sequential order. Show less

Various technologies and techniques are disclosed for providing concurrent exception handling. When one or more exceptions are received from concurrent workers, one or more exception handler functions are supplied. For each respective exception in the exception results, determine if the respective exception is one of a kind of exceptions handled by the one or more exception handler functions. If the respective exception is one of a kind handled by the exception handler functions, then run a… Show more

Various technologies and techniques are disclosed for providing concurrent exception handling. When one or more exceptions are received from concurrent workers, one or more exception handler functions are supplied. For each respective exception in the exception results, determine if the respective exception is one of a kind of exceptions handled by the one or more exception handler functions. If the respective exception is one of a kind handled by the exception handler functions, then run a particular handler of the exception handler functions and mark the respective exception as handled. Any unhandled exceptions are then processed appropriately. In one implementation, a collection of input data is processed to produce a collection of output results, with the exceptions being interleaved with other output results. In another implementation, a particular exception is selected that represents the multiple exceptions. The selected one particular exception is then thrown. Show less

Various technologies and techniques are disclosed that improve implementation of concurrency control modes in a transactional memory system. A transactional memory word is provided for each piece of data. The transactional memory word includes a version number, a reader indicator, and an exclusive writer indicator. The transactional memory word is analyzed to determine if the particular concurrency control mode is proper. Using the transactional memory word to help with concurrency control… Show more

Various technologies and techniques are disclosed that improve implementation of concurrency control modes in a transactional memory system. A transactional memory word is provided for each piece of data. The transactional memory word includes a version number, a reader indicator, and an exclusive writer indicator. The transactional memory word is analyzed to determine if the particular concurrency control mode is proper. Using the transactional memory word to help with concurrency control allows multiple combinations of operations to be performed against the same memory location simultaneously and/or from different transactions. For example, a pessimistic read operation and an optimistic read operation can be performed against the same memory location. Show less

Various technologies and techniques are disclosed for providing a software transactional memory system that supports allocation and use of finalizable objects inside transactions. By supporting such finalizable object usage inside a software transactional memory system, correct behavior is maintained when a garbage collector must determine when a particular one or more of the objects are eligible for finalization. A to-be-finalized set is provided for a transaction. An object is placed into the… Show more

Various technologies and techniques are disclosed for providing a software transactional memory system that supports allocation and use of finalizable objects inside transactions. By supporting such finalizable object usage inside a software transactional memory system, correct behavior is maintained when a garbage collector must determine when a particular one or more of the objects are eligible for finalization. A to-be-finalized set is provided for a transaction. An object is placed into the to-be-finalized set for the transaction whenever a finalizable object is allocated within the transaction. A finalize indicator is set for each object in the to-be-finalized set at an appropriate time to indicate that the objects are eligible for finalization. For example, if the transaction is ready to commit and the transaction is an open transaction, then the to-be-finalized set is traversed and a finalize indicator is set for each object to indicate they are eligible for finalization. Show less

A method of translating a comprehension into executable code for execution on a SIMD (Single Instruction, Multiple Data stream) execution unit, includes receiving a user specified comprehension. The comprehension is compiled into a first set of executable code. An intermediate representation is generated based on the first set of executable code. The intermediate representation is translated into a second set of executable code that is configured to be executed by a SIMD execution unit.

Various technologies and techniques are disclosed that improve implementation of concurrency control modes in a transactional memory system. A transactional memory word is provided for each piece of data. The transactional memory word includes a version number, a reader indicator, and an exclusive writer indicator. The transactional memory word is analyzed to determine if the particular concurrency control mode is proper. Using the transactional memory word to help with concurrency control… Show more

Various technologies and techniques are disclosed that improve implementation of concurrency control modes in a transactional memory system. A transactional memory word is provided for each piece of data. The transactional memory word includes a version number, a reader indicator, and an exclusive writer indicator. The transactional memory word is analyzed to determine if the particular concurrency control mode is proper. Using the transactional memory word to help with concurrency control allows multiple combinations of operations to be performed against the same memory location simultaneously and/or from different transactions. For example, a pessimistic read operation and an optimistic read operation can be performed against the same memory location. Show less

The subject disclosure pertains to systems and methods for supporting null capabilities for general purpose programming languages. Low level, runtime support for a nullable type is provided to ensure consistency and coherency. An execution component restricts support of the nullable type to programming language types that lack a null capability. The execution component may also provide support for conversion between the nullable type and a reference type.

Various technologies and techniques are disclosed for applying ordering to transactions in a software transactional memory system. A software transactional memory system is provided with a feature to allow a pre-determined commit order to be specified for a plurality of transactions. The pre-determined commit order is used at runtime to aid in determining an order in which to commit the transactions in the software transactional memory system. A contention management process is invoked when a… Show more

Various technologies and techniques are disclosed for applying ordering to transactions in a software transactional memory system. A software transactional memory system is provided with a feature to allow a pre-determined commit order to be specified for a plurality of transactions. The pre-determined commit order is used at runtime to aid in determining an order in which to commit the transactions in the software transactional memory system. A contention management process is invoked when a conflict occurs between a first transaction and a second transaction. The pre-determined commit order is used in the contention management process to aid in determining whether the first transaction or the second transaction should win the conflict and be allowed to proceed. Show less