Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-10-26
2004-04-13
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S118000, C711S141000
Reexamination Certificate
active
06721856
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention generally relates to an improved data processing system and in particular to improved memory management in a data processing system. Still more particularly, the present invention relates to improved cache memory management in a data processing system, which includes a system controller containing a bus transaction sequence log directory.
2. Description of the Related Art
Most data processing systems are controlled by one or more processors and employ various levels of memory. Typically, programs and data are loaded into a data processing system's memory storage areas for execution or reference by the processor, and are stored in different portions of the memory storage depending on the processor's current need for such programs or data. A running program or data referenced by a running program must be within the system's main memory (primary or main storage, which is typically random access memory). Programs or data which are not needed immediately may be kept in secondary memory (secondary storage, such as a tape or disk drive) until needed, and then brought into main storage for execution or reference. Secondary storage media are generally less costly than random access memory components and have much greater capacity, while main memory storage may generally be accessed much faster than secondary memory.
Within the system storage hierarchy, one or more levels of high-speed cache memory may be employed between the processor and main memory to improve performance and utilization. Cache storage is much faster than the main memory, but is also relatively expensive as compared to main memory and is therefore typically employed only in relatively small amounts within a data processing system. In addition, limiting the size of cache storage enhances the speed of the cache. Various levels of cache memory are often employed, with trade-offs between size and access latency being made at levels logically further from the processor(s). Cache memory generally operates faster than main memory, typically by a factor of five to ten times, and may, under certain circumstances, approach the processor operational speed. If program instructions and/or data which are required during execution are pre-loaded in high speed cache memory, average overall memory access time for the system will approach the access time of the cache.
In order to enhance performance, contemporary data processing systems often utilize multiple processors which concurrently execute portions of a given task. To further enhance performance, such multiple processor or multi-processor (MP) data processing systems often utilize a multi-level cache/memory hierarchy to reduce the access time required to retrieve data from memory. A multi-processor system may include a number of processors each with an associated on-chip, level-one (L1) cache, a number of level-two (L2) caches, and a number of system memory modules. Typically, the cache/memory hierarchy is arranged such that each L2 cache is accessed by a subset of the L1 caches within the system via a local bus. In turn, each L2 cache and system memory module is coupled to a system bus (or interconnect switch) such that an L2 cache within the multi-processor system may access data from any of the system memory modules coupled to the bus.
The use of cache memory imposes one more level of memory management overhead on the data processing system. Logic must be implemented to control allocation, deallocation, and coherency management of cache content. When space is required, instructions or data previously residing in the cache must be “swapped” out, usually on a “least-recently-used” (LRU) basis. Accordingly, if there is no room in the cache for additional instructions or data, then the information which has not been accessed for the longest period of time will be swapped out of the cache and replaced with the new information. In this manner, the most recently used information, which has the greatest likelihood of being again required, is available in the cache at any given time.
As noted, previous cache management techniques mostly depend on least-recently-used (LRU) algorithms in selecting a cache line victim for eviction and replacement. However, empirical measurements have shown that strict least-recently-used algorithms are unsatisfactory in many cases. Various enhancements to LRU algorithms have been proposed or implemented in recent years, such as software managed LRU, pseudo-random influences, etc. Basic symmetric multi-processor snooping protocols have also been utilized to influence cache management.
Even with a cache memory management scheme, there are additional, related problems that can cause system performance to suffer. For example, in data processing systems with several levels of cache/memory storage, a great deal of shuttling of instructions and data between the various cache/memory levels occurs, which consumes system resources such as processor cycles and bus bandwidth which might otherwise be put to more productive processing use. The problem has been exacerbated in recent years by the growing disparity between processor speeds and the operational speeds of the different system components used to transfer information and instructions to the processor.
It would be desirable, therefore, provide a system increasing the “intelligence” of cache management, and in particular to logging system bus transactions and utilizing that information to optimize cache management.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide an improved data processing system.
It is another object of the present invention to provide improved memory management in a data processing system.
It is yet another object of the present invention to provide improved cache memory management in a multi-processor data processing system, which includes a system controller containing a bus transaction sequence log directory.
The foregoing objects are achieved as is now described. In addition to an address tag, a coherency state and an LRU position, each cache directory entry includes historical processor access, snoop operation, and system controller hint information for the corresponding cache line. Each entry includes different subentries for different processors which have accessed the corresponding cache line, with subentries containing a processor access sequence segment, a snoop operation sequence segment, and a system controller hint history segment. In addition to an address tag, within each system controller bus transaction sequence log directory entry is contained one or more opcodes identifying bus operations addressing the corresponding cache line, a processor identifier associated with each opcode, and a timestamp associated with each opcode. Also, along with each system bus transaction's opcode, the individual snoop responses that were received from one or more snoopers and the hint information that was provided to the requestor and the snoopers may also be included. This information may then be utilized by the system controller to append hints to the combined snoop responses in order to influence cache controllers (the requestor(s), snoopers, or both) handling of victim selection, coherency state transitions, LRU state transitions, deallocation timing, and other cache management functions.
The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5335335 (1994-08-01), Jackson et al.
patent: 5355467 (1994-10-01), MacWilliams et al.
patent: 5369753 (1994-11-01), Tipley
patent: 5737759 (1998-04-01), Merchant
patent: 5809533 (1998-09-01), Tran et al.
patent: 5890200 (1999-03-01), Merchant
patent: 5987571 (1999-11-01), Shibata et al.
patent: 5995967 (1999-11-01), Iacobovici et al.
patent: 6052760 (2000-04-01), Bauman et al.
patent: 6138217 (2000-10-01), Hamaguchi
patent: 6230260 (2001-05-01), Luick
patent: 6282615 (2001-08-01), Arimilli et al.
Arimilli Ravi K.
Dodson John Steven
Fields, Jr. James Stephen
Guthrie Guy Lynn
Bracewell & Patterson L.L.P.
Salys Casimer K.
Thai Tuan V.
LandOfFree
Enhanced cache management mechanism via an intelligent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced cache management mechanism via an intelligent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced cache management mechanism via an intelligent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3256509