CN110795363B - Hot page prediction method and paging method for storage medium - Google Patents

Abstract

A hot page prediction method and a page scheduling method of a storage medium are provided, wherein access information of N recently accessed pages in the storage medium is obtained, a weight value of the current accessed page is obtained according to the access information of the current accessed page and the access information of N recently accessed pages, hot page prediction is carried out on the accessed page according to the weight value of the accessed page, and the access information comprises access times and physical addresses. Because the hot page prediction is carried out on the accessed page according to the access times and the physical address in the access information, the efficiency and the accuracy of the hot page prediction are higher.

Description

Hot page prediction method and paging method for storage medium

technical field

The invention relates to the technical field of memory access, in particular to a hot page prediction method and a page scheduling method of a storage medium.

Background technique

Random access memory (random access memory, RAM), also known as "random access memory", is an internal memory that directly exchanges data with the CPU, and is also called main memory (memory). It can be read and written at any time, and the speed is very fast, and it is usually used as a temporary data storage medium for operating systems or other running programs. According to the working principle of the storage unit, random access memory is divided into static random access memory (Static RAM, SRAM) and dynamic random access memory (Dynamic RAM, DRAM). As the data scale continues to increase and memory access-intensive applications continue to increase, DRAM is gradually unable to meet the needs of applications. Emerging memory devices have greater storage density, lower prices, and lower energy consumption, but they have the disadvantages of higher latency and limited lifespan, and cannot directly replace DRAM. For example, non-volatile memory (non-volatile memory, NVM) refers to a kind of memory that can still retain data after power failure. It has non-volatile, byte-based access, high storage density, low energy consumption, and read and write performance close DRAM, but its reading and writing speed is asymmetrical and its lifespan is limited. Using this new type of storage device and DRAM to form a hybrid memory can make good use of their respective advantages. One way is to combine DRAM and NVM into a unified address space, and data is either placed on DRAM or NVM. Since the latency of DRAM is different from that of NVM, storing more hot data in DRAM can greatly reduce the average access latency of memory. With the running of the program, the hot data of the application is not static, and the hotness of the data may change at any time, so the data needs to be migrated according to the change of the heat, and the hotter data is always stored in the DRAM. How to accurately identify and migrate hot data is an important issue to be solved in the parallel hybrid memory architecture.

The existing hybrid memory paging technology mainly improves the traditional LRU and CLOCK algorithms, utilizes the principle of locality and the basic principle that read and write requests are stored according to the storage medium, and realizes the migration operation of pages at different stages through different data structures. It can be roughly divided into passive migration, active migration and the combination of active and passive migration. The passive page migration strategy writes the requested data directly to the DRAM when the main memory misses, and triggers the migration operation when the DRAM is full, and then migrates the cold pages with low access frequency or pages with unclear read and write tendencies to the DRAM. NVM. This passive migration method can make full use of the high read and write bandwidth of DRAM, and concentrate as many write operations as possible on DRAM to achieve the goal of increasing the life of NVM. However, this passive migration strategy lacks write-frequent page migration from NVM to DRAM, and the insufficiency of the read-write prediction mechanism leads to a limited reduction in the number of NVM writes. The active page migration strategy defines the hotness and coldness of pages through access frequency and access interval, selects the appropriate data structure to develop temporal locality and spatial locality, and judges the read-write tendency of the page to perform corresponding page migration to ensure that the DRAM stores the write tendency pages, while NVM stores read-oriented pages. These methods can effectively predict the reading and writing heat of the page, and perform the migration operation when the page shows a tendency to read and write, but it requires a large space overhead to record the frequency of read and write access and local access heat, and the prediction results of each algorithm also have large differences. difference. Based on CLOCK, a paging algorithm combining active and passive is proposed. The pages in DRAM are passively managed to migrate to NVM, while the pages in NVM are actively distinguished by frequently written pages, and then migrated to DRAM. The active and passive paging algorithm can give full play to the advantages of DRAM and NVM storage media, and the implementation cost is relatively small, but this management method will cause inconsistency in the judgment of read and write heat, and the page migration ratio There are also differences. These algorithms can effectively take advantage of DRAM write performance and control the number of NVM write operations, but there are generally the following problems: First, frequent and invalid page migration between mixed memory media cannot be effectively avoided, resulting in unnecessary system overhead; Second, the prediction effect of data reading and writing tendency in weak locality application scenarios is not good, and inaccurate migration operations are prone to occur; third, it is not possible to migrate as much read-frequent data to NVM as possible, and NVM cannot be further developed The advantages of low read power consumption and static power consumption. Among them, the so-called weak temporal locality, from the perspective of time, the access is relatively scattered in the time dimension, and does not show the phenomenon of centralized access to a certain piece of data in a certain period of time, which is called weak temporal locality; from the perspective of space In other words, it does not exhibit the characteristic of concentrated access to a certain address range, which is called weak spatial locality.

It can be seen that no matter which migration method is adopted, effective prediction of hot pages is required, and there is a lack of suitable scheduling strategies for different application scenarios, especially in the case of weak locality, the read and write heat of pages cannot be accurately predicted. It is easy to cause the problem of frequent page migration, and the I/O performance and energy saving level of the hybrid memory system cannot be fully utilized. Therefore, it is particularly important to design a reasonable and effective hot page prediction method for hybrid memory paging strategies based on dynamic page sorting.

Contents of the invention

The technical problem mainly solved by the present invention is the defect of the hot page prediction method based on the hybrid memory architecture in the prior art, and a hot page prediction method of the storage medium and a paging method based on the hybrid memory architecture are proposed.

According to the first aspect, an embodiment provides a method for predicting hot pages of a storage medium, including:

Acquiring access information of recently N accessed pages in the storage medium, wherein the access information includes access times and physical addresses;

When a page is accessed in the storage medium, the weight value of the currently accessed page is obtained according to the access information of the currently accessed page and the access information of the recent N accessed pages;

Predict the hot page of the visited page according to the weight value of the visited page.

Further, when the currently visited page is not among the recent N visited pages, the currently visited page is added to the recently visited N pages, and the number of visits of the currently visited page is set to 1, to update the recent N visited pages; obtain the weight value of the currently visited page according to the visit information of the currently visited page;

When the currently accessed page is in the recently N accessed pages, add 1 to the number of visits of the currently accessed page; obtain the physical address of the currently accessed page; The weight value of the currently visited page is updated.

When the currently visited page is not in the recent N visited pages, when adding the currently visited page to the recent N visited pages, apply the least recently used algorithm in the recent N visited pages Excluding a page, and adding the currently visited page to the recent N visited pages;

The number of visits to the removed page is recorded as the historical number of visits when the page enters the recent N visited pages next time.

Further, perform quantization processing on the number of visits of the excluded pages;

Recording the result after quantization processing as the historical access times when the rejected page enters the recent N accessed pages next time;

Quantize the access times according to the following rules:

When the number of visits is 0, the result of quantization is 0;

When the number of visits is 1 to 8, the result of quantization is 1;

When the number of visits is 9 to 31, the result of quantization is 2;

When the number of visits is greater than 31, the result of quantization is 3.

According to the second aspect, an embodiment provides a paging method based on a hybrid memory architecture, the hybrid memory includes a first storage medium and a second storage medium, and the access latency of the first storage medium is smaller than that of the second storage medium. The access delay of medium; described method comprises:

Perform hot page prediction on the accessed pages in the first storage medium and the second storage medium according to the hot page prediction method in the first aspect;

Place the accessed page with a higher weight value among the recent N accessed pages in the first storage medium.

Further, establishing a corresponding relationship between each page of the first storage medium and multiple pages of the second storage medium to form a page exchange group;

The page with the highest weight value in each page exchange group is stored in the first storage medium.

According to a hot page prediction method and a page scheduling method of a storage medium in the above-mentioned embodiments, by acquiring the access information of recently N accessed pages in the storage medium, and according to the access information of the currently accessed page, the access information of the currently accessed page is obtained. weight value, and perform hot page prediction on the accessed page according to the weight value of the accessed page, wherein the access information includes access times and physical addresses. Since the hot page prediction is performed on the accessed page according to the number of visits and the physical address in the access information, the efficiency and accuracy of the hot page prediction are higher.

Description of drawings

FIG. 1 is a schematic structural diagram of a memory system based on a hybrid memory architecture in an embodiment;

Fig. 2 is a structural block diagram of a hot page predictor in an embodiment;

Fig. 3 is a structural block diagram of a hot page prediction unit in an embodiment;

Fig. 4 is a schematic diagram of grouping a first storage medium and a second storage medium in an embodiment;

Fig. 5 is a schematic flowchart of a hot page prediction method in an embodiment;

FIG. 6 is a schematic flowchart of a method for obtaining a first feature weight value in an embodiment;

FIG. 7 is a schematic flowchart of a method for obtaining a second feature weight value in an embodiment;

FIG. 8 is a schematic flowchart of a method for obtaining a third feature weight value in an embodiment;

Fig. 9 is a schematic diagram of comparing the DRAM access rate with the MDM algorithm;

Figure 10 is a schematic diagram of comparing the number of NVM writes with the MDM algorithm;

Figure 11 is a schematic diagram of the comparison of DRAM access rates under different weight tables;

FIG. 12 is a schematic flowchart of a paging method based on a hybrid memory architecture in another embodiment.

Detailed ways

The present invention will be further described in detail below through specific embodiments in conjunction with the accompanying drawings. Wherein, similar elements in different implementations adopt associated similar element numbers. In the following implementation manners, many details are described for better understanding of the present application. However, those skilled in the art can readily recognize that some of the features can be omitted in different situations, or can be replaced by other elements, materials, and methods. In some cases, some operations related to the application are not shown or described in the description, this is to avoid the core part of the application being overwhelmed by too many descriptions, and for those skilled in the art, it is necessary to describe these operations in detail Relevant operations are not necessary, and they can fully understand the relevant operations according to the description in the specification and general technical knowledge in the field.

In addition, the characteristics, operations or characteristics described in the specification can be combined in any appropriate manner to form various embodiments. At the same time, the steps or actions in the method description can also be exchanged or adjusted in a manner obvious to those skilled in the art. Therefore, the various sequences in the specification and drawings are only for clearly describing a certain embodiment, and do not mean a necessary sequence, unless otherwise stated that a certain sequence must be followed.

The serial numbers assigned to components in this document, such as "first", "second", etc., are only used to distinguish the described objects, and do not have any sequence or technical meaning. The "connection" and "connection" mentioned in this application all include direct and indirect connection (connection) unless otherwise specified.

A variety of migration methods have been proposed in the prior art, but these migration methods only consider a single feature when predicting hot pages, and only identify hot pages by historical page access frequency. But sometimes a single frequency feature cannot reflect the future popularity of the data well, and combining multiple features can identify hot pages more accurately. At different stages, the characteristics reflecting the popularity of the page may be different. At some point, the features that reflect the popularity of different pages may also be different, and using only a single feature may get wrong results. For example, consider two sequences of memory accesses:

1) ACCCD...

2)BCC...CCE...

In both cases, page C will not be accessed again. If it is judged only based on the number of visits (the page has been accessed n times, it is a hot page, and it is migrated), then in both cases (n=3) , Page C will be recognized as a hot page and will be migrated to DRAM after being accessed 3 times. But actually in the first case, C will never be accessed again, and it would incur unnecessary overhead if migrated. If further judgment is aided by their last visited page, it is possible to distinguish between these two cases and predict hot pages more accurately. In the above example, if the previously accessed page is A, then page C will not be a hot page, and if the previously accessed page is B then page C will be a hot page. Therefore, at this time, features such as the number of visits to the page at this time and the number of historical visits, the address of the previously visited page, and the address of the currently visited page can be selected. For each feature, we can record the probability that the page is a hot page under different feature values. For example, for the feature of number of visits, when the page is accessed 1, 2...n times, the probability p1, p2...pn of the recorded page is a hot page. Because different pages have different probabilities of being a hot page under the same feature, it is necessary to record the probability of each page being a hot page at different values of each feature. But this cost will be huge and unacceptable. Therefore, we borrow the methods used in predicting page reuse and branch prediction in the cache to predict the probability that different pages are hot pages under different feature values.

In the embodiment of the present application, by obtaining the access information of recently N accessed pages in the storage medium, and according to the access information of the currently accessed page, the weight value of the currently accessed page is obtained, and according to the weight value of the accessed page Hot page prediction is performed on the accessed page, where the access information includes access times and physical addresses. Since the hot page prediction is performed on the accessed pages according to the access times and physical addresses in the access information of the recently N accessed pages, the efficiency and accuracy of the hot page prediction are higher.

Embodiment one:

Please refer to FIG. 1 , which is a schematic structural diagram of a memory system based on a hybrid memory architecture in an embodiment, including a first storage medium 30 , a second storage medium 20 and a memory controller 10 . Wherein, the access delay of the first storage medium 30 is smaller than the access delay of the second storage medium 20 . The memory controller 10 includes a hot page predictor 11, configured to obtain access information of recently N accessed pages in the first storage medium and the second storage medium, and also used for when a page in the first storage medium or the second storage medium is accessed When accessing, the weight value of the currently visited page is obtained according to the visit information of the currently visited page and the visit information of the recent N visited pages, and then the hot page prediction of the visited page is performed according to the weight value of the visited page. The access information includes access times and physical addresses, and N is a natural number. The memory controller 10 is configured to place pages with high weight values in the first storage medium 30 . The memory controller 10 also includes a plurality of feature weight tables 12 for recording the weight value corresponding to any feature value of a feature of an accessed page. Each feature weight table includes a plurality of feature index values and feature weight values corresponding to the index values.

Please refer to FIG. 2 , which is a structural block diagram of a hot page predictor in an embodiment. The hot page predictor 11 includes N hot page prediction units, and each hot page prediction unit is used to record the number of visits of a recently visited page. It is also used to record the weight value of the recently visited page. In one embodiment, the hot page prediction unit uses the physical page number to index the recorded pages.

Please refer to FIG. 3 , which is a structural block diagram of a hot page prediction unit in an embodiment. Taking the first hot page prediction unit 111 as an example, each hot page prediction unit records the number of visits 1111, feature index value 1112, The number of historical visits is 1113 and the weight value is 1114. The memory controller 10 is used for when the physical address of the currently accessed page is not recorded in the hot page predictor 11, the hot page predictor 11 records the physical address of the currently accessed page in a hot page in the hot page predictor 11 In the prediction unit, and the number of accesses in the hot page prediction unit is set to 1, the hot page predictor 11 obtains the weight value of the currently accessed page according to the number of accesses and the physical address of the currently accessed page, and records it in the hot page In the page prediction unit, it is recorded on the weight value position of the hot page prediction unit; when the physical address of the currently accessed page is recorded in the hot page predictor 11, the hot page predictor 11 will record the hot page of the currently accessed page The number of visits in the prediction unit is increased by 1, and the weight value in the hot page prediction unit is updated according to the number of visits and the physical address of the currently accessed page; when the physical address of the currently accessed page is not recorded in the hot page predictor 11 , and when the hot page prediction units of the hot page predictor 11 are full, the hot page predictor 11 is also used to remove a page by applying the least recently used algorithm, and record the currently accessed page in the hot page prediction device. The least recently used algorithm (Least Recently Used, LRU) is for the management of virtual paging storage, and it makes decisions based on the usage of the page after it is loaded. Since the future usage of each page cannot be predicted, the "recent past" can only be used as an approximation of the "near future". Therefore, the LRU algorithm is to eliminate the pages that have not been used for the longest time. In one embodiment, the hot page predictor 11 uses a special stack to record page information of recently N accessed pages. When the currently accessed page is to be recorded in the hot page predictor 11, the currently accessed page is pushed into the top of the stack, and other pages are moved to the bottom of the stack, if the hot page prediction unit in the hot page predictor 11 is full, then Remove the page at the bottom of the stack. In this way, the top of the stack is always the latest accessed page, while the bottom of the stack is the page that has not been accessed the most recently.

In one embodiment, the first storage medium is used to record the number of accesses of the removed page as the historical number of accesses when the removed page enters the hot page predictor 11 next time, or quantify the number of times of access to the removed page first. Quantization processing, the result after the quantization processing is used as the historical access times when the rejected page enters the hot page predictor 11 next time.

In one embodiment, the access times are quantized according to the following rules:

When the number of visits is 0, the result of quantization is 0;

When the number of visits is 1 to 8, the result of quantization is 1;

When the number of visits is 9 to 31, the result of quantization is 2;

When the number of visits is greater than 31, the result of quantization is 3.

When the physical address of the currently accessed page is not in the hot page predictor 11, the hot page predictor 11 is also used to read the historical access times of the currently accessed page from the first medium, and record the historical access times in the page In the hot page prediction unit, it is recorded in the position of the historical access times of the hot page prediction unit.

In an embodiment, the memory controller 10 further includes a plurality of feature weight tables, namely a first feature weight table, a second feature weight table and/or a third feature weight table. The first feature weight table includes a plurality of first feature index values and first feature weight values corresponding to the index values, and is used to record the number of visits and the number of visits of any accessed page in the first storage medium and the second storage medium. The corresponding relationship of the weight value of the first feature. The second feature weight table includes a plurality of second feature index values and second feature weight values corresponding to the index values, and is used to record the historical access times of any accessed page in the first storage medium and the second storage medium The corresponding relationship with the second feature weight value. The third feature weight table includes a plurality of third feature index values and third feature weight values corresponding to the index values, and is used to record the correspondence between the physical addresses of previously accessed pages and the third feature weight values. In one embodiment, the physical address of the previously accessed page includes the physical address of the previously accessed page or the physical addresses of the previous two accessed pages, that is, the physical address of the currently accessed page is used as the third feature of the next accessed page , and/or the physical address of the previously accessed page relative to the currently accessed page as the third feature of the next accessed page. Each hot page prediction unit also records the first feature index value, the second feature index value and/or the third feature index value of the accessed page, so as to use the first feature index value and the second feature index value of the accessed page The index value and/or the third characteristic index value obtains the weight value of the visited page. The hot page prediction unit is also used to record the sum of the first feature weight value, the second feature weight value and/or the third feature weight value as the weight value of the accessed page, which is recorded in the weight value position of the hot page prediction unit . Wherein, the first characteristic weight value, the second characteristic weight value and/or the third characteristic weight value are obtained according to the first characteristic index value, the second characteristic index value and/or the third characteristic index value of the accessed page, That is, the weight value corresponding to the index value is obtained in the feature weight table through the index value.

In one embodiment, when the physical address of the currently accessed page is recorded in the hot page predictor 11, and the weight value of the currently accessed page is greater than a preset value, the hot page predictor 11 does not calculate the weight value of the currently accessed page. to update. That is, when the weight value recorded by a hot page prediction unit in the hot page predictor 11 is greater than a preset value, the weight value recorded by the prediction unit is not increased.

In one embodiment, the first storage medium includes an address remapping table, which is used to translate the physical address of the accessed page into a real address, and access pages in the first storage medium or the second storage medium according to the real address, and the memory controller further An address remapping table cache of the first storage medium is included.

Please refer to FIG. 4 , which is a schematic diagram of grouping the first storage medium and the second storage medium in an embodiment, and the memory controller is also used to establish a corresponding relationship between each page of the first storage medium and multiple pages of the second storage medium A page exchange group is formed, and the page with the highest popularity in each page exchange group is stored in the first storage medium. For example, page 1 of the first storage medium and pages 1 to m of the second storage medium form a first page swap group, and the memory controller stores the page with the largest weight value in the first page swap group in the first storage medium page 1 of the .

In one embodiment, the first storage medium is DRAM, and the second storage medium is NVM. A memory system with a hybrid memory architecture includes a cache architecture and a parallel architecture. A parallel architecture in which DRAM and NVM form a unified address space can better utilize the capacity of DRAM and NVM. So we adopt a parallel architecture, DRAM and NVM form a unified address space, and data is either placed in DRAM or in NVM. When the memory controller obtains the physical address, it first translates the physical address into a real address through the address remapping table RT (Remap Table), and then obtains data from DRAM or NVM according to the real address. In order to speed up address translation, RT's address remapping table cache RTC (Remap Table Cache) is maintained in memory. Each visit will judge the feature value required for migration according to the visit modification, and the feature weight table used to decide whether to migrate. Each NVM access will decide whether to migrate based on the information in the weight table. If it is to be migrated into DRAM, both the page and the swapped-out DRAM page are read into the swap buffer of the memory controller, and then written back to DRAM and NVM respectively.

There are many ways of address remapping, full associative, group associative, and direct mapping. Full associative is the most flexible. Any NVM page can be swapped to any position in DRAM, but remapping costs the most. The direct mapping method converts a DRAM Pages and multiple NVM pages are organized into a swap group. Page migration can only be performed within the group. Any NVM page can only be swapped with the only DRAM page in the group. The flexibility is poor, but the mapping overhead is small. In order to reduce the overhead of metadata, we adopt the way of direct mapping. DRAM and NVM form a mixed memory according to 1:m. Each DRAM page and m NVM pages form a swap group. Page migration can only be performed within the swap group, and only one page in the group can be migrated to DRAM. The entire memory space is divided into n swap groups. The swap group number is from 1 to n. The physical address modulo n can get the swap group number of the page. After determining the swap group to which it belongs, query the RT of the group to get the page group number. s position. When M=32, 6 bits are needed to identify the position of each page, so a swap group needs 25B to store remapping information. The remapping table is placed in DRAM. If each memory access requires access to DRAM once to obtain the page location, and then read data, it will cause a large number of additional memory accesses and greatly reduce performance. Therefore, a cache RTC of the remapping table is maintained in the memory control. Only when the RTC miss occurs, the DRAM will be accessed to obtain the remapping table, which can greatly reduce additional memory access.

The entire memory access process is as follows: After the physical address reaches the memory controller, it is converted into a real address according to the corresponding item in the RTC, and then the real address is used to access DRAM or NVM. If the RTC miss occurs, it is necessary to access the DRAM to obtain the corresponding real address, and then Insert an entry into the RTC.

In the embodiment of the present application, the multi-feature migration algorithm is used to predict hot pages, and it is necessary to record the weight of each page being a hot page under different feature values, and then use the sum of weights to make a judgment. The embodiment of the present application maintains a weight table for each feature, including the four features of access times, historical access times, and two previous access physical addresses (that is, the physical address of the currently accessed page is used as the next access The third characteristic of the page, and/or the physical address of the previous accessed page relative to the currently accessed page is used as the third characteristic of the next accessed page), so four weight tables are maintained. We use the XOR result of the eigenvalue and the physical address of the currently accessed page, and take the value modulo the size of the weight table as the index of the weight table, and the position pointed to by the index in the weight table is the weight of the page under the eigenvalue . If the page is visited, the weight corresponding to the feature of the last visit of the page is increased, and if the page is excluded from the training set, the weight of the feature of the last visit of the page is decreased. In order to modify the weight of the last access feature, we need to record the index of the last access feature value in the weight table, so the information recorded by the hot page prediction unit includes the number of visits (AC), the number of historical visits (QAC), the weight value (yout ) and four feature index values. AC records the historical access frequency and describes the AC status of the page in the hot page predictor last time. When a page is eliminated from the hot page predictor, the AC value of the eliminated page is quantized, and the result is a new QAC value. The four feature index values are used to store the index of the weight table corresponding to the four features of the last access to the page. The yout field records the current weight sum.

In order to quickly obtain and update the hot page prediction information, the hot page predictor is set in the memory controller, and the space occupied by the hot page prediction unit is as follows: the AC field is a 6-bit saturation counter, which records the number of accesses. QAC only needs 2 bits to record the number of quantized visits. Since the size of the weight table corresponding to each feature is 1024 items, each element of the four feature index value fields can be described by 10 bits. Since four features are used to analyze the accessed page in this embodiment, this field is maintained with 40 bytes. Since the absolute value of yout sets an upper limit, when the upper limit is 256, 9 bits are required to store the yout value. If we design the size of the hot page prediction unit to be 1024 entries, then the total overhead is about 7KB. The memory controller maintains a weight table for each feature. This embodiment uses four features, so four weight tables need to be maintained in the memory controller. Weight table entries record weight values, so each entry requires 8 bits, and the size of each weight table is 1024, so the total overhead is 1KB. The total overhead of the four weight tables is 4KB. The specific access process is:

When it arrives at the memory controller, look it up in RTC and TS at the same time, look up the real address through RTC, and add it to the hot page predictor. For each access, the value of the weight table is updated through the index recorded in the hot page predictor, and the feature values of several features are modified at the same time, and the new feature value is XORed with the page number, and the weight table is moduloed to obtain this time Access the index value of the feature value on the weight table, record the new index to the hot page predictor, and calculate the new weight and update it to the hot page predictor. If no entry corresponding to the page is found in the hot page predictor, the QAC value of the page is obtained from the DRAM, and the QAC value and the new AC value are written into the newly established hot page prediction unit, according to the current feature value Calculate the new index and weight sum and record it. When a new entry is inserted into the hot page predictor, if the hot page predictor is full, the entry of a page needs to be eliminated. The eliminated page is considered to be less popular, and the weight value in the weight table is reduced according to the index value recorded by it. , quantize the AC value of the eliminated page as a new QAC value and write it back to the DRAM, and then delete the entry. Further, if the accessed page is an NVM page, it is also necessary to determine whether to migrate. When calculating the weight sum of the page, synchronously calculate the current weight sum of the only DRAM page that can be swapped in the swap group, if the weight sum of the NVM page is greater, then swap, otherwise not swap.

Based on the above-mentioned memory system, please refer to FIG. 5 , which is a schematic flowchart of a hot page prediction method in an embodiment. The present application also discloses a hot page prediction method, including:

In step 1, access information of recently accessed pages is obtained.

Obtain access information of recently accessed pages in the storage medium, where the access information includes access times and physical addresses. In one embodiment, the access information of the recently accessed pages is obtained, that is, the access information of the previously accessed page and the access information of the previous two accessed pages relative to the currently accessed page are obtained. In one embodiment, access information of recently accessed pages is obtained.

Step 2, obtaining access information of the currently accessed page.

When a page of the storage medium is accessed, the access information of the currently accessed page is obtained.

Step 3, obtain the weight value according to the access information.

According to the access information of the currently accessed page and the access information of the recently accessed page, the weight value of the currently accessed page is obtained. In one embodiment, the weight value of the currently visited page is obtained according to the visit information of the currently visited page and the visit information of the previous visited page. In one embodiment, the weight value of the currently visited page is obtained according to the visit information of the currently visited page and the visit information of the previous two visited pages.

When the currently visited page is not among the recent N visited pages, add the currently visited page to the recent N recently visited pages, and set the number of visits of the currently visited page to 1 to update the recent N recently visited pages Visit the page, and obtain the weight value of the currently visited page according to the visit information of the currently visited page. In an embodiment, the weight value of the accessed page is the sum of the first feature weight value, the second feature weight value and/or the third feature weight value.

Please refer to FIG. 6 , which is a schematic flowchart of a method for obtaining a first feature weight value in an embodiment. The method for obtaining a first feature weight value includes:

Step 11, obtaining access information of the currently accessed page.

Obtain the physical address and access times of the currently accessed page.

Step 12, XOR the number of visits and the physical address.

XOR the access count of the currently accessed page with the physical address of the currently accessed page to obtain the XOR result.

In step 13, the XOR result is moduloed to the first feature weight table.

The XOR result of step 12 is moduloed by the total size of the first feature weight table to obtain the first feature index value. Wherein, the first feature weight table includes a plurality of first feature index values and the first feature weight values corresponding to the index values, and is used to record the number of visits and the first feature weight value of any accessed page in the storage medium. corresponding relationship.

Step 14, retrieve the weight value in the first feature weight table.

The first feature weight value corresponding to the first feature index value is acquired from the first feature weight table. The weight value of the first feature is the weight value of this feature of the page relative to the number of visits.

Please refer to FIG. 7 , which is a schematic flowchart of a method for obtaining a second feature weight value in an embodiment. The method for obtaining a second feature weight value includes:

Step 21, obtaining the historical visit times of the currently visited page.

Get the historical visit count of the currently visited page. Among them, the number of historical visits is the number of visits when the currently visited page last entered the recent N visited pages, or the number of visits when the last time it entered the recent N visited pages was quantized The value is used as the number of historical visits to this page. The number of visits of any visited page in the storage medium is stored in the preset location of the storage medium. If the currently visited page enters the recent N visited pages for the first time, the historical visit times of the page is 0 .

Step 22, XOR the historical access times and the physical address.

Exclusive OR the historical access times of the currently accessed page and the physical address of the currently accessed page to obtain the exclusive OR result.

In step 23, the XOR result is moduloed to the second feature weight table.

The XOR result of step 22 is moduloed by the total size of the second feature weight table to obtain the second feature index value. Wherein, the second feature weight table includes a plurality of second feature index values and second feature weight values corresponding to the index values, and is used to record the historical access times and the second feature weight of any accessed page in the storage medium. value correspondence.

Step 24, retrieve the weight value in the second feature weight table.

Obtain the second feature weight value corresponding to the second feature index value from the second feature weight table. The weight value of the second feature is the weight value of this feature of the page relative to the number of historical visits.

Please refer to FIG. 8 , which is a schematic flowchart of a method for obtaining a third feature weight value in an embodiment. The method for obtaining a third feature weight value includes:

Step 31, obtaining the physical addresses of the currently and previously accessed pages.

Obtain the physical address of the currently accessed page, and then obtain the physical address of the previously accessed page.

Step 32, XOR the physical addresses of the current and previous accessed pages.

XOR the physical address of the previously accessed page with the physical address of the currently accessed page to obtain the XOR result. In one embodiment, the physical address of the previously accessed page includes the physical address of the previously accessed page. In an embodiment, the physical address of the previously accessed page includes the physical addresses of the previously accessed pages twice.

In step 33, the XOR result is moduloed to the third feature weight table.

The XOR result of step 32 is moduloed by the total size of the third feature weight table to obtain the third feature index value. Wherein, the third feature weight table includes a plurality of third feature index values and third feature weight values corresponding to the index values, and is used to record the correspondence between the physical addresses of previously accessed pages and the third feature weight values.

Step 34, retrieve the weight value in the third feature weight table.

Obtain the third feature weight value corresponding to the third feature index value from the third feature weight table. The third characteristic weight value is the weight value of this characteristic of the page relative to the physical address of the previously accessed page.

When the currently accessed page is among the recent N accessed pages, add 1 to the number of visits of the currently accessed page, and obtain the physical address of the currently accessed page, which is used to base the physical address and access of the currently accessed page The number of times to update the weight value of the currently visited page. The update method is to update the first feature weight value, the second feature weight value and/or the third feature weight value of the currently accessed page. Wherein, the update method of the first feature weight value includes adding 1 to the first feature weight value of the currently accessed page, the update method of the second feature weight value includes adding 1 to the second feature weight value of the currently accessed page, and the third The method for updating the feature weight value includes adding 1 to the third feature weight value of the currently accessed page. The updated weight value of the accessed page is the sum of the updated first feature weight value, second feature weight value and/or third feature weight value. Being visited indicates that the corresponding feature of the last visit indicates that it will be visited later, so the weight of the last visit feature needs to be increased. The position of the weight value of the three features in the weight table is recorded in the feature index position in the hot page prediction unit, and the weight value of the feature on each weight table is found according to the recorded index position, and the weight is increased according to the above rules, namely The page is more likely to be visited under this feature. After updating the weight value corresponding to the feature of the last visit, you need to record the index value of the weight value corresponding to the feature of this visit, so that you can modify the weight value corresponding to this feature when the next page is accessed or deleted. For the three features, XOR is performed with the page number and feature value of this visit, and the XOR result is modulo the size of the weight table, and the calculated result is the position of the weight value of the feature of this visit in the weight table .

When the currently visited page is not among the recently visited pages, apply the least recently used algorithm to remove a page from the recently visited pages, and add the currently visited page to the recently visited pages, and record The number of visits of the excluded page is used as the historical number of visits when the page next enters the recent N visited pages. Or perform quantization on the number of visits of the removed page, and then record the result of the quantization as the historical number of visits when the removed page enters the recent N visited pages next time. In one embodiment, the number of accesses to the excluded pages is quantized according to the following rules:

When the number of visits is 0, the result of quantization is 0;

When the number of visits is 1 to 8, the result of quantization is 1;

When the number of visits is 9 to 31, the result of quantization is 2;

When the number of visits is greater than 31, the result of quantization is 3.

The removal of a page indicates that the corresponding page is not popular enough, and the weight needs to be reduced. Similar to being visited, the weight value is found according to the weight table index of the last access feature recorded in the hot page prediction unit, and the weight is reduced according to the above rules, which means that the last access feature of the page may indicate that the popularity of the page has declined. After modifying the values of the four weight tables, the entry excludes the page from the hot page predictor, and needs to quantize the AC value of the current round and write it back to DRAM.

In one embodiment, when the weight value of the currently accessed page is greater than a preset value, the weight value of the currently accessed page is not updated. When the weight value increases to a certain threshold, it cannot continue to increase, so as to ensure that when the program access mode changes, the weight value can respond to the change situation more quickly. Consider this situation: Assuming no restrictions, when a page is very popular in the first stage, after a period of time, the weight value will become very large; when the next stage comes, the page suddenly becomes cold, and rarely is visited. At this time, it takes a long time to adjust the weight value and keep reducing it. During this period, due to the excessive weight value, the hot page predictor may make a misjudgment and migrate the page that should be cooled. Therefore, it is necessary to set a range for the weight value so that when the application memory access stage changes significantly, it can quickly converge.

In the embodiment of this application, a hybrid storage data migration method based on multi-features is proposed, and four kinds of features are selected for hot page prediction, and the method of perceptron learning is applied to fuse multiple features that may reflect data popularity for parallel prediction . The perceptron is a linear model of binary classification, its input is the feature vector of the instance, and the output is the category of the instance. In order to use multiple features to predict the result, multiple features are combined into a feature vector. The dot product result yout of the feature vector and the corresponding weight is the prediction result. If the dot product result exceeds the threshold, the prediction result is true, otherwise it is False, training is the process of updating weights. If the prediction is true and the weight value does not exceed the upper limit, increase the weight value, and if the prediction is false, decrease the weight value. After training, the weight value will reflect the probability that the predicted result is true under this feature. In the hot page prediction, if the hot page is accessed, it means that the result of predicting it is a hot page is true, and the weight value is increased. If it is eliminated, it means that it is not a hot page, and the prediction result is false, and the corresponding weight value of the feature is reduced. At this point, the larger the weight value, the more likely the page with this feature is to be a hot page. In order to reduce the overhead, the dot product is no longer used to calculate the prediction result, but the feature is used to index the weight table, and then the weight sum of the index is used as the prediction result instead. For each NVM access, it is determined whether the page needs to be migrated. Since the characteristics of each access indicate the next access situation, judging whether the NVM page will be a hot page in the future only needs to be judged according to the characteristics of the current access. Add the weight values corresponding to the features of this visit to get the weight sum. If the weight sum exceeds the threshold, it will be determined as a hot page and migrated.

Compared with the MDM hot page prediction method in the prior art, the method disclosed in the present application considers more features reflecting the popularity of the page, and can perform hot page prediction more accurately.

Please refer to Figure 9 and Figure 10, which are a comparison diagram of the DRAM access rate and a comparison diagram of the NVM write quantity compared with the MDM algorithm, where the vertical axis of Figure 9 is the DRAM access rate, and the vertical axis of Figure 10 is the NVM write quantity, respectively. It is a comparison of DRAM access rate and NVM write quantity between the method disclosed in the embodiment of this application and the MDM algorithm. The above algorithm was implemented on gem5 and NVMain, tested using the benchmark of SPEC2006, and compared with the existing MDM migration algorithm with the best performance. By comparing the difference between MDM and mfHMM in DRAM access ratio and NVM write quantity. It is found that mfHMM can migrate more hot pages to DRAM, increase the proportion of DRAM access, and reduce the number of NVM access. Please refer to FIG. 11 , which is a schematic diagram of a comparison of DRAM access rates under different weight tables, where the ordinate is the DRAM access rate. It can be seen that increasing the size of the weight table can improve the accuracy of the prediction. The figures show that the weight table sizes are 1024, 2048, and 4096, respectively. Only adding less than 12KB of overhead, the DRAM access rate is increased by an average of 7.07%, and the NVM write is reduced by an average of 20.57%.

Embodiment two:

Please refer to FIG. 12 , which is a schematic flowchart of a paging method based on a hybrid memory architecture in another embodiment, wherein the hybrid memory includes a first storage medium and a second storage medium, and the access delay of the first storage medium is less than that of the second storage medium Delay, the method includes:

Step 1, perform hot page prediction on the visited page.

According to the hot page prediction method described in one of the embodiments, hot page prediction is performed on accessed pages in the first storage medium and the second storage medium.

Step 2, schedule the page.

An accessed page with a higher weight value among the recent N accessed pages is placed in the first storage medium. In one embodiment, the first storage medium is DRAM, and the second storage medium is NVM.

In one embodiment, when placing an accessed page with a high weight value among the recent N accessed pages on the first storage medium, first establish a corresponding relationship between each page of the first storage medium and multiple pages of the second storage medium A page exchange group is formed, and the page with the highest weight value in each page exchange group is stored in the first storage medium.

Those skilled in the art can understand that all or part of the functions of the various methods in the foregoing implementation manners can be realized by means of hardware, or by means of computer programs. When all or part of the functions in the above embodiments are implemented by means of a computer program, the program can be stored in a computer-readable storage medium, and the storage medium can include: read-only memory, random access memory, magnetic disk, optical disk, hard disk, etc., through The computer executes the program to realize the above-mentioned functions. For example, the program is stored in the memory of the device, and when the processor executes the program in the memory, all or part of the above-mentioned functions can be realized. In addition, when all or part of the functions in the above embodiments are realized by means of a computer program, the program can also be stored in a storage medium such as a server, another computer, a magnetic disk, an optical disk, a flash disk, or a mobile hard disk, and saved by downloading or copying. To the memory of the local device, or to update the version of the system of the local device, when the processor executes the program in the memory, all or part of the functions in the above embodiments can be realized.

The above uses specific examples to illustrate the present invention, which is only used to help understand the present invention, and is not intended to limit the present invention. For those skilled in the technical field to which the present invention belongs, some simple deduction, deformation or replacement can also be made according to the idea of the present invention.

Claims (8)

1. A method for predicting hot pages of a storage medium, comprising: Acquiring access information of recently N accessed pages in the storage medium, wherein the access information includes access times and physical addresses; When a page is accessed in the storage medium, the weight value of the currently accessed page is obtained according to the access information of the currently accessed page and the access information of the recent N accessed pages; Predict the hot page of the visited page according to the weight value of the visited page; When the storage medium has a page accessed, according to the access information of the currently accessed page and the access information of the recent N accessed pages, the weight value of the currently accessed page is obtained, including: When the currently visited page is not in the recent N visited pages, the currently visited page is added to the recently visited N pages, and the number of visits of the currently visited page is set to 1 to update The recent N visited pages; obtaining the weight value of the currently visited page according to the access information of the currently visited page; When the currently accessed page is in the recently N accessed pages, add 1 to the number of visits of the currently accessed page; obtain the physical address of the currently accessed page; The weight value of the currently visited page is updated; The weight value of the accessed page is the sum of the first feature weight value, the second feature weight value and/or the third feature weight value; The method for obtaining the first feature weight value includes: Obtain the physical address of the currently accessed page; XOR the access times of the currently accessed page with the physical address of the currently accessed page to obtain the XOR result; Taking the XOR result modulo the total size of the first feature weight table to obtain the first feature index value; The first feature weight table includes a plurality of first feature index values and first feature weight values corresponding to the index values, and is used to record the number of visits of any accessed page in the storage medium and the first feature weight value. Correspondence of weight values; Acquiring a first feature weight value corresponding to the first feature index value from the first feature weight table; The method for obtaining the second feature weight value includes: Obtain the number of historical visits of the currently visited page; XOR the historical access times of the currently accessed page with the physical address of the currently accessed page to obtain the XOR result; taking the XOR result modulo the total size of the second feature weight table to obtain a second feature index value; The second feature weight table includes a plurality of second feature index values and second feature weight values corresponding to the index values, and is used to record the historical access times of any accessed page in the storage medium and the second Correspondence of feature weight values; acquiring a second feature weight value corresponding to the second feature index value from the second feature weight table; The method for obtaining the third feature weight value includes: Obtain the physical address of the currently accessed page; Obtain the physical address of the previously accessed page; XOR the physical address of the previously accessed page with the physical address of the currently accessed page to obtain the XOR result; taking the XOR result modulo the total size of the third feature weight table to obtain a third feature index value; The third feature weight table includes a plurality of third feature index values and third feature weight values corresponding to the index values, and is used to record the correspondence between the physical address of the previously accessed page and the third feature weight value; Obtain a third feature weight value corresponding to the third feature index value from the third feature weight table. 2. The hot page prediction method according to claim 1, wherein said updating said recent N visited pages further comprises: When the currently accessed page is not among the recently N accessed pages, apply the least recently used algorithm to remove a page from the recently N accessed pages, and add the currently accessed page to the recently N accessed pages access page; The number of visits of the removed page is recorded as the historical number of visits when the page next enters the recent N visited pages. 3. The method for predicting hot pages as claimed in claim 2, wherein the recording of the number of visits of the rejected page is used as the historical number of visits when the page enters the N recently visited pages next time, including : Quantize the number of visits to the excluded pages; Recording the result after quantization processing as the historical access times when the rejected page enters the recent N accessed pages next time; Quantize the access times according to the following rules: When the number of visits is 0, the result of quantization is 0; When the number of visits is 1 to 8, the result of quantization is 1; When the number of visits is 9 to 31, the result of quantization is 2; When the number of visits is greater than 31, the result of quantization is 3. 4. The hot page prediction method according to claim 1, wherein the physical address of the previously accessed page comprises the physical address of the previously accessed page or the physical addresses of the previously accessed pages twice. 5. The hot page prediction method according to claim 1, wherein said updating the weight value of the currently accessed page according to the physical address of the currently accessed page and the number of visits includes: updating the first feature weight value, the second feature weight value and/or the third feature weight value of the currently accessed page; The update method of the first feature weight value includes: Add 1 to the first feature weight value of the currently visited page; The update method of the second feature weight value includes: Add 1 to the second feature weight value of the currently visited page; The update method of the third feature weight value includes: Add 1 to the weight value of the third feature of the currently visited page; The updated weight value of the accessed page is the sum of the updated first feature weight value, second feature weight value and/or third feature weight value. 6. The hot page prediction method according to claim 5, further comprising: When the weight value of the currently accessed page is greater than a preset value, the weight value of the currently accessed page is not updated. 7. A paging method based on a hybrid memory architecture, wherein the hybrid memory includes a first storage medium and a second storage medium, and the access delay of the first storage medium is less than the access delay of the second storage medium; The methods include: performing hot page prediction on the accessed pages in the first storage medium and the second storage medium according to the hot page prediction method according to any one of claims 1 to 6; Place the accessed page with a higher weight value among the recent N accessed pages in the first storage medium. 8. The paging method according to claim 7, wherein the placing the accessed page with a high weight value among the recent N accessed pages on the first storage medium comprises: Establishing a corresponding relationship between each page of the first storage medium and multiple pages of the second storage medium to form a page exchange group; The page with the highest weight value in each page exchange group is stored in the first storage medium.

Images