# US 2017/0286421 A1 · Indexing entries of a storage structure shared between multiple threads

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

- Number: US 2017/0286421 A1
- Document ID: US20170286421A1
- Status: Published application
- Kind: A1
- Application number: 15/086,866
- Filed: 2016-03-31
- Published: 2017-10-05
- Earliest claimed: 2016-03-31
- Assignees: Arm Limited
- Applicants: Arm Limited
- Inventors: Mitchell Bryan HAYENGA; Curtis Glenn DUNHAM; Dam SUNWOO
- Web page: https://patentgrep.com/patent/US20170286421A1

## CPC

- G06F 16/2255: {Hash tables}
- G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer}
- G06F 9/3842: {Speculative instruction execution}
- G06F 9/3844: {using dynamic branch prediction, e.g. using branch history tables}
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F 12/0875: with dedicated cache, e.g. instruction or stack
- G06F 12/1009: using page tables, e.g. page table structures
- G06F 12/1027: using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- G06F 16/172: Caching, prefetching or hoarding of files
- G06F 21/75: by inhibiting the analysis of circuitry or operation
- G06F 9/3848: {using hybrid branch prediction, e.g. selection between prediction techniques}
- G06F 2212/6032: Way prediction in set-associative cache
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An apparatus has processing circuitry for processing instructions from multiple threads. A storage structure is shared between the threads and has a number of entries. Indexing circuitry generates a target index value identifying an entry of the storage structure to be accessed in response to a request from the processing circuitry specifying a requested index value corresponding to information to be accessed from the storage structure. The indexing circuitry generates the target index value as a function of the requested index value and a key value selected depending on which of the threads trigger the request. The key value for at least one of the threads is updated from time to time.

## Claims

### Claim 1

An apparatus comprising:
processing circuitry to process instructions from a plurality of threads;
a storage structure shared between the plurality of threads and comprising a plurality of entries; and
indexing circuitry to generate a target index value identifying an entry of the storage structure to be accessed in response to a request from the processing circuitry specifying a requested index value corresponding to information to be accessed from the storage structure;
wherein the indexing circuitry is configured to generate the target index value as a function of the requested index value and a key value selected depending on which of the plurality of threads triggered the request, and to update the key value selected for at least one of the threads from time to time.

### Claim 2 (depends on 1)

The apparatus according to claim 1, wherein the indexing circuitry is configured to update the key value selected for said at least one of the threads in response to a key updating event.

### Claim 3 (depends on 2)

The apparatus according to claim 2, wherein the key updating event comprises elapse of a predetermined period since a previous key updating event.

### Claim 4 (depends on 2)

The apparatus according to claim 2, wherein the key updating event comprises a context switch.

### Claim 5 (depends on 2)

The apparatus according to claim 2, comprising monitoring circuitry configured to monitor at least one performance metric indicative of a level of contention between threads for entries of the storage structure; and
the key updating event comprises said at least one performance metric satisfying at least one predetermined condition.

### Claim 6 (depends on 1)

The apparatus according to claim 1, wherein the key value comprises a random or pseudorandom number.

### Claim 7 (depends on 1)

The apparatus according to claim 1, comprising a plurality of pseudorandom number generators each corresponding to one of the plurality of threads;
wherein the indexing circuitry is configured to select, as the key value to be used for generating the target index value, a pseudorandom number generated by the pseudorandom number generator corresponding to the thread that triggered the request.

### Claim 8 (depends on 7)

The apparatus according to claim 7, wherein in response to a key updating event, the indexing circuitry is configured to control each of the plurality of pseudorandom number generators to update its pseudorandom number.

### Claim 9 (depends on 1)

The apparatus according to claim 1, wherein the requested index value is dependent on a virtual address.

### Claim 10 (depends on 1)

The apparatus according to claim 1, wherein the storage structure comprises a predictive storage structure for which the plurality of entries are configured to store information indicating a predicted behaviour of the processing circuitry to be used when processing instructions.

### Claim 11 (depends on 1)

The apparatus according to claim 1, wherein the storage structure comprises at least one of:
branch prediction storage to store information indicative of predicted outcomes of branch instructions;
a branch target address cache to store information indicative of predicted target addresses of branch instructions;
a data prefetch storage structure to store information for predicting addresses from which data values are to be prefetched into a cache;
a translation lookaside buffer to store address translation information for translating virtual addresses to physical addresses;
a store-to-load forwarding storage structure configured to store a data value to be stored to a data store in response to a store instruction for access by a subsequent load instruction targeting the same address as the store instruction; and
a virtually-indexed cache.

### Claim 12 (depends on 1)

The apparatus according to claim 1, wherein in a first mode, the indexing circuitry is configured to generate the target index value as a function of the requested index value and the key value selected depending on which of the plurality of threads triggered the request; and
in a second mode, the indexing circuitry is configured to generate the target index value from the requested index value independent of which of the plurality of threads triggered the request.

### Claim 13 (depends on 12)

The apparatus according to claim 12, wherein the indexing circuitry is configured to select whether to use the first mode or the second mode in dependence on the requested index value.

### Claim 14 (depends on 12)

The apparatus according to claim 12, wherein in the first mode, the indexing circuitry is configured to generate a first portion of the target index value as a function of a first portion of the requested index value and the key value, and to generate a second portion of the target index value using a direct mapping from a second portion of the requested index value.

### Claim 15 (depends on 12)

The apparatus according to claim 12, wherein the storage structure comprises a virtually-indexed cache, and the requested index value depends on a virtual address;
the apparatus comprises a further physically-indexed cache; and
the indexing circuitry is configured to select the second mode for a selected range of requested index values in response to a signal from the further physically-indexed cache indicating that multiple threads are detected to be accessing data for the same physical address.

### Claim 16 (depends on 1)

The apparatus according to claim 1, wherein the processing circuitry comprises a processing pipeline to process instructions from the plurality of threads with instructions from multiple threads in flight in the processing pipeline concurrently.

### Claim 17

An apparatus comprising:
means for processing instructions from a plurality of threads;
means for storage shared between the plurality of threads and comprising a plurality of entries; and
means for generating a target index value identifying an entry of the means for storage to be accessed in response to a request from the means for processing specifying a requested index value corresponding to information to be accessed from the means for storage;
wherein the means for generating is configured to generate the target index value as a function of the requested index value and a key value selected depending on which of the plurality of threads triggered the request, and to update the key value selected for at least one of the threads from time to time.

### Claim 18

A data processing method comprising:
processing instructions from a plurality of threads;
issuing a request for information from a storage structure shared between the plurality of threads and comprising a plurality of entries, the request specifying a requested index value corresponding to the information to be accessed; and
generating a target index value identifying an entry of the storage structure to be accessed in response to the request, wherein the target index value is generated as a function of the requested index value and a key value selected depending on which of the plurality of threads triggered the request, and the key value selected for at least one of the threads is updated from time to time.
