Variable-grained memory sharing for clusters of symmetric multi-processors using private and shared state tables
First 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.
4 Assignments
0 Petitions
Accused Products
Abstract
In a distributed shared memory system, clusters of symmetric multi-processors are connected to each other by a network. Each symmetric multi-processor includes a plurality of processors, a memory having addresses, and an input/output interface to interconnect the processors. A software implemented method enables data sharing between the clusters of symmetric multi-processors using variable sized quantities of data called blocks. A set of the addresses of the memories are designated as virtual shared addresses to store shared data, and a portion of the virtual shared addresses are allocated to store a shared data structure as one or more blocks. The size of a particular allocated block can vary for different shared data structures. Each block includes an integer number of lines, and each line includes a predetermined number of bytes of shared data. Directory information of a particular block is stored in the memory of a processor designed as the home of the block. The directory information includes the size of the particular block, the identity of the processor that last modified the data in the particular block and the identity of all processors having a copy of the block.
95 Citations
20 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. 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. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification