# US 11,113,208 B2 · Pseudo-first in, first out (FIFO) tag line replacement > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,208 B2 - Document ID: US11113208B2 - Status: Granted - Kind: B2 - Application number: 16/589,108 - Filed: 2019-09-30 - Published: 2020-11-26 - Granted: 2021-09-07 - Earliest claimed: 2019-05-22 - Assignees: Texas Instruments Incorporated - Applicants: Texas Instruments Incorporated - Inventors: Sureshkumar Govindaraj - Web page: https://patentgrep.com/patent/US11113208B2 ## CPC - G06F 12/0207: {with multidimensional access, e.g. row/column, matrix} - G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list - G06F 12/04: Addressing variable-length words or parts of words - G06F 12/0646: {Configuration or reconfiguration} - G06F 12/0811: with multilevel cache hierarchies - G06F 12/0886: Variable-length word access - G06F 12/0888: using selective caching, e.g. bypass - G06F 12/121: using replacement algorithms - G06F 2212/1008: Correctness of operation, e.g. memory ordering - G06F 2212/1024: Latency reduction - G06F 2212/1044: Space efficiency improvement - G06F 2212/454: Vector or matrix data - G06F 2212/455: Image or video data - G06F 2212/608: Details relating to cache mapping - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method is provided that includes searching tags in a tag group comprised in a tagged memory system for an available tag line during a clock cycle, wherein the tagged memory system includes a plurality of tag lines having respective tags and wherein the tags are divided into a plurality of non-overlapping tag groups, and searching tags in a next tag group of the plurality of tag groups for an available tag line during a next clock cycle when the searching in the tag group does not find an available tag line. ## Claims ### Claim 1 A method comprising: searching tags in a first tag group comprised in a tagged memory system for an available tag line during a first clock cycle, wherein the tagged memory system comprises a plurality of tag lines having respective tags and wherein the tags are divided into a plurality of non-overlapping tag groups; and searching tags in a next tag group of the plurality of non-overlapping tag groups for an available tag line during a next clock cycle when the searching in the first tag group does not find an available tag line; wherein the searching tags in the first tag group starts with a tag in the first tag group immediately after a tag associated with a tag line that was allocated in a previous search. ### Claim 2 (depends on 1) The method of claim 1, wherein searching tags in the first tag group further comprises finding an available tag line, allocating the tag line, and setting a pointer to a tag associated with a next tag line. ### Claim 3 (depends on 1) The method of claim 1, wherein the tagged memory system consists of thirty-two tag lines each having an associated tag and each tag group consists of eight tags. ### Claim 4 (depends on 1) The method of claim 1, wherein the tagged memory system is comprised in a streaming engine of a processor. ### Claim 5 (depends on 1) The method of claim 1, wherein a priority encoder is used to search tags in each tag group. ### Claim 6 (depends on 1) The method of claim 1, wherein searching tags in the first tag group further comprises searching tags in the first tag group for two available tag lines, and searching tags in the next tag group further comprises searching the next tag group for two available tag lines when the searching in the first tag group does not find two available tag lines. ### Claim 7 A tagged memory system comprising: a plurality of tag lines; a plurality of tags, wherein each tag is associated with a respective tag line of the plurality of tag lines and the plurality of tags is divided into a plurality of non-overlapping tag groups; and a storage allocation component configured to perform pseudo-first-in-first-out (FIFO) tag replacement in which a first tag group of the plurality of non-overlapping tag groups is searched for an available tag line during a first clock cycle, and a next tag group of the plurality of non-overlapping tag groups is searched for an available tag line during a next clock cycle when searching in the first tag group does not find an available tag line; wherein the first tag group is searched beginning with a tag in the first tag group immediately after a tag associated with a tag line allocated in a previous search. ### Claim 8 (depends on 7) The tagged memory system of claim 7, wherein when an available tag line is found in the first tag group, the tag line is allocated and a pointer is set to a tag associated with a next tag line. ### Claim 9 (depends on 7) The tagged memory system of claim 7, wherein the plurality of tag lines consists of thirty-two tag lines each having an associated tag and each tag group consists of eight tags. ### Claim 10 (depends on 7) The tagged memory system of claim 7, wherein the tagged memory system is comprised in a streaming engine of a processor. ### Claim 11 (depends on 7) The tagged memory system of claim 7, wherein a priority encoder is used to search tags in a tag group. ### Claim 12 (depends on 7) The tagged memory system of claim 7, wherein the first tag group is searched for two available tag lines during the first clock cycle, and the next tag group is searched for two available tag lines in the next clock cycle when the search in the first tag group does not find two available tag lines. ### Claim 13 A tagged memory system comprising: a plurality of tag lines; a plurality of tags, wherein each tag is associated with a respective tag line of the plurality of tag lines and the plurality of tags is divided into a plurality of non-overlapping tag groups; and a storage allocation component configured to search each tag group of the plurality of non-overlapping tag groups in round robin order until an available tag line is located or all of the plurality of non-overlapping tag groups have been searched, wherein the search begins with the tag group comprising a tag associated with a tag line allocated in a previous search and wherein each tag group searched is searched in a single clock cycle. ### Claim 14 (depends on 13) The tagged memory system of claim 13, wherein the storage allocation component is further configured to search each tag group using a priority encoder. ### Claim 15 (depends on 13) The tagged memory system of claim 13, wherein the plurality of tag lines consists of thirty-two tag lines each having an associated tag and each tag group consists of eight tags. ### Claim 16 (depends on 13) The tagged memory system of claim 13, wherein the tagged memory system is comprised in a streaming engine of a processor. ### Claim 17 (depends on 13) The tagged memory system of claim 13, wherein the storage allocation component is further configured to search each tag group for two available tag lines until two available tag lines are located in a same tag group or all tag groups have been searched. ### Claim 18 (depends on 13) The tagged memory system of claim 13, wherein the tagged memory system is comprised in a digital signal processor.