STORING DATA STRUCTURES IN CACHE

• US 20140013054A1
• Filed: 07/09/2012
• Published: 01/09/2014
• Est. Priority Date: 07/09/2012
• Status: Abandoned Application

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Chang, Jichuan, Ranganathan, Parthasarathy
• Application Number:
  US13/544,575
• Publication Number:
  US 20140013054A1
• Time in Patent Office: Days
• US Class Current: 711/122
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method and system for implementing a data structure cache are provided herein. The method includes identifying a data structure. The method also includes identifying a plurality of frequently accessed data blocks in the data structure. Additionally, the method includes reserving a portion of a cache for storage of the frequently accessed data blocks. Furthermore, the method includes storing the frequently accessed data blocks in the reserved portion of the cache.

Claims

1. A method comprising:

identifying a data structure;

identifying a plurality of frequently accessed data blocks in the data structure;

reserving a portion of a cache for storage of the frequently accessed data blocks; and

storing the frequently accessed data blocks in the reserved portion of the cache.

2. The method of claim 1, comprising:

detecting a requested data block;

determining a cache segment identifier, wherein the cache segment identifier identifies the portion of the cache storing the plurality of frequently accessed data blocks; and

determining the requested data block is stored in the portion of the cache for storage of the frequently accessed data blocks based on the cache segment identifier.

3. The method of claim 1 further comprising generating a stored element bit vector, wherein the stored element bit vector indicates a plurality of elements and a plurality of subfields of the data structure that are stored in the portion of the cache for storage of the frequently accessed data blocks.

4. The method of claim 1 comprising:

calculating a record identifier for each of the frequently accessed data blocks; and

storing the record identifier in a tag array.

5. The method of claim 1 comprising:

detecting a request for a data block;

determining the data block is a frequently accessed data block;

determining the data block is stored in the reserved portion of the cache; and

retrieving the data block from the reserved portion of the cache.

6. The method of claim 5, comprising:

determining that an infrequently accessed data block corresponds to the data block;

retrieving the infrequently accessed data block from a second cache or memory; and

concatenating the data block and the infrequently accessed data block.

7. The method of claim 1, comprising:

detecting a plurality of requests for a plurality of data blocks;

determining the data blocks reside in the portion of the cache for storage of the frequently accessed data blocks; and

concatenating the plurality of data blocks.

8. The method of claim 1, wherein storing the plurality of frequently accessed data blocks in the portion of the cache further comprises calculating a record index for each of the frequently accessed data blocks based on a plurality of memory addresses for the frequently accessed data blocks.

9. A system comprising:

a processor to execute stored instructions;

an L1 cache to store instructions;

an L2 cache to store instructions; and

a data structure module comprising processor executable code that, when executed by the processor, causes the processor to;

identify a data structure;

identify a plurality of frequently accessed data blocks in the data structure;

reserve a portion of a cache for storage of the frequently accessed data blocks;

determine a record identifier for each of the frequently accessed data blocks;

evict data blocks from the portion of the cache for storage of the frequently accessed data blocks;

store the record identifiers in the portion of the cache for storage of the frequently accessed data blocks; and

store the plurality of frequently accessed data blocks in the portion of the cache for storage of the frequently accessed data blocks.

10. The system of claim 9, wherein the processor executable code causes the processor to store a segment identifier in a register.

11. The system of claim 10, wherein the processor executable code causes the processor to translate a plurality of virtual addresses of the frequently accessed data blocks to a plurality of logical addresses.

12. The system of claim 10, wherein the processor executable code causes the processor to calculate a record index based on the memory address of each frequently accessed data block.

13. The system of claim 9, wherein the processor executable code causes the processor to:

create a record identifier for each frequently accessed data block; and

store the record identifier in a tag array.

14. The system of claim 9, wherein the processor executable code causes the processor to generate a stored element bit vector, wherein the stored element bit vector indicates a plurality of elements and a plurality of subfields of the data structure that are stored in the portion of the cache for storage of the frequently accessed data blocks.

15. The system of claim 9, wherein the processor executable code causes the processor to:

detect a plurality of requests for a plurality of data blocks;

determine the data blocks reside in the reserved portion of the cache; and

concatenate the plurality of data blocks.

16. A system comprising:

a processor;

an L1 cache to store instructions;

an L2 cache to store instructions; and

a data structure module comprising a programmable state machine that causes the processor to;

detect a request for a data block;

determine the data block is a frequently accessed data block;

determine the data block is stored in a data structure cache; and

retrieve the data block from the data structure cache.

17. The system of claim 16, wherein the programmable state machine causes the processor to:

determine that an infrequently accessed data block corresponds to the data block;

retrieve the infrequently accessed data block from memory; and

concatenate the data block and the infrequently accessed data block.

18. The system of claim 16, wherein the data structure module resides between a processor and a first cache.

19. The system of claim 16, wherein the data structure module resides between a first cache and a second cache.

20. The system of claim 16, wherein the programmable state machine causes the processor to:

detect a plurality of requests for a plurality of data blocks;

determine the plurality of data blocks reside in the data structure cache; and

concatenate the plurality of data blocks.