System and method for increasing cache efficiency through optimized data allocation
First Claim
1. In a computer system having a processor, a main memory store, and a cache memory that is divided into separate cache slots, each cache slot having multiple cache lines, a method for allocating cache lines within a cache slot for storing a data block of data block size and a corresponding header block of header block size that identifies the data block, the method comprising the machine-executed steps of:
- responsive to a request from the processor to use a data block, allocating a cache slot having a slot size to store the requested data block and its corresponding header block, wherein the slot size is larger than the data block size plus the size of the header block;
referencing a predetermined size criterion defining a relationship between the data block size and the cache slot size to determine if the predetermined size criterion is met by this allocation; and
aligning the data block and the corresponding header block within the multiple cache lines in the cache slot according to whether the predetermined size criterion is met, by;
(a) aligning the data block to the beginning of a first half of the cache slot and placing a corresponding header block that identifies the data block in a second half of the cache slot if the predetermined size criterion is met;
or(b) aligning the header block to the beginning of the second half of the cache slot and placing the data block next to the header block so that part of the data block fits in the second half of the cache slot and the remainder of the data block fits in the first half of the cache slot if the predetermined size criterion is not met.
1 Assignment
0 Petitions
Accused Products
Abstract
Logic for decreasing the number of cache lines dedicated to user data. When pools for allocation are selected using a dynamic storage allocation procedure, the size of a data block is compared to the size of the allocated pool. If the comparison results meet a predetermined criterion, the logic aligns the data to the beginning of a cache line and places the header in a separate cache line that may be deallocated. And if the data will fit within one-half of a cache slot in the allocated pool, then the line or lines having the header data can be re-used as the header is deallocated. Otherwise, user data blocks are placed in cache lines that are spatially local.
-
Citations
16 Claims
-
1. In a computer system having a processor, a main memory store, and a cache memory that is divided into separate cache slots, each cache slot having multiple cache lines, a method for allocating cache lines within a cache slot for storing a data block of data block size and a corresponding header block of header block size that identifies the data block, the method comprising the machine-executed steps of:
-
responsive to a request from the processor to use a data block, allocating a cache slot having a slot size to store the requested data block and its corresponding header block, wherein the slot size is larger than the data block size plus the size of the header block; referencing a predetermined size criterion defining a relationship between the data block size and the cache slot size to determine if the predetermined size criterion is met by this allocation; and aligning the data block and the corresponding header block within the multiple cache lines in the cache slot according to whether the predetermined size criterion is met, by; (a) aligning the data block to the beginning of a first half of the cache slot and placing a corresponding header block that identifies the data block in a second half of the cache slot if the predetermined size criterion is met;
or(b) aligning the header block to the beginning of the second half of the cache slot and placing the data block next to the header block so that part of the data block fits in the second half of the cache slot and the remainder of the data block fits in the first half of the cache slot if the predetermined size criterion is not met. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A computer system for allocating cache lines within a cache slot for storing a data block of data block size and a corresponding header block of header block size that identifies the data block, the system comprising:
-
a processor; main memory coupled to the processor; cache memory coupled to the main memory and also coupled to the processor; dynamic storage allocation logic that is loaded into main memory for performing the allocation of cache lines; and the dynamic storage allocation logic having machine-executed means coupled to the processor for aligning the data block and the corresponding header block in response to a processor request to use a data block by; allocating a cache slot having a slot size to store the requested data block and its corresponding header block, wherein the slot size is larger than the data block size plus the size of the header block; referencing a predetermined size criterion defining a relationship between the data block size and the cache slot size to determine if the predetermined size criterion is met by this allocation; and aligning the data block and the corresponding header block within the cache lines in the cache slot according to whether the predetermined size criterion is met; the machine executed means including; means for aligning the data block to the beginning of a first half of the cache slot and placing a corresponding header block that identifies the data block in a second half of the cache slot if the predetermined size criterion is met; and means for aligning the header block to the beginning of the second half of the cache slot and placing the data block next to the header block so that part of the data block fits in the second half of the cache slot and the remainder of the data block fits in the first half of the cache slot if the predetermined size criterion is not met. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A computer program product for use in a computer system having a processor, a main memory store, and a cache memory that is divided into separate cache slots, each cache slot having multiple cache lines, the computer program product being adapted for allocating cache lines within a cache slot for storing a data block of data block size and a corresponding header block of header block size that identifies the data block, the computer program product comprising:
-
a recording medium; first means, recorded on the recording medium, for being responsive to a request from the processor to use a data block by allocating a cache slot having a slot size to store the requested data block and its corresponding header block, wherein the slot size is larger than the data block size plus the size of the header block; second means, recorded on the recording medium, for referencing a predetermined size criterion defining a relationship between the data block size and the cache slot size to determine if the predetermined size criterion is met by this allocation; and third means, recorded on the recording medium, for aligning the data block and the corresponding header block within the multiple cache lines in the cache slot according to whether the predetermined size criterion is met; the third means including; means for aligning the data block to the beginning of a first half of the cache slot and placing a corresponding header block that identifies the data block in a second half of the cache slot if the predetermined size criterion is met; and means for aligning the header block to the beginning of the second half of the cache slot and placing the data block next to the header block so that part of the data block fits in the second half of the cache slot and the remainder of the data block fits in the first half of the cache slot if the predetermined size criterion is not met. - View Dependent Claims (12, 13, 14, 15)
-
-
16. An apparatus for storing a data block of data block size and a corresponding header block of header block size that identifies the data block in a cache memory, the apparatus comprising:
-
a processor; main memory coupled to the processor; cache memory coupled to the main memory and also to the processor, the cache memory being divided into separate cache slots, each cache slot having multiple cache lines; dynamic storage allocation logic loaded into the main memory for allocating a cache slot for storing the data block and its corresponding header block; and the dynamic storage allocation logic including; a processor request module that is adapted to be responsive to a request from the processor to use a data block, by allocating a cache slot having a slot size to store the requested data block and its corresponding header block, wherein the slot size is larger than the data block size plus the size of the header block; a referencing and criterion determining module that is adapted to reference a predetermined size criterion defining a relationship between the data block size and the cache slot size to determine if the predetermined size criterion is met by this allocation; and an alignment module that is adapted to align the data block and the corresponding header block within the multiple cache lines in the cache slot according to whether the predetermined size criterion is met by, either, aligning the data block with a beginning of a first half of the cache slot and placing the corresponding header block in a second half of the cache slot if the predetermined size criterion is met; or, aligning the corresponding header block with a beginning of the second half of the cache slot and placing the data block next to the header block, with a portion of the data block being in the second half of the cache slot.
-
Specification