Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-09-27
2003-07-15
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S144000, C711S141000
Reexamination Certificate
active
06594733
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to a method and mechanism for tracking and managing cached data in a multiprocessor system and, in particular, to a cache based vector coherency method and mechanism for tracking and managing data use in a multiprocessor system.
BACKGROUND OF THE INVENTION
Present computer systems are commonly configured and function as shared multiprocessor node systems comprised of a plurality of processor nodes communicating through an interconnection structure, such as a wide or local area network or bus. Each processor node may typically be comprised of one or more processors, an input/output sub-system and a memory sub-system providing a node memory space which functionally includes both dynamic memory and storage devices such as disk drives.
One or the primary advantages of shared multiprocessor systems is that the processors may share information resident in the various processor nodes, including both data and program code. Because information is shared among the nodes and node processors, the information accessible to the processors is effectively distributed across and through the system, and the memory spaces of the processor nodes functionally form a single, global memory pool. The global memory pool and the information is typically shared at some predetermined granularity, which is often referred to as a “line” wherein a “line” is typically of a fixed size corresponding to a unit of data convenient to operations of the processors.
In a typical shared multiprocessor system, a line will reside in or be “owned” by one processor or node, which may change over time with operations of the system, and copies of the line may be encached in the memory space of other nodes or processors at different points in time. The processor nodes and processors will typically have rights to read, modify and write a given line or copy thereof, and these rights will vary with time, depending, for example, upon the operations of the processors. For this reason, the tracking and management of the locations and status of lines and copies of lines is a critical function of a shared multiprocessor system to allow, for example, a processor to locate a given line or copy of the line, and to insure coherency of the information as various processors utilize a line or a copy of a line.
In general, the tracking and management of lines in a shared multiprocessor system and the maintenance of information coherency requires the generation and maintenance of sharing information, that is, of information pertaining to the locations of a line and encached copies of the line, of the status of the line and the encached copies of the line, and of the rights possessed by various processors to use the line. Shared multiprocessor systems of the prior art have attempted a number of solutions to the problem of cache coherency and sharing information, all of which have been unsatisfactory for one reason or another.
One approach has been to store all of the sharing information, that is, the information pertaining to the location and status of each line and each encached copy of each line in one deterministic location, which is typically the line's “home node”. This method is advantageous in terms of performance as all of the sharing information is co-located and can therefore be processed concurrently. This method is disadvantageous, however, in requiring an excessive amount of storage overhead as each home node must maintain a “tag” for each of its global memory lines and each of these tags is of a relatively large size as it must contain all of the sharing information for the associated line. The end result is typically a significant increase in system cost and, in particular, the cost of system storage space and, although there are techniques to reduce the overhead requirements of such methods, they typically introduce second order behaviors which can negatively affect system performance.
A second approach to storing sharing information is to distribute the sharing information for each line as evenly as possible across all of the nodes sharing the line, typically by requiring each node to store and maintain the sharing information associated with the lines encached in the node. The amount of total cache space in the nodes is typically orders of magnitude smaller than the amount of global memory, so that the number of lines encached in the nodes will be orders of magnitude less than the number of lines in the system global memory. Because of this, these methods thereby minimize the amount of information stored in each home node tag, for which there is one per line of global memory and distribute the remainder of the sharing information across the cache tags maintained by the other nodes sharing the line. In this respect, it will be recognized that the sharing information storage requirements that are thereby imposed on the nodes encaching lines belonging to other nodes is limited because the number of lines that can be encached in a given node is limited. The advantage of these methods is thereby a significant reduction in the overhead storage requirements for sharing information in each home node. The primary disadvantage of these methods is that since the sharing information is no longer co-located, the average latency per transaction is usually greatly increased, thereby significantly reducing system performance.
The present invention provides a solution to these and other problems of the prior art.
SUMMARY OF THE INVENTION
The present invention is directed to a method and mechanism for tracking and managing cached data in a multiprocessor system and, in particular, to a cache based vector coherency method and mechanism for tracking and managing data use in a multiprocessor system. In particular, the present invention is directed to a shared line coherency method and mechanism for maintaining coherency of shared lines among the nodes of a system including a plurality of nodes sharing lines of information wherein each line is an element of information.
The shared line coherency mechanism includes a single associated home node for each shared line wherein the home node of a line always contains a copy of the line, may include a plurality of leaf nodes for a given shared line wherein each leaf node shares the line and contains an encached copy of the line, and may include a single associated owner node for a given shared line wherein the owner node shares the line, contains an encached copy of the line, and contains a vector directory identifying the leaf nodes of the line. According to the present invention, all requests directed to a shared line are directed to the home node of the line and a home node receiving a request directed to a shared line will provide a copy of the line to the requesting node and will forward the request to the owner node of the line for completion of the request. The owner node is the first node to access the line, and subsequently the last node to modify the line, and operates to track all leaf nodes of the line and, for this purpose, the vector directory contains an entry for each possible leaf node of the line wherein each entry indicates whether the corresponding node is a leaf node having a valid copy of the line.
Each node maintains a line tag for each line resident in the node, whether the line resides in the node because the node is the home node or whether the node is a leaf node of an owner node of the line. The home node of a line includes the associated line, a line tag representing a current home node state and an identifier of a current node to which the home node is to direct communications and a leaf node of a line includes an encached copy of the line, a line tag representing a current leaf node state, and an identification of a current node to which the leaf node is to direct communications. An owner node of a line includes an encached copy of the line, a line tag representing a current owner node state and a vector directory including an entry corresponding to each possible sharing node of the system and indicating each c
Baker Paul
Bragdon Reginald G.
Davis & Bujold P.L.L.C.
LandOfFree
Cache based vector coherency methods and mechanisms for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cache based vector coherency methods and mechanisms for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache based vector coherency methods and mechanisms for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3030800