Back to results
US 8,789,060 B1Granted
Deterministic, parallel execution with overlapping regions
AssigneeCadence Design Systems, Inc.
InventorsKen Wadland, Charles W. Grant, Randall Lawson, Richard Allen Woodward, Jr., Sean Bergan
Life of this patent
Estimating the term…
Abstract
A method, computer program product and apparatus for utilizing simulated locking prior to starting concurrent execution are disclosed. The results of this simulated locking are used to define a canonical ordering which controls the order of execution and the degree of parallelism that can be used.
Claims18
A method for parallel processing comprising:
- decomposing a problem domain into at least a first task operating on a first region and a second task operating on a second region, in which the first region and the second region are subsets of data of a data set and overlap each other;
- analyzing the problem domain using simulated locking based at least in part upon the first region and the second region and the at least the first task and the second task;
- associating a first permit with the first task and a second permit with the second task, in which the first permit and the second permit respectively define what data to process for the first task and the second task;
- associating multiple regions with the first permit, in which the multiple regions include one or more goal regions, one or more writable regions, or one or more readable regions, wherein the one or more goal regions are a subset of the one or more writable regions which are a subset of the one or more readable regions;
- determining dispatch dependencies and a commit order of the first region and the second region based at least in part upon the simulated locking utilizing the second permit and the multiple regions associated with the first permit, rather than upon using one or more locks that block access to at least one of the first region and the second region until the one or more locks are released;
- and
- executing, by using a processor, the first task and the second task, which respectively operate on the first region and the second region that overlap each other, concurrently with the determined dispatch dependencies and the commit order.
4 more elements
An apparatus for parallel processing comprising:
- a processor that is to:
- decompose a problem domain into at least a first task operating on a first region and a second task operating on a second region, in which the first region and the second region are subsets of data of a data set and overlap each other;
- analyze the problem domain using simulated locking based at least in part upon the first region and the second region and at least the first task and the second task;
- associate a first permit with the first task and a second permit with the second task, in which the first permit and the second permit respectively define what data to process for the first task and the second task;
- associate multiple regions with the first permit, in which the multiple regions include one or more goal regions, one or more writable regions, or one or more readable regions, wherein the one or more goal regions are a subset of the one or more writable regions which are a subset of the one or more readable regions;
- determine dispatch dependencies and a commit order of the first region and the second region based at least in part upon the simulated locking utilizing the second permit and the multiple regions associated with the first permit, rather than upon using one or more locks that block access to at least one of the first region and the second region until the one or more locks are released;
- and
- execute the first task and the second task, which respectively operate on the first region and the second region that overlap each other, concurrently with the determined dispatch dependencies and the commit order.
5 more elements
A computer program product that includes a non-transitory computer-usable medium having a sequence of instructions which, when executed by a processor, causes the processor to execute a process for parallel processing, the process comprising:
- decomposing a problem domain into at least a first task operating on a first region and a second task operating on a second region, in which the first region and the second region are subsets of data of a data set and overlap each other;
- analyzing the problem domain using simulated locking based at least in part upon the first region and the second region and the at least the first task and the second task;
- associating a first permit with the first task and a second permit with the second task, in which the first permit and the second permit respectively define what data to process for the first task and the second task;
- associating multiple regions with the first permit, in which the multiple regions include one or more goal regions, one or more writable regions, or one or more readable regions, wherein the one or more goal regions are a subset of the one or more writable regions which are a subset of the one or more readable regions;
- determining dispatch dependencies and a commit order of the first region and the second region based at least in part upon the simulated locking utilizing the second permit and the multiple regions associated with the first permit, rather than upon using one or more locks that block access to at least one of the first region and the second region until the one or more locks are released;
- and
- executing the first task and the second task, which respectively operate on the first region and the second region that overlap each other, concurrently with the determined dispatch dependencies and the commit order.
4 more elements
Dependencies are inferred from the claim text.