MFU substitution algorithm: automaton model, synthesis and assessment of the hardware implementation

Abstract

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.