Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-11-23
2003-02-11
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S003000, C711S205000, C711S210000
Reexamination Certificate
active
06519684
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory systems and, more particularly, to an improved method and apparatus for selecting and updating an entry in a translation-lookaside buffer (TLB) or other cache memory.
BACKGROUND OF THE INVENTION
Today's high performance data processing systems rely upon sophisticated memory management systems to translate logical addresses into real (physical) addresses. Logical addresses are the software addresses used by the programmer when writing software. Physical addresses are the hardware addresses used by the semiconductor chips and electronic circuitry running the software.
In a very simple microprocessor-based system, the central processing unit (CPU) is linked directly to memory. With this type of configuration, no memory mapping or task protection capabilities are provided, and the addresses generated by the CPU directly identify the physical locations to be accessed. This type of system, however, is unsuitable for multiple-task operations since there is no protection to prevent corruption of memory used by one task during execution of another.
A memory management unit (MMU) with one or more translation-lookaside buffers (TLBs) is often used to provide the address mapping and the task protection needed to construct a multi-tasking data processing system. The MMU acts as an interface between the CPU and the physical memory. The MMU controls all accesses to physical devices, and tasks can be prevented from accessing the memory resources used by other tasks. When under the control of an operating system with virtual memory capabilities, the logical-to-physical mapping functions allow tasks to utilize the entire address space of the CPU to build a memory system as large as the CPU address space without detailed knowledge of the physical characteristics of the system.
The logical address is generated by an instruction unit or a data unit of the CPU and is received as an input by the MMU. The MMU, using one or more TLBs, performs address translation and privilege checking for the logical address and, if the mapping is valid, drives the corresponding physical address to the data or instruction cache or some other type of memory. Note that the corresponding physical address produced by a TLB may be used to access either data or an instruction, depending upon whether the TLB is part of a data memory unit or part of an instruction memory unit.
Generally, a MMU contains one or more TLBs which are used to perform address translation and privilege checking. The MMU may also contain one or more cache memories that store actual data or instructions. Each entry in the TLB usually contains a logical address, a corresponding physical address, and one or more protection or control bits (collectively called attribute bits or attributes).
Typically, a TLB includes a content addressable memory portion (CAM), a random access memory portion (RAM), and associated control circuitry. The CAM is organized in a number of lines with each line capable of storing a logical address and each line including a corresponding match line. On each operation of the TLB, an incoming logical address is received by the TLB and compared to the logical addresses stored in the CAM. If the logical address matches a stored logical address, a TLB translation “hit” (also called a “match”) occurs, and the corresponding match line of the CAM produces a valid match signal.
Generally, each line of the CAM couples to a particular portion of the RAM and the enablement of a particular match line causes the RAM to produce a corresponding physical address. When the CAM does not contain the requisite logical address, a translation “miss” (also called “no match”) occurs, and a hardware state machine or a software routing is invoked to search main memory in order to determine the physical address that corresponds to the received logical address. This search is often called a “table search” or a “table walk” because it may require the data processing system to access and read more than one memory table stored in MAIN memory.
The main advantage of a TLB is that it saves a great deal of processing time. Rather than having to access tables in main memory every time a translation is required, the data processing system can quickly access the TLB and receive the correct physical address for certain selected logical addresses. However, TLB management (particularly when performed by software) must be minimized in order to fully realize the benefits of a virtual memory system.
In particular, the overhead required to update a TLB entry following an exception contributes directly to a loss in overall system performance, and it is thus desirable to minimize such overhead. In existing solutions, software (e.g., a “miss” handler) generally determines whether an existing entry is to be modified, or whether a new entry needs to be created. Following a miss, the miss handler also traverses the translation architecture to update the selected TLB entry with information from a translation table.
More specifically, when updating a TLB entry via software, the entry is selected based upon the known presence or absence of a corresponding entry which may be present in the TLB. The software must determine whether an existing entry is to be modified, or whether a new entry needs to be created in order for the TLB to remain consistent and to avoid multiple entries with the same logical to physical mapping, but differing access permissions. Prior solutions for updating TLB entries have generally involved a significant amount of software overhead.
REFERENCES:
patent: 4910656 (1990-03-01), Scales et al.
patent: 5893142 (1999-04-01), Moyer et al.
patent: 5913228 (1999-06-01), Bedarida
patent: 5920890 (1999-07-01), Moyer et al.
patent: 5995420 (1999-11-01), Hesley
patent: 6047354 (2000-04-01), Yoshioka et al.
patent: 6078995 (2000-06-01), Bewick et al.
patent: 6092172 (2000-07-01), Nishimoto et al.
patent: 6145057 (2000-11-01), Arimilli et al.
patent: 6148370 (2000-11-01), Kobayashi
patent: 6366978 (2002-04-01), Middleton et al.
patent: 6412043 (2002-06-01), Chopra et al.
Chace Christian P.
Clingan, Jr. James L.
Motorola Inc.
Yoo Do Hyun
LandOfFree
Low overhead method for selecting and updating an entry in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Low overhead method for selecting and updating an entry in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low overhead method for selecting and updating an entry in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3161360