A Multilevel Cache Management Policy for Performance Improvement in Distributed System

Author Name(s): Manish Motghare, Dr. Preeti Voditel
Author Email: motgharemm@rknec.edu


Caching improves the performance of a system by storing most used recently or frequently accessed data in an upper layer of the multilevel cache hierarchy, results in reducing the delay in I/O system. In parallel and distributed systems, blocks are placed in multilevel cache hierarchy for faster execution of the application. There are many policies; including Hint (information) based which try to improve the gap between various levels of a cache hierarchy in multilevel cache architecture. This information based policy i.e. HINT works on the basis of a number of recent promote and demote operations of cache blocks, i.e. it stores the latest information about the cache block and performs the shifting of cache blocks based on promote and demote operations in various levels of the cache hierarchy. This policy works well for the standalone application, where a number of promote and demote operations occurs rarely. But in a distributed or parallel system, this kind of policy is insufficient because of frequent promote and demote operations. In this paper, we proposed a novel multilevel cache management policy, which keeps a track record of the number of promote and demote operations took place with each cache block for promotion and demotion in a multilevel cache hierarchy. Apart from hint history promote and demote operation, we considered three more parameters for replacement of cache block from upper level to lower level and vice-versa. The proposed policy is able to identify the hot and cold data effectively. The Simulations results show that our proposed policy achieves better performance compared to existing well-known policies like LRU-K, MQ (Multi-Queue) and 2Q.

Keywords Multilevel Cache, Hints, Recency (Most Recently Used), Frequency, Demote, Promote, Cache Performance


Cache memory is the fastest memory and more expensive than the others. It consists of various levels from L1 to Ln depending upon the system architecture. In distributed multilevel cache hierarchy, upper layer serves as a cache for lower layer cache architecture. The caching architecture includes L1, L2 cache and translation schemes. The upper layer cache i.e. L1 is the closest to the processor or sometimes inbuilt with the processor. The L2 cache, generally larger than the primary cache and placed it as a separate chip. In a multilevel cache architecture, cache blocks move from upper level to lower level and vice-versa depending upon the access pattern of the application. In order to manage these data, Hints are used to identify cold and hot data for improving the performance of the system [1][2]. Based on the different information stored by the Hints, they are classified into three following categories [3][4]. • Demotion Hints: The demotion hints are commonly known as demote hints, contains flags which occupies only a few bits. The demote hints shows the information about cache block which is shifted from upper level cache i.e. L1 to lower level L2. The information about this hint is explained in Demote and so on [5][6][7][8]. • Promotion Hints: The promotion hints are also known as promote hints, saves information of those blocks which are updated from lower level cache to upper level. The promote policy was mentioned in the Promote policy [16] and Multiple clients Multiple caches [17]. • Application Hints: These flags are used to store the various information about the active cache blocks related to various applications. Some of them are static as mentioned [18][19] and rest are dynamic which keep track of the cache blocks based on hints history information [20][21].



The proposed policy efficiently performs the cache management by replacing the most accurate cache block with the victim cache block. The decision of which cache blocks to be replaced is taken by considering the frequency, recency and size of the block hence the replacement is more accurate. This policy shows improved performance compared to LRU-K, MQ (Multi-Queue) and 2Q by improving the hit ratio, and reducing the time spent in performing the I/O and overall execution. This policy differs from other multilevel cache management policies as it considers the latest cache block information of all the cache levels while making replacement decision. It also considers the parameters like size and resident time which are most essential for the correct block to be replaced with total cache utilization. LRU-K, 2Q, and MQ (Multi-Queue) do not consider these parameters. The concept of compressed caching is used in this policy which is not used by other multilevel cache management policies. This helps in saving essential cache space. In this policy cache replacement decision is based on the frequency of data block, size, and recency. Use of various parameters in making replacement decision helps in increases the hit ratio of each individual sub-cache partition which in turn improves the overall hit ratio. This leads to effective and efficient utilization of the available cache memory space

571 total views, 1 views today

Download PDF File

About the author: admin