Cache Access System for Multiple Requestors Providing Independent Access to the Cache Arrays

This invention relates to data processing systems using cache memories, and more particularly to systems for processing multiple access requests to the cache memories.

Cache systems are conventionally used with CPU's of all types to increase memory access speed. A conventional cache memory is interposed between the CPU and the main memory. The cache memory has a smaller capacity but a lower access time than the main memory. The cache memory, therefore, is used whenever possible, to satisfy a processor request.

Conventional cache memories include a STORE array for storing data, instructions, etc., and a TAG array for identifying the addresses in main memory from which the data in the STORE array was obtained. During an access request, the TAG array is first accessed to determine whether the information sought is in the STORE array. Access to the TAG array may be made using a multibit address which corresponds to a portion of an address in the main memory. If the sought after instruction is in the STORE array, the same multibit address used to access the TAG array can be used to access the required information in the STORE array.

Multiprocessor systems have become very popular recently. Such systems are used in a parallel processing environment. In order to increase the speed of such systems, each CPU can have its own cache memory. The cache memories are connected to a common main memory. Such a configuration leads to multiple requests of each cache memory. These requests must be processed efficiently and accurately for the system to operate properly. This task is complicated by the fact that separate requests can be made for access to the TAG array and to the STORE array. In order to enhance processing time, these separate requests should preferably be processed independently.

One object of the present invention is to provide an access system for a cache memory which enables effective and efficient access so as to enhance processor speed.

Another object of the present invention is to provide a cache memory access system which processes TAG array access requests and STORE array access requests independently whenever possible.

A further object of the present invention is to provide a cache memory access system which provides sequential access to a TAG array and a data array based on the same address information.

In accordance with the above, the present invention is an apparatus comprising first and second addressable arrays and an input for receiving address information related to the arrays. A first request line receives from a first source first request signals for access to the first and second arrays based on the address information. A second request line receives from a second source second request signals for access to the first and second arrays based on the address information. A processing circuit transmits the address information to the first and second addressable arrays in response to the first and second request signals based on a priority of the first and second request signals.

First and second latches are provided for latching the address information related to the first and second request signals.

In accordance with other aspects, the invention is an apparatus comprising a cache memory having an independently accessible TAG array and an independently accessible STORE array. An address input receives address signals related to the TAG and STORE arrays and a plurality of access request lines receive access request signals from different sources. A latch is associated with each access request line for latching address information on the address line. The address information is selectively passed by one circuit to the TAG array and by another circuit to the STORE array.

The foregoing and other objects of the invention will become more readily apparent as the invention becomes more fully understood based on the detailed description below, reference being had to the accompanying drawings in which like reference numerals represent like parts and in which:

FIG. 1 is block diagram of a multiprocessor system according to the present invention;

FIG. 2 is a block diagram depicting the operation of the cache memory access system of the present invention;

FIG. 3 is schematic diagram of the request storage and multiplex circuits of FIG. 2;

FIG. 4 is a block diagram of the priority based multiplex control of FIG. 2; and

FIG. 5 is a schematic diagram of one access block of FIG. 4.

FIG. 6 is a flowchart showing the method of operation.

FIG. 1 shows a multiple CPU multiple cache processing system 10. System 10 includes 3 CPU's 12, 14 and 16 connected to respective cache memories 18, 20 and 22 through buses 24, 26, and 28, respectively. The caches 18, 20, 22 are connected to a main memory 30 through a common bus system 32. Memory 30 can communicate with an external storage device such as a disk, tape, drum or the like 34.

System 10 is set up so that each cache 18, 20, 22 can receive three types of access requests. One such request comes from the associated CPU 12, 14, 16 and is referred to as a processor request. A second type of request, known as a command request, is generated by a global control processor 31 and relates to the operation of the cache itself in connection with memory 30. Various types of cache systems are known in the art. The type used in the present system is called a copyback cache. This operates by storing all available data for the associated CPU and transferring the stored data to the main memory 30. Each storage location of the cache contains a status bit which is set when the information in that location is updated but yet not transferred to the main memory 30. Periodically, such as at the end of a processing cycle, a global control processor 31 requires modified information to be transferred to the main memory 30. Such a transfer results in a command access to the cache. Finally, each cache monitors bus 32 to determine if a request is being made of memory 30 for data which is updated and stored only in the monitoring cache. This operation is referred to as "bus watching" and results in a data intervention signal being asserted to prevent access to memory 30 so that the required data can be supplied by the cache having the data. These operations are conventional and will not be discussed in further detail.

FIG. 2 shows a block diagram of the circuit 201 of the present invention. One such circuit 201 is provided within each cache 18, 20, 22. The circuit of FIG. 2 includes a processor request processing block 50, a command request processing block 52 and a bus watch request processing block 54. Each of these blocks 50, 52 and 54 receives address information from an address bus 56 which contains the address of the location to be accessed. Each block 50, 52 and 54 also contain a pair of request inputs for requesting access either to TAG array 58 or data array 60. As is conventional in cache memories, TAG array 58 contains a plurality of addressable registers which indicate which addresses of main memory 30 are stored in corresponding addressable registers of data array 60. This information is transmitted through cache controller 62 which is responsible for identifying a hit to determine whether the request can be serviced by accessing DATA array 60 rather than main memory 30.

Each of the blocks 50, 52 and 54 requires two inputs since the TAG array 58 and data array 60 are individually accessible. Request line 64 of processor request block 50 indicates a request for access to TAG array 58 whereas request line 66 is a request for access to data array 60. Similarly, request line 68 indicates a command request for TAG array 58 and request line 70 indicates a command request for data array 60. Finally, a signal on line 72 indicates a bus watch request for TAG array 58 and a signal on line 74 indicates a bus watch request for access to data array 60. The DATA array access requests can be generated by cache control 62 if a hit is detected in TAG array 58. Such operation is conventional and will not be discussed in detail here.

The address information from the various processing blocks 50, 52 and 54 is passed to a pair of multiplexers 80 and 82 which are operated by multiplex controllers 84 and 86. The address information received on bus 56 is the same for each block 50, 52 and 54. These blocks serve to store the address data and pass it to the appropriate multiplexer along buses 56A, 56B, 56C, 56D, 56E and 56F depending on the asserted request signal on lines 64, 66, etc. Blocks 50, 52 and 54 also ensure that the address data sent to multiplexer 82 is first channelled to multiplexer 80, as will be discussed below.

The multiplexers 80 and 82 are controlled by multiplex select controllers 84 and 86 through multiplex select lines 87A-87F to activate multiplexers 80 and 82 to cause these multiplexers to pass address data respectively from buses 56A-56F to a pair of decoders 90 and 92 which then access the appropriate locations in arrays 60 and 58, respectively.

Multiplex controllers 84 and 86 operate according a predetermined priority. For example, bus watching requests may be given highest priority in which case a bus watch TAG access request on line 72 or bus watch data access request on line 74 would be processed first resulting in TAG array multiplex select line 87E or DATA array multiplex select line 87F being asserted to cause multiplexers 80 and 82 to pass address data on buses 56E or 56F to multiplexer output buses 81 and 83, respectively. It should be understood that multiplex controllers 84 and 86 operate independently so that the TAG array 58 and DATA array 60 may be accessed simultaneously.

FIG. 3 shows schematically the processor request block 50, the command request block 52, the bus watch block 54 and multiplexers 80 and 82 together with related circuitry. It should be understood that the diagram of FIG. 3 relates to a single bit line 56.sub.1 of address bus 56. This circuitry, therefore, must be duplicated for each bit line of the address bus.

As shown in FIG. 3, bus watch processing block 54 comprises FET 100 which has, its drain connected to address bit line 56.sub.1 and its source connected an inverting latch 102. The gate of FET 100 is connected to the bus watch TAG array access request line 72. The inverting latch 102 output is passed to an inverter 103 as well as to bit line 56E.sub.1 which is a single bit line of bus 56E. This bit line is input to multiplexer 80. The output of inverter 103 is connected to the drain of a second FET transistor 104 whose gate is connected to bus watch data array request line 74 and whose source is connected to a second inverting latch 106. The output of inverting latch 106 is connected to bit line 56F.sub.1 which is one bit line of bus 56F. This bit line leads to multiplexer 82.

Multiplexers 80 and 82 are shown in FIG. 3 as comprising a plurality of CMOS switches controlled by respective multiplex select lines. For example, bit line 56E is connected to the input of CMOS switch 110 and DATA array multiplex select line 87E is connected to the complementary inputs of switch 110 through line 112 and inverter 114. Similarly, line 56F.sub.1 is connected to the input of switch 116 and TAG array multiplex select line 87F is connected to opposite gates of the switch through line 118 and inverter 120. The output of switch 110 is received on line 122 and the output of switch 116 is received on line 124. Command block 52 operates in a manner similar to bus watch block 54 with TAG bit line 56.sub.1 forming an input to FET transistor 130, the output of transistor 130 latching inverting latch 132, the output of latch 132 being provided to the input of inverter 134 and to CMOS switch 136 through line 56C.sub.1, the output of inverter 134 being provided to the input of transistor 140 whose output is connected to inverting latch 142. The output of latch 142 is provided to a CMOS switch 144. Transistors 130 and 140 are controlled by command TAG array request line 68 and command DATA array request line 70, respectively. Switch 136 is connected to line 122 and switch 144 is connected to line 124.

Processor block 50 has essentially the same construction with one minor variation. In block 50, a transistor 160 has its input connected to address bit line 56.sub.1 and its output connected to inverting latch 162, its gate being controlled by processor TAG request line 64. In addition, latch 162 receives an input from line 166 which is the output of a transistor 168. The gate of transistor 168 is connected to a speed path TAG access request line 170 and its input is connected to a speed path address bit line 172.sub.1 which is one bit line of an address bus used for speed path functions. The remainder of block 50 is the same as blocks 52 and 54 with the output of inverting latch 162 connected to the input of inverter 174 and to a CMOS switch 176 through line 56A.sub.1. The output of inverter 174 is connected to the input of transistor 178 whose gate is controlled by DATA multiplex select line 66. The output of transistor 178 is connected to a second inverting latch 180 whose output is connected to the input of CMOS switch 182. The gates of switch 176 are controlled by TAG multiplex select line 87A and the gates of switch 182 are controlled by DATA array multiplex select line 87B.

Speed paths are sometimes provided in processors to enhance processing speed under certain conditions. The present invention is adapted for use in such an environment and includes the speed path address bus 172 of which line 172.sub.1 is a single bit line. In addition to being connected to transistor 168, line 172.sub.1 is connected to the input of a CMOS switch 190 and to the input of a CMOS switch 192. Switch 190 is controlled by a TAG multiplex select line 194 and switch 192 is connected by a DATA array multiplex select line 196. During speed path operation, the processor causes an address to be passed along bus 172, activates line 172 and activates line 194 or line 196 depending on whether access is requested to the TAG array or DATA array. The speed line bypasses latch 162, inverter 174, transistor 178 and latch 180 thereby eliminating the inherent delays caused by the elements. However, in the event that the appropriate switch 190 or 192 has not been actuated by the multiplexer, switch 168 also passes the speed path address data to the input to latch 162 so that the address information can be stored and processed in turn. With this configuration, a speed path is used if available but, if not available, the normal processing path is used.

Another feature of the circuit in FIG. 3 is the generation of a command hit or processor hit signal on lines 200 or 202, respectively, in the event that a bus watch TAG access request occurs at the same time and for the same address as a command TAG access request or a processor TAG access request. The circuit comprises an exclusive OR gate 204 which receives one input from line 56E.sub.1 and a second input from line 56C.sub.1. Accordingly, the output of exclusive OR gate 204 on line 210 is held low when the signals at its input are the same, and transistor 214 is held off. If a high signal is asserted on compare enable line 216, transistor 218 is turned on causing command hit line 200 to go low when transistor 214 is also on. Accordingly, a high signal in line 200 when a compare enable signal is asserted indicates a command hit. A command hit line 200 is provided for each bit of the address bus so that if all command hit lines are high at the same time when the compare enable line is high, a hit is indicated.

The operation is similar for exclusive OR gate 220 which receives inputs from line 56E.sub.1 and 56A.sub.1 and provides an output through line 222 to transistor 226. Transistor 228 is responsive to the signal on compare enable line 216. If the output of exclusive OR gate 220 is low, transistor 226 is turned off causing processor hit line 202 to remain high if a signal is asserted on compare enable line 216. A single command hit line 200 is connected to each bit of the address bus so that any unmatch-compare of any bit when the compare enable line is high will cause the command hit line to go low, otherwise, if the command hit line remains high, a hit is indicated.

Command hit signals and processor hit signals are provided to the global control processor to indicate that accesses to the DATA and TAG arrays must be serialized. In other words, in the absence of a hit signal, it is possible to carry out several operations, such as a read operation and a write operation in the same location in the DATA array. However, if concurrent requests are being made, all operations must be serialized.

FIG. 4 shows one multiplex controller of FIG. 2. It will be assumed that the controller in FIG. 4 is multiplex controller 84, it being understood that controller 86 has an identical configuration.

Controller 84 contains three access blocks 310, 320 and 330. The outputs of the access blocks comprise multiplex select lines 87F, 87B, and 87D. Each block also has a clock input which accepts clock pulses on line 332 for synchronization. Each block also has an enable input to accept an enable signal on a respective enable line 334, 336 or 338. Each block also has a reset input to accept a reset signal on line 340.

Each block also has a request input to receive a respective access request signal. Block 310 receives bus watch DATA array access request line 74, block 320 receives processor DATA array request line 66 and block 330 receives command DATA array access request line 70. Each block also has a BUSY input which receives a high signal to prevent that block from producing an output.

It will be seen that the BUSY input to block 310 is grounded so that block 310 is always enabled to produce an output on line 87F whenever it receives a request on line 74. The BUSY input of block 320 receives as its input request line 74 so that block 320 is prevented from producing an output on line 87B whenever a request is being made to block 310.

Each block also has a wait output which is asserted whenever that block has received a request on its request input and a high signal on its BUSY input and has not yet serviced that request. The BUSY input of block 330 receives the output on line 340 from an OR gate 342. The input to the OR gate comprises lines 74 and 66 as well as line 344 from the wait output of block 320. Accordingly, the BUSY input of block 330 receives a high signal whenever a request is being made to block 310, a request is being made to block 320, or block 320 is in a wait state.

As will be understood, the connections discussed above produce a priority response in which bus watch access requests on line 74 are processed with highest priority, processor requests on line 66 are processed with second highest priority, and command requests on line 70 have lowest priority.

FIG. 5 shows a circuit which is duplicated in each of the blocks 310, 320 and 330. For ease of reference, it will be assumed that FIG. 5 is the circuit of block 320, it being understood that the other blocks have the same circuits.

As seen in FIG. 5, request line 66 is input to a CMOS switch 360 whose output is passed along line 362 to inverter 364. The output of inverter 364 is received at the output of a second CMOS switch 366 whose output is passed along line 368 to an inverted input of a AND gate 370.

One gate of switch 360 is connected to line 336 and the complementary gate is connected through inverter 372 to line 336 so that a high signal line on line 336 opens switch 360 to pass a request signal on line 64 to inverter 364 which passes the signal to switch 366. One gate of switch 366 is connected to clock line 332 while a complementary input is connected through inverter 374 to clock line 332. The clock pulse is a bi-phase clock pulse so that switch 366 is opened on positive going half cycles to pass the output of inverter 364 to line 368.

The other input of AND gate 370 is the inverted signal on line 74. Therefore, it can be seen that if line 74 is low, request signals on line 66 are passed directly to line 87F during positive clock pulses when the enable signal is asserted.

When the BUSY input is high, the signal on line 74 is inverted by inverter 380 and passed to an inverting input of AND gate 382. The other input of gate 382 is the inverted signal on line 368. The output of AND gate 382 is wait line 344. This line is passed to the input of a CMOS switch 390 whose output is connected to the input of inverter 364. One gate of switch 390 is connected to the output of inverter 374 and the complementary gate is connected clock line 332 so that switch 390 is activated to pass the signal on line 344 to inverter 364 during negative half cycles of the clock signal on line 332.

As will be understood from FIG. 5, a request received on line 66 during the presence of a BUSY signal on line 74 causes the request signal to be latched onto line 368. This latching takes place due to the high signal on BUSY line 74 in conjunction with the high signal on request line 66 resulting in a high output of AND gate 382 during a positive clock signal half cycle. The high output of AND gate 382 is returned during negative clock half cycles through switch 390 to maintain a high request signal on line 362. It will be understood that finite time is required for the output of a CMOS switch to decay when the switch is turned off. Thus, a high signal on the input of switch 390 causes a high output of switch 390 during negative half cycles and the output decays slowly during positive half cycles when switch 390 is turned off. As a consequence of this slow decay and the clock speed, whenever line 344 is high, the output of switch 390 appears to be continuously high causing the output of inverter 364 to be continuously low. This results in the output of switch 366 being continuously low to maintain a low signal at the inverting inputs of gates 370 and 382. When the BUSY signal on line 74 is deasserted, the output of gate 370 goes high asserting the signal on line 87F. At the same, the output of gate 382 goes low causing the output of switch 390 to go low at the next negative clock cycle.

As will also be understood, a reset signal on line 340 causes line 362 to go low by turning on FET 396. This resets the signal on line 87F to a low state.

As will also be understood, an enable signal should asserted on line 336 whenever it is desired that the system respond to bus watch access request.

Returning to FIG. 4, it can be seen that more or less access blocks can be provided depending on the number of possible access requests. Also, blocks can be disabled individually if it is desired to eliminate responses to certain access requests. The enable and reset lines of each block 310, 320 and 330 are controlled from the associated microprocessor in a manner which would be readily apparent to one skilled in the art.

The foregoing has been set forth to illustrate the present invention but is not deemed to limit the scope of protection being sought. It is clear the numerous addition, modifications and other changes could be made to the invention without departing from the scope of the appended claims.