US5802600A — Method and apparatus for determining a desirable …

Claim 1

Independent Claim 202 words

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.

Claim 2

Independent Claim 202 words

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.

Claim 3

Dependent Claim 60 words

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.

Claim 4

Dependent Claim 31 words

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.

Claim 5

Dependent Claim 44 words

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.

Claim 6

Dependent Claim 65 words

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.

Claim 7

Dependent Claim 43 words

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.

Claim 8

Dependent Claim 87 words

The method as recited in claim 2, wherein said processor means adjusts said ratio by use of the following expressions: c'=Min((m-f)(Kc+d)/(Km+(K/4)f), w(Kc+d)/(Kw+1)) 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.

Claim 9

Dependent Claim 228 words

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.

Claim 10

Dependent Claim 228 words

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.

Claim 11

Dependent Claim 57 words

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.

Claim 12

Dependent Claim 32 words

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.

Claim 13

Dependent Claim 46 words

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.

Claim 14

Dependent Claim 67 words

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.

Claim 15

Dependent Claim 63 words

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.

Claim 16

Dependent Claim 63 words

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.

Claim 17

Dependent Claim 87 words

The memory device as recited in claim 9, wherein said means for controlling adjusts said ratio by use of the following expressions: c'=Min((m-f)(Kc+d)/(Km+(K/4)f), w(Kc+d)/(Kw+1)) 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.

Claim 18

Dependent Claim 292 words

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.

Claim 19

Dependent Claim 292 words

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.

Claim 20

Dependent Claim 34 words

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.

Claim 21

Dependent Claim 27 words

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.

Claim 22

Dependent Claim 46 words

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.

Claim 23

Dependent Claim 67 words

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.

Claim 24

Dependent Claim 72 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-08-31	2002-03-02	2002-09-01	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-08-31	2006-03-02	2006-09-01	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-08-31	2010-03-02	2010-09-01	$7700.00	Window Closed / Lapsed

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

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag