CN103729309B - A kind of catalogue Cache coherence methods - Google Patents

Abstract

The present invention provides a kind of catalogue Cache coherence methods, and its implementation process is：With reference to limited catalogue and full mapping directory, the two-stage catalogue storage organization of double agreements is set on the basis of memory Cache has been used；And the replacement algorithm between memory layer and memory Cache layers is ensured using a kind of pseudo- LRU of shared number weighting.Compared to the prior art a kind of catalogue Cache coherence methods, solve full mapping directory and take excessive storage overhead, and limited catalogue can be limited by directory entry spilling, practical, it is easy to promote the problems such as the available time of chain type catalogue is relatively low.

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 description

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 kind of catalogue Cache coherence methods, it is characterised in that it implements process and is：

The first, two-stage catalogue storage organization, i.e., full mapping directory and limited catalogue are set, wherein the storage of full mapping directory is deposited with the overall situation The relevant data of each block in reservoir so that each cache in system can simultaneously store the copy of any data block, The directory entry of each full mapping directory includes N number of pointer, and N is the number of processor in system；Limited catalogue and full mapping directory Difference is each of which directory entry pointer containing fixed number；

The pseudo- LRU of the shared number weighting for the 2nd, being used between memory layer and memory Cache layers：It is assumed that Each directory entry of memory layer uses Q pointer, then only use the algorithm to sharing cache line of the number less than Q when replacing It is replaced；When the shared number of all cache lines in memory Cache is all more than Q, the minimum high speed of shared number is delayed Row is deposited to replace out memory Cache and carry out corresponding calcellation treatment.

2. a kind of catalogue Cache coherence methods according to claim 1, it is characterised in that：Described two-stage catalogue is deposited In storage structure, there are a processor position and a dirty position in the directory entry with the realization of full mapping method：The former respective handling The cacheline of device is presence or absence of state；The latter if " 1 ", and have one also only one of which processor position be " 1 ", then the processor write operation can be just carried out to the block, each block of cache has two mode bits：One expression Whether block is effective；Another one represents whether active block allows to write.

3. a kind of catalogue Cache coherence methods according to claim 2, it is characterised in that：The shared number weighting The detailed content of pseudo- LRU is：

1）If cache line is in memory Cache, 2 are performed, otherwise perform 5；

2）Data are read from memory Cache；

3）If new shared node, then 4 are performed, otherwise perform 14；

4）Modification Cache directory entries, perform 14；

5）Data are read from memory；

6）If new shared node, then 7 are performed, otherwise perform 9；

7）If memory directory entry overflows, 8 are performed, otherwise perform 9；

8）Record overflow entry；

9）If available free directory entry in Cache, performs 10,11 are otherwise performed；

10）Data are added into Cache and Cache directory entries are changed according to memory directory entry, skip to 14；

11）If there is shared directory entry of the number less than Q in Cache, 12 are performed, otherwise perform 13；

12）Select a block number according to Cache is replaced out using lru algorithm in shared cache line of the number less than Q, perform 10；

13）Minimum cache line is shared in selection one carries out the respective handling of shared calcellation, performs 10；

14）Complete.