Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1998-07-02
2001-07-10
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S113000, C711S114000, C711S167000
Reexamination Certificate
active
06260108
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to data transfer arrangements in multiple disk systems and specifically to a system and method for optimizing data throughput in an input/output (I/O) bus coupled to a plurality of disk drives.
BACKGROUND OF THE INVENTION
In the past decade, computer systems have enjoyed a hundred-fold increase in processor speed, while the speed of disk drives has increased by less than a factor of 10. As a consequence of this disparity, computer systems that run applications that perform I/O-intensive processing, are designed to use many disks in parallel, usually organized as a disk farm or a RAID array. The physical organization generally consists of one or more I/O buses, (e.g., SCSI, FC, or SSA) with several disks on each bus.
Previous work related to disk I/O performance has focused on the disk drive, down playing the importance of bus contention and other bus effects. Indeed, the bus effects play an insignificant role in I/O performance for workloads with small I/O request sizes. But many I/O-intensive applications benefit significantly from larger requests (8-128 KB). Among these are multimedia servers and certain database and scientific computing applications that use external memory and out-of-core algorithmic techniques to process massive data sets. In such applications, parallel I/O performance is often limited by the bus.
Some prior art systems have attempted to implement a model of a computer system that retrieves data from a plurality of disk drives that are coupled to a bus, for example, a bus that employs a Small Computer System Interface (SCSI) protocol. Others have presented detailed performance studies for single disk systems, and approximation techniques for multiple disk systems. For several important workloads, the previous disk models fail to give an accurate prediction of system performance.
Thus there is a need for a system and a method for obtaining an analytical model of a bus supporting multiple disks, and based on that model, implementing a system that is configured to optimize the data throughput traveling via that bus.
SUMMARY OF THE INVENTION
In accordance with one embodiment of the invention, a computer system accesses data located in a plurality of disk drives coupled to a disk bus having a predetermined bus bandwidth. Each disk drive includes a buffer or cache memory for storing data intended to be transferred via the bus or onto the disk surface. The data from the disk are stored in the cache memory at a disk rotational bandwidth, and the data from cache to the disk bus are transferred at the bus bandwidth. During each read iteration, each disk drive loads its disk cache with the next request's data while the bus is being used by other disk drives to transfer the data for the current requests. Thus, each disk drive retrieves the data for the following read iteration from each disk to the corresponding disk cache, while data for the current read iteration is being provided from each disk cache to the disk bus.
In accordance with another embodiment of the invention, during each read iteration, each drive loads its disk cache with the data in the disk sector located before the sector that contains the data required for the next request. Thus, each disk drive retrieves the data for the following read iteration from each disk to the corresponding disk cache using a disk pre-fetch feature while data for the current read iteration is being provided from each disk cache to the disk bus.
In accordance with another embodiment of the invention, a computer system includes a plurality of disk drives each disk drive having a disk cache with a zero fence parameter value coupled to a host computer via a common bus, a read duration estimator for measuring the average time to read data blocks in each one of the disk drives comprises an overhead unit configured to provide the time during which a request is created and sent from a host computer to a disk drive via the bus. A minimum positioning time estimator is also included and is configured to measure the shortest time required for a disk drive to locate the data block. A mechanism-to-cache read time estimator is included and is configured to measure the time required for a leading portion of a requested data block to be transferred to a disk cache with the minimum positioning time. A data block read time estimator is configured to measure the time required to transfer data blocks remaining after transmitting to the host a corresponding leading portion of a requested data block in each of the disk caches. An adder is coupled to the overhead unit, the minimum positioning time estimator, the mechanism-to-cache read time estimator, and the data block read time estimator to provide an estimated duration for data request.
It is noted that in accordance with another embodiment of the invention, the read duration estimator employs a disk drive with a non-zero fence parameter. Thus, a computer system in accordance with this embodiment comprises an overhead unit configured to provide the time during which a request is created and sent from a host computer to a disk drive via the bus. A minimum positioning time estimator is configured to measure an expected minimum positioning time corresponding to the shortest time required for a disk drive to locate the requested data block. A mechanism-to-cache read time estimator is configured to provide the time required for a disk drive to transfer a data portion to a disk cache. A data block read time estimator is configured to measure the time required to transfer data blocks stored in each of the disk caches to the host. An adder is coupled to the overhead unit, the minimum positioning time estimator, the mechanism-to-cache read time estimator, and the data block read time estimator to provide an estimated duration for a data request.
REFERENCES:
patent: 5313585 (1994-05-01), Jeffries et al.
patent: 5592630 (1997-01-01), Yamagami et al.
patent: 5659539 (1997-08-01), Porter et al.
patent: 5752067 (1998-05-01), Wilkinson et al.
patent: 5761417 (1998-06-01), Henley et al.
patent: 5890207 (1999-03-01), Sne et al.
Arunachalam, M., Choudhary, A., and Rullman, B. “A prefetching prototype for the parallel file system on the Paragon.” Proceedings of ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems (Ottawa, Canada), pp. 321-323, May 1995.
Barve, R.D., Grove. E.F., and Vitter, J.S. Simple randomized mergesort on parallel disks. Parallel Computing, 23 (4):601-631. North-Holland (Elsevier Scientific) Jun. 1997.
Bitton, D., and Gray, J. “Disk Shadowing” Proceedings of the 14th International Conference on Verly Large Data Bases (Los Angeles, CA), pp. 331-338, 1988.
Cao, P., Felten, E.W., Karlin, A.R. and Li, K. Implementation and performance of integrated application-controlled caching, prefetching and disk scheduling.ACM Transaction of Computer Systems (TOCS)ACM Press, Nov. 1996.
Cormen, T.H. and Hirschl. M. Early experiences in evaluation the Parallel Disk Model with he ViC* implementation.Parallel Computing, 23(4):571-600. North-Holland (Elsevier Scientific) Jun. 1997.
Hennessy, J.L. and Patterson D.A. Computer architecture: a quantitative approach. Morgan Kaufmann Publishers, Incorporated, San Francisco, CA. 1996, 2nd Ed.
Kimbrel, et al. A trace-driven comparison of algorithms for parallel prefetching and caching. Proceedings of the 1996 Symposium on Operations Systems Design and Implementation (Seattle, WA), pp. 19-34, USENIX Association, Oct. 1996.
Mowry, Denke and Krieger. Automatic compiler-inserted I/O prefetching for out-of-core applications. Proceedings of the 1996 Symposium on Operationg Systems Design and Implementation (Seattle, WA), pp. 3-17, USENIX Association, Oct. 1996.
Elizabeth Shriver, 1997. “Performance modeling for realistic storage devices” PhD thesis, Department of Computer Science, New York University, New York, NY.
Barve Rakesh D.
Gibbons Phillio B.
Hillyer Bruce K.
Matias Yossi
Shriver Elizabeth
Anderson Matthew D.
Kim Matthew
Lucent Technologies - Inc.
LandOfFree
System and method for modeling and optimizing I/O throughput... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for modeling and optimizing I/O throughput..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for modeling and optimizing I/O throughput... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2449264