Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-04-29
2002-10-08
Hudspeth, David (Department: 2651)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S003000, C711S145000, C711S144000
Reexamination Certificate
active
06463506
ABSTRACT:
TECHNICAL FIELD
This application relates in general to LSI circuit design and is specific to data organization within cache lines.
BACKGROUND
In a multiprocessor system, problems arise when more than one processor attempts to access a memory location. While multiple processors can access a single memory location, if one of those processors attempts to update the information in the memory location without informing the other processors who also have access to the specific memory location, data mismatches may occur. Multiprocessor systems typically use memory cache which is associated with each processor. These local memory locations are typically called processor cache. Examples of such an architecture are set forth in U.S. Pat. No. 6,049,851 entitled “Method and Apparatus for Checking Cache Coherency in a Computer Architecture” and U.S. Pat. No. 5,737,757 entitled, “Cache Tag System for use with Multiple Processors Including the Most Recently Requested Processor Identification”, both patents are assigned to the owner of the present invention, and are incorporated herein by reference in their entirety.
Within the processor cache, the processor may store information as recently accessed. Processor cache is typically separated out into cache lines. A cache line is typically 64, 128, or 256 bytes of data. Therefore, when a processor attempts to access a specific memory location it first searches its cache to determine if it already has a copy of the information stored for that memory location. If the memory location is not currently stored in the processor cache, the processor attempts to obtain a copy of that memory location from main memory. If the memory location is available in the processor cache, the processor will use the cache for its copy. Issues arise when multiple processors attempt to access the same memory location.
Numerous protocols exist which attempt to reduce or eliminate memory contentions between processors. One such protocol is called MESI. MESI stands for Modified, Exclusive, Shared, Invalid and is described in detail in M. Papamarcos and J. Patel “A Low Overhead Coherent Solution for Multiprocessors with Private Cache Memories” in Proceedings of the 11th International Symposium on Computer Architecture, IEEE, New York (1984), pp. 348-354, incorporated herein by reference. Under the MESI protocol, a cache line is categorized according to its use. A modified cache line indicates that the particular line has been written to by a processor in which case the data has been modified. An exclusive cache line indicates that one specific processor has exclusive access to the line so that it can modify the information contained within that memory location if desired. A shared cache line indicates that more than one processor has access to that memory location. The information in that memory location could also currently be stored in more than one processors' cache. A shared cache line is considered “read only” and any processor with access to the memory location can not modify or write to that memory location. An invalid cache line identifies a particular processor's cache which is invalid i.e., may no longer be current. While MESI is a standard term in the industry, other classifications of nomenclature are frequency employed. Modified cache lines are typically referred to as private dirty. Exclusive cache lines are typically referred to as private cache lines. Private cache lines which have not been modified are typically referred to as private clean cache lines.
If a processor requires access to a specific memory location it will first check its processor cache to determine if the information is available there. If the information is not currently contained within the processor's cache, the processor will go to main memory to access the information. Before allowing the processor access to a memory location, the cache coherency controller will determine what access to the memory location is available. If a processor desires exclusive or private use of a cache line, it is the function of the cache coherency controller to make sure that no other cache in the system has a valid copy of that line. Only one processor will be allowed exclusive or private access to a memory location at a time. If a cache coherency controller has characterized a specific cache line as read only or shared, potentially every processor or every processor cache in the entire system could have a copy of that line. Difficulties arise, however, if one of the processors needs to update the information within that cache line.
In order for a processor to update or modify information within the specific memory location it must have exclusive access to a memory location. If the memory location is currently categorized as read only, a processor that needs to update or otherwise modify the information must make a request for exclusive access to the memory location. The cache coherency controller then determines which other processors or which other processor cache currently have access to the memory cache line and makes the necessary arrangements for the requesting processor to have exclusive use of the memory cache line.
One method for a processor to obtain the exclusive use of a cache line is for the cache coherency protocol to invalidate other copies of other processor's access to the memory line cache currently in use. Once other processors access to the memory cache line has been invalidated, the remaining processor has exclusive use of the data and can modify the data as required.
Early attempts at cache coherency included write-through caches that ensured that information was updated simultaneously in memory and in other processor caches. Alternately, if all processors have access to a common memory bus, each processor can listen in or “snoop” on the bus for potentially conflicting requests by other processors for exclusive use of the memory location. Once a processor snooped another processor's request for memory location that the former currently had access to, it could determine that a potential memory conflict may exist. However, snooping requires a common system bus so that every processor could see every other processor's traffic and make sure the memory they currently have access to was not affected. Snooping also increases overhead, and provides the potential for errors if a message is missed.
Another method of cache coherency is a full directory-based system where rather than sending each transaction to every other agent or other processor in the system a table is maintained which indicates a processor's access to various cache lines. Regardless of the method used, the job of the cache coherency protocol is to make sure that if there are any caches in a system, especially cache between a processor and a memory, or between system input and output and a memory, and a processor has exclusive use of the line: no other cache has a valid copy of the same exclusive line. Cache coherency controllers can be implemented by processors or by memory.
SUMMARY OF THE INVENTION
According to one aspect of the invention, a memory system includes a main memory controller supplying data in response to transactions received by the main memory controller. A plurality of modules each include a cache memory for storing data supplied by the main memory controller. The modules request data from the main memory controller by sending module generated transactions to the main memory controller. A cache tag array includes a cache tag corresponding to at least each data line stored in one of the cache memories of the modules, there being a one-to-one correspondence between the cache tags and the data lines. The data lines together with their associated cache tags are combined and arranged in a plurality of sequential data chunks, the cache tags included in an initial portion of the data chunks (i.e, a first sequence of bits) followed by inclusion of the data lines in a subsequent portion of the data chunks (i.e., the usable bit positions following inclusion of all of the cache tag bit
Douglas Robert C.
McAllister Curtis R.
Yu Henry
Hewlett--Packard Company
Hudspeth David
Tzeng Fred F.
LandOfFree
Arrangement of data within cache lines so that tags are... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arrangement of data within cache lines so that tags are..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arrangement of data within cache lines so that tags are... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2957236