Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
1999-07-13
2003-04-29
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S150000, C711S151000, C711S152000, C711S158000, C710S028000, C710S040000, C710S244000
Reexamination Certificate
active
06557084
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention generally relates to computer system memory and more specifically relates to memory systems that support shared memory locations.
2. Background Art
Today, our society is heavily dependent upon computers for everyday activity. Computers are found in homes, in business offices, and in most production and manufacturing environments. Most computer systems are controlled by a central processing unit (CPU) and have various levels of memory which can be used by the CPU to perform the various functions for which it has been programmed. Typically, computer programs are loaded into the computer system's memory storage areas and executed by the CPU. The programs and data are stored in different areas of the computer system's memory depending on what type of function the CPU is performing. Traditionally, the computer system's memory has been classified as either main memory (primary or main storage) or secondary memory (secondary storage). Programs and data need to be in main memory in order to be executed or referenced by a running program, while programs or data not needed immediately may be kept in secondary memory until needed and then brought into main storage for execution or reference.
In the 1960's, it became clear that the traditional memory storage hierarchy could be extended by one more level with dramatic improvements in performance and utilization. This additional level, the “cache,” is a high-speed memory that is much faster than the main memory. Cache storage is relatively expensive when compared with main memory and therefore, in a typical computer system, only relatively small amounts of cache memory are used. In addition, limiting the size of cache storage enhances the speed of the cache.
Cache memory generally operates faster than main memory, typically by a factor of five to ten times and may, under certain circumstances, approach the operational speed of the CPU itself. By keeping the most frequently accessed instructions and/or data in high speed cache memory, average overall memory access time for the system will approach the access time of the cache. There is a certain amount of overhead involved in shuttling information between various memory locations. This overhead is kept as small as possible so that it does not cancel out the performance increase achieved by utilizing cache storage. In addition, if the specific program instruction to be executed or data to be used has been pre-loaded into the cache, the CPU may execute the program instruction or use the data without returning to either main memory or secondary memory, thereby significantly increasing the operational speed of the system.
While adding caches to computer systems has been beneficial, there are additional costs associated with caches, particularly in today's multiprocessing computers. When a cache has a copy of information that also resides in memory, there is the potential that the copy of the information in the cache may not match the copy of the information in the memory. This is most apparent in multiprocessing systems, where there are multiple processors, caches, and either shared or exclusive memories. In these complex systems, a copy of information in one cache may not match copies of this information in other caches or memories.
To prevent potential problems due to these mismatches, engineers have designed coherency protocols. One of the more popular coherency protocols is called MESI, which stands for Modified, Exclusive, Shared, and Invalid. Each acronym letter of MESI stands for one potential state of a cache memory location (usually called a “line”). A cache line in the Modified state means that the cache line has been updated and any copies are currently invalid. A cache line in the Exclusive state means that the cache line has the only copy of the data, but the copy in main memory is valid. When a cache line is in a Shared state, more than one cache may be holding a copy of the line, but the copy in main memory is valid. Cache lines that are in the Invalid state essentially have invalid data.
To support the MESI protocol, processors have a “snooping” mechanism that monitors (“snoops”) the system bus. If one processor writes to a line in a cache, the bus controller (which contains the snooping mechanism) for other processors will invalidate their copies of this cache line. Alternatively, the bus controller for the processor that is performing the write could broadcast an invalidate transaction on the system bus to inform other caches that this line has been changed. Regardless of how the other caches learn of the invalidation, the caches that have copies of this line then know that they have old copies and that their processors must request new copies, either from main memory or from the cache that has the new copy of the line. Additionally, snooping mechanisms allow processors and caches to order retries for situations when a recently updated cache line has not yet been written to main memory, but when another processor wishes to read main memory for information contained in the recently updated cache line.
Thus, snooping and MESI work together to ensure cache coherency. Even with coherency protocols, however, there are times when reads from and writes to shared memory locations are not as efficient as they could be.
BRIEF SUMMARY OF INVENTION
According to the present invention, an apparatus and method for improving reads from and writes to shared memory locations is disclosed. By giving writes priority over reads, the current invention can decrease the time associated with certain sequences of reads from and writes to shared memory locations. In particular, load-invalidate-load sequences are changed to load—load sequences with the current invention. Furthermore, contention for a shared memory location will be reduced in particular situations when using the current invention.
The foregoing and other features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings.
REFERENCES:
patent: 5125083 (1992-06-01), Fite et al.
patent: 5432918 (1995-07-01), Stamm
patent: 5524235 (1996-06-01), Larson et al.
patent: 5909699 (1999-06-01), Sarangdhar et al.
patent: 6003106 (1999-12-01), Fields, Jr. et al.
patent: 6049847 (2000-04-01), Vogt et al.
patent: 6079006 (2000-06-01), Pickett
patent: 6092158 (2000-07-01), Harriman et al.
patent: 6105094 (2000-08-01), Lindeman
patent: 6161168 (2000-12-01), Kametani
patent: 6237067 (2001-05-01), Eberhard et al.
patent: 6286083 (2001-09-01), Chin et al.
Freerksen Donald Lee
Levenstein Sheldon Bernard
Lippert Gary Michael
Bragdon Reginald G.
International Business Machines - Corporation
Schmeiser Olsen & Watts
Vital Pierre M.
LandOfFree
Apparatus and method to improve performance of reads from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method to improve performance of reads from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method to improve performance of reads from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3089480