×

Enhanced prefetching and caching strategies for single- and multi-disk systems. (English) Zbl 1079.68113

Summary: We study integrated offline caching and prefetching algorithms both in the single- and the multi-disk case. For the problem of minimizing the execution time of a given request sequence, we present simple algorithms. In the single-disk case we present a combinatorial algorithm with an approximation ratio of \(3/2\). An optimal solution can be computed using a linear program but this requires a very large number of variables. Our new result improves on all previous combinatorial approximation algorithms. For the multi-disk case we give combinatorial 2-approximation algorithms. Additionally, we consider this problem in the resource augmentation model where the approximation algorithms may use more cache lines than the optimal solution they are compared to. Here, we give strategies using one additional cache line per disk that outperform the optimum solution without additional cache in the single-disk case and achieve \((1+o(1))\)-approximations in the multi-disk case. In contrast to some of the previous approaches, all the algorithms we present are combinatorial and easy to implement.

MSC:

68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albers, S., Garg, N., Leonardi, S.: Minimizing stall time in single and parallel disk systems. Journal of the ACM 47, 969–986 (2000) · Zbl 1094.68572 · doi:10.1145/355541.355542
[2] Albers, S., Witt, C.: Minimizing stall time in single and parallel disk systems using multicommodity network flows. In: Proc. 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 12–23. Springer LNCS 2129 (2001) · Zbl 1005.68504
[3] Belady, L.A.: A study of replacement algorithms for virtual storage computers. IBM Systems Journal 5, 78–101 (1966) · doi:10.1147/sj.52.0078
[4] El-Yaniv, B.: Online Computation and Competitive Analysis. Cambrige University Press (1998) · Zbl 0931.68015
[5] Cao, P., Felten, E.W., Karlin, A.R., Li, K.: A study of integrated prefetching and caching strategies. In: Proc. ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) pp. 188–196 (1995)
[6] Cao, P., Felten, E.W., Karlin, A.R., Li, K.: Implementation and performance of integrated application-controlled caching, prefetching and disk scheduling. ACM Transaction on Computer Systems (TOCS) 14, 311–343 (1996) · doi:10.1145/235543.235544
[7] Gaysinsky, A., Itai, A., Shachnai, H.: Strongly competitive algorithms for caching with pipelined prefetching. In Proc. of the 9th Annual European Symposium on Algorithms (ESA01), pp. 49–61, Springer LNCS 2161 (2001) · Zbl 1006.68521
[8] Kimbrel, T., Karlin, A.R.: Near-optimal parallel prefetching and caching. SIAM Journal on Computing 29, 1051–1082 (2000) · Zbl 0947.68072 · doi:10.1137/S0097539797326976
[9] Kimbrel, T., Cao, P., Felten, E.W., Karlin, A.R., Li, K.: Integrated parallel prefetching and caching. In: Proc. ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) (1996)
[10] Kimbrel, T., Tomkins, A., Patterson, R.H., Bershad, B., Cao, P., Felten, E.W., Gibson, G.A., Karlin, A.R., Li, K.: A trace-driven comparison of algorithms for parallel prefetching and caching. In: Proc. of the ACM SIGOPS/USENIX Association Symposium on Operating System Design and Implementation (1996)
[11] Tarjan, S.: Amortized efficiency of list update and paging rules. CACM 28, 202–208 (1985)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.