Deadlock resolution with cache snooping

Abstract

A device for resolving deadlock between a local processor and system resources for access to a local store in a multiprocessor data processing system having high speed cache comprises an address storage device, deadlock resolution logic and a deadlock detector. The address storage device is coupled to the local bus for storing addresses in response a local store access signal on the system bus and for supply of the address to the cache controller. The detector is connected to the local bus and system bus to detect a deadlock condition. The deadlock resolution logic generates a sequence of control signals in response to the deadlock signal that resolves the deadlock condition. In particular, deadlocks are resolved by tristating the local buffer in response to the deadlock signal to disable external access signals from controlling the local bus to allow a local store access signal to gain control of the local bus. If the local store access signal is a write access, the address of the write access is stored in the address store, and the local buffer is released from the high impedance state of allow the external access signal to control the local bus. After the external access signal completes, the address for the address store is supplied to the cache controller for performance of snooping function. If the local store access signal is a read access, then the local buffer is released from its high impedance state after the read access completes.

We claim: 
     
       1. A data processing apparatus comprising: a system bus;   a local bus;   system buffer means, having a first interface connected to the system bus and a second interface connected to the local bus, ±or buffering communication of local store access signals from the system bus to the local bus;   local storage means, coupled to the local bus, for storing data for read and write access in response to local store access signals on the local bus;   local processing means, having a local bus port, for processing data and supplying external access signals to the local bus port, the local processing means including   cache means, having a plurality of storage locations, for storing data retrieved from the local storage means in the plurality of storage locations, and   tag means, having a plurality of tag locations identified by addresses, for storing validity codes in tag locations for corresponding storage locations in the cache means,   tag search means, having a tag search input and coupled to the tag means, for determining the validity codes at tag locations in response to addresses and a tag search signal at the tag search input;   local buffer means, having a first interface connected to the local bus port on the local processor means and a second interface connected to the local bus, for buffering communication of external access signals from the local processor means to the local bus, the local buffer means including   means, having a tristate control input, for disabling the second interface in response to a tristate signal supplied to the tristate control input;   deadlock resolving means, coupled to the system bus and the local bus, for resolving deadlocks caused by local store access signals on the system bus and the external access signals on the local bus, including   address storage means, having a control input and coupled to the local bus, for storing in response to a store signal at the control input an address from a local store access signal on the local bus, for supply to the tag search means in response to a supply signal at the control input,   decoding means, connected to the local bus and the system bus, for generating a deadlock signal in response to a local store access signal on the system bus and an external access signal on the local bus,   logic means, connect to the tag search means, address storage means and the local buffer means, for generating the tristate signal, the store signal, the supply signal and the tag search signal in a control sequence, wherein the control sequence includes   asserting the tristate signal in response to the deadlock signal to disable the external access signal from controlling the local bus to allow a local store access signal from the system bus to gain control of the local bus,   if the local store access signal that gains control of the local bus is a write access, then asserting the store signal to store the address of the write access to the address storage means, and after the local store access signal completes the write access, then de-assetting the tristate signal to allow the external access signal to control the local bus, and after the external access signal completes, asserting the supply signal and the tag search signal to invalidate any location in the cache means storing data identified by the address of the write access, and   if the local store access signal that gains control of the local bus is a read access, then de-asserting the tristate signal after the read access completes.   
     
     
       2. The apparatus of claim 1, wherein the system buffer means includes a write access pipeline with at least one stage for storing a local store access signal for a write access pending completion of a preceding local store access, and wherein the decoding means generates the deadlock signal for a write access only when the write access pipeline is full. 
     
     
       3. The apparatus of claim 1, wherein the address storage means includes a plurality of address storage locations, and in the control sequence, the supply signal and tag search signal are repeated for each address stored in the address storage means. 
     
     
       4. The apparatus of claim 3, wherein the address storage means includes a first-in-first-out buffer. 
     
     
       5. The apparatus of claim 3, wherein the address storage means includes means for generating an overflow signal if the address storage means overflows, and the tag search means includes means receiving the overflow signal, for marking all tag locations invalid in response to the overflow signal. 
     
     
       6. The apparatus of claim 3, wherein the control sequence includes, before de-asserting the tristate signal after a local store access, a step of maintaining the tristate signal if the deadlock signal persists. 
     
     
       7. In a data processing system having a system bus, a local bus, a system buffer means, a local buffer means, and a local processing means, a method for resolving deadlocks caused by a local store access signal on the system bus and an external access signal on the local bus, said method comprising steps of: generating a deadlock signal in response to the local store access signal on the system bus and the external access signal on the local bus;   asserting a tristate signal in response to the deadlock signal to disable the local buffer means to allow the local store access signal to gain control of the local bus and execute a local store access operation;   if the local store access signal that gains control of the local bus is a write access to a given address, storing the given address in an address store;   de-asserting the tristate signal to allow the external access signal to control the local bus after the local store access signal completes its access operation; and   if the local store access signal that gained control of the local bus was a write access to the given address, supplying the given address stored in the address store to a tag search means, and asserting a tag search signal to invalidate any location in a cache means storing data identified by the given address after the external access signal completes.   
     
     
       8. The method of claim 7, wherein the system buffer means includes a write access pipeline with at least one stage for storing a local store access signal for a write access, and wherein the deadlock signal is generated for a write access only when the write access pipeline is full. 
     
     
       9. The method of claim 7, wherein the address store includes a plurality of address storage locations, and the method further comprises the steps of: after the step of de-asserting the tristate signal, generating the deadlock signal again if a local store access signal is on the system bus;   after completion of the external access, supplying all addresses stored in the address store to the tag search means; and   asserting the tag search signal in sequence to invalidate any location in the cache means storing data identified by the addresses stored in the address store.   
     
     
       10. The method of claim 9, further including the step of generating an overflow signal if the address store overflows, and wherein the tag search means includes means for receiving the overflow signal, for marking all tag locations invalid in response to the overflow signal. 
     
     
       11. The method of claim 9, including before the step of de-asserting the tristate signal, a step of maintaining the tristate signal if the deadlock signal persists.