Susanne Albers
Naveen Garg
Stefano Leonardi
Abstract
We study integrated prefetching and caching problems following the work of Cao et al. [1995] and Kimbrel and Karlin [1996]. Cao et al. and Kimbrel and Karlin gave approximation algorithms for minimizing the total elapsed time in single and parallel disk settings. The total elapsed time is the sum of the processor stall times and the length of the request sequence to be served.
We show that an optimum prefetching/caching schedule for a single disk problem can be computed in polynomial time, thereby settling an open question by Kimbrel and Karlin. For the parallel disk problem, we give an approximation algorithm for minimizing stall time. The solution uses a few extra memory blocks in cache. Stall time is an important and harder to approximate measure for this problem. All of our algorithms are based on a new approach which involves formulating the prefetching/caching problems as linear programs.
- BELADY, L. A. 1966. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5, 78-101.Google Scholar
- BORODIN, A., IRANI, S., RAGHAVAN, P., AND SCHIEBER, B. 1995. Competitive paging with locality of reference. J. Comput. Syst. Sci. 50, 244-258. Google Scholar
- CAO, P., FELTEN, E. W., KARLIN, A. R., AND LI, K. 1995. A study of integrated prefetching and caching strategies. In Proceedings of the Joint ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '95/PERFORMANCE '95) (Ottawa, Ont., Canada, May 15-19). ACM, New York, 188-196. Google Scholar
- CAO, P., FELTEN, E. W., KARLIN, A. R., AND LI, K. 1996. Implementation and performance of integrated application-controlled caching, Prefetching and disk scheduling. ACM Trans. Comput. Syst. (TOCS) 14, 4 (Nov.), 311-343. Google Scholar
- CUREWITZ, K. M., KRISHNAN, P., AND VITTER, J. S. 1993. Practical prefetching via data compres-sion. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (Washington, D.C., May 26-28). ACM, New York, pp. 257-266. Google Scholar
- ELLIS, C. S., AND KOTZ, D. 1989. Prefetching in file systems for MIMD multiprocessors. In Proceedings of the 1989 International Conference on Parallel Processing, pp. I306-314.Google Scholar
- FIAT, A., KARP, R. M., MCGEOCH, L. A., SLEATOR, D. D., AND YOUNG, N. E. 1991. Competitive paging algorithms. J. Algorithms 12, 685-699. Google Scholar
- FIAT, A., AND KARLIN, A. R. 1995. Randomized and multiprocessor paging with locality of reference. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (Las Vegas, Nev., May 29-June 1), ACM, New York, pp. 626-634. Google Scholar
- FIAT, A., AND ROSEN, Z. 1997. Experimental studies of access graph based heuristics. Beating the LRU standard. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, pp. 63-72. Google Scholar
- FUCHS, D. R., AND KNUTH, D. E. 1985. Optimal prepaging and font caching. ACM Trans. Prog. Lang. Syst. 7, 62-79. Google Scholar
- KARLIN, A. R., PHILLIPS, S., AND RAGHAVAN, P. 1992. Markov paging. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 208-217.Google Scholar
- KIMBREL, T. 1997. Parallel prefetching and caching (Ph.D. dissertation). Tech. rep. 97-07-03. Dept. Comput. Sci. Eng., Univ. Washington. Google Scholar
- KIMBREL, T., TOMKINS, A., PATTERSON, R. H., BERSHAD, B., CAO, P., FELTEN, E. W., GIBSON, G. A., KARLIN, A. R., AND LI, K. 1996. A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching. In Proceedings of the ACM SIGOPS/USENIX Association Symposium on Operating System Design and Implementation (OSDI) ACM, New York, 19-34. Google Scholar
- KIMBREL, T., AND KARLIN, A. R. 1996. Near-optimal parallel prefetching and caching. In Proceedings of the 37th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Science Press, Los Alamitos, Calif., pp. 540-549. Google Scholar
- KOTZ, D., AND ELLIS, C. S. 1993. Practical prefetching techniques for multiprocessor file systems. J. Dist. Paral. Datab. 1, 33-51. Google Scholar
- KRISHNAN, P., AND VITTER, J. S. 1994. Optimal prediction for prefetching in the worst case. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (Arlington, Va., Jan. 23-25). ACM, New York, pp. 392-401. Google Scholar
- LEE, K.-K., AND VARMAN, P. 1995. Prefetching and I/O parallelism in multiple disk systems. In Proceedings of the 1995 International Conference on Parallel Processing. CRC Press, Boca Raton, Fla., pp. III160-163.Google Scholar
- PALMER, M., AND ZDONIK, S. B. 1991. Fido: A cache that learns to fetch. In Proceedings of the 17th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, Calif., pp. 255-264. Google Scholar
- PATTERSON, R. H., GIBSON, G. A., GINTING, E., STODOLSKY, D., AND ZELENKA, J. 1995. Informed prefetching and caching. In Proceedings of the 15th Symposium on Operating Systems Principles. (Copper Mountain Resort, Colo., Dec. 3-6). ACM, New York, pp. 79-95. Google Scholar
- SCHRIJVER, A. 1986. Linear and Integer Programming. Wiley, Chichester, England. Google Scholar
- SLEATOR, D. D., AND TARJAN, R. E. 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28, 2 (Feb.), 202-208. Google Scholar
- VITTER, J., AND KRISHNAN, P. 1991. Optimal prefetching via data compression. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 121-130. Google Scholar
Index Terms
- Minimizing stall time in single and parallel disk systems
Recommendations
Integrated prefetching and caching in single and parallel disk systems
We study integrated prefetching and caching in single and parallel disk systems. In the first part of the paper we investigate approximation algorithms for the single disk problem. There exist two very popular approximation algorithms called Aggressive ...
Integrated prefetching and caching in single and parallel disk systems
SPAA '03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architecturesWe 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 ...
Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer ArchitectureOn-die caches are a popular method to help hide the main memory latency. However, it is difficult to build large caches without substantially increasing their access latency, which in turn hurts performance. To overcome this difficulty, on-die caches ...
Comments