{'fraction_non_alphanumeric': 0.028146710257458112, 'fraction_numerical': 0.009807928075194115, 'mean_word_length': 4.463857102986324, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
MAC: a novel systematically multilevel cache replacement policy for PCM memory

The rapid development of multi-core system and increase of data-intensive application in recent years call for larger main memory. Traditional DRAM memory can increase its capacity by reducing the feature size of storage cell. Now further scaling of DRAM faces great challenge, and the frequent refresh operations of DRAM can bring a lot of energy consumption. As an emerging technology, Phase Change Memory (PCM) is promising to be used as main memory. It draws wide attention due to the advantages of low power consumption, high density and nonvolatility, while it incurs finite endurance and relatively long write latency. To handle the problem of write, optimizing the cache replacement policy to protect dirty cache block is an efficient way. In this paper, we construct a systematically multilevel structure, and based on it propose a novel cache replacement policy called MAC. MAC can effectively reduce write traffic to PCM memory with low hardware overhead. We conduct simulation experiments on GEM5 to evaluate the performances of MAC and other related works. The results show that MAC performs best in reducing the amount of writes (averagely 25.12%) without increasing the program execution time.


INTRODUCTION
Traditional computer storage system generally adopts multi-layer structure and uses DRAM as main memory. The development of multi-core system and sharp increase of data-intensive application put forward higher demand to storage system. As for main memory, a normal way to enlarge the memory capacity is integrating more DRAM cells by reducing the feature size of a single cell. Scaling DRAM becomes extremely hard when the size has reached 20 nm [1,2]. In response to the challenge, searching for novel storage materials turns to be a hotspot in recent years.
PCM (phase change memory) is an emerging storage technology which is likely to take this responsibility. As shown in Table 1 [15], PCM can provide up to 4x more density than DRAM and the feature of nonvolatility eliminates the power consumption of refresh operations. PCM can only tolerate 10 8~1 0 9 writes. Main memory in actual system will face frequent writes. If we directly use PCM as main memory without protective measures, it can be disabled in hours. In addition, write to PCM costs much more power and latency than read [3,4,5]. There are many technologies proposed focus on the problem of write. Among them, optimizing the cache replacement policy of last level cache (LLC) is an effective way.
Traditional cache replacement policies are designed for systems using DRAM memory. As DRAM doesn't have the problem of write endurance. These policies give no special considerations to reducing write traffic. The basic idea of cache replacement policies proposed for systems using PCM memory is preferentially keeping dirty blocks in cache under the premise of ensuring high hit ratio, because write operations to memory only occur when dirty blocks are evicted from LLC. A common defect of the existing works is that they don't distinguish the dirty block thoughout the whole lifetime of a cache block. The most obvious part is the demotion process (i.e., changing a long-term idle cache block to a relative low protection priority). Thus although they do give some special considerations to dirty cache blocks, the effects are limited. There are also some specialized page replacement policies proposed for systems using NAND flash [14] disk. Their design principles are instructive to us. As shown in Table I, NAND Flash also has the problem of write endurance. Due to its long latency, NAND Flash is commonly used as disk. We arrange the rest content of the article as follows: Section 2 introduces the related work includes kinds of technologies to solve the problem of high cost of write to PCM. We mainly give brief descriptions of the representatively existing cache replacement policies we select. Section 3 and Section 4 illustrate our systematically multilevel structure and the novel cache replacement policy respectively. Then Section 5 is the experimental methodology, including the results and analysis. We make a conclusion in Section 6 and section 7 is the acknowledgement.

RELATED WORK
There are many works proposed to handle the problem of write operations to PCM. We summarize them into four main categories, the cache replacement policy is one of them. The rest three categories are utilizing extra storages [4,6,7,20,21], omitting the unnecessary writes [6,9,10,17,24] and making the load uniformly distributed [6,24]. The category of cache replacement policy can be almost perfectly incorporated with the technologies of other categories. Below we give a relatively detailed introduction to it.
Among traditional cache replacement policies, LRU [11] is the best representative since it is most commonly used. LRU assumes that a recently used cache block is more likely to be re-referenced. It uses a chain structure to record the order of last references of all the cache blocks. The first-ofchain called MRU is for the most recently used block, and the end-of-chain is called LRU. LRU works well only when the data access pattern has high temporal locality. For example, if there are many single-use data, LRU barely brings a hit. RRIP [12] can effectively handle this situation by giving cache blocks high protection priority only when they are re-referenced. As for systems using PCM memory, recently works include DRRIPW [22], LDF [8], RWA [15] and I-RWA [15]. DRRIPW refers to a series of replacement policies, which are all based on DRRIP [12]. The main modification is that instead of using cache hit ratio as the criterion, DRRIPW uses Set Dueling [16] to select the replacement policy which creates less writes to main memory. LDF makes use of the fine-grained dirtiness management. It divides a cache block (e.g., 4KB) into several subblocks (e.g., 256B), and stores the number of dirty sub-blocks for each block. When it is time to select a victim, it victimizes a block with the least number of dirty sub-blocks among the candidates. LDF is more like an upgrade patch to be integrated into other policies. In order to utilize it, we need other technologies so that only the dirty part of a cache block will be written to PCM. There is a critical point that ignored by both DRRIPW and LDF: the cause of dirty cache blocks, which means the write back operation. RWA notices this factor and distinguishes write operations (write back) from read operations (load and store). RWA is based on SRRIP [12]. It gives dirty cache block the safest position in the beginning by modifying the progress of insertion.
There will be troubles if the re-reference intervals of dirty blocks are too long. To solve this problem, I-RWA narrows the difference between read and write operations in the progress of insertion, and makes up in the process of promotion under hits. CCF-LRU (Cold-Clean-First LRU) [13] is an efficient page replacement policy designed for systems using NAND flash disk. Its main idea is using labels to divide the pages into four protection priorities.

SYSTEMATICALLY MULTILEVEL STRUCTURE
In the existing cache replacement policies for systems using PCM memory, the special treatments of dirty cache blocks don't cover each process of cache. In order to make distinctions between the dirty cache blocks and clean ones throughout their whole lifetime, we construct a systematically multilevel structure as a basis of designing novel cache replacement policy.
This structure considers both aspects of hit ratio and write traffic. In the purpose of reducing write traffic to PCM memory, we need to preferentially protect the dirty cache blocks, while to get a high hit ratio, we also need to keep the blocks which are likely to be re-referenced. We adopt classification to quantify the combination property of each cache block.
As for hit ratio, we divide the blocks into 1 levels. An extreme case is making each block a single level, and in this case 1 reaches its maximum (e.g., The LRU cache replacement policy), so the value range of 1 is as shown in (1). FL (Fresh Level) indicates which one of the 1 levels the block belongs to, and its value range is as shown in (2).

≤ ≤ The Number of Cache Way
(1) For write traffic, the blocks are divided into 2 levels according to how many dirty bytes they have. Theoretically the finest situation is tracking each byte and record it is dirty or not, and 2 reaches its maximum in this case. Its value range is as shown in (3) (B is the total number of bytes in a cache block). DL (Dirty Level) indicates which one of the 2 levels the block belongs to. DL can take values in the range as shown in (4).
The function of 1 , 2 , FL and DL is helping designer gain clarity. Taking both aspects into account, we have levels as in (5), and we add a label FDL (Fresh Dirty Level) to each cache block to indicate which one of the total levels it belongs to. FDL is the combination of FL and DL and has a value range as shown in (6). The specific value of FDL is determined by FL and DL together. There will be a correspondence table of FL, DL and FDL in practice.
The value of FDL stands for the protection priority of the cache block. For convenience, we assume that a larger FDL means a lower protection priority (FL and DL adopt the same assumption). The FDL of a block is changeable. For example, if a block hasn't been referenced for a long time, its FDL should be changed to a larger value, or it has more dirty bytes, then its FDL should be decreased.
It should be noticed that 1 , 2 , , FL, DL and FDL are all integers. Through controlling the value of 1 and 2 , and arranging the correspondence among FL, DL and FDL, we can intentionally change the attentions to each aspect, then get cache replacement policies of various effects.
We divide the cache blocks into different groups by making the cache blocks whose FDLs correspond to a same DL belong to a same group. A group of smaller DL generally correspond to smaller FDLs. If a cache block only changes its FL, its FDL will still in the value range of original group. Through this division, we can make cache blocks of different dirty degrees separately change their protection priorities within their own ranges.
At last, our systematically multilevel structure can be summarized as follows: This structure divides the whole cache blocks into levels considering both aspects of keeping high hit ratio and reducing write traffic to PCM memory. It adds a label called FDL to each cache block to indicate which level of the ones it belongs to. FDL stands for the protection priority of a cache block. Cache blocks of same dirty degree belong to one group. The FDL of a cache block can only vary within the value range of its group unless the dirty degree of the cache block has changed. Though this we can give the dirty cache blocks roundly protections to reduce the write traffic.

NOVEL CACHE REPLACEMENT POLICY
Based on the systematically multilevel structure, we design a novel cache replacement policy for systems using PCM memory. This policy called MAC (Multilayer Ark for Cache) can effectively reduce write traffic to PCM memory with low hardware overhead.
We want MAC can be used in general situation, which means no modification to the process of writing data to PCM memory, so we only distinguish dirty and clean cache blocks. In that case the value of 2 is set as 2. We set the value of 1 as 2 so that the structure can be simple, and add a global LRU structure of all cache blocks as a supplement. According to (3), we have 4 protection priority levels in total.
We consider that the aspect of hit ratio relatively needs more attention. So we make sure that the protection priorities of cache blocks with FLs equal to 1 are still higher than those with FLs equal to 2, as shown in Table 2. The value of DL is 2 means that the cache block is clean, while 1 means dirty. The cache blocks with FLs equal to 1 are referenced more recently than those with FLs equal to 2. We decompose the concrete content of MAC into three parts. The insertion policy is the method handling new cache blocks. The promotion policy presents the corresponding changes when a cache block is re-referenced. The victim policy is the algorithm of selecting a cache block to evict when necessary. The detailed introductions are as follows (read means load/store operation, and write means write back operation): 1) The Insertion Policy: In order to stop single-use data occupying cache, the FLs of all new blocks are set as 2 (the LRU chain can take care of the temporal locality). If a read miss occurs the new block is clean, which means its DL is 2. So as shown in Table 3, it is labelled with FDL equal to 4. If the new block is caused by a write miss, its DL is 1 and its FDL is 3. Under both situations, the new cache block will be inserted at the MRU position of the global LRU chain.
2) The Promotion Policy: When a cache block is re-referenced, its FL will be changed to 1, so FDL will be 1 or 2. If its DL is 1 (FDL is 1 or 3) before the hit, or 2 (FDL is 2 or 4) and under a write hit, in both situations its new FDL is 1, otherwise is 2. To visually view the processes, we show them in Table 3. Besides the change of FDL, the cache block being re-referenced will be promoted to the MRU position of the global LRU chain. We use pseudo-code to explicate the select-victim algorithm in Figure 1.  (7). The result is acceptable in practice.

Experiment Setup
To evaluate the performances of MAC and other representative cache replacement policies, we conduct a series of experiments on GEM5 [23]. GEM5 is a powerful simulation tool encompassing system-level architecture as well as processor microarchitecture. The simulated system has eight cores of timing CPU modal using the X86 instruction set. The L1 cache is private. The L2 cache and PCM are shared by all eight cores. We simulate detailed memory controllers as well. The parameter values are chosen in-line with other researcher's works. Table 4 shows the specific parameters of configurations.
We evaluate the performance of LRU, RRIP, DRRIPW, LDF and RWA for comparison. In order to display obvious differences between these cache replacement policies, we prefer to use test programs which have large amounts of data accesses so that there will be plenty of cache blocks evicted from the L2. The test programs are selected from SPLASH-2 [18] and PASEC [19]. The parameters of these programs are shown in Table 5.

Result and Analysis
We use three performance criteria, which are writes (i.e., the amount of writeback operations to the PCM memory), hit ratio and execution time. Since the original results are not convenient for comparison, we select the system using LRU as baseline and carry out normalization. Actually in our experiments RRIP means SRRIP, and LDF means SRRIP integrated with LDF. The RRPVs of RRIP, DRRIPW, LDF and RWA are all 2 bits. Figure 2 shows the comparison of writes. We can see that RRIP hardly provide obvious reduction (except in fluidanimate), sometimes it even brings more writes than LRU (e.g., in streamcluster and x264). The performance of LDF is close to RRIP, because the amount of writes only depends on how many dirty cache blocks are evicted, the effect of LDF is limited to distinguishing dirty cache blocks and clean ones for RRIP. In most cases, DRRIPW and RWA produce less writes, and by contrast RWA performs better than DRRIPW (except in radix). Compared with the others, MAC presents a better performance in almost each program. This proves that MAC works effectively in various situations. In some programs (i.e., swaptions. fluidanimate and blacksholes) it brings a significant more than 50% reduction. Both RWA and MAC consider the difference between write and read operations, thus they all perform better than DRRIPW. By distinguishing write operation from read operation, RWA and MAC can recognize the dirty cache blocks in the process of inserting new blocks into cache, then take corresponding protective measure. For example, when a write miss occurs, RWA and MAC will insert the new cache block in a relatively higher protection level since it will be dirty after the write, while DRRIPW just treats it in the same way of the clean cache block following a read miss. MAC occurs less writes than RWA because it protects dirty cache blocks in the process of demotion while RWA doesn't. For example, we use numbers from 1 to 4 to denote the protection priority level, and 1 means safest. If a dirty cache block hasn't been re-referenced for a long time, it can be downgraded to level 4 according to RWA, which means most likely to be evicted. While in MAC, dirty cache blocks can only be level 1 or 3. So no matter how long a dirty cache block has been idle, it is totally safe as long as there is one clean cache block in level 4.
We divide the whole lifetime of a cache block in to four process: 1) Insertion: the process of inserting the cache block into cache.
2) Promotion: the process of giving the cache block higher protection priority when it is rereferenced.
3) Demotion: the process of giving the cache block lower protection priority if it is long-term idle.
4) Selection: the process of deciding whether if evict the cache block. Table 7 shows that whether DRRIPW, LDF, RWA and MAC distinguish dirty cache block or not in each process. We can see that only MAC covers all the four processes.
As shown in Figure 3, in most programs the differences of hit ratio between these policies are negligible. The average results are in Table 8 the hit ratio by 1.41% due to the single-use data. LDF also increases by 1.15% since its hit ratio is determined by the cache replacement policy it integrated with. DRRIPW, RWA and MAC respectively decrease the hit ratio by 1%, 0.72% and 0.41% in average. They spare part attentions to reducing the writes, sometimes a dirty cache block with slightly low probability of being rereferenced is more worth preserving than a clean one with high probability of being re-referenced. Considering their contributions of reducing writes, the influences of hit ratio are acceptable. Among them MAC has the lowest degradation of hit ratio.   Figure 4 shows the results of execution time. Except in freqmine and streamcluster, the performances of these policies are almost the same. As shown in Table 9, RRIP, DRRIPW, LDF and MAC shorten the execution time by 0.32%, 0.42%, 0.23% and 0.44% respectively in comparison to LRU. As to PCM, the latency of a write operation may be longer than the total latency of several read operations. Although DRRIPW and MAC have relatively low hit ratios, their execution times are all shorter than LRU due to less write operations.

CONCLUSIONS
In this paper we proposed a systematically multilevel structure for designing cache replacement policy to reduce write traffic to PCM memory, and based on the structure we present an effective cache replacement policy called MAC. MAC can greatly reduce the amount of writes to PCM with low hardware overhead, and hardly brings degradation of program performance.
Through the simulation experiments we proved that MAC is more efficient in the aspect of reducing writes compared with LRU, RRIP, DRRIPW, LDF and RWA. In some programs (e.g., swaptions and fluidanimate) MAC achieves dramatically more than 50% reductions compared with LRU. The average results show that MAC produces the least writes and shortest execution time among these policies.