# US 12,111,767 B2 · Method and apparatus for a page-local delta-based prefetcher > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,111,767 B2 - Document ID: US12111767B2 - Status: Granted - Kind: B2 - Application number: 18/302,968 - Filed: 2023-04-19 - Published: 2023-11-23 - Granted: 2024-10-08 - Earliest claimed: 2020-06-26 - Assignees: Advanced Micro Devices, Inc. - Applicants: Advanced Micro Devices, Inc. - Inventors: Susumu Mashimo; John Kalamatianos - Web page: https://patentgrep.com/patent/US12111767B2 ## CPC - G06F 12/0862: with prefetch - G06F 9/30036: {Instructions to perform operations on packed data, e.g. vector, tile or matrix operations} - G06F 9/30047: {Prefetch instructions; cache control instructions} - G06F 9/30101: {Special purpose registers} - G06F 9/3455: {using stride} - G06F 9/3832: {Value prediction for operands; operand history buffers} - G06F 12/0877: Cache access modes - G06F 18/214: Generating training patterns; Bootstrap methods, e.g. bagging or boosting - G06F 2212/6024: History based prefetching - G06F 2212/6026: Prefetching based on access pattern detection, e.g. stride based prefetch - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method includes recording a first set of consecutive memory access deltas, where each of the consecutive memory access deltas represents a difference between two memory addresses accessed by an application, updating values in a prefetch training table based on the first set of memory access deltas, and predicting one or more memory addresses for prefetching responsive to a second set of consecutive memory access deltas and based on values in the prefetch training table. ## Claims ### Claim 1 A method, comprising: recording a first set of consecutive memory access deltas, wherein each of the consecutive memory access deltas represents a difference between two memory addresses; updating values in a prefetch training table based on the first set of memory access deltas by copying a first subset of the consecutive memory access deltas to the prefetch training table; and predicting one or more memory addresses for prefetching based on the updated values in the prefetch training table. ### Claim 2 (depends on 1) The method of claim 1, wherein the updating values in a prefetch training table is performed in response to determining that the first set of consecutive memory access deltas includes a predetermined quantity of memory access deltas. ### Claim 3 (depends on 1) The method of claim 1, wherein the prefetch training table includes a pattern history table storing one or more entries, each of the one or more entries including a sequence of memory access delta values and an age field. ### Claim 4 (depends on 1) The method of claim 1, wherein the predicting is performed in response to a second set of consecutive memory access deltas. ### Claim 5 (depends on 4) The method of claim 4, further comprising: calculating each of the first set of consecutive memory access deltas based on memory addresses located in a first memory page; calculating each of a second set of consecutive memory access deltas based on memory addresses located in a second memory page; and storing the first set of consecutive memory access deltas and the second set of consecutive memory access deltas in different entries. ### Claim 6 (depends on 4) The method of claim 4, further comprising: in response to determining that a first entry contains at least m memory access deltas, wherein m is an integer greater than or equal to 2, selecting the values from the prefetch training table by: calculating a hash based on a program counter value associated with a most recent memory access and the second set of consecutive memory access deltas, and performing a lookup of the hash in a correlation table to identify an entry in the prefetch training table containing the values. ### Claim 7 (depends on 1) The method of claim 1, wherein: the values selected from the prefetch training table comprise one or more of the first set of consecutive memory access deltas; and the method further comprises predicting one or more prefetch addresses based on the selected values and a memory address of a most recent memory access by an application. ### Claim 8 (depends on 1) The method of claim 1, wherein: the prefetch training table comprises a correlation weight table; the values from the prefetch training table represent weights in the correlation weight table; and the updating the values in the prefetch training table further comprises, for each memory access delta in a subset of memory access deltas from the first set of memory access deltas: in the correlation weight table, incrementing one of the weights associated with: the memory access delta, a most recent memory access delta, and a sequence distance of the memory access delta from the most recent memory access delta. ### Claim 9 (depends on 1) The method of claim 1, wherein: the prefetch training table comprises a correlation weight table; and the method further comprises, in response to determining that a local pattern buffer contains at least n memory access deltas: for each memory access delta of the at least n memory access deltas, from the correlation weight table, selecting a set of weight values corresponding to the memory access delta and to a sequence position of the memory access delta relative to a sequence position of a future memory access delta, and adding the selected weight values to respective accumulated weight values in a sum register vector, wherein the predicting one or more memory addresses for prefetching is based on an index of a highest accumulated weight value in the sum register vector after the adding the selected weight values has been performed for all of the at least n memory access deltas. ### Claim 10 (depends on 9) The method of claim 9, further comprising performing a prefetch based on the predicted one or more memory addresses in response to determining that the highest accumulated weight value exceeds a threshold. ### Claim 11 (depends on 1) The method of claim 1, wherein: the prefetch training table comprises a correlation weight table; an index of a highest accumulated weight value represents a predicted future memory access delta; and predicting one or more additional memory addresses for prefetching by performing a lookup in the correlation weight table based on the predicted future memory access delta and a most recent memory access delta. ### Claim 12 (depends on 1) The method of claim 1, wherein: the prefetch training table comprises a correlation weight table; and the method further comprises, in response to detecting eviction of unused prefetched data from a cache, decrementing in the correlation weight table each of a set of weights associated with the evicted prefetched data. ### Claim 13 A computing device, comprising: a storage device to store a first set of consecutive memory access deltas, wherein each of the consecutive memory access deltas represents a difference between two memory addresses accessed by an application; memory adapted to store prefetch training data in a prefetch training table; and prefetch logic configured to: update values in the prefetch training table based on the first set of consecutive memory access deltas by copying a first subset of the first set of consecutive memory access deltas to the prefetch training table; and predict one or more memory addresses for prefetching based on values in the prefetch training table. ### Claim 14 (depends on 13) The computing device of claim 13, wherein the prefetch logic is configured to update the values in the prefetch training table in response to determining that the first set of consecutive memory access deltas includes a predetermined quantity of memory access deltas. ### Claim 15 (depends on 13) The computing device of claim 13, wherein the prefetch training table comprises a pattern history table storing one or more entries, each of the one or more entries including a sequence of memory access delta values and an age field. ### Claim 16 (depends on 13) The computing device of claim 13, wherein the prefetch logic is configured to predict the one or more memory addresses for prefetching in response to a second set of consecutive memory access deltas. ### Claim 17 (depends on 13) The computing device of claim 13, further comprising: a hash engine configured to calculate a hash based on a program counter value associated with a most recent memory access and a second set of consecutive memory access deltas, wherein the prefetch logic is further configured to: in response to determining that a first entry contains at least m memory access deltas, wherein m is an integer greater than or equal to 2, select the values from the prefetch training table by performing a lookup of the hash in a correlation table to identify an entry in the prefetch training table containing the values. ### Claim 18 (depends on 13) The computing device of claim 13, wherein: values selected from the prefetch training table comprise one or more of the first set of consecutive memory access deltas; and the prefetch logic is further configured to predict one or more prefetch addresses based on the selected values and a memory address of a most recent memory access by an application. ### Claim 19 (depends on 13) The computing device of claim 13, wherein: the prefetch training table comprises a correlation weight table; the values from the prefetch training table represent weights in the correlation weight table; and the prefetch logic is configured to update the values in the prefetch training table by, for each memory access delta in a subset of memory access deltas from the first set of memory access deltas, in the correlation weight table, incrementing one of the weights associated with: the memory access delta, a most recent memory access delta, and a sequence distance of the memory access delta from the most recent memory access delta. ### Claim 20 A computing system, comprising: a main memory; a cache memory; and a prefetcher coupled with the main memory and the cache memory, wherein the prefetcher is configured to: record a first set of consecutive memory access deltas, wherein each of the consecutive memory access deltas represents a difference between two memory addresses in the main memory accessed by an application; update values in a prefetch training table based on the first set of consecutive memory access deltas by copying a first subset of the first set of consecutive memory access deltas to the prefetch training table; and prefetch data from one or more prefetch memory addresses of the main memory to the cache memory based on values in the prefetch training table.