Cache controller for processing simultaneous cache accesses

We claim:

1. A method for processing simultaneous accesses of a cache memory, comprising the steps of:

communicating an external address value using an external address bus using an external address bus;

communicating an internal address value using an internal address bus using an internal address bus;

decoding the external address value to access a first memory location in a first cache tag memory using a first decoder, the first decoder being coupled to the external address bus for receiving the external address value;

concurrently decoding the internal address value to access a second memory location in a second cache tag memory using a second decoder, the second decoder being coupled to the external address bus for receiving the internal address value;

concurrently accessing a status value from a status memory which corresponds to both the first memory location in the first cache tag memory and the second memory location in the second cache tag memory, the status memory being coupled to the first cache tag memory and being coupled to the second cache tag memory; and

selectively modifying the status value using a logic circuit to provide a modified status value when the first memory location of the first cache tag memory and the second memory location of the second cache tag memory are concurrently accessed.

2. The method of claim 1 further comprising the steps of:

storing a plurality of snoop tag values in the first cache tag memory, a first one of the plurality of snoop tag values being used to indicate when a preselected data value is stored in a memory of a first data processor; and

storing a plurality of data tag values in the second cache tag memory, each of the plurality of data tag values being used to indicate when the preselected data value is stored in a cache memory of a second data processor.

3. The method of claim 2 wherein the first memory location of the first cache tag memory is accessed by the external address value when the first data processor performs a snoop data processing operation and wherein the second memory location of the second cache tag memory is accessed by the internal address value when a corresponding data value is stored in the cache memory of the second data processor.

4. The method of claim 3 further comprising the step of:

modifying the status value using the logic circuit when the corresponding data value is written to the cache memory of the second data processor.

5. A cache controller, comprising:

an external address bus;

an internal address bus;

an internal control bus;

a first cache tag memory having a first memory location, the first memory location, the first cache tag memory being coupled to the external address bus;

a second cache tag memory having a second memory location, the second cache tag memory being coupled to the internal address bus; and

a status memory having a status value for providing status information to both the first memory location and the second memory location, the status memory comprising:

a first data buffer having a first input coupled to the internal control bus for receiving a first one of the plurality of data status control signals, a second input coupled to the internal control bus for receiving a second one of the plurality of data status control signals, and the first data buffer having an output;

a second data buffer having a first input coupled to the internal control bus for receiving the first one of the plurality of data status control signals, a second input coupled to the internal control bus for receiving a third one of the plurality of data status control signals, the second data buffer having an output;

a first sense amplifier coupled to the first data buffer for receiving the output of the first data buffer, the sense amplifier coupled to the internal control bus to transfer a first data status value;

a first transistor having a first current terminal coupled to the first data buffer for receiving the output of the first data buffer, a second current terminal, and a control terminal coupled to the internal control bus to receive a fourth one of the plurality of data status control signals;

a second transistor having a first current terminal coupled to the second current terminal of the first transistor, a second current terminal, and a control terminal coupled to the internal control bus to receive a fifth one of the plurality of data status control values;

a status bit cell having a first terminal coupled to the second current terminal of the second transistor and having a second terminal;

a third data buffer having a first input coupled to the internal control bus for receiving a first one of the plurality of snoop status control signals, having a second input coupled to the internal control bus for receiving a second one of the plurality of snoop status control signals, the third data buffer having an output;

a fourth data buffer having a first input coupled to the internal control bus for receiving the first one of the plurality of snoop status control signals, the fourth data buffer having a second input coupled to the internal control bus for receiving a second one of the plurality of snoop status control signals, the fourth data buffer having an output;

a second sense amplifier coupled to the third data buffer for receiving the output of the third data buffer, the sense amplifier coupled to the internal control bus to transfer a first snoop status value;

a third transistor having a first current terminal coupled to the third data buffer for receiving the output of the third data buffer, a second current terminal, and a control terminal coupled to the internal control bus to receive a third one of the plurality of snoop status control signals; and

a fourth transistor having a first current terminal coupled to the second current terminal of the third transistor, a second current terminal, and a control terminal coupled to the internal control bus to receive an fourth one of the plurality of snoop status control values.

6. The method of claim 5 wherein the status value is selectively modified by the status memory to indicate the second memory location is accessed by the external address value and the status value is selectively modified to indicate the first memory location is concurrently accessed by the internal address value.

7. A cache controller, comprising:

an external address bus for communicating an external address value;

an internal address bus for communicating an internal address value;

a first cache tag memory having a first memory location, the first memory location being accessed by the external address value, the first cache tag memory being coupled to the external address bus for receiving the external address value;

a second cache tag memory having a second memory location, the second memory location being accessed by the internal address value, the second cache tag memory being coupled to the internal address bus for receiving the internal address value;

an execution unit for providing an internal control value;

an internal control bus for transferring the internal control value; and

a cache control logic circuit coupled to the internal control bus for communicating the internal control value, coupled to the internal address bus for communicating the internal address value, coupled to the external address bus for communicating the external address bus, the cache control logic circuit, and coupled to the status memory for providing both a plurality of data status control signals and a plurality of snoop status control signals; and

a status memory for storing a status value, the status value for providing status information to both the first memory location of the first cache tag memory and the second memory location of the second cache tag memory, the status memory selectively changing the status value to provide a modified status value when the first memory location is accessed by the external address value and the second memory location is concurrently accessed by the internal address value, the status memory comprising:

a first data buffer having a first input coupled to the cache control logic circuit for receiving a first one of the plurality of data status control signals, the first data buffer having a second input coupled to the cache control logic circuit for receiving a second one of the plurality of data status control signals, and the first data buffer having an output;

a second data buffer having a first input coupled to the cache control logic circuit for receiving the first one of the plurality of data status control signals, the second data buffer having a second input coupled to the cache control logic circuit for receiving a third one of the plurality of data status control signals, the second data buffer having an output;

a first sense amplifier coupled to the first data buffer for receiving the output of the first data buffer, the sense amplifier coupled to the cache control logic circuit to transfer a first data status value;

a first transistor having a first current terminal coupled to the first data buffer for receiving the output of the first data buffer, a second current terminal, and a control terminal coupled to the cache control logic circuit to receive a fourth one of the plurality of data status control signals;

a second transistor having a first current terminal coupled to the second current terminal of the first transistor, a second current terminal, and a control terminal coupled to the cache control logic circuit to receive a fifth one of the plurality of data status control values;

a status bit cell having a first terminal coupled to the second current terminal of the second transistor and having a second terminal;

a third data buffer a first input coupled to the cache control logic circuit for receiving a first one of the plurality of snoop status control signals, the third data buffer having a second input coupled to the cache control logic circuit for receiving a second one of the plurality of snoop status control signals, and the third data buffer having an output;

a fourth data buffer having a first input coupled to the cache control logic circuit for receiving the first one of the plurality of snoop status control signals, the fourth data buffer having a second input coupled to the cache control logic circuit for receiving a second one of the plurality of snoop status control signals, the fourth data buffer having an output;

a second sense amplifier coupled to the third data buffer for receiving the output of the third data buffer, the sense amplifier coupled to the cache control logic circuit to transfer a first snoop status value;

a third transistor having a first current terminal coupled to the third data buffer for receiving the output of the third data buffer, a second current terminal, and a control terminal coupled to the cache control logic circuit to receive a third one of the plurality of snoop status control signals; and

a fourth transistor having a first current terminal coupled to the second current terminal of the third transistor, a second current terminal, and a control terminal coupled to the cache control logic circuit to receive an fourth one of the plurality of snoop status control values.

Description Submit all comments and votes

CROSS REFERENCE TO RELATED APPLICATION

This application is related to a commonly assigned copending patent application filed simultaneously herewith and entitled:

"A METHOD FOR PERFORMING CACHE ACCESSES WITH A PIPELINED BUS" by Gene W. Shen et al., Ser. No. 07/829,095.

FIELD OF THE INVENTION

This invention relates generally to a cache memory system, and more particularly to a cache controller in a cache memory system.

BACKGROUND OF THE INVENTION

In the electronics industry, multi-processing systems have been developed to enable a user of a system to manipulate and process information more quickly and efficiently. A multi-processing system generally includes two or more data processors which are interconnected with a system interface bus to a shared memory array. Each of the data processors may contain a data cache to reduce the amount of data transferred between each component of the multi-processing system and to improve access times from the data processors to the memory array. Generally, the data cache includes a cache controller, a data tag cache, and a snoop tag cache. The data tag cache unit services internal memory requests from execution units in the data processor to determine whether an information value is currently being stored in the data cache. The data tag cache may also indicate if an information value stored in the data cache is valid. The snoop tag cache unit monitors, or "snoops," transactions on the system interface bus to maintain data coherency between each element of the multi-processing system. Each information value modified by an external processor must be snooped in order to maintain data coherency throughout the entire multi-processing system. Additionally, the cache controller controls operation of the data cache.

In multi-processing systems, conflicts may occur during reading and writing operations which use the data tag cache and the snoop tag cache. In a first example, assume a first data processor attempts to read data currently resident in the data cache and a second data processor attempts to simultaneously change that data. When the first data processor reads the data, a predetermined address in the data cache tag is accessed to indicate, or "point to" an address location of the data in the data cache. Similarly, when the second data processor attempts to change that data, the snoop tag cache also points to the address location in the data cache. When the same address location is accessed by the data tag cache and the snoop tag cache simultaneously, a potential for an error, or "collision" occurs. In this case, when the first data processor attempts to read the cached data at a predetermined address in the data cache tag while the second data processor attempts to write to the address, a "read/write" collision occurs.

A second example of a conflict, referred to as a "dual write collision," occurs when both data processors attempt to modify the same data simultaneously. A "dual read collision" in which both data processors attempt to read the same data may also occur. However, because a read operation generally does not modify the contents of the data cache, no error occurs. In some situations, a read operation may modify state information corresponding to the data.

Read/write and dual write collisions adversely affect the operation and performance of a multi-processing system. When a collision occurs, the cache controller typically processes the collision as an error. Therefore, rather than performing a function specified by a user of the multi-processing system, the cache controller must enable the data processor to respond to the error and subsequently provide an indeterminate response to the user. Additionally, read/write and dual write collisions are difficult to predict in a multi-processing system and, therefore, may not be easily anticipated or corrected. For more information relating to techniques used to control collisions in a multi-processing system, refer to an article entitled "Multiprocessor Cache Synchronization-Issues, Innovations, Evolution" and published on pages 424 through 433 of the IEEE Transactions on Computers in 1986. The article was written by Philip Bitar and Alvin M. Despain. Additionally, refer to a technical paper entitled "Efficient Synchronization Primitives for Large-Scale Cache-Coherent Multiprocessors" and published in the proceedings of the Third International Conference on Architectural Support for Programming Languages and Operating System on pages 64 through 75. The paper was written by James R. Goodman, Mary K. Vernon, and Philip J. Woest.

Therefore, a need exists for a cache controller which is able to resolve read/write and dual write collisions quickly and efficiently. The cache controller should also be able to fully execute each type of operation specified during a collision. For example, in a read/write collision, both the read and the write operations should be executed to provide a correct result.

SUMMARY OF THE INVENTION

The previously mentioned needs are fulfilled with the present invention. Accordingly, there is provided, in one form, a cache controller. The cache controller includes a first bus interface for coupling the cache controller to a first bus and a second bus interface for coupling the cache controller to a second bus. A first cache tag memory array is coupled to the first bus interface. The first cache tag memory array has a predetermined number of entries, each of which corresponds to an unique entry in a data memory array external to the cache controller. A second cache tag memory array is coupled to the second bus interface means. The second cache tag memory array includes the predetermined number of entries, each of which corresponds to an unique entry in the data memory array. A status memory array is coupled to both the first and second cache tag memory arrays. The status memory array comprises the predetermined number of entries, each of which corresponds to an unique entry in the first cache tag memory array and to an unique entry in the second cache tag memory array.

These and other features, and advantages, will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawing. It is important to note the drawings are not intended to represent the only form of the invention.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 illustrates in block diagram form a multi-processing system having a data cache unit in accordance with the present invention;

FIG. 2 illustrates in block diagram form the data cache unit of FIG. 1;

FIG. 3 illustrates in block diagram form a tag unit of FIG. 2 in accordance with the present invention;

FIG. 4 illustrates in partial logic diagram form a status array bit cell circuit of FIG. 3;

FIG. 5 illustrates in timing diagram form address and data bus activity during cache tag write operations in accordance with the present invention;

FIG. 6 illustrates in timing diagram form both a typical pipelined instruction flow and a resource pipelined instruction flow in accordance with the present invention;

FIG. 7 illustrates in timing diagram form a status flow of both a write/read collision operation and a read/write collision operation in accordance with the present invention;

FIG. 8 illustrates in timing diagram form a status flow of both a dual write collision operation and a dual read collision operation in accordance with the present invention; and

FIG. 9 illustrates in state diagram form a state machine for executing a snoop cache tag write operation in accordance with the present invention.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

The present invention provides a cache controller for a multi-processing system. In the implementation of the invention described herein, the cache controller efficiently resolves "collisions" which occur when a particular address location in a data cache memory array is accessed by a plurality of data processors simultaneously. A first technique referred to as "resource pipelining" and a second technique referred to as "status forwarding"are each used to allow the cache controller to efficiently resolve such collision situations. Both techniques will be subsequently discussed in further detail. Additionally, by splitting a pipelined bus into separate address and data tenures and recognizing each as a separate tenure, more information may be processed. As well, snoop operations of a particular cache may be performed without being lost or slowed by write operations to the same cache. The cache controller also maintains data coherency in the data cache memory array and any other memory array in the multi-processing system.

FIG.1 illustrates a multi-processing system 10 which provides an implementation of the claimed invention as described herein. Of course, multi-processing system 10 is provided by way of example only and is not intended to represent the only implementation of the claimed invention. Multi-processing system 10 generally includes a memory system 12, a processor A 20, and a processor B 21. In one particular embodiment, both processor A 20 and processor B 21 may be implemented as a single integrated circuit such as a MC88110 which is available from Motorola, Inc. of Austin, Tex. The MC88110 is able to function both in a uni-processor and multi-processor environment. As is explained below, the MC88110 also provides a system for efficiently performing cache accesses, even in a multi-processing situation in which an address location in an on-board data cache is accessed simultaneously by two or more data processors.

Although both processor A 20 and processor B 21 are implemented as MC88110 RISC processors in this embodiment of the invention, only processor B 21 is shown in detail. Processor B 21 generally includes a clock logic circuit 22, a bus interface unit 23, an execution unit 24, a data cache unit 26, an instruction cache unit 28, a sequencer 30, and a load/store unit 32.

During operation, an Address Bus 14 is connected to an address input of each of memory system 12, processor A 20, and processor B 21 to provide a signal labelled "External Address." The External Address signal transfers an external address which is typically n bits wide, where n is an integer. In the example described herein, the external address is thirty-two bits wide, and, therefore, n is also equal to thirty-two. Similarly, a Data Bus 16 is connected to a data input of each of memory system 12, processor A 20, and processor B 21 to provide an "External Data" signal. The External Data signal transfers an external data value which is typically m bits wide, where m is an integer. As described herein, the external data value is sixty-four bits wide and, therefore, m is also equal to sixty-four. Additionally, a Control Bus 18 provides a plurality of control values to a first input of each of memory system 12, processor A 20, and processor B 21. The plurality of control values is necessary for each of memory system 12, processor A 20, and processor B 21 to function correctly together. Control Bus 18 provides a first portion and a second portion of the plurality of control values to memory system 12 and to processor A 20, respectively. Similarly, Control Bus 18 provides a third portion of the plurality of control values to processor B 21 via a signal labelled "External Control."

In processor B 21, the external address value is provided to a first plurality of address inputs of both data cache unit 26 and bus interface unit 23. Each of the plurality of inputs of data cache unit 26 receives a predetermined bit of the external address value and is labelled respectively. For example, a first one of the plurality of address inputs is labelled "EA0" and receives bit zero of the external address. Similarly, a last one of the plurality of address inputs is labelled "EA31" and is dedicated to receive bit thirty-one of the external address. Additionally, the external data value transferred via Data Bus 16 is provided to a bidirectional data terminal of bus interface unit 23. The External Control signal is also provided to bus interface unit 23.

Bus interface unit 23 serves as an interface between processor B 21 and the remaining components of multi-processing system 10. Bus interface unit 23 is coupled to data cache unit 26 to provide an external address value and receive an external data value. The external address value is provided via a Data Cache Address bus and the external data value is received via a Data Cache Data bus. Similarly, bus interface unit 23 is coupled to instruction cache unit 28 to provide the external address value via an Instruction Cache Address bus and the external data value via an Instruction Cache Data bus. The External Control signal enables bus interface unit 23 to communicate either address or data information at an appropriate point in time.

Additionally, a "Clock" signal, transferred via Control bus 18, is provided to a clock logic circuit 22. Clock logic circuit 22 provides a plurality of clock signals respectively labelled "T1," "T2," "T3," and "T4." Each of the plurality of clock signals represents a single phase of a four phase clock period and is provided to each of the respective components of processor B 21. Although the routing of each of the clock signals is not shown in detail in FIG. 1, such routing is commonly known and should be readily understood by one with ordinary skill in the art.

Execution unit 24 communicates both a n-bit wide internal data value and a plurality of control signals to a bidirectional Internal Data bus 25 and a bidirectional Internal Control bus 27, respectively. Internal Data bus 25 is connected to a first data input of both load/store unit 32 and sequencer 30 to transfer the internal data value to and from execution unit 24. Similarly, Internal Control bus 26 is connected to a plurality of control inputs of both load/store unit 32 and sequencer 30 to transfer the plurality of internal control signals to and from execution unit 24.

Sequencer 30 is connected to a plurality of address inputs of instruction cache unit 28 to provide an n bit wide signal labelled "Internal Instruction Address." Although the Internal Instruction Address signal is the same width as the external address value in this implementation of the invention, the Internal Instruction Address signal might also have a different bit width than the external address value. Sequencer 30 is also connected to a second plurality of bidirectional data inputs of instruction cache unit 28 to provide a signal labelled "Internal Instruction Cache Data." The Internal Instruction Cache Data signal communicates internal data between sequencer 30 and instruction cache unit 28. Additionally, sequencer 30 is connected to a plurality of bidirectional control inputs of instruction cache unit 28 to provide a plurality of control signals collectively labelled "Instruction Cache Control."

Instruction cache unit 28 is accessed during execution of a software routine to quickly provide instructions and reduce an amount of processing time generally required to fetch instructions. In response to the internal data and control signals provided by execution unit 24, sequencer 30 accesses a predetermined address location in instruction cache unit 28 via the Internal Instruction Address signal such that a next instruction to be processed by execution unit 24 may be provided. If an instruction stored at the predetermined address location is valid and is correctly accessed, the instruction cache unit 28 provides both the accessed instruction and a next instruction to sequencer 30 via the Internal Instruction Cache Data signal. Sequencer 30 then provides the two instructions to execution unit 24 to be processed. If the instruction had not been stored in instruction cache unit 28, execution unit 24 would have been required to access the instruction from another source (not shown herein).

Load/store unit 32 is connected to a second plurality of address inputs of data cache unit 26 to provide the Internal Data Address signal. Load/store unit 32 is also connected to a second plurality of