Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-05-19
2001-01-16
Chan, Eddie P. (Department: 2751)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S122000, C711S120000, C711S135000, C711S154000, C711S145000
Reexamination Certificate
active
06175899
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to multiprocessor computing systems wherein each of a plurality of processors may require access to information stored in main memory and additionally stored in multilevel cache memory locations having graduated line-size storage.
BACKGROUND OF THE INVENTION
Cache storage schemes have been developed to provide faster access to frequently required data or instructions. Information which a processor needs can be retrieved from the main memory storage location; however, such retrieval may take a long time, particularly when viewed from the perspective of the increasingly fast processors which have been and are continuously being developed. In order to reduce the number of wait states involved when accessing information from main memory, more responsive memory locations have been provided in the form of caches. Each cache is smaller than the main memory storage location and is provided to store copies of certain lines of information from the main memory. Generally, a cache will be used to store the most recently and/or most frequently accessed information in order to provide that information to the processor with minimal memory access time.
Multiple layers or levels of cache memory have been implemented between the main memory and the processor to further expand the caching capabilities of a system and to provide faster access to larger amounts of information. Typically, a higher level memory location (e.g., L
3
) will be a large memory cache for storing some subset of the information contained in the main memory, while lower level memory locations (e.g., L
2
) will be smaller memory caches for storing subsets of the information contained in the higher level memory locations. Until recently, the monetary expense of incorporating cache memory into computer systems prohibited widespread usage of multilevel caches, in spite of the improved time efficiency. Now, however, multilevel cache usage is widespread, and is particularly popular in multiprocessor systems and in distributed computing environments.
In multiprocessor systems, more than one processor may require access to information stored at a particular location.
FIG. 1
illustrates a multiprocessor system, M, having four processors, P
A
through P
D
, each associated with a lower level cache memory location, L
2A
through L
2D
. Each of the lower level cache memory locations contains a subset of the information stored at the higher level cache memory location L
3
, which in turn stores a subset of the information stored at the main memory (not shown). The multiprocessor system may additionally be connected along an interconnection network,
20
, to another multiprocessor system, M′, having processors P
E
through P
H
associated with lower level caches L
2E
through L
2H
, which contain subsets of the information stored at the higher level cache location L
3
′, as shown in
FIG. 2
, and further to any number of multiprocessor systems M
x
(not shown).
In distributed computing systems, it is beneficial to incorporate multilevel caches to facilitate faster access to the stored information, whether the access is from a local processor or from remote processors located elsewhere on the network. Therefore, multilevel caches are provided which can be accessed by not only one or more local processors, but also by a plurality of remote processors.
In general, in multiprocessor systems, one processor is the designated “owner” of the information stored at a particular cache location, and that owner will be responsible for updating information in the cache and for allowing other processors to update the information stored in that cache. Any update to a given cache location is ideally carried through to all other stored copies of the information, in order to assure that each location has the most recent copy of the information stored therein, providing so-called cache coherency. However, the time and bandwidth required to broadcast and globally implement every memory update can be prohibitive. Therefore, systems generally adhere to one of two basic approaches to memory updates, implementing a write through or a write back policy, or a modified combination of both.
Under a write through policy, each update to a cache location is written to the next level cache, where the resident copy of the information will be updated and sent to the next level cache, with the change ultimately propagating through to all copies of the information. As noted above, such a policy is optimal for assuring that all retrieved information is not stale; however, time and resources are tied up throughout implementation of the write through policy.
As an alternative, the write back policy provides that an update is done at the cache location, with each of the other copies of the information, including the main memory, only being updated later when access to that copy is requested by its associated processor. When the update is done to a line of data at the “owned” memory location, an invalidation signal is sent out on the bus indicating that the line is being modified. Each cache location which has a copy of that line must then invalidate its resident copy of the line. Upon a subsequent attempt to access that line of data, the requesting processor learns that the line has been invalidated. The requesting processor must issue a request for the updated data from the owner, and only then will the line of data at the “non-owned” cache location be updated.
In bus-based systems, cache locations learn of an update or an invalidation by monitoring or “snooping” for any write requests or invalidation signals that involve information stored at that location. The write request will be issued by the owner of the information, and will identify that information which is to be updated. Invalidation signals will identify the line of information which has been updated. Therefore, the snooping location simply looks for write packets or invalidation signals which include any identifiers matching its stored information.
A problem that arises when operating under a write back policy in a multiprocessor environment is that different storage locations may have different copies of the stored information. Since one processor can be accessing a lower level cache, for example P
A
accessing information ftom L
2A
, at the same time as another processor is accessing the “same” information from a higher level cache, P
E
accessing information from L
3
, each may be receiving a different version of the stored information. The foregoing is particularly a concern when the request for access to the information is received at a cache location after the write to the owned location but before the invalidation signal has been received at the cache-location.
The invalidation process becomes even more problematic when the granularity of sharing between levels is altered. For example, there may be a difference in the line sizes between memory locations as different levels, so that one line of information from location L
3
will be broken up for storage at the lower level locations, L
2
, with different portions of that line being stored at four different cache locations in level L
2
. With reference to
FIG. 2
, assume that a line of information stored at L
3
has components of that line stored at each of locations L
2A
through L
2D
. Other lines of information from L
3
may be stored in fewer than the four locations, depending upon the line size in the L
2
caches and depending upon the amount of information in the line from L
3
. If the line of information stored at L
3
is owned by a processor in M′, and that processor issues an update for the line, L
3
will put an invalidation signal on the L
2
bus so that all cache locations storing any portions of the line will be invalidated. Since four separate invalidation signals must be sent, and L
3
may have to wait for access to the L
2
bus, it is possible that P
A
, P
B
, P
C
or P
D
may attempt to read that line from its associated cache in the interim between L
3
being updated and L
3
s
Baylor Sandra Johnson
Hsu Yarsun
Cameron Douglas W.
Chan Eddie P.
Dougherty Anne Vachon
International Business Machines - Corporation
Kim Hong
LandOfFree
Method for providing virtual atomicity in multi processor... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for providing virtual atomicity in multi processor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for providing virtual atomicity in multi processor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2450782