CN102354301A - Cache partitioning method - Google Patents

Abstract

The invention discloses a cache partition method, which includes the following steps: partitioning: logically divide the last level of cache into two areas of the same size, which are respectively partition one and partition two; adding cache data block information bits: adding The number of visits, using 2 bits to indicate the number of times the cache data block has been accessed; Add a historical access record table: add a historical access record table to record the cache data blocks that have been accessed, and each record is the cache data block Information flag bit and valid bit. Invented to partition the last-level cache to improve the efficiency of the last-level cache. For large-capacity caches, the cache data blocks with more access times are stored in the cache, and the cache data blocks with less access times are moved to the main memory, thereby improving the cache access hit rate and improving system performance.

Description

cache partition method

technical field

The invention belongs to the technical field of storage, and relates to a large-capacity cache and a cache partition method under a multi-core architecture.

Background technique

At present, the performance of most computer systems is largely determined by the average memory access latency. Improving the cache hit rate can reduce the number of memory accesses and improve system performance. The current processors all use a cache mechanism, and the function of the cache is mainly to alleviate the speed and performance mismatch between the adjustment processor and the low-speed main memory. The cache implements a hierarchical mechanism. Most current processors use three-level cache (L1, L2, L3), and the last level cache (L3) is close to the main memory. As the capacity of the last-level cache continues to increase, the corresponding management strategy must also be continuously improved to increase the utilization of the cache and reduce the number of accesses to the main memory.

Cache management strategies include insertion algorithms and replacement algorithms. The insertion algorithm is where a cache data block read into the cache from the main memory should be placed in the cache. The replacement algorithm is due to the limited capacity of the cache space. When a new cache block comes in, a cache data block in the cache needs to be moved from the cache to the main memory to make room for the new cache data block. The cache management strategy used by most processors today is the least recently used algorithm (LRU). LRU regards a group of caches as a linked list. When there is a new cache data block to be inserted into the cache, the cache data block at the end of the table is moved to the main memory, and other cache data blocks in the table are moved back accordingly. A location to place new cached data blocks at the table header. During the cache access process, if a cache data block is hit, the LRU algorithm will move the cache data block to the header position. The LRU algorithm is very effective for managing small-capacity caches, but it is somewhat inefficient for managing large-capacity caches. The current last-level cache has a relatively large capacity. How to manage this large-capacity cache is a problem for many scientific researchers. A question everyone is thinking about. Therefore, it is necessary to conduct research to provide a method to solve the existing problems.

Contents of the invention

The purpose of the embodiments of the present invention is to provide a cache partition method, which improves the cache access hit rate and system performance.

The embodiment of the present invention is achieved in this way, a cache partition method, comprising the following steps:

Partition: logically divide the last level cache into two areas of the same size, namely Partition 1 and Partition 2;

New cache data block information bit: increase the number of access times, and use 2 bits to indicate the number of times the cache data block is accessed;

New historical access record table: Add a new historical access record table to record the cached data blocks that have been accessed, and each record is the information flag bit and valid bit of the cached data block.

Further, the cache configurations of partition 1 and partition 2 are the same, and partition 1 stores cache data blocks that have not been accessed; while partition 2 stores cache data that has been accessed before but has been moved to the main memory piece.

Further, the information bit of the newly added cached data block is an increase of the number of access times, represented by 2 bits.

Further, each cache data block has some information bits, mainly including a flag bit, a valid bit, an LRU bit, a read/write bit, and an access count bit.

Further, the historical access record table stores the access records of the replaced cache data blocks, and each record is the information flag bit and valid bit of the cache data block.

Further, the number of data blocks that can be recorded in the historical access record table is the same as the number of cache data blocks that can be accommodated by the partition.

Further, the historical access record table is used to store the flag bits of the cache data blocks that were replaced to the main memory before. When a cache data block is to be moved to the main memory, its flag bits will be stored in this table.

Further, when a cache data block is read into the cache from the main memory, a table lookup operation is required, and if the mark bit of the cache data block is in the record table, it is stored in Partition 2 and stored in The effective bit of the record in the record table is set to 0, otherwise it is stored in partition one.

Further, the record table adopts a first-in-first-out replacement method. When the tag bit of a cache data block is to be stored in the table, first look up whether there is a record with a valid bit of 0 in the table, and if so, then Store these flag bits into the record whose effective bit is 0, and set the effective bit to 1, otherwise, set the flag bit of the last record in the table to the flag bit that needs to be stored

The present invention partitions the last-level cache to improve the utilization efficiency of the last-level cache. For large-capacity caches, the cache data blocks with more access times are stored in the cache, and the cache data blocks with less access times are moved to the main memory, thereby improving the cache access hit rate and improving system performance.

Description of drawings

Figure 1 is a flow diagram of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

The cache partition method of the present invention divides the large-capacity cache into two areas of the same size, which is a cache management strategy based on the least recently used strategy. The two partitions respectively store data blocks of different natures, and remove less accessed data blocks from the cache, leaving more space for data blocks with more access times, so as to improve the efficiency of the cache. It uses a historical access record table to record the accessed cache data blocks. When it is necessary to read the cache data block from the main memory into the cache, it is necessary to look up this historical access record table. If the tag bit information of this cache data block is found in this table, then this cache data block is placed in partition two, otherwise it is placed in partition one.

Referring to Figure 1, the cache partition method of the present invention includes the following steps:

Partition: logically divide the last level cache into two areas of the same size, namely Partition 1 and Partition 2;

New cache data block information bit: increase the number of access times, and use 2 bits to indicate the number of times the cache data block is accessed;

New historical access record table: Add a new historical access record table to record the cached data blocks that have been accessed, and each record is the information flag bit and valid bit of the cached data block.

Wherein, the cache configurations of the partition one and partition two are the same, and they are all the same in terms of group association and access delay, and all use the least recently used (LRU) management strategy; The cache data blocks of partition 2 store the cache data blocks that have been accessed before but moved to the main memory.

The advantage of being divided into two smaller-capacity partitions is that the access latency of a small-capacity cache is smaller, because the cache access latency is proportional to its capacity, that is, the larger the capacity, the higher the access latency, and the smaller the capacity, the lower the access latency. Just small. Partition 1 stores cache data blocks that have not been accessed, and these data blocks are considered to be less accessed. Partition 2 stores the cache data blocks that have been accessed before but moved to the main memory. These data blocks are considered to be accessed more often. In this way, data blocks that are frequently accessed and data blocks that are accessed less frequently are stored separately to reduce the access delay of the cache.

The information bit of the newly added cache data block is an increase in the number of times of access, which is represented by 2 bits. Each cache data block has some information bits, mainly including mark bits, valid bits, LRU bits, and read and write bits. The current cache data blocks all have information bits, and different information bits are required according to different cache replacement algorithms. For example, a 16-way set associative cache adopts the least recently used replacement algorithm (LRU), then each cache data block needs 4 bits to store LRU information. This creation increases the number of access times on the original basis, expressed by 2 bits, to record the number of times the cache data block is accessed, referred to as UC.

When a new cache data block is read into the cache (partition 1 or partition 2) from the main memory, its UC value is set to 0, and other information bits are set according to the original method. During the cache access process, if a cache data block is hit and its UC value is less than 3, then its UC value is increased by 1. This is because the UC value is represented by 2 bits, and its value range is 0-3.

Due to the limited cache capacity, when a cache data block replacement operation is required, assuming that the current new cache data block will be stored in partition 1 as an example, the LRU strategy first selects the cache data block with the largest LRU value in partition 1. The cache data block is called victim for short. Then, analyze the victim's UC value. If the UC value is less than 2, then store the victim's mark bit in the historical access record table and move it to the main memory. Otherwise, set its UC bit to 0 and move it to partition 2. At this time, the cache data block with the largest LRU value in partition 2 needs to be replaced. This cache data block is called victim for short. Similarly, it is necessary to check the UC value of the victim. If it is less than 2, it will be directly moved to the main memory, and the mark bit will be stored in the historical access record table, otherwise its UC bit will be cleared and moved to partition one. Repeat this until a cache data block is found, its LRU value is the largest and its UC value is less than 2, then this cache data block is moved to the main memory and its mark bit is stored in the historical access record table.

The newly added historical access record table is a newly added historical access record table, which records the accessed cache data blocks. This historical access record table stores the access records of the replaced cache data blocks, and each record is the information flag bit and valid bit of the cache data block. The number of data blocks that can be recorded in the record table is the same as the number of cache data blocks that the partition can hold. For example, if a 2MB cache is divided into two 1MB partitions, and the cache data block size is 64B, then the number of cache data blocks that can be accommodated in each partition is 16K, so the capacity of this table is 16k records. Here k means 2^10, M means 2^20, and B means byte. The group associative of this record table is the same as the group associative of the partition, a 16-way group associative cache, then this table is also a 16-way group associative.

The historical access record table is used to store the tag bits of the cache data blocks that were replaced to the main memory before. When a cache data block is to be moved to main memory, its flag will be stored in this table. When a cache data block is read into the cache from the main memory, a table lookup operation is required. If the mark bit of this cache data block is in the table, it is stored in partition two and the effective bit of its record in the table is set to 0, otherwise it is stored in partition one.

The record table adopts a first-in first-out replacement strategy. When the flag bits of a cache data block are to be stored in the table, first look up whether there is a record with an effective bit of 0 in the table, and if so, store these flag bits into the record with an effective bit of 0, and Set the valid bit to 1, otherwise, set the flag bit of the last record in the table to the flag bit that needs to be stored.

Taking the last level cache (L3) of a processor as an example, the cache configuration is as follows: capacity is 2MB, 16-way set associative, 4 bits represent LRU value, cache data block size is 64B, adopts LRU management Strategy. Divide it into two partitions A and B. The configuration of partitions A and B is as follows: capacity is 1MB, 16-way set associative, 4 bits represent LRU value, cache data block size is 16B, and LRU management strategy is adopted. The history record table contains 16K records, 16-way group associative, adopts first-in-first-out management strategy. (unit k means 2^10), M means 2^20, unit B means byte). A cache data block D is read from the main memory into the cache, and the flag bit of D is first searched in the record table. If found, the valid bit of the corresponding record is set to 0, and then D is stored in partition B, otherwise D is stored in partition A, regardless of which partition it is stored in, the UC value is set to 0. Taking the assumption that it is stored in partition A as an example, first select the cache data block victim with an LRU value of 15 in A. Then test the victim's UC value, if it is less than 2, store the victim's mark bit in the history table. Otherwise, set its UC value to 0 and move it to partition B. At this time, you need to select a cache data block victim with an LRU value of 15 in partition B, and then test the victim's UC value. The loop repeats until a cache data block victim is found, its LRU value is 15, and its UC value is less than 2. In this way, the victim's mark bit is stored in the historical access record table and the victim is moved to the main memory.

The creation of the present invention is mainly aimed at large-capacity cache. By improving the cache management strategy, the cache data blocks with more access times are stored in the cache, and the cache data blocks with less access times are moved to the main memory, thereby improving cache access. Hit rate, improve system performance.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.

Claims (9)

1. a cache partitions method is characterized in that, comprises the steps:

Subregion: logically the afterbody buffer memory is divided into two identical zones of size, is respectively subregion one and subregion two;

Newly-increased caching data block information bit: increase by the access times position, represent that with 2 bits caching data block is by access times;

Newly-increased history access record table: newly-increased history access record table, the caching data block that record was visited, every information flag position and significance bit that record is exactly a caching data block.

2. cache partitions method as claimed in claim 1 is characterized in that: said subregion one is identical with the cached configuration of subregion two, and what subregion one was deposited is the caching data block of not visited; And being visited before that subregion two is deposited still is moved to the caching data block in the main memory.

3. like claim 1 and 2 described cache partitions methods, it is characterized in that: said newly-increased caching data block information bit is to increase by the access times position, representes with 2 bits.

4. cache partitions method as claimed in claim 3 is characterized in that: each caching data block all has some information bits, mainly comprises marker bit, significance bit, LRU position, read-write position and by the access times position.

5. cache partitions method as claimed in claim 4 is characterized in that: the storage of said history access record table be the Visitor Logs of the caching data block that is replaced away, every information flag position and significance bit that record is exactly a caching data block.

6. cache partitions method as claimed in claim 5 is characterized in that: recordable data block bar number is the same with the open ended caching data block number of subregion in the said history access record table.

7. cache partitions method as claimed in claim 6; It is characterized in that: said history access record table is to be used for storing the marker bit that is replaced to the caching data block of main memory before; When a caching data block will be moved in the main memory, its marker bit will be stored in this table.

8. cache partitions method as claimed in claim 7; It is characterized in that: when a caching data block when main memory is read into the buffer memory; Need carry out table lookup operation; If the marker bit of this caching data block is in record sheet; Then it is stored in the subregion two and with the significance bit of its record in record sheet and be arranged to 0, otherwise be stored in the subregion one.

9. cache partitions method as claimed in claim 8; It is characterized in that: what said record sheet adopted is the replacement method of first in first out; When the marker bit of a caching data block will be deposited in the table; Whether elder generation has significance bit in the look-up table is 0 record; If have, then these marker bits are deposited into this significance bit and are in 0 the record, and significance bit is arranged to 1; Otherwise, the marker bit of the last item record in the table is arranged to the marker bit that needs are stored.

Images