ITERATOR REGISTER FOR STRUCTURED MEMORY

• US 20110010347A1
• Filed: 07/23/2010
• Published: 01/13/2011
• Est. Priority Date: 01/26/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Hicamp Systems Incorporated
• Inventors: Solomatnikov, Alexandre Y., Firoozshahian, Amin, Cheriton, David R.
• Granted Patent: US 9,601,199 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 2212/602 Details relating to cache prefetching
• CPC Class Codes: G06F 2212/622 State-only directory, i.e. not recording identity of sharing or owning nodes
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

Abstract

Loading data from a computer memory system is disclosed. A memory system is provided, wherein some or all data stored in the memory system is organized as one or more pointer-linked data structures. One or more iterator registers are provided. A first pointer chain is loaded, having two or more pointers leading to a first element of a selected pointer-linked data structure to a selected iterator register. A second pointer chain is loaded, having two or more pointers leading to a second element of the selected pointer-linked data structure to the selected iterator register. The loading of the second pointer chain reuses portions of the first pointer chain that are common with the second pointer chain.

Modifying data stored in a computer memory system is disclosed. A memory system is provided. One or more iterator registers are provided, wherein the iterator registers each include two or more pointer fields for storing two or more pointers that form a pointer chain leading to a data element. A local state associated with a selected iterator register is generated by performing one or more register operations relating to the selected iterator register and involving pointers in the pointer fields of the selected iterator register. A pointer-linked data structure is updated in the memory system according to the local state.

Claims

1. A memory system comprising:

a pointer-linked data structure comprising nodes; and

an iterator register wherein;

the iterator register includes a plurality of pointer fields that store corresponding pointers;

a plurality of the corresponding pointers form a pointer chain leading to a specific node; and

a portion of the pointer chain is used to access a related node in the pointer-linked data structure.

2. A memory system as recited in claim 1, wherein accessing a related node is accessing a next leaf node.

3. A memory system as recited in claim 1, wherein a successive memory load operation for the pointer-linked data structure performed with the iterator register makes use of part but not all of a fully cached pointer chain in the iterator register.

4. A memory system as recited in claim 1, wherein a memory store operation for the pointer-linked data structure performed with the iterator register makes corresponding modifications to a local state associated with the iterator register, followed by updating the pointer-linked data structure according to the local state.

5. A memory system as recited in claim 1, wherein the pointer-linked data structure is hierarchical.

6. A memory system as recited in claim 1, wherein the pointer-linked data structure is made of immutable memory blocks.

7. A memory system as recited in claim 1, wherein the pointer-linked data structure is deduplicated.

8. A memory system as recited in claim 1, wherein the iterator register stores a plurality of pointer chains simultaneously.

9. A memory system as recited in claim 1, wherein the iterator register maintains a transient line state.

10. A memory system as recited in claim 1, wherein the pointer-linked data structure represents one or more of the following:

a content-addressable memory, a snapshot checkpointing memory, a database, a snapshot of state for lock-free execution, an inverted index, and a sparse matrix.

11. A memory system as recited in claim 1, wherein the iterator register can be made active or inactive under software control.

12. A memory system as recited in claim 1, wherein the iterator register further includes an element field that provides storage for a node.

13. A method of loading data from a computer memory system comprising:

loading into a selected iterator register, from a memory that stores one or more pointer linked data structures, a first pointer chain having two or more pointers leading to a first element of a selected pointer-linked data structure;

loading a second pointer chain having two or more pointers leading to a second element of the selected pointer-linked data structure to the selected iterator register;

wherein the loading of the second pointer chain reuses portions of the first pointer chain that are common with the second pointer chain.

14. A method as recited in claim 13, wherein the second element is a next non-default element in the selected data structure after the first element.

15. A method as recited in claim 14, further comprising performing a prefetch of the second element.

16. A method as recited in claim 13, wherein the selected data structure is sequentially accessed by iterating through the selected iterator register.

17. A method as recited in claim 13, further comprising translating a compacted pointer representation in the selected data structure to a non-compacted pointer representation in the selected iterator register.

18. A method as recited in claim 13, further comprising providing an immutable representation of the selected data structure to ensure that the selected data structure does not change after the first loading and prior to the second loading.

19. A method as recited in claim 18, wherein the immutable representation of the selected data structure is used to provide snapshot semantics for three or more consecutive load operations on the selected data structure by way of the selected iterator register.

20. A method of modifying data stored in a computer memory system, the method comprising:

generating a local state associated with a selected iterator register that includes two or more pointer fields for storing two or more pointers that form a pointer chain leading to a data element by performing one or more register operations relating to the selected iterator register and involving pointers in the pointer fields of the selected iterator register;

updating a pointer-linked data structure in a memory system according to the local state.

21. A method as recited in claim 20, wherein the updating a pointer-linked data structure is performed atomically.

22. A method as recited in claim 20, further comprising translating a non-compacted pointer representation in the selected iterator register to a compacted pointer representation in the pointer-linked data structure.

23. A method as recited in claim 20, wherein the iterator registers each further include an element field that provides storage for the data elements.

24. A method as recited in claim 20, further comprising translating a compacted pointer representation in the selected iterator register to a compacted pointer representation in the pointer-linked data structure.