# US 8,789,060 B1 · Deterministic, parallel execution with overlapping regions

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,789,060 B1
- Document ID: US8789060B1
- Status: Granted
- Kind: B1
- Application number: 11/965,695
- Filed: 2007-12-27
- Granted: 2014-07-22
- Earliest claimed: 2007-12-27
- Assignees: Cadence Design Systems, Inc.
- Applicants: Ken Wadland; Charles W. Grant; Randall Lawson; Richard Allen Woodward, Jr.; Sean Bergan
- Inventors: Ken Wadland; Charles W. Grant; Randall Lawson; Richard Allen Woodward, Jr.; Sean Bergan
- Web page: https://patentgrep.com/patent/US8789060B1

## CPC

- G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F 2209/484: Precedence
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, wherein the simulated locking further comprising:
determining if the first region or the second region is blocked;
setting the dispatch dependencies; and
determining a canonical order.

### Claim 3 (depends on 2)

The method of claim 2, further comprising: adding the set dispatch dependencies to the canonical ordering.

### Claim 4 (depends on 3)

The method of claim 3, further comprising controlling concurrency scheduling using the dispatch dependencies.

### Claim 5 (depends on 1)

The method of claim 1, further comprising making a run-time selection between deterministic and non-deterministic behavior for the first task and the second task respectively operating on the first region and the second region.

### Claim 6 (depends on 1)

The method of claim 1, wherein the problem domain comprises an application area of electronic design.

### Claim 7

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.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein the simulated locking further comprising:
a decision queue to determine if the first region or the second region is blocked;
a task queue to set the dispatch dependencies; and
a commit queue to determine a canonical order.

### Claim 9 (depends on 8)

The apparatus of claim 8, in which the processor adds the dispatch dependencies to the canonical ordering.

### Claim 10 (depends on 9)

The apparatus of claim 9, in which the dispatch dependencies controls concurrency scheduling.

### Claim 11 (depends on 7)

The apparatus of claim 7, in which the processor provides a run-time selection between deterministic and non-deterministic behavior for the first task and the second task respectively operating on the at least the first region and the second region.

### Claim 12 (depends on 7)

The apparatus of claim 7, wherein the problem area comprises an application area of electronic design.

### Claim 13

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.

### Claim 14 (depends on 13)

The product of claim 13, wherein the simulated locking further comprising:
determining if the first region or the second region is blocked;
setting the dispatch dependencies; and
determining a canonical order.

### Claim 15 (depends on 14)

The product of claim 14, further comprising:
adding the set dispatch dependencies to the canonical ordering.

### Claim 16 (depends on 15)

The product of claim 15, further comprising controlling concurrency scheduling using the dispatch dependencies.

### Claim 17 (depends on 13)

The product of claim 13, further comprising making a run-time selection between deterministic and non-deterministic behavior for the at least the first task and the second task respectively operating on the first region and the second.

### Claim 18 (depends on 13)

The product of claim 13, wherein the problem area comprises an application area of electronic design.