Cache coherency scheme for XBAR storage structure with delayed invalidates until associated write request is executed

Claims

We claim:

1. In a data processing system having a first storage controller and at least one other storage controller(s) wherein the first storage controller has a first local memory element that may contain a first copy of a data block and wherein each of the at least one other storage controller(s) have a local memory element contained therein that may contain a second copy of the data block, the first storage controller being able to execute a local write instruction to the first local memory element and further having the capability to execute a remote write to the local memory element(s) contained within the at least one other storage controllers(s), the improvement comprising:

a. an XBAR interface block coupled to the first storage controller and further coupled to the at least one other storage controller(s), said XBAR interface block providing an interface between the first storage controller and the at least one other storage controller(s);

b. an invalidate request block coupled to the first storage controller for generating an invalidate request when the first storage controller executes a write instruction;

c. a write request block coupled to the first storage controller for generating a write request when the first storage controller executes a write instruction; and

d. delaying means coupled to said XBAR interface block for delaying the transmission of the invalidate request to the at least one other storage controller(s) until said XBAR interface block transmits the write request to a selected one of the at least one other storage controller(s).

2. An improvement according to claim 1 wherein said invalidate request block further generates an invalidate address when the first storage controller executes a write instruction.

3. An improvement according to claim 2 wherein said write request block further generates a write address when the first storage controller executes a write instruction.

4. An improvement according to claim 3 wherein said delaying means does not delay the transmission of the invalidate request when the write instruction is a local write instruction.

5. An improvement according to claim 4 wherein said delaying means does not delay the transmission of the invalidate request when the write request has already been transmitted to the selected one of the at least one other storage controller(s) by the XBAR interface block.

6. An improvement according to claim 5 wherein the at least one other storage controller(s) comprise invalidate means for invalidating the second copy of the data block contained in the local memory element(s) therein when the second copy of the data block matches the invalidate address.

7. An improvement according to claim 6 wherein said invalidate means comprises an invalidate duplicate tag block.

8. An improvement according to claim 7 wherein a at least one first processing element(s) is coupled to said first storage controller; said at least one first processing element(s) initiating the write instruction.

9. An improvement according to claim 8 wherein said at least one first processing element(s) initiating the write instruction by providing a write request and a write address to said write request block and by further providing an invalidate request and invalidate address to said invalidate request block.

10. An improvement according to claim 9 wherein said at least one first processing element(s) comprises an instruction processor.

11. An improvement according to claim 9 wherein said at least one first processing element(s) comprises an input/output element.

12. An improvement according to claim 10 wherein a at least one second processing element(s) is coupled to each of said at least one other storage controller(s); said at least one second processing element(s) accessing said local memory element in a corresponding one of said at least one other storage controller(s).

13. An improvement according to claim 12 wherein said at least one second processing element(s) are prohibited from accessing the second copy of the block of data contained in a corresponding one of the local memory element(s) if the second copy of the block of data has been invalidated by said invalidating means.

14. An improvement according to claim 13 wherein said at least one second processing element(s) comprise an instruction processor.

15. An improvement according to claim 13 wherein said at least one second processing element(s) comprise an input/output element.

16. An improvement according to claim 14 wherein said write request block further comprises a remote out queue wherein said remote out queue services the write requests provided by said at least one first processing element(s) in a predetermined order.

17. An improvement according to claim 16 wherein said invalidate request block further comprises an invalidate out queue wherein said invalidate out queue services the invalidate requests provided by said at least one first processing element(s) in a predetermined order.

18. An improvement according to claim 17 wherein said remote out queue triggers the invalidate out queue thereby ensuring that said write request is processed before said invalidate request.

19. An improvement according to claim 18 wherein said delaying means comprises a remote in queue wherein said remote in queue receives at least one write request from said at least one remote out queue(s) of said at least one first processing element(s) and services the at least one write request(s) in a predetermined order.

20. An improvement according to claim 19 wherein said delaying means further comprises an invalidate in queue wherein said invalidate in queue receives at least one invalidate request from said at least one invalidate out queue(s) of said at least one first processing element(s) and services the at least one invalidate request(s) in a predetermined order.

21. An improvement according to claim 20 wherein said remote in queue triggers the invalidate in queue thereby ensuring that a selected write request is processed before a selected invalidate request.

22. An improvement according to claim 21 further comprising:

a. an invalidate acknowledge block coupled to the at least one other storage controller(s) for providing a corresponding at least one invalidate acknowledge signal(s) in response to said invalidate request; said invalidate acknowledge block providing said at least one invalidate acknowledge signal(s) to said XBAR interface block;

b. providing means coupled to said delaying means for providing an anticipatory acknowledge signal to the first storage controller when said delaying