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

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).

Claim 47

A method of ensuring data coherency 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 instruction to the local memory element(s) contained within the at least one other storage controller(s), comprising: a. providing a XBAR interface block coupling the first storage controller to the at least one other storage controller(s), the XBAR interface block providing an interface between the first storage controller and the at least one other storage controller(s); b. providing an invalidate request block coupled to the first storage controller for generating a invalidate request when the first storage controller executes a write instruction; c. providing 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 the transmission of the invalidate request to the at least one other storage controller(s) within the XBAR interface block until the XBAR interface block transmits the write request to a selected one of the at least one other storage controller(s).

Claim 48

A method of ensuring data coherency 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 instruction to the local memory element(s) contained within the at least one other storage controller(s), comprising: a. providing a XBAR interface block coupling the first storage controller to the at least one other storage controller(s), the XBAR interface block providing an interface between the first storage controller and the at least one other storage controller(s); b. providing an invalidate request block coupled to the first storage controller for generating a invalidate request when the first storage controller executes a write instruction; c. providing 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 the transmission of the invalidate request to the at least one other storage controller(s) within the XBAR interface block until the XBAR interface block transmits the write request to a selected one of the at least one other storage controller(s).

Claim 49

A method of ensuring data coherency 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 instruction to the local memory element(s) contained within the at least one other storage controller(s), comprising the steps of: a. providing an XBAR interface block coupling the first storage controller to the at least one other storage controller(s), the XBAR interface block providing an interface between the first storage controller and the at least one other storage controller(s); b. providing 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. providing a write request block coupled to the first storage controller for generating a write request when the first storage controller executes a write instruction; d. providing a write out queue, a write in queue, an invalidate out queue, and an invalidate in queue within the first storage controller and within each of the at least one other storage controller(s); e. providing a remote write queue and a remote invalidate queue within the XBAR interface block; f. providing an invalidate duplicate tag block within the first storage controller and the at least one other storage controller(s); g. waiting for the write request block within the first storage controller to generate a write request; h. capturing the write request in the write out queue within the first storage controller when step (g) detects the write request; i. waiting for the write out queue to service the write request captured in step (h); j. determining if the write request is to a memory within the first storage controller or to a memory within one of the at least one other storage controller(s) thereby determining if the write request is local or remote; k. routing a corresponding write address and write data to the local memory element within the first storage controller and perform a write therein if step (j) determines that the write request is local; l. placing an invalidate request into the invalidate out queue; m. waiting for the invalidate out queue to service the invalidate request; n. routing an invalidate address to the invalidate duplicate tag block within the first storage controller; o. determining if there is a match between the invalidate address and the contents of the invalidate duplicate tag block; p. invalidating the first copy of the data block if a match is found in step (o); q. performing steps (r)→(zz) if the write request is to a remote storage controller; r. sending the write request and the corresponding write address to the remote write queue within the XBAR interface block; s. sending the invalidate request and the corresponding invalidate address to the remote invalidate queue within the XBAR interface block; t. waiting for the remote write queue to service the write request; u. allowing the invalidate request to enter the remote invalidate queue when the remote write queue services the write request; v. routing the write request and the corresponding write address to the write in queue within a selected one of the at least one other storage controller(s); w. waiting for the remote invalidate queue to service the invalidate request; x. routing the invalidate request and the corresponding invalidate address to the invalidate in queue within the selected one of the at least one other storage controller(s); y. waiting for the write in queue to service the write request, and once serviced, route the corresponding write address to the local memory within the selected one of the at least one other storage controller(s) and performing a write thereon; z. routing the invalidate address to the invalidate duplicate tag block within the selected one of the at least one other storage controllers and determining of there is a match between the invalidate address and the contents of the invalidate duplicate tag block; and zz. invalidating the second copy of the data block if a match is found in step (z).

Claim 50

A method of ensuring data coherency 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 instruction to the local memory element(s) contained within the at least one other storage controller(s), comprising the steps of: a. providing an XBAR interface block coupling the first storage controller to the at least one other storage controller(s), the XBAR interface block providing an interface between the first storage controller and the at least one other storage controller(s); b. providing 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. providing a write request block coupled to the first storage controller for generating a write request when the first storage controller executes a write instruction; d. providing a write out queue, a write in queue, an invalidate out queue, and an invalidate in queue within the first storage controller and within each of the at least one other storage controller(s); e. providing a remote write queue and a remote invalidate queue within the XBAR interface block; f. providing an invalidate duplicate tag block within the first storage controller and the at least one other storage controller(s); g. waiting for the write request block within the first storage controller to generate a write request; h. capturing the write request in the write out queue within the first storage controller when step (g) detects the write request; i. waiting for the write out queue to service the write request captured in step (h); j. determining if the write request is to a memory within the first storage controller or to a memory within one of the at least one other storage controller(s) thereby determining if the write request is local or remote; k. routing a corresponding write address and write data to the local memory element within the first storage controller and perform a write therein if step (j) determines that the write request is local; l. placing an invalidate request into the invalidate out queue; m. waiting for the invalidate out queue to service the invalidate request; n. routing an invalidate address to the invalidate duplicate tag block within the first storage controller; o. determining if there is a match between the invalidate address and the contents of the invalidate duplicate tag block; p. invalidating the first copy of the data block if a match is found in step (o); q. performing steps (r)→(zz) if the write request is to a remote storage controller; r. sending the write request and the corresponding write address to the remote write queue within the XBAR interface block; s. sending the invalidate request and the corresponding invalidate address to the remote invalidate queue within the XBAR interface block; t. waiting for the remote write queue to service the write request; u. allowing the invalidate request to enter the remote invalidate queue when the remote write queue services the write request; v. routing the write request and the corresponding write address to the write in queue within a selected one of the at least one other storage controller(s); w. waiting for the remote invalidate queue to service the invalidate request; x. routing the invalidate request and the corresponding invalidate address to the invalidate in queue within the selected one of the at least one other storage controller(s); y. waiting for the write in queue to service the write request, and once serviced, route the corresponding write address to the local memory within the selected one of the at least one other storage controller(s) and performing a write thereon; z. routing the invalidate address to the invalidate duplicate tag block within the selected one of the at least one other storage controllers and determining of there is a match between the invalidate address and the contents of the invalidate duplicate tag block; and zz. invalidating the second copy of the data block if a match is found in step (z).

Claim 58

A method of accelerating the invalidate priority 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 instruction to the local memory element(s) contained within the at least one other storage controller(s), comprising: a. providing an XBAR interface block wherein said XBAR interface block is 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); said XBAR interface block having an invalidate request queue; b. providing 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. providing 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; d. waiting for the first storage controller to perform a write operation; e. generating an invalidate request via said invalidate request block when step (d) detects a write operation; f. providing said invalidate request to said XBAR interface block; g. placing said invalidate request into the invalidate request queue; h. issuing an anticipatory acknowledge back to the first storage controller; i. allowing the first storage controller to perform subsequent write operations upon receiving the anticipatory acknowledge issued in step (h); j. sending said invalidate request to a predetermined set of the at least one other storage controller(s); k. receiving an invalidate acknowledge from each of said invalidate acknowledge block(s) of the at least one other storage controller(s); l. determining if a predetermined number of the invalidate acknowledge signals received in step (k) are activated; and m. issuing an error and performing an error recovery algorithm of step (1) determines that a predetermined number of the invalidate acknowledge signals are not activated.

Claim 59

A method of accelerating the invalidate priority 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 instruction to the local memory element(s) contained within the at least one other storage controller(s), comprising: a. providing an XBAR interface block wherein said XBAR interface block is 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); said XBAR interface block having an invalidate request queue; b. providing 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. providing 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; d. waiting for the first storage controller to perform a write operation; e. generating an invalidate request via said invalidate request block when step (d) detects a write operation; f. providing said invalidate request to said XBAR interface block; g. placing said invalidate request into the invalidate request queue; h. issuing an anticipatory acknowledge back to the first storage controller; i. allowing the first storage controller to perform subsequent write operations upon receiving the anticipatory acknowledge issued in step (h); j. sending said invalidate request to a predetermined set of the at least one other storage controller(s); k. receiving an invalidate acknowledge from each of said invalidate acknowledge block(s) of the at least one other storage controller(s); l. determining if a predetermined number of the invalidate acknowledge signals received in step (k) are activated; and m. issuing an error and performing an error recovery algorithm of step (1) determines that a predetermined number of the invalidate acknowledge signals are not activated.

Claim 61

An apparatus comprising: a. a first storage controller having a first local memory element wherein the first local memory element may contain a first copy of a data block; b. a number of other storage controllers, wherein each of said number of other storage controllers include a local memory element that may containing a second copy of the data block; c. an XBAR interface block coupled to said first storage controller and further coupled to selected ones of said number of other storage controllers, the XBAR interface block providing an interface between said first storage controller and the selected ones of the number of other storage controllers; and d. said first storage controller being capable of providing a remote write instruction to selected ones of said local memory elements of the selected ones of the number of other storage controllers via said XBAR interface block.

Claim 62

An apparatus comprising: a. a first storage controller having a first local memory element wherein the first local memory element may contain a first copy of a data block; b. a number of other storage controllers, wherein each of said number of other storage controllers include a local memory element that may containing a second copy of the data block; c. an XBAR interface block coupled to said first storage controller and further coupled to selected ones of said number of other storage controllers, the XBAR interface block providing an interface between said first storage controller and the selected ones of the number of other storage controllers; and d. said first storage controller being capable of providing a remote write instruction to selected ones of said local memory elements of the selected ones of the number of other storage controllers via said XBAR interface block.