AUTOMATON MODEL, DEVICE SYNTHESIS AND ADAPTIVE SUBSTITUTION ALGORITHM FOR CACHE MEMORY

Вадим Олексійович Пуйденко

Abstract


The probability indicators of the hits or misses events have conditioned the application of the certain substitution policies in the associative cache and the associative translation look-a-side buffer. The implementation of combined substitution policies can improve cache memory and cache buffer performance in general by the interoperability of algorithms with unidirectional or multidirectional substitution policies with the ability to switch from one policy to another. Adaptation of substitution algorithms is based on the compatibility of algorithms according to several characteristics, such as substitution policy, productivity, and implementation complexity. All listed characteristics are summarized in the corresponding table and they are allowed to create the construction for the so-called compatibility matrix, which allows observing not only pairs of compatible algorithms, but also their triads. The substitution policy of the adaptive algorithms extends as to the associative cache memory as to the associative translation look-a-side buffer of the processor core. In the paper, the automaton model of an adaptive algorithm was built and was created by a pair of compatible algorithms. On the one side, the substitution policy algorithm policy should rely on finding and replacing the least recently used or least frequently used element of the addressed set of the data unit. On the other side, this policy may occur in searching and replacing the most recently used or most frequently used element in the addressed set of a data unit. The automaton model is described by the corresponding discrete functions and structural block diagrams of algorithms. The automaton model was created and algorithmized and was the reason for the synthesis of adaptive algorithm hardware for q – directional associative cache memory and associative translation look-a-side buffer. The synthesis was based on the mathematical apparatus of combinatorial synthesis for determining the enabling conditions for selecting q - directions. The result of the synthesis was the logic model of a selection of q – directions according to an adaptive algorithm with the corresponding hardware solution.

Keywords


substitution policy, adaptive algorithm, PLRU (Pseudo Least Recently Used), LRU (Least Recently Used), MRU (Most Recently Used), LFU (Least Frequently Used), MFU (Most Frequently Used), automaton model, combinatorial synthesis, associative cache memory, a

References


Puydenko, V. O. Alhorytm zamishchennya MFU: avtomatna model', syntez ta otsinka aparatnoyi realizatsiyi [MFU substitution algorithm: automatic model, synthesis and evaluation of hardware implementation]. Suchasni informatsiyni systemy – Advanced information systems, vol. 4, no. 4, 2020, pp. 57-63. DOI: 10.20998/2522-9052.2020.4.08.

Puydenko, V. O., Kharchenko, V. S. Minimizatsiya lohichnoyi skhemy dlya realizatsiyi pseudo – LRU shlyakhom mizh typovoho perekhodu u tryhernykh strukturakh [The minimizating of logical scheme for implementation of pseudo lru by inter-type transition in trigger structures]. Radioelektronni i komp'uterni sistemi – Radioelectronic and computer systems, 2020, no. 2, pp. 33-47. DOI: 10.32620/reks.2020.2.03.

Sudarshan, T. S. B., Mir, Rahil Abbas.,Vijayalakshmi, S. Highly Efficient LRU Implementations for High Associativity Cache Memory. Birla Institute of Technology and Science, Pilani, Rajasthan 330331 INDIA, 2017. Available at: http://www.semanticscholar.org/paper/Highly-efficient-LRU-implementations-for-high-cache-Sudarshan-Mir/e9a6b5b9cb70fc3782b2709ebcf1414051ed6e4c. (Accessed 10.05.2020).

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

Khan, Burhan Ul Islam., Olanrewaju, Rashidah F., Mir, Roohie Naaz., Khan, Abdul Raouf., Yusoff, S. H. A Computationally Efficient P-LRU based Optimal Cache Heap Object Replacement Policy. International Journal of Advanced Computer Science and Applications, vol. 8, no. 1, 2017, pp. 128-138.

Kumar, Swadhesh., Singh, P. K. An Overview of Modern Cache Memory and Performance Analysis of Replacement Policies. 2nd IEEE International Conference on Engineering and Technology, India, 2016, pp. 4145-4148.

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

Reineke, J., Grund, D., Berg, C., Wilhelm, R. Timing predictability of cache replacement policies. Real-Time Syst., vol. 37, no. 2, 2007, pp. 99-122.




DOI: https://doi.org/10.32620/reks.2020.4.06

Refbacks

  • There are currently no refbacks.