Maintaining order of write operations in a multiprocessor for memory consistency

• US 6,493,809 B1
• Filed: 01/28/2000
• Issued: 12/10/2002
• Est. Priority Date: 01/28/2000
• Status: Expired due to Fees

• Current Assignee: Sequent Computer Systems, Inc. (International Business Machines Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Safranek, Robert J., Lovett, Thomas D.
• Primary Examiner(s): Robertson, David L.
• Application Number:
  US09/493,782
• Time in Patent Office: 1,047 Days
• Field of Search: 711/148, 711/141, 711/167
• US Class Current: 711/167
• CPC Class Codes: G06F 13/4243 with synchronous protocol

Abstract

A method of invalidating shared cache lines such as on a sharing list by issuing an invalidate acknowledgement before actually invalidating a cache line. The method is useful in multiprocessor systems such as a distributed shared memory (DSM) or non-uniform memory access (NUMA) machines that include a number of interconnected processor nodes each having local memory and caches that store copies of the same data. In such a multiprocessor system using the Scalable Content Interface (SCI) protocol, an invalidate request is sent from the head node on the sharing list to a succeeding node on the list. In response to the invalidate request, the succeeding node issues an invalidate acknowledgement before the cache line is actually invalidated. After issuing the invalidate acknowledgement, the succeeding node initiates invalidation of the cache line. The invalidate acknowledgement can take the form of a response to the head node or a forwarding of the invalidate request to the next succeeding node on the list. To maintain processor consistency, a flag is set each time an invalidate acknowledgement is sent. The flag is cleared after the invalidation of the cache line is completed. Cacheable transactions received at the succeeding node while a flag is set are delayed until the flag is cleared.

Claims

1. In a multiprocessor system having a number of interconnected processor nodes each containing one or more caches, a method of invalidating cache lines on different nodes linked in a sharing list, the method comprising:

from a node at the head of the list, sending an invalidate request to a succeeding node on the list, the invalidate request for invalidating a cache line on the succeeding node; and

in response to the invalidate request, issuing on the succeeding node an invalidate acknowledgement before actually invalidating the cache line.

2. The method of claim 1 wherein issuing on the succeeding node an invalidate acknowledgement includes responding with the invalidate acknowledgement to the head of the list.

3. The method of claim 1 wherein issuing on the succeeding node an invalidate acknowledgement includes forwarding the invalidate request to a succeeding node on the list.

4. The method of claim 1 wherein the invalidate request and the invalidate acknowledgement conform to an SCI protocol.

5. The method of claim 1 wherein the step of issuing an invalidate acknowledgement is repeated for each succeeding node on the sharing list in response to an invalidate request.

6. The method of claim 1 including, after issuing the invalidate acknowledgement, setting a flag indicating that an invalidation of a cache line is pending.

7. The method of claim 6 including, after actually invalidating the cache line, clearing the flag.

8. The method of claim 1 including:

receiving at the succeeding node a cacheable transaction;

in response, determining whether an invalidation is pending at the succeeding node; and

if so, delaying the cacheable transaction until after the cache line is actually invalidated.

9. The method of claim 8 wherein a cacheable transaction includes an issuance of a read response to a node bus, an issuance of a write request to a node bus, or an issuance of an interrupt.

10. The method of claim 1 wherein actually invalidating the cache line includes:

issuing a bus invalidate request;

invalidating the cache line in response to the bus invalidate request; and

issuing a bus invalidate acknowledgement that the invalidation of the cache line is completed.

11. The method of claim 1 including initiating an invalidation of the cache line on the succeeding node after issuing the invalidate acknowledgement.

12. A computer-readable medium on which is stored computer instructions that perform the steps of claim 1.

13. The method of claim 1 wherein each step is performed by a cache controller.

14. A multiprocessor system having a number of interconnected processor nodes each containing one or more caches, apparatus for invalidating cache lines on different nodes linked in a sharing list, the system further comprising:

a first cache controller on node at the head of the list, the first cache controller adapted to send an invalidate request to a succeeding node on the list to invalidate a cache line on the succeeding node;

a second cache controller on a succeeding node on the list, the second cache controller adapted to receive the invalidate request and respond by issuing an invalidate acknowledgement before the cache line is actually invalidated.

15. The multiprocessor system of claim 14 wherein the second cache controller is adapted to issue the invalidate acknowledgement by responding to the head of the list.

16. The multiprocessor system of claim 14 wherein the second cache controller is adapted to issue the invalidate acknowledgement by forwarding the invalidate request to a succeeding node on the list.

17. The multiprocessor system of claim 14 including a flag on the succeeding node, the flag being set when an invalidation of a cache line is pending and being cleared after the cache line is actually invalidated.

18. The multiprocessor system of claim 14 wherein the second controller is adapted to invalidate a cache line by issuing a bus invalidate request, and the system further includes a bus controller adapted to receive the bus invalidate request, invalidate the cache line in response, and issue a bus invalidate acknowledgement to the cache controller.

19. In a multiprocessor system having a number of interconnected processor nodes each containing one or more caches, a method of invalidating cache lines on different nodes, the method comprising:

from a first node, sending an invalidate request to a second node, the invalidate request for invalidating a cache line on the second node; and

in response to the invalidate request, issuing on the second node an invalidate acknowledgement before actually invalidating the cache line.

20. The method of claim 19 wherein issuing on the second node an invalidate acknowledgement includes responding with the invalidate acknowledgement to the first node.

21. The method of claim 19 wherein issuing on the second node an invalidate acknowledgement includes forwarding the invalidate request to a third node.

22. The method of claim 19 including, after issuing the invalidate acknowledgement, setting a flag indicating that an invalidation of a cache line is pending.

23. The method of claim 22 including, after actually invalidating the cache line, clearing the flag.

24. The method of claim 19 including:

receiving at the second node a cacheable transaction;

in response, determining whether an invalidation is pending at the second node; and

if so, delaying the cacheable transaction until after the cache line is actually invalidated.