Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-10-08
2002-09-17
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S136000, C711S159000, C711S160000, C711S205000, C711S207000
Reexamination Certificate
active
06453387
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to processors and computer systems, and more particularly to address translation memory systems used within computer systems and processors.
2. Description of the Related Art
A typical computer system includes a processor which reads and executes instructions of software programs stored within a memory system. In order to maximize the performance of the processor, the memory system must supply the instructions to the processor such that the processor never waits for needed instructions. There are many different types of memory from which the memory system may be formed, and the cost associated with each type of memory is typically directly proportional to the speed of the memory. Most modern computer systems employ multiple types of memory. Smaller amounts of faster (and more expensive) memory are positioned closer to the processor, and larger amounts of slower (and less expensive) memory are positioned farther from the processor. By keeping the smaller amounts of faster memory filled with instructions (and data) needed by the processor, the speed of the memory system approaches that of the faster memory, while the cost of the memory system approaches that of the less expensive memory.
Most modern computer systems also employ a memory management technique called “virtual” memory which allocates memory to software programs upon request. This automatic memory allocation effectively hides the memory hierarchy described above, making the many different types of memory within a typical memory system (e.g., random access memory, magnetic hard disk storage, etc.) appear as one large memory. Virtual memory also provides for isolation between different programs by allocating different physical memory locations to different programs running concurrently.
A typical modern processor includes a cache memory unit coupled between an execution unit and a bus interface unit. The execution unit executes software instructions. The cache memory unit includes a relatively small amount of memory which can be accessed very quickly. The cache memory unit is used to store instructions and data (i.e. data items) recently used by the execution unit, along with data items which have a high probability of being needed by the execution unit in the near future. Searched first, the cache memory unit makes needed data items readily available to the execution unit. When a needed data item is not found in the cache memory unit, the bus interface unit is used to fetch the needed data item from a main memory unit external to the processor. The overall performance of the processor is improved when needed data items are often found within the cache memory unit, eliminating the need for time-consuming accesses to the main memory unit.
Modern processors (e.g., x86 processors) support a form of virtual memory called “paging”. Paging divides a physical address space, defined by the number of address signals generated by the processor, into fixed-sized blocks of contiguous memory called “pages”. If paging is enabled, a “virtual” address is translated or “mapped” to a physical address. For example, in an x86 processor with paging enabled, a paging unit within the processor translates a “linear” (i.e., virtual) address produced by a segmentation unit to a physical address. If an accessed page is not located within the main memory unit, paging support constructs (e.g., operating system software) load the accessed page from secondary memory (e.g., magnetic disk) into main memory. In x86 processors, two different tables stored within the main memory unit, namely a page directory and a page table, are used to store information needed by the paging unit to perform the linear-to-physical (i.e., virtual-to-physical) address translations.
In order to reduce the number of required main memory unit accesses to retrieve information from the page directory and page table, a small cache memory system called a translation lookaside buffer (TLB) is typically used to store the most recently used virtual-to-physical address translations. As the amount of time required to access a virtual-to-physical address translation in the TLI is relatively small, overall processor performance is increased as needed address translations are often found in the readily accessible TLB.
In general, processor performance increases with the number of address translations (i.e., entries) in the TLB. When an entry corresponding to an input linear (i.e., virtual) address is found within the TLB, the TLB asserts a “HIT” signal. As the number of entries in the TLB increases, the time required to generate the HIT signal also increases. Any increase in the time required to generate the ST signal may increase the amount of time which must be allocated to address translation. Address translation may be on a critical timing path within the processor, thus increasing the number of TLB entries beyond a certain number may result in a reduction in processor performance.
Data items from main memory are stored within cache memory units (i.e., “caches”) in groups called “blocks”. Cache memory systems are distinguished from one another by where a given data block may be placed within or “mapped into” the caches. In a “direct mapped” cache, there is only one set of locations, collectively referred to as a “line”, within the cache where a given block may be placed. In a “fully associative” cache, a given block may be placed in any line within the cache. In a “set associative” cache, a given block can only be placed in one of a restricted set of lines within the cache.
When a needed data item is not found within the cache, a new block containing the data item must be fetched from main memory and placed within a line of the cache. If all of the lines where the block may be placed (i.e., “candidate” lines) are filled with valid data, one of the candidate lines must be removed from the cache to make room for the new block. In the case of a direct-mapped cache, there is only one candidate line, and this line must be removed from the cache to make room for the block. In a fully associative or set-associative cache, there are multiple candidate lines. A replacement “policy” or “strategy” is used to select the candidate line to be removed from the cache in order to make room for the new block.
Common cache line replacement policies include random, least recently used (LRU), and first in first out (FIFO). In a random replacement strategy, one of the candidate lines is randomly selected for replacement. The LRU replacement strategy involves replacing the candidate line which has remained “unused” for the longest period of time. A candidate line is referred to as “unused” when a needed data item is not found within the candidate line. The FIFO replacement strategy replaces the candidate line which has been stored in the cache for the longest period of time.
For some cache sizes and configurations, employing the LRU replacement strategy may result in a greater number of needed data items being found within the cache. A TLB is one form of cache memory, therefore it would thus be desirable to have a TLB which implements an LRU replacement strategy.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a memory unit (e.g., a translation lookaside buffer or TLB) employing a least recently used (LRU) replacement strategy. The memory unit may include a memory subunit for storing data items, circuitry coupled to the memory subunit for determining if the memory subunit contains a needed data item, and a control unit for controlling the storing of data items within the memory subunit. The memory subunit may include, for example, n entry locations for storing data items where n≧2. The memory unit may generate a first signal indicating which of the n entry locations are currently in use (i.e., contain valid data items), and the circuitry coupled to the memory subunit may produce a second signal indicating which of the n entry locations contains the needed data item. When a needed data item is n
Advanced Micro Devices , Inc.
Chace Christian P.
Conley Rose & Tayon PC
Kim Matthew
Kivlin B. Noäl
LandOfFree
Fully associative translation lookaside buffer (TLB)... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fully associative translation lookaside buffer (TLB)..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fully associative translation lookaside buffer (TLB)... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2867943