Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – Addressing cache memories
Reexamination Certificate
1998-04-17
2003-06-03
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Addressing combined with specific memory configuration or...
Addressing cache memories
C711S205000, C711S206000
Reexamination Certificate
active
06574698
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for data processing in general, and in particular to a method and system for enhancing the speed of a memory access within a data processing system. Still more particularly, the present invention relates to a method and system for accessing a cache memory within a data processing system.
2. Description of the Prior Art
A common way of organizing a main memory within a data processing system for memory access is by dividing the main memory into blocks of contiguous locations called pages, each page having a same number of lines, each line having a same number of bytes. Accordingly, an address utilized to access the main memory typically includes a page number, a line number, and a byte location. Such an address is commonly referred to as a real address (RA) or physical address. However, when a virtual addressing scheme is being utilized, the access address is then referred to as an effective address (EA) or virtual address. Given the fact that instructions or data are relocatable within the virtual addressing scheme, the effective address or virtual address must be mapped back to a corresponding real address or physical address that specifies an actual location within the main memory. Nevertheless, because the main memory is conceptually divided in pages, as mentioned previously, the low-order bits of an effective address that typically identify a byte within a page of the main memory usually do not require any translation, while only the high-order bits of the effective address are required to be translated to a corresponding real page address that specifies the actual page location within the main memory.
In order to increase the speed of access to the data stored within the main memory, modern data processing systems generally maintain the most recently used data in a high-speed memory known as a cache memory. This cache memory has multiple cache lines, with several bytes per cache line for storing information in contiguous addresses within the main memory. In addition, each cache line has an associated tag that typically identifies a partial address of a corresponding page of the main memory. Because the information within each cache line may come from different pages of the main memory, the tag provides a convenient way to identify to which page of the main memory a cache line belongs.
In a typical cache memory implementation, information is stored in one or several memory arrays. In addition, the corresponding tags for each cache line are stored in a structure known as a directory or tag array. Usually, an additional structure, called a translation lookaside buffer (TLB), is also utilized to facilitate the translation of an effective address to a real address during a cache memory access.
In order to access a byte in a cache memory with an effective address, the line portion (mid-order bits) of the effective address is utilized to select a cache line from the memory array along with a corresponding tag from the directory. The byte portion (low-order bits) of the effective address is then utilized to choose the indicated byte from the selected cache line. At the same time, the page portion (high-order bits) of the effective address is translated via the translation lookaside buffer to determine a real page number. If the real page number obtained by this translation matches the real address tag stored within the directory, then the data read from the selected cache line is the data actually sought by the program. This is commonly referred to as a cache “hit,” meaning the requested data was found in the cache memory. If the real address tag and translated real page number do not agree, a cache “miss” occurs, meaning that the requested data was not stored in the cache memory. Accordingly, the requested data have to be retrieved from the main memory or elsewhere within the memory hierarchy.
With a direct-mapped cache, only one of the group of corresponding lines from all pages in a real memory page can be stored in the cache memory at a time; but in order to achieve a better “hit” ratio, sometimes a set-associative cache is utilized instead. For example, with an N-way set associative cache, corresponding lines from N different pages may be stored. Since all entries can be distinguished by their associated tags, it is always possible to resolve which of the N lines having the same line number contains the information a program requested. The resolution requires comparison of the translated real page number to the N tags associated with a given line number. Each comparison generates an input to an N-to-
1
multiplexor to select an appropriate cache line from among the N possibilities.
Regardless of the cache architecture being utilized, the critical path for address translation still includes a translation lookaside buffer, a directory and a group of comparison circuits, which must be utilized during a cache access to select an appropriate cache line within the cache memory. Because this critical path can contribute certain unnecessary delays to the entire cache access process, it would be desirable to provide an improved method and system for address translation during a cache access within a data processing system.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore an object of the present invention to provide an improved method and system for data processing.
It is another object of the present invention to provide an improved method and system for enhancing the speed of a memory access within a data processing system.
It is yet another object of the present invention to provide an improved method and system for accessing a cache memory within a data processing system.
In accordance with a preferred embodiment of the present invention, a cache memory includes a memory array and a directory along with a translation lookaside buffer. The cache memory may be accessed by an effective address that includes a byte field, a line field, and an effective page number field. In order to facilitate the cache access process, a translation array is provided that has the same number of rows as the translation lookaside buffer. Each row of the translation array has the same number of array entries as the product of the number of lines per page of memory and the set associativity of the cache. The translation array is updated after the contents of the directory or the translation lookaside buffer have been updated. The translation array can be accessed with the contents of a line field of an effective address to determine whether or not the cache so memory stores data associated with translated address.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4797814 (1989-01-01), Brenza
patent: 5299147 (1994-03-01), Holst
patent: 5835928 (1998-11-01), Auslander et al.
patent: 5970512 (1999-10-01), Martens et al.
patent: 5996062 (1999-11-01), Sachs
Dhong Sang Hoo
Silberman Joel Abraham
Bracewell & Patterson L.L.P.
Bragdon Reginald G.
International Business Machines - Corporation
Salys Casimer K.
Vital Pierre M.
LandOfFree
Method and system for accessing a cache memory within a data... 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 system for accessing a cache memory within a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for accessing a cache memory within a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3089137