 |
References  |
|
|
| *references marked with an asterisk below are user-added references |
 |
U.S. References |
|
|
| Add a new US reference: |
| | Reference | Relevancy | Comments | Reference | Relevancy | Comments | 5457793
Elko
Oct,1995 |  Your vote accepted
[0 after 0 votes] | | 5434992
Mattson
Jul,1995 | Your vote accepted
[0 after 0 votes] | | 5390318
Ramakrishnan
711/158
Feb,1995 | Your vote accepted
[0 after 0 votes] | | 5297265
Frank
Mar,1994 | Your vote accepted
[0 after 0 votes] | | 5150472
Blank
711/137
Sep,1992 | Your vote accepted
[0 after 0 votes] | | 5140690
Hata
714/5
Aug,1992 | Your vote accepted
[0 after 0 votes] | | 5113510
Hillis
711/121
May,1992 | Your vote accepted
[0 after 0 votes] | | 5043885
Robinson
711/133
Aug,1991 | Your vote accepted
[0 after 0 votes] | | 4956803
Tayler
711/113
Sep,1990 | Your vote accepted
[0 after 0 votes] | | 4951194
Bradley
711/132
Aug,1990 | Your vote accepted
[0 after 0 votes] | | 4920478
Furuya
711/136
Apr,1990 | Your vote accepted
[0 after 0 votes] | | 4905139
Asai
711/136
Feb,1990 | Your vote accepted
[0 after 0 votes] | | 4835686
Furuya
711/136
May,1989 | Your vote accepted
[0 after 0 votes] | | 4811203
Hamstra
711/142
Mar,1989 | Your vote accepted
[0 after 0 votes] | | 4802086
Gay
711/133
Jan,1989 | Your vote accepted
[0 after 0 votes] | | 4785395
Keeley
711/122
Nov,1988 | Your vote accepted
[0 after 0 votes] | | 4783735
Miu
711/136
Nov,1988 | Your vote accepted
[0 after 0 votes] | | 4695943
Keeley
711/140
Sep,1987 | Your vote accepted
[0 after 0 votes] | | 4530054
Hamstra
711/133
Jul,1985 | Your vote accepted
[0 after 0 votes] | | 4507729
Takahashi
714/48
Mar,1985 | Your vote accepted
[0 after 0 votes] | | 4490782
Dixon
711/136
Dec,1984 | Your vote accepted
[0 after 0 votes] | | 4489378
Dixon
710/33
Dec,1984 | Your vote accepted
[0 after 0 votes] | | 4464712
Fletcher
711/122
Aug,1984 | Your vote accepted
[0 after 0 votes] | | 4463424
Mattson
711/136
Jul,1984 | Your vote accepted
[0 after 0 votes] | | 4463420
Fletcher
711/133
Jul,1984 | Your vote accepted
[0 after 0 votes] | | 4437155
Sawyer
711/136
Mar,1984 | Your vote accepted
[0 after 0 votes] | | 4334289
Lange
711/160
Jun,1982 | Your vote accepted
[0 after 0 votes] | | 4322795
Lange
711/136
Mar,1982 | Your vote accepted
[0 after 0 votes] | | 4168541
DeKarske
365/49
Sep,1979 | Your vote accepted
[0 after 0 votes] | | 4008460
Bryant
711/136
Feb,1977 | Your vote accepted
[0 after 0 votes] | | |
|
 |
|
 |
U.S. References |
|
|
|
Foreign References |
|
|
|
|
|
|
|
|
Foreign References |
|
|
|
Other References |
|
|
|
|
|
|
|
|
Other References |
|
|
 |
|
|
|
References |
|
|
|
Claims |
|
|
We claim:
1. A cache within a staged hierarchical memory system of a data processing
system, the cache comprising:
a cache memory for storing a plurality of data blocks, each block belonging
to one of a plurality of data sets;
a cache directory having a list of entries associated with data blocks
stored in the cache memory, wherein the list is configured as an ordered
list having a top position to a bottom position, and further wherein each
entry corresponds to an individual data block and has fields for storing
information including a designation of the data set to which the
corresponding data block belongs;
a directory controller which generates an entry corresponding to a data
block of a given data set when the data block is loaded in the cache, the
directory controller inserts the generated entry into the list at an
insertion point for the given data set corresponding to a calculated
optimal single-reference residency time for the given data set, and
removes the bottom entry from the list, which is at the bottom position of
the list, when an entry is inserted in the list, and further wherein the
directory controller moves an entry in the list to an insertion point for
the given data set of a corresponding data block when the corresponding
data block is referenced in the cache; and
a storage control unit for storing data blocks within the cache memory,
which replaces the data block corresponding to the bottom entry with the
data block corresponding to the entry inserted into the list.
2. The cache according to claim 1, wherein the directory controller
periodically calculates the insertion point for entries of the given data
set such that an entry inserted at the insertion point will have
approximately the optimal single-reference residency time for the given
data set.
3. The cache according to claim 2, wherein the insertion point is
calculated to be directly above a number of entries from the bottom
position equal to:
B+L.times.g.sub.ds
wherein
B=predetermined minimum number of entries
L=total number of entries stored in the list, less B
##EQU3##
f.sub.ds =efficiency ratio for a given data set u=optimal efficiency ratio
for the given data set.
4. The cache according to claim 3, wherein the optimal single-reference
residency time for a given data set is calculated as:
SRRT'.sub.ds =g.sub.ds .times.SRRT.sub.max
wherein,
##EQU4##
f.sub.ds =efficiency ratio for the given data set u=optimal efficiency
ratio for the data set
SRRT.sub.max =maximum single-reference residency time.
5. The cache according to claim 2, wherein the efficiency ratio for a given
data set is calculated as:
##EQU5##
wherein, Add.sub.-- sum.sub.ds =sum of the Visit Extension Times for the
data set that have occurred since the last update
M.sub.ds =total of misses directed to the data set since the last update
SRRT.sub.ds =current single-reference residency time for the data set.
6. The cache according to claim 3, wherein the cache directory inserts a
dummy block at the top position and measures the time the dummy block
remains in the list, the measured time being the maximum single-reference
residency time.
7. The cache according to claim 1, wherein a data block is a data track of
a disk drive, and a data set is a range of device cylinders.
8. A method of dynamic cache memory allocation comprising the steps of:
periodically determining an insertion point, within a list of entries, for
each data set of a plurality of data sets, wherein the insertion point for
a given data set corresponds to a calculated optimal single-reference
residency time for the given data set which is also periodically updated;
maintaining the list of entries, wherein the list is ordered sequentially
from a top position to a bottom position, each entry of the list
corresponding to a data block contained in a cache and having fields for
storing information including a designation of one of a plurality of data
sets to which the corresponding data block belongs, and wherein the bottom
entry, which is at the bottom position of the list, is removed from the
list when an entry is inserted in the list, and further wherein, when a
data block corresponding to an entry in the list is referenced, moving the
entry to the insertion point for the data set corresponding to the data
block;
loading a data block belonging to a given data set of the plurality of data
sets into the cache; and
in response to a data block of a given data set being loaded into the
cache, inserting an entry corresponding to the data block into the list of
entries at the insertion point for the given data set.
9. The method according to claim 8, wherein the step of periodically
determining an insertion point comprises calculating a point where it is
estimated an entry inserted at that point will reach the bottom of the
list, if not referenced, in an amount of time equal to the optimal
single-reference residency time for the data set to which the data block
corresponding to the entry belongs.
10. The method according to claim 8, wherein the step of periodically
determining an insertion point comprises increasing the optimal
single-reference residency time when the corresponding data set has
experienced an increased number of hits in the cache relative to misses
since a most recent update.
11. The method according to claim 8, wherein the step of periodically
determining an insertion point comprises increasing the optimal
single-reference residency time when the corresponding data set has
experienced approximately the same number of hits in the cache relative to
misses since a most recent update, and the entries corresponding to the
data set have spent an increased amount of time in a visit extension phase
since the most recent update.
12. The method according to claim 8, wherein the step of periodically
determining an insertion point comprises calculating the ratio of the
average visit extension time for the data set to the average visit time
for the data set, dividing by a predetermined desired efficiency ratio,
and multiplying a resulting quotient by a maximum single-reference
residency time for the data set to generate an optimal single-reference
residency time for the data set which is updated.
13. The method according to claim 8, wherein the insertion point is
calculated to be directly above a number of entries from the bottom
position equal to:
B+L.times.g.sub.ds
wherein,
B=predetermined minimum number of entries
L=total number of entries stored in the list, less B
##EQU6##
f.sub.ds =efficiency ratio for a given data set u=optimal efficiency ratio
for the given data set.
14. The method according to claim 8, wherein the point is a number of
entries above the bottom entry equal to a fraction of the total entries in
the list, wherein a resulting fraction is equal to the ratio of the
optimal single-reference residency time to a maximum single-reference
residency time.
15. The method according to claim 8, wherein the optimal single-reference
residency time for a given data set is calculated as:
SRRT'.sub.ds =g.sub.ds .times.SRRT.sub.max
wherein,
##EQU7##
f.sub.ds =efficiency ratio for the given data set u=optimal efficiency
ratio for the data set
SRRT.sub.max =maximum single-reference residency time.
16. The method according to claim 15, further comprising the step of
inserting a dummy block at the top position and measuring the time the
dummy block remains in the list, the measured time being a maximum
single-reference residency time.
17. The method according to claim 16, further comprising the step of
periodically updating a maximum single-reference residency time.
18. The method according to claim 15, further comprising the step of saving
time stamps of data blocks for which the time stamp differs from the
current time by no more than a current value of a maximum single-reference
residency time, and if a miss occurs to a data block with a saved time
stamp, updating the maximum single-reference residency time to equal the
difference between the current time and the missed data block's saved time
stamp, and further increasing the maximum single-reference residency time
by a constant amount when a hit occurs to a data block having a saved time
stamp.
19. The method according to claim 8, wherein the efficiency ratio for a
given data set is calculated as:
##EQU8##
wherein, Add.sub.-- sum.sub.ds =sum of Visit Extension Times for the data
set that have occurred since the last update
M.sub.ds =total of misses directed to the data set since the last update
SRRT.sub.ds =current single-reference residency time for the data set.
20. The method according to claim 8, further comprising the step of setting
the optimal single-reference residency time for each data set to a maximum
single-reference residency time when the optimal single-reference
residency time is initially calculated.
21. The method according to claim 8, further comprising the steps of:
maintaining a list of time stamps, wherein the list is configured as linked
entries ordered sequentially from a top position to a bottom position,
each entry of the list of time stamps corresponding to a data block
contained in the cache, and wherein the bottom entry, which is at the
bottom position of the list, is removed from the list when an entry is
inserted in the list, and further wherein, when a data block corresponding
to an entry in the list is referenced, moving the entry to a point in the
list of time stamps equal to the insertion point for the data set
corresponding to the data block;
in response to a data block of a given data set being loaded into the
cache, inserting a date stamp entry corresponding to the data block into
the list of entries at a point in the list of time stamps equal to the
insertion point for the given data set.
22. The method according to claim 21, wherein the step of periodically
determining an insertion point comprises calculating the ratio of a
average visit extension time for date stamps of the particular data set to
the average visit time for the date stamps of the particular data set,
dividing by a predetermined desired efficiency ratio, and multiplying a
resulting quotient by a maximum single-reference residency time for the
data set to generate an optimal single-reference residency time for the
data set which is updated.
23. The method according to claim 21, wherein the efficiency ratio for a
given data set is calculated as:
##EQU9##
wherein, Add.sub.-- sum.sub.ds =sum of Visit Extension Times for time
stamps in the data set that have occurred since the last update
M.sub.ds =total of the misses directed to time stamps belonging to the data
set since the last update
SRRT.sub.max =current maximum single-reference residency time for the data
set.
24. A data processing system comprising:
a staged hierarchical memory system including a cache memory for storing a
plurality of data blocks, each block belonging to one of a plurality of
data sets;
a processor which requests data blocks from and stores data blocks to the
staged hierarchical memory system;
a cache directory having a list of entries associated with data blocks
stored in the cache memory, wherein the list is configured entries ordered
sequentially from a top position to a bottom position, and further wherein
each entry corresponds to an individual data block and has fields for
storing information including a designation of the data set to which the
corresponding data block belongs;
a directory controller which generates an entry corresponding to a data
block of a given data set when the data block is loaded in the cache, the
directory controller inserts the generated entry into the list at an
insertion point for the given data set corresponding to a calculated
optimal single-reference residency time for the given data set, and
removes the bottom entry from the list, which is at the bottom position of
the list, when an entry is inserted in the list, and further wherein the
directory controller moves an entry in the list to an insertion point for
the given data set of a corresponding data block when the corresponding
data block is referenced in the cache; and
a storage control unit for storing data blocks within the cache memory,
which replaces the data block corresponding to the bottom entry with the
data block corresponding to the entry inserted into the list.
25. The data processing system according to claim 24, wherein the directory
controller periodically calculates the insertion point for entries of the
given data set such that an entry inserted at the insertion point will
have approximately the optimal single-reference residency time for the
given data set.
26. The data processing system according to claim 24, wherein the insertion
point is calculated to be directly above a number of entries from the
bottom position equal to:
B+L.times.g.sub.ds
wherein,
B=predetermined minimum number of entries
L=total number of entries stored in the list, less B
##EQU10##
f.sub.ds =efficiency ratio for a given data set u=optimal efficiency ratio
for the given data set.
27. The data processing system according to claim 24, wherein the
efficiency ratio for a given data set is calculated as:
##EQU11##
wherein, Add.sub.-- sum.sub.ds =sum of Visit Extension Times for the data
set that have occurred since the last update
M.sub.ds =total of misses directed to the data set since the last update
SRRT.sub.ds =current single-reference residency time for the data set.
28. The data processing system according to claim 24, wherein the optimal
single-reference residency time for a given data set is calculated as:
SRRT'.sub.ds =g.sub.ds .times.SRRT.sub.max
wherein,
##EQU12##
f.sub.ds =efficiency ratio for the given data set u=optimal efficiency
ratio for the data set
SRRT.sub.max =maximum single-reference residency time.
29. The data processing system according to claim 24, wherein the cache
directory inserts a dummy block at the top position and measures the time
the dummy block remains in the list, the measured time being the maximum
single-reference residency time.
30. The data processing system according to claim 24, wherein a data block
is a data track of a disk drive, and a data set is a range of device
cylinders. |
|
|
|
|
|
|
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to a cache in a data processing
system, and more particularly to a method and apparatus for dynamic cache
memory allocation among data sets.
2. Description of the Related Art
A computer system typically includes an information processor coupled to a
hierarchial stage stored system. The hardware can dynamically allocate
parts of memory within the hierarchy for addresses deemed most likely to
be accessed soon. The type of storage employed in each staging location
relative to the processor is normally determined by balancing requirements
for speed, capacity, and costs. Computer processes continually refer to
this storage over their executing lifetimes, both reading from and writing
to the staged stored system. These references include self-referencing as
well as references to every type of other process, overlay or data. It is
well-known in the art that data storage devices using high-speed random
access memories (RAM) can be referenced orders of magnitude faster than
high volume direct-access storage devices (DASD's) using rotating magnetic
media. Such electronic RAM storage relies upon high-speed transfer of
electrical charges over small distances, while DASD's typically operate
mechanically by rotating a data storage position on a magnetic disk with
respect to read-write heads. The relative cost of a bit of storage for
DASD and RAM makes it necessary to use DASD for bulk storage and
electronic RAM for processor internal memory and caching.
A commonly employed memory hierarchy includes a special, high-speed memory
known as cache, in addition to the conventional memory which includes main
memory and bulk memory. Cache memory speed increases the apparent access
times of the slower memories by holding the words that the CPU is most
likely to access. For example, a computer may use a cache memory that
resides between the external devices and main memory, called a disk cache,
or between main memory and the CPU, called a CPU cache.
The transfer of operands or instructions between main store and CPU cache,
or bulk storage and the disk cache is usually effected in fixed-length
units called blocks. A block of data may be transferred in varying sizes
such as tracks, sectors, lines, bytes, etc., as are known in the art. When
accessing of the disk allows retrieval of necessary data from the cache,
such success is called a "hit", and when retrieval of necessary data
cannot be performed in the cache, such failure is called a "miss".
A high-speed CPU cache enables relatively fast access to a subset of data
instructions which were previously transferred from main storage to the
cache, and thus improves the speed of operation of the data processing
system. Cache memory may also be used to store recently accessed blocks
from secondary storage media such as disks. This cache memory could be
processor buffers contained in main memory or a separate disk cache memory
located between secondary and main storage.
A disk cache is a memory device using a semiconductor RAM or SRAM and is
designed to eliminate an access gap between a high-speed main memory and
low-speed large-capacity secondary memories such as magnetic disk units.
The disk cache is typically in a magnetic disk controller arranged between
the main memory and a magnetic disk unit, and serves as a data buffer.
The principle of a disk cache is the same as that of a central processing
unit (CPU) cache. When the CPU accesses data on disk, the necessary blocks
are transferred from the disk to the main memory. At the same time, they
are written to the disk cache. If the CPU subsequently accesses the same
blocks, they are transferred from the disk cache and not from the disk,
| | |
