Variable-grained memory sharing for clusters of symmetric multi-processors using private and shared state tables

Claim 1

In a computer system including a plurality of symmetric multi-processors, each symmetric multi-processor including a plurality of processors, a memory having addresses, and an input/output interface connected to each other by a bus, the input/output interfaces connecting the symmetric multi-processors to each other by a network, a software implemented method for sharing access to data stored in the memories of the symmetric multi-processors, comprising the steps of: designating a set of the addresses of the memories as virtual shared addresses to store shared data; allocating a portion of the virtual shared addresses to store a shared data structure as one or more blocks accessible by programs executing in any of the processors, the size of a particular allocated block to vary with the size of the shared data structure, each block including an integer number of lines, each line including a predetermined number of bytes of shared data; maintaining a shared state table including a plurality of shared state entries, there being one shared table entry for each line of the one or more blocks, each shared state entry to indicate a possible state of the line, the possible states being invalid, shared, exclusive, and pending; and maintaining a private state table for each processor of the plurality of symmetric multi-processors, each private state table having a plurality of private state entries, the private state table entries of a particular private state table to indicate a possible state of a particular line accessed by the associated particular processor: storing directory information of a particular block of the shared data structure in the memory of a home processor, the directory information including the size of the particular block; instrumenting the programs with instructions which access the shared data to check whether the data are available; and in response to receiving an access request from a requesting one of the processors to access the shared data, sending a particular block including the particular line and the size of the particular block to the requesting processor via the network to enable the processors to exchange shared data structures stored in variable sized blocks via the network.

Claim 16

A system comprising: a network; a plurality of symmetric multi-processors interconnected by the network, each symmetric multi-processor including a plurality of processors; and a memory having a layout of addresses for each symmetric multi-processor, each memory address having a designated set of virtual shared addresses to store shared data, a portion of the virtual shared addresses storing a shared data structure as one or more blocks accessible by programs executing in any of the processors, the size of a particular allocated block varying with a size of the shared data structure, each block including an integer number of lines, each line including a predetermined number of bytes of shared data; wherein the layout includes: i) a shared state table including a plurality of shared state entries, one shared entry for each line of the one or more entries, each shared entry indicating a possible state of the line, the possible states being invalid, shared, exclusive and pending; ii) a private state table for each processor of the plurality of symmetric multi-processors, each private state table having a plurality of private state entries, the private state entries of a particular private state table indicating a possible state of a particular line accessed by the associated particular processor; wherein the shared data is accessed to check whether the data are available and a particular block is sent to a requesting processor from one other processor via the network to exchange shared data structures stored in variable sized blocks.

Claim 17

A system comprising: a network; a plurality of symmetric multi-processors interconnected by the network, each symmetric multi-processor including a plurality of processors; and a memory having a layout of addresses for each symmetric multi-processor, each memory address having a designated set of virtual shared addresses to store shared data, a portion of the virtual shared addresses storing a shared data structure as one or more blocks accessible by programs executing in any of the processors, the size of a particular allocated block varying with a size of the shared data structure, each block including an integer number of lines, each line including a predetermined number of bytes of shared data; wherein the layout includes: i) a shared state table including a plurality of shared state entries, one shared entry for each line of the one or more entries, each shared entry indicating a possible state of the line, the possible states being invalid, shared, exclusive and pending; ii) a private state table for each processor of the plurality of symmetric multi-processors, each private state table having a plurality of private state entries, the private state entries of a particular private state table indicating a possible state of a particular line accessed by the associated particular processor; wherein the shared data is accessed to check whether the data are available and a particular block is sent to a requesting processor from one other processor via the network to exchange shared data structures stored in variable sized blocks.