System Including Processor and Cache Memory and Method of Controlling the Cache Memory

The present invention relates to a cache memory control system and, particularly, to a technology of controlling a cache memory connected to a processor that gains access to data such as vector data.

If a cache memory that operates normally is connected to a processor that accesses particular data, such as a vector operation type processor that accesses vector data, the speed of the system as a whole is often reduced because of a penalty in the case of a cache miss, thereby making it difficult to increase the speed of processing. It has therefore been desired to provide a control system that reduces the penalty in the case of a cache miss and maintains a high-speed operation even when a cache memory that normally operates is connected to a processor that accesses vector data.

The cache memory is generally connected between a low speed main memory and a high speed processor such that the processor is allowed to gain access to the data at a high speed.

The cache memory is divided into "entries" called lines, as shown in, for example, FIGS. 1a and 1b. Each entry has a line size of, usually, about 16 bytes or about 32 bytes. In the case of a line size of, for example, 32 bytes or a double precision of 8 bytes as shown in FIG. 1a, four words (data) are stored in each line.

Outline of the cache memory operation is described with reference to a cache memory of a copy back system.

When data exists in the cache memory under the condition that a processor that controls the cache memory is gaining access to the cache memory, i.e., in the case of a "cache hit", the entry including this data is read out from the cache memory at the time of reading, and the above data is written onto the above entry in the cache memory at the time of writing.

On the other hand, when the data to which access is made does not exist in the cache memory, i.e., in the case of a "cache miss" in general, the entry is placed in the cache memory. Concretely speaking, the corresponding entry is read out from the main memory and replaces a corresponding entry in the cache memory.

In this case, the data of an amount of one entry (four data, i.e., data of 32 bytes in the case of double precision data of 8 bytes) must be read out from the main memory to be stored in the cache memory. That is, in the case of a cache miss at the time of read access, the data read out from the main memory is not the data to which access is made but instead consists of data (32 bytes) of one entry that includes the above data. Similarly, even in the case of a cache miss at the time of write access, an entry (32 bytes of data) including the missed (miss-hit) data is read out from the main memory, replacing the corresponding entry in the cache memory and, then, the write data are written thereon.

In an ordinary cache memory, when the processor gains access to the instruction or data, in general, the data to which access is made next are stored, in many cases, in an address near the preceding data. Even when the entry data are cached at the time of a cache miss, the data of the cached entry will be hit with a relatively large probability by an access that is made subsequently.

In the case of memory access for the vector data effected by, for example, the processor of the vector operation type, problems arise as will be described later.

Here, the vector data stands for a set of data of a kind used for the arithmetic operation and in which each of the data is called "element" of vector data. In general, what are frequently used for gaining access to the vector data are a sequential data access and a data access with distance. In the case of, for example, double precision data of 8 bytes, the "sequential data access" represents an access mode such that addresses for the elements are arranged maintaining a distance (stride) of 8 bytes and the elements of vector data are sequentially stored in the memory. On the other hand, the "data access with distance" represents an access mode such that the elements of vector data are arranged not maintaining a distance (stride) of 8 bytes, but maintaining a value that is twice as great and the elements of vector data are stored in the memory maintaining a predetermined gap (distance). For the sake of convenience, the data access mode represented by the data access with distance is called "non-sequential data access" in contrast to "sequential data access".

In the case of sequential data access, one entry of data including data (i.e., element) to which access is made are read out from the main memory and replace the corresponding entry in the cache memory according to a process that is usually performed at the time of a cache miss. In this case, however, the entry that is substituted includes data (element) to which access will be made. Therefore, the data is necessarily hit when access is made thereto. In other words, in the case of the sequential data access, the data to which access will be made next is stored in an address neighboring the address of the preceding data. Therefore, even when the entry data are replaced according to the processing at the time of a cache miss as described above, the data of the replaced entry is reliably hit by the subsequent access, thereby retaining the efficiency of the whole system.

In the case of the non-sequential data access, on the other hand, one entry of data is replaced at the time of a cache miss as described above. In this case, however, the elements of vector data are stored maintaining a predetermined distance (stride), and the replaced entry does not include the data (element) to which access will be made next. In other words, in the case of the non-sequential data access, the data to which access will be made next is stored in an address (another entry in many cases) that is distant, maintaining a predetermined stride from the address of the preceding data. Therefore, even when one entry of data is cached according to a processing at the time of a cache miss, the other data (element) of the cached entry is seldom used by the subsequent access. That is one entry of data read out from the main memory becomes useless excepting the data in the cache-miss state. Therefore, the processing time is lengthened by gaining access to the useless data and the efficiency of the system as a whole is lowered.

It is, therefore, an object of the present invention to improve the efficiency of the system in which a processor is connected to the cache memory to gain access to particular data such as vector data by reducing the penalty at the time of a cache miss in effecting non-sequential data access and, hence, by realizing a high-speed operation.

In order to accomplish this object according to the present invention, the cache memory is controlled by recognizing that the kind of access to the vector data (sequential data access or non-sequential data access) has generally been determined at the time of starting the access and by utilizing the information thereof.

According to a first aspect of the present invention, therefore, there is provided a processor that gains access to data in a cache memory, comprising a unit for outputting a discrimination signal that indicates whether the access made to said the cache memory is a sequential address data access or a non-sequential address data access, to thereby control said cache memory.

According to a second aspect of the present invention, furthermore, there is provided a system comprising a cache memory connected to a processor and a main memory, wherein said processor has a unit for outputting a discrimination signal that indicates whether access made to said cache memory is a sequential address data access or a non-sequential address data access, and said cache memory has a unit for changing the processing in a cache-miss state depending upon said discrimination signal, thereby suppressing unnecessary access to said main memory in the case of non-sequential address data access.

According to a third aspect of the present invention, there is provided a method of controlling a cache memory in a system equipped with said cache memory connected to a processor and with a main memory, comprising a step of sending a discrimination signal from said processor to said cache memory indicating whether the access is a sequential address data access or a non-sequential address data access, and a step of changing the processing in a cache-miss state when said discrimination signal is indicating the non-sequential address data access in a cache-miss state.

According to the aforementioned constitution (second aspect of the present invention), the discrimination signal indicating the kind of access is sent from the processor to the cache memory, and the processing in a cache-miss state is changed depending upon the discrimination signal. That is, in the case of the non-sequential data access, unnecessary access to the main memory is suppressed. Therefore, the processing time is shortened by an amount by which the useless access is suppressed, and the efficiency of the system as a whole is improved.

Actions and effects of the first aspect and third aspect of the present invention as well as other structural features and actions of the present invention will be described below in detail byway of an embodiment with reference to the accompanying drawings.

FIGS. 1a and 1b are diagrams illustrating a control mode in cache-hit state in the conventional sequential data access;

FIGS. 2a and 2b are diagrams illustrating a control mode in cache-miss state in the conventional sequential data access;

FIGS. 3a and 3b are diagrams illustrating a control mode in a cache-hit state in the conventional non-sequential data access;

FIGS. 4a and 4b are diagrams illustrating a control mode in a cache-miss state in the conventional non-sequential data access:

FIG. 5 is a diagram illustrating the principle and constitution of a cache memory control system according to the present invention;

FIG. 6 is a block diagram that schematically illustrates a constitution to which the cache memory control system of the present invention is used;

FIG. 7 is a block diagram that illustrates in detail the constitution of the system of FIG. 6;

FIG. 8 is a block diagram that illustrates in detail the constitution of the processor of FIG. 7;

FIG. 9 is a block diagram that illustrates in detail the constitution of an address unit of FIG. 8;

FIGS. 10a and 10b are diagrams illustrating a control mode in cache-hit state in the non-sequential data access according to an embodiment of the present invention; and

FIGS. 11a and 11b are diagrams illustrating a control mode in cache-miss state in the non-sequential data access according to the embodiment of the present invention.

For a better understanding of the embodiment of the present invention, first, problems inherent in the prior art will be described with reference to FIGS. 1a to 4b.

FIGS. 1a, 1b, 2a and 2b illustrate cache memory control modes during the sequential data access according to the prior art.

In this case as shown in FIG. 1a, the vector data are sequentially stored from the fourth word (element 0; EL0) of an entry 1 in the cache memory.

In the case of a cache hit as shown in FIG. 1b, access is made sequentially to the elements (e0 to e8) in response to clocks.

In the case of a cache miss, for example, in the case of a cache miss at an element 1 (EL1) shown in FIG. 2a, the corresponding entry (elements 1 to 4; EL1 to EL4) is read out from the main memory and is stored in the corresponding region of the cache memory. In this case, 8 bytes of data are read out during one access to the main memory. Therefore, access of the main memory is gained four times, and one entry of data (32 bytes) is read out and replaced by a corresponding entry in the cache memory.

In this case, the substituted entry includes the following elements 2 to 4 (EL2 to EL4) and is necessarily hit when access is made to the elements 2 to 4. That is, the data to which access will be gained next is stored in an address neighboring the address of the preceding data. Therefore, even when one entry of data is replaced according to the processing in a cache-miss state, the data of the replaced entry are reliably hit by the subsequent access.

When sequential data access is made as described above, the efficiency of the system as a whole decreases slightly even when a processing (i.e., access to the main memory) similar to that of the ordinary cache memory is carried out.

Next, the cache memory control modes at the time of non-sequential data access will be described with reference to FIGS. 3a, 3b, 4a and 4b.

In the diagram of the embodiment, the elements of vector data are arranged maintaining a distance (stride) of 32 bytes. In this case, since the distance is the same as the line size of the cache memory, the elements (EL0 to EL3) of vector data are arranged in a vertical direction at positions of the second words of the entries as shown in FIG. 3a.

In the case of a cache hit as shown in FIG. 3b, access of the elements (e0 to e8) is sequentially gained in response to clocks.

On the other hand, in the case of a cache miss, for example, in the case of a cache miss at the element 1 (EL1) of FIG. 4a, one entry of data (32 bytes) including the above element is read out from the main memory four access times and is replaced by a corresponding entry in the cache memory.

What is needed by the above entry however is one word of element data (EL1) of the element, and the subsequent elements jump to other entries. Therefore, other words of the replaced entry are not hit by the subsequent access. That is, among 32 bytes of data read out from the main memory, 24 bytes of data (corresponding to three access times) become useless. In other words, the processing time is lengthened by an amount of the access gained to the useless data, and the efficiency of the system decreases as a whole.

FIG. 5 illustrates the principle and constitution of the cache memory control system according to the present invention, wherein reference numeral 1 denotes a processor that gains access to particular data such as vector data; 2 denotes a cache memory connected to the processor, and 3 denotes a main memory that exchanges data relative to the cache memory.

The processor 1 has a unit 1A for outputting a discrimination signal S that indicates whether access gained to the cache memory 2 is a sequential data access or a non-sequential data access. The cache memory 2 has a unit 2A for changing processing in a cache-miss state based upon the discrimination signal. In the case of the non-sequential data access, unnecessary access to the main memory 3 is suppressed.

A concrete embodiment of the present invention will now be described with reference to FIGS. 6 to 11b.

FIG. 6 schematically illustrates the constitution of a system in which the cache memory control system of the present invention is used.

In FIG. 6, reference numeral 1 denotes a 1-chip vector operation type processor LSI; 2 denotes a cache memory that receives access control from the processor via a processor bus 4, and 3 denotes a main memory that exchanges data and addresses relative to the cache memory 2 via a memory bus 5.

At the time of starting access to the cache memory 2, the processor 1 outputs to the cache memory 2, a signal S (hereinafter referred to as non-sequence access discrimination signal) that indicates the kind of access (i.e., whether it is a sequential data access or a non-sequential data access). Upon receipt of the non-sequence access discrimination signal S, the cache memory 2 changes processing in a cache-miss state. More specifically, when the non-sequence access discrimination signal S indicates non-sequential data access, the cache memory 2 does not update the entry that is in a miss state but gains access directly to the data in the main memory 3.

When the processor 1 gains a sequential data access to the cache memory 2, the non-sequence access discrimination signal S is negated and the operation is performed in the same manner as the conventional cache memory.

In the case of the non-sequential data access, on the other hand, the processor 1 asserts the non-sequence access discrimination signal S and informs the cache memory 2 of the non-sequential access. The control mode of the cache memory of this case will be described later.

FIG. 7 illustrates in detail the constitution of the system of FIG. 6, wherein the processor 1 and the cache memory 2 are connected together via a processor bus 4 (address bus PAB and data bus PDB), and the cache memory 2 and the main memory 3 are connected together via a memory bus 5 (address bus MAB and data bus MDB).

As will be described later in detail, the processor 1 has, as part of its constituent elements, an instruction decoder 13 for decoding instruction INST and an address unit 10 that forms the non-sequence access discrimination signal S and effects address conversion based upon the decoded result. Further, the non-sequence access discrimination signal S is used to temporarily freeze or stop the function of the cache memory 2 when asserted and, in this sense, is also called a cache freeze signal CF in the following description.

The cache memory 2 has a tag memory 21 that stores addresses corresponding to the entries taken in via the processor address bus PAB; a comparator 22 that compares the content of the tag memory with the address taken in through the address bus PAB and outputs a cache hit signal (signal HT of the "H" level) when the address that is taken in exists in the addressess stored in the tag memory 21; an inverter 23 that forms an inverted signal HTX of the output of said comparator; an inverter 24 that forms an inverted signal CFX of the cache freeze signal CF from the processor 1, an AND gate 25 that forms a cache freeze control signal in response to the outputs of the inverters 23 and 24; a register 26 that temporarily stores the data taken in via the memory data bus MDB based upon the entry take-in control, which will be mentioned later, a data memory 27 that takes in or retrieves the data from the register 26 in response to the cache freeze control signals from the AND gate 25, a selector 28 that selects either the data from the data memory 27 or the data from the register 26 depending upon the output HT of the comparator 22 and sends it to the processor data bus PBD; and an entry take-in control circuit 29 that controls the take-in of one entry of data from the main memory 3 depending upon the output HT of the comparator 22 and the cache freeze signal CF.

In this constitution, when the cache freeze signal CF is negated (i.e., inverted signal CFX has the "H" level) in a cache-miss state (i.e., inverted signal HTX has the "H" level) during the sequential data access, the output (cache freeze control signal) of the AND gate 25 assumes the "H" level, and the data memory 27 receives the data from the register 26 in response thereto. On the other hand, when the cache freeze signal CF is asserted (i.e., inverted signal CFX has the "L" level) during the non-sequential data access or in the case of a cache-hit (i.e., inverted signal HTX has the "L" level), the above cache freeze control signal becomes invalid (L level) and the memory 27 inhibits the take-in of data from the register 26. Further, the selector 28 selects and outputs the data from the data memory 27 when the output HT of the comparator 22 has the "H" level (i.e., in the case of a cache hit), and selects and outputs the data from the register 26 when the output HT of the comparator 22 has the "L" level (i.e., in the case of a cache miss).

FIG. 8 illustrates in detail the constitution of the processor 1.

The diagram of the processor is a 1-chip vector operation type processor LSI as described above and comprises a chip bus 6 (address bus CAB and data bus CDB), an address unit 10 connected to the chip bus 6, an instruction control unit 11 connected to the chip bus 6, a bus control unit 14 connected to the chip data bus CDB, a vector unit 15 connected to the chip bus 6, and a store pipe 16 and a load pipe 17 that are connected between the vector unit and the bus control unit 14 to control the pipeline processing. Here, the instruction control unit 11 has an instruction queue (buffer) 12 that issues an instruction INST and an instruction decoder 13 that decodes the instruction INST and sends the decoded result to the address unit 10.

The vector unit 15 has a vector register 30 for storing the vector data, a read port 31 for reading out the data from the vector register, a write port 32 for newly writing data onto the vector register 30, an adder 33, a multiplier 34 and a divider 35 that effect the addition, multiplication and division of data that are read out via the read port 31. The aforementioned store pipe 16 stores the data read out from the vector register 30 via the read port 31 and sends the data to the bus control unit 14 after having effected a suitable pipeline processing. The load pipe 17, on the other hand, loads the data that are taken in from the processor data bus PDB via bus control unit 14, similarly effects a suitable pipeline processing, and sends the data to the write port 32.

FIG. 9 illustrates, in detail, the constitution of the address unit 10.

The address unit that is diagramed comprises a scalar register 100 having registers 101 and 102 which, respectively, store strides and base addresses that are taken in via chip data bus CDB and address bus CAB and output corresponding stride information and base address information depending upon the decoded result of the instruction decoder 13; registers 111 and 112 that temporarily store strides and base addresses read out from said registers 101 and 102, respectively, a selector 113 that selectively outputs either the data "0" or the data from the register 111 depending upon a load/store start signal STT, a selector 114 that selectively outputs either the data from the register 112 or the output data of an adder that is described below depending upon the load/store start signal STT, an adder 115 that adds output data of the selectors 113 and 114, a comparator 116 that compares the content of the register 111 with data "8" or "4S" to output the aforementioned cache freeze signal CF, a counter 117 that inputs the load/store start signal STT and counts the address that corresponds to the vector length (length of vector data), a register 118 that stores the data of a vector length taken in via the chip address bus CAB, a comparator 119 that compares the content of the register with the counted value of the counter 117, and an address translation circuit 120 that has a buffer (TLB) with an address translation table and which carries out address translation based on the output of the adder 115 by making reference to the above table.

In this constitution, the cache freeze signal CF is negated when the content of the register 111 is in agreement with the aforementioned predetermined data (data "8" indicating 8-byte distance in the case of double precision data or data "4" indicating 4-byte distance in the case of single precision data) in the comparator 116 (i.e., when the processor 1 makes a sequential data access to the cache memory 2). The cache freeze signal CF is asserted when they are not in agreement with each other (i.e., in the case of non-sequential data access). Furthermore, when the counted value (address corresponding to the vector length) of the counter 117 is in agreement with the content of the register 118, the comparator 119 produces a control signal for halting the function of the address unit 10. Moreover, the load/store start signal STT is produced at the start of reading the data out from the registers 101 and 102 in the scalar register 100. In this case, the above selectors 113 and 114, respectively, select and output data "0" and data from the register 112 at a moment when the load/store start signal STT is output, and then select and output data from the register 111 and output data from the adder 115.

Next, the cache memory control modes at the time of non-sequential data access will be described with reference to FIGS. 10a, 10b, 11a and 11b.

In the diagramed example, the elements of vector data are arranged maintaining a gap (distance) of 32 bytes, the elements (EL0 to EL3) of vector data being arranged in the vertical direction at positions of the second words of the entries as shown in FIG. 10a.

In the case of a cache hit as shown in FIG. 10b access, of the elements (e0 to e8) is made sequentially to in response to the clocks.

On the other hand, in the case of a cache miss, for example, in the case of a cache miss at the element 1 (EL1) shown in FIG. 11a, the non-sequence access discrimination signal S is asserted and the entry that includes the above element of a cache miss (entry 1 in the diagramed embodiment) is not updated and the element (EL1) is directly read out (in the case of reading operation) from the main memory 3. Therefore, the intial data are maintained under the condition that the entry 1 in the cache memory 2 is in a miss state. In the case of the writing operation, similarly, the entry in the cache memory 2 is not replaced in a cache-miss state but is dirctly written into the main memory 3.

The above control operation makes it possible to reduce the number of access times to the main memory 3 in a cache-miss state at the time of non-sequential data access from four times (corresponding to data of 32 bytes) down to one time (corresponding to data of 8 bytes), and the time needed for the cache-miss processing is reduced to one-fourth.

In this case, the entry 1 in the cache memory 2 remains in a cache-miss state but to which no access is gained at the time of access to the next element. Moreover, access of this entry is seldom gained at the time when access is made to the next vector data.

According to the control mode of this embodiment as described above, the cache memory 2 is informed of the kind of access (i.e., sequential data access or non-sequential data access) from the processor 1 at the time of memory access. In the case of non-sequential data access, unnecessary access to the main memory 3 is suppressed making it possible to reduce the penalty at the time of a cache miss without decreasing the hit rate of the cache memory 2. As a result, a high-speed operation is realized and the efficiency of the system as a hole can be improved.