Cache coherent network adapter for scalable shared memory processing systems

• US 6,343,346 B1
• Filed: 03/01/2000
• Issued: 01/29/2002
• Est. Priority Date: 07/10/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Olnowich, Howard Thomas
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US09/516,393
• Time in Patent Office: 699 Days
• Field of Search: 711/121, 711/122, 711/143, 711/144, 711/145, 711/146, 711/148, 711/153, 711/142, 709/214, 709/215, 709/218, 709/250
• US Class Current: 711/142
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0817 using directory methods

Abstract

A shared memory parallel processing system interconnected by a multi-stage network combines new system configuration techniques with special-purpose hardware to provide remote memory accesses across the network, while controlling cache coherency efficiently across the network. The system configuration techniques include a systematic method for partitioning and controlling the memory in relation to local verses remote accesses and changeable verses unchangeable data. Most of the special-purpose hardware is implemented in the memory controller and network adapter, which implements three send FIFOs and three receive FIFOs at each node to segregate and handle efficiently invalidate functions, remote stores, and remote accesses requiring cache coherency. The segregation of these three functions into different send and receive FIFOs greatly facilitates the cache coherency function over the network. In addition, the network itself is tailored to provide the best efficiency for remote accesses.

Claims

1. A shared memory processing system, comprising:

a multi-stage network;

a shared memory;

a plurality of processing nodes interconnected by said multi-stage network, each processing node including a section of said shared memory, a local processor, at least one local cache and a local invalidation directory, said local invalidation directory for tracking which of said plurality of processing nodes have accessed copies of data held in said shared memory at said local processor;

means for writing a second data to replace a first data in said at least one cache at a first node, and either writing the same second data selectively to replace said first data in shared memory at said first node or sending that same second data over said network to be written to a section of shared memory of a second node;

means responsive to said local invalidation directory for identifying a set of processing nodes having copies of said first data; and

means for generating and sending invalidation messages over said network for invalidating said copies of first data in said set of processing nodes.

2. The system of claim 1 wherein said at least one cache is a private write-through cache accessible by only a local processor.

3. A shared memory processing system, comprising:

a plurality of processing nodes interconnected by a multi-stage network, each processing node including

a section of local shared memory of said system,

a local processor,

at least one private local cache accessible only by said local processor, and

a local invalidation directory, said local invalidation directory for tracking which of said plurality of processing nodes have accessed copies of data held in said local shared memory at this processing node;

said local processor at a first processing node comprising means for writing a second data to replace a first data in said at least one private local cache at said first node while either writing said second data to shared memory at said first processing node to replace said first data or sending said second data over said network to be written to the shared memory of a second processing node;

means responsive to said local invalidation directory for identifying a set of processing nodes having copies of said first data; and

means for generating and sending update messages over said network for replacing said copies of first data with said second data in said set of processing nodes.

4. The system of claim 3 wherein said at least one cache is a write-through cache.

5. The system of claim 3 each of said shared memory sections further comprising a first memory section including a zero or more cache lines for storing data which does not change and a second memory section including one or more cache lines for storing data that changes.

6. The system of claim 5, said invalidation directory further comprising at each of said processing nodes indicia identifying those other nodes which have accessed cache lines containing data stored in said second memory section at said this node.

7. The system of claim 6, further comprising at each of said processing nodes a network adapter for transmitting and receiving messages with respect to the plurality of other processing nodes over said network.

8. The system of claim 7, wherein each of said processing nodes includes means for reading, storing and invalidating shared memory at any of said plurality of processing nodes.

9. The system of claim 8, wherein each of said processing nodes includes means for accessing shared memory at any of said plurality of processing nodes by transmitting and receiving first, second, third and fourth messages types, said first message type for requesting a read of a cache line, said second message type for returning a requested cache line, said third message type for storing a cache line, and said fourth message type for invalidating a cache line.

10. The system of claim 9, said network adapter further comprising:

a first buffer for storing and forwarding to said network said first and second message types for reading data from shared memory;

a second buffer for storing and forwarding to said network said third message types for storing data to shared memory;

a third buffer for storing and forwarding to said network said fourth message type for invalidating a cache line in shared memory;

a fourth buffer for storing and forwarding from said network said first and second message types for reading data from shared memory;

a fifth buffer for storing and forwarding from said network said third message types for storing data to shard memory; and

a sixth buffer for storing and forwarding from said network said fourth message types for invalidating a cache line in shared memory.

11. The system of claim 10, wherein said third and sixth buffers store and forward said fourth message types with respect to said invalidation directory.

12. A shared memory processing node, comprising:

a communications port for connected to a communications network for interfacing to other processing nodes;

a node memory including a section of a shared memory;

a local processor;

at least one private local cache accessible only by said local processor;

a local invalidation directory, said local invalidation directory for tracking which of said processing nodes have accessed copies of data held in said shared memory at said local processor;

said local processor comprising means for writing a second data to replace a first data in said at least one private local cache while either writing said second data to replace said first data in said section of shared memory or loading said second data to said communications port for updating a cache and section of shared memory at another processing node;

means responsive to said local invalidation directory for identifying a set of processing nodes having copies of said first data; and

means for generating and sending invalidation messages over said communication port for invalidating said copies of first data in said set of processing nodes having copies of said first data.

13. A method for operating a tightly coupled shared memory processing system, the system including a multi-stage network, a shared memory, a plurality of processing nodes interconnected by said multi-stage network, each processing node including a section of said shared memory, a local processor, at least one local cache and a local invalidation directory for tracking which of said plurality of processing nodes have accessed copies of data held in said shared memory section at said local processor;

comprising the steps of;

writing a second data to replace a first data in said at least local cache at a first node; and

either writing said second data to replace said first data in the shared memory section at said first node or sending said second data over said network to be written to a section of shared memory of a second node;

using said local invalidation directory to identify a set of processing nodes having copies of said first data; and

generating and sending invalidation messages over said network for invalidating said copies of first data in said set of processing nodes.

14. A shared memory parallel processing system, comprising:

a plurality of nodes;

a multi-stage switching network for interconnecting said plurality of nodes;

each of said plurality of nodes including a node memory, at least one cache, an invalidation directory, and a controller;

system memory distributed among the node memories at said plurality of nodes and accessible by any node;

each of said node memories being organized into a plurality of addressable word locations;

said controller at a first node being responsive to a request to access a word location in system memory for selectively executing a local memory access to the node memory of said first node or executing a remote memory access over said switching network to the node memory of a second node; and

said controller at said first node being responsive to both local memory accesses and remote memory accesses to data stored in a word location of said node memory at said first node for write-through caching accessed data in the at least one cache of said first node and for communicating data for assuring cache coherency throughout said system over said network and for listing in said invalidation directory at said first node a set of nodes having copies of each of said plurality of addressable word locations of the node memory of said first node.

15. The shared memory parallel processing system of claim 14, wherein said system memory is distributed among said plurality of nodes such that each node includes an equal portion of said system memory.

16. The shared memory parallel processing system of claim 14, wherein said node memory is organized into sequential double words, each double word comprising 65 bits;

and wherein said cache is organized into a plurality of cache lines, each cache line comprising eight double words and assigned a unique cache address for locating and accessing said each cache line.

17. The shared memory parallel processing system of claim 14, wherein each of said node memories includes a changeable memory section for storing data that is changeable and an unchangeable memory section for storing data that is not changeable.

18. The shared memory parallel processing system of claim 17, further comprising at each node allocation means for allocating node memory between said changeable memory section and said unchangeable memory section.

19. The shared memory parallel processing system of claim 18, said allocation means including a locator register for storing an extent boundary of said changeable memory section such that all memory addresses within said extent boundary reside within said changeable memory section and all memory addresses beyond said extent boundary reside in said unchangeable memory section.

20. The shared memory parallel processing system of claim 19, wherein said controller provides cache coherency only for said changeable memory section.

21. The shared memory parallel processing system of claim 20, further comprising for each data word format changeable indicia characterizing said data word as changeable data or unchangeable data.

22. The shared memory parallel processing system of claim 21, said controller being operable for preventing data words stored in said unchangeable memory section from being stored in said cache and said indicia of data words stored in said unchangeable memory section from being characterized as changeable.

23. The shared memory parallel processing system of claim 18, wherein all of said node memory of a node is assigned to said changeable memory section.

24. The shared memory parallel processing system of claim 23, further comprising memory addressing means for addressing said node memory according to an address word comprising a node identifier segment and a memory address segment, with a unique node identifier segment being assigned to each node within said system and a unique memory address segment being assigned to each addressable word location in said node memory.

25. The shared memory parallel processing system of claim 24, said memory addressing means being operable to access within said distributed memory an addressable word location identified by said memory address segment at the node identified by said node identifier segment.

26. The shared memory parallel processing system of claim 25, said memory addressing means being further operable to organize said distributed memory into a plurality of sequential cache lines.

27. The shared memory parallel processing system of claim 26, said controller at each of said nodes further comprising a cache coherency controller including:

tracking means for adding to said invalidation directory the node identifier segment of nodes copying a cache line of said own node memory; and

invalidation means responsive to a change to a cache line for invalidating all local and remote node copies of the changed cache line.

28. The shared memory parallel processing system of claim 27, further comprising an overflow directory for expanding said invalidation directory, said tracking means being operable for adding node identifier segments to said invalidation directory and said overflow directory, and an extension address generation means for assigning an extension of the invalidation directory to the overflow directory.

29. A cache coherency controller for a processing node of a shared memory parallel processing system, said node including a node memory and a cache, wherein said node communicates with said plurality of other nodes via an interconnection network, wherein changed data is stored immediately to shared memory causing the shared memory always to contain the most recent data, said cache coherency controller comprising:

an invalidation directory associated with said node memory for storing a list of node identifier segments for nodes which have copied a cache line from said node memory since the last time said cache line was changed;

tracking means for adding to said invalidation directory the node identifier segment of nodes copying each cache line from said node memory; and

invalidation means responsive to a change to a cache line for invalidating the copies of said changed cache line at all local and remote nodes listed in said invalidation directory for said changed cache line.

30. The cache coherency controller of claim 29, wherein said invalidation means invalidates a changed cache line by updating copies of said changed cache line.

31. The cache coherency controller of claim 29, wherein:

said invalidation directory further comprises a plurality of invalidation words, at least one invalidation word dedicated to each cache line of memory in said node memory;

said invalidation word including a plurality of node ID segments and corresponding validity indicia; and

said tracking means being operable for monitoring each access to local node memory, accessing said invalidation word for the cache line being accessed, adding the node ID number of the node requesting the access as a valid node ID number field to a node ID number field that was previously invalid in said invalidation word, and returning the modified invalidation word to said invalidation directory.

32. A shared memory processing node, comprising:

a network adapter for interfacing a communications network;

a node memory including a section of a shared memory;

at least one private cache;

a local processor for writing data to said at least one private cache while selectively writing said data to said section of shared memory or loading said data to said network adapter for updating a cache and section of shared memory at another processing node;

said network adapter further comprising;

a send FIFO;

a receive FIFO;

an invalidation directory associated with said node memory for storing a list of node identifier segments for nodes which have copied a cache line from said node memory since the last time said cache line was changed;

store message processing means for generating store messages and controlling the operation of said send FIFO and said receive FIFO for selectively sending and receiving said store messages;

said store message processing means being responsive to a store message for a selected cache line from a given remote node and to said invalidation directory for storing said cache line to said local cache and node memory and for providing a cache line invalidation message to said network adapter for communication to all remote nodes other than said given remote node;

said store message processing means being operable for deleting nodes being sent invalidation messages with respect to said selected cache line from said the list of nodes having copies of said selected cache line in said invalidation directory.

33. The shared memory processing node of claim 32, said store message processing means being further operable for invalidating response messages stored in said receive FIFO which contain a cache line with obsolete data.

34. Method of maintaining cache coherency for a processing node of a shared memory parallel processing system interconnected via a network, said node including a node processor, a node memory, a cache, and an invalidation directory associated with said node memory, comprising the steps of:

storing in said invalidation directory a list of node identifier segments for nodes which have copied a cache line from said node memory since the last time said cache line was changed;

detecting changes made to each cache line stored in said node memory;

responding to changes to a cache line in said node memory by storing the changed data immediately to shared memory causing the shared memory always to contain the most recent data and invalidating the copies of said changed cache line at all local and remote nodes listed in said invalidation directory by sending invalidation messages across said network individually to each node having a copy of said changed cache line.

35. The method of claim 34, further comprising the step of:

expanding said invalidation directory by using an overflow directory for increasing the number of node identifier segments above the capacity of the invalidation directory.

36. The method of claim 34, further comprising the step of:

pipelining the sending and receiving of said invalidation messages over said network by implementing a network adapter at each node having a plurality of send and receive FIFOs and dedicating one send and one receive FIFO from said plurality of FIFOs to the processing of invalidation messages.

37. The method of claim 34, further comprising the step of:

dividing said node memory into two sections, one for changeable data and one for unchangeable data, and listing node identifier segments for the changeable section of node memory.

38. A method for operating a tightly coupled shared memory processing system with cache coherency, the system including a multi-stage network, a shared memory, a plurality of processing nodes interconnected by said multi-stage network, each processing node including a node memory comprising a section of said shared memory, a local processor, at least one local cache and a local invalidation directory, said local invalidation directory for tracking which of said plurality of processing nodes have accessed copies of data held in said shared memory at said local processor;

comprising the steps of;

storing in said invalidation directory a list of node identifier segments for nodes which have copied a cache line from said node memory since the last time said cache line was changed;

detecting changes made to each cache line stored in said node memory;

responding to changes to a cache line in said node memory by storing the changed data immediately to shared memory causing the shared memory always to contain the most recent data and invalidating the copies of said changed cache line at all local and remote nodes listed in said invalidation directory by sending invalidation messages across said network individually to each node having a copy of said changed cache line.

39. The method of claim 38, further comprising the step of:

expanding said invalidation directory by using an overflow directory for increasing the number of node identifier segments above the capacity of the invalidation directory.

40. The method of claim 38, further comprising the step of:

pipelining the sending and receiving of said invalidation messages over said network by implementing a network adapter at each node having a plurality of send and receive FIFOs and dedicating one send FIFO and one receive FIFO from said plurality of FIFOs to the processing of invalidation messages.

41. The method of claim 38, further comprising the step of:

dividing said node memory into two sections, one for changeable data and one for unchangeable data, and listing node identifier segments for the changeable section of node memory.

42. The method of operating a shared memory parallel processing system with cache coherency, the system including a plurality of nodes, shared system memory distributed across the nodes as node memory, a multi-stage switching network for interconnecting said plurality of nodes with each node including at least one cache, an invalidation directory, and a controller, wherein changed data is stored immediately to shared memory causing the shared memory always to contain the most recent data;

comprising the steps of;

organizing each of said node memories into a plurality of addressable word locations;

said controller at a first node responding to a request to access a word location in shared system memory by selectively executing a local memory access to the node memory of said first node or executing a remote memory access over said switching network to the node memory of a second node; and

said controller at said first node responding to both local memory accesses and remote memory accesses to data stored in a word location of said node memory at said first node and assuring cache coherency throughout said system over said network by listing in said invalidation directory at said first node a set of nodes having copies of each of said plurality of addressable word locations of the node memory of said first node.

43. The method of claim 42, further comprising the steps of:

detecting changes made to each of said plurality of addressable word locations in said node memory;

responding to changes to each of said plurality of addressable word locations in said node memory by invalidating the copies of said changed word locations at all local and remote nodes listed in said invalidation directory by sending invalidation messages across said network individually to each node having a copy of said changed cache line.

44. The method of claim 42, further comprising the step of:

expanding said invalidation directory by using an overflow directory for increasing the list of nodes having copies of each of said plurality of addressable word locations above the capacity of the invalidation directory.

45. The method of claim 42, further comprising the step of:

pipelining the sending and receiving of said invalidation messages over said network by implementing a network adapter at each node having a plurality of send and receive FIFOs and dedicating one send FIFO and one receive FIFO from said plurality of FIFOs to the processing of invalidation messages.

46. The method of claim 42, further comprising the step of:

dividing said node memory into two sections, one for changeable data and one for unchangeable data, and listing nodes having copies of each of said plurality of addressable word locations for the changeable section of node memory.

47. The method of expanding a distributed invalidation directory in a shared memory parallel processing system by using overflow directories, wherein said shared memory parallel processing system is comprised of a plurality of nodes, each node comprising a local processor, a local node memory containing a unique portion of the shared memory, a local cache coherency controller, a local invalidation directory, and a local overflow directory, comprising the steps of:

providing a plurality of invalidation words for comprising said local invalidation directory and said overflow directory, each invalidation word comprising n node identifier segments and an extension address field;

associating each of said plurality of invalidation words in said local invalidation directory with a unique cache line in said local node memory;

initializing all invalidation words in said local invalidation directory and said local overflow directory to indicate that all n node identifier segments and all extension address fields are available for use;

monitoring all reads from and all writes of data to said local node memory via said local cache coherency controller;

storing a node identifier in said associated invalidation word into an available node identifier segment whenever a cache line is read from said local node memory thereby comprising a list of up to n node identifier segments in an invalidation word in said local invalidation directory for identifying nodes which have copied the same cache line from said local node memory since the last time said cache line was changed;

marking a newly stored node identifier segment as being used and no longer available for use;

expanding said local invalidation directory using said local overflow directory when more than n nodes copy the same cache line;

requesting an available extension address from said overflow directory for providing the address of an available invalidation word in said local overflow directory;

using said extension address field of said invalidation word to store the requested extension address and to access an available invalidation word from said local overflow directory which provides a second invalidation word dedicated to the same cache line of local node memory as the first invalidation word in the local invalidation directory and permits n more node identifier segments to be stored;

invalidating the copies of said changed cache line at all nodes listed in said local invalidation directory or local overflow directory for each changed cache line in said local node memory;

returning a node identifier segment to an available for use state after invalidating the copy of the cache line at the identified node; and

making available for use an invalidation word in the local overflow directory and resetting the extension address field in the invalidation word in the local invalidation directory when all in node identifier segments in an invalidation word in the local overflow directory have been returned to said available for use state.

48. The method of claim 47, further comprising the step of:

generating an extension address for locating an invalidation word in said overflow directory that is available for use;

tracking the invalidation words in said local overflow directory which are available for use by using a stand alone memory containing one validity bit for each invalidation word in said local overflow directory;

initializing a next extension address register and all said stand alone memory to all zeroes to indicate that all invalidation word s are available for use;

using the address stored in said next extension address register for addressing and writing a validity bit associated with said next extension address;

sending the address in said next extension address register to said tracking means when requested;

incrementing said next generation address, accessing from said standalone memory the validity bit associated with said next extension address;

testing said validity bit and if in valid rendering it valid,

waiting for said tracking means to request a new extension address if said validity was previously invalid, or continuing the search for an address having an invalid validity bit by incrementing said next generation address, accessing from said standalone memory the next validity bit associated with said next extension address, and testing said next validity bit validity and if invalid rendering it valid, and

waiting for the next request for a new extension address.

49. The method of tracking which nodes have copies of cache lines in a shared memory parallel processing system by using invalidation and overflow directories, wherein said shared memory parallel processing system is comprised of a plurality of nodes, each node comprising a local processor, a local node memory containing a unique portion of the shared memory, a local cache coherency controller, a local invalidation directory, and a local overflow directory, comprising the steps of:

providing a plurality of invalidation words comprising said local invalidation directory and said overflow directory, each invalidation word comprising n node identifier segments and an extension address field;

associating each of said plurality of invalidation words in said local invalidation directory with a unique cache line in said local node memory;

initializing all invalidation words in said local invalidation directory and said local overflow directory to indicate that all n node identifier segments and all extension address fields are available for use;

monitoring all reads from and all writes of data to said local node memory via said local cache coherency controller;

storing a node identifier in said associated invalidation word into an available node identifier segment whenever a cache line is read from said local node memory thereby comprising a list of up to n node identifier segments in an invalidation word in said local invalidation directory for tracking nodes which have copied the same cache line from said local node memory since the last time said cache line was changed;

marking a newly stored node identifier segment as being used and no longer available for use;

expanding said local invalidation directory using said local overflow directory when more than n nodes copy the same cache line;

requesting an available extension address from said overflow directory for providing the address of an available invalidation word in said local overflow directory;

using said extension address field of said invalidation word to store the requested extension address and to access an available invalidation word from said local overflow directory which provides a second invalidation word dedicated to the same cache line of local node memory as the first invalidation word in the local invalidation directory and permits n more node identifier segments to be stored;

invalidating the copies of a changed cache line at all nodes listed in said local invalidation directory or local overflow directory for each changed cache line in said local node memory;

returning a node identifier segment to an available for use state after invalidating the copy of the cache line at the identified node; and

making available for use an invalidation word in the local overflow directory and resetting the extension address field in the invalidation word in the local invalidation directory when all in node identifier segments in an invalidation word in the local overflow directory have been returned to said available for use state.

50. The method of claim 49, further comprising the step of:

generating an extension address for locating an invalidation word in said overflow directory that is available for use;

tracking invalidation words in said local overflow directory which are available for use by using a stand alone memory containing one validity bit for each invalidation word in said local overflow directory;

initializing a next extension address register and all said stand alone memory to indicate that all invalidation words are available for use;

using the address stored in said next extension address register to address and write a validity bit associated with said next extension address;

sending the address in said next extension address register to said tracking means when requested;

incrementing said next generation address, and accessing from said standalone memory the validity bit associated with said next extension address;

testing said validity bit and if invalid rendering it valid,

waiting for said tracking means to request a new extension address if said validity was previously invalid, or continuing the search for an address having an invalid validity bit by incrementing said next generation address, accessing from said standalone memory the next validity bit associated with said next extension address, and testing said next validity bit validity and if invalid rendering it valid, and

waiting for the next request for a new extension address.

51. An invalidation directory for a digital parallel processing system comprised of a plurality of nodes each containing a processor and a node memory containing a portion of shared memory, wherein each of said nodes communicates with said plurality of other nodes via an interconnection network, wherein changed data is stored immediately to shared memory causing the shared memory always to contain the most recent data, comprising:

means associating a distributed invalidation directory containing a potion of said invalidation directory with a node memory of a node of a shared memory parallel processing system, said node including said node memory and a cache; and

means for storing a list of node identifier segments for nodes which have copied a cache line from said node memory since the last time said cache line was changed.

52. The invalidation directory of claim 51, further comprising:

tracking means for adding to said invalidation directory the node identifier segments of nodes copying each cache line from said node memory, and

invalidation means responsive to a change to a cache line for invalidating the copies of said changed cache line at all local and remote nodes listed in said invalidation directory for said changed cache line.

53. The invalidation directory of claim 52 wherein said invalidation means invalidates the copies of the changed cache line by updating copies of said changed cache line.

54. The invalidation directory of claim 53 further comprising a plurality of invalidation words, at least one invalidation word dedicated to each cache line of memory in said node memory;

said invalidation word including a plurality of node ID segments and corresponding validity indicia.

55. A tracking system for an invalidation directory associated with a node memory for a digital parallel processing system including a plurality of nodes each containing a processor and a node memory containing a portion of shared memory, wherein each said node communicates with said plurality of other nodes via an interconnection network, wherein changed data is stored immediately to shared memory causing the shared memory always to contain the most recent data, comprising:

means for monitoring each access to said node memory;

means for accessing an invalidation word for a cache line being accessed, adding the node ID number of the node requesting the access as a valid node ID number field to a node ID number field that was previously invalid in said invalidation word, and returning the modified invalidation word to said invalidation directory.

56. An overflow directory for expanding an invalidation directory in a node including a node memory and a cache, comprising:

tracking means for adding to said invalidation directory or said overflow directory the node identifier segment of nodes copying each cache line from node memory; and

invalidation means responsive to a change to a cache line for invalidating the copies of said changed cache line at all local and remote nodes listed in said invalidation directory or overflow directory for said changed cache line.

57. The overflow directory of claim 56, wherein said invalidation directory includes one invalidation word for each cache line of local memory and said overflow directory includes plurality of invalidation words.

58. A shared memory parallel processing system, comprising:

a plurality of nodes;

a multi-stage switching network for interconnecting said plurality of nodes;

each of said plurality of nodes including a node memory, at least one cache, an invalidation directory, and a controller;

system memory distributed among the node memories at said plurality of nodes and accessible by any node;

each of said node memories being organized into a plurality of addressable word locations;

said controller at a first node being responsive to a request to access a word location in system memory for selectively executing a local memory access to the node memory of said first node or executing a remote memory access over said switching network to the node memory of a second node;

said controller at said first node being responsive to both local memory accesses and remote memory accesses to data stored in a word location of said node memory at said first node for write-through caching accessed data in the cache of said first node and for communicating data for assuring cache coherency throughout said system over said network and for listing in said invalidation directory at said first node a set of nodes having copies of each of said plurality of addressable word locations of the node memory of said first node;

each of said node memories includes a changeable memory section for storing data that is changeable and an unchangeable memory section for storing data that is not changeable;

at each node allocation means for allocating node memory between said changeable memory section and said unchangeable memory section;

wherein all of said node memory of a node is assigned to said changeable memory section;

memory addressing means for addressing said node memory according to an address word comprising a node identifier segment and a memory address segment, with a unique node identifier segment being assigned to each node within said system and a unique memory address segment being assigned to each addressable word location in said node memory;

said memory addressing means being operable to access within said distributed memory an addressable word location identified by said memory address segment at the node identified by said node identifier segment;

said memory addressing means being further operable to organize said distributed memory into a plurality of sequential cache lines;

said controller at each of said nodes further comprising a cache coherency controller including;

tracking means for adding to said invalidation directory the node identifier segment of nodes copying a cache line in the node memory of this node since the last time said cache line was changed;

invalidation means responsive to a change to a cache line for invalidating all local and remote node copies of the changed cache line; and

an overflow directory for expanding said invalidation directory, said tracking means being operable for adding node identifier segments to said invalidation directory and said overflow directory, and an extension address generation means for assigning an extension of the invalidation directory to the overflow directory.

59. Method of maintaining cache coherency for a processing node of a shared memory parallel processing system interconnected via a network, said node including a node processor, a node memory, a cache, and an invalidation directory associated with said node memory, comprising the steps of:

storing in said invalidation directory a list of node identifier segments for nodes which have copied a cache line from said node memory since the last time said cache line was changed;

detecting changes made to each cache line stored in said node memory;

responding to changes to a cache line in said node memory by invalidating the copies of said changed cache line at all local and remote nodes listed in said invalidation directory by sending invalidation messages across said network individually to each node having a copy of said changed cache line; and

expanding said invalidation directory by using an overflow directory for increasing the number of node identifier segments above the capacity of the invalidation directory.

60. A method for operating a tightly coupled shared memory processing system with cache coherency, the system including a node memory containing a multi-stage network, a shared memory, a plurality of processing nodes interconnected by said multi-stage network, each processing node including a section of said shared memory, a local processor, at least one local cache and a local invalidation directory, said local invalidation directory for tracking which of said plurality of processing nodes have accessed copies of data held in said shared memory at said local processor;

comprising the steps of;

storing in said invalidation directory a list of node identifier segments for nodes which have copied a cache line from said node memory since the last time said cache line was changed;

detecting changes made to each cache line stored in said node memory;

responding to changes to a cache line in said node memory by invalidating the copies of said changed cache line at all local and remote nodes listed in said invalidation directory by sending invalidation messages across said network individually to each node having a copy of said changed cache line; and

expanding said invalidation directory by using an overflow directory for increasing the number of node identifier segments above the capacity of the invalidation directory.

61. A method of operating a shared memory parallel processing system with cache coherency, the system including a plurality of nodes, shared system memory distributed across the nodes as node memories, a multi-stage switching network for interconnecting said plurality of nodes with each node including at least one cache, an invalidation directory, and a controller;

comprising the steps of;

organizing each of said node memories into a plurality of addressable word locations;

said controller at a first node responding to a request to access a word location in shared system memory by selectively executing a local memory access to the node memory of said first node or executing a remote memory access over said switching network to the node memory of a second node;

said controller at said first node responding to both local memory accesses and remote memory accesses to data stored in a word location of said node memory at said first node and assuring cache coherency throughout said system over said network by listing in said invalidation directory at said first node a set of nodes having copies of each of said plurality of addressable word locations of the node memory of said first node; and

expanding said invalidation directory by using an overflow directory for increasing the list of nodes having copies of each of said plurality of addressable word locations above the capacity of the invalidation directory.