Multiprocessor cache coherence directed by combined local and global tables

• US 6,088,769 A
• Filed: 10/01/1996
• Issued: 07/11/2000
• Est. Priority Date: 10/01/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Luick, David Arnold, Willis, John Christopher, Winterfield, Philip Braun
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US08/724,628
• Time in Patent Office: 1,379 Days
• Field of Search: 711/118, 711/130, 711/165, 711/141, 711/146-148, 711/124, 711/152, 711/144
• US Class Current: 711/141
• CPC Class Codes: G06F 12/082 Associative directories G06F12/0822 takes precedence
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers

Abstract

A method and apparatus for maintaining coherence between shared data stored within a plurality of memory devices, each memory device residing in a different node within a tightly coupled multiprocessor system. Each node includes a "local coherence unit" and an associated processor. A cache unit is associated with each memory/processor pair. Each local coherence unit maintains a table which indicates whether the most current copy of data stored within the node resides in the local memory, in the local cache, or in a non-local cache. The present invention includes a "global coherence" unit coupled to each node via the logical interconnect. The global coherence unit includes a interconnect monitoring device and a global coherence table. When data which resides within the memory of a first node is transferred to a second node, the interconnect monitoring device updates the global coherence table to indicate that the data is being shared. The global coherence table also preferably indicates in which node a copy of the most current data resides.

Claims

1. A method for maintaining cache coherence in a tightly coupled multiprocessor system having a plurality of nodes coupled to an interconnecting bus and storing portions of shared data, each node having a cache, a local coherence unit, a memory device and a processor device, the memory and processor device being coupled to form a memory/processor pair, the processor device within each node being capable of accessing data from the local memory device, the local cache, or over the interconnecting bus, from a non-local memory device, or a non-local cache, the method including the steps of:

(a) checking a local coherence unit to determine with a single data entry in a table whether a most current copy of a requested portion of data is stored locally, in response to a request by a requesting processor associated with that local coherence unit for the requested portion of data;

(b) if the most current copy of the requested portion of data is not stored locally, then checking a global coherence unit to determine in which node the most current copy of the requested portion of data is stored for addresses of the requested data;

(c) sending a message to the requesting node from the global coherence unit indicating in which node the most current copy of the requested data is stored;

(d) sending a request to transfer data from the requesting node to the node in which the most current copy of the requested data is stored; and

(e) transferring to the requesting node, in response to the request to transfer, the most current copy of the requested data.

2. A method for maintaining cache coherence in a tightly coupled multiprocessor system having a plurality of nodes coupled to an interconnecting bus and storing portions of shared data, each node having a cache, a local coherence unit, a memory device and a processor device, the memory and processor device being coupled to form a memory/processor pair, the processor device within each node being capable of accessing data from the local memory device, the local cache, or over the interconnecting bus, from a non-local memory device, or a non-local cache, the method including the steps of:

(a) checking a local coherence unit to determine with a single data entry in a table whether a most current copy of a requested portion of data is stored locally, in response to a request by a requesting processor associated with that local coherence unit for the requested portion of data;

(b) if the most current copy of the requested portion of data is not stored locally, then checking a global coherence unit to determine in which node the most current copy of the requested portion of data is stored for addresses of the requested data;

(c) sending a request from the global coherence unit to the node in which the most current copy of the data is stored to transfer the most current copy of the requested portion of the data to the requesting node; and

(d) sending, in response to the global coherence unit request, the most recent copy of the requested data to the requesting node.

3. The method of claim 2, further including the steps of:

sending to the global coherence unit, the most current copy of the data from the node in which the most recent copy of the data is stored; and

sending to the requesting node, from the global coherence unit, the most recent copy of the requested data.

4. A method for maintaining cache coherence in a tightly coupled multiprocessor system having a plurality of nodes coupled to an interconnecting bus and storing portions of shared data, each node being capable of accessing data from the local memory device, the local cache, or over the interconnecting bus, from a non-local memory device, or a non-local cache, the method including the steps of:

(a) writing new data to a local cache within a first node having a cache, a local coherence unit, a memory device and a processor device, the memory device and processor device being coupled to form a memory/processor pair;

(b) updating a table of the local coherence unit within the first node to indicate with a single data entry that the most current copy of the data is stored in the local cache within the first node; and

(c) updating the global coherence unit to indicate that the most current copy of the data is stored in the local cache within the first node for addresses of the shared data.

5. The method of claim 4, wherein the data is stored at an associated virtual address within one of the memory devices, further including the step of:

copying the written data from the local cache within the first node to the local memory device at the virtual address associated with the data.

6. A method for maintaining cache coherence in a tightly coupled multiprocessor system having a plurality of nodes coupled to an interconnecting bus and storing portions of shared data, each node being capable of accessing data from the local memory device, the local cache, or over the interconnecting bus, from a non-local memory or a non-local cache, the method including the steps of:

(a) writing new data to a local cache within a first node having a cache, a local coherence unit, a memory device, and a processor device, the memory device and processor device being coupled to form a memory/processor pair;

(b) checking a single data entry of a table maintained in the node to determine whether the most current copy of the data is in the local cache;

(c) if the most current copy of the data is not in the local cache, then checking the same data entry to determine whether the local coherence unit indicates that the most current copy of the data is in the local memory;

(d) if the most current copy of the data is not in the local memory, then updating a global coherence unit that stores data addresses of the shared data and updating the local coherence unit to indicate that the local cache has the most current copy of the data; and

(e) if the most current copy of the data is in the local memory, then updating the local coherence unit to indicate that the most current copy of the data is in the local cache.