Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-07-03
2003-06-17
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S204000, C711S213000
Reexamination Certificate
active
06581140
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data processor memories, and in particular, the present invention relates to a method and apparatus for improving the speed in which memory is accessed.
RELATED ART
In general, data processing systems comprise a central processing unit (CPU) that executes instructions that are fetched from a main memory. One method to improve the performance of the CPU is to use cache memory. Cache memory is high speed memory that works in conjunction with the CPU and the main memory to provide the necessary data to the CPU. With this architecture, a lower latency response time is possible than if the CPU fetches all instructions and operands directly from main memory. The improved performance is possible because the cache contains the data that the CPU is most likely to request in the near future. The cache is typically also much faster than the main memory, therefore, the cache can usually provide the data required by the CPU much faster than the main memory. Part of the methodology used to load data into the cache is to predict and store the data that is frequently used by the CPU and is likely to be used by the CPU in the near future.
One type of cache memory is organized into a structure known as an “associative” structure (also referred to as “set associative”). In an associative structure, the blocks of storage locations are accessed as arrays having rows (often referred to as “sets”) and columns (often referred to as “ways”). When a cache is searched for bytes residing at an address, a number of bits from the address are used as an “index” into the cache. The index selects a particular set within the array, and therefore the number of address bits required for the index is determined by the number of sets configured into the cache. The act of selecting a set via an index is referred to as “indexing”. The addresses associated with bytes stored in the multiple ways of a set are examined to determine if any of the addresses stored in the set match the requested address. If a match is found, the access is said to be a “hit”, and the cache provides the associated bytes. If a match is not found, the access is said to be a “miss”. When a miss is detected, the bytes are transferred from the memory system into the cache. The addresses associated with bytes stored in the cache are also stored. These stored addresses are referred to as “tags” or “tag addresses”.
The blocks of memory configured into a set form the columns of the set. Each block of memory is referred to as a “way”; multiple ways comprise a set. The way is selected by providing a way value to the cache. The way value is determined by examining the tags for a set and finding a match between one of the tags and the requested address. A cache designed with one way per set is referred to as a “direct-mapped cache”. In a direct-mapped cache, the tag must be examined to determine if an access is a cache hit, but the tag examination is not required to select which bytes are transferred to the outputs of the cache. Since only an index is required to select bytes from a direct-mapped cache, the direct-mapped cache is a “linear array” requiring only a single value to select a storage location within it.
The hit rate in a data cache is important to the performance of a data processing system because when a miss is detected the data must be fetched from the memory system. The microprocessor will quickly become idle while waiting for the data to be provided. Set-associative caches require more access time than direct-mapped caches since the tags must be compared to the requested address and the resulting hit information must then be used to select which data bytes should be conveyed out of the data cache. As the clock frequencies of data processing systems increase, there is less time to perform the tag comparison and way selection. Therefore, there is a need for a data cache having the advantages of a set-associative cache with faster access times.
REFERENCES:
patent: 5845323 (1998-12-01), Roberts et al.
patent: 6016533 (2000-01-01), Tran
patent: 6247094 (2001-06-01), Kumar et al.
patent: 6356990 (2002-03-01), Aoki et al.
patent: 6418525 (2002-07-01), Charney et al.
patent: 6425075 (2002-07-01), Stiles et al.
Inoue et al., “Way-Predicting Set-Associative Cache for High Performance and Low Energy Consumption,” IEEE, pp 273-275, Aug. 1999.
Bruce Magnus K.
Snyder Michael D.
Sullivan Steven C.
Clingan, Jr. James L.
Elmore Stephen
Kim Matthew
Motorola Inc.
Noonan Michael P.
LandOfFree
Method and apparatus for improving access time in... 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 and apparatus for improving access time in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for improving access time in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3118788