CN107729263B - Replacement strategy of tree-structured improved LRU algorithm in high-speed Cache - Google Patents

Abstract

The invention discloses a replacement strategy of a tree-structured improved LRU algorithm in a high-speed Cache, which is based on a program locality principle and adopts the replacement strategy of the tree-structured improved LRU algorithm to improve the replacement efficiency and the hit rate. In the invention, when the cache needs to be updated, the decoding circuit judges the valid bit, when the valid bits are all 1, the value of the replacement state memory is decoded according to the improved LRU algorithm of the tree structure to determine the replaced line, and when the valid bits are not all 1, the line needing to be replaced is obtained according to the priority decoding circuit, thereby completing the whole replacement process. The replacement method can further improve the data replacement hit speed of the high-speed Cache and improve the performance of the high-speed Cache while completing data read-write operation.

Description

A Replacement Strategy of an Improved LRU Algorithm with Tree Structure in High-speed Cache

technical field

The invention relates to the technical field of embedded microprocessor design, in particular to a replacement strategy of an improved LRU algorithm with a tree-like structure in a high-speed cache, and further relates to a method for improving how an embedded microprocessor core can quickly read and write data from the high-speed cache .

Background technique

One of the design problems of embedded microprocessors is that the high-speed operating frequency of embedded microprocessors is very different from the low-speed read/write speed of off-chip memory, which limits the performance and efficiency of embedded microprocessors to a large extent. In modern microprocessors, it has become an effective solution to narrow the speed gap between memory and embedded microprocessors by designing one or more levels of caches between the embedded microprocessor core and off-chip memory to form a multi-level storage system. However, when the cache is working, it is prone to misses. When a cache miss occurs, a line is read from the main memory and stored in the cache. At this time, if there is no free line in the cache, you need to select a line to replace it as a replacement object. The replacement efficiency of different replacement algorithms is greatly different, and the resources occupied by different algorithms are also different. The current mainstream replacement algorithm is the LRU (Least Recently Used) algorithm, that is, the algorithm that has not been used for the longest time recently. The LRU algorithm is a statistical method. According to the usage of each way, the line that has been used the least recently is counted and then used as a replacement. This method can better reflect the locality principle of the program and has a good hit rate, but it is more difficult to implement in hardware than other conventional algorithms and consumes more resources. This results in slower replacement and increased system power consumption.

Therefore, it is urgent to propose a replacement strategy of the improved LRU algorithm based on the principle of program locality and adopting the idea of tree structure to improve the replacement efficiency and hit rate.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a replacement strategy of an improved LRU algorithm with a tree structure in a high-speed cache in order to solve the above-mentioned defects in the prior art.

The purpose of the present invention can be achieved by adopting the following technical solutions:

A replacement strategy for a tree-structured improved LRU algorithm in a high-speed Cache, the replacement strategy includes the following steps:

S1. Complete the division of the four-way group connection mapping method Set and line;

S2. Set up a register stack for each of the divided Sets, the capacity of which is the Set number n of the high-speed Cache, and the register stack records the recently accessed Set_a and the longest unvisited Set_b from the top of the stack to the bottom of the stack in turn;

S3. When a certain Set is accessed, the elements in the stack above the Set number move down one line in turn, and the accessed Set number is pushed to the top of the stack, and the elements in the stack are rearranged through the above operations. Get the Set number that is rarely used recently;

S4. Use a tree-like structure-based method in the recently used Set number to find out that the line in a specific road needs to be replaced;

S5. Read out the data of a line from the main memory and store it in the high-speed Cache to complete the data replacement.

Further, the step S4 is specifically as follows:

S401. Design a three-bit register in Set, denoted as status[2:0], and the update method is: replace Way0 when status[2:0]=00×, replace Way1 when status[2:0]=01× , Way2 is replaced when status[2:0]=1×0, and Way3 is replaced when status[2:0]=1×1, where “×” means keep the original value;

S402. When an access loss occurs, first determine the value of the status[2] bit in the register status[2:0], and when status[2]=0, determine the value of status[1], if status[1]= When 0, replace Line in Way0, if status[1]=1, replace Line in Way1;

When status[2]=1, judge the value of status[0], if status[0]=0, replace Line in Way2, and if status[0]=1, replace Line in Way3.

Further, the step S1 is specifically as follows:

S101. Divide the cache into 4 equal parts according to the space size of the Cache, and obtain 4 ways, that is, 4 ways, which are way1, way2, way3 and way4 respectively;

S102, divide the main memory into equal parts according to the size of each way to obtain Page 0～Page n;

S103, re-equally divide each way in the cache and each Page in the main memory to obtain each line, which are respectively line0-linen;

S104 , the same line in all the ways is divided into a Set, and after the setting of the Set is completed, the division of the four-way group connection mapping mode Set and the line is completed.

Compared with the prior art, the present invention has the following advantages and effects:

1) Based on the principle of program locality, the present invention adopts the replacement strategy of the improved LRU algorithm with tree structure to improve replacement efficiency and hit rate. In the present invention, when the cache needs to be updated, the decoding circuit will judge the valid bits, and when the valid bits are all 1, it will decode the value of the replacement state memory according to the improved LRU algorithm of the tree structure, and decide The replaced line is output. When the valid bits are not all 1, the line to be replaced will be obtained according to the priority decoding circuit, thereby completing the entire replacement process.

2) The present invention completes the replacement of pages in the cache, and uses a parallel judgment circuit in the decoding circuit to complete the decoding, which can significantly improve the replacement speed of the cache.

Description of drawings

Fig. 1 is the division of Set and line in the connection of four-way group among the present invention;

Fig. 2 is that the register stack method in the present invention obtains the Set number that is not often used in the near future;

Fig. 3 is the LRU algorithm replacement strategy flow chart of tree structure in the present invention;

Fig. 4 is the structural diagram of the state module in the present invention;

Fig. 5 is the workflow of decoding circuit in the present invention;

Fig. 6 is the replacement circuit when part of line is idle in the present invention;

Fig. 7 is the parallel comparison circuit of the LRU algorithm based on tree structure in the present invention;

Fig. 8 is the structure of the coding circuit in the present invention.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

Example

In order to overcome the shortcomings and deficiencies of the LRU replacement algorithm in the high-speed cache, this embodiment provides an efficient, fast and high hit rate replacement method, which can further improve the data replacement hit speed of the high-speed cache while completing data read and write operations. , to improve the performance of high-speed Cache.

A replacement strategy for an improved LRU algorithm with a tree-like structure specifically includes the following steps:

S1. Complete the division of the four-way group connection mapping mode Set and line.

The steps of dividing the four-way group connection mapping mode Set and line in this step S1 are as follows:

S101. Divide the cache into 4 equal parts according to the design (the space size of the Cache) to obtain 4-way (4-way), which are way1, way2, way3 and way4 respectively;

S102: Divide the main memory into equal parts according to the size of each way to obtain Page 0 to Page n;

S103, re-equally divide each way in the cache and each Page in the main memory to obtain each line (line 0～line n);

S104 , the same lines in all the ways are divided into a Set (group, for example, line 0 in way 0 and way 1 forms Set_0, and there are Set_0 to Set_n in total). After completing the setting of the Set, the division of the four-way group connection mapping method Set and line is completed, as shown in Figure 1 after the division is completed.

S2. Set up a register stack for each divided Set, the capacity of which is the Set number n of the high-speed Cache, and the register stack sequentially records Set_a that has been accessed recently and Set_b that has not been accessed for the longest time from the top of the stack to the bottom of the stack.

S3. When a certain Set is accessed, the elements in the stack above the Set number move down one line in turn, and the accessed Set number is pushed to the top of the stack, thus realizing the rearrangement of the elements in the stack, and obtaining Set number that is not frequently used recently.

S4. Use a tree-like structure-based method in the recently used Set number to find out which line in the route needs to be replaced.

The step S4 is specifically as follows:

S401. Design a three-bit register in Set, denoted as status[2:0], and the update method is: replace Way0 when status[2:0]=00×; replace Way1 when status[2:0]=01× ; Replace Way2 when status[2:0]=1×0; Replace Way3 when status[2:0]=1×1. (“×” means keep the original value), the truth table is shown in Table 1, in order to realize further records for the recent visit;

Table 1. LRU algorithm update method of tree structure

S402. When an access loss occurs, first determine the value of the status[2] bit in the register status[2:0]. When status[2]=0, the value of status[1] is judged. If status[1]=0, replace Line in Way0; if status[1]=1, replace Line in Way1. When status[2]=1, the value of status[0] is judged. If status[0]=0, replace Line in Way2, and if status[0]=1, replace Line in Way3.

S5. Read out the data of a line from the main memory and store it in the high-speed Cache to complete the data replacement.

In the actual circuit design, the replacement status (replace statues) of each line of the cache is composed of an SRAM or a set of registers, and the structure is shown in Figure 4. In the state module circuit, it consists of an encoding circuit circuit and a decoding circuit.

1. Decoding circuit

The main function of the decoding circuit is to judge whether each line has been completely filled with data according to the valid bits, and to decode the replacement state. When the cache needs to be updated, the decoding circuit determines the line for replacement from the following two situations:

(1) The valid bits are not all 1. This shows that there are still free lines in the Set. At this time, the decoding circuit will use the line whose valid bit is not 1 for data replacement. The left half of Figure 5 is the flow chart when part of the line is idle. The specific flow is as follows:

T1, first judge the valid bit valid[0], if valid[0] is 0, replace way0; otherwise, enter T2;

T2, judge the valid bit valid[1], if valid[1] is 0, replace way1; otherwise, enter T3;

T3, judge the valid bit valid[2], if valid[2] is 0, replace way2; otherwise, replace way3;

This is a kind of priority decoding circuit in hardware, and the truth table is as follows:

Table 2 Partial truth table for alternate circuits when line is idle

Therefore, the minimum term is obtained according to the truth table, and the optimized gate-level circuit is designed. As shown in Figure 6, the logic expression of the gate-level circuit is:

rep[0] = ~valid[0];

rep[1]=valid[0]&(~valid[1]);

rep[2]=valid[0]&valid[1]&(~valid[2]);

rep[3]=valid[0]&valid[1]&valid[2];

(2) All valid bits are 1. In this case, all lines have been used. The decoding circuit will decode the value of the replacement state memory according to the idea of the tree structure in FIG. 3 to determine the replaced line.

When all lines have been used, the decoding circuit determines to replace each bit of the state memory. However, if each bit is judged one by one, the delay of the path will inevitably increase. If the parallel judgment method is used, the speed of judgment can be accelerated, thereby reducing the delay of the path. Therefore, the present invention adopts the circuit design as shown in Figure 7. Parallel judgment circuit to complete the design of the decoding circuit.

2. Encoding circuit

The encoding circuit encodes the hits and replacements of each way, and rewrites the contents of the replacement state memory. When the cache accesses a certain way (whether it is read-write after hit or replacement after miss), the encoding circuit encodes the information that has recently accessed the cache according to the LRU algorithm of the tree structure, and records it in the register, as shown in Figure 8. The structure of the encoding circuit.

The above-mentioned embodiments are preferred embodiments of the present invention, but the embodiments of the present invention are not limited by the above-mentioned embodiments, and any other changes, modifications, substitutions, combinations, The simplification should be equivalent replacement manners, which are all included in the protection scope of the present invention.

Claims (2)

1. A replacement strategy of a tree-structured modified LRU algorithm in a high-speed Cache is characterized by comprising the following steps:

s1, completing the division of the Set and line of the four-way group connection mapping mode, wherein the step S1 is as follows:

s101, dividing the Cache into 4 equal parts according to the space size requirement of the Cache to obtain 4 ways, namely 4 ways which are respectively way1, way2, way3 and way 4;

s102, equally dividing the main memory according to the size of each path to obtain pages 0-Page n;

s103, equally dividing each way in the cache and each Page in the main memory again to obtain each line which is line 0-line n respectively;

s104, dividing the same lines in all the ways into a Set, and finishing the Set setting to finish the Set of the four-way group connection mapping mode and the line division;

s2, setting a register stack for each divided Set, wherein the capacity of the register stack is the Set number n of the high-speed Cache, and the register stack sequentially records the most recently accessed Set _ a and the least recently accessed Set _ b from the stack top to the stack bottom;

s3, when a Set is accessed, the elements in the stack above the Set number move downwards one row in sequence, the accessed Set number is pressed into the top of the stack, and the elements in the stack are rearranged through the operation to obtain the Set number which is not frequently used in the near term;

s4, finding out the line in a specific path to be replaced by adopting a method based on a tree structure in a recently infrequently used Set number;

and S5, reading out the data of one line from the main memory and storing the data in the high-speed Cache to finish data replacement.

2. A replacement policy of a tree-structured LRU algorithm in a high-speed Cache according to claim 1, wherein said step S4 is as follows:

s401, designing a three-bit register in Set, recording the register as status [2:0], and updating the register in such a Way that WAy0 is replaced when status [2:0] is 00 x, WAy1 is replaced when status [2:0] is 01 x, WAy2 is replaced when status [2:0] is 1 x 0, and Way3 is replaced when status [2:0] is 1 x 1, wherein x represents that the original value is kept;

s402, when an access miss occurs, first, the value of status [2] bit in the register status [2:0] is determined, when status [2] is equal to 0, the value of status [1] is determined, when status [1] is equal to 0, Line in Way0 is replaced, and when status [1] is equal to 1, Line in Way1 is replaced;

when status [2] is equal to 1, the numerical value of status [0] is determined, and when status [0] is equal to 0, the Line in Way2 is replaced, and when status [0] is equal to 1, the Line in Way3 is replaced.

Images