Методи та засоби апаратної реалізації та вибору алгоритмів заміщення даних у кеш-пам'яті мікропроцесорів

Abstract

Дисертація на здобуття наукового ступеня кандидата технічних наук (доктора філософії) за спеціальністю 05.13.05 – Комп'ютерні системи та компоненти (12 – Інформаційні технології). – Національний аерокосмічний університет ім. М. Є. Жуковського "Харківський авіаційний інститут", Національний технічний університет "Харківський політехнічний інститут", Міністерство освіти і науки України, Харків, 2021. Дисертаційна робота присвячена розв'язанню важливої науково-технічної задачі, яка полягає в розробленні методів та засобів апаратних реалізацій та вибору алгоритмів заміщення даних у кеш-пам'яті процесорів. Метою роботи є підвищення швидкодії та надійності засобів апаратної реалізації алгоритмів заміщення процесорів шляхом розроблення і впровадження раціональних логічних структур для керування заміщенням даних з адаптацією і самоконтролем. Об'єктом дослідження є процеси створення і оцінювання апаратної реалізації та вибору алгоритмів заміщення даних у кеш-пам'яті процесорів. Предметом дослідження є моделі, методи і засоби апаратної реалізації та вибору алгоритмів заміщення даних у кеш-пам'яті процесорів. У першому розділі дисертаційної роботи проведений аналіз відомих алгоритмів заміщення та аналіз літературних джерел. Детальний аналіз показує, що дослідження алгоритмів заміщення проводяться переважно на таких двох показниках кешу, як затримка та частота влучань. Кожна стратегія заміни являє собою компроміс між частотою влучань і затримкою. Вимірювання частоти влучань зазвичай виконуються в тестових програмах. Фактичний коефіцієнт влучання сильно варіюється від одного додатка до іншого. До того ж, у роботах провідних авторів не приділена увага дослідженню таких важливих показників, як складність та надійність апаратних рішень алгоритмів заміщення. У першому розділі також проведений аналіз відомих комп’ютерних середовищ моделювання, що дало змогу обґрунтувати вибір комп'ютерного середовища моделювання засобів апаратної реалізації заміщення даних. Обґрунтування вибору комп'ютерного середовища моделювання здійснювалося з урахуванням наступних важливих критеріїв: - можливість моделювання цифрових логічних схем апаратних рішень алгоритмів заміщення з використанням сучасної електронної елементної бази; - можливість створення гнучких тестових програм керування синтезованими апаратними рішеннями алгоритмів заміщення з боку мікроконтролерів; - можливість створення програмно-керованих затримок при управлінні апаратними рішеннями алгоритмів заміщення з боку мікроконтролерів; - можливість створення програмних нештатних ситуацій при управлінні апаратними рішеннями засобів контролю апаратури алгоритмів заміщення з метою визначення їх працездатності. Також перший розділ містить формулювання загальної і часткових задач досліджень з подальшим обґрунтування методики, математичного апарату та етапів досліджень. У другому розділі розв’язано задачу підвищення швидкодії та зменшення складності реалізації алгоритмів заміщення PLRU та MFU кеш-пам’яті процесорів. Відомо, що для роботи алгоритму PLRU потрібно всього декілька бітів на множину елементів даних кешу. Це має надати певні переваги перед певними апаратними рішеннями таких алгоритмів заміщення, як LFU(LRU) та MFU. У дисертаційній роботі для асоціативного кеш-буфера сторінкового перетворення з напрямками q=4 та асоціативної кеш-пам'яті з напрямками q=8 вперше запропонована модель синхронного цифрового автомату політики заміщення даних за алгоритмом PLRU, яка описана відповідною складною перемикальною функцією. Синтез автоматної моделі дозволив отримати мінімальні логічні рівняння апаратного рішення алгоритму заміщення PLRU. Отримане апаратне рішення алгоритму заміщення PLRU дало змогу провести дослідження таких характеристик, як швидкодія, складність та надійність. У дисертаційній роботі вдосконалено апаратне рішення алгоритму заміщення PLRU за рахунок мінімізації логічної схеми PLRU шляхом міжтипового переходу у тригерних структурах. Мінімізація логічної схеми PLRU представлена двома варіантами: варіантом мінімізації на базі оновлення бітів стану за алгоритмом PLRU та варіантом на базі послідовності зміни q – індексу напрямку. Вдосконалення апаратного рішення алгоритму заміщення PLRU за обома варіантами дозволили покращити і відповідні характеристики: швидкодію, складність та надійність апаратури. У дисертаційній роботі синтезована автоматна модель алгоритму заміщення MFU. Синтез автоматної моделі алгоритму дозволив отримати мінімальні логічні рівняння апаратного рішення алгоритму, що дало змогу побудувати відповідне апаратне рішення, дослідити характеристики апаратури та порівняти з дослідженими характеристиками апаратури алгоритму PLRU. У третьому розділі приводиться розроблення та дослідження методу та апаратної реалізації адаптивного алгоритму заміщення. Попередньо був проведений аналіз сумісності алгоритмів заміщення з використанням матриць сумісності. Проведений аналіз дозволив висвітлити визначення сумісних алгоритмів заміщення. Включена до матриці множина алгоритмів дозволила виділити не тільки пари сумісних, але й їх тріади. У розділі також розв’язана задача апаратної реалізації заміщення даних для адаптивного алгоритму LFU–MFU, внаслідок чого вперше запропоновано метод і засоби реалізації адаптивних алгоритмів заміщення даних у кеш-пам'яті процесора, які на відміну від відомих базуються на побудові та аналізі матриць сумісності алгоритмів і надають змогу обирати алгоритм заміщення залежно від результатів динамічного прогнозу галужень програми, що забезпечує підвищення швидкодії процесору. У четвертому розділі удосконалено засоби контролю реалізації алгоритмів заміщення даних у кеш-пам'яті процесора за рахунок використання уніфікованої автоматної моделі, яка враховує кількість напрямків вибору даних при заміщенні, а також оцінок складності базових компонентів засобів контролю, що дозволяє оцінювати приріст достовірності функціонування на одиницю апаратних витрат. Удосконалено метод вибору алгоритмів і засобів реалізації для заміщення даних у кеш-пам’яті процесора шляхом включення до множини алгоритмів алгоритми з контролем і адаптацією, їх упорядкування за показниками складності, швидкодії і достовірності, що дозволяє покращити відповідні показники процесора. Систематизовано і проаналізовано результати впровадження наукових результатів. Ключові слова: асоціативна кеш-пам'ять, асоціативний кеш-буфер TLB, алгоритм заміщення даних PLRU, LRU, LFU, MFU, матриця сумісності, сумісні алгоритм заміщення даних, позитивно сумісні алгоритми заміщення даних, адаптивний алгоритм заміщення даних, синхронний цифровий автомат, швидкодія, складність, надійність, приріст достовірності, коефіцієнт ефективності функціонування, критерій вибору.

Dissertation for the degree candidate of technical sciences (philosophy doctor) in specialty of 05.13.05 – Computer systems and components (12 - Information technologies). – National Aerospace University named after M.E. Zhukovsky «Kharkіv Aviation Institute», National Technical University «Kharkiv Polytechnic Institute», Ministry of Education and Science of Ukraine, Kharkiv, 2021. The dissertation is devoted to the solution of an important scientific and technical problem, which consists in the development of methods and means of hardware implementations and selection of algorithms for data substitution in the cache memory of processors. The purpose of the work is to increase the high-speed performance and reliability of hardware implementation of processor substitution algorithms by developing and implementing rational logical structures to control the substitution of data with adapting and self-control. The research object – the processes of creation and evaluation of hardware implementation and selection of algorithms for data substitution in processor cache. The research subject – models, methods and means of hardware implementation and selection of algorithms for data substitution in the processor cache memory. In the first chapter of the dissertation work, the analysis of known substitution algorithms and the analysis of references were carried out. Detailed analysis shows that the studies of substitution algorithms are carried out predominantly on two cache indicators, such as delay and hit rate. Each substitution strategy there is compromise between hit rate and delay. Hit rate measurements are usually performed in test programs. The actual hit rate varies greatly from one application to another. In addition, the works of leading authors have not pay attention to the study of such important indicators as the complexity and reliability of hardware solutions of substitution algorithms. The first chapter also analyzed the known computer simulation environments, which allowed to justify the choice of a computer simulation environment for hardware implementation of data substitution. Reasonable selection of the computer modeling environment was carried out taking into account the following important criteria: - possibility of modeling digital logic schemes of hardware solutions of substitution algorithms using a modern electronic element base; - possibility to create flexible test control programs of synthesized hardware solutions of substitution algorithms on the part of microcontrollers; - possibility to create software-controlled delays when controlling hardware solutions of substitution algorithms on the part of microcontrollers; - possibility to create software abnormal situations at control of hardware solutions of control hardware of substitution algorithms in order to determine their operability. Also, the first chapter contains the formulation of the general and partial problems of the research to further substantiation of the methodology, mathematical apparatus and stages of research. In the second chapter solved the task of increasing the speed and reducing the complexity of implementing PLRU and MFU substitution algorithms of processor cache. It is known that the PLRU algorithm requires only a few bits per cache multitude data elements. This should provide certain advantages over certain hardware solutions of replacement algorithms such as LFU (LRU) and MFU. In the dissertation work for the associative translation look – a – side buffer with directions q = 4 and for the associative cache memory with directions q = 8 first proposed the synchronous digital automaton model of the data substitution algorithm according to the PLRU policy, which is described by the corresponding complex switching function. The synthesis of the automaton model allowed to obtain the minimal logical equations for the hardware solution of the PLRU substitution algorithm. The resulting hardware solution of the PLRU substitution algorithm allowed to research such characteristics as high-speed performance, complexity and reliability. In the dissertation work, the hardware solution of the PLRU substitution algorithm is improved by minimizing the PLRU logic by inter-type transition in trigger structures. Minimization logic of PLRU is represented by two options: a minimization option based on the update of state bits according to the PLRU algorithm and an option based on the sequence of changes q – the direction index. The improvement of the hardware solution of the PLRU substitution algorithm for the both options have improved the corresponding characteristics such as high-speed performance, complexity and reliability of hardware. In the dissertation, an automaton model of the MFU substitution algorithm was synthesized. The synthesis of the algorithm automaton model allowed to obtain minimal logical equations, which allowed to build an appropriate hardware solution, investigate the characteristics of the equipment and compare with the investigated hardware characteristics of the PLRU algorithm. The third chapter provides the development and study of the method and hardware implementation of the adaptive substitution algorithm. The compatibility analysis of substitution algorithms using compatibility matrices was previously performed. The produced analysis allowed to clarify the definition of compatible substitution algorithms. The set of algorithms, which included in the matrix, have allowed to detect not only pairs of compatible substitution algorithms, but also their triads. In the third chapter, the problem of hardware implementation of data substitution for the LFU – MFU adaptive algorithm is solved, as a result of which for the first time a method and means of implementing adaptive data substitution algorithms in the processor cache are proposed, which, unlike the known ones, are based on the construction and analysis of compatibility matrices of algorithms and allow you to select a substitution algorithm depending on the results of dynamic prediction of the branching program, that increases high-speed performance of the processor. In the fourth chapter presented improvement for the control of data substitution algorithms in the processor cache by using a unified automatic model that takes into account the number of data selection directions when substituting, as well as estimates of the complexity of the basic components of the control tools, which allows you to estimate the increase in the reliability of operation per unit of hardware costs. Also, in the dissertation chapter, the method of selecting algorithms and means of implementation for substitution data in the processor cache is improved by including algorithms with control and adaptation , their ordering by indicators of complexity, high-speed performance and reliability, which improves the corresponding processor indicators.