CN111290706A - Double-layer read-write wear balancing method based on bloom filter - Google Patents

Abstract

Translated fromChinese

一种基于布隆过滤器的双层读写磨损均衡方法，本发明涉及混合内存存储器控制器磨损均衡方法。本发明的目的是为了解决现有表格磨损均衡算法空间开销大的问题。本发明将计数布隆过滤器应用在存储器控制器的设计中，通过动态的更改读写布隆过滤器的阈值来代表访存程序的时间局部性。同时，通过对读写布隆过滤器中的数值与动态阈值的比较来判断页面的读写热度。使混合内存的高度写磨损页面与轻度写磨损页面就行交换，达到混合内存整体磨损均衡的效果，从而提高混合内存系统的整体寿命。本发明用于混合内存的磨损均衡控制领域。

A double-layer read-write wear leveling method based on Bloom filter relates to a wear leveling method for a hybrid memory storage controller. The purpose of the present invention is to solve the problem of large space overhead in the existing table wear leveling algorithm. The invention applies the counting bloom filter in the design of the memory controller, and represents the time locality of the memory access program by dynamically changing the threshold value of the read-write bloom filter. At the same time, the read/write heat of the page is judged by comparing the value in the read/write bloom filter with the dynamic threshold. The pages with high write wear and the pages with light write wear of the hybrid memory can be exchanged, so as to achieve the effect of the overall wear balance of the hybrid memory, thereby improving the overall life of the hybrid memory system. The invention is used in the field of wear leveling control of hybrid memory.

Description

Translated fromChinese

一种基于布隆过滤器的双层读写磨损均衡方法A double-layer read-write wear leveling method based on Bloom filter

技术领域technical field

本发明涉及混合内存存储器控制器磨损均衡方法。The present invention relates to a wear leveling method for a hybrid memory memory controller.

背景技术Background technique

为了满足现代嵌入式系统对存储器内存的大容量和低功耗的要求，DRAM与非易失性存储器构成的混合型内存得到了广泛的应用。在非易失存储器中相变存储器PCM(PhaseChange Memory)已经成为学术界和工业界的新宠。相比于传统DRAM，PCM持久性内存具有静态功率低，存储密度高，按字节寻址的能力和数据持久力高等优点，这些优点为存储器的高效性能带来了巨大的挑战和机遇。尽管PCM优点众多，但其较高的写入延时和较低的写耐受力限制了PCM的使用寿命。在PCM和DRAM的混合主存储器设计中，如何提高平行混合架构中PCM的使用寿命成为目前的研究热点。磨损均衡算法是被广泛采用的用于提高混合存储器耐受性的一种方法。磨损均衡技术把上层不均衡的写访问通过重映射后均衡地写回到底层物理单元上，避免一些内存行因为写次数过高而提前磨穿，从而提升混合内存系统的寿命。磨损均衡需要解决恶意攻击和正常负载下混合内存系统的寿命问题。对于混合存储器，目前的磨损均衡算法分为基于表格的磨损均衡算法和基于代数的磨损均衡算法。基于表格的磨损均衡算法使用地址映射表记录逻辑地址与物理地址之间的对应关系，周期性的交换写次数较高和较低的区域，从而达到磨损均衡的目的，但是表格磨损均衡算法需要较高的时间和空间开销。代数磨损均衡算法使用代数函数将逻辑地址随机的重映射到物理空间，空间开销很低，代数磨损均衡算法可以在内存器控制器或芯片内部执行。但代数磨损均衡算法普遍面临着磨损预测不准确的问题，该类算法只能全局的轮转交换页面，并未有针对性的对某些写热度很高的页面进行特殊的磨损均衡处理。因此，提出一种低开销、高预测率的混合内存磨损均衡算法是非常有必要的。In order to meet the requirements of large capacity and low power consumption of memory in modern embedded systems, the hybrid memory composed of DRAM and non-volatile memory has been widely used. In non-volatile memory, phase change memory PCM (PhaseChange Memory) has become a new favorite in academia and industry. Compared with traditional DRAM, PCM persistent memory has the advantages of low static power, high storage density, byte-addressable ability and high data persistence, which bring great challenges and opportunities for the efficient performance of memory. Although PCM has many advantages, its high write latency and low write endurance limit the service life of PCM. In the hybrid main memory design of PCM and DRAM, how to improve the service life of PCM in parallel hybrid architecture has become a current research focus. Wear-leveling algorithms are a widely adopted method for improving the endurance of hybrid memories. The wear leveling technology writes the unbalanced write access of the upper layer back to the underlying physical unit through remapping, so as to prevent some memory lines from being worn out in advance due to the high number of writes, thereby improving the lifespan of the hybrid memory system. Wear leveling needs to address both malicious attacks and the longevity of mixed memory systems under normal load. For hybrid memory, current wear leveling algorithms are divided into table-based wear leveling algorithms and algebra-based wear leveling algorithms. The table-based wear leveling algorithm uses the address mapping table to record the correspondence between logical addresses and physical addresses, and periodically swaps regions with higher and lower writes to achieve the purpose of wear leveling. However, the table wear leveling algorithm requires more High time and space overhead. The algebraic wear leveling algorithm uses an algebraic function to randomly remap logical addresses to physical space. The space overhead is very low. The algebraic wear leveling algorithm can be executed in the memory controller or inside the chip. However, the algebraic wear leveling algorithm generally faces the problem of inaccurate wear prediction. This type of algorithm can only globally rotate pages, and does not perform special wear leveling processing on some pages with high write heat. Therefore, it is very necessary to propose a hybrid memory wear leveling algorithm with low overhead and high prediction rate.

发明内容SUMMARY OF THE INVENTION

本发明的目的是为了解决现有表格磨损均衡算法时间和空间开销大的问题，而提出一种基于布隆过滤器的双层读写磨损均衡方法。The purpose of the present invention is to propose a double-layer read-write wear-leveling method based on Bloom filter in order to solve the problem of high time and space overhead of the existing table wear-leveling algorithm.

一种基于布隆过滤器的双层读写磨损均衡方法具体过程为：The specific process of a double-layer read-write wear leveling method based on Bloom filter is as follows:

步骤1、当有操作对页面P访存时，request_counter加1；Step 1. When there is an operation to fetch the page P, the request_counter is incremented by 1;

如果当前的操作是写操作，则通过两个哈希函数，对write_counting_bloom_filter相应位置加1，进入步骤2；If the current operation is a write operation, add 1 to the corresponding position of write_counting_bloom_filter through two hash functions, and enter step 2;

如果当前的操作是读操作，则通过两个哈希函数，对read_counting_bloom_filter相应位置加1，进入步骤3；If the current operation is a read operation, add 1 to the corresponding position of read_counting_bloom_filter through two hash functions, and enter step 3;

所述request_counter为访存请求计数器；The request_counter is a memory access request counter;

所述write_counting_bloom_filter为写布隆过滤器，read_counting_bloom_filter为读布隆过滤器；The write_counting_bloom_filter is a write bloom filter, and read_counting_bloom_filter is a read bloom filter;

在时间T内，将当前写操作使得两个哈希函数对write_counting_bloom_filter相应位置write_counting_bloom_filter[i]和write_counting_bloom_filter[j]的值均大于PCM_write_threhold的页面认为是写磨损较多页面；In the time T, the current write operation makes the two hash functions consider the page whose values of write_counting_bloom_filter[i] and write_counting_bloom_filter[j] in the corresponding positions of write_counting_bloom_filter are greater than PCM_write_threhold to be the page with more wear and tear;

在时间T内，将当前读操作使得两个哈希函数对read_counting_bloom_filter相应位置read_counting_bloom_filter[i]和read_counting_bloom_filter[j]的值均大于PCM_read_threhold，并且read_counting_bloom_filter[i]>write_counting_bloom_filter[i]、read_counting_bloom_filter[j]>write_counting_bloom_filter[j]的页面认为是写磨损较少的页面，是读热页面；During time T, the current read operation is made so that the values of read_counting_bloom_filter[i] and read_counting_bloom_filter[j] at the corresponding positions of read_counting_bloom_filter by the two hash functions are both greater than PCM_read_threhold, and read_counting_bloom_filter[i]>write_counting_bloom_filter[i], read_counting_bloom_filter[j]> The page of write_counting_bloom_filter[j] is considered to be a page with less write wear and is a hot page for reading;

步骤2、如果当前写操作使得两个哈希函数对write_counting_bloom_filter相应位置write_counting_bloom_filter[i]和write_counting_bloom_filter[j]的值均大于PCM_write_threhold，那么将写磨损较多的页面与写磨损较少的页面进行交换，进入步骤4；否则，进入步骤5；Step 2. If the current write operation causes the values of the two hash functions to write_counting_bloom_filter[i] and write_counting_bloom_filter[j] in the corresponding positions of write_counting_bloom_filter to be greater than PCM_write_threhold, then the page with more write wear is exchanged with the page with less write wear, Go to step 4; otherwise, go tostep 5;

所述PCM_write_threhold为相变存储器写阈值；The PCM_write_threhold is the phase change memory write threshold;

步骤3、如果当前读操作使得两个哈希函数对read_counting_bloom_filter相应位置read_counting_bloom_filter[i]和read_counting_bloom_filter[j]的值均大于PCM_read_threhold，并且read_counting_bloom_filter[i]>write_counting_bloom_filter[i]、read_counting_bloom_filter[j]>write_counting_bloom_filter[j]，则将当前读操作页面放入读热页面候选列表中，进入步骤6；否则，直接进入步骤6；Step 3. If the current read operation makes the values of read_counting_bloom_filter[i] and read_counting_bloom_filter[j] in the corresponding positions of read_counting_bloom_filter by the two hash functions are greater than PCM_read_threhold, and read_counting_bloom_filter[i]>write_counting_bloom_filter[i], read_counting_bloom_filter[j]>write_counting_bloom_filter[ j], then put the current read operation page into the read hot page candidate list, and enter step 6; otherwise, directly enter step 6;

所述PCM_read_threhold为相变存储器读阈值；The PCM_read_threhold is the read threshold of the phase change memory;

步骤4、将读热页面候选列表中表头存放的页面K取出，将页面P与页面K进行位置交换，进入步骤5；Step 4. Take out the page K stored in the header of the read hot page candidate list, exchange the position of page P and page K, and go tostep 5;

步骤5、如果PCM_write_threhold>HRWTH，则PCM_write_threhold减半，write_counting_bloom_filter中所有记录值减半，进入步骤7；否则直接进入步骤7；Step 5. If PCM_write_threhold>HRWTH, then PCM_write_threhold is halved, and all record values in write_counting_bloom_filter are halved, and go to step 7; otherwise, go directly to step 7;

所述，HRWTH为写操作最大阈值；As mentioned above, HRWTH is the maximum threshold for write operations;

步骤6、如果PCM_read_threhold>HRRTH，则PCM_read_threhold减半，read_counting_bloom_filter中所有记录值减半，进入步骤8；否则直接进入步骤8；Step 6. If PCM_read_threhold>HRRTH, then PCM_read_threhold is halved, and all the recorded values in read_counting_bloom_filter are halved, and go toStep 8; otherwise, go directly toStep 8;

所述，HRRTH为读操作最大阈值；Said, HRRTH is the maximum threshold of the read operation;

步骤7、如果request_counter是Tupwth的整数倍时，PCM_write_threhold＝PCM_write_threhold+addwrite；否则结束程序；Step 7. If request_counter is an integer multiple of Tupwth, PCM_write_threhold=PCM_write_threhold+addwrite; otherwise, end the program;

所述，Tupwth为写阈值更新周期；Said, Tupwth is the write threshold update period;

addwrite为写阈值增加跨度；addwrite increases the span for the write threshold;

步骤8、如果request_counter是Tuprth的整数倍时，PCM_read_threhold＝PCM_read_threhold+addread；否则结束程序；Step 8. If request_counter is an integer multiple of Tuprth, PCM_read_threhold=PCM_read_threhold+addread; otherwise, end the program;

所述，Tuprth为读阈值更新周期；As mentioned, Tuprth is the read threshold update period;

addread为读阈值增加跨度。addread adds the stride to the read threshold.

本发明的有益效果为：The beneficial effects of the present invention are:

本发明拟提高混合系统内存使用寿命，对混合内存的存储器控制器进行设计，提出了一种基于布隆过滤器的双层读写磨损均衡方法(Double Layer Bloom Filter，DLBF)，在较小的硬件开销下，实现PCM芯片内部粒度适中的磨损均衡，实现了在较小的空间开销小达到磨损均衡的目的。The invention intends to improve the service life of the memory of the hybrid system, designs the memory controller of the hybrid memory, and proposes a double-layer read-write wear leveling method (Double Layer Bloom Filter, DLBF) based on the Bloom filter. Under the hardware overhead, the wear leveling with moderate granularity inside the PCM chip is realized, and the purpose of achieving wear leveling with a small space overhead is achieved.

实验结果表明，相较于无磨损均衡算法、random算法，Bloom Filter算法，本发明将混合内存系统的使用寿命分别提升至这些算法的2.34倍、1.22倍、1.02倍。同时，本发明使得写分布的平均方差分别降低至无磨损均衡算法、random算法，Bloom Filter算法的1.04％、66.27％、96.97％。The experimental results show that, compared with the non-wear leveling algorithm, the random algorithm, and the Bloom Filter algorithm, the present invention increases the service life of the hybrid memory system to 2.34 times, 1.22 times, and 1.02 times, respectively, of these algorithms. At the same time, the present invention reduces the average variance of the write distribution to 1.04%, 66.27%, and 96.97% of the wear-free leveling algorithm, the random algorithm, and the Bloom Filter algorithm, respectively.

附图说明Description of drawings

图1为在无磨损均衡算法中dijkstra负载写操作分布情况图；Figure 1 shows the distribution of dijkstra load write operations in the wear-free leveling algorithm;

图2为在无磨损均衡算法中jpeg_dec负载写操作分布情况图；Figure 2 is a diagram of the distribution of jpeg_dec load write operations in the wear-free leveling algorithm;

图3为在无磨损均衡算法中mpeg_dec负载写操作分布情况图；Figure 3 is a diagram of the distribution of mpeg_dec load write operations in the wear-free leveling algorithm;

图4为在DLBF磨损均衡算法中dijkstra负载写操作分布情况图；Figure 4 is a diagram of the distribution of dijkstra load write operations in the DLBF wear leveling algorithm;

图5为在DLBF磨损均衡算法中jpeg_dec负载写操作分布情况图；Figure 5 is a diagram showing the distribution of jpeg_dec load write operations in the DLBF wear leveling algorithm;

图6为在DLBF磨损均衡算法中mpeg_dec负载写操作分布情况图；Figure 6 is a diagram showing the distribution of mpeg_dec load write operations in the DLBF wear leveling algorithm;

图7为在不同算法中归一化的混合内存系统使用寿命情况图，Without WL为无磨损均衡算法，random为随机算法，Bloom Filter为布隆过滤器算法，DLBF为双层布隆过滤器算法；Figure 7 shows the normalized service life of the hybrid memory system in different algorithms. Without WL is a wear-free leveling algorithm, random is a random algorithm, Bloom Filter is a Bloom filter algorithm, and DLBF is a double-layer Bloom filter algorithm. ;

图8为归一化的写分布平均方差情况图。FIG. 8 is a graph of the normalized mean variance of the write distribution.

具体实施方式Detailed ways

具体实施方式一：本实施方式一种基于布隆过滤器的双层读写磨损均衡方法具体过程为：Embodiment 1: The specific process of a double-layer read-write wear leveling method based on Bloom filter in this embodiment is:

步骤1、当有操作对页面P访存时，request_counter加1；Step 1. When there is an operation to fetch the page P, the request_counter is incremented by 1;

如果当前的操作是写操作，则通过两个哈希函数，对write_counting_bloom_filter相应位置(操作对应的地址带入哈希函数，因为是两个哈希函数，所以会得出两个值i,j。即确定了布隆过滤器的相应位置)加1，进入步骤2；If the current operation is a write operation, the corresponding position of write_counting_bloom_filter (the address corresponding to the operation is brought into the hash function through two hash functions, because there are two hash functions, two values i, j will be obtained. That is, the corresponding position of the Bloom filter is determined) plus 1, and enter step 2;

如果当前的操作是读操作，则通过两个哈希函数，对read_counting_bloom_filter相应位置加1，进入步骤3；If the current operation is a read operation, add 1 to the corresponding position of read_counting_bloom_filter through two hash functions, and enter step 3;

所述request_counter为访存请求计数器；The request_counter is a memory access request counter;

所述write_counting_bloom_filter为写布隆过滤器，read_counting_bloom_filter为读布隆过滤器；The write_counting_bloom_filter is a write bloom filter, and read_counting_bloom_filter is a read bloom filter;

在时间T内，将当前写操作使得两个哈希函数对write_counting_bloom_filter相应位置write_counting_bloom_filter[i]和write_counting_bloom_filter[j]的值均大于PCM_write_threhold的页面认为是写磨损较多页面；In the time T, the current write operation makes the two hash functions consider the page whose values of write_counting_bloom_filter[i] and write_counting_bloom_filter[j] in the corresponding positions of write_counting_bloom_filter are greater than PCM_write_threhold to be the page with more wear and tear;

在时间T内，将当前读操作使得两个哈希函数对read_counting_bloom_filter相应位置read_counting_bloom_filter[i]和read_counting_bloom_filter[j]的值均大于PCM_read_threhold，并且read_counting_bloom_filter[i]>write_counting_bloom_filter[i]、read_counting_bloom_filter[j]>write_counting_bloom_filter[j]的页面认为是写磨损较少的页面，是读热页面；During time T, the current read operation is made so that the values of read_counting_bloom_filter[i] and read_counting_bloom_filter[j] at the corresponding positions of read_counting_bloom_filter by the two hash functions are both greater than PCM_read_threhold, and read_counting_bloom_filter[i]>write_counting_bloom_filter[i], read_counting_bloom_filter[j]> The page of write_counting_bloom_filter[j] is considered to be a page with less write wear and is a hot page for reading;

步骤2、如果当前写操作使得两个哈希函数对write_counting_bloom_filter相应位置write_counting_bloom_filter[i]和write_counting_bloom_filter[j]的值均大于PCM_write_threhold，那么将写磨损较多的页面与写磨损较少的页面进行交换，进入步骤4；否则(当前的页面并不是写磨损多的页面)，进入步骤5；Step 2. If the current write operation causes the values of the two hash functions to write_counting_bloom_filter[i] and write_counting_bloom_filter[j] in the corresponding positions of write_counting_bloom_filter to be greater than PCM_write_threhold, then the page with more write wear is exchanged with the page with less write wear, Go to step 4; otherwise (the current page is not a page with more wear and tear), go tostep 5;

所述PCM_write_threhold为相变存储器写阈值；The PCM_write_threhold is the phase change memory write threshold;

步骤3、如果当前读操作使得两个哈希函数对read_counting_bloom_filter相应位置read_counting_bloom_filter[i]和read_counting_bloom_filter[j]的值均大于PCM_read_threhold，并且read_counting_bloom_filter[i]>write_counting_bloom_filter[i]、read_counting_bloom_filter[j]>write_counting_bloom_filter[j]，则将当前读操作页面放入读热页面候选列表中，进入步骤6；否则，直接进入步骤6；Step 3. If the current read operation makes the values of read_counting_bloom_filter[i] and read_counting_bloom_filter[j] in the corresponding positions of read_counting_bloom_filter by the two hash functions are greater than PCM_read_threhold, and read_counting_bloom_filter[i]>write_counting_bloom_filter[i], read_counting_bloom_filter[j]>write_counting_bloom_filter[ j], then put the current read operation page into the read hot page candidate list, and enter step 6; otherwise, directly enter step 6;

所述PCM_read_threhold为相变存储器读阈值；The PCM_read_threhold is the read threshold of the phase change memory;

步骤4、将读热页面候选列表中表头存放的页面K取出，将页面P与页面K进行位置交换，进入步骤5；Step 4. Take out the page K stored in the header of the read hot page candidate list, exchange the position of page P and page K, and go tostep 5;

步骤5、如果PCM_write_threhold>HRWTH，则PCM_write_threhold减半，write_counting_bloom_filter中所有记录值减半，进入步骤7；否则直接进入步骤7；Step 5. If PCM_write_threhold>HRWTH, then PCM_write_threhold is halved, and all record values in write_counting_bloom_filter are halved, and go to step 7; otherwise, go directly to step 7;

所述，HRWTH为写操作最大阈值；As mentioned above, HRWTH is the maximum threshold for write operations;

步骤6、如果PCM_read_threhold>HRRTH，则PCM_read_threhold减半，read_counting_bloom_filter中所有记录值减半，进入步骤8；否则直接进入步骤8；Step 6. If PCM_read_threhold>HRRTH, then PCM_read_threhold is halved, and all the recorded values in read_counting_bloom_filter are halved, and go toStep 8; otherwise, go directly toStep 8;

所述，HRRTH为读操作最大阈值；Said, HRRTH is the maximum threshold of the read operation;

步骤7、如果request_counter是Tupwth的整数倍时，PCM_write_threhold＝PCM_write_threhold+addwrite；否则结束程序；Step 7. If request_counter is an integer multiple of Tupwth, PCM_write_threhold=PCM_write_threhold+addwrite; otherwise, end the program;

所述，Tupwth为写阈值更新周期；Said, Tupwth is the write threshold update period;

addwrite为写阈值增加跨度；addwrite increases the span for the write threshold;

步骤8、如果request_counter是Tuprth的整数倍时，PCM_read_threhold＝PCM_read_threhold+addread；否则结束程序；Step 8. If request_counter is an integer multiple of Tuprth, PCM_read_threhold=PCM_read_threhold+addread; otherwise, end the program;

所述，Tuprth为读阈值更新周期；As mentioned, Tuprth is the read threshold update period;

addread为读阈值增加跨度。addread adds the stride to the read threshold.

具体实施方式二：本实施方式与具体实施方式一不同的是，所述步骤1中两个哈希函数分别是Embodiment 2: The difference between this embodiment and Embodiment 1 is that the two hash functions in the step 1 are respectively

i＝(R1*7+pageNo+1)％bf_size；i=(R1*7+pageNo+1)%bf_size;

j＝(R2*31+pageNo+1)％bf_size；j=(R2*31+pageNo+1)%bf_size;

其中，bf_size为布隆过滤器长度，取值为256；pageNo为每个地址的特殊编码；R1,R2为随机数。Among them, bf_size is the length of the Bloom filter, the value is 256; pageNo is the special code of each address; R1, R2 are random numbers.

其它步骤及参数与具体实施方式一相同。Other steps and parameters are the same as in the first embodiment.

具体实施方式三：本实施方式与具体实施方式一不同的是，所述步骤1中时间T为10000个访存请求的时间。Embodiment 3: This embodiment is different from Embodiment 1 in that the time T in step 1 is the time for 10,000 memory access requests.

其它步骤及参数与具体实施方式一相同。Other steps and parameters are the same as in the first embodiment.

具体实施方式四：本实施方式与具体实施方式二或三不同的是，所述步骤5中写操作最大阈值200<HRWTH<8000。Embodiment 4: The difference between this embodiment and Embodiment 2 or 3 is that in thestep 5, the maximum threshold of the write operation is 200<HRWTH<8000.

其它步骤及参数与具体实施方式二或三相同。Other steps and parameters are the same as in the second or third embodiment.

具体实施方式五：本实施方式与具体实施方式一至四之一不同的是，所述步骤6中读操作最大阈值10000<HRRTH<80000。Embodiment 5: The difference between this embodiment and one of Embodiments 1 to 4 is that in the step 6, the maximum threshold of the read operation is 10000<HRRTH<80000.

其它步骤及参数与具体实施方式一至四之一相同。Other steps and parameters are the same as one of the first to fourth embodiments.

具体实施方式六：本实施方式与具体实施方式一至五之一不同的是，所述步骤7中写阈值更新周期10000<Tupwth<80000；Embodiment 6: The difference between this embodiment and one of Embodiments 1 to 5 is that in the step 7, the writing threshold update period is 10000<Tupwth<80000;

写阈值增加跨度1≤addwrite≤16。Write threshold increase span 1≤addwrite≤16.

其它步骤及参数与具体实施方式一至五之一相同。Other steps and parameters are the same as one of the specific embodiments one to five.

具体实施方式七：本实施方式与具体实施方式一至六之一不同的是，所述步骤8中读阈值更新周期2000<T_uprth<20000；Embodiment 7: The difference between this embodiment and one of Embodiments 1 to 6 is that in thestep 8, the read threshold update period is 2000<T_uprth <20000;

读阈值增加跨度1≤addread≤8。Read threshold increase span 1≤addread≤8.

其它步骤及参数与具体实施方式一至六之一相同。Other steps and parameters are the same as one of Embodiments 1 to 6.

采用以下实施例验证本发明的有益效果：Adopt the following examples to verify the beneficial effects of the present invention:

实施例一：Example 1:

本发明使用Gem5-Nvmain系统模拟器对bitcount、CRC32、dijkstra、FFT、jpeg_decoder、jpeg_encoder、mpeg2_dec、patricia、qsort、sha这10种常用负载进行测试，这些负载来自mediabench或Mibench。主存储器的详细仿真配置列于表1中。The present invention uses the Gem5-Nvmain system simulator to test 10 common loads such as bitcount, CRC32, dijkstra, FFT, jpeg_decoder, jpeg_encoder, mpeg2_dec, patricia, qsort, and sha, and these loads come from mediabench or Mibench. The detailed emulation configuration of the main memory is listed in Table 1.

表1：仿真配置Table 1: Simulation Configuration

如图1所示，本发明将访存过程中的写操作均匀的分布在了混合内存中。与无磨损均衡算法的混合内存写分布情况相比，当系统运行这三种测试负载时，本发明DLBF磨损均衡算法将系统的使用寿命分别提高提高了67.99％、84.21％、54.23％。同时DLBF将写分布方差降至无磨损均衡算法的7.2％、0.91％、1.15％。As shown in FIG. 1 , the present invention evenly distributes the write operations in the memory access process in the mixed memory. Compared with the mixed memory write distribution without the wear leveling algorithm, when the system runs the three test loads, the DLBF wear leveling algorithm of the present invention increases the service life of the system by 67.99%, 84.21% and 54.23% respectively. At the same time, DLBF reduces the write distribution variance to 7.2%, 0.91%, and 1.15% of the non-wear leveling algorithm.

如图2所示，与无磨损均衡算法、random算法，Bloom Filter算法相比，本发明DLBF将混合内存系统的使用寿命分别提升至这些算法的2.34倍、1.22倍、1.02倍。As shown in FIG. 2 , compared with the non-wear leveling algorithm, the random algorithm, and the Bloom Filter algorithm, the DLBF of the present invention increases the service life of the hybrid memory system to 2.34 times, 1.22 times, and 1.02 times, respectively, of these algorithms.

图3显示了混合内存中写分布的归一化平均方差，DLBF使得写分布的平均方差分别降低至无磨损均衡算法、random算法、Bloom Filter算法的1.04％、66.27％、96.97％。Figure 3 shows the normalized mean variance of the write distribution in the hybrid memory. DLBF reduces the mean variance of the write distribution to 1.04%, 66.27%, and 96.97% of the wear-leveling algorithm, the random algorithm, and the Bloom Filter algorithm, respectively.

本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，本领域技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。The present invention can also have other various embodiments. Without departing from the spirit and essence of the present invention, those skilled in the art can make various corresponding changes and deformations according to the present invention, but these corresponding changes and deformations are all It should belong to the protection scope of the appended claims of the present invention.

Claims (7)

Translated fromChinese

1.一种基于布隆过滤器的双层读写磨损均衡方法，其特征在于：所述方法具体过程为：1. a double-layer read-write wear leveling method based on Bloom filter, is characterized in that: the concrete process of described method is:步骤1、当有操作对页面P访存时，request_counter加1；Step 1. When there is an operation to fetch the page P, the request_counter is incremented by 1;如果当前的操作是写操作，则通过两个哈希函数，对write_counting_bloom_filter相应位置加1，进入步骤2；If the current operation is a write operation, add 1 to the corresponding position of write_counting_bloom_filter through two hash functions, and enter step 2;如果当前的操作是读操作，则通过两个哈希函数，对read_counting_bloom_filter相应位置加1，进入步骤3；If the current operation is a read operation, add 1 to the corresponding position of read_counting_bloom_filter through two hash functions, and enter step 3;所述request_counter为访存请求计数器；The request_counter is a memory access request counter;所述write_counting_bloom_filter为写布隆过滤器，read_counting_bloom_filter为读布隆过滤器；The write_counting_bloom_filter is a write bloom filter, and read_counting_bloom_filter is a read bloom filter;在时间T内，将当前写操作使得两个哈希函数对write_counting_bloom_filter相应位置write_counting_bloom_filter[i]和write_counting_bloom_filter[j]的值均大于PCM_write_threhold的页面认为是写磨损较多页面；In the time T, the current write operation makes the two hash functions consider the page whose values of write_counting_bloom_filter[i] and write_counting_bloom_filter[j] in the corresponding positions of write_counting_bloom_filter are greater than PCM_write_threhold to be the page with more wear and tear;在时间T内，将当前读操作使得两个哈希函数对read_counting_bloom_filter相应位置read_counting_bloom_filter[i]和read_counting_bloom_filter[j]的值均大于PCM_read_threhold，并且read_counting_bloom_filter[i]>write_counting_bloom_filter[i]、read_counting_bloom_filter[j]>write_counting_bloom_filter[j]的页面认为是写磨损较少的页面，是读热页面；During time T, the current read operation is made so that the values of read_counting_bloom_filter[i] and read_counting_bloom_filter[j] at the corresponding positions of read_counting_bloom_filter by the two hash functions are both greater than PCM_read_threhold, and read_counting_bloom_filter[i]>write_counting_bloom_filter[i], read_counting_bloom_filter[j]> The page of write_counting_bloom_filter[j] is considered to be a page with less write wear and is a hot page for reading;步骤2、如果当前写操作使得两个哈希函数对write_counting_bloom_filter相应位置write_counting_bloom_filter[i]和write_counting_bloom_filter[j]的值均大于PCM_write_threhold，那么将写磨损较多的页面与写磨损较少的页面进行交换，进入步骤4；否则，进入步骤5；Step 2. If the current write operation causes the values of the two hash functions to write_counting_bloom_filter[i] and write_counting_bloom_filter[j] in the corresponding positions of write_counting_bloom_filter to be greater than PCM_write_threhold, then the page with more write wear is exchanged with the page with less write wear, Go to step 4; otherwise, go to step 5;所述PCM_write_threhold为相变存储器写阈值；The PCM_write_threhold is the phase change memory write threshold;步骤3、如果当前读操作使得两个哈希函数对read_counting_bloom_filter相应位置read_counting_bloom_filter[i]和read_counting_bloom_filter[j]的值均大于PCM_read_threhold，并且read_counting_bloom_filter[i]>write_counting_bloom_filter[i]、read_counting_bloom_filter[j]>write_counting_bloom_filter[j]，则将当前读操作页面放入读热页面候选列表中，进入步骤6；否则，直接进入步骤6；Step 3. If the current read operation makes the values of read_counting_bloom_filter[i] and read_counting_bloom_filter[j] in the corresponding positions of read_counting_bloom_filter by the two hash functions are greater than PCM_read_threhold, and read_counting_bloom_filter[i]>write_counting_bloom_filter[i], read_counting_bloom_filter[j]>write_counting_bloom_filter[ j], then put the current read operation page into the read hot page candidate list, and enter step 6; otherwise, directly enter step 6;所述PCM_read_threhold为相变存储器读阈值；The PCM_read_threhold is the read threshold of the phase change memory;步骤4、将读热页面候选列表中表头存放的页面K取出，将页面P与页面K进行位置交换，进入步骤5；Step 4. Take out the page K stored in the header of the read hot page candidate list, exchange the position of page P and page K, and go to step 5;步骤5、如果PCM_write_threhold>HRWTH，则PCM_write_threhold减半，write_counting_bloom_filter中所有记录值减半，进入步骤7；否则直接进入步骤7；Step 5. If PCM_write_threhold>HRWTH, then PCM_write_threhold is halved, and all record values in write_counting_bloom_filter are halved, and go to step 7; otherwise, go directly to step 7;所述，HRWTH为写操作最大阈值；As mentioned above, HRWTH is the maximum threshold for write operations;步骤6、如果PCM_read_threhold>HRRTH，则PCM_read_threhold减半，read_counting_bloom_filter中所有记录值减半，进入步骤8；否则直接进入步骤8；Step 6. If PCM_read_threhold>HRRTH, then PCM_read_threhold is halved, and all the recorded values in read_counting_bloom_filter are halved, and go to Step 8; otherwise, go directly to Step 8;所述，HRRTH为读操作最大阈值；Said, HRRTH is the maximum threshold of the read operation;步骤7、如果request_counter是Tupwth的整数倍时，PCM_write_threhold＝PCM_write_threhold+addwrite；否则结束程序；Step 7. If request_counter is an integer multiple of Tupwth, PCM_write_threhold=PCM_write_threhold+addwrite; otherwise, end the program;所述，Tupwth为写阈值更新周期；Said, Tupwth is the write threshold update period;addwrite为写阈值增加跨度；addwrite increases the span for the write threshold;步骤8、如果request_counter是Tuprth的整数倍时，PCM_read_threhold＝PCM_read_threhold+addread；否则结束程序；Step 8. If request_counter is an integer multiple of Tuprth, PCM_read_threhold=PCM_read_threhold+addread; otherwise, end the program;所述，Tuprth为读阈值更新周期；As mentioned, Tuprth is the read threshold update period;addread为读阈值增加跨度。addread adds the stride to the read threshold.2.根据权利要求1所述一种基于布隆过滤器的双层读写磨损均衡方法，其特征在于：所述步骤1中两个哈希函数分别是2. a kind of double-layer read-write wear leveling method based on Bloom filter according to claim 1, is characterized in that: in described step 1, two hash functions are respectivelyi＝(R1*7+pageNo+1)％bf_size；i=(R1*7+pageNo+1)%bf_size;j＝(R2*31+pageNo+1)％bf_size；j=(R2*31+pageNo+1)%bf_size;其中，bf_size为布隆过滤器长度，取值为256；pageNo为每个地址的特殊编码；R1,R2为随机数。Among them, bf_size is the length of the Bloom filter, the value is 256; pageNo is the special code of each address; R1, R2 are random numbers.3.根据权利要求1所述一种基于布隆过滤器的双层读写磨损均衡方法，其特征在于：所述步骤1中时间T为10000个访存请求的时间。3 . The double-layer read-write wear leveling method based on Bloom filter according to claim 1 , wherein the time T in the step 1 is the time for 10,000 memory access requests. 4 .4.根据权利要求2或3所述一种基于布隆过滤器的双层读写磨损均衡方法，其特征在于：所述步骤5中写操作最大阈值200<HRWTH<8000。4 . The double-layer read-write wear leveling method based on Bloom filter according to claim 2 or 3, characterized in that: in the step 5, the maximum threshold of the write operation is 200<HRWTH<8000.5.根据权利要求4所述一种基于布隆过滤器的双层读写磨损均衡方法，其特征在于：所述步骤6中读操作最大阈值10000<HRRTH<80000。5 . The double-layer read-write wear leveling method based on Bloom filter according to claim 4 , wherein: in the step 6, the maximum threshold of the read operation is 10000<HRRTH<80000. 6 .6.根据权利要求5所述一种基于布隆过滤器的双层读写磨损均衡方法，其特征在于：所述步骤7中写阈值更新周期10000<Tupwth<80000；6. a kind of double-layer read-write wear leveling method based on Bloom filter according to claim 5, is characterized in that: in described step 7, write threshold value update period 10000<Tupwth<80000;写阈值增加跨度1≤addwrite≤16。Write threshold increase span 1≤addwrite≤16.7.根据权利要求6所述一种基于布隆过滤器的双层读写磨损均衡方法，其特征在于：所述步骤8中读阈值更新周期2000<T_uprth<20000；7. a kind of double-layer read-write wear leveling method based on Bloom filter according to claim 6, is characterized in that: in described step 8, read threshold value update period 2000＜T_uprth ＜20000;读阈值增加跨度1≤addread≤8。Read threshold increase span 1≤addread≤8.

Images