10.14489/vkit.2020.05.pp.049-056

DOI: 10.14489/vkit.2020.05.pp.049-056

Вишнеков А. В., Иванова Е. М.
МЕТОДИКА ДИНАМИЧЕСКОГО УПРАВЛЕНИЯ ПРОЦЕССОМ ЗАМЕЩЕНИЯ СТРОК КЭШ-ПАМЯТИ
(с. 49-56)

Аннотация. Исследуются вопросы увеличения производительности вычислительных систем за счет повышения эффективности работы кэш-памяти. Проведен анализ показателей эффективности алгоритмов замещения. Показана необходимость создания средств автоматизированной/автоматической настройки работы кэш-памяти на текущие условия исполнения программного кода, а именно средств динамического управления процессом замещения строк путем замены текущего алгоритма замещения на более эффективный в процессе вычислений. Целью работы является разработка методики управления процессом кэширования на основе определения типа выполняемой программы: циклической, последовательной, локально-точечной, смешанной. Проведен анализ существующих алгоритмов замещения строк кэш-памяти. Предлагается процедура принятия решения по выбору эффективного алгоритма замещения строк на основе методов поддержки принятия решения: методов ранжирования альтернатив, предпочтений и метода анализа иерархий.

Ключевые слова: производительность вычислительной системы; эффективность кэш-памяти; алгоритм замещения строк кэш-памяти; методы поддержки принятия решений.

Vishnekov A. V., Ivanova E. M.
DYNAMIC CONTROL METHODS OF CACHE LINES REPLACEMENT POLICY
(pp. 49-56)

Abstract. The paper investigates the issues of increasing the performance of computing systems by improving the efficiency of cache memory, analyzes the efficiency indicators of replacement algorithms. We show the necessity of creation of automated or automatic means for cache memory tuning in the current conditions of program code execution, namely a dynamic cache replacement algorithms control by replacement of the current replacement algorithm by more effective one in current computation conditions. Methods development for caching policy control based on the program type definition: cyclic, sequential, locally-point, mixed. We suggest the procedure for selecting an effective replacement algorithm by support decision-making methods based on the current statistics of caching parameters. The paper gives the analysis of existing cache replacement algorithms. We propose a decision-making procedure for selecting an effective cache replacement algorithm based on the methods of ranking alternatives, preferences and hierarchy analysis. The critical number of cache hits, the average time of data query execution, the average cache latency are selected as indicators of initiation for the swapping procedure for the current replacement algorithm. The main advantage of the proposed approach is its universality. This approach assumes an adaptive decision-making procedure for the effective replacement algorithm selecting. The procedure allows the criteria variability for evaluating the replacement algorithms, its’ efficiency, and their preference for different types of program code. The dynamic swapping of the replacement algorithm with a more efficient one during the program execution improves the performance of the computer system.

Keywords: Computer performance; Cache efficiency; Cache replacement algorithm; Decision-making support.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

А. В. Вишнеков, Е. М. Иванова (Национальный исследовательский университет «Высшая школа экономики», Москва, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

A. V. Vishnekov, E. M. Ivanova (National Research University Higher School of Economics, Moscow, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Маличенко Д. А. Эвристический алгоритм расчета размеров памяти в многоуровневой системе хранения // Информационно-управляющие системы. 2015. № 5. С. 100 – 105. doi:10.15217/issn1684-8853.2015.5.100
2. Memory Management. URL: https://blog.csdn.net/ gaoxiangnumber1/article/details/52075066 (дата обращения: 17.04.2019).
3. Кошпаев А. А., Васяева Е. С. Анализ алгоритмов замещения данных в кэш-памяти // Перспективы развития науки и образования: тр. VII Междунар. науч.-практ. конф. Йошкар-Ола, 31 июля 2016. С. 70 – 74.
4. Pancham, Chaudhary D., Gupta R. Comparison of Cache Page Replacement Techniques to Enhance Cache Memory Performance // International Journal of Computer Applications. 2014. V. 98, No. 19. P. 27 – 33.
5. Megiddo N., Modha D. S. ARC: A Self-Tuning, Low Overhead Replacement Cache // Proc. FAST’03: 2nd USENIX Conference on File and Storage Technologies. San Francisco, CA, USA, 31 March – 2 April 2003. P. 115 – 130.
6. Improving GPU Cache Hierarchy Performance with a Fetch and Replacement Cache / F. C. Margaix et al. // Proc. 24th International European Conference on Parallel and Distributed Computing, Torino (Italy). August 27 – 31 2018. P. 235 – 249. doi: 10.1007/978-3-319-96983-1_17
7. Bansal S., Modha D. S. CAR: Clock with Adaptive Replacement // Proc. 3rd USENIX Conference on File and Storage Technologies, San Francisco, CA, March 31, 2004. P. 187 – 200.
8. Соколинский Л. Б. Стратегия замещения или как освободить место в буфере: сб. науч.-поп. ст. / под ред. акад. В. П. Скулачева // Российская наука: нам гранты думать и жить помогают. М.: Октопус, 2004. С. 302 – 312.
9. Жуков А. И. Адаптивные алгоритмы кэширования в информационных системах: автореф. … канд. техн. наук. Ростов-на-Дону: ДГТУ, 2012. 21 с. [Научная библиотека диссертаций и авторефератов disserCat https://dlib.rsl.ru/viewer/01005054523#?page=1 (дата обращения: 17.04.2019)].
10. Lazareva S., Kirgizov G., Ragimov R. Smart Face Control: Machine Learning Algorithms for Efficient SSD Caching // Proc. 13th Central & Eastern European Soft ware Engineering Conference in Russia. Saint-Petersburg, October 20 – 22, 2017. Article No. 15. doi: 10.1145/3166094.3166109 [на русском: Умный «фейс-контроль»: алгоритмы машинного обучения для эффективного кэширования данных на SSD https://habr.com/ru/company/raidix/blog/352366/ (дата обращения: 17.04.2019)].
11. Петраков И. Е. Модели и алгоритмы гибридизации стратегий кэширования // Программные продукты, системы и алгоритмы. 2016. № 2. С. 1–2.
12. Мосаб Басам А. Гибридные алгоритмы в системах кэширования объектов // Вестник Донского государствен¬ного технического университета. 2008. № 8(4). C. 147 – 155.
13. Пласковицкий В. А. Применение метрик программного обеспечения для оценки сложности исполняемого кода // Тр. БГТУ. 2013. № 6. С. 145 – 148.
14. Метрики кода и практическая реализация по их сбору и анализу. URL: http://club.cnews.ru/blogs/entry/ metriki_koda_i_prakticheskaya_realizatsiya_po_ih_sboru_i_analizu_chast_1_ (дата обращения: 17.06.2019).
15. Ларичев О. И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах. Изд. 3-е. М.: Логос, 2008. 298 с.
16. Saaty T. L. Decision Making for Leaders: The Analytic Hierarchy Process for Decisions in a Complex World. Pittsburgh: RWS Publications, 1980. 278 p. [Саати Т. Принятие решений. Метод анализа иерархий: пер. с англ. Р. Г. Вачнадзе. М.: Радио и связь, 1993. 278 с.].
17. Eddowes M., Stansfield R. Decision Making Techniques (ACCA). Softcover, Sweet & Maxwell ltd., 1992. 590 p.
18. Zhou Y., Philbin J. F., Li K. The Multi-Queue Replacement Algorithm for Second Level Buffer Caches // Proc. 2001 USENIX Annual Technical Conference. Boston, Massachusetts, USA, 2001. P. 91 – 104.

Eng

1. Malichenko D. A. (2015). Heuristic algorithm for calculating the size of tiers in a hierarchical storage system. Informatsionno-upravlyayushchie sistemy, (5), pp. 100 – 105. [in Russian language] doi:10.15217/issn1684-8853.2015.5.100.
2. Memory management. Available at: https://blog.csdn.net/gaoxiang-umber1/article/details/52075066 (Accessed: 21.02.2020)
3. Koshpaev A. A., Vasyaeva E. S. (2016). Analysis of algorithms for updating the data in the cache memory. Prospects for the development of science and education: proceedings of the VII International Scientific and Practical Conference, pp. 70 – 74. Joshkar-Ola. [in Russian language]
4. Pancham, Chaudhary D., Gupta R. (2014). Comparison of Cache Page Replacement Techniques to Enhance Cache Memory Performance. International Journal of Computer Applications, Vol. 98, 19, pp. 27 – 33.
5. Megiddo N., Modha D. S. (2003). ARC: A Self-Tuning, Low Overhead Replacement Cache. Proceedings FAST’03: 2nd USENIX Conference on File and Storage Technologies, pp. 115 – 130. San Francisco.
6. Margaix F. C., Petit S., Valero A., Sahuquillo J. (2018). Improving GPU Cache Hierarchy Performance with a Fetch and Replacement Cache. Proceedings 24th International European Conference on Parallel and Distributed Computing, pp. 235 – 249. Torino. doi: 10.1007/978-3-319-96983-1_17
7. Bansal S., Modha D. S. (2004). CAR: Clock with Adaptive Replacement. Proceedings 3rd USENIX Conference on File and Storage Technologies, pp. 187 – 200. San Francisco.
8. Skulachev V. P. (Ed.), Sokolinsky L. B. (2004). Substitution strategy or how to free up space in the buffer. Russian science: grants help us to think and live, pp. 302 – 312. Moscow: Oktopus. [in Russian language]
9. Zhukov A. I. (2012). Adaptive Caching Algorithms in Information Systems. Rostov-na-Donu: DGTU. [in Russian language]
10. Lazareva S., Kirgizov G., Ragimov R. (2017). Smart face control: machine learning algorithms for efficient SSD caching. Proceedings 13th Central & Eastern European Soft-ware Engineering Conference in Russia. Saint-Petersburg. doi: 10.1145/3166094.3166109
11. Petrakov I. E. (2016). Models and algorithms of hybridization of caching strategies. Programmnye produkty, sistemy i algoritmy, (2), pp. 1 – 2. [in Russian language]
12. Mosab Bassam A. (2008). Hybrid algorthim in object cache systems. Vestnik Donskogo gosudarstvennogo tekhnicheskogo universiteta, 8(4), pp. 147 – 155. [in Russian language]
13. Plaskovitskiy V. A. (2013). Application of software metrics for evaluation of executable code complexity. Trudy BGTU, (6), pp. 145 – 148. [in Russian language]
14. Code metrics and practical implementation for their collection and analysis. Available at: http://club.cnews.ru/blogs/entry/metriki_koda_i_prakticheskaya_realizatsiya_po_ih_sboru_i_analizu_chast_1_ (Accessed: 21.02.2020) [in Russian language]
15. Larichev O. I. (2008). Theory and decision-making methods, as well as the Chronicle of events in the Magic countries. 3rd ed. Moscow: Logos. [in Russian language]
16. Saaty T. L. (1980). Decision making for leaders: The analytic hierarchy process for decisions in a complex world. Pittsburgh: RWS Publications.
17. Eddowes M., Stansfield R. (1992). Decision Making Techniques (ACCA). Softcover, Sweet & Maxwell ltd.
18. Zhou Y., Philbin J. F., Li K. (2001). The Multi-Queue Replacement Algorithm for Second Level Buffer Caches. Proceedings 2001 USENIX Annual Technical Conference, pp. 91 – 104. Boston, Massachusetts.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2020.05.pp.049-056

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2020.05.pp.049-056

and fill out the form