DOI: https://doi.org/10.20998/2522-9052.2020.4.08

АЛГОРИТМ ЗАМІЩЕННЯ MFU: АВТОМАТНА МОДЕЛЬ, СИНТЕЗ ТА ОЦІНКА АПАРАТНОЇ РЕАЛІЗАЦІЇ

Vadym Puidenko

Анотація


Політика заміщення алгоритму MFU (Most Frequently Used) поширюється на архітектуру асоціативного кеш буфер сторінкового перетворення. Подія влучання у кеш буфері сторінкового перетворення має спричинити подію фіксації використання відповідного елементу адресованої множини блоку даних. Подія промаху має залучити певну апаратну логіку для прийняття процесором рішення про заміщення достовірного найбільш часто використаного елементу у блоці даних з урахуванням аналізу фіксацій подій звертання до певних елементів при подіях влучань. В статті побудована автоматна модель політики з комбінаторним підходом компаративного аналізу фіксованих подій звертання. Автоматна модель описана відповідними дискретними функціями і структурною блок – схемою алгоритму. Створена й алгоритмізована автоматна модель спричинила синтез апаратури політики заміщення алгоритму MFU для q – спрямованого асоціативного кеш буфера сторінкового перетворення. В основу синтезу був покладений математичний апарат комбінаторного синтезу визначення дозволених умов селекції q - напрямків. Результатом синтезу стали логічні рівняння селекції q - напрямків зі схемотехнічним рішенням апаратури політики заміщення та детальна блок – схема керуючого апаратурою алгоритму. Синтезоване апаратне рішення дало змогу оцінити її складність за Квайном за кількістю полюсів схеми та за загальною кількістю вентилів. Це дозволило провести розрахунки ймовірностей безвідмовної роботи за час напрацювань на відмову до 100000 годин при ймовірності 10-7 відмови одного вентиля. Стаття також містить оцінку швидкодії апаратного рішення як при подіях промахів, такі при подіях влучань.


Ключові слова


асоціативний кеш буфер сторінкового перетворення; політика заміщення; алгоритм MFU; автоматна модель; комбі-наторний синтез; швидкодія; оцінка складності; ймовірність безвідмовної роботи

Повний текст:

PDF

Посилання


Puidenko, V. and Kharchenko, V. (2020), “The Pseudo LRU Hardware Complexity Decreasing for Associative Cache Memory and Translation Look-a-Side Buffer”, CERes Journal, Vol. 6, Is. 1, pp. 142-153.

Sabarinathan, Sayiraman, Senthil Kumar, Dayalan and Shanmugavel Mani, Subbiah (2002), A Framework for MF-LRU (Most Frequently-Least Recently Used) Replacement Policy, available at:

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.618.3125&rep=rep1&type=pdf

Hsin-Chuan, Chen and Jen-Shiun, Chiang (2007), “A high-performance sequential MRU cache using valid-bit assistant search algorithm”, Journal of Circuits, Systems, and Computers, Vol. 16, No. 4, pp. 613–626.

Sudarshan, T.S.B. Rahil Abbas, Mir and Vijayalakshmi, S. (2017), “Highly Efficient LRU Implementations for High Associativity Cache Memory”, Birla Institute of Technology and Science, Pilani, Rajasthan 330331 INDIA.

Safaa S., Omran and Ibrahim A., Amory (2018), “Implementation of LRU Replacement Policy for Reconfigurable Cache Memory Using FPGA”, 2018 International Conference on Advanced Science and Engineering, Kurdistan Region, Iraq, November, 12-14, pp.13-18.

Jaafar, Alghazo, Adil, Akaaboune and Nazeih, Botros (2004), “Cache Replacement Algorithm Records”, 2004 International Workshop on Memory Technology, Design and Testing, Illinois, USA, August, pp.19-24.

Alejandro, Valero, Julio, Sahuquillo, Salvador, Petit, Pedro, Lopez, and Jose, Duato (2019), “MRU-Tour-based Replacement Algorithms for Last-Level Caches”, Conference: 23rd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Vitória (Brazil), DOI: https://doi.org/10.1109/SBAC-PAD.2011.13

Burhan U.l. Islam, Khan, Rashidah, Olanrewaju, Roohie, Naaz Mir, Abdul Raouf, Khan and Yusoff, S.H. (2017), “A Computationally Efficient P-LRU based Optimal Cache Heap Object Replacement Policy”, Int. Journal of Advanced Computer Science and Applications, Vol. 8, No. 1, pp. 128-139, DOI: https://doi.org/10.14569/IJACSA.2017.080118

Swadhesh, Kumar and Singh, P.K. (2016), “An Overview of Modern Cache Memory and Performance Analysis of Replacement Policies”, 2nd IEEE International Conference on Engineering and Technology, India, pp. 4145-4148, DOI: https://doi.org/10.1109/ICETECH.2016.7569243




Copyright (c) 2021 Vadym Puidenko