CN103729309A - Method for cataloging Cache consistency - Google Patents

Abstract

The invention provides a directory Cache consistency method, the implementation process of which is: combining the limited directory and the full mapping directory, setting a dual-protocol two-level directory storage structure on the basis of using the memory Cache; The replacement algorithm between is guaranteed using a pseudo-least recently used algorithm weighted by the number of shares. Compared with the existing technology, this directory cache consistency method solves the problems that the full map directory occupies too much storage overhead, the limited directory will be limited by the overflow of directory items, and the time validity of the chain directory is low. It is practical. Strong, easy to promote.

Description

A Directory Cache Consistency Method

technical field

The invention relates to the field of computer technology, more specifically to a directory Cache consistency method.

Background technique

In a multilevel network, the cache directory holds information about where copies of cache lines reside to support cache coherency. The main difference between the various directory approaches is how the directory maintains information and what information it stores. The first directory scheme is to use a central directory to store copies of all cache directories, and the central directory can provide all the information needed to ensure consistency. Therefore, it is very large and must be retrieved using an associative method, similar to the catalog of a single cache. Large-scale multiprocessor systems adopting a central directory will have two disadvantages, conflict and long retrieval time. The distributed directory scheme was proposed by Censier and Feautrier. In the distributed directory, each memory module maintains its own directory, which records the state and current information of each memory block, where the state information is local, and the current information indicates which caches have a copy of the memory block . Different types of catalog methods can be divided into three categories: full map catalog, limited catalog and chain catalog. Among them, the full map directory occupies too much storage overhead, the limited directory is limited by the overflow of directory items, and the time validity of the chain directory is low. Based on this, the present invention provides an improved directory Cache consistency method, which combines limited directories and full-mapped directories to solve the above problems.

Contents of the invention

The technical task of the present invention is to solve the deficiencies of the prior art, and provide a directory Cache consistency method that is simple to operate, easy to realize and improved.

The technical scheme of the present invention is realized in the following manner, and the specific implementation process of this kind of directory Cache consistency method is:

1. Set up a two-level directory storage structure, that is, a full-map directory and a limited directory. The full-map directory stores data related to each block in the global memory, so that each cache in the system can store a copy of any data block at the same time. Each directory entry contains N pointers, and N is the number of processors in the system; the difference between the limited directory and the full mapping directory is that each directory entry contains a fixed number of pointers;

2. Pseudo-least-recently-used algorithm weighted by the shared number used between the memory layer and the memory Cache layer: assuming that each directory entry of the memory layer uses Q pointers, only the cache lines whose shared number is less than Q are used when replacing This algorithm performs replacement; when the shared numbers of all cache lines in the memory Cache are greater than Q, the cache line with the smallest shared number is replaced out of the memory Cache and invalidated accordingly.

In the two-level directory storage structure, there is a processor bit and a dirty bit in the directory entry realized by the full mapping method: the former indicates the existence or non-existence of the cache block of the corresponding processor; if the latter is " 1", and one and only one processor bit is "1", then the processor can write to the block. Each block in the cache has two status bits: one bit indicates whether the block is valid; Another bit indicates whether writing is allowed for valid blocks.

The details of the pseudo-least recently used algorithm weighted by the sharing number are as follows:

1) If the cache line is in the memory Cache, execute 2, otherwise execute 5;

2) Read data from the memory Cache;

3) If it is a new shared node, execute 4, otherwise execute 14;

4) Modify the Cache directory item, go to 14;

5) Read data from memory;

6) If it is a new shared node, execute 7, otherwise execute 9;

7) If the memory directory item overflows, execute 8, otherwise execute 9;

8) Record overflow items;

9) If there are free directory entries in the Cache, execute 10, otherwise execute 11;

10) Add the data to the Cache and modify the Cache directory entry according to the storage directory entry, skip to 14;

11) If there are directory entries in the Cache with a shared number less than Q, execute 12, otherwise execute 13;

12) Use the LRU algorithm to select a piece of data in the cache line whose shared number is less than Q to replace the Cache, and execute 10;

13) Select a cache line with the smallest share to perform the corresponding processing of shared invalidation, go to step 10;

14) Done.

The beneficial effect that the present invention produces compared with prior art is:

A directory cache consistency method of the present invention combines the limited directory and the full mapping directory, and then uses the Cache consistency method of the two-level directory, which solves the problem that the full mapping directory takes up too much storage overhead, and the limited directory will be affected by directory items. Overflow restrictions, low time validity of chained directories, etc. The limited directory is used in the storage layer. Since a single directory entry of the limited directory occupies a small space, it can save a lot of storage space in the storage layer that requires a large number of directory entries. At the same time, the full-map directory is used in the memory cache layer, and the cache capacity is limited, so even if a single directory entry occupies a large space, the total occupied space will not be much. It not only solves the problem of directory entry overflow of limited directories, but also the most frequently used data and its directory entries are always in the memory cache layer using the full map directory, so the access speed of this two-level storage structure can be compared with that of the first-level memory That is, the memory Cache has the same speed, strong practicability, and easy promotion.

Description of drawings

Accompanying drawing 1 is a schematic diagram of a two-level directory storage structure.

Accompanying drawing 2 is the pseudo-least recently used algorithm flow chart of sharing number weighting in the present invention.

Detailed ways

A directory Cache consistency method of the present invention will be described in detail below in conjunction with the accompanying drawings.

As shown in accompanying drawing 1, the present invention proposes a kind of directory Cache consistency method, and its specific implementation process is:

Set up a two-level directory storage structure, combine the limited directory and the full-map directory, and then use the Cache consistency method of the two-level directory to solve the excessive storage overhead of the full-map directory. block-related data, so that each cache in the system can simultaneously store a copy of any data block, each directory entry contains N pointers, and N is the number of processors in the system. A limited directory differs from a full-mapped directory in that each directory entry contains a fixed number of pointers, regardless of the size of the system.

A replacement algorithm is used between the memory layer and the memory Cache layer, that is, the pseudo-least recently used LRU algorithm weighted by the shared number, so the cache lines whose shared number exceeds the limited number of directory pointers of the memory layer can be guaranteed to be in the memory Cache to realize utilization Relatively little storage space guarantees cache data coherency.

In the above two-level directory storage structure, there is a processor bit and a dirty bit in the directory entry implemented by the full mapping method: the former indicates the existence or non-existence of the cache block of the corresponding processor; if the latter is "1 ", and one and only one processor bit is "1", then the processor can write to the block. Each block of the cache has two status bits: one bit indicates whether the block is valid; the other bit indicates whether the valid block is allowed to be written. The cache coherency method must ensure that the status bits of the memory directory are consistent with the status bits of the cache. The limited directory method can alleviate the problem of too large directory. If there is a certain limit on the number of copies of any data block in the cache at the same time, then the size of the directory will not exceed a certain constant.

In the pseudo-least-recently-used LRU algorithm weighted by the sharing number, the cache lines whose sharing number exceeds the limited directory pointer number of the memory layer can be guaranteed to be stored in the storage Cache. Assuming that each directory entry of the memory layer uses Q pointers, only the cache lines whose share number is less than Q are replaced using the LRU replacement algorithm. Only when the sharing numbers of all cache lines in the memory Cache are greater than Q, a cache line with the smallest sharing number is replaced out of the memory Cache and invalidated accordingly. And this kind of directory entry overflow situation can be avoided by setting the size of the memory Cache appropriately.

As shown in accompanying drawing 2, the detailed content of the false least recently used algorithm of described shared number weighting is:

1) If the cache line is in the memory Cache, execute 2, otherwise execute 5.

2) Read data from the memory Cache.

3) If it is a new shared node, go to 4, otherwise go to 14.

4) To modify the Cache directory entry, go to 14.

5) Read data from memory.

6) If it is a new shared node, go to 7, otherwise go to 9.

7) If the memory directory entry overflows, execute 8, otherwise execute 9.

8) Log overflow items.

9) If there are free directory entries in the Cache, execute 10, otherwise execute 11.

10) Add the data to the Cache and modify the Cache directory entry according to the storage directory entry, skip to 14.

11) If there is a directory entry in the Cache with a shared number less than Q, go to step 12, otherwise go to step 13.

12) Use the LRU algorithm to select a piece of data in the cache line whose shared number is less than Q and replace it with the cache, and execute 10.

13) Select a cache line with the smallest share to perform the corresponding processing of share invalidation, go to step 10.

14) Done.

So far, an improved directory cache consistency method has been completely implemented. In terms of system performance, according to the granularity of the task, the time constraints of the application, and the proportion of read and write operations, reasonably set the size of the memory cache and cache line and use a suitable replacement algorithm to ensure a high hit rate for the memory cache . When a certain directory entry in the memory layer overflows, the directory entry information will be copied to the memory Cache layer. According to the replacement algorithm weighted by the number of shares, this directory information will always be kept in the memory cache until the number of shared nodes is less than the limited number of directory entry pointers Q in the memory layer, then it can be replaced out of the memory cache. Therefore, not only the directory item overflow problem of the limited directory is solved, but also the most frequently used data and its directory items are always in the memory cache layer using the full map directory, so the access speed of this two-level storage structure can be compared with the first Level memory, that is, memory Cache, has the same speed.

Of course, the present invention can also have other various embodiments, and those skilled in the art can make various corresponding changes and deformations according to the present invention without departing from the spirit and essence of the present invention, but these corresponding Changes and deformations should all belong to the protection scope of the claims of the present invention.

Claims (3)

1. A directory Cache consistency method is characterized in that its concrete implementation process is: 1. Set up a two-level directory storage structure, that is, a full-map directory and a limited directory. The full-map directory stores data related to each block in the global memory, so that each cache in the system can store a copy of any data block at the same time. Each directory entry contains N pointers, and N is the number of processors in the system; the difference between the limited directory and the full mapping directory is that each directory entry contains a fixed number of pointers; 2. Pseudo-least-recently-used algorithm weighted by the shared number used between the memory layer and the memory Cache layer: assuming that each directory entry of the memory layer uses Q pointers, only the cache lines whose shared number is less than Q are used when replacing This algorithm performs replacement; when the shared numbers of all cache lines in the memory Cache are greater than Q, the cache line with the smallest shared number is replaced out of the memory Cache and invalidated accordingly. 2. a kind of directory Cache consistency method according to claim 1, is characterized in that: in described two-level directory storage structure, there is a processor bit and a dirty bit in the directory entry that realizes with full mapping method: The former indicates the existence or non-existence of the cache block of the corresponding processor; if the latter is "1" and one and only one processor bit is "1", the processor can write to the block , each block of the cache has two status bits: one indicates whether the block is valid; the other indicates whether the valid block is allowed to be written. 3. a kind of directory Cache consistency method according to claim 2, is characterized in that: the detailed content of the false least recently used algorithm of described sharing number weighting is: 1) If the cache line is in the memory Cache, execute 2, otherwise execute 5; 2) Read data from the memory Cache; 3) If it is a new shared node, execute 4, otherwise execute 14; 4) Modify the Cache directory item, go to 14; 5) Read data from memory; 6) If it is a new shared node, execute 7, otherwise execute 9; 7) If the memory directory item overflows, execute 8, otherwise execute 9; 8) Record overflow items; 9) If there are free directory entries in the Cache, execute 10, otherwise execute 11; 10) Add the data to the Cache and modify the Cache directory entry according to the storage directory entry, skip to 14; 11) If there are directory entries in the Cache with a shared number less than Q, execute 12, otherwise execute 13; 12) Use the LRU algorithm to select a piece of data in the cache line whose shared number is less than Q to replace the Cache, and execute 10; 13) Select a cache line with the smallest share to perform the corresponding processing of shared invalidation, go to step 10; 14) Done.

Images