Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-07-28
2001-01-30
Thai, Tuan V. (Department: 2752)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S003000, C711S118000, C711S203000, C711S210000
Reexamination Certificate
active
06182195
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a system and method for cache coherency, and more particularly to a system and method for maintaining coherency of virtual-to-physical memory translations in a multiprocessor computer.
2. Related Art
Maintaining the coherence of virtual translation caches (such as translations stored in translation-lookaside buffers (TLBs)) is usually handled in software rather than hardware in most distributed, shared-memory multiprocessors. This is based on a number of reasons.
Translation updates (i.e., TLB coherence actions) are much less frequent than updates to memory locations (normal memory coherence actions). These translation updates are often associated with paging, which also involves a relatively expensive read or write, or both to a disk. This disk access dominates the cost of maintaining coherence. Most memory pages are private to individual processes and processors so TLB updates can often be done by simply purging a translation entry in a single processor's TLB. In many architectures (including MIPS), translation table updates, which comprise loads and purges, are handled in software anyway, so it is more natural to handle TLB coherence in software as well.
It should also be noted that much of the cost of software TLB coherence in a multiprocessor is the need to synchronize (i.e., interrupt) all the processors who need to have entries in their TLB invalidated or updated.
In a large-scale non-uniform memory architecture (NUMA) many of these conditions do not hold. A NUMA computer system typically includes a plurality of processing nodes each having one or more processors, a cache connected to each processor, and a portion of main memory that can be accessed by any of the processors. The main memory is physically distributed among the processing nodes. In other words, each processing node includes a portion of the main memory. At any time, data elements stored in a particular main memory portion can also be stored in any of the caches existing in any of the processing nodes.
Most importantly, the NUMA architecture implies that translation may change due to migrating data from the memory of one node to a node that contains the processor referencing the data more frequently. This can cause the rate of translation updates to increase over traditional systems. Further, the non-TLB update costs decrease since the data moves only from one memory to another, not to disk. Thus, in a NUMA system it is desirable to have hardware acceleration of TLB coherence. Furthermore, since most processors (including all the MIPS processors) do not support TLB coherence in hardware, it is desirable for TLB coherence to be managed outside of the processor, and to remove the need for inter-processor synchronization in the updating of the TLBs.
There are a number of schemes that have been described in the literature for maintaining TLB coherence. (See Teller et al., “Translation-Lookaside Buffer Consistency”,
IEEE Computer
, June 1990). Teller's TLB validation algorithm maintains a generation count in memory, which is incremented when a page table translation update is made. Along with each memory access, the processor includes its TLB copy of the generation count and memory compares these. If the two match, then the translation is valid and the access is validated. If the generation counts do not match, then the processor is notified to invalidate the appropriate TLB entry. An advantage of Teller's scheme is that it does not have problems reclaiming stale pages. When reused, the new translation starts with the next generation count for that physical page (frame is just another name for a page-sized portion of main memory). It does have a problem of needing to purge translations when a given generation counter overflows.
A bus error scheme is used in the Wisconsin Wind Tunnel (WWT) (Reinhardt et al., “The Wisconsin Wind Tunnel: Virtual Prototyping of Parallel Computers”, ACM SIGMETRICS Conference Proceedings, May 1993) for triggering memory and coherence operations in software. In the WWT design, the error correction code (ECC) for a given memory word is corrupted to cause a bus error, which subsequently invokes software that maintains the illusion of coherent shared-memory on top of a message-passing system (i.e., a CM-5 computer: “Connection Machine CM-5: Technical Summary”, Thinking Machines Corporation, November 1993). This scheme, however, is for cache coherency and does not address the problem of maintaining virtual-to-physical memory translations.
The problem not addressed by art is how to minimize costly synchronization of the processors. Thus, what is required is an improved mechanism to handle virtual-to-physical memory translations for maintaining coherency in a distributed computer system that results in minimal if any system performance degradation, and that requires minimal if any additional storage overhead.
SUMMARY OF THE INVENTION
The present invention is directed to a system and method for maintaining coherency between virtual-to-physical memory translations of multiple requesters in a shared-memory multiprocessor system.
A poison bit is associated with each memory block in the system. The poison bit is set when a virtual-to-physical memory translation for a memory block is stale.
A memory controller, or the like, associated with that memory block, generates an exception in response to an access by one of the requesters to the memory block if the poison bit is set. In a preferred embodiment, a requestor comprises a processor, input/output device, or the like. The exception indicates that the virtual-to-physical memory translation entry for the memory block is stale. In response to the exception, the requester updates its virtual-to-physical memory translation for the memory block with the virtual memory translation corresponding to a new physical location for the memory block.
The system may be a cached system or a non-cached system. An example of a cached system would include a cache in each processor. In this case, all cached copies of the memory block are invalidated when the poison bit is set. Preferably, the system supports a “poisoned read” operation that returns the current copy of a block while automatically setting the block's poison bit. The contents of the block can then be written to the new physical location. If the system supports caches, then the poison read would additionally invalidate all cached copies of the block at its old location.
The requestors can be a plurality of processors each with a cache memory and a translation-lookaside buffer to store virtual-to-physical memory translations. Alternatively, the requestors could also be input/output devices, or the like.
An advantage of the present invention over Teller is reduced memory overhead. According to the invention, only one state encoding is required (i.e., poison state), versus Teller's generation count and the need to send generation counts to memory.
An advantage of the present invention over the WWT approach is that WWT does not address TLB consistency at all. Their scheme is used to trigger cache coherency operations.
REFERENCES:
patent: 4141067 (1979-02-01), McLagan
patent: 4481573 (1984-11-01), Fukunaga et al.
patent: 4622631 (1986-11-01), Frank et al.
patent: 4825412 (1989-04-01), Sager et al.
patent: 4914577 (1990-04-01), Stewart et al.
patent: 5214770 (1993-05-01), Ramanujan et al.
patent: 5226144 (1993-07-01), Moriwaki et al.
patent: 5228136 (1993-07-01), Shimizu et al.
patent: 5282274 (1994-01-01), Liu
patent: 5297269 (1994-03-01), Donaldson et al.
patent: 5361340 (1994-11-01), Kelly et al.
patent: 5398325 (1995-03-01), Chang et al.
patent: 5406504 (1995-04-01), Denisco et al.
patent: 5412787 (1995-05-01), Forsyth et al.
patent: 5437017 (1995-07-01), Moore et al.
patent: 5455834 (1995-10-01), Chang et al.
patent: 5487162 (1996-01-01), Tanaka et al.
patent: 5493660 (1996-02-01), DeLano et al.
patent: 5515522 (1996-05-01), Bridges et al.
patent: 5530933 (1996-06-01), Frink et al
Laudon James P.
Lenoski Daniel E.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
Thai Tuan V.
LandOfFree
System and method for maintaining coherency of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for maintaining coherency of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for maintaining coherency of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2459548