Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-11-12
2001-07-10
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S133000, C711S137000, C711S113000, C714S718000, C702S186000
Reexamination Certificate
active
06260113
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to benchmark tests of computer storage disks. More particularly, the invention concerns defining a random miss list, and producing a desired hit ratio in a benchmark test using the miss list.
2. Description of the Related Art
Benchmark performance tests are frequently used to evaluate the performance of computer disk storage products such as, for example, disk drives. Generally, benchmark tests are used to test response time, which is how quickly input/output (I/O) completion occurs when reading or writing, and throughput, which is the number of I/O operations that a drive can process per second. In order to reflect data base accesses in a credible way with these benchmarks, multiple processes must generate I/O concurrently to a shared set of files on the system.
One or more disks and a cache, which is a high speed memory associated with the disk(s), together make up a disk storage system. A hit occurs when the data that is the object of an I/O operation is present in the cache. Conversely, a miss occurs when the data that is the object of an I/O operation is not present in the cache. The hit ratio is the number of hits divided by the total number of I/O operations. Similarly, the miss ratio is the number of misses divided by the total number of I/O operations. Typically, a range of hit ratios must be tested, often including specific anticipated hit-ratios. The I/O operations are typically reads and writes. Because the sum of the hit ratio and the miss ratio equals one, the hit ratio can be determined if the miss ratio is known, and the miss ratio can be determined if the hit ratio is known. A dial-in hit ratio is a hit ratio that can be specified by the user. When data that is the object of an I/O operation is not present in the cache (a miss), typically the data will be loaded into the cache, which is referred to as a stage operation. Commonly, a track of data is loaded in the cache as the result of a stage operation.
A prior art method for producing a desired hit ratio in a benchmark test is illustrated by the tasks
100
of the flowchart in
FIGS. 1A and 1B
. This method has a dial-in hit ratio. In task
105
, the disk area to be tested is divided into N tracks. The disk area to be tested can include one or more entire disk drives and/or portions of one or more disk drives. Preferably, the disk area to be tested is one or more entire disk drive(s). Typically, the disk area to be tested will be drive(s) of a computer on which the benchmark test is run. Preferably, the disk drive is a magnetic disk drive (commonly referred to as a “hard drive”). Alternatively, this method could be used to test other data storage media, for example, optical data storage disks, or magneto-optical data storage disks. This method for producing a desired hit ratio in a benchmark can generally be run on any type of computer system having sufficient computing power to drive the particular I/O system being used.
A track is defined as the largest unit of transfer from disk to cache. Tracks are defined such that a request for data on one track does not enable a hit to occur on any other track. The exact definition of a track is flexible, and need not be related to physical tracks. For example, some or all of the tracks can be logical tracks rather than physical tracks.
Cache misses are obtained or produced as needed by making requests to the tracks identified in a miss list. A single miss list can be used to obtain cache misses for successive benchmark tests, which can also be referred to as experiments. In order to be able to produce misses with a desired frequency, a list of tracks for the miss list is defined (which can also be referred to as being generated). The miss list is defined implicitly, without requiring an array or other memory structure to enumerate the elements of the list. The tracks in the miss list are used for the I/O operations in the benchmark test(s). The miss list consists of L of the available tracks organized in a pseudo-random order. In task
110
in
FIG. 1
, a miss list of L tracks is defined, with L≦N, wherein N represents a number of tracks the disk area to be tested is divided into and with L being larger than the largest number of track images that can be stored in disk cache, which is designated S. L must be larger than the largest number of track images that can be stored in disk cache in order to ensure that elements of the miss list will be cycled out of the cache before possibly being used again, to ensure that a miss will occur if an element is used again. Randomness of the addresses of the tracks chosen for the miss list is desirable because it enhances the reliability of the results of the benchmark test because it spreads the misses randomly throughout the disk area being tested.
A miss will occur the first time a track on the miss list is accessed in an I/O operation. A hit will occur subsequent times that a track on the miss list is accessed in an I/O operation, unless the track is used again after cycling through the entire miss list, or after cycling through enough of the miss list to cause that track to be cycled out of the cache. Thus, the user can select the hit ratio by specifying the probability that a new track on the miss list will be used for an I/O operation.
As shown in task
115
, prior to conducting the first I/O operation of the first benchmark test to be run with a particular miss list, it must be ensured that the cache corresponding with the disk area to be tested does not contain the address of any of the tracks in or on the miss list. This prevents the occurrence of inadvertent hits, and is accomplished by clearing the contents of the cache, or by writing into the cache any data pattern that does not load the addresses of any of the tracks in the miss list in any of the address fields of the cache. If necessary, the cache can be powered down to clear the contents of the cache. When using a single miss list for more than one benchmark test, it is not necessary to clear the cache between benchmark tests or to write a data pattern described above into the cache between benchmark tests, even if different hit ratios are used in the benchmark tests.
The tracks in the miss list are referred to as m(i), for i=0, 1, . . . L−1. In task
120
, the tracks in the miss list are subdivided into groups, with each group having G tracks. G is chosen such that:
(safety factor one)(maximum misses in any single benchmark run)≦
GP ≦L;
(1)
where P is the number of concurrent processes. Safety factor one is included to ensure that no process generates more than G misses in a single experiment. In the prior art, it is known to use a value of 1.5 for safety factor one. The maximum misses in any single benchmark run is estimated as:
(test interval)(physical disks)(miss ratio)/(fastest disk service time);
where the test interval is the period of time of running the benchmark for collecting data, and where the fastest disk service time is the shortest possible time in which data can be retrieved from the disk.
In task
125
, a different group of G tracks from the miss list is assigned to each one of a plurality of concurrent processes. For example, in the first benchmark test (also referred to as an experiment), process zero is assigned the tracks:
m
(
i
),
i=
0,1
, . . . , G−
1;
and process one is assigned the tracks:
m
(
i
),
i=G,G+
1, . . . , 2
G−
1.
This pattern continues until the final process is assigned the tracks:
m
(
i
),
i=
(
P−
1)
G
, (
P−
1)
G+
1, . . . , ((
P−
1)
G+G−
1
=PG−
1).
Assignment of tracks in subsequent experiments continues where the previous assignments leave off, until all of the elements of the miss list have been exhausted. The pattern of assignments then continues by rotating back to the beginning of the miss list. For example, ifi=PG=L−1 represents the last element of the list, then in the second experiment of the example a
Cherian Neena Annie
McNutt Bruce
Altera Law Group LLC
Gossage Glenn
International Business Machines - Corporation
LandOfFree
Method and apparatus defining a miss list and producing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus defining a miss list and producing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus defining a miss list and producing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2526382