Proof of Optimality based on Greedy Algorithm for Offline Cache Replacement Algorithm

##plugins.themes.academic_pro.article.sidebar##

Published Oct 31, 2022
https://doi.org/10.47164/ijngc.v13i3.609
Download
Requires Subscription PDF
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 13, Special Issue 3, October 2022

##plugins.themes.academic_pro.article.main##

Swapnita Srivastava
9984631766
P.K. Singh
MMMUT

Abstract

The optimal offline cache replacement algorithm is a MIN algorithm that chooses which data item to remove when a new data item is brought from lower level of cache or main memory. The optimal offline algorithm evicts a cache item whose next request is the furthest away. For a particular program, the performance behavior of the cache memory is determined by memory and block sizes and by the nature of the replacement algorithm. Replacement algorithms, however, deserve analysis because they are based on a variety of assumptions and design considerations. This paper presents a simpler proof based on the greedy algorithm. The paper demonstrates that every ideal solution can be repeatedly transformed into the solution provided by the greedy algorithm without increasing the miss of the optimal solution, hence demonstrating that the greedy solution is providing optimality.
This paper also presents a new replacement algorithm named Greedy Weight-based Cache Replacement Algorithm (GWCRA), on the basis of the Greedy algorithm and it also incorporates the weighted access-based parameter, recency and frequency. The GWCRA achieves an average speedup of 57.29% when compared to LRU and SRRIP which is 55.58% and 55.65%, respectively.

##plugins.themes.academic_pro.article.details##

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite
Srivastava, S., & Singh, P. (2022). Proof of Optimality based on Greedy Algorithm for Offline Cache Replacement Algorithm . International Journal of Next-Generation Computing, 13(3). https://doi.org/10.47164/ijngc.v13i3.609
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. Ahmed, M. W. and Shah, M. A. 2015. Cache memory: An analysis on optimization techniques.
  2. International Journal of Computer and IT 4, 2, 414–418.
  3. Akbari Bengar, D., Ebrahimnejad, A., Motameni, H., and Golsorkhtabaramiri, M. 2020. A page replacement algorithm based on a fuzzy approach to improve cache memory performance. Soft Computing 24, 2, 955–963. DOI: https://doi.org/10.1007/s00500-019-04624-w
  4. Butt, A. R., Gniady, C., and Hu, Y. C. 2007. The performance impact of kernel prefetching
  5. on buffer cache replacement algorithms. IEEE Transactions on Computers 56, 7, 889–908.
  6. Cerrone, C., Cerulli, R., and Golden, B. 2017. Carousel greedy: a generalized greedy algorithm with applications in optimization. Computers & Operations Research 85, 97–112. DOI: https://doi.org/10.1016/j.cor.2017.03.016
  7. Choi, H. and Park, S. 2022. Learning future reference patterns for efficient cache replacement decisions. IEEE Access 10, 25922–25934. DOI: https://doi.org/10.1109/ACCESS.2022.3156692
  8. Deshmukh, S., Thirupathi Rao, K., and Shabaz, M. 2021. Collaborative learning based straggler prevention in large-scale distributed computing framework. Security and communication networks 2021. DOI: https://doi.org/10.1155/2021/8340925
  9. Dou, C., Zheng, L., Wang, W., and Shabaz, M. 2021. Evaluation of urban environmental and economic coordination based on discrete mathematical model. Mathematical Problems in Engineering 2021. DOI: https://doi.org/10.1155/2021/1566538
  10. Gast, N. and Van Houdt, B. 2015. Transient and steady-state regime of a family of list-based DOI: https://doi.org/10.1145/2745844.2745850
  11. cache replacement algorithms. In Proceedings of the 2015 ACM SIGMETRICS International
  12. Conference on Measurement and Modeling of Computer Systems. 123–136.
  13. Hu, Y., Sharma, A., Dhiman, G., and Shabaz, M. 2021. The identification nanoparticle DOI: https://doi.org/10.1155/2021/7548329
  14. sensor using back propagation neural network optimized by genetic algorithm. Journal of
  15. Sensors 2021.
  16. Javaid, Q., Zafar, A., Awais, M., and Shah, M. A. 2017. Cache memory: An analysis on
  17. replacement algorithms and optimization techniques. Mehran University Research Journal
  18. of Engineering & Technology 36, 4, 831–840.
  19. Lee, M.-K., Michaud, P., Sim, J. S., and Nyang, D. 2016. A simple proof of optimality for
  20. the min cache replacement policy. Information Processing Letters 116, 2, 168–170.
  21. Li, K. and Shen, H. 2004. An improved greedydual cache document replacement algorithm. In
  22. IEEE/WIC/ACM International Conference on Web Intelligence (WI’04). IEEE, 457–460.
  23. Ma, T., Tian, W., Wang, B., Guan, D., and Lee, S. Y. 2011. Weather data sharing system:
  24. an agent-based distributed data management. IET software 5, 1, 21–31. DOI: https://doi.org/10.1049/iet-sen.2009.0027
  25. Mattson, R. L., Gecsei, J., Slutz, D. R., and Traiger, I. L. 1970. Evaluation techniques
  26. for storage hierarchies. IBM Systems journal 9, 2, 78–117.
  27. Rizzo, L. and Vicisano, L. 2000. Replacement policies for a proxy cache. IEEE/ACM Transactions DOI: https://doi.org/10.1109/90.842139
  28. on networking 8, 2, 158–170.
  29. Samiee, K. 2009. A replacement algorithm based on weighting and ranking cache objects.
  30. International Journal of Hybrid Information Technology 2, 2, 93–104.
  31. Swain, D., Paikaray, B., and Swain, D. 2011. Awrp: Adaptive weight ranking policy for
  32. improving cache performance. arXiv preprint arXiv:1107.4851 .
  33. Van Roy, B. 2007. A short proof of optimality for the min cache replacement algorithm. DOI: https://doi.org/10.1016/j.ipl.2006.11.009
  34. Information processing letters 102, 2-3, 72–73.
  35. Vogler, W. 2008. Another short proof of optimality for the min cache replacement algorithm. DOI: https://doi.org/10.1016/j.ipl.2007.12.001
  36. Information processing letters 106, 5, 219–220.
  37. Wang, B., Yao, X., Jiang, Y., Sun, C., and Shabaz, M. 2021. Design of a real-time DOI: https://doi.org/10.1155/2021/7212567
  38. monitoring system for smoke and dust in thermal power plants based on improved genetic
  39. algorithm. Journal of Healthcare Engineering 2021.
  40. Wu, X., Xu, H., Zhu, X., and Li, W. 2015. Web cache replacement strategy based on reference DOI: https://doi.org/10.1109/SmartCity.2015.72
  41. degree. In 2015 IEEE International Conference on Smart City/SocialCom/SustainCom
  42. (SmartCity). IEEE, 209–212.