JPH0711791B2 - Cache memory system - Google Patents

Description

[Detailed Description of the Invention] [Overview] Cache read hit / miss hit is determined for the cache memory during block replacement, and data is output to the CPU when hit. However, the CPU standby time is shortened by keeping the standby state when there is a miss hit without shifting the CPU to the standby state. At the same time, the addresses being replaced are compared, and if they match, the data is output to the CPU, and the address of the next CPU cycle following fetch bypass and the address of the data being replaced by the block are also output. , And if they match, output the data to the CPU
It reduces the waiting state and improves the CPU efficiency.

[Industrial application field]

The present invention relates to a cache memory system that replaces in blocks, and more particularly to a cache memory system that can process a fetch access request from a CPU even during block replacement.

[Conventional technology]

As a means to improve CPU performance, increase the parallel processing unit (for example, 8bit → 16bit → 32bit → 64bit), adopt RISC type architecture, and speed up operating clock and shorten internal cycle and bus cycle. Is a general tendency.

In addition, in the memory, the accessible address space is also increasing, and high integration (for example, 256Kbit → 1Mbit → 4M
bit) is being addressed. On the other hand, for dynamic memories, it is becoming difficult for faster access times to follow the tempo of shortening the CPU bus cycle. Therefore, a static memory is used instead of the dynamic memory, but constructing with a static memory of a large capacity memory system is not feasible in terms of cost, integration, and power consumption. .

Therefore, a memory interleaved memory system was used in which the access time was apparently shortened by dividing the dynamic memory into two or more groups and alternately accessing each block. However, depending on the program configuration, I was not able to fully utilize the performance I had.

Therefore, a memory hierarchy system that combines static memory with high speed / expensive / low integration and dynamic memory with low speed / inexpensive / high integration was considered.

The cache memory is one of the methods for realizing this memory hierarchy, and it uses the access time of the main memory and the CPU.
It is a small-capacity high-speed memory placed between the two to fill the gap in the cycle time.

The principle of this cache memory is that the data referenced at a certain time is likely to be referenced again in the near future, and the temporal locality of the memory reference of the program, the data near the referenced data can be referenced. It is based on two localities of spatial locality, such as large locality. By using this locality to copy the referenced data and the data in the vicinity from the main memory to the cache memory, most of the access to the main memory can be done to the cache memory, and the efficiency can be improved. It becomes possible to improve.

The fetch algorithm is a method that determines at what point in time a block read or the like is performed to copy data from the main memory to the cache memory. The method is roughly divided into a demand fetch method and a prefetch method.

In the demand fetch method, the contents of the main memory are transferred to the cache memory when a certain block is needed. On the other hand, in the prefetch method, in addition to the demand fetch method, the required block is predicted and transferred to the cache memory in advance. As a prediction method, there is often a method of prefetching a block at an address next to the referenced block. Regarding the fetch algorithm by the demand fetch method, in order to make it possible to continue the operation of the CPU even during the transfer from the main memory to the cache memory, the replace transfer is started from the data accessed by the CPU and the data is transferred. At the same time as the data is fetched to the cache memory, the data is also handed over to the CPU to restart the operation of the CPU, and then the contents of the remaining blocks are fetched from the main memory. I was trying.

[Problems to be Solved by the Invention]

In a conventional cache memory system that replaces data in block units, after fetch bypass is completed,
If the CPU made an access before the replacement was completed, it was necessary to shift to the standby state, which was a problem in processing efficiency. This tended to be more pronounced as the block size increased.

It is an object of the present invention to process fetch access from the CPU even during the block replacement period and reduce the chance of the CPU entering the standby state as much as possible.

[Means for Solving the Problems]

According to the present invention, the fetch address from the CPU is processed even when the cache memory is performing block replacement. Therefore, a portion (way) which can be read in the cache memory regardless of the replacement is accessed,
If there is a hit, that data is output to the CPU, and if the address of the replace data during block transfer and the fetch address are compared and they match, the data at that address is output.
It is output to the CPU.

FIG. 1 shows the principle configuration of the invention in an exemplary way. For simplicity, only the fetch bypass control system during replacement is shown.

In FIG. 1, 1 is a CPU.

2 is a main memory.

Reference numeral 3 is a cache memory having two or more ways.

Reference numeral 4 is a cache memory controller.

Reference numeral 5 is a basic access function, which determines hit / miss hit of the cache memory according to a fetch access request from the CPU 1, outputs data to the CPU in the case of hit, but executes block replacement in the case of miss hit. .

6 is a first fetch bypass function, which is a hit address in the cache memory 3 due to the fetch address from the CPU 1, and when a certain way is block replaced, it becomes a miss hit earlier in the first bus cycle. Output data to CPU.

7 is an access function during replacement, which is a CPU cycle after fetch bypass is performed in the first bus cycle of block replacement, and when the fetch address is output from CPU1, fetches the ways other than the replacement target of the cache memory. The address is accessed and the read data is output to the CPU when a hit occurs.

A second fetch bypass function 8 compares the address transferred from the main memory to the main memory by block replacement with the fetch address from the CPU 1, and outputs the data to the CPU 1 when a match is obtained. If no match is found, CPU1 is put in a standby state.

In the configuration of FIG. 1, the access function during replacement 7 and the second fetch bypass function 8 are shown to operate sequentially, but they are operated in parallel at the same time.
Alternatively, only one of them may be provided. Further, even in the cache memory system which does not have the first fetch / bypass function, the access function during replacement 7 and the second fetch / bypass function 8 can be applied.

[Action]

According to the configuration of the present invention shown in FIG. 1, when the cache memory 3 becomes a mishit in response to a fetch access request from the CPU 1, block replacement is performed and fetch bypass is performed as in the conventional case. In the subsequent cycle, depending on the fetch address generated by the CPU 1 before the end of replacement in the subsequent cycle, the access function during replacement 7 accesses the way that is not the replacement target, and the second fetch bypass function 8 is used. The address of the data being transferred from the main memory for replacement is checked, and if it matches the fetch address, it can be output to CPU1.

Therefore, even during the block replacement period, subsequent data fetch requests from CPU1 may hit,
The processing of the CPU 1 advances accordingly, and the processing efficiency improves.

〔Example〕

FIG. 2 shows the configuration of the first embodiment of the present invention having the second fetch bypass function of FIG.

In FIG. 2, 11 is a CPU, 12 is a cache memory controller CMC, 13 is a direct mapping type cache memory CM, 14
Is an address comparator COMP, 15 is a memory controller MC, 16 is a one-port main memory MM, 17 is an address bus, 18 is a data bus, and 19 is an address buffer B.

Next, the outline of the sequence will be described according to the configuration of FIG.

Based on the address output from CPU11, CMC12 determines hit / miss hit. In case of hit, CM1
Data is output from 3 to the CPU 11. If it is a mishit, move to the replace sequence.

The replacement is performed in block units, and at this time, the address for the MM16 is output from the CMC12. In the fetch bypass, the data transferred in the first bus cycle of replacement is the data expected by the CPU 11, and therefore it is not necessary to judge whether the addresses match or not, and the data is sent to the CPU 11 as it is.

The CPU 11 shifts to the next cycle and outputs the address, but this is blocked by B.19 and does not reach the MM16.
However, it is input to CMC12 via another route. The input address data is compared with the replace address output by CMC12 in COMP.14, and if they match, M
At the same time as the data transfer from M16 to CM13, a data valid signal is issued to CPU11. As a result, the CPU 11 can take in data even during the replacement period.

Next, a detailed sequence will be described with reference to the timing chart of FIG.

* REPL if it is determined to be a cache read miss
ACE = "0", and the replacement sequence is started. The block replace transfers the block (6 entries in the above time chart) including the read-missed address from the main memory. The replace address RE-ADDRESS is set to ADDRESS at the time of a miss hit, and is sequentially incremented each time the transfer of one entry is completed.

For CPU11, enter * REA at the beginning of the replacement
Set DY = "0" to fetch data (during fetch bypass). CPU11 shifts to the next cycle, and AD
Output DRESS. The address output from the CPU 11 is compared with the address output from the cache controller CMC 12, and if they match, * READY is output again to the CPU 11 to cause the data to be fetched. If they do not match, * READY = "1" is set to prevent malfunction by suppressing data acquisition.

Although not shown, the cache memory mainly comprises an LRU unit, an address tag unit, a valid bit unit, a data block unit, an address tag comparator, a buffer, a memory interface and the like.

The LRU (Least Recently Used) part is a part that stores the information of the memory block to be replaced,
It is provided in the cache memory, excluding the direct mapping cache memory. address·
The tag portion is a portion that stores address information. In a cache memory system that performs block replacement, only high-order addresses are stored. The valid bit portion corresponds to the lower address, while the address tag portion stores the upper address, and indicates whether each address is valid or invalid. The data block part is a part that stores actual data. The address / tag comparator compares the address information output from the CPU with the contents of the address tag and outputs a match / mismatch signal.

Normally, when the address / tag comparator determines that they do not match, a so-called mishit occurs, and the replace sequence is activated. By a mishit, L
One of the memory blocks (4
In the case of the way set associative method, one of 4 ways is selected, the address tag part and valid bit part are updated, and data transfer from the main memory to the data block part is started. .

Therefore, if the configuration of the cache memory is improved, the address tag section and the valid bit section can be accessed in parallel even during the data transfer to the data block section.

Therefore, assuming a dual-port type static RAM that has an input port and an output port independently as cache memory, access is performed using the output port, and replacement is performed using the input port. Shall be used. As a result, while performing the replacement sequence, the data
Blocks can be accessed, and parallel operation can be achieved even with a direct mapping type cache memory system.

FIG. 4 shows the configuration of the second embodiment of the present invention using such a dual port type and direct mapping type cache memory CM. Further, FIG. 5 shows the configuration of the third embodiment further including the address comparator 14 of the first embodiment of FIG.

Next, if the cache memory data consists of two or more sets of data blocks (two-way or more set associative method) and one-port memory is used, the remaining ways except the way during block replacement are used. The cache read hit is judged, if it hits, the data is output to the CPU, and if it becomes a miss hit, the completion of the replacement is waited and the hit in the way where the replacement was carried out is judged. .

FIGS. 6 and 7 show the data flow and address flow of the fourth embodiment of the present invention using a 4-way set associative cache memory with a 1-port memory. Also, in FIG. 8 and FIG. 9, the address comparator CO
7 shows a data flow and an address flow of the fifth embodiment having MP.

In FIGS. 6 to 9, CM ₁ to CM ₄ correspond to four ways. There are also two Bs at each end of each CM.
Is a port that secures a route between the port that outputs data to the CPU and the MM (indicated by MM ₁ to MM ₃ ) for replacement.

Furthermore, when a dual port memory having independent input ports and output ports is used as the cache memory, it is possible to perform hit / miss hit comparison even between ways during which block replacement is being executed.

10 and 11 show the data flow and address flow of the sixth embodiment having such a configuration. Also the 12th
FIG. 13 and FIG. 13 show the data flow and address flow of the seventh embodiment in which the address comparator COMP. Is added.

CM ₁ and CM _{2 in} FIGS. 10 to 13 form a dual port 2-way cache memory.

〔The invention's effect〕

Even during replacement, it is possible to judge hit / miss / hit, and at the time of hit, the CPU can take in data, and also hit / miss hit with the data during replacement. Even if it is determined and a hit occurs, the CPU can similarly take in data, so the expected cycle time value following a cache miss hit can be reduced. This will reduce the CPU standby time and improve system performance.

[Brief description of drawings]

1 is a block diagram of the principle of the present invention, FIG. 2 is a block diagram of the first embodiment of the present invention, FIG. 3 is a timing diagram of the first embodiment of the present invention, and FIG. 4 is a second diagram of the present invention. FIG. 5 is a configuration diagram of an embodiment, FIG. 5 is a configuration diagram of a third embodiment of the present invention, and FIGS. 6 and 7 are data flow diagrams and address flow diagrams of a fourth embodiment of the present invention, FIG. 8 and FIG. FIG. 9 is a data flow diagram and address flow diagram of the fifth embodiment of the present invention, and FIGS.
FIG. 12 is a data flow diagram and address flow diagram of the sixth embodiment of the present invention, and FIGS. 12 and 13 are data flow diagram and address flow diagram of the seventh embodiment of the present invention. Figure 1: 1: CPU 2: Main memory 3: Cache memory 4: Cache memory controller 5: Basic access function 6: First fetch / bypass function 7: Access during replacement 8: Second fetch / bypass function

Front page continuation (72) Inventor Chisato Hanate 4-2-49, Fukaminishi, Yamato-shi, Kanagawa Prefecture Yamato Plant, PFU Co., Ltd. (72) Takayuki Okubo 4-49, Fukaminishi, Yamato-shi, Kanagawa No. Stock Company PFU Uchi Yamato Factory (56) Reference JP-A-59-177782 (JP, A) JP-A-64-29953 (JP, A) JP-A-61-118855 (JP, A)

Claims (4)

[Claims] 1. In a set-associative cache memory system of two-way or more, which replaces data in block units, fetch addresses subsequently given from the CPU during block replacement exclude ways during block replacement. The cache read hit / miss hit is judged in the remaining ways, and when hit, the corresponding data is
A cache memory system that outputs to a CPU. 2. A cache memory system having a function of replacing data in units of blocks and performing fetch bypass, after fetch bypass during block replacement is performed.
The fetch address given subsequently by the CPU in the CPU cycle is compared with each address of the replace data being block transferred from the main memory. If the addresses match, the corresponding replace data is transferred to the cache memory and at the same time the CPU A cache memory system that is also output to. 3. In a cache memory system for replacing data in block units, the cache memory is also accessed for a fetch address continuously given from the CPU in a CPU cycle after fetch bypass during block replacement, and when a hit occurs, the cache is cached. The corresponding data in the memory is output to the CPU, and the fetch address from the CPU is compared with each address of the replace data in the block transfer from the main memory. The cache memory system is characterized in that the replacement data is transferred to the cache memory and is simultaneously output to the CPU. 4. The cache memory system according to claim 3, wherein the cache memory system that replaces data in block units is a set associative cache memory system of two or more ways.