CN114780889B - A cache replacement system and method based on imitation learning - Google Patents

Abstract

The invention discloses a cache replacement system and a cache replacement method based on imitation learning, wherein the system comprises an access data acquisition module, a cache replacement prediction module, a cache replacement module and a database; the method comprises the following steps: 1) Acquiring a cache access request sequence; 2) Inputting a cache access request sequence into a trained cache replacement prediction neural network, calculating to obtain cache line eviction probability, and transmitting the cache line eviction probability to a cache replacement module; 3) And the cache replacement module performs cache line eviction according to a cache line eviction policy, so that the current cache access request is stored in a cache. The invention builds the neural network model by using the sequence information feature extractor such as the time convolution neural network and the attention mechanism, fully extracts the history information of the access sequence and the context information of the cache line in the cache, and improves the performance of model prediction.

Description

A cache replacement system and method based on imitation learning

Technical Field

The present invention relates to the field of network cache, and in particular to a cache replacement system and method based on imitation learning.

Background Art

A cache is a temporary high-speed data exchange memory that ensures that frequently accessed content can be quickly obtained. Cache replacement is a strategy for updating cache memory content when the cache is full. The goal is to replace the cache content that is accessed less frequently in the cache and store the cache content that is accessed more frequently. It ensures that the limited size of cache resources can be used as efficiently as possible. The quality of the cache replacement model directly determines the performance of the computer system or network server.

The cache replacement system based on imitation learning revolves around the content delivery network (CDN) as the core of content management and network traffic management, ensuring that the network edge cache server provides users with more efficient services, thereby building a high-quality, high-efficiency, and distinct network order network application service model. This is the fundamental goal of this system.

In the field of network caching, the quality of cache replacement models is the core issue of whether cache resources can be fully and efficiently utilized. In recent years, due to the increasing demand for Internet data flow and network content access, cache replacement algorithms for network edge caches have attracted more and more attention from researchers. At present, common cache replacement models are generally divided into the following two types: one is a heuristic-based cache replacement model and its variants. This type of model replaces and models the cache according to heuristic rules, and the implementation is relatively simple. The other is a cache replacement model based on machine learning. The idea of this type of model is to continuously modify the model through supervised learning to adapt to different cache access patterns.

The first model is a heuristic model with weak generalization ability, large performance differences in different cache access patterns, and is greatly affected by the quality of cache access sequences, and performs poorly in network caches with variable content access. The second model based on machine learning improves the generalization ability of the model well, but requires a large number of learning samples and is affected by feedback delays, which may lead to slow response in highly dynamic environments and ineffective use of historical access information, resulting in a reduced cache replacement hit rate.

Summary of the invention

The object of the present invention is to provide a cache replacement system based on imitation learning, comprising an access data acquisition module, a cache replacement prediction module, a cache replacement module and a database;

The access data acquisition module acquires a cache access request sequence S = { _st-H+1 , St _-H+2 , ..., st _-1 , _st }, and transmits it to the cache replacement prediction module; _st represents the cache access at time t, and H is the number of historical cache accesses;

The cache replacement prediction module stores a neural network;

The cache replacement prediction module predicts cache line eviction probability using a cache eviction prediction neural network and transmits the prediction to the cache replacement module;

The cache replacement module stores the current cache access request in the cache according to the cache line eviction probability;

The database stores data of the access data acquisition module, the cache replacement prediction module, and the cache replacement module.

Furthermore, the cache eviction prediction neural network includes a temporal convolutional neural network, an attention mechanism neural network, a receiving layer and an output layer.

Further, the temporal convolutional neural network includes an input layer, a hidden layer and an output layer;

The input of the temporal convolutional neural network input layer is the cache access request sequence S = {s _t-H+1 ,S _t-H+2 ,…,s _t-1 ,s _t }, and the output is the embedding of the cache access request sequence e(s) = {e(s _t-H+1 ),e(s _t-H+2 ),…,e(s _t-1 ),e(s _t )}; where e(s _t ) represents the embedding of the cache access at time t;

The input of the first hidden layer of the temporal convolutional neural network is the output e(s) of the input layer of the temporal convolutional neural network;

The input of the j+1th hidden layer is the output of the jth hidden layer The output is

Among them, the hidden layer output As shown below:

Where F(s _t ) represents the output of the dilated convolution at time t; Activation is the activation function;

Among them, the output F(s _t ) of the dilated convolution of the temporal convolutional neural network at time t is as follows:

In the formula, is the information of the access data at time td·i in the jth hidden layer; f(i) is the convolution filter; k is the convolution kernel size; d is the expansion coefficient, for the jth layer, d=2 ^j ;

The output of the output layer of the temporal convolutional neural network is the output of the last hidden layer, and the output of this layer is represented as the historical information of the cache access request sequence h(s)={h(s _t-H+1 ),h(s _t-H+2 ),…,h(s _t-1 ),h(s _t )}; where h(s _t ) represents the historical information of the cache access content at time t.

Further, the input of the attention mechanism neural network is the historical information of the current cache access request sequence h(s)={h(s _t-H+1 ),h(s _t-H+2 ),…,h(s _t-1 ),h(s _t )}, the embedding of the cache line content of the current time step e(l)={e(l ₁ ),e(l ₂ ),e(l ₃ ),…,e(l _W )}, and the output is the context vector gw={g ₁ ,g ₂ ,…,g _W } for each cache line; wherein l _w represents the wth cache line in the cache; W represents the number of cache lines in the cache; g _w represents the context content of the wth cache line; w=1, 2,…, W;

Among them, the context vector g _w is as follows:

The coefficients _αi are as follows:

α _i =softmax(e(l _w ) ^T W _e h(s _t-H+i )) (4)

Where _We is a trainable parameter.

Furthermore, the input of the receiving layer is the context vector g _w , and the output is the reuse distance dis = {dis ₁ , dis ₂ , ..., dis _W } of each cache line; wherein dis _w represents the reuse distance of the wth cache line;

Among them, the reuse distance dis of each cache line is as follows:

dis=Linear(Relu(Linear(gw))) (5)

In the formula, Relu is the activation function; Linear is the linear function;

The input of the output layer is the reuse distance dis of each cache line, and the output is the eviction probability prob = {p ₁ ,p ₂ ,…,p _W } of each cache line; wherein p _w represents the eviction probability of the wth cache line in the cache;

Among them, the eviction probability prob of each cache line is as follows:

prob＝Sigmoid(dis) (6)

In the formula, Sigmoid is the activation function.

Further, a neural network training module is included;

The neural network training module is used to train the cache eviction prediction neural network of the cache replacement prediction module.

Furthermore, the steps of training the cache eviction prediction neural network include:

1) Determine whether the current cache is not full or whether the current cache access request is already in the cache. If so, directly put the current cache access request into the cache or obtain the current cache access request from the cache. Otherwise, proceed to step 2);

2) Building a cache eviction prediction neural network;

3) Use the Belady algorithm to calculate the actual reuse distance of each cache access request Where n is the total number of visits; Indicates the actual reuse distance of the nth cache access request;

4) Generate the eviction probability of each cache line prob = {p ₁ ,p ₂ ,…,p _W } using the cache eviction prediction neural network;

5) Calculate the error between the cache line eviction probability output by the cache eviction prediction network at time t and the Belady algorithm Right now:

Where, prob _t , are the cache line eviction probabilities of the cache eviction prediction network and Belady algorithm at time t, respectively; are the probabilities of evict the i-th cache line at time t by the cache eviction prediction network and the Belady algorithm, respectively; W is the cache size;

Among them, the cache line eviction probability Satisfy the following formula:

Among them, the parameters topk and sequence They are as follows:

topk＝int(W*α) (10)

Where α is the eviction percentage, int() is the rounding down function, and decend_sort() is the descending sorting function;

6) Use the gradient of the cache eviction prediction network to update the neural network parameter ω, and determine whether the loss function value reaches the minimum or the number of training rounds reaches the preset value. If so, end the training of the cache eviction prediction neural network, otherwise, proceed to step 7);

The parameter ω is updated as follows: Cache eviction prediction neural network

Among them, ω is the current network parameter; ω′ is the updated parameter; ε _t is the current learning rate, is the gradient symbol; Bceloss is the loss function.

7) The cache replacement module selects a cache line to evict and stores the current access in the cache;

8) Get a new cache access request and return to step 1).

Further, the step of the cache replacement module storing the current cache access request into the cache includes:

1) Determine whether the current cache is not full or whether the current cache access request is already in the cache. If so, directly put the current cache access request into the cache or obtain the current cache access request from the cache. Otherwise, go to step 2).

2) The cache replacement module retrieves the cache line eviction probability from the cache replacement prediction module and generates a cache line eviction strategy;

3) The cache replacement module evicts the cache line according to the cache line eviction policy, thereby storing the current cache access request in the cache.

Furthermore, the cache line eviction strategy is as follows:

index=decend_sort(prob) (13)

evict_index＝index(0) (14)

Where prob is the cache line eviction probability vector, decend_sort() is the descending sorting function, index(0) represents the cache line with the highest eviction probability, evict_index is the eviction strategy, and index is the guidance function.

A method for using a cache replacement system based on imitation learning comprises the following steps:

1) Build a cache replacement system based on imitation learning;

2) Obtain cache access request sequence;

3) Determine whether the current cache is not full or whether the current access is in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache and go to step 9). Otherwise, go to step 4).

4) training a cache replacement prediction neural network of a cache replacement prediction module;

5) Input the cache access request sequence into the trained cache replacement prediction neural network, calculate the cache line eviction probability, and transmit it to the cache replacement module;

6) The cache replacement module determines whether the current cache is not full or whether the current cache access request is already in the cache. If so, the current cache access request is directly placed in the cache or obtained from the cache. Otherwise, it proceeds to step 7).

7) The cache replacement module retrieves the cache line eviction probability from the cache replacement prediction module and generates a cache line eviction strategy;

8) The cache replacement module evicts the cache line according to the cache line eviction policy, thereby storing the current cache access request in the cache.

9) Obtain a new cache access request sequence and return to step 3).

The technical effect of the present invention is unquestionable. The present invention uses sequence information feature extractors such as temporal convolutional neural networks and attention mechanisms to build a neural network model, which fully extracts the historical information of the access sequence and the contextual information of the cache lines in the cache, thereby improving the performance of model prediction.

The present invention uses the imitation learning technology to further imitate the behavior of the Belady expert, trains the neural network model according to the gap between the output of the cache replacement prediction module and the output of the Belady expert, and improves the hit rate and application scope of the model.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a general algorithm flow chart of a cache replacement method based on imitation learning;

FIG2 is a diagram showing the structure of a neural network model of a cache replacement method based on imitation learning;

FIG3 is a flowchart of a neural network training for a cache replacement method based on imitation learning.

DETAILED DESCRIPTION

The present invention is further described below in conjunction with the embodiments, but it should not be understood that the above subject matter of the present invention is limited to the following embodiments. Without departing from the above technical ideas of the present invention, various substitutions and changes are made according to the common technical knowledge and customary means in the art, which should all be included in the protection scope of the present invention.

Embodiment 1:

Referring to FIG. 1 to FIG. 3 , a cache replacement system based on imitation learning includes an access data acquisition module, a cache replacement prediction module, a cache replacement module and a database;

The access data acquisition module acquires a cache access request sequence S = { _st-H+1 , st _-H+2 , ..., st _-1 , _st }, and transmits it to the cache replacement prediction module; _st represents the cache access at time t, and H is the number of historical cache accesses;

The cache replacement prediction module stores a neural network;

The cache replacement prediction module predicts cache line eviction probability using a cache eviction prediction neural network and transmits the prediction to the cache replacement module;

The cache replacement module stores the current cache access request in the cache according to the cache line eviction probability;

The database stores data of the access data acquisition module, the cache replacement prediction module, and the cache replacement module.

The cache eviction prediction neural network includes a temporal convolutional neural network, an attention mechanism neural network, a receiving layer and an output layer.

The temporal convolutional neural network includes an input layer, a hidden layer and an output layer;

The input of the temporal convolutional neural network input layer is the cache access request sequence S = {s _t-H+1 ,s _t-H+2 ,…,s _t-1 ,s _t }, and the output is the embedding of the cache access request sequence e(s) = {e(s _t-H+1 ),e(s _t-H+2 ),…,e(s _t-1 ),e(s _t )}; where e(s _t ) represents the embedding of the cache access at time t;

The input of the first hidden layer of the temporal convolutional neural network is the output e(s) of the input layer of the temporal convolutional neural network;

The input of the j+1th hidden layer is the output of the jth hidden layer The output is

Among them, the hidden layer output As shown below:

Where F(s _t ) represents the output of the dilated convolution at time t; Activation is the activation function;

Among them, the output F(s _t ) of the dilated convolution of the temporal convolutional neural network at time t is as follows:

In the formula, is the information of the access data at time td·i in the jth hidden layer; f(i) is the convolution filter; k is the convolution kernel size; d is the expansion coefficient, for the jth layer, d=2 ^j ;

The output of the output layer of the temporal convolutional neural network is the output of the last hidden layer, and the output of this layer is represented as the historical information of the cache access request sequence h(s)={h(s _t-H+1 ),h(s _t-H+2 ),…,h(s _t-1 ),h(s _t )}; where h(s _t ) represents the historical information of the cache access content at time t.

F(s _t ) in Formula 2 is the dilated convolution output of the temporal convolutional neural network at time t, and F(s _t ) is the input at time t. After residual connection, the output Therefore, F(s _t ) can be regarded as the intermediate output of the temporal convolutional neural network at time t, which is consistent with the input at the current time. The output after the residual connection is the actual output of the temporal convolutional neural network at the current moment. Here, the output h(s) of the temporal convolutional neural network output layer is the actual output of the last layer of the temporal convolutional neural network.

The input of the attention mechanism neural network is the historical information of the current cache access request sequence h(s)={h( _st-H+1 ),h( _st-H+2 ),…,h( _st-1 ),h( _st )}, the embedding of the cache line content of the current time step e(l)={e( _l1 ),e( _l2 ),e( _l3 ),…,e( _lW )}, and the output is the context vector gw={ _g1 , _g2 ,…, _gw } for each cache line; where _lw represents the wth cache line in the cache; W represents the number of cache lines in the cache; _gw represents the context content of the wth cache line; w=1, 2,…,W;

Among them, the context vector g _w is as follows:

The coefficients _αi are as follows:

α _i =softmax(e(l _w ) ^T W _e h(s _t-H+i )) (4)

Where _We is a trainable parameter.

The input of the receiving layer is the context vector g _w , and the output is the reuse distance dis = {dis ₁ , dis ₂ , ..., dis _W } of each cache line; wherein dis _w represents the reuse distance of the wth cache line;

Among them, the reuse distance dis of each cache line is as follows:

dis=Linear(Relu(Linear(gw))) (5)

In the formula, Reli is the activation function; Linear is the linear function;

The input of the output layer is the reuse distance dis of each cache line, and the output is the eviction probability prob = {p ₁ ,p ₂ ,…,p _W } of each cache line, where p _w represents the eviction probability of the w-th cache line in the cache;

Among them, the eviction probability prob of each cache line is as follows:

prob＝Sigmoid(dis) (6)

In the formula, Sigmoid is the activation function.

The system also includes a neural network training module;

The neural network training module is used to train the cache eviction prediction neural network of the cache replacement prediction module.

The steps to train a cache eviction prediction neural network include:

1) Determine whether the current cache is not full or whether the current cache access request is already in the cache. If so, directly put the current cache access request into the cache or obtain the current cache access request from the cache. Otherwise, proceed to step 2);

2) Building a cache eviction prediction neural network;

3) Use the Belady algorithm to calculate the actual reuse distance of each cache access request Where n is the total number of visits; Indicates the actual reuse distance of the nth cache access request;

4) Generate the eviction probability of each cache line prob = {p ₁ ,p ₂ ,…,p _W } using the cache eviction prediction neural network;

5) Calculate the error between the cache line eviction probability output by the cache eviction prediction network at time t and the Belady algorithm Right now:

Where, prob _t , are the cache line eviction probabilities of the cache eviction prediction network and Belady algorithm at time t, respectively; are the probabilities of evict the i-th cache line at time t by the cache eviction prediction network and the Belady algorithm, respectively; W is the cache size;

Among them, the cache line eviction probability Satisfy the following formula:

topk＝int(W*α) (8)

Where α is the eviction percentage, int() is the floor function, and decend_sort() is the descending sort function.

6) Use the gradient of the cache eviction prediction network to update the neural network parameter ω, and determine whether the loss function value reaches the minimum or the number of training rounds reaches the preset value. If so, end the training of the cache eviction prediction neural network, otherwise, proceed to step 7);

The parameter ω is updated as follows: Cache eviction prediction neural network

Among them, ω is the current network parameter; ω′ is the updated parameter; ε _t is the current learning rate, is the gradient symbol; Bceloss is the binary cross entropy loss function.

7) The cache replacement module selects a cache line to evict and stores the current access in the cache;

8) Get a new cache access request and return to step 1).

The step of storing the current cache access request in the cache by the cache replacement module includes:

1) Determine whether the current cache is not full or whether the current cache access request is already in the cache. If so, directly put the current cache access request into the cache or obtain the current cache access request from the cache. Otherwise, go to step 2).

2) The cache replacement module retrieves the cache line eviction probability from the cache replacement prediction module and generates a cache line eviction strategy;

3) The cache replacement module evicts the cache line according to the cache line eviction policy, thereby storing the current cache access request in the cache.

The cache line eviction policy is as follows:

index=decend_sort(prob) (13)

evict_index＝index(0) (14)

Where prob is the cache line eviction probability vector, decend_sort() is the descending sorting function, index(0) represents the cache line with the highest eviction probability, evict_index is the eviction strategy, and index is the guidance function.

A method for using a cache replacement system based on imitation learning comprises the following steps:

1) Build a cache replacement system based on imitation learning;

2) Obtain cache access request sequence;

3) Determine whether the current cache is not full or whether the current access is in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache and go to step 9). Otherwise, go to step 4).

4) training a cache replacement prediction neural network of a cache replacement prediction module;

5) Input the cache access request sequence into the trained cache replacement prediction neural network, calculate the cache line eviction probability, and transmit it to the cache replacement module;

6) The cache replacement module determines whether the current cache is not full or whether the current cache access request is already in the cache. If so, the current cache access request is directly placed in the cache or obtained from the cache. Otherwise, it proceeds to step 7).

7) The cache replacement module retrieves the cache line eviction probability from the cache replacement prediction module and generates a cache line eviction strategy;

8) The cache replacement module evicts the cache line according to the cache line eviction policy, thereby storing the current cache access request in the cache.

9) Obtain a new cache access request sequence and return to step 3).

Embodiment 2:

A cache replacement system based on imitation learning includes an access data acquisition module, a cache replacement prediction module, a cache replacement module and a database.

The access data acquisition module obtains the access sequence to the cache. S = { _st-H+1 , st _-H+2 , ..., st _-1 , _st }. Where _st represents the cache access at time t, and H is the number of historical cache accesses in the cache access sequence. Determine whether the current cache is not full or whether the currently accessed content is already in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache. Otherwise, send the access sequence to the cache replacement prediction module.

The cache replacement prediction module includes a temporal convolutional neural network, an attention mechanism neural network, a receiving layer and an output layer, and sends the output cache line eviction probability to the cache replacement module.

The temporal convolutional neural network and the attention mechanism neural network have a sequential relationship. The temporal convolutional neural network extracts the historical information of each cache access in the access sequence in real time, and the attention mechanism neural network extracts the historical information of each access sequence and calculates the embedding of the cache line in the current cache to generate the context of each cache line. Together with the receiving layer and the output layer, they form a neural network model, and the structure includes:

Ⅰ) Temporal convolutional neural network extracts access sequence history information;

II) The attention network calculates the context vector;

III) The receiving layer outputs the reuse distance prediction of each cache line;

IV) The output layer outputs the eviction probability prediction for each cache line;

Temporal Convolutional Neural Network: Temporal Convolutional Neural Network consists of input layer, hidden layer and output layer.

The input of the temporal convolutional neural network input layer is the cache access request sequence S = { _st-H+1 , st _-H+2 , ..., st _-1 , _st }, and the output is the embedding of the cache access sequence e(s) = {e( _st-H+1 ), e( _st-H+2 ), ..., e( _st-1 ), e( _st )}, where e( _st ) represents the embedding of the cache access at time t. The output of the input layer is used as the input of the first hidden layer.

Temporal Convolutional Neural Network Hidden Layers The input is the previous hidden layer The output, The calculation steps are as follows:

Where F(s _t ) represents the output of the dilated convolution, and Activation is the activation function. In order to prevent the gradient from disappearing, the temporal convolutional neural network uses residual connections in each layer to obtain the output hidden ^l+1 of the next layer.

In the formula, is the information of the access data at time td·i in the jth hidden layer; f:{0,…,k-1}→R is the convolution filter, k is the convolution kernel size, d is the expansion coefficient, and for the lth layer, d＝2 ^j .

The output layer of the temporal convolutional neural network outputs the information of the last hidden layer as the historical information of each cache access data h(s) = {h(s _t-H+1 ), h(s _t-H+2 ),…, h(s _t-1 ), h(s _t )}, where h(s _t ) represents the historical information of the cache access content at time t.

Attention network: For any time step t, the input of the attention network is the historical information of the current cache access request sequence h(s) = {h( _st-H+1 ), h( _st-H+2 ), ..., h( _st-1 ), h( _st )} and the embedding of the cache line content of the current time step e(l) = {e( _l1 ), e( _l2 ), e( _l3 ), ..., e( _lW )}, where _lw represents the wth cache line in the cache and W represents the number of cache lines in the cache. The output is the context vector gw = { _g1 , _g2 , ..., _gw } for each cache line, where _gw represents the context content of the wth cache line.

The context g _w is as follows:

α _i =softmax(e(l _w ) ^T W _e h(s _t-H+i )) (3)

Where _We is a trainable parameter

Continuing layer: The input of the continuing layer is the context vector gw, and the output is the reuse distance dis = {dis ₁ , dis ₂ , ..., dis _W } of each cache line, where dis _w represents the reuse distance of the w-th cache line.

dis=Linear(Relu(Linear(gw))) (5)

The activation function of the receiving layer is RELU: f(x) = max(0,x), and the linear function is Linear: y = xA ^T + b.

Output layer: The input of the output layer is the reuse distance dis of each cache line, and the output is the eviction probability prob = {p ₁ , p ₂ , ..., p _W } of each cache line, where p _w represents the eviction probability of the w-th cache line in the cache.

prob＝Sigmoid(dis) (6)

The activation function of the output layer is Sigmoid:

The cache replacement module selects a cache line to evict and stores the currently accessed data according to the eviction probability of each cache line in the cache.

The cache line eviction selection steps are as follows:

index=decend_sort(prob) (7)

evict_index＝index(0) (8)

Where prob represents the cache line eviction probability vector, decend_sort() is the descending sort function, and index(0) represents the cache line with the highest eviction probability.

The neural network training module trains the neural network model to obtain a trained neural network model.

The steps to train a neural network model include:

1) Determine whether the current cache is not full or whether the currently accessed content is already in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache and go to step 7). Otherwise, go to step 2).

2) Belady expert strategy calculates the true reuse distance of each access data based on all access data Where n is the total number of visits.

3) Establishing a cache eviction prediction network, wherein the cache eviction prediction network includes a cache replacement prediction module and a cache eviction module.

During the neural network training process, a cache eviction prediction network model is built, which is the neural network model described in Ⅰ), Ⅱ), Ⅲ), and Ⅳ above. The difference between neural network training and generating actual cache replacement strategies is that during training, Belady experts generate cache eviction content in real time and cache line eviction probabilities generated by the model for error calculation and parameter update; while in the actual cache replacement strategy, only the trained model is used to calculate cache line eviction probabilities.

4) The cache replacement prediction module generates the eviction probability prob = {p ₁ , p ₂ , ..., p _W } for each cache line.

5) Calculate the error between the cache line eviction probability output by the cache eviction prediction network and the Belady expert strategy.

Where, prob _t , are the probability vectors of the model and Belady algorithm evicting cached content at time t, respectively. are the probabilities of evicting the i-th cache line at time t by the model and Belady algorithm, respectively, and W is the cache size.

The calculation of is as follows:

topk＝int(W*α) (10)

Where α is the eviction percentage, int() is the floor function, and decend_sort() is the descending sort function.

The cache eviction prediction network parameter ω is updated as follows:

Among them, ω is the current network parameter, ω′ is the updated parameter, ε _t is the current learning rate, is the gradient symbol.

6) Use the gradient of the cached eviction prediction network to update the global neural network parameters.

7) The cache replacement module selects a cache line for eviction and stores the current access in the cache.

8) Get a new cache access sequence and return to step 1).

The cache replacement module comprises the following steps:

1) Determine whether the current cache is not full or whether the currently accessed content is already in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache. Otherwise, go to step 2).

2) Using the trained neural network to extract the reuse distance of each cache access content in the current cache sequence, the steps include:

2.1) Taking the last hidden layer state of the temporal convolutional network and the embedding of the cache line as input, we get the context information gw of each cache line.

2.2) The context information gw of each cache line is output through the receiving layer to obtain the reuse distance dis of the cache line.

3) Use the trained neural network to output the eviction probability of each cache line through the output layer based on the extracted cache reuse distance.

4) Use the cache replacement module to replace cache content.

The database stores data of the access data acquisition module, the cache replacement prediction module, the cache replacement module, and the neural network training module.

Embodiment 3:

Referring to FIG. 1 to FIG. 3 , the cache replacement method based on imitation learning includes the following steps:

1) Get the access sequence to the cache.

The access data acquisition module obtains the access sequence to the cache. S = { _st-H+1 , st _-H+2 , ..., st _-1 , _st }. Where _st represents the cache access at time t, and H is the number of historical cache accesses in the cache access sequence. Determine whether the current cache is not full or whether the currently accessed content is already in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache. Otherwise, send the access sequence to the cache replacement prediction module.

2) Establish a cache replacement prediction model and send the output cache line eviction probability to the cache replacement module.

The cache replacement prediction module includes a temporal convolutional neural network, an attention mechanism neural network, a receiving layer and an output layer, and sends the output cache line eviction probability to the cache replacement module.

The temporal convolutional neural network includes an input layer, a hidden layer and an output layer.

The input of the temporal convolutional neural network input layer is the cache access request sequence S = {s _t-H+1 ,s _t-H+2 ,…,s _t-1 ,s _t }, and the output is the embedding of the cache access sequence e(s) = {e(s _t-H+1 ),e(s _t-H+2 ),…,e(s _t-1 ),e(s _t )}, where e(s _t ) represents the embedding of the cache access at time t. The output of the input layer is used as the input of the first hidden layer.

Temporal Convolutional Neural Network Hidden Layers The input is the previous hidden layer The output, The calculation steps are as follows:

Where F(s _t ) represents the output of the dilated convolution, and Activation is the activation function. In order to prevent the gradient from disappearing, the temporal convolutional neural network uses residual connections in each layer to obtain the output hiddenj ⁺¹ of the next layer.

In the formula, is the information of the access data at time td·i in the jth hidden layer; f:{0,…,k-1}→R is the convolution filter, k is the convolution kernel size, d is the expansion coefficient, and for the jth layer, d=2 ^j .

The output layer of the temporal convolutional neural network outputs the information of the last hidden layer as the historical information of each cache access data h(s) = {h(s _t-H+1 ), h(s _t-H+2 ),…, h(s _t-1 ), h(s _t )}, where h(s _t ) represents the historical information of the cache access content at time t.

For any time step t, the attention network takes the output of the temporal convolutional network output layer h(s) = {h(s _t-H+1 ), h(s _t-H+2 ), …, h(s _t-1 ), h(s _t )} and the embedding of the cache line content of the current time step e(l) = {e(l ₁ ), e(l ₂ ), e(l ₃ ), …, e(l _w )} as the input of the attention network, where l _w represents the wth cache line in the cache and W represents the number of cache lines in the cache. The output is the context vector gw = {g ₁ , g ₂ , …, g _w } for each cache line, where g _w represents the context content of the wth cache line.

The context g _w is as follows:

α _i =softmax(e(l _w ) ^T W _e h(s _t-H+i )) (3)

Where _We is a trainable parameter

The input of the receiving layer is the context vector gw, and the output is the reuse distance dis={dis ₁ , dis ₂ , …, dis _W } of each cache line, where dis _w represents the reuse distance of the w-th cache line.

dis=Linear(Relu(Linear(gw))) (5)

The activation function of the receiving layer is RELU: f(x) = max(0,x), and the linear function is Linear: y = xA ^T + b.

The input of the output layer is the reuse distance dis of each cache line, and the output is the eviction probability prob = {p ₁ , p ₂ , ..., p _W } of each cache line, where p _w represents the eviction probability of the wth cache line in the cache.

prob＝Sigmoid(dis) (6)

The activation function of the output layer is Sigmoid:

3) The output of the cache replacement prediction module is input to the cache replacement module to replace a cache line in the cache with the current cache access.

The cache replacement module selects a cache line to evict and stores the currently accessed data according to the eviction probability of each cache line in the cache.

The cache line eviction selection steps are as follows:

index=decend_sort(prob) (7)

evict_index＝index(0) (8)

Where prob represents the cache line eviction probability vector, decend_sort() is the descending sort function, and index(0) represents the cache line with the highest eviction probability.

4) Establishing a neural network training module, training the neural network in the cache replacement prediction model, and obtaining a trained neural network model.

The steps to train a neural network model include:

4.1) Determine whether the current cache is not full or whether the currently accessed content is already in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache and proceed to step 7), otherwise, proceed to step 2).

4.2) Belady expert strategy calculates the true reuse distance of each access data based on all access data Where n is the total number of visits.

4.3) Establishing a cache eviction prediction network, wherein the cache eviction prediction network includes a cache replacement prediction module and a cache eviction module.

4.4) The cache replacement prediction module generates the eviction probability prob = {p ₁ , p ₂ , …, p _W } for each cache line.

4.5) Calculate the error between the cache line eviction probability output by the cache eviction prediction network and the Belady expert strategy.

Where, prob _t , are the probability vectors of the model and Belady algorithm evicting cached content at time t, respectively. are the probabilities of evicting the i-th cache line at time t by the model and Belady algorithm, respectively, and W is the cache size.

The calculation of is as follows:

k＝int(W*topk) (10)

Where α is the eviction percentage, int() is the rounding down function, and decend_sort() is the descending sorting function

The cache eviction prediction network parameter ω is updated as follows:

Among them, ω is the current network parameter, ω′ is the updated parameter, ε _t is the current learning rate, is the gradient symbol.

4.6) Use the gradient of the cached eviction prediction network to update the global neural network parameters.

4.7) The cache replacement module selects a cache line for eviction and stores the current access in the cache.

4.8) Get a new cache access sequence and return to step 1).

5) Input the access sequence into the trained neural network model and use the cache replacement module to complete the cache replacement operation.

The trained neural network is used to predict and replace cache access data. The steps include:

5.1) Determine whether the current cache is not full or whether the currently accessed content is already in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache. Otherwise, go to step 2).

5.2) Using the trained neural network to extract the reuse distance of each cache access content in the current cache sequence, the steps include:

5.2.1) Taking the last hidden layer state of the temporal convolutional network and the embedding of the cache line as input, we get the context information gw of each cache line.

5.2.2) The context information gw of each cache line is output through the receiving layer to obtain the reuse distance dis of the cache line.

5.3) Use the trained neural network to output the eviction probability of each cache line through the output layer based on the extracted cache reuse distance.

5.4) Use the trained cache replacement module to replace cache content.

Claims (7)

1. A cache replacement system based on imitation learning, characterized by comprising an access data acquisition module, a cache replacement prediction module, a cache replacement module and a database; The access data acquisition module acquires a cache access request sequence S = { _st-H+1 , st _-H+2 , ..., st _-1 , _st }, and transmits it to the cache replacement prediction module; _st represents the cache access at time t, and H is the number of historical cache accesses; The cache replacement prediction module stores a neural network; The cache replacement prediction module predicts cache line eviction probability using a cache eviction prediction neural network and transmits the prediction to the cache replacement module; The cache replacement module stores the current cache access request in the cache according to the cache line eviction probability; The database stores data of the access data acquisition module, the cache replacement prediction module, and the cache replacement module; The cache eviction prediction neural network includes a temporal convolutional neural network, an attention mechanism neural network, a receiving layer and an output layer; The temporal convolutional neural network includes an input layer, a hidden layer and an output layer; The input of the temporal convolutional neural network input layer is a cache access request sequence S = { _st-H+1 , st _-H+2 , ..., st _-1 , _st }, and the output is an embedding of the cache access request sequence e(s) = {e( _st-H+1 ), e( _st-H+2 ), ..., e( _st-1 ), e( _st )}; where e( _st ) represents the embedding of the cache access at time t; The input of the first hidden layer of the temporal convolutional neural network is the output e(s) of the input layer of the temporal convolutional neural network; The input of the j+1th hidden layer is the output of the jth hidden layer The output is Among them, the hidden layer output As shown below: Where F(s _t ) represents the output of the dilated convolution at time t; Activation is the activation function; Among them, the dilated convolution F(s _t ) at time t is as follows: In the formula, is the information of the access data at time td·i in the jth hidden layer; f(i) is the convolution filter; k is the convolution kernel size; d is the expansion coefficient, for the jth layer, d=2 ^j ; The output of the output layer of the temporal convolutional neural network is the output of the last hidden layer, and the output of this layer is represented as the historical information of the cache access request sequence h(s)={h(s _t-H+1 ), h(s _t-H+2 ), ..., h(s _t-1 ), h(s _t )}; where h(s _t ) represents the historical information of the cache access content at time t; The steps to train a cache eviction prediction neural network include: 1) Determine whether the current cache is not full or whether the current cache access request is already in the cache. If so, directly put the current cache access request into the cache or obtain the current cache access request from the cache. Otherwise, proceed to step 2); 2) Building a cache eviction prediction neural network; 3) Use the Belady algorithm to calculate the actual reuse distance of each cache access request Where n is the total number of visits; Indicates the actual reuse distance of the nth cache access request; 4) Generate the eviction probability prob = {p ₁ , p ₂ , ..., p _W } of each cache line using the cache eviction prediction neural network; 5) Calculate the error between the cache line eviction probability output by the cache eviction prediction network at time t and the Belady algorithm Right now: In the formula, are the cache line eviction probabilities of the cache eviction prediction network and Belady algorithm at time t, respectively; are the probabilities of evict the i-th cache line at time t by the cache eviction prediction network and the Belady algorithm, respectively; W is the cache size; Among them, the cache line eviction probability Satisfy the following formula: Among them, the parameters topk and sequence They are as follows: topk＝int(W*α) (10) Where α is the eviction percentage, int() is the rounding down function, and decend_sort() is the descending sorting function; 6) Use the gradient of the cache eviction prediction network to update the neural network parameter ω, and determine whether the loss function value reaches the minimum or the number of training rounds reaches the preset value. If so, end the training of the cache eviction prediction neural network, otherwise, proceed to step 7); The parameter ω is updated as follows: Cache eviction prediction neural network Among them, ω is the current network parameter; ω′ is the updated parameter; ε _t is the current learning rate, is the gradient symbol; Bceloss is the loss function; 7) The cache replacement module selects a cache line to evict and stores the current access in the cache; 8) Get a new cache access request and return to step 1). 2. The cache replacement system based on imitation learning according to claim 1 is characterized in that the input of the attention mechanism neural network is the historical information of the current cache access request sequence h(s) = {h(s _t-H+1 ), h(s _t-H+2 ), ..., h(s _t-1 ), h(s _t )}, the embedding of the cache line content at the current time step e(l) = {e(l ₁ ), e(l ₂ ), e(l ₃ ), ..., e(l _W )}, and the output is the context vector gw = {g ₁ , g ₂ , ..., g _W } for each cache line; where l _w represents the wth cache line in the cache; W represents the number of cache lines in the cache; g _w represents the context content of the wth cache line; w = 1, 2, ..., W; Among them, the context vector g _w is as follows: The coefficients _αi are as follows: α _i =softmax(e(l _w ) ^T W _e h(s _t-H+i )) (4) Where _We is a trainable parameter. 3. The cache replacement system based on imitation learning according to claim 2, characterized in that the input of the receiving layer is the context vector g _w , and the output is the reuse distance dis of each cache line = {dis ₁ , dis ₂ , ..., dis _W }; wherein dis _W represents the reuse distance of the Wth cache line; Among them, the reuse distance dis of each cache line is as follows: dis=Linear(Relu(Linear(gw))) (5) In the formula, Relu is the activation function; Linear is the linear function; The input of the output layer is the reuse distance dis of each cache line, and the output is the eviction probability prob = {p ₁ , p ₂ , ..., p _W } of each cache line; wherein p _W represents the eviction probability of the Wth cache line in the cache; Among them, the eviction probability prob of each cache line is as follows: prob＝Sigmoid(dis) (6) In the formula, Sigmoid is the activation function. 4. The cache replacement system based on imitation learning according to claim 3, characterized in that: it also includes a neural network training module; The neural network training module is used to train the cache eviction prediction neural network of the cache replacement prediction module. 5. The cache replacement system based on imitation learning according to claim 1, wherein the step of the cache replacement module storing the current cache access request into the cache comprises: a1) determining whether the current cache is not full or whether the current cache access request is already in the cache; if so, directly placing the current cache access request in the cache or obtaining the current cache access request from the cache; otherwise, proceeding to step a2); a2) the cache replacement module retrieves the cache line eviction probability from the cache replacement prediction module and generates a cache line eviction strategy; a3) The cache replacement module evicts the cache line according to the cache line eviction policy, thereby storing the current cache access request in the cache. 6. The cache replacement system based on imitation learning according to claim 5, characterized in that the cache line eviction strategy is as follows: index=decend_sort(prob) (13) evict_index＝index(0) (14) Where prob represents the cache line eviction probability vector, decend_sort() is the descending sort function, index(0) represents the cache line with the highest eviction probability, evict_index is the eviction strategy, and index is the guidance function. 7. A method for using the cache replacement system according to any one of claims 1 to 6, characterized in that it comprises the following steps: s1) Build a cache replacement system based on imitation learning; s2) obtaining a cache access request sequence; s3) Determine whether the current cache is not full or whether the current access is in the cache. If so, directly put the current access into the cache or obtain the current cache access from the cache and go to step s9). Otherwise, go to step s4); s4) training a cache replacement prediction neural network of a cache replacement prediction module; s5) inputting the cache access request sequence into the trained cache replacement prediction neural network, calculating the cache line eviction probability, and transmitting it to the cache replacement module; s6) The cache replacement module determines whether the current cache is not full or whether the current cache access request is already in the cache. If so, the current cache access request is directly placed in the cache or obtained from the cache. Otherwise, the process proceeds to step s7); s7) the cache replacement module retrieves the cache line eviction probability from the cache replacement prediction module and generates a cache line eviction strategy; s8) the cache replacement module evicts the cache line according to the cache line eviction policy, thereby storing the current cache access request in the cache; s9) Obtain a new cache access request sequence and return to step s3).