Study On Cache Partition Optimization Based On Non-stacked Cache Replacement Algorithm

Cache partitioning has become an important means of improving cache performance in shared storage systems today by providing the performance isolation of a private cache and the capacity benefits of a shared cache.The cache miss ratio curve(MRC)describes the relationship between cache miss ratio and cache capacity and is an indispensable and efficient tool for guiding cache partitioning.However,constructing MRCs requires significant storage overhead and time overhead and it is difficult to be constructed efficiently in real-time environments,especially for non-stack cache replacement algorithms that implementing complex but high-performing,which hinder the efficient application of cache partitioning technology in shared storage systems.Miniature Simulations simultaneously provides a small number of sample requests to multiple scaled-down miniature caches to obtain the miss rates of multiple cache size at the same time,and construct the MRC of the non-stacked cache replacement algorithm online.However,Existing work uses uniform fixed-configuration cache shards(miniature caches)to calculate miss ratio,which can leads to the same miss ratio of multiple cache sizes being calculated repeatedly,increasing the consumption of cache space.It also leads to missing miss ratio for some significant cache sizes,constructing MRCs with less precision,and leading to invalid cache partitioning.In response to the above issues,this thesis has done the following work:First,this thesis presents exhaustive research and analysis of existing MRC online construction algorithms and illustrates two significant problems in current MRC online construction algorithms: the excessive cache space consumption problem introduced by repeated calculations of multiple cache sizes with the same miss ratio and the low precision of MRC due to the missing miss ratio of some key cache sizes.Secondly,for the problem of high cache space consumption,we propose a cache shards filtering method based on the locality of application access,named SFshards.SFshards focus on identifying and removing invalid cache shards according to the program's past access behavior at the end of each running epoch,optimizes the initial cache shards configuration for the new epoch,and reduces the consumption of cache space.Thirdly,for the problem of the low precision of MRC,this thesis proposes a dynamic adjustment method for cache shards based on program access diversity(Dashards).Dashards eliminates critical cache size misses by dynamically capturing and adding missing cache shards during the run epoch to adapt to workload changes and ensure MRC construction accuracy.This thesis experiment and evaluate the above strategies with the typical loads of MSR.The results show that SFshards reduces the cache space for MRC construction by about 47% compared to the cache shards' fixed-configuration algorithm.Dashards can construct MRCs with the same accuracy as unfiltered cache shards.At the same time,the combination of SFshards and Dashards improves the cache hit ratio total system of the shared cache system by about 17%.