Integrated prefetching and caching in single and parallel disk systems

ABSTRACT

We study integrated prefetching and caching in single and parallel disk systems. There exist two very popular approximation algorithms called Aggressive and Conservative for minimizing the total elapsed time in the single disk problem. For D parallel disks, approximation algorithms are known for both the elapsed time and stall time performance measures. In particular, there exists a D-approximation algorithm for the stall time measure that uses D-1 additional memory locations in cache.In the first part of the paper we investigate approximation algorithms for the single disk problem. We give a refined analysis of the Aggressive algorithm, showing that the original analysis was too pessimistic. We prove that our new bound is tight. Additionally we present a new family of prefetching and caching strategies and give algorithms that perform better than Aggressive and Conservative.In the second part of the paper we investigate the problem of minimizing stall time in parallel disk systems. We present a polynomial time algorithm for computing a prefetching/caching schedule whose stall time is bounded by that of an optimal solution. The schedule uses at most 3(D-1) extra memory locations in cache. This is the first polynomial time algorithm for computing schedules with a minimum stall time. Our algorithm is based on the linear programming approach of [1]. However, in order to achieve minimum stall times, we introduce the new concept of synchronized schedules in which fetches on the D disks are performed completely in parallel.

REFERENCES

• 1: Susanne Albers , Naveen Garg , Stefano Leonardi, Minimizing stall time in single and parallel disk systems, Journal of the ACM (JACM), v.47 n.6, p.969-986, Nov. 2000 [doi>10.1145/355541.355542]
• 2: Susanne Albers , Carsten Witt, Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.12-23, August 18-20, 2001
• 3: L.A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78--101, 1966.
• 4: Allan Borodin , Sandy Irani , Prabhakar Raghavan , Baruch Schieber, Competitive paging with locality of reference, Journal of Computer and System Sciences, v.50 n.2, p.244-258, April 1995
• 5: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, A study of integrated prefetching and caching strategies, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.188-197, May 15-19, 1995, Ottawa, Ontario, Canada
• 6: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.311-343, Nov. 1996 [doi>10.1145/235543.235544]
• 7: A. Fiat , M. Mendel, Truly online paging with locality of reference, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.326, October 19-22, 1997
• 8: David R. Fuchs , Donald E. Knuth, Optimal prepaging and font caching, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.62-79, Jan. 1985 [doi>10.1145/2363.2367]
• 9: Alexander Gaysinsky , Alon Itai , Hadas Shachnai, Strongly Competitive Algorithms for Caching with Pipelined Prefetching, Proceedings of the 9th Annual European Symposium on Algorithms, p.49-61, August 28-31, 2001
• 10: David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter, Duality between Prefetching and Queued Writing with Parallel Disks, Proceedings of the 9th Annual European Symposium on Algorithms, p.62-73, August 28-31, 2001
• 11: Mahesh Kallahalla , Peter J. Varman, Optimal prefetching and caching for parallel I/O sytems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.219-228, July 2001, Crete Island, Greece [doi>10.1145/378580.378648]
• 12: Tracy Kimbrel , Anna R. Karlin, Near-Optimal Parallel Prefetching and Caching, SIAM Journal on Computing, v.29 n.4, p.1051-1082, Feb. 2000 to March 2000 [doi>10.1137/S0097539797326976]
• 13: Tracy Kimbrel , Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, Integrated parallel prefetching and caching, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.262-263, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 14: Tracy Kimbrel , Andrew Tomkins , R. Hugo Patterson , Brian Bershad , Pei Cao , Edward W. Felten , Garth A. Gibson , Anna R. Karlin , Kai Li, A trace-driven comparison of algorithms for parallel prefetching and caching, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.19-34, October 29-November 01, 1996, Seattle, Washington, United States
• 15: P. Krishnan , Jeffrey Scott Vitter, Optimal Prediction for Prefetching in the Worst Case, SIAM Journal on Computing, v.27 n.6, p.1617-1636, Dec. 1998 [doi>10.1137/S0097539794261817]
• 16: Mark Palmer , Stanley B. Zdonik, Fido: A Cache That Learns to Fetch, Proceedings of the 17th International Conference on Very Large Data Bases, p.255-264, September 03-06, 1991
• 17: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 18: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 19: Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996 [doi>10.1145/234752.234753]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
caching, magnetic disk systems, prefetching