Research On MRC Approximate Construction Algorithm Based On Reuse Distance Analysis

Based on the local principle of program access,cache is often applied to the computer system design to avoid the huge cost of frequent access to the hard disk.Miss ratio curve(MRC)is often used to analyze the application's real-time cache requirements and achieve dynamic cache allocation,so as to maximize the overall hit rate.Although the existing MRC construction algorithm can achieve high accuracy,the space-time overhead is still large,and it doesn't fit the feasibility of real-time MRC construction.According to the requirements of MRC real-time construction and dynamic cache allocation,this paper analyzes and summarizes the working principle,advantages and disadvantages and optimization space of existing MRC construction algorithms.Based on the research of existing MRC construction algorithms,the spatial sampling and re access ratio based approximate reuse distance analysis(SS-RAR-ARDA)algorithm is proposed,which analyzes the reuse distance of access traffic,combines the strategies of spatial sampling and re-access rate statistics.SS-RAR-ARDA is able to construct the approximate MRC with low space-time cost under the acceptable accuracy loss.Meanwhile,the local accurate construction is applied as the supplement to reduce the error of MRC approximate construction,and the algorithm parameters configuration is provided to obtain the balance between MRC accuracy and algorithm cost according to the actual demand.The cache resource management application based on SS-RAR-ARDA can track the access traffic in real time in the background of the system with less resource occupation,and has the potential of online model analysis.Finally,the accuracy and space-time cost of SS-RAR-ARDA are evaluated and compared generally with the existing MRC construction algorithms.Experimental results show that compared with the precise construction algorithm,the proposed algorithm can reduce the time cost to 5.5 times and the space cost to 245.5 times with a precision loss of less than 1%.