JPH1055308A - Cache memory - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To prevent occurrence of a cache miss depending on the arrangement state of a loop program and to store a loop program in a wide range even when a loop program is stored by the entire capacity of a cache memory and loop processing is performed.・ Improve the hit rate corresponding to the program. SOLUTION: Two upper address registers 111 and 112,
Data memory 12 for storing a plurality of words, two valid bit registers 131 and 132, and two comparators 141 and 142
And two comparators 151 and 152 that pass the data memory output when the valid bit of the word to be read from the data memory is valid.
A page flag circuit 16 indicating which of the valid bit registers is the tag of the current page, and reading / storing the data memory and controlling the flag of the valid bit register and the flag of the page flag circuit in accordance with the judgment result of the comparator And a cache control circuit 17.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cache memory, and more particularly to a cache memory of a valid bit control system provided with a register for controlling a valid bit, which is used, for example, in a computer system.

[0002]

2. Description of the Related Art In a computer system, the difference between the operating speed of a microprocessor (MPU) and the operating speed of a main memory is increasing, and the data transfer speed between the two affects the performance of the entire system. It has become. Various improvements have been made to solve this problem. A typical example is placed between the MPU to fill the difference between the cycle time of the MPU and the access time of the main memory. This is the adoption of a high-speed memory (cache memory) that enables improvement.

At present, three types of cache memories are known. The first type is a static type memory (SRAM) which is independent from the MPU and the main memory, and the second type is a cache type memory on the MPU chip. S called on-chip cache or embedded memory mounted
The memory is composed of a RAM (actually, an MPU having a cache memory may further have an SRAM cache of another chip). The third is mounted on a dynamic memory (DRAM) chip. SRAM
It consists of cells. Of the above three types of cache memories, the second or third configuration is compact, and is therefore used for workstations and high-end personal computers.

FIGS. 2 to 4 show the cache memory 3.
3 shows a basic configuration (direct map system, 2-way set associative system, full associative system). Hereinafter, the capacity of the cache memory is set to 1
The description will be made assuming 28 words.

In the direct map type cache memory shown in FIG. 2, an instruction address register 50 designates, as a group, instructions to be executed next among program instructions read from an external storage device (not shown). And an address composed of a lower address for designating each of a group of instructions designated by the upper address.

[0006] A plurality of upper address registers (tag address registers) 51 store tag addresses supplied from the instruction address register 50. A plurality of data memories (original cache memory units) 52 are provided corresponding to the plurality of tag address registers 51, prefetch and store a group of instructions specified by a tag address, and store a group of instructions stored therein. Each is specified according to the lower address supplied from the instruction address register 50.

A comparator 53 compares a tag address stored in a tag address register selected and designated among the plurality of tag address registers 51 with a tag address supplied from the instruction address register 50, and compares both tag addresses. Judgment of address match / mismatch (hit / miss).

Further, when the result of the determination by the comparator 53 is a match, the data memory 52 corresponding to the tag address register 51 storing the tag address corresponding to the match is stored in the lower address supplied from the instruction address register 50. , And outputs one of the instructions stored in the data memory 52. If the result of the determination by the comparator 53 does not match, the external storage is performed according to the address supplied from the instruction address register 50. A cache control circuit (not shown) that reads and outputs an instruction from the device and controls the read instruction to be stored in the data memory 52 corresponding to the tag address register 51 that stores the tag address related to the mismatch. ) Is provided.

Each of the data memories 52 has a capacity to store data read from an external storage device in word units. That is, the direct map type cache memory specifies the position of the tag address register 51 using the lower bits of the address stored in the instruction address register 50, and stores the contents of the specified tag address register and the instruction address register 50. Are compared by the comparator 53 with the upper bit (tag address) of the address stored in.

When the comparison result of the comparator 53 matches (hit), that is, when the tag address for accessing the storage device is assigned to the tag register, the information stored in the data memory 52 is used. Is controlled to be output.

On the other hand, when the result of the determination is a mismatch (miss), that is, when information that is not stored in the data memory 52 is required, another information is stored in the external storage device storing the required information. Is read from the position, and is controlled so as to be stored in the data memory 52 and output.

However, the direct map method as described above has a problem in that when a plurality of lower bits refer to a plurality of common addresses or when a program jumps back and forth between the addresses, a conflict occurs.

The cache memory of the two-way set associative system shown in FIG. 3 is obtained by dividing a plurality of tag address registers 51 and a plurality of data memories 52 in a direct map system into two sets and providing a comparator 53 in each of the two sets. Thus, the lower few bits are expanded so that up to two common addresses can be stored while avoiding contention.

The full associative method shown in FIG.
The plurality of tag address registers 51 and the plurality of data memories 52 in the direct map system are divided into a plurality of sets each including one combination, and the plurality of sets are provided with the comparators 53, respectively. It is an extension that can store everything.

In order to realize the cache memory of each of the above-described methods, in addition to the data memory 52, the tag address register 51 is required in the direct map method, and the tag address register 51 and the comparator 53 are required in the associative method.

However, the data memory 52 is essentially required for mounting the cache memory, and other necessary resources (the tag address register 51 and the comparator 5) are required.
Since 3) is overhead, it is desirable to reduce as much as possible. Therefore, when the data memory 52 is changed to handle a plurality of data collectively, the number of tag address registers 51 and comparators 53 can be reduced accordingly.

FIGS. 5 to 7 show a cache memory constructed by focusing on the above facts, as a direct map system, a two-way set associative system, and a full associative system shown in FIGS. 2 to 4, respectively. 1 shows an example in which a data memory in a cache memory of a system is implemented as a line memory in units of, for example, four words.

As described above, one tag address register 5
If the number of words in the data memory 52 corresponding to 1 is increased, the number of tag address registers 51 can be reduced. That is, in each of the systems shown in FIGS. 3 to 7, the number of tag address registers 51 can be reduced to 1/4 as compared with each of the systems shown in FIGS.
The word-based full associative method is different from the full associative method shown in FIG.
The number of 3 can also be reduced to 1/4.

However, one tag address register 51
If the hit / miss is determined by collectively handling too much data in the data memory 52 corresponding to the data memory 52, there is too much waste. Therefore, a valid / invalid determination flag (hit / miss determination It is conceivable to add one bit for (flag).

When the full associative method is extended based on such a concept, a cache memory having a configuration as shown in FIG. 8 can be considered. The cache memory shown in FIG. 8 is provided with two combinations of a tag address register 51, a data memory 52a that collectively handles a large number of words of data (for example, in units of 64 words), and a comparator 53. Correspondingly, a register 71 for controlling a valid bit (valid bit) is provided.

As described above, in the cache memory of the effective bit control system provided with the register for the effective bit control, the tag address register 51 is used when the access is made over the storage area of two consecutive pages in the external storage device. 1
Individually, all data memory 52
Since the content of a becomes invalid, the tag address register 51 cannot be reduced to less than two in order to avoid this.

By the way, the computer program is:
Since a lot of time is spent in loop processing, the hit rate of the cache memory during the loop processing is important, and even a small-capacity cache memory should support a wide range of loops as much as possible. When the effective bit control type cache memory is configured with a capacity of 128 words as described above, all of the loop program having a maximum of 128 words can be stored in the cache memory. However,
This is limited to the case where the loop program is arranged and stored in the storage area 61 for two consecutive pages in the external storage device as shown in FIG.
As shown in (b), when the loop program is arranged and stored in the storage area 61 for three consecutive pages in the external storage device, the total amount of the loop program is within 128 words. However, a miss occurs in the cache operation.

In order to solve such a problem, it is easy to cope with the problem by increasing the capacity of the cache memory itself. However, without increasing the capacity of the cache memory itself, the loop program is increased by the entire capacity of the cache memory. Is desirable.

[0024]

As described above, the conventional effective bit control type cache memory provided with the effective bit control register has a large number of loop programs even when a loop program of less than the full capacity of the cache memory is stored.・
There is a problem that a cache miss occurs during loop processing depending on the arrangement of programs.

The present invention has been made in order to solve the above-described problem. When a loop program is stored by the entire capacity of the cache memory and loop processing is performed, a cache miss depending on the arrangement state of the loop program is performed. Of the effective bit control method that can prevent the occurrence of a pattern, increase the hit rate corresponding to a wide range of loop programs, and further reduce the pattern occupation area, reduce the chip cost and increase the operation speed. It is an object to provide a cache memory.

[0026]

SUMMARY OF THE INVENTION A cache memory according to the present invention comprises an upper address for designating, as a group, instructions to be executed next among program instructions read from an external storage device, and a higher address for designating the instructions. Instruction address register for storing address data composed of lower addresses designating each of a group of instructions to be executed, a first upper address register for storing an upper address supplied from the instruction address register, and a second upper address register for storing an upper address. And a capacity for storing a group of instructions for one page specified by an upper address stored in the instruction address register, and prefetching a group of instructions read from the external storage device. Each of the stored group of instructions is stored in a lower address supplied from the instruction address register. A data memory for storing a plurality of words specified in advance and a corresponding one of the two upper address registers are provided corresponding to each word read from the external storage device and stored in the data memory. A first valid bit register and a second valid bit register for alternately storing a group of added valid / invalid bits according to page switching of data read from the external storage device; and the two upper addresses A register is provided corresponding to a register, and an upper address stored in correspondence with each of the two upper address registers is compared with an upper address supplied from the instruction address register. A first comparator and a second comparator to be determined, a comparison determination result of the first comparator, and the data A valid bit stored in the first valid bit register is input corresponding to the word to be read from the memory, and when the comparison determination input matches and the valid bit input is valid, the data is read from the data memory. A first gate circuit for passing an output, a comparison result of the second comparator, and a valid bit stored in the second valid bit register corresponding to a word to be read from the data memory. The second gate circuit that passes the read output from the data memory when the comparison determination input matches and the valid bit input is valid, and which of the two valid bit registers plays the role of the tag of the current page A page flag circuit for outputting a page flag indicating whether or not the comparison is being performed; If the determination result is a match, one of the instructions stored in the data memory is read and output in accordance with the lower address supplied from the instruction address register, and if the determination result of the comparator does not match, A cache control circuit that reads and outputs an instruction from the external storage device in accordance with an address supplied from the instruction address register, and controls the read instruction to be stored in the data memory. It is characterized by having.

[0027]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 shows a cache memory (capacity is, for example, 128 words) of a valid bit control method in a computer system according to a first embodiment of the present invention, and a connection relationship between the cache memory and an external storage device 20.

In FIG. 1, the cache memory includes an instruction address register 10, two upper address registers (tag registers) 111 and 112, a data memory 12,
Two valid bit registers 131, 132, two comparators 141, 142, two gate circuits 151, 1
52, a page flag circuit 16 and a cache control unit 17.

The instruction address register 10 is a high-order address for designating, as a group, instructions to be executed next among program instructions read from the external storage device 20 and controlled by the cache control unit 17 to the bus 18. A tag address) and address data (for example, 32 bits) composed of a lower address designating each of the group of instructions designated by the upper address. In this example, the upper address is a page address that specifies one page of data in the external storage device 20.

The two upper address registers (the first upper address register 111 and the second upper address register 112) store the tag address supplied from the instruction address register 10, respectively.

The data memory 12 is an original cache memory unit, and has a capacity for storing a group of instructions (128 words) for one page specified by a tag address stored in the instruction address register 10. A group of instructions read from the external storage device 20 is prefetched and stored, and each of the stored group of instructions is designated according to a lower address supplied from the instruction address register 10.

The two valid bit registers (the first valid bit register 131 and the second valid bit register 132) correspond to each word read from the external storage device 20 and stored in the data memory. A group of added valid bits (hit / miss determination flag bits) is alternately stored in accordance with page switching of data read from the external storage device 20.

The two comparators (the first comparator 141 and the second comparator 142) correspond to the two upper address registers 111,
The tag address stored in the register address 112 is compared with the tag address supplied from the instruction address register 10 to determine a match / mismatch (hit / miss) between the two tag addresses.

A first gate circuit 151 of the two gate circuits has a first valid bit corresponding to the comparison result of the first comparator 141 and a word to be read from the data memory 12. Register 131
When the valid bit stored in the data memory 12 is input, the comparison determination input matches, and the valid bit input is valid, the data memory 12
And sends it to an execution unit (for example, an MPU) through the read output from the MPU.

The second gate circuit 152 of the two gate circuits has a second valid bit corresponding to the comparison result of the second comparator 142 and the word to be read from the data memory 12. Register 132
When the valid bit stored in the data memory 12 is input, the comparison determination input matches, and the valid bit input is valid, the data memory 12
And sends it to the execution unit by passing the read output from the execution unit.

The page flag circuit 16 outputs a page flag indicating which of the two valid bit registers 131 and 132 plays the role of the tag of the current page. For example, a flip-flop circuit (FF) And the output (page flag) is controlled so as to be inverted every time the page is switched.

The cache control unit 17 has the following functions and, if necessary, a write-back function. (1) If the judgment results of the comparators to be judged out of the two comparators 141 and 142 are coincident, they are stored in the data memory 12 according to the lower address supplied from the instruction address register 10. A first control function for reading and outputting one of the instructions present.

(2) The two comparators 141, 1
When the judgment result of the comparator to be judged out of 42 is not coincident, the instruction is read out from the external storage device 20 in accordance with the address supplied from the instruction address register 10, and is output. A second control function for controlling the data to be stored in the data memory 12;

(3) Two valid bit registers 13 according to page switching of data read from the external storage device 20
A third control function for controlling a group of valid / invalid bits to be alternately stored in 1, 132.

(4) A fourth control function for controlling the page flag output of the page flag circuit 16 to be inverted every time the page of data read from the external storage device 20 is switched. Further, the read output of the data memory 12 may enter an output buffer circuit (not shown), and the output buffer circuit may be activated by the output of a coincidence signal from the comparator 141 or 142. By outputting the mismatch signal output of the comparator 141 or 142 as a wait signal via a buffer circuit (not shown),
The PU may be configured to be in the wait state.

In the cache memory having the above-described configuration, one upper address register 111, 112 and two valid bit registers 131, 132
Since the number of data memories 12 is shared, the number of words corresponding to each tag address is apparently 128 words, which is twice the 64 words of the above-described conventional example. Also, the control becomes slightly complicated.

More specifically, one valid bit register 1
Each time the valid bit of the word hit by the data of the current page in 31 or 132 is set to a valid state (for example, "1" state), the other valid bit register 1
At 32 or 131, the valid bit of the corresponding word must be forcibly cleared to the reset state (for example, "0" state). That is, one data memory 1
2 effective bit registers 131 and 132 sharing
Must be exclusively set to the valid state.

With this control, in the case of a simple loop program, even if the data read from the external storage device 20 is switched to the data of another page, the data (instruction) of the page used immediately before ) Can be used effectively.

Here, a specific operation example will be described on the assumption that the cache memory is an instruction cache memory and writing to the external storage device 20 does not occur.
Since the two valid bit registers 131 and 132 are symmetrically connected to the data memory 12, whichever may be used for the current page immediately after reset, the role of the tag of the current page / previous page during the cache operation. Work alternately.

Since the page flag circuit 16 is controlled so that the output is inverted every time the page is switched, the output of the page flag circuit 16 indicates which of the two valid bit registers 131 and 132 plays the role of the tag of the current page. Can be used as a flag.

The cache control unit 17 performs the following (1) to
The control as described in (4) is performed. (1) When both the current page and the previous page are misses (such as immediately after reset). All valid bits of one valid bit register 131 or 132 corresponding to the data of the previous page are collectively cleared to correspond to the data of the current page, and the other of the valid bits corresponding to the data of the current page until now is cleared. All the valid bits of the valid bit register 132 or 131 are collectively cleared to correspond to the data of the previous page. Thereafter, data is read from the external storage device 20, the valid bit of the current page valid bit register corresponding to the updated word is set to a valid state, and the corresponding valid bit of the previous page valid bit register is cleared. . (2) When the current page is hit, but the word is missed (this is the case when the program is sequentially executed without jumping backward).

Since the data corresponding to the new address does not exist in the data memory 12, the data is read from the external storage device 20 and the valid bit of the current page valid bit register corresponding to the updated word is set. The corresponding valid bit of the valid bit register for the previous page is cleared. (3) When the current page is hit and the word is also hit (this applies after the program jumps by referring to the back, or during execution of a loop program).

Since this is a cache hit, data is supplied from the corresponding data memory 12 to the execution unit without accessing the external storage device 20. (4) When the previous page hits and the word hits (this applies after the program jumps by referring to the rear across a plurality of pages, or when a loop program is executed).

Since this is a cache hit, data is supplied from the corresponding data memory 12 to the execution unit without accessing the external storage device 20. Also, the roles of the valid bit register for the previous page and the valid bit register for the current page are switched. Thus, the next access should be as described in (3) above.

The cache control operation as described above is not limited to the case where the loop program is arranged and stored in the storage area for two consecutive pages in the external storage device 20. As shown, even when the loop program is arranged and stored in the storage area for three consecutive pages in the external storage device 20, regardless of the storage location of the program in the data memory 12, , It is possible to always refer backward to 128 words, so that no cache operation miss occurs.

In other words, according to the cache memory, it is possible to store the loop program by the entire capacity of the data memory 12 and to increase the hit rate corresponding to a wide range of the loop program. Since it is not necessary to increase the capacitance itself, it is possible to further reduce the pattern occupation area, suppress an increase in chip cost, and increase the operation speed.

[0052]

As described above, according to the present invention, even when the loop program is stored by the entire capacity of the cache memory, a cache miss does not occur at the time of the loop processing depending on the arrangement state of the loop program. It is possible to increase the hit rate in response to loop programs, further reduce the pattern occupation area,
It is possible to provide an effective bit control type cache memory capable of suppressing chip cost and increasing operation speed.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a cache memory according to a first embodiment of the present invention.

FIG. 2 is a block diagram showing an example of a basic configuration of a conventional cache memory.

FIG. 3 is a block diagram showing another example of the basic configuration of a conventional cache memory.

FIG. 4 is a block diagram showing still another example of the basic configuration of the conventional cache memory.

FIG. 5 is a block diagram showing an example in which the data memory in the cache memory of FIG. 2 is implemented as a line memory in units of four words.

FIG. 6 is a block diagram showing an example in which the data memory in the cache memory of FIG. 3 is implemented as a line memory in units of four words.

FIG. 7 is a block diagram showing an example in which the data memory in the cache memory of FIG. 4 is implemented as a line memory in units of four words.

FIG. 8 is a block diagram showing an effective bit control type cache memory that is conventionally considered by expanding the full associative type cache memory in FIG. 7;

9 shows an example in which a cache operation is normally performed and an example in which a cache miss occurs due to the arrangement of the loop program in the storage device when a loop program is stored and processed in the effective bit control type cache memory of FIG. FIG.

[Explanation of symbols]

 Reference numeral 10: Instruction address register, 111, 112: Upper address register, 12: Data memory (original cache memory unit), 131, 132: Valid bit register, 141, 142: Comparator, 151, 152: Gate circuit, 16: Page Flag circuit, 17: cache control unit, 20: external storage device.

Claims (3)

[Claims] 1. An upper address for designating, as a group, instructions to be executed next among program instructions read from an external storage device, and a lower address for designating each of a group of instructions designated by the upper address. An instruction address register for storing address data composed of addresses; a first upper address register and a second upper address register for storing an upper address supplied from the instruction address register; It has a capacity to store a group of instructions for one page specified by the stored upper address, stores a group of instructions read out from the external storage device in advance, and stores the group of instructions. A data memory for storing a plurality of words each designated according to a lower address supplied from the instruction address register. And Li, provided corresponding to the two upper address register,
A first valid bit register and a second valid bit register for storing a group of valid / invalid bits added corresponding to each word read from the external storage device and stored in the data memory; Provided corresponding to the two upper address registers,
The upper address stored in correspondence with each of the two upper address registers is compared with the upper address supplied from the instruction address register, and a match / mismatch (hit / miss) of both upper addresses is determined. 1 and a second comparator, and a comparison result of the first comparator and a valid bit stored in the first valid bit register corresponding to a word to be read from the data memory. A first gate circuit that selects and outputs a word to be read from the data memory when the comparison determination input matches and the valid bit input is valid; a comparison determination result of the second comparator and the data; Stored in the second valid bit register corresponding to the word to be read from the memory. A second gate circuit that selects and outputs a word to be read from the data memory when the valid bit input is input, the comparison determination input matches, and the valid bit input is valid; and the two valid bits A page flag circuit that outputs a page flag indicating which of the registers plays the role of the tag of the current page; and if the determination result of the comparator to be determined among the two comparators is the same, the instruction A first control function for reading and outputting one of the instructions stored in the data memory according to the lower address supplied from the address register, and the instruction address when the determination result of the comparator does not match. A command is read and output from the external storage device according to the address supplied from the register, and the read command is read. A second control function for controlling the data to be stored in the data memory; and a group of the valid / invalid bits alternately stored in the two valid bit registers in accordance with page switching of data read from the external storage device. And a fourth control function of controlling the page flag output of the page flag circuit to be inverted every time a page of data read from the external storage device is switched. And a circuit. 2. The cache control circuit according to claim 1, further comprising: (1) if the judgment result of said comparator does not match the current page / previous page, one of the valid bits corresponding to the data of the previous page. All the valid bits of the register are collectively cleared to correspond to the data of the current page, and all the valid bits of the other valid bit register corresponding to the data of the current page are collectively cleared to the data of the previous page. After the correspondence, the data is read from the external storage device, the valid bit of the current page valid bit register corresponding to the updated word is set, and the corresponding valid bit of the previous page valid bit register is cleared. (2) When the judgment result of the comparator is that the current page matches and the word does not match, the data is read from the external storage device and the updated word is read. A control function of setting the valid bit of the corresponding valid bit register for the current page and clearing the valid bit of the corresponding valid bit register for the previous page; (3) the judgment result of the comparator is the current page or word. A control function for supplying data from the corresponding data memory to the execution unit without access to the external storage device when the values match, and (4) when the determination result of the comparator also matches the previous page and word. A control function for supplying data from the corresponding data memory to the execution unit without accessing the external storage device, and for switching the role of the valid bit register for the previous page and the role of the valid bit register for the current page. The cache memory according to claim 1, wherein: 3. The cache memory according to claim 1, wherein the page flag circuit is a flip-flop circuit whose output is controlled every time a page is switched.