Алгоритм заміщення MFU: автоматна модель, синтез та оцінка апаратної реалізації

Abstract

Політика заміщення алгоритму MFU (Most Frequently Used) поширюється на архітектуру асоціативного кеш буфер сторінкового перетворення. Подія влучання у кеш буфер і сторінкового перетворення має спричинити подію фіксації використання відповідного елементу адресованої множини блоку даних. Подія промаху має залучити певну апаратну логіку для прийняття процесором рішення про заміщення достовірного найбільш часто використаного елементу у блоці даних з урахуванням аналізу фіксацій подій звертання до певних елементів при подіях влучань. В статті побудована автоматна модель політики з комбінаторним підходом компаративного аналізу фіксованих подій звертання. Автоматна модель описана відповідними дискретними функціямиі структурною блок-схемою алгоритму. Створена й алгоритмізована автоматна модель спричинила синтез апаратури політики заміщення алгоритму MFU для q –спрямованого асоціативного кеш буфера сторінкового перетворення. В основу синтезу був покладений математичний апарат комбінаторного синтезу визначення дозволених умов селекції q - напрямків. Результатом синтезу стали логічні рівняння селекції q - напрямків зі схемотехнічним рішенням апаратури політики заміщення та деталь на блок-схему керуючого апаратурою алгоритму. Синтезоване апаратне рішення дало змогу оцінити її скла-ність за Квайном за кількістю полюсів схеми та за загальною кількістю вентилів. Це дозволило провести розрахунки ймовірностей безвідмовної роботи за час напрацювань на відмову до 100000 годин при ймовірності 10-7 відмови одного вентиля. Стаття також містить оцінку швидкодії апаратного рішення як при подіях промахів, так і при подіях влучань.The substitution policy of the MFU (Most Frequently Used) algorithm is extending to the associative translation look-a-side buffer architecture. The hit event in the translation look-a-side buffer should call the event of fixing and using the corresponding element in the multitude of the data unit, which was addressed. The miss event should involve certain hardware logic to allow the processor core to make a decision about of the most frequently used element substitution in the data unit, taking into account the analysis of events fixing on access to certain elements at the hit events.The paper has developed automaton model of the policy with combinatorial approach of comparative analysis for fixed events of access. The automaton model is described by the corresponding discrete functions and the structural block diagram of the algorithm. The automaton model which was created and algorithmized caused the synthesis of the hardware substitution policy of the MFUalgorithm for q-directed associative translation look-a-side buffer. The synthesis was founded on the mathematical apparatus of combinatorial synthesis of determining the enabled conditions for selecting q-directions. The result of the synthesis was logical equations of selection for q-directions with technical scheme solution of the substitution policy hardware and the detailed diagram block of the control algorithm. The synthesized hardware solution made it possible to make an assessment of complexity according to Quine by the number of poles of the circuit and by the total number of gates, that is allow to compute the probability of failure-free operation during the time of failures up to 100,000 hours with a probability of failures in 10-7 for a one gate. The paper also contains an assessment of the productivity for the developed hardware solution as for the miss event, as for the hit event.