# US 12,222,875 B1 · Insertion/promotion vectors to update replacement data in caches based on criticality > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,875 B1 - Document ID: US12222875B1 - Status: Granted - Kind: B1 - Application number: 18/361,169 - Filed: 2023-07-28 - Granted: 2025-02-11 - Earliest claimed: 2022-12-22 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Tyler J. Huberty; Henry A. Pellerin; Daniel A. Jimenez - Web page: https://patentgrep.com/patent/US12222875B1 ## CPC - G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list - G06F 12/126: with special data handling, e.g. priority of data or instructions, handling errors or pinning - G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel - G06F 2212/1021: Hit rate improvement - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A cache memory supports a plurality of insertion/promotion vectors (IPVs) and a replacement control circuit configured to update replacement data for the cache memory based on the plurality of IPVs. In one embodiment, the IPV is selected for a given request based a criticality status of a cache line accessed by the given request. For example, cache lines deemed important or critical for performance reasons may be replaced less frequently via a first IPV, while non-critical cache lines are replaced more frequently via a second IPV. ## Claims ### Claim 1 An apparatus comprising: a cache memory configured to store a plurality of cache lines; a plurality of clocked storage devices configured to store a plurality of insertion and promotion vectors (IPVs); and a replacement control circuit coupled to the cache memory and to the plurality of clocked storage devices, wherein: the replacement control circuit is configured to maintain replacement data corresponding to the cache memory based on the plurality of IPVs, and the replacement control circuit is configured to select a selected IPV of the plurality of IPVs to update the replacement data for a given access request to the cache memory based on a criticality level of a particular cache line accessed by the given access request. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein: the replacement data stores information usable to specify a rank of the plurality of cache lines from most replaceable to least replaceable; the selected IPV comprises a vector element for each position in the rank, a given vector element identifying a promotion position in the rank; and the replacement control circuit is configured to update the rank to promote the particular cache line to an identified promotion position in response to the given access request. ### Claim 3 (depends on 2) The apparatus of claim 2 wherein: the selected IPV further comprises an additional vector element that specifies an insertion position in the rank for a cache line that is being stored into the cache memory in response to a cache miss; and the replacement control circuit is configured to insert a missing cache line into the cache memory at the insertion position in response to the given access request. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein a first of the plurality of IPVs corresponds to a criticality level indicating criticality greater than non-critical and a second of the plurality of IPVs corresponds to a criticality level indicating non-critical status. ### Claim 5 (depends on 4) The apparatus of claim 4, wherein the plurality of IPVs include respective IPVs for a non-critical level and two or more increasingly critical levels. ### Claim 6 (depends on 4) The apparatus of claim 4, wherein the plurality of IPVs include a first IPV for a first criticality level indicating non-critical status and a second IPV shared by at least two levels of criticality indicating increasing levels of criticality. ### Claim 7 (depends on 4) The apparatus of claim 4, wherein the first IPV specifies a least recently used (LRU) replacement scheme. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein the second IPV specifies a non-LRU replacement scheme. ### Claim 9 A method comprising: storing, by a computing device, a plurality of cache lines for a cache memory and a plurality of insertion and promotion vectors (IPVs) for the cache memory; maintaining, by the computing device using the plurality of the IPVs, replacement data for the cache memory; receiving, by the computing device, an access request to the cache memory; determining, by the computing device, a criticality level of a particular cache line corresponding to the access request; selecting, by the computing device based on the criticality level of the particular cache line, a selected IPV of the plurality of IPVs; and updating, by the computing device using the selected IPV, the replacement data for the access request. ### Claim 10 (depends on 9) The method of claim 9, wherein: the replacement data specifies a rank of the plurality of cache lines from most replaceable to least replaceable; and the selected IPV comprises a vector element for each position in the rank and is usable to identify a promotion position in the rank when a cache hit occurs for the particular cache line. ### Claim 11 (depends on 10) The method of claim 10, further comprising updating, by the computing device, the rank to promote the particular cache line to the promotion position in response to the access request resulting in a hit. ### Claim 12 (depends on 10) The method of claim 10, wherein: the selected IPV further comprises an additional vector element that specifies an insertion position in the rank for a cache line that is being stored into the cache memory to replace one of the plurality of cache lines; and wherein the method further comprises: inserting, by the computing device, a new cache line into the plurality of cache lines at the insertion position in response to the access request resulting in a miss. ### Claim 13 (depends on 9) The method of claim 9, wherein at least one of the plurality of IPVs has a criticality level indicating criticality greater than non-critical and at least one other one of the plurality of IPVs has another criticality level indicating non-critical status. ### Claim 14 (depends on 9) The method of claim 9, wherein respective IPVs correspond to respective ones of two or more increasingly critical levels. ### Claim 15 (depends on 9) The method of claim 9, wherein a given cache line can be denoted as having a criticality level selected from one of two or more increasingly critical levels, wherein at least one IPV is shared by a plurality of the two or more increasingly critical levels. ### Claim 16 A non-transitory computer readable storage medium having instructions of a hardware description language stored thereon, wherein the instructions are executable by a computing system to program the computing system to generate a computer simulation model, wherein the computer simulation model represents a hardware circuit that includes: a cache memory configured to store a plurality of cache lines; a plurality of clocked storage devices configured to store a plurality of insertion and promotion vectors (IPVs); and a replacement control circuit coupled to the cache memory and to the plurality of clocked storage devices, wherein: the replacement control circuit is configured to maintain replacement data corresponding to the cache memory based on the plurality of IPVs, and the replacement control circuit is configured to select a selected IPV of the plurality of IPVs to update the replacement data for a given access request to the cache memory based on a criticality level of a particular cache line accessed by the given access request. ### Claim 17 (depends on 16) The non-transitory computer readable storage medium of claim 16, wherein: the replacement data stores information usable to specify a rank of the plurality of cache lines from most replaceable to least replaceable; the selected IPV comprises a vector element for each position in the rank, a given vector element identifying a promotion position in the rank; and the replacement control circuit is configured to update the rank to promote the particular cache line to an identified promotion position in response to the given access request. ### Claim 18 (depends on 17) The non-transitory computer readable storage medium of claim 17, wherein: the selected IPV further comprises an additional vector element that specifies an insertion position in the rank for a cache line that is being stored into the cache memory to replace one of the plurality of cache lines in the cache memory; and the replacement control circuit is configured to insert a missing cache line into the cache memory at the position in the replacement data indicated by the insertion position in response to the given access request accessing the cache line. ### Claim 19 (depends on 16) The non-transitory computer readable storage medium of claim 16, wherein a first of the plurality of IPVs is associated with a criticality level indicating criticality greater than non-critical and a second of the plurality of IPVs is associated with a criticality level indicating non-critical status. ### Claim 20 (depends on 16) The non-transitory computer readable storage medium of claim 16, wherein: the criticality level is usable to specify a non-critical level and two or more increasingly critical levels; and respective IPVs correspond to respective ones of the two or more increasingly critical levels.