Prefetch stream allocation for multithreading systems

Patent metadata

Field	Value
Publication number	US-10671394-B2
Application number	US-201816177273-A
Country	US
Kind code	B2
Filing date	Oct 31, 2018
Priority date	Oct 31, 2018
Publication date	Jun 2, 2020
Grant date	Jun 2, 2020

Abstract

A computer system for prefetching data in a multithreading environment includes a processor having a prefetching engine and a stride detector. The processor is configured to perform requesting data associated with a first thread of a plurality of threads, and prefetching requested data by the prefetching engine, where prefetching includes allocating a prefetch stream in response to an occurrence of a cache miss. The processor performs detecting each cache miss, and based on detecting the cache miss, monitoring the prefetching engine to detect subsequent cache misses and to detect one or more events related to allocations performed by the prefetching engine. The processor further performs, based on the stride detector detecting a selected number of events, directing the stride detector to switch from the first thread to a second thread by ignoring stride-1 allocations for the first thread and evaluating stride-1 allocations for potential strided accesses on the second thread.

First claim

What is claimed is:

1. A computer system for prefetching data in a multithreading environment, the system comprising:
a memory including a local cache;
a processor operatively connected to the local cache, the processor including a prefetching engine and a stride detector, the processor configured to perform:
requesting, by the processor, data associated with a first thread of a plurality of threads;
prefetching requested data from a cache structure into the local cache by the prefetching engine, wherein prefetching includes allocating a prefetch stream in response to an occurrence of a cache miss;
detecting, by the stride detector, each cache miss;
based on detecting the cache miss, monitoring the prefetching engine to detect subsequent cache misses and to detect one or more events related to allocations performed by the prefetching engine; and
based on the stride detector detecting a selected number of events, directing the stride detector to switch from the first thread to a second thread by ignoring stride-1 allocations for the first thread and evaluating stride-1 allocations for potential strided accesses on the second thread.

2. The computer system of claim 1 , wherein the prefetching engine is configured to direct the stride detector to switch between each of the plurality of threads in order according to a round-robin schedule.

3. The computer system of claim 1 , wherein the selected number of events is a selected number of prefetch stream allocations.

4. The computer system of claim 1 , wherein the prefetching engine is configured to support both stride-1 prefetching and stride-N prefetching.

5. The computer system of claim 4 , wherein the selected number of events is a number of prefetch stream allocations without a successful stride-N prefetch stream allocation.

6. The computer system of claim 1 , wherein the stride detector is connected to a stride detection table, the stride detection table including an entry for each cache miss detected by the stride detector during processing of the first thread, wherein a respective entry includes a subset of a cache structure address associated with a respective cache miss and a stride value or values relative to an address of an existing entry or entries, the stride value or values indicating a number of cachelines in the address structure between the address associated with the respective cache miss and the address in the existing entry or entries.

7. The computer system of claim 6 , wherein the stride detector is configured to, in response to detecting a cache miss, add a new entry to the stride detection table, and calculate a stride value or values for the new entry in relation to the existing entry or entries in the stride detection table.

8. The computer system of claim 1 , wherein the processor is configured to perform simultaneous multithreading (SMT).

9. A method of prefetching data in a multithreading environment, the method comprising:
requesting, by a processor including a local cache, data associated with a first thread of a plurality of threads;
prefetching requested data from a cache structure into the local cache by a prefetching engine, wherein prefetching includes allocating a prefetch stream in response to an occurrence of a cache miss;
detecting, by a stride detector, the cache miss;
based on detecting the cache miss, monitoring the prefetching engine to detect subsequent cache misses and to detect one or more events related to allocations performed by the prefetching engine; and
based on the stride detector detecting a selected number of events, directing the stride detector to switch from the first thread to a second thread by ignoring stride-1 allocations for the first thread and evaluating stride-1 allocations for potential strided accesses on the second thread.

10. The method of claim 9 , wherein the prefetching engine is configured to direct the stride detector to switch between each of the plurality of threads in order according to a round-robin schedule.

11. The method of claim 9 , wherein the selected number of events is a selected number of prefetch stream allocations.

12. The method of claim 9 , wherein the prefetching engine is configured to support both stride-1 prefetching and stride-N prefetching, and the selected number of events is a number of prefetch stream allocations without a successful stride-N prefetch stream allocation.

13. The method of claim 9 , wherein the stride detector is connected to a stride detection table, the stride detection table including an entry for each cache miss detected by the stride detector during processing of the first thread, wherein a respective entry includes a subset of a cache structure address associated with a respective cache miss and a stride value or values relative to an address of an existing entry or entries, the stride value or values indicating a number of cachelines in the address structure between the address associated with the respective cache miss and the address in the existing entry or entries.

14. The method of claim 13 , wherein the stride detector is configured to, in response to detecting a cache miss, add a new entry to the stride detection table, and calculate a stride value or values for the new entry in relation to the existing entry or entries in the stride detection table.

15. The method of claim 9 , wherein the processor is configured to perform simultaneous multithreading (SMT).

16. A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processing system to perform:
requesting, by a processor including a local cache, data associated with a first thread of a plurality of threads;
prefetching requested data from a cache structure into the local cache by a prefetching engine, wherein prefetching includes allocating a prefetch stream in response to an occurrence of a cache miss;
detecting, by a stride detector, the cache miss;
based on detecting the cache miss, monitoring the prefetching engine to detect subsequent cache misses and to detect one or more events related to allocations performed by the prefetching engine; and
based on the stride detector detecting a selected number of events, directing the stride detector to switch from the first thread to a second thread by ignoring stride-1 allocations for the first thread and evaluating stride-1 allocations for potential strided accesses on the second thread.

17. The computer program product of claim 16 , wherein the stride detector is configured to direct the prefetching engine to switch between each of the plurality of threads in order according to a round-robin schedule.

18. The computer program product of claim 16 , wherein the selected number of events is a selected number of prefetch stream allocations.

19. The computer program product of claim 16 , wherein the prefetching engine is configured to support both stride-1 prefetching and stride-N prefetching, and the selected number of events is a number of prefetch stream allocations without a successful stride-N prefetch stream allocation.

20. The computer program product of claim 16 , wherein the stride detector is connected to a stride detection table, the stride detection table including a respective entry for each cache miss detected by the stride detector during processing of a thread, the respective entry including a subset of an address in the cache structure associated with a respective cache miss and a stride value or values re

Assignees

• IBM

Inventors

• Britto Vivek
• Rohrbaugh Iii George W
• Karve Mohit
• Thompto Brian

Classifications

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/5016

  the resource being the memory · CPC title

• G06F9/383

  Operand prefetching (cache prefetching G06F12/0862) · CPC title

• G06F9/3861

  Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00) · CPC title

• G06F9/3455 Primary

  using stride · CPC title