Patent ID: 11914518
Assignee: ARM LIMITED
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 15:
16. An apparatus comprising:
a cache storage comprising a plurality of entries to store data;
lookup circuitry, responsive to a given access request, to perform a lookup operation in the cache storage to determine whether one of the entries in the cache storage is allocated to store data associated with a memory address indicated by the given access request, to generate a hit indication for the given access request when one of the entries in the cache storage is allocated to store data associated with the memory address, and to otherwise generate a miss indication for the given access request;
wherein the lookup circuitry is configured to perform, during a single lookup period, lookup operations in parallel for up to N access requests, where N is a plural integer; and
the apparatus further comprises:
allocation circuitry configured to determine, during the single lookup period, at least N candidate entries for allocation from amongst the plurality of entries, and to cause one of the candidate entries to be allocated for each of the up to N access requests for which the lookup circuitry generates the miss indication;
wherein:
the allocation circuitry is arranged to employ a tree pseudo least recently used (tree-PLRU) scheme to determine N candidate entries;
the lookup circuitry is arranged to generate, during each lookup period, a result signal indicating each entry for which a hit indication has been generated in that lookup period;
the allocation circuitry is arranged to maintain N separate tree structures, and to update each tree structure based on each result signal generated by the lookup circuitry; and
each separate tree structure is associated with one of N possible misses observable in any given lookup period, and the allocation circuitry comprises control circuitry to control each separate tree structure such that, when triggered by the control logic, that separate tree structure is arranged to identify the candidate entry for the associated miss, wherein the control logic is further arranged, in a given lookup period, to cause each of the separate tree structures to be updated in dependence on a number of misses observed in that given lookup period.