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

Autor: Puidenko, Vadym
Jazyk: ukrajinština
Rok vydání: 2020
Předmět:
ассоциативный кэш буфер страничного преобразования
productiv-ity
комби-наторный синтез
вероятность безотказной работы
комбі-наторний синтез
complexity assessment
швидкодія
автоматная модель
MFU algorithm
автоматна модель
асоціативний кеш буфер сторінкового перетворення
ймовірність безвідмовної роботи
быстродействие
оценка сложности
оцінка складності
004.254
substitution policy
automaton model
политика замещения
combinatorial synthesis
probability of failure-free operation
політика заміщення
алгоритм MFU
associative translation look-a-side buffer
Zdroj: Сучасні інформаційні системи; Том 4 № 4 (2020): Сучасні інформаційні системи; 57-63
Advanced Information Systems; Vol. 4 No. 4 (2020): Advanced Information Systems; 57-63
Современные информационные системы-Sučasnì ìnformacìjnì sistemi; Том 4 № 4 (2020): Современные информационные системы; 57-63
ISSN: 2522-9052
Popis: 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 MFU algorithm 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.
Политика замещения адаптивного алгоритма MFU (Most Frequently Used) распространяется на архитектуру ассоциативного кэш - буфер страничного преобразования. Событие попадания в кэш - буфере страничного преобразования должно вызвать событие фиксации использования соответствующего элемента адресованного множества блока данных. Событие промаха должно привлечь определенную аппаратную логику для принятия процессором решения о замещении достоверного наиболее часто использованного элемента в блоке данных с учетом анализа фиксаций событий обращения к определенным элементам при событиях попаданий. В статье построена автоматная модель политики с комбинаторным подходом компаративного анализа фиксированных событий обращения. Автоматная модель описана соответствующими дискретными функциями и структурной блок - схемой алгоритма. Созданная и алгоритмизированная автоматная модель вызвала синтез аппаратуры политики замещения алгоритма MFU для q - направленного ассоциативного кэш - буфера страничного преобразования. В основу синтеза был положен математический аппарат комбинаторного синтеза определения разрешенных условий селекции q - направлений. Результатом синтеза стали логические уравнения селекции q - направлений со схемотехническим решением аппаратуры политики замещения и детальная блок - схема управляющего аппаратурой алгоритма. Синтезированное аппаратное решение аппаратуры позволило оценить ее сложность по Квайну: по количеству полюсов схемы и по общему количеству вентилей, что позволило провести расчеты вероятностей безотказной работы за время наработок на отказ до 100000 часов при вероятности 10-7 отказа одного вентиля. Статья также содержит оценку быстродействия аппаратного решения как при событиях промахов, такие при событиях попаданий.
Політика заміщення алгоритму MFU (Most Frequently Used) поширюється на архітектуру асоціативного кеш буфер сторінкового перетворення. Подія влучання у кеш буфері сторінкового перетворення має спричинити подію фіксації використання відповідного елементу адресованої множини блоку даних. Подія промаху має залучити певну апаратну логіку для прийняття процесором рішення про заміщення достовірного найбільш часто використаного елементу у блоці даних з урахуванням аналізу фіксацій подій звертання до певних елементів при подіях влучань. В статті побудована автоматна модель політики з комбінаторним підходом компаративного аналізу фіксованих подій звертання. Автоматна модель описана відповідними дискретними функціями і структурною блок – схемою алгоритму. Створена й алгоритмізована автоматна модель спричинила синтез апаратури політики заміщення алгоритму MFU для q – спрямованого асоціативного кеш буфера сторінкового перетворення. В основу синтезу був покладений математичний апарат комбінаторного синтезу визначення дозволених умов селекції q - напрямків. Результатом синтезу стали логічні рівняння селекції q - напрямків зі схемотехнічним рішенням апаратури політики заміщення та детальна блок – схема керуючого апаратурою алгоритму. Синтезоване апаратне рішення дало змогу оцінити її складність за Квайном за кількістю полюсів схеми та за загальною кількістю вентилів. Це дозволило провести розрахунки ймовірностей безвідмовної роботи за час напрацювань на відмову до 100000 годин при ймовірності 10-7 відмови одного вентиля. Стаття також містить оцінку швидкодії апаратного рішення як при подіях промахів, такі при подіях влучань.
Databáze: OpenAIRE
Externí odkaz: