Cache coherency using flexible directory bit vectors

• US 5,634,110 A
• Filed: 05/05/1995
• Issued: 05/27/1997
• Est. Priority Date: 05/05/1995
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Lenoski, Daniel E., Laudon, James P.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): SAUNDERS, KEITH
• Application Number:
  US08/435,463
• Time in Patent Office: 753 Days
• Field of Search: 395/470, 395/471, 395/742, 395/451, 395/449, 395/468, 395/474, 395/475, 395/480, 364/134
• US Class Current: 711/145
• CPC Class Codes: G06F 12/0826 Limited pointers directories; State-only directories without pointers
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture

Abstract

A memory controller in a computer system is described. The memory controller maintains a directory comprising a plurality of entries. Each entry is associated with a memory block. The memory controller maintains an entry of the directory in a modified fine bit vector format when a memory block associated with the entry is cached in one or more nodes all of which are within a single partition of the computer system. The entry when maintained in the modified fine bit vector format comprises a partition field storing information identifying the single partition, and a modified fine bit vector field storing information identifying nodes in the single partition where the memory block is cached. The memory controller maintains the entry in a modified coarse bit vector format when the memory block is cached in multiple nodes distributed among P partitions of the computer system, where P is greater than one. The entry when maintained in the modified coarse bit vector format comprises Q partition fields each storing information identifying one of the P partitions, and Q modified coarse bit vector fields each storing information identifying nodes in one of the P partitions where the memory block is cached.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

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;

(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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

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 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.

17. 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.