Alan J. Smith
Abstract
The current trend of computer system technology is toward CPUs with rapidly increasing processing power and toward disk drives of rapidly increasing density, but with disk performance increasing very slowly if at all. The implication of these trends is that at some point the processing power of computer systems will be limited by the throughput of the input/output (I/O) system.
A solution to this problem, which is described and evaluated in this paper, is disk cache. The idea is to buffer recently used portions of the disk address space in electronic storage. Empirically, it is shown that a large (e.g., 80-90 percent) fraction of all I/O requests are captured by a cache of an 8-Mbyte order-of-magnitude size for our workload sample. This paper considers a number of design parameters for such a cache (called cache disk or disk cache), including those that can be examined experimentally (cache location, cache size, migration algorithms, block sizes, etc.) and others (access time, bandwidth, multipathing, technology, consistency, error recovery, etc.) for which we have no relevant data or experiments. Consideration is given to both caches located in the I/O system, as with the storage controller, and those located in the CPU main memory. Experimental results are based on extensive trace-driven simulations using traces taken from three large IBM or IBM-compatible mainframe data processing installations. We find that disk cache is a powerful means of extending the performance limits of high-end computer systems.
- 1 AMDAHL, G.M. Storage and IO parameters and systems potential. In Proceedings of the IEEE Computer Group Conference (Washington, D.C., June 16-18). IEEE. New York, 1970, pp. 371- 372.Google Scholar
- 2 ARTIS, H.P. Calculating head of string utilization in a shared DASD environment. In Proceedings of the CMG International Conference (Dec. 6-8, Washington, D.C.). Computer Measurement Group, 1983, pp. 62-65.Google Scholar
- 3 BASTIAN, A. L., HYDE, J. S., AND LANGSTROTH, W. E. Characteristics of DASD use. In Proceedings of the CMG 12th International Conference (Dec. 1-4, New Orleans, Dec.). Computer Measurement Group, 1981, pp. 107-109.Google Scholar
- 4 BASTIAN, A. L. Cached DASD performance prediction and validation. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, pp. 174-177.Google Scholar
- 5 BATALDEN, G. D., CRABTREE, M. R. AND GOURNEAU D.A. DASD cache for file subsystem. IBM Tech. Disc. Bull. 27, 6 (Nov. 1984), 3433-3435.Google Scholar
- 6 BELADY, L.A. A study of replacement algorithms for a virtual storage computer. IBM Sys. J. 5, 2 (1966), 78-101.Google Scholar
- 7 BENNETT, B. T. AND MAY, C. Improving performance of buffered DASD to which some references are sequential. IBM Tech. Disc. Bull. 24, 3 {Aug. 1981), 1559-1562.Google Scholar
- 8 BERBECK, S., SHIBAMIYA A., TOGASAKI, S., AND YOSHIDA, H. Use of direct access storage devices by MVS customersiGuide survey results. In Proceedings o/the Guide 47 Conference (Chicago, Nov. 10). 1978, pp. 1121-1138.Google Scholar
- 9 BERETVAS, T. Performance tuning in OS/VS2 MVS. IBM Sys. d. 17, 3 {1978), 290-313.Google Scholar
- 10 BRANDWAJN, A. Models of DASD subsystems: Basic model of reconnection. Perform. Eval. 1 (1981), 263-281.Google Scholar
- 11 BOZEN J.P. BEST/1 analysis of the IBM 3880-13 cached storage controller. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, pp. 156-172.Google Scholar
- 12 COMPUTERWORLD. Cache memory reduces data transfer time. Computer (Feb., 1982), 103Google Scholar
- 13 COMPUTERWORLD. HP 3000 access time slashed 400%. Computerworld {Feb. 8, 1982), 109.Google Scholar
- 14 COMPUTERWORLD. Cache disk system out for IBM ACP. Computerworld (June 7, 1982), 101.Google Scholar
- 15 COMPUTERWORLD. Cache disk system speeds access for power firm. ComputerworM {Dec, 6, 1982), 34.Google Scholar
- 16 COMPUTERWORLD. Amdahl offers cache for new, older, drives. Computerworld (Mar. 12, 1984), 4.Google Scholar
- 17 COMPUTERWORLD. Storage Technology Corp., Sybercache statistical product. Computerworld (July 9, 1984), 80.Google Scholar
- 18 COTE, H. J. AND DUHL, B. New horizons for cached disk and buffered tape. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, pp. 333-337.Google Scholar
- 19 DAttMAN, K. AND GROSSMAN, G. Effective use of cached DASD in a data base/data communications environment. In Proceedings of the 1983 CMG International Conference (Washington, D.C., Dec.). 1983, pp. 425-431.Google Scholar
- 20 DATE, C. J. An Introduction to Database Systems. 2nd ed., Addison-Wesley, Reading, Mass., 1977. Google Scholar
- 21 DENSINC,, P.J. On modelling program behavior. In Proceedings of the Spring Joint Computer Conference, vol. AFIPS Press, Reston, Va., 1972, pp. 937-944.Google Scholar
- 22 DIxoN, J. D., MARAZAS G. A., AND McNEILL, A.B. Mini-ops--A microcoded data transfer scheduling and execution systems for the optimized control of an I/O controller cache memory. IBM Tech. Disc. Bull. 27, 2 {July, 1984), 1226-1227.Google Scholar
- 23 DODSON, G.W. Cached DASD evaluations for paging and non-paging data. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, p. 338.Google Scholar
- 24 DUKE, A. H., HARTUNG, M. H., HUNTLEY, J. D., AND MARSCHNER, F.J. Buffered writing in a peripheral storage hierarchy. IBM Tech. Disc. Bull. 25, 4 (Sept. 1982), 2075-2076.Google Scholar
- 25 DUKE, A. H. AND HARTUNG, M. H. Controlling multitrack references in a cached storage system. IBM Tech. Disc. Bull. 25, 7B (Dec. 1982), 3756-3757.Google Scholar
- 26 DUKE, A. H., HARTUNG, M. H., HUNTLEY, J. D., AND NOLAN K.P. Inhibiting cache loading. IBM Tech. Disc. Bull. 25, 12 (May 1983), 6351-6353.Google Scholar
- 27 ELECTRONICS I. Cache memories catch on for disks. Electronics (Apr. 21, 1981), 62-63.Google Scholar
- 28 ELECTRONIC NEWS. IBM expands CPU for system 38; adds series 1 processor, disk drive. Electron. News (Apr. 11, 1983).Google Scholar
- 29 ELECTRONIC NEWS. New HP 16-bit CPUs Based on OS Upgrades. Electron. News (May 30, 1983), 18.Google Scholar
- 30 ELECTRONIC NEWS. IBM Increases Memory, Cuts Tag on 3880 Controller. Electron. News (Sept. 24, 1984), 27, 39.Google Scholar
- 31 ELECTRONIC NEWS. Storage Tek Offers Controller Upgrade. Electron. News (Aug. 13, 1984), 33.Google Scholar
- 32 FAJMAN, R. AND BORGELT, J. Wylbur: An interactive text editing and remote job entry system. Commun. ACM 16, 5 (May, 1973), 314-322. Google Scholar
- 33 FRIEDMAN, M. "DASD access patterns" In Proceedings of the 1983 CMG International Conference, (Dec. 1-4 Washington, D. C.). 1983, pp. 51-61.Google Scholar
- 34 GALE, L. Work station performs at the superminicomputer level. Electronics (Sept. 8, 1983), 119-123.Google Scholar
- 35 HARKER, J. M., BREDE, D. W., PATTISON, R. E., SANTANA, G. R., AND TAFT, L.G. A quarter century of disk file innovation. IBM J. Res. Devel. 25, 5 (Sept. 1981), 677-689.Google Scholar
- 36 HOAGLAND, A.S. Storage technology: Capabilities and limitations. Computer 12, 5 (May 1979) 12-18.Google Scholar
- 37 HODGES, D.A. A review and projection of semiconductor components for digital storage. Proc. IEEE 63, 8 (Aug. 1975), 1136-1147.Google Scholar
- 38 HUGELSHOFER W. AND SHULTZ, }~, Cache buffer for disk accelerates minicomputer performance. Electronics (Feb. 10, 1982), 155-159.Google Scholar
- 39 HUNTER, D. Modeling real DASD configurations. IBM Res. Rep. RC 8606, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1980.Google Scholar
- 40 HUNTER, D.W. DASD arm buffers. IBM Tech. Disc. Bull. 24, 4 (Sept. 1981), p. 2035.Google Scholar
- 41 INFOWORLD. Cache/Q Disk buffering enhancement for CP/M. Infoworld 5, 7 (Jan. 14, 1983), 50-54.Google Scholar
- 42 INTEL. FAST-3805 Functional Description. PN 19-1619-006 (Aug. 1979), Intel Commercial Systems Division, Phoenix, Ariz.Google Scholar
- 43 IBC/INTEORATED BUSINESS COMPUTERS. CADET/10 cache disk memory reference manual. integrated Business Computers, Chatsworth, Calif., 1982.Google Scholar
- 44 IBM. Reference manual for the IBM 2835 storage control and the IBM 2305 fixed head storage module. GA26-1589, IBM Corporation, 1972, San Jose, Calif.Google Scholar
- 45 IBM. Reference manual for IBM 3830 storage control and IBM 3330 disk storage. GA26-1592, IBM Corporation, Armonk, N.Y.Google Scholar
- 46 IBM. OS/VS2 system programming library: Service aids. GC28-0674-1, IBM Corporation, Gaithersburg, Md., 1976.Google Scholar
- 47 IBM. Reference manual for IBM 3350 direct access storage. GA26-1638-2, IBM Corporation, San Jose, Calif., 1977.Google Scholar
- 48 IBM. OS/VS MVS systems programming library: System management facilities (SMF). GC28- 0706-1, IBM Corporation, Poughkeepsie, N. Y., 1977.Google Scholar
- 49 IBM. IBM 3310 direct access storage reference manual. GA26-1660, IBM Corporation, San Jose, Calif., 1979.Google Scholar
- 50 IBM. IBM 3370 direct access storage description. Pub GAZ6-1657-2 IBM Corporation, General Products Division, San Jose, Calif., 1979.Google Scholar
- 51 IBM. Introduction to IBM 3880 storage control, model 11. GA32-0060, IBM Corporation. Tucson, Ariz., 1981.Google Scholar
- 52 IBM. IBM 3880 storage control model 11 description. GA32-0061, IBM Corporation, Tucson, Ariz., 1982.Google Scholar
- 53 IBM. Introduction to IBM 3880 storage control model 13. GA32-0062, IBM Corporation, Tucson, Ariz., 1983.Google Scholar
- 54 IBM. IBM 3880 storage control model 13 description. GA32-0067, IBM Corporation, Tucson, Ariz., 1983.Google Scholar
- 55 IBM. Cache RMF reporter. G320-0362, IBM Corporation, Irving, Tex., 1984.Google Scholar
- 56 KNUTH, D.E. The Art of Computer Programming. Vol. 3, Sorting and Searching Addisonwelsey, Reading, Mass., 1973. Google Scholar
- 57 LOWMAN, R. IBM 3880 model 13 storage subsystem. Rep., IBM Corporation, General Products Division, Tucson, Ariz., 1983.Google Scholar
- 58 LYNCH, W.C. Do disk arms move? Perform. Eval. Rev. 1 {Dec. 1972), 3-16. Google Scholar
- 59 MANKEKAR, P. S. AND MILLI(~AN, C.A. Performance prediction and validation of interacting multiple subsystems in skew-loaded cached DASD Proceedings 1983 CMG International Conference (Washington, D. C., Dec.). 1983, pp. 383-387.Google Scholar
- 60 MATTSON, R. L., GECSEI, J., SLUTZ D. R., AND TRAIGER, I. L, Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.Google Scholar
- 61 MEMOREX. 3770 Disc cache product description manual. Mernorex Corporation, Santa Clara, Calif., 1978.Google Scholar
- 62 ORGANmK, E. The Multics System: An Examination of its Structure, MIT Press, Cambridge, Mass., 1972. Google Scholar
- 63 RITCHIE D. AND THOMPSON, K. The UNIX time sharing system. Commun. CACM 17, 7 (July 1974), 365-375. Google Scholar
- 64 SHERMAN, S., B~,SKV.TT F. AND BROWNE, J.C. Trace driven modeling and analysis of CPU scheduling in a multiprogramming system. Commun. CACM 15, 12 (Dec. 1972}, 1063-1069. Google Scholar
- 65 SMITH A.J. A locality model for disk reference patterns. In Proceedings of the IEEE Computer Society Conference {Feb., San Francisco, Calif.) 1975 IEEE, New York, pp. 109-112.Google Scholar
- 66 SMITH, A.J. Analysis of a locality model for disk reference patterns. In Proceedings of the 2nd Conference on Information Sciences and Systems {Baltimore, MD., Apr.). 1976, pp. 593--601.Google Scholar
- 67 SMITH, A.J. Bibliography on paging and related topics. Oper. Syst. Rev. 12, 4 (Oct. 1978), 39- 56. Google Scholar
- 68 SMITH, A.J. On the effectiveness of buffered and multiple arm disks. In Proceedings of the 5th Computer Architecture Symposium (Palo Alto, Calif., Apr.) 242-248. Google Scholar
- 69 SMITH, A.J. Sequentiality and prefetching in data base systems. ACM Trans. Database Syst. 3, 3 (Sept. 1978), 223-247. Google Scholar
- 70 SMITH, A.J. Sequential program prefetching in memory hierarchies. IEEE Computer II, 12 (Dec. 1978), 7-21.Google Scholar
- 71 Smith, A.J. Input/Output optimization and disk architecture: A survey. Perform. Eval. 1, 2 (198i) 104-117.Google Scholar
- 72 SMITH, A.J. Bibliography on file system and Input/Output optimization and related topics. oper. Syst. Rev. 15, 4 (Oct 1981) 39-54.Google Scholar
- 73 SMITH, A. J. Optimization of I/O systems by cache disk and file migration, A summary. Perform. Eval. 1, 3 (1981), 249-262.Google Scholar
- 74 SMITH, A.J. Cache Memories. ACM Comput. Surv. 14, 3 {Sept., 1982), 473-530. Google Scholar
- 75 Cache disk system. Sperry Univac Product Announcement, for 5057 Cache Disk Processor and 7053 Storage Unit, Sperry Univac, 1981.Google Scholar
- 76 Storage Technology Corporation. Sybercache 8890 intelligent disk controller. Storage Technology Corporation, Louisville, Colo. 1982.Google Scholar
- 77 TOKUNAGA, T., HmAl, Y., AND YAMAMOTO S. Integrated disk cache system with file adaptive control., in Proceedings of the IEEE Computer Society Conference, (Washington, D. C., Sept.) IEEE, New York, 1980, pp. 412-416.Google Scholar
- 78 WELCU, T. Effects of sequential data access on memory hierarchy design. In Proceedings of the IEEE Computer Society Conference, (San Francisco, February). IEEE, New York, 1979 pp. 65- 68.Google Scholar
- 79 WELCH, W.A. Analysis of memory hierarchies for sequential data access. Computer 12, 5 (May 1979), 19-26.Google Scholar
Index Terms
- Disk cache—miss ratio analysis and design considerations
Recommendations
Cache miss behavior: is it √2?
CF '06: Proceedings of the 3rd conference on Computing frontiersIt has long been empirically observed that the cache miss rate decreased as a power law of cache size, where the power was approximately -1/2. In this paper, we examine the dependence of the cache miss rate on cache size both theoretically and through ...
Reviews
Brian T. Bennett
This paper is valuable study of disk caches. The disk cache, a buffer in electronic storage of recently used portions of the disk address space, has the potential to improve system performance significantly. Key factors affecting performance are the miss ratio, the fraction of disk requests not captured by the cache, and the response time for hits and misses. The miss ratio is primarily dependent on the workload and secondarily on the cache design. In this paper, the workload is represented by trace data of disk I/O from three mainframe IBM or IBM-compatible data processing installations. Using the trace data, the miss ratio for disk caches of various sizes and designs are simulated and compared. For example, the miss ratio of a single cache, which can be located in main memory, is compared with that of multiple caches located at the disk control units; it is also compared with the further partition to caches for each disk. The effect on miss ratio of various block sizes (of one, two, four, or eight tracks and one, two, four, or eight cylinders) are compared. The value of caching is evaluated separately by category of file (for example, paging, temporary, and system) and by source (for example, system, interactive user, or batch job). Alternate migration algorithms such as prefetching, purge behind, and whether to cache all devices and time of day effects are evaluated. The optimal static allocation of the most frequently referenced tracks is evaluated and shown inferior to the dynamic LRU allocation. The overall performance impact of disk cache involves not only the miss ratio but the response time for hits and misses. The paper does not attempt to determine this; rather, issues such as access time, bandwidth, and multipathing are discussed. Performance and data integrity issues such as write through versus copy back, consistency over multiple CPUs, and error recovery are also discussed. Ideas such as dynamically turning the cache on and off and technology choices are presented. The issue of who should manage the cache, the CPU, or the storage controller is brought up as are implications to the operating system of disk caches. Commercial disk cache products are described with particular attention to the NEC and IBM designs. The references are very extensive and will be very valuable to other authors. In all, this is a good contribution to the storage hierachy literature. As the author suggests, more comprehensive data is needed to fully explore this subject.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments