Granted Patent B2

US 12,443,533 · App. 17/815,516 · Granted Oct 14, 2025

Inventor: David Andrew Roberts (Wellesley, MA)

Assignee: Micron Technology, Inc.

G06F12/0862G06F12/0891G06F2212/6026

Abstract

Claims (84)

1. An apparatus comprising:

at least one memory configured to store a data structure and a dataset, the dataset comprising multiple entries including access metadata corresponding to memory accesses for an address space, each entry of the multiple entries covering a respective address range of a set of address ranges covered by the access metadata; and

logic coupled to the at least one memory and configured to:

maintain the data structure within the at least one memory, the data structure comprising multiple nodes distributed across multiple levels, each respective level of the multiple levels corresponding to entries of the dataset having a respective range size of multiple range sizes, the multiple levels including a first level corresponding to a first range size and a second level corresponding to a second range size smaller than the first range size, each respective entry of the multiple entries associated with a respective node of the multiple nodes at a level of the multiple levels that corresponds to the respective address range covered by the access metadata of the respective entry;

split a node of the first level of the data structure into two or more nodes of the second level of the data structure based on access metadata covering the respective address range of the node; and

split an entry of the multiple entries into two or more entries of the dataset, the entry covering the respective address range of the node, the two or more entries covering two or more non-overlapping address ranges contained by the respective address range of the node,

one or more nodes of the multiple nodes including at least one node tag configured to uniquely identify at least one node within a respective level of the multiple levels of the data structure, the one or more nodes and the at least one node at different levels of the multiple levels of the data structure; and

another node of the multiple nodes including coverage data pertaining to access metadata for an address range of the set of address ranges, the coverage data comprising a reference to another entry of the multiple entries of the dataset, and the other entry including the access metadata for the address range.

2. The apparatus of claim 1 , wherein the logic is configured to:

modify the data structure to adjust the set of address ranges based, at least in part, on utility metrics of the access metadata; and

propagate modifications of the data structure to the dataset.

3. The apparatus of claim 2 , wherein the logic is configured to:

propagate the modifications of the data structure by reconfiguring the set of address ranges covered by respective entries of the dataset that include access metadata to correspond with the adjusted set of address ranges of the data structure.

4. The apparatus of claim 1 , wherein:

the coverage data comprises the access metadata for the address range.

5. The apparatus of claim 1 , wherein:

the data structure is separate from the dataset;

the at least one memory comprises a first memory and a second memory;

the first memory is configured to store the data structure; and

the second memory is configured to store the dataset.

6. The apparatus of claim 1 , wherein:

the multiple nodes include a particular node;

the particular node is part of the first level of the multiple levels; and

the particular node includes at least two of a next valid indicator, a next pointer, an entry valid indicator, or an entry pointer.

7. The apparatus of claim 1 , wherein:

the multiple levels include a third level corresponding to a third range size smaller than the second range size.

8. The apparatus of claim 7 , wherein:

the second level comprises a particular node that references a child structure of the third level, the child structure including two or more other nodes corresponding to the third range size.

9. The apparatus of claim 1 , wherein:

the apparatus comprises a memory device; and

the memory device includes the at least one memory and the logic.

10. The apparatus of claim 1 , wherein the logic is configured to:

add a particular node to the second level of the multiple levels of the data structure in response to a determination that a specified address is not covered by the multiple entries of the dataset, the particular node configured to represent an address range that includes the specified address; and

create a particular entry of the multiple entries of the dataset to cover the address range represented by the particular node.

11. The apparatus of claim 1 , wherein:

the two or more nodes include a first node of the second level and a second node of the second level;

the two or more non-overlapping address ranges include a first address range corresponding to the first node and a second address range corresponding to the second node;

the two or more entries include a first entry corresponding to the first node and a second entry corresponding to the second node; and

the logic is configured to:

update first access metadata stored in the first entry based on memory accesses pertaining to the first address range; and

update second access metadata stored in the second entry based on memory accesses pertaining to the second address range.

12. The apparatus of claim 1 , wherein the logic is configured to:

merge two or more other nodes of the second level of the data structure into a particular node of the first level of the data structure based on access metadata covering two or more other non-overlapping address ranges of the two or more other nodes, the particular node corresponding to a respective address range that spans the two or more other non-overlapping address ranges; and

merge two or more other entries of the dataset into a particular entry of the dataset, the particular entry covering the respective address range of the particular node.

13. The apparatus of claim 1 , wherein:

each respective entry of the multiple entries comprises an indication of the respective address range covered by the access metadata of the respective entry; and

the access metadata comprises at least one of access statistics, access pattern statistics, access history, access sequences, access frequency metadata, access time metadata, access pattern metadata, stride patterns, correlation patterns, delta sequences, access modeling metadata, machine learning modeling metadata, or machine learning feature data.

14. The apparatus of claim 1 , wherein the logic is configured to:

provide, to a prefetcher, access metadata of a particular entry of the dataset, the prefetcher configured to prefetch data within a particular address range covered by the particular entry into a cache memory based, at least in part, on the provided access metadata; and

set a metric of the particular entry based, at least in part, on prefetch performance within the particular address range covered by the particular entry.

15. A method comprising:

storing in at least one memory a dataset comprising multiple entries including access metadata corresponding to memory accesses for an address space, each entry of the multiple entries covering a respective address range of a set of address ranges covered by the access metadata;

maintaining a data structure within the at least one memory, the data structure comprising multiple nodes distributed across multiple levels, each respective level of the multiple levels corresponding to entries of the dataset having a respective range size of multiple range sizes, the multiple levels including a first level corresponding to a first range size and a second level corresponding to a second range size smaller than the first range size, each respective entry of the multiple entries associated with a respective node of the multiple nodes at a level of the multiple levels that corresponds to the respective address range covered by the access metadata of the respective entry;

splitting a node of the first level of the data structure into two or more nodes of the second level of the data structure based on access metadata covering the respective address range of the node; and

splitting an entry of the multiple entries into two or more entries of the dataset, the entry covering the respective address range of the node, the two or more entries covering two or more non-overlapping address ranges contained by the respective address range of the node,

one or more nodes of the multiple nodes including at least one node tag configured to uniquely identify at least one node within a respective level of the multiple levels of the data structure, the one or more nodes and the at least one node at different levels of the multiple levels of the data structure; and

another node of the multiple nodes including coverage data pertaining to access metadata for an address range of the set of address ranges, the coverage data comprising a reference to another entry of the multiple entries of the dataset, and the other entry including the access metadata for the address range.

16. The method of claim 15 , further comprising:

determining that a specified address is outside of the set of address ranges covered by the dataset;

mapping a second node of the second level of the data structure to a second tag corresponding to a second portion of the specified address, the second node defining a second address range of the second range size that covers the specified address;

mapping a first node of the first level of the data structure to a first tag corresponding to a first portion of the specified address, the first node referencing the second node; and

associating a designated entry of the dataset with the second node, the designated entry configured to cover the second address range.

17. The method of claim 15 , further comprising:

identifying a particular entry of the dataset having a metric below a threshold, the identified particular entry covering a particular address range of the first range size and being referenced by a designated node within the first level of the data structure;

creating a group of nodes within the second level of the data structure, each node of the group of nodes covering a respective portion of the particular address range covered by the designated node;

replicating access metadata of the identified particular entry within entries corresponding to respective nodes of the group of nodes; and

configuring the designated node to reference the group of nodes created within the second level of the data structure.

18. The method of claim 15 , further comprising:

identifying a particular entry of the dataset having a metric below a threshold, the identified particular entry covering a particular address range of the second range size and being referenced by a particular node within the second level of the data structure;

invalidating the identified particular entry; and

removing the particular node from the data structure.

19. The method of claim 15 , further comprising:

maintaining copies of the multiple entries of the dataset within nodes of the data structure, wherein:

each node of the second level of the data structure comprises a copy of a given entry for the second range size; and

each node of the first level of the data structure comprises one of:

a copy of a given entry for the first range size, or

a reference to a child structure comprising one or more nodes of the second level of the data structure.

20. A system comprising:

means for storing in at least one memory a dataset comprising multiple entries including access metadata corresponding to memory accesses for an address space, each entry of the multiple entries covering a respective address range of a set of address ranges covered by the access metadata;

means for maintaining a data structure within the at least one memory, the data structure comprising multiple nodes distributed across multiple levels, each respective level of the multiple levels corresponding to entries of the dataset having a respective range size of multiple range sizes, the multiple levels including a first level corresponding to a first range size and a second level corresponding to a second range size smaller than the first range size, each respective entry of the multiple entries associated with a respective node of the multiple nodes at a level of the multiple levels that corresponds to the respective address range covered by the access metadata of the respective entry;

means for splitting a node of the first level of the data structure into two or more nodes of the second level of the data structure based on access metadata covering the respective address range of the node; and

means for splitting an entry of the multiple entries into two or more entries of the dataset, the entry covering the respective address range of the node, the two or more entries covering two or more non-overlapping address ranges contained by the respective address range of the node,

one or more nodes of the multiple nodes including at least one node tag configured to uniquely identify at least one node within a respective level of the multiple levels of the data structure, the one or more nodes and the at least one node at different levels of the multiple levels of the data structure; and

another node of the multiple nodes including coverage data pertaining to access metadata for an address range of the set of address ranges, the coverage data comprising a reference to another entry of the multiple entries of the dataset, and the other entry including the access metadata for the address range.

Assignments (1)

Continuity (2)

References Cited (174)