System and method for increasing cache efficiency through optimized data allocation

• US 5,651,136 A
• Filed: 06/06/1995
• Issued: 07/22/1997
• Est. Priority Date: 06/06/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Denton, James L., Griffin, Kevin Curtis, Ryan, Sandra Kay, Eickemeyer, Richard James, Lipasti, Mikko Herman, Kunkel, Steven Raymond, Johnson, Ross Evan
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Chow, Christopher S.
• Application Number:
  US08/470,315
• Time in Patent Office: 777 Days
• Field of Search: 395/445, 395/481, 395/497.01, 395/497.04, 395/456, 395/497.02
• US Class Current: 711/118
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing

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.

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.

2. The method of claim 1, wherein the predetermined size criterion is met if the size of the data block is less than or equal to the size of the cache slot divided by two.

3. The method of claim 1, step (a) further comprising the machine-executed steps of:

(a1) transferring the header block from the second half of the cache slot into main memory; and

(a2) deallocating the second half of the cache slot following the transferring of the header block.

4. The method of claim 1, wherein the cache slot is selected from a plurality of cache slots grouped in a pool of cache slots and each cache slot grouped together in a pool has the same slot size as each other cache slot in the pool, wherein each pool is selected according to a segregated storage procedure.

5. The method of claim 4, wherein the segregated storage procedure selects pools having cache slots with sizes that are ordered in powers-of-two.

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.

7. The system of claim 6, the means for aligning the data block further including data transferring means to transfer the header block from the second half of the cache slot into main memory and means for deallocating the second half of the cache slot following the transferring of the header block.

8. The system of claim 6, wherein the predetermined size criterion is met if the size of the data block is less than or equal to the size of the cache slot divided by two.

9. The system of claim 6, wherein the cache slot is selected from a plurality of cache slots grouped in a pool of cache slots and each cache slot grouped together in a pool has the same slot size as each other cache slot in the pool, wherein each pool is selected according to a segregated storage procedure.

10. The system of claim 9, wherein the segregated storage procedure selects pools having cache slots with sizes that are ordered in powers-of-two.

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.

12. The computer program product of claim 11, wherein the predetermined size criterion is met if the size of the data block is less than or equal to the size of the cache slot divided by two.

13. The computer program product of claim 11, the means for aligning the data block further including means for transferring the header block from the second half of the cache slot into main memory, and also further including means, recorded on the medium, for deallocating the second half of the cache slot following the transferring of the header block.

14. The computer program product of claim 11, wherein the cache slot is selected from a plurality of cache slots grouped in a pool of cache slots and each cache slot grouped together in a pool has the same slot size as each other cache slot in the pool, wherein each pool is selected according to a segregated storage procedure.

15. The computer program product of claim 14, wherein the segregated storage procedure selects pools having cache slots with sizes that are ordered in powers-of-two.

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.