Cache coherency using flexible directory bit vectors

Claim 2

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a method for denoting nodes in which said memory blocks are cached, said method comprising the steps of: (1) maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and (2) maintaining an entry of said directory in a modified fine bit vector format when a memory block associated with said entry is cached in one or more nodes all of which are within a single partition of said computer system, said entry when maintained in said modified fine bit vector format comprising a partition field storing information identifying said single partition, and a modified fine bit vector field storing information identifying nodes in said single partition where said memory block is cached.

Claim 3

The method of claim 1, wherein said modified fine bit vector field comprises a plurality of bits each associated with a node in said single partition, step (2) comprising the step of: setting a bit of said modified fine bit vector field if said memory block is cached in a node associated with said bit.

Claim 4

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a method for denoting nodes in which said memory blocks are cached, said method comprising the steps of: (1) maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and (2) maintaining an entry of said directory in a modified coarse bit vector format when a memory block associated with said entry is cached in multiple nodes distributed among P partitions of said computer system, P being greater than one, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is cached, Q being greater than or equal to P.

Claim 5

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a method for denoting nodes in which said memory blocks are cached, said method comprising the steps of: (1) maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and (2) maintaining an entry of said directory in a modified coarse bit vector format when a memory block associated with said entry is cached in multiple nodes distributed among P partitions of said computer system, P being greater than one, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is cached, Q being greater than or equal to P.

Claim 6

The method of claim 3, wherein each modified coarse bit vector field comprises a plurality of bits each associated with multiple nodes in one of said P partitions, step (2) comprising the step of: setting a bit of said modified coarse bit vector field if said memory block is cached in at least one node associated with said bit.

Claim 7

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a method for denoting nodes in which said memory blocks are cached, said method comprising the steps of: (1) maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; (2) maintaining an entry of said directory in a modified fine bit vector format when a memory block associated with said entry is cached in one or more nodes all of which are within a single partition of said computer system, said entry when maintained in said modified fine bit vector format comprising a partition field storing information identifying said single partition, and a modified fine bit vector field storing information identifying nodes in said single partition where said memory block is cached; (3) maintaining said entry in a modified coarse bit vector format when said memory block is cached in multiple nodes distributed among P partitions of said computer system, P being greater than one, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is cached; and (4) dynamically switching in real time between at least said modified fine bit vector format and said modified coarse bit vector format, depending upon a current cache state of said memory block.

Claim 8

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a method for denoting nodes in which said memory blocks are cached, said method comprising the steps of: (1) maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; (2) maintaining an entry of said directory in a modified fine bit vector format when a memory block associated with said entry is cached in one or more nodes all of which are within a single partition of said computer system, said entry when maintained in said modified fine bit vector format comprising a partition field storing information identifying said single partition, and a modified fine bit vector field storing information identifying nodes in said single partition where said memory block is cached; (3) maintaining said entry in a modified coarse bit vector format when said memory block is cached in multiple nodes distributed among P partitions of said computer system, P being greater than one, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is cached; and (4) dynamically switching in real time between at least said modified fine bit vector format and said modified coarse bit vector format, depending upon a current cache state of said memory block.

Claim 9

The method of claim 5, wherein said modified fine bit vector field comprises a plurality of bits each associated with a node in said single partition, step (2) comprising the step of: setting a bit of said modified fine bit vector field if said memory block is cached in a node associated with said bit.

Claim 10

The method of claim 5, wherein each modified coarse bit vector field comprises a plurality of bits each associated with multiple nodes in one of said P partitions, step (3) comprising the step of: setting a bit of said modified coarse bit vector field if said memory block is cached in at least one node associated with said bit.

Claim 11

A computer system, comprising: a communication network; and a plurality of nodes, each connected to said communication network and comprising at least a portion of main memory having a plurality of memory blocks and a memory controller; said memory controller comprising: directory maintaining means for maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and modified fine bit vector format maintaining means for maintaining an entry of said directory in a modified fine bit vector format when a memory block associated with said entry is cached in one or more nodes all of which are within a single partition of said computer system, said entry when maintained in said modified fine bit vector format comprising a partition field storing information identifying said single partition, and a modified fine bit vector field storing information identifying nodes in said single partition where said memory block is cached.

Claim 12

A computer system, comprising: a communication network; and a plurality of nodes, each connected to said communication network and comprising at least a portion of main memory having a plurality of memory blocks and a memory controller; said memory controller comprising: directory maintaining means for maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and modified fine bit vector format maintaining means for maintaining an entry of said directory in a modified fine bit vector format when a memory block associated with said entry is cached in one or more nodes all of which are within a single partition of said computer system, said entry when maintained in said modified fine bit vector format comprising a partition field storing information identifying said single partition, and a modified fine bit vector field storing information identifying nodes in said single partition where said memory block is cached.

Claim 13

The computer system of claim 8, wherein said modified fine bit vector field comprises a plurality of bits each associated with a node in said single partition, said modified fine bit vector format maintaining means comprising: means for setting a bit of said modified fine bit vector field if said memory block is cached in a node associated with said bit.

Claim 14

The computer system of claim 8, wherein said memory controller further comprises: modified coarse bit vector format maintaining means for maintaining said entry in a modified coarse bit vector format when said memory block is cached in multiple nodes distributed among P partitions of said computer system, P being greater than one, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is cached and; means for dynamically switching in real time between said modified fine bit vector format and said modified coarse bit vector format, depending upon a current cache state of said memory block.

Claim 15

The computer system of claim 10, wherein each modified coarse bit vector field comprises a plurality of bits each associated with multiple nodes in one of said P partitions, said modified coarse bit vector format maintaining means comprising: means for setting a bit of said modified coarse bit vector field if said memory block is cached in at least one node associated with said bit.

Claim 16

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a memory controller comprising: directory maintaining means for maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and modified fine bit vector format maintaining means for maintaining an entry of said directory in a modified fine bit vector format when a memory block associated with said entry is cached in one or more nodes all of which are within a single partition of said computer system, said entry when maintained in said modified fine bit vector format comprising a partition field storing information identifying said single partition, and a modified fine bit vector field storing information identifying nodes in said single partition where said memory block is cached.

Claim 17

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a memory controller comprising: directory maintaining means for maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and modified fine bit vector format maintaining means for maintaining an entry of said directory in a modified fine bit vector format when a memory block associated with said entry is cached in one or more nodes all of which are within a single partition of said computer system, said entry when maintained in said modified fine bit vector format comprising a partition field storing information identifying said single partition, and a modified fine bit vector field storing information identifying nodes in said single partition where said memory block is cached.

Claim 18

The memory controller of claim 12, wherein said modified fine bit vector field comprises a plurality of bits each associated with a node in said single partition, said modified fine bit vector format maintaining means comprising: means for setting a bit of said modified fine bit vector field if said memory block is cached in a node associated with said bit.

Claim 19

The memory controller of claim 12, further comprising: modified coarse bit vector format maintaining means for maintaining said entry in a modified coarse bit vector format when said memory block is cached in multiple nodes distributed among P partitions of said computer system, P being greater than one, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is cached and means for dynamically switching in real time between said modified fine bit vector format and said modified coarse bit vector format, depending upon a current cache state of said memory block.

Claim 20

The memory controller of claim 14, wherein each modified coarse bit vector field comprises a plurality of bits each associated with multiple nodes in one of said P partitions, said modified coarse bit vector format maintaining means comprising: means for setting a bit of said modified coarse bit vector field if said memory block is cached in at least one node associated with said bit.

Claim 21

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a memory controller comprising: directory maintaining means for maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and modified coarse bit vector format maintaining means for maintaining each said entry in a modified coarse bit vector format when said one or more associated memory blocks is stored in multiple nodes distributed among P partitions of said computer system, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is stored.

Claim 22

In a node comprising at least a portion of main memory having a plurality of memory blocks, said node being part of a computer system having a plurality of partitions each comprising a plurality of nodes, a memory controller comprising: directory maintaining means for maintaining a directory comprising a plurality of entries, each entry associated with one or more of said memory blocks; and modified coarse bit vector format maintaining means for maintaining each said entry in a modified coarse bit vector format when said one or more associated memory blocks is stored in multiple nodes distributed among P partitions of said computer system, said entry when maintained in said modified coarse bit vector format comprising Q partition fields each storing information identifying one of said P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of said P partitions where said memory block is stored.

Claim 23

The memory controller of claim 16, wherein each modified coarse bit vector field comprises a plurality of bits each associated with multiple nodes in one of said P partitions, said modified coarse bit vector format maintaining means comprising: means for setting a bit of said modified coarse bit vector field if said memory block is stored in at least one node associated with said bit.