# US 11,907,722 B2 · Methods and apparatus for storing prefetch metadata > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,907,722 B2 - Document ID: US11907722B2 - Status: Granted - Kind: B2 - Application number: 17/724,600 - Filed: 2022-04-20 - Published: 2023-10-26 - Granted: 2024-02-20 - Earliest claimed: 2022-04-20 - Assignees: Arm Limited - Applicants: Arm Limited - Inventors: Luca Maroncelli; Harvin Iriawan; Peter Raphael Eid; Cédric Denis Robert Airaud - Web page: https://patentgrep.com/patent/US11907722B2 ## CPC - G06F 9/3802: {Instruction prefetching} - G06F 9/383: {Operand prefetching (cache prefetching G06F12/0862)} - G06F 9/3851: {from multiple instruction streams, e.g. multistreaming} - G06F 12/0848: {Partitioned cache, e.g. separate instruction and operand caches} - G06F 12/0862: with prefetch - G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems - G06F 12/12: Replacement control - G06F 2212/1024: Latency reduction - G06F 2212/282: Partitioned cache - G06F 2212/466: Metadata, control data - 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 Aspects of the present disclosure relate to an apparatus comprising processing circuitry, prefetch circuitry and prefetch metadata storage comprising a plurality of entries. Metadata items, each associated with a given stream of instructions, are stored in the prefetch metadata storage. Responsive to a given entry of the plurality of entries being associated with the given stream associated with a given metadata item, the given entry is updated. Responsive to no entry of the plurality of entries being associated with the given stream associated with a given metadata item, an entry is selected according to a default replacement policy, the given stream is allocated thereto, and the selected entry is updated based on the given metadata item. Responsive to a switch condition being met, the default selection policy is switched to an alternative selection policy comprising locking one or more entries by preventing allocation of streams to the locked entries. ## Claims ### Claim 1 An apparatus comprising: processing circuitry to process streams of instructions; prefetch circuitry to prefetch data in advance of said data being processed by said streams of instructions; and prefetch metadata storage to store metadata associated with said prefetching, the prefetch metadata storage comprising a plurality of entries and the prefetch circuitry being configured to: determine metadata items, each being associated with a given stream of instructions, for storage in the prefetch metadata storage; responsive to a given entry of the plurality of entries being associated with the given stream associated with a given metadata item, updating the given entry based on the given metadata item; responsive to no entry of the plurality of entries being associated with the given stream associated with a given metadata item: selecting an entry according to a default replacement policy; allocating said given stream to the selected entry; and updating the selected entry based on the given metadata item, and responsive to a switch condition being met, identifying one or more of said entries to lock, and switching said default selection policy to an alternative selection policy comprising locking each identified entry by preventing allocation of streams to the locked entries, wherein the switch condition is indicative of a number of active streams of instructions exceeding a capacity of the prefetch metadata storage. ### Claim 2 (depends on 1) An apparatus according to claim 1, wherein the switch condition is that a number of active streams of instructions exceeds a threshold. ### Claim 3 (depends on 2) An apparatus according to claim 2, wherein the threshold is greater than the number of entries in said plurality of entries. ### Claim 4 (depends on 1) An apparatus according to claim 1, wherein an active stream is a stream for which metadata has been received within at least one of: a current window; and a window within a given number of previous windows. ### Claim 5 (depends on 1) An apparatus according to claim 1, wherein the prefetch circuitry is configured to determine that the switch condition is met by: counting, over a window, a number of received metadata items for which no metadata storage circuitry entry is associated with the associated stream and thus the prefetch circuitry allocates the associated stream to an entry; and responsive to said count exceeding a threshold, determining that the switch condition is met. ### Claim 6 (depends on 5) An apparatus according to claim 5, wherein the prefetch circuitry is configured to determine that the switch condition is met responsive to said count exceeding the threshold over a plurality of consecutive time windows. ### Claim 7 (depends on 1) An apparatus according to claim 1, wherein said updating a given entry based on a given metadata item comprises training said given entry based on the given metadata item. ### Claim 8 (depends on 1) An apparatus according to claim 1, wherein the prefetch circuitry is configured to identify one or more recently-used entries as said one or more entries to lock. ### Claim 9 (depends on 8) An apparatus according to claim 8, wherein a recently-used entry is at least one of: an entry which was updated in a current window; an entry which was updated within one or more latest windows; and an entry which was updated within a current rolling window. ### Claim 10 (depends on 8) An apparatus according to claim 8, wherein the prefetch circuitry is responsive to determining that a locked entry is no longer recently-used to unlock said locked entry. ### Claim 11 (depends on 1) An apparatus according to claim 1, wherein the prefetch circuitry is responsive to a second switch condition being met to switch from the alternative replacement policy to the default replacement policy. ### Claim 12 (depends on 11) An apparatus according to claim 11, wherein the second switch condition is indicative of a number of active streams of instructions being within a capacity of the prefetch metadata storage. ### Claim 13 (depends on 11) An apparatus according to claim 11, wherein the second switch condition is that a number of metadata items, for which entries would have been allocated according to the default replacement policy, is below a threshold within a time window. ### Claim 14 (depends on 13) An apparatus according to claim 13, wherein the prefetch circuitry is configured to determine said number by counting a number of dropped streams within said time window. ### Claim 15 (depends on 1) An apparatus according to claim 1, wherein the prefetch circuitry is configured to: when the default replacement policy is active, perform said prefetching based on the plurality of entries; when the alternative replacement policy is active, perform said prefetching based on the locked entries. ### Claim 16 (depends on 1) An apparatus according to claim 1, wherein each said stream is associated with at least one of: a respective processing operation having with a given address; an opcode of said respective processing operation; and a processor state. ### Claim 17 (depends on 16) An apparatus according to claim 16, wherein each said stream is associated with a respective load-store operation having the given address. ### Claim 18 A method comprising: making predictions of data in advance of said data being processed by processing circuitry; and determining metadata items, each being associated with predictions of data for a given stream of instructions, for storage in metadata storage comprising a plurality of entries; responsive to a given entry of the plurality of entries being associated with the given stream associated with a given metadata item, updating the given entry based on the given metadata item; responsive to no entry of the plurality of entries being associated with the given stream associated with a given metadata item: selecting an entry according to a default replacement policy; allocating said given stream to the selected entry; and updating the selected entry based on the given metadata item, and responsive to a switch condition being met, identifying one or more of said entries to lock, and switching said default selection policy to an alternative selection policy comprising locking each identified entry by preventing allocation of streams to the locked entries, wherein the switch condition is indicative of a number of active streams of instructions exceeding a capacity of the prefetch metadata storage. ### Claim 19 A non-transitory computer-readable storage medium to store computer-readable code for fabrication of an apparatus comprising: processing circuitry to process streams of instructions; prefetch circuitry to prefetch data in advance of said data being processed by said streams of instructions; and prefetch metadata storage to store metadata associated with said prefetching, the prefetch metadata storage comprising a plurality of entries and the prefetch circuitry being configured to: determine metadata items, each being associated with a given stream of instructions, for storage in the prefetch metadata storage; responsive to a given entry of the plurality of entries being associated with the given stream associated with a given metadata item, updating the given entry based on the given metadata item; responsive to no entry of the plurality of entries being associated with the given stream associated with a given metadata item: selecting an entry according to a default replacement policy; allocating said given stream to the selected entry; and updating the selected entry based on the given metadata item, and responsive to a switch condition being met, identifying one or more of said entries to lock, and switching said default selection policy to an alternative selection policy comprising locking each identified entry by preventing allocation of streams to the locked entries, wherein the switch condition is indicative of a number of active streams of instructions exceeding a capacity of the prefetch metadata storage.