Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reissue Patent
2001-04-18
2004-05-11
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S100000, C711S144000, C711S154000
Reissue Patent
active
RE038514
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer systems having multiple processors with caches. In particular, the present invention relates to a system and method for implementing cache tags in a memory for maintaining cache coherence.
2. Description of the Background Art
The use of multiple processors is a recent trend in computer design. Each processor may work on a separate portion of a problem, or work on different problems, simultaneously. The processors used in the multi-processor architectures generally each have cache. A cache is a relatively small group, when compared to shared memories, of high speed memory cells that are specifically dedicated to a processor. A processor's cache is usually on the processor chip itself or may be on separate chips.
Processors use caches to hold data that the processor has recently accessed. A memory access is any action, such as a read or a write, where a processor receives, modifies, or receives as well as modifies the contents of a memory location. Generally, a processor can access data in its cache faster than it can access data in the main memory of the computer. Furthermore, by using data in its cache, a processor does not use the bus of the computer system to access data. This leaves the bus free for use by other processors and devices.
A particular problem associated with the use of caches is that the data becomes “stale.” A first processor may access data in the main memory and copy the data into its cache. The first processor may then modify the data in its cache. At the instant when the data in the cache of the first processor is modified, the corresponding data in the memory is stale. If a second processor subsequently accesses the original data in the main memory, the second processor does not find the most current version of the data. The most current version is in the cache of the first processor. The second processor, however, needs the most current version of the data. A prior art solution to this problem is for processors to eavesdrop on the bus. When the first processor detects the main memory access by the second processor for data that the first processor holds in its cache, the first processor inhibits the main memory and supplies the data to the second processor. In this way, a processor always receives the most current version of the data.
This prior art solution suffers from a number of problems. Computer architectures are moving to multiple-processor, multiple-bus configurations. The busses are coupled through an interface. For efficiency purposes, many signals on a bus are not transmitted across the interface to other busses. Among signals, which are not transmitted across the interface, are memory access signals where the path between source and target devices does not cross the interface. Many other devices also do not transmit all signals that they receive. For example, cross-bar switches, which concurrently connect multiple pairs of source and target ports, limit the transmission of memory access signals to the data path between source and target. When devices do not transmit all memory access signals over its data path, it is impossible for processors, which are not the source and target, to eavesdrop on memory accesses and therefore, impossible to determine when the data is stale. Thus, this prior art solution is not effective in systems that use devices that do not transmit all memory access signals.
Decreases in access time of main memories and increases in the size of caches have created other problems with eavesdropping. Eavesdropping on the bus assumes that a processor can inhibit the main memory and place the data on the bus faster than the main memory can access the data. Memories may, however, cache copies of recently accessed data within themselves; in which case, they often can provide data before a processor can inhibit the memory. Also, caches have become larger. Generally, larger memories, whether main memories or caches, require more time to access. Processors, with large caches, cannot access the larger cache fast enough to make the prior art solution workable unless other memory access are delayed while eavesdropping is performed. Such a delay would significantly degrade the performance of the processor.
Memory tags have been used to overcome some of these problems. A memory tag is associated with a memory address whose data is held in a cache. When a processor copies the data at that address into its cache, a memory tag is updated to identify the processor in whose cache the data is held. If a second processor attempts to access the data in the memory, the processor will receive the memory tag. Memory tags remove the need for eavesdropping. The memory tags are held in a separate memory device called a tag storage. When a processor reads or writes data to a memory address, both the tag storage and the memory address are accessed. The memory address is accessed for the data, and the tag storage is accessed for the possibility of a memory tag. If the accesses are performed sequentially, two accesses greatly slow the operation of the memory. If done in parallel, the tag storage greatly complicates the design of the memory controller. The width of the tag storage differs from the width of the main memory, in one embodiment the tag storage is 20 bits wide and the main memory is 64 bits wide. The different sized memories require complicated modifications to the memory controller. Furthermore, the tag storage requires changes in the bus width and requires additional circuit chips that occupy space, consume power, and add to the expense of the computer system.
Referring now to
FIG. 1
, a block diagram of a prior art memory
23
is shown. The prior art memory
23
comprises a data storage
40
, a tag storage
42
, and a memory controller
25
. The data storage
40
comprises a plurality of memory lines. Each memory line comprises one or more words and has an unique address. A first memory line
44
has address 0, and a second memory line
46
has address 1. Each address indicates a complete memory line. The remaining memory lines of the data storage
40
are addressed similarly so that a last memory line
48
has address N−1, where N is the total number of memory lines in the data storage
40
. Each word has a fixed bit size. A word may be any number of bits long, but currently is preferably 64 bits long or other powers of 2. A memory line
44
,
46
,
48
may include any number of words, but within the data storage
40
each memory line
44
,
46
,
48
has the same number of words. The tag storage
42
comprises a tag cell for each memory line of the data storage
40
. Each tag cell has an address that corresponds to a memory line of the data storage
40
. A tag cell
50
has an address 0 and corresponds to the first memory line
44
. Similarly, a tag cell
52
has an address 1 and corresponds to a second memory line
46
, and a tag cell
54
has address N−1 and corresponds to a final memory line
48
. Each tag cell
50
,
52
,
54
is more than one bit wide and contains data that indicates if the data held in the corresponding memory line
44
,
46
,
48
is valid data or if a processor holds the data. Data is valid, or “fresh,” if no processor holds the data in its cache. Fresh data may also be referred to as “unowned” data. Data is referred to in this application as “owned” and is not fresh if a processor holds a copy of the data in its cache. If a processor owns the data, the tag cell
50
,
52
,
54
contains an indicator for indicating that the data is owned and a tag that identifies the processor that owns the data.
Any memory operation that requires the data held at an address is referred to as an access. The basic operations are ReadOwned and WriteReturn. ReadOwned and WriteReturn will be discussed in detail below. Other operations may also be performed. The processor that is executing an operation is referred to as the accessing processor. Every memory access requires an operation on the addressed memory lin
James David V.
Stone Glen D.
Apple Computer Inc.
Fenwick & West LLP
Thai Tuan V.
LandOfFree
System for and method of efficiently controlling memory... 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 for and method of efficiently controlling memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for and method of efficiently controlling memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241107