Research On Cache Partition Scheduling Strategy Based On Program Clustering

Chip multiprocessor(CMP)architecture is an important content of high-performance processor research.At the same time,the cache contention phenomenon in CMP architecture is an important factor leading to cache pollution and resource utilization decline.With the increase of the number of on-chip cores,the cache contention phenomenon is becoming increasingly prominent.Cache partition scheduling strategy is one of the main methods to avoid cache contention.Due to the limitation of single cache partition mode and the high time overhead of cache partition algorithm,the traditional cache partition scheduling strategy has the problems of poor scalability and high time overhead.To solve the above problems,this paper proposes a cache partition scheduling strategy based on program clustering(CPBC),and studies the key technologies involved in CPBC,such as the prediction algorithm of cache miss rate curve(MRC).The core idea of CPBC is to group programs to achieve intra-group cache sharing,inter-group cache isolation,and to schedule cache resources flexibly and efficiently.CPBC contains two core algorithms: a program clustering algorithm that considers minimizing the loss of IPC(Instructions Per Cycle),and a cache partitioning algorithm based on the decomposability of program groups.The clustering algorithm calculates the IPC loss to quantify the degree of cache contention,uses the degree of cache contention as the distance between programs to cluster programs,and finally outputs a clustering tree.Each layer in the tree represents a program grouping scheme.The cache partitioning algorithm takes the above clustering tree as input,starts from the root node of the clustering tree,and searches for the optimal cache partitioning plan for each layer of program grouping scheme from top to bottom.The search for each layer can be completed in linear time.Compared with the traditional cache partitioning algorithm,the cache partitioning algorithm searches for the optimal cache partitioning plan with lower time complexity.MRC and hybrid MRC prediction algorithms are two key techniques used to calculate IPC loss in CPBC.CPBC adopts the existing Average Eviction Time(AET)analysis technology to implement the AET-based MRC prediction algorithm and complete the construction of MRC? the traditional hybrid MRC prediction algorithm has low accuracy in scenarios with significant differences in memory access rates and cannot be To meet the requirements of CPBC,a hybrid MRC prediction algorithm considering the difference in memory access rate is proposed.The algorithm calculates the memory access rate of each program and uses it to weight the cache miss rate of each program,so as to obtain a more accurate Hybrid MRC.Experiments show that,compared with the traditional hybrid MRC prediction algorithm,the accuracy of the hybrid MRC prediction algorithm considering the poor memory access rate increases by 6.8% on average,and in extreme cases where the difference in memory access rate is significant,the accuracy rate increases by 18.6%.In order to reflect practical value,CPBC is designed and implemented as a cache partition system,and then the system is inserted into the kernel as a Linux module.Experiments show that using CPBC improves the overall performance by an average of 5.2% compared to when the cache partition scheduling strategy is not used,and increases the performance by an average of 1.3% when using the traditional cache partition scheduling strategy.