# US 2015/0178086 A1 · Method and apparatus for selecting cache locality for atomic operations

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

- Number: US 2015/0178086 A1
- Document ID: US20150178086A1
- Status: Published application
- Kind: A1
- Application number: 14/137,218
- Filed: 2013-12-20
- Published: 2015-06-25
- Earliest claimed: 2013-12-20
- Assignees: Intel Corporation
- Inventors: Christopher J. Hughes; Daehyun Kim; Camilo A. Moreno; Jong Soo Park; Richard M. Yoo
- Web page: https://patentgrep.com/patent/US20150178086A1

## CPC

- G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer}
- G06F 9/3004: {to perform operations on memory}
- G06F 9/30087: {Synchronisation or serialisation instructions}
- G06F 9/382: {Pipelined decoding, e.g. using predecoding}
- G06F 9/3834: {Maintaining memory consistency}
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06F 15/80: comprising an array of processing units with common control, e.g. single instruction multiple data processors (G06F15/82 takes precedence {; for correlation function computation G06F17/15})
- G06F 11/0724: {in a multiprocessor or a multi-core unit (multiprocessors per se G06F15/80)}
- G06F 12/0806: Multiuser, multiprocessor or multiprocessing cache systems
- G06F 12/0811: with multilevel cache hierarchies
- G06F 12/0842: for multiprocessing or multitasking
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An apparatus and method for determining whether to execute an atomic operation locally or remotely. For example, one embodiment of a processor comprises: a decoder to decode an atomic operation on a local core; prediction logic on the local core to estimate a cost associated with execution of the atomic operation on the local core and a cost associated with execution of the atomic operation on a remote core; and the remote core to execute the atomic operation remotely if the prediction logic determines that the cost for execution on the local core is relatively greater than the cost for execution on the remote core; and the local core to execute the atomic operation locally if the prediction logic determines that the cost for local execution on the local core is relatively less than the cost for execution on the remote core.

## Claims

### Claim 1

A processor comprising:
a local core comprising:
a decoder to decode an atomic operation;
prediction logic to estimate a cost associated with execution of the atomic operation on the local core and a cost associated with execution of the atomic operation on a remote core; and
a remote core to execute the atomic operation if the prediction logic determines that the cost for execution on the local core is relatively greater than the cost for execution on the remote core; and
the local core to execute the atomic operation locally if the prediction logic determines that the cost for local execution on the local core is relatively less than the cost for execution on the remote core.

### Claim 2 (depends on 1)

The processor as in claim 1 wherein the cost associated with execution of the atomic operation on the local core comprises determining a probability of a local cache hit for a cache line associated with the atomic operation and/or expected contention for the cache line.

### Claim 3 (depends on 2)

The processor as in claim 2 wherein the cost associated with execution of the atomic operation on the remote core comprises determining a probability of a remote cache hit for a cache line associated with the atomic operation and/or expected contention for the cache line.

### Claim 4 (depends on 3)

The processor as in claim 3 further comprising:
a prediction table within each core storing an entry for each of a plurality of atomic operations, wherein the table stores a number of times each atomic operation has been executed and a number of local cache hits, wherein the prediction logic is to determine probability of a local cache hit for each atomic operation using a ratio comprising a number of local cache hits over a number of times each atomic operation has been executed.

### Claim 5 (depends on 4)

The processor as in claim 4 wherein the table is indexed by an instruction pointer address associated with each atomic operation.

### Claim 6 (depends on 3)

The processor as in claim 3 wherein, if a most recent atomic operation was executed locally, then the prediction logic predicts probability of a local cache hit to determine costs but not expected contention.

### Claim 7 (depends on 3)

The processor as in claim 3 wherein, if a most recent atomic operation was executed remotely, then the prediction logic predicts expected contention to determine costs but not probability of a local cache hit.

### Claim 8 (depends on 3)

The processor as in claim 3 wherein to determine cost of a remote atomic operation, the prediction logic additionally determines an expected cost to send a request to the remote core to execute the atomic operation.

### Claim 9 (depends on 1)

The processor as in claim 1 further comprising:
remote core identification logic to determine an identify of a remote core to perform the atomic operation using at least a portion of an instruction pointer address associated with the atomic operation.

### Claim 10 (depends on 9)

The processor as in claim 9 wherein the remote core identification logic is to perform a hash operation using the at least a portion of the instruction pointer address associated with the atomic operation to generate the identity of the remote core.

### Claim 11

A method comprising:
decoding an atomic operation;
estimating a cost associated with execution of the atomic operation on the local core and a cost associated with execution of the atomic operation on a remote core; and
executing the atomic operation on a remote core if the estimated cost for execution on the local core is relatively greater than the estimated cost for execution on the remote core; and
executing the atomic operation on a local core if the estimated cost for execution on the local core is relatively less than the estimated cost for execution on the remote core.

### Claim 12 (depends on 11)

The method as in claim 11 wherein the estimated cost associated with execution of the atomic operation on the local core comprises determining a probability of a local cache hit for a cache line associated with the atomic operation and/or expected contention for the cache line.

### Claim 13 (depends on 12)

The method as in claim 12 wherein the estimated cost associated with execution of the atomic operation on the remote core comprises determining a probability of a remote cache hit for a cache line associated with the atomic operation and/or expected contention for the cache line.

### Claim 14 (depends on 13)

The method as in claim 13 further comprising:
storing an entry in a table for each of a plurality of atomic operations, wherein the table stores a number of times each atomic operation has been executed and a number of local cache hits, the probability of a local cache hit is determined for each atomic operation using a ratio comprising a number of local cache hits over a number of times each atomic operation has been executed.

### Claim 15 (depends on 14)

The method as in claim 14 wherein the table is indexed by an instruction pointer address associated with each atomic operation.

### Claim 16 (depends on 13)

The method as in claim 13 wherein, if a most recent atomic operation was executed locally, then predicting probability of a local cache hit to determine costs but not expected contention.

### Claim 17 (depends on 13)

The method as in claim 13 wherein, if a most recent atomic operation was executed remotely, then predicting expected contention to determine costs but not probability of a local cache hit.

### Claim 18 (depends on 13)

The method as in claim 13 wherein to determine cost of a remote atomic operation, an expected cost to send a request to the remote core to execute the atomic operation is determined.

### Claim 19 (depends on 11)

The method as in claim 11 further comprising:
determining an identify of a remote core to perform the atomic operation using at least a portion of an instruction pointer address associated with the atomic operation.

### Claim 20 (depends on 19)

The method as in claim 19 wherein identifying a remote core further comprises performing a hash operation using the at least a portion of the instruction pointer address associated with the atomic operation to generate the identity of the remote core.

### Claim 21

A system comprising a memory for storing instructions and data;
a graphics processor for performing graphics operations in response to certain instructions, a network interface for receiving and transmitting data over a network; and
a processor comprising:
a local core comprising:
a decoder to decode an atomic operation;
prediction logic to estimate a cost associated with execution of the atomic operation on the local core and a cost associated with execution of the atomic operation on a remote core; and
a remote core to execute the atomic operation if the prediction logic determines that the cost for execution on the local core is relatively greater than the cost for execution on the remote core; and the local core to execute the atomic operation locally if the prediction logic determines that the cost for local execution on the local core is relatively less than the cost for execution on the remote core.
