Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-05-25
2003-06-10
Breene, John (Department: 2177)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06578107
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to digital data storage systems, such as disk drives, and in particular to prefetching data from a data storage system to a cache memory. Still more particularly, the present invention relates to a method and system for prefetching data where commands are reordered for execution.
2. Description of Related Art
A digital data storage system typically includes one or more storage devices that store data on storage media such as magnetic or optical data storage disks. Within magnetic disk drive systems, a head disk assembly generally consists of one or more hard disks and a hard disk drive controller that is utilized to manage local operations involving the hard disks. The hard disks are rigid platters, typically constructed of aluminum alloy or a mixture of glass and ceramic, which are covered with a magnetic coating. Generally, two or three platters are stacked vertically on a common spindle that is rotated by a disk drive motor.
The only other moving part within a typical hard drive assembly is a head positioning system that has a recording head associated with each side of each platter. In most modern drives, the recording heads are mounted at the end of small ceramic sliders that are elevated just above and below the platter's surface. The sliders are supported by an air bearing surface that is self-pressurized by the airflows generated by the rapidly spinning disk. Each head is also connected to a flexible actuator arm that supports the entire head flying unit. More than one of such arms may be employed together to form a single armature unit.
Each head scans the hard disk platter surface during a “read” or “write” operation. The head/arm assembly is positioned over the hard disk platter surface utilizing an actuator, also called a voice coil actuator, driven by a servo voice coil motor. The stator of the voice coil if motor is mounted to a base plate or casting on which is mounted a spindle supporting the disks. The base plate, in turn, is mounted to a frame via a compliant suspension. When current is applied to the motor, the voice coil motor develops a force, or torque, that is substantially proportional to the applied current. The arm acceleration is therefore substantially proportional to the magnitude of the applied current. As the head approaches the desired track, a reverse polarity signal, acting as a brake, is applied to the actuator, to cause the recording head to stop over a desired location on the platter surface.
After a disk drive controller receives an instruction from a user or a bus master, the controller causes a disk drive motor to actuate disk heads to move to the specified location and retrieve the requested data. The time required to store and retrieve data on disk drives is a function of four key parameters: seek times, rotational latencies, data transfer times and overheads. These factors are designed into the disk drive along with features incorporated into the drives to lessen the impact of these parameters in various workloads and logical environments. The term “workload” describes the dynamic qualities of the requests to store and retrieve data such as transfer length, transfer direction (to/from drive, store/retrieve or write/read), spatial location of data relative to past and future requests, and temporal location, i.e., how fast are the request/commands sent to the drive. “Logical environment” describes the static qualities of the requests along with which features utilized in the drive are allowed to be employed. These features include data caching algorithms, command queuing and command reordering algorithms.
Seek time is the time required to position the disk head over the recording surface. Furthermore, because the disk drives have spinning media platters, a rotational latency while the platter spins to get the data in place for reading and writing is also introduced. Typically, disk I/O performance is dominated by these two factors, i.e., seek and latency, that are introduced by the mechanical parts of the disk in moving to a location where data is stored.
To minimize seek and rotational time delays, data storage systems incorporate disk data caches and command reordering algorithms that utilize command queuing. Disk caches take advantage of the principle of locality of references well known in the programming art. Typically the data from the disk is buffered into a memory device with a relatively fast access time. If the data requested already resides in the cache memory, the controller can transfer the data directly from the cache memory. Performance is increased because accessing data from the cache memory is substantially faster than accessing data from a disk drive.
Command reordering algorithms take advantage of a feature called command queuing. If commands are allowed to be queued, the host system can give the drive controller multiple requested commands, without the drive having completed prior requested commands. Besides other benefits, such as being able to overlap command overhead with seeking, latency and transferring data to/from disk, this means that the drive controller has multiple commands from which to choose a command to execute next. Algorithms can be employed that determine the “best” candidate command to be executed next. The physical design of the disk drive e.g., seek times, latency, and how the data is laid out in the disk surface, along with host system design determine what is “best.” For example, one algorithm may select the next command to be the one that would complete the soonest. Another algorithm may choose a combination of C commands such that the group of C commands would execute faster than any other groups of C commands. Another algorithm may take into account that executing certain types of commands, e.g., requests to certain blocks, reads versus writes, etc., would be better than other types of commands. Despite selecting the “best” command to execute next, there is still “extra” time when the drive is not seeking or transferring data.
For workloads that frequently access data that is located near, and after, previously requested data, cache prefetch techniques are effective in increasing cache hit ratios. However, in high speed workload environments where queuing is employed and command reordering is allowed, any time not spent executing direct requests from a host system, i.e., prefetching data that may be subsequently requested, is considered “lost” time.
There are currently three approaches to increase the cache hit ratio for the workload environments employing command reordering and queuing. One approach uses a minimum prefetch algorithm. As defined in the Small Computer Systems Interface (SCSI) standard, minimum prefetch instructs the drive that it must prefetch “X” amount of data blocks following the completion of read commands.
A second approach utilizes a cache segmentation scheme that forces the size of a given cache segment to hold the same amount of data as a physical track. Consequently, track caching algorithms then can require that an entire track be read before executing a subsequent command. Both these approaches involve forcing prefetching of data after the completion of previous commands. However, they also reduce the effectiveness of command reordering algorithms by not allowing certain “best” command candidates to be executed.
The third approach prefetches data located prior to requested data on the next command to be executed, instead of prefetching data located after data requested from a previously executed command. This technique is commonly known as “Zero Latency Reads” (ZLRs). An analysis of several workload environments, however, has indicated that data located after previously requested data is more likely to be accessed than data located before previously accessed data.
According, what is needed in the art is an improved and more efficient method for prefetching data that mitigates the above-discussed limitations.
SUMMARY OF THE INVENTION
It is therefore an object of the
Anderson Clark
Hall David Robison
Kub Alice Louise
Marier Louise Ann
Bracewell & Patterson LLP
Breene John
International Business Machines - Corporation
Pannala S R
Truelson Roy W.
LandOfFree
Method and system for prefetching data where commands are... 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 system for prefetching data where commands are..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for prefetching data where commands are... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3154533