Method and apparatus for determining a desirable directory/data block ratio in a cache memory

• US 5,802,600 A
• Filed: 11/12/1996
• Issued: 09/01/1998
• Est. Priority Date: 11/12/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Carpenter, Kelly, King, Gary Malcolm, Smith, Kevin Frank
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Lee, Felix B.
• Application Number:
  US08/747,721
• Time in Patent Office: 658 Days
• Field of Search: 711/153, 711/130, 711/129, 711/173
• US Class Current: 711/173
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory

Abstract

A data processing system dynamically balances allocation of storage areas in a shared coupling facility that is devoted to storage of directory entries and data blocks. Each directory entry includes information regarding the validity of a data block that is locally stored by one or more processor modules in the data processing system. The system includes a coupling facility having a cache memory wherein a first portion is allocated to storage of data blocks and a second portion is allocated to storage of directory entries. Each directory entry, associated with a data block, indicates the validity or invalidity of data contained in a copy of the data block maintained by a connected computer module in its local memory. Each computer module, upon requiring a first data block and determining that (i) the first data block is present in its local memory (i.e., a buffer "hit"), but (ii) is not marked valid and (iii) is not present in the coupling facility (i.e., a cache "miss"), accesses the first data block from a disk store, even though the first data block in its local memory may be valid. A memory allocation procedure controls the sizes of the first portion and second portion of the cache memory. The procedure (i) maintains a record, per unit of time, of a number of cache "miss" occurrences, (i.e., a cache "miss" rate) and an estimate of the number of false invalidation occurrences (i.e., a false invalidation rate); derives a first order derivative of the sum of cache miss-rate and the estimated false invalidation rate and (iii) employs the derivative to adjust the sizes of the first portion and second portion of the cache memory so as to minimize the sum of the expected miss and false invalidation rate values.

Claims

1. A method for dynamically balancing storage allocations in a computer system that includes cache memory that is accessible from plural computer modules, each computer module including local memory for storage of data blocks, the cache memory including a first portion for storing plural data blocks and a second portion for storing directory entries, each directory entry including information regarding a validity status of an associated data block, said method comprising the steps of:

a) maintaining a first record of a number of cache misses over a time period, each cache miss occurring when a computer module does not find a desired data block resident in said cache memory;

b) maintaining a second record of a number of false invalidations over a time period, each false invalidation occurring when a desired data block is resident in a computer module'"'"'s local memory but a directory entry for said desired data block with a validity status indication therefor, is absent from said cache memory; and

c) employing said first record and second record to adjust a ratio of size allocations of said first portion and second portion so as to reduce at least one of said number of false invalidations and number of cache misses.

2. The method as recited in claim 1, wherein step c) includes the further step of:

c1) employing a derivative of a sum of (i) a cache miss rate derived from said first record, and (ii) a false invalidation rate derived from said second record, to determine a cache miss value and a false invalidation value, which together minimize said derivative.

3. The method as recited in claim 1, wherein said employing step c) is performed at intervals to re-adjust said ratio of said size allocations of said first portion and second portion.

4. The method as recited in claim 3, wherein employing step c) re-adjusts said ratio of said size allocations of said first portion and second portion only if a difference of said ratio before adjustment and said ratio after adjustment exceeds a randomly derived value.

5. The method as recited in claim 3, wherein employing step c) re-adjusts said ratio of said size allocations of said first portion and second portion by a full determined amount only if said full determined amount does not exceed a threshold value, and if said full determined amount does exceed said threshold value, adjusting said ratio by a value less than said full determined amount.

6. The method as recited in claim 2, wherein said employing step c) is inhibited if a number of data blocks and directory entries in said cache memory increases or decreases, as the case may be, by a value greater than a preset value.

7. The method as recited in claim 2, wherein said processor means adjusts said ratio by use of the following expressions:

space="preserve" listing-type="equation">c'"'"'=Min((m-f)(Kc+d)/(Km+(K/4)f), w(Kc+d)/(Kw+1))

space="preserve" listing-type="equation">d'"'"'=K(c-c'"'"')+d

where;

c=average no. of physical data blocks in cache during a test interval;

m=number of cache misses;

d=average number of directory entries during said test interval;

f=number of false invalidations;

w=average number of physical data blocks per logical data block;

K=number of directory entries in a physical data block memory size

c'"'"'= adjusted number of logical data blocks;

d'"'"'= adjusted number of directory entries.

8. A memory device including a procedure for dynamically balancing storage allocations when used in conjunction with a computer system, said computer system including cache memory that is accessible from plural computer modules, each computer module including local memory for storage of data blocks, the cache memory including a first portion for storing plural data blocks and a second portion for storing directory entries, each directory entry including information regarding a validity status of an associated data block, said memory device comprising:

means for maintaining a first record of a number of cache misses over a time period in respect of said cache memory, each cache miss occurring when a computer module does not find a desired data block resident in said cache memory;

means for maintaining a second record of a number of false invalidations over a time period, each false invalidation occurring when a desired data block is resident in a computer module'"'"'s local memory but a directory entry for said desired data block with a validity status indication therefor, is absent from said cache memory; and

means for controlling a processor present in said computer system to employ said first record and second record to adjust a ratio of size allocations of said first portion and second portion so as to reduce at least one of said number of false invalidations and number of cache misses.

9. The memory device as recited in claim 8, wherein said means for controlling employs a derivative of a sum of (i) a cache miss rate derived from said first record, and (ii) a false invalidation rate derived from said second record, to determine a cache miss value and a false invalidation value, which together minimize said derivative.

10. The memory device as recited in claim 8, wherein said means for controlling operates at repeated intervals to re-adjust said ratio of said size allocations of said first portion and second portion.

11. The memory device as recited in claim 10, wherein said means for controlling re-adjusts said ratio of said size allocations of said first portion and second portion only if a difference of said ratio before adjustment and said ratio after adjustment exceeds a randomly derived value.

12. The memory device as recited in claim 10, wherein said means for controlling re-adjusts said ratio of said size allocations of said first portion and second portion by a full determined amount only if said full determined amount does not exceed a threshold value, and if said full determined amount does exceed said threshold value, adjusting said ratio by a value less than said full determined amount.

13. The memory device as recited in claim 8, wherein, if a number of data blocks and directory entries in said cache memory increases by a value greater than a preset value, at least a portion of said cache memory that increased in size is allocated in accord with a ratio which favors a space allocation for data blocks as contrasted to directory entries.

14. The memory device as recited in claim 8, wherein, if a number of data blocks and directory entries in said cache memory decreases by a value greater than a preset value, at least a portion of said cache memory that decreased in size is allocated in accord with a ratio which favors a space allocation for directory entries as contrasted to data blocks.

15. The memory device as recited in claim 9, wherein said means for controlling adjusts said ratio by use of the following expressions:

space="preserve" listing-type="equation">c'"'"'=Min((m-f)(Kc+d)/(Km+(K/4)f), w(Kc+d)/(Kw+1))

space="preserve" listing-type="equation">d'"'"'=K(c-c'"'"')+d

where;

c=average no. of physical data blocks in cache during a test interval;

m=number of cache misses;

d=average number of directory entries during said test interval;

f=number of false invalidations;

w=average number of physical data blocks per logical data block;

K=number of directory entries in a physical data block memory size

c'"'"'=adjusted number of logical data blocks;

d'"'"'=adjusted number of directory entries.

16. A data processing system including means for dynamically balancing storage allocations of a cache memory in a shared cache memory, the cache memory storing directory entries and data blocks, each directory entry including information regarding validity of at least a data block locally stored with one or more processor modules in said data processing system, said data processing system comprising:

a cache memory with a first portion allocated for storage of data blocks and a second portion allocated for storage of directory entries, each directory entry indicating a validity status indication for data contained in a data block;

plural computer modules coupled to said cache memory, each having local memory for storage of data blocks, a processor module, upon requiring a first data block and determining that (i) said first data block is present in local memory in said processor module, (ii) and neither a directory entry corresponding to said first data block or a copy of said first data block is present in said cache memory (i.e., a cache miss), performing an access of said first data block from a disk store, even though said first data block in local memory may be valid, (i.e., a false invalidation); and

processor means associated with said coupling facility for controlling a ratio of sizes of said first portion and second portion by a memory allocation procedure, said procedure (i) maintaining a record of a number of cache miss occurrences (i.e., a cache miss rate) and of a number of false invalidation occurrences (i.e., a false invalidation rate) (ii) deriving a function of a sum of said cache miss rate and said false invalidation rate and (iii) employing said function to adjust said ratio of said sizes of said first portion and second portion.

17. The data processing system as recited in claim 16, wherein said processor means adjusts said ratio of said sizes of said first portion and second portion by selecting a ratio which minimizes said function.

18. The data processing system as recited in claim 16, wherein said processor means periodically adjusts said ratio of said sizes of said first portion and second portion.

19. The data processing system as recited in claim 18, wherein said processor means re-adjusts said ratio of said size allocations of said first portion and second portion only if a difference of said ratio before adjustment and said ratio after adjustment exceeds a randomly derived value.

20. The data processing system as recited in claim 18, wherein said processor means re-adjusts said ratio of said size allocations of said first portion and second portion by a full determined amount only if said full determined amount does not exceed a threshold value, and if said full determined amount does exceed said threshold value, adjusting said ratio by a value less than said full determined amount.

21. The data processing system as recited in claim 17, wherein said processor means re-adjusts said ratio to favor data blocks if a number of data blocks and directory entries in said cache memory increases by a value greater than a preset value or re-adjusts said ratio to favor directory entries if a number of data blocks and directory entries in said cache memory decreases by a value greater than a preset value.