# US 2014/0198110 A1 · Reducing the number of sequential operations in an application to be performed on a shared memory cell

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

- Number: US 2014/0198110 A1
- Document ID: US20140198110A1
- Status: Published application
- Kind: A1
- Application number: 13/997,056
- Filed: 2011-12-28
- Published: 2014-07-17
- Earliest claimed: 2011-12-28
- Assignees: Intel Corporation
- Inventors: Tomasz Janczak; Marek Targowski
- Web page: https://patentgrep.com/patent/US20140198110A1

## CPC

- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06F 9/4552: {Involving translation to a different instruction set architecture, e.g. just-in-time translation in a JVM}
- G06F 9/526: {Mutual exclusion algorithms}
- G06F 13/1605: {based on arbitration (arbitration in handling access to a common bus or bus system G06F13/36)}
- G06T 1/60: Memory management
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and apparatuses to reduce the number of sequential operations such as atomic operations in an application to be performed on a shared memory cell may be provided. A translation unit can detect in the application multiple atomic operations to be performed on the same memory and replaces the multiple atomic operations with an equivalent single atomic operation. In some implementations, the application includes shader code. In some implementations, each of the multiple atomic operations increment a value stored at the same memory by an update amount. The translation unit may calculate the partial prefix sum over all the atomic operations and replace the multiple atomic operations with a single atomic operation to increment the value stored at memory by the sum of the update amounts.

## Claims

### Claim 1

A system comprising:
a storage device to store an application;
a central processor to load the application from the storage device to a translation unit;
a graphics driver including the translation unit and a compiler, the translation unit to detect in the application a plurality of atomic operations to be performed on a memory and replace the plurality of atomic operations in the application with an equivalent single atomic operation to produce a translated application and the compiler to compile the translated application; and
a graphics processor to execute the translated application.

### Claim 2 (depends on 1)

The system of claim 1, wherein the application includes shader code.

### Claim 3 (depends on 1)

The system of claim 1, wherein each of the plurality of atomic operations increments a value stored in the memory by an update amount.

### Claim 4 (depends on 3)

The system of claim 3, wherein the translation unit is further configured to compute a localized partial prefix sum of the update amounts up to a SIMD execution engine length.

### Claim 5 (depends on 3)

The system of claim 3, wherein the translation unit is configured to replace the plurality of atomic operations in the application with an atomic operation to increment the value stored in the memory by an amount equal to a sum of the update amounts.

### Claim 6 (depends on 2)

The system of claim 2, wherein the compiler includes a just-in-time compiler.

### Claim 7 (depends on 1)

The system of claim 1, wherein the graphics processor includes a SIMD architecture.

### Claim 8

A computer implemented method comprising:
detecting in an application a plurality of atomic operations to be performed on a memory;
replacing the plurality of atomic operations in the application with an equivalent single atomic operation to produce a translated application; and
compiling the translated application.

### Claim 9 (depends on 8)

The computer implemented method of claim 8, wherein the application includes shader code.

### Claim 10 (depends on 8)

The computer implemented method of claim 8, wherein each of the plurality of atomic operations increments a value stored in the memory by an update amount.

### Claim 11 (depends on 10)

The computer implemented method of claim 10, further including computing a localized partial prefix sum of the update amounts up to a SIMD execution engine length.

### Claim 12 (depends on 10)

The computer implemented method of claim 10, wherein replacing the plurality of atomic operations in the application with an equivalent single atomic operation includes replacing the plurality of atomic operations in the application with an atomic operation to increment the value stored in the memory by an amount equal to a sum of the update amounts.

### Claim 13 (depends on 8)

The computer implemented method of claim 8, further including executing the translated application.

### Claim 14

A computer readable medium comprising a set of instructions which, if executed by a processor, cause a computer to:
detect in an application a plurality of atomic operations to be performed on a memory;
replace the plurality of atomic operations in the application with an equivalent single atomic operation to produce a translated application; and
compile the translated application.

### Claim 15 (depends on 14)

The computer readable medium of claim 14, wherein the application includes shader code.

### Claim 16 (depends on 14)

The computer readable medium of claim 14, wherein each of the plurality of atomic operations increments a value stored in the memory by an update amount.

### Claim 17 (depends on 16)

The computer readable medium of claim 16, wherein the instructions, if executed, cause a computer to compute a localized partial prefix sum of the update amounts up to a SIMD execution engine length.

### Claim 18 (depends on 16)

The computer readable medium of claim 16, wherein replacing the plurality of atomic operations in the application with an equivalent single atomic operation is to include replacing the plurality of atomic operations in the application with an atomic operation to increment the value stored in the memory by an amount equal to a sum of the update amounts.

### Claim 19 (depends on 17)

The computer readable medium of claim 17, wherein the instructions, if executed, cause a computer to compute partial prefix sums of the plurality of update amounts are outside a critical section.

### Claim 20 (depends on 14)

The computer readable medium of claim 14, wherein the instructions, if executed, cause a computer to execute the translated application.

### Claim 21

A system comprising:
a storage device to store an application;
a translation unit configured to detect in the application a plurality of atomic operations to be performed on a memory and replace the plurality of atomic operations in the application with an equivalent single atomic operation to produce a translated application; and
a compiler to compile the translated application.

### Claim 22 (depends on 21)

The system of claim 21, wherein the application includes shader code.

### Claim 23 (depends on 21)

The system of claim 21, wherein each of the plurality of atomic operations increments a value stored in the memory by an update amount.

### Claim 24 (depends on 23)

The system of claim 23, wherein the translation unit is further configured to compute a localized partial prefix sum of the update amounts up to a SIMD execution engine length.

### Claim 25 (depends on 23)

The system of claim 23, wherein the translation unit is configured to replace the plurality of atomic operations in the application with an atomic operation to increment the value stored in the memory by an amount equal to a sum of the update amounts.

### Claim 26 (depends on 21)

The system of claim 21, wherein the compiler comprises a just-in-time compiler.

### Claim 27 (depends on 21)

The system of claim 21, further comprising a graphics processor to execute the translated application.

### Claim 28 (depends on 21)

The system of claim 21, wherein the translation unit is located in a graphics driver.