Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2001-05-07
2002-06-18
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S209000
Reexamination Certificate
active
06408373
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory organization in computer systems. More specifically, the present invention relates to virtual memory systems that supports regions, and the process by which virtual addresses are translated to physical addresses.
DESCRIPTION OF THE RELATED ART
Many prior art computer systems use a technique called virtual memory, which simulates more logical memory than physical memory actually present and allows the computer to run several programs concurrently, regardless of their size. Concurrent user programs access main memory physical addresses via virtual addresses assigned by the operating system. The mapping of the virtual addresses to the main memory physical addresses is a process known as virtual address translation. Virtual address translation can be accomplished by any number of techniques, thereby allowing the processor to access the desired information in main memory.
The virtual address and physical address spaces are typically divided into equal size blocks of memory called pages, and a page table provides the translation between virtual addresses and physical addresses. Each page table entry typically contains the virtual address and/or the physical address, and protection and status information concerning the page. Status information typically includes information about the type of accesses the page has undergone. For example, a dirty bit indicates there has been a modification to data in the page. Because the page tables are usually large, they are stored in memory. Therefore each regular memory access can actually require at least two accesses, one to obtain the translation and a second to access the physical memory location.
Many computer systems that support virtual address translation use a translation lookaside buffer (TLB). The TLB is typically a small, fast, associative memory which is usually situated on or in close proximity to the processor unit and stores recently used pairs of virtual and physical addresses. The TLB contains a subset of the translations in the page table and can be accessed much more quickly. When the processing unit needs information from main memory, it sends the virtual address to the TLB. The TLB accepts the virtual address page number and returns a physical page number. The physical page number is combined with low order address information to access the desired byte or word in main memory.
In most cases the TLB cannot contain the entire page table. Accordingly, when a virtual page is accessed and the translation is not in the TLB, the page table is accessed to determine the translation of the virtual page number to a physical page number, and this information is entered in the TLB. Access to the page table can take twenty times longer than access to the TLB, and therefore program execution speed is optimized by keeping the translations being utilized in the TLB.
Some computers expand the virtual addressing concept by supporting regions. Regions provide the capability to effectively create independent local, shared and global address spaces within the virtual address space by dividing the virtual address space into equally sized regions. Typically, only a subset of regions can be active at any time. Associated with each region is a region identifier, which uniquely tags address translations of given regions. If the region identifier for a region is assigned to a particular process, this region space becomes local to that process. If the region identifier for a region is shared among processes, this region space becomes shared. If the region identifier for a region is shared by all processes, this region becomes global. Changing the region identifiers for the local regions effectively swaps virtual addresses from the local space of one process to the local space on another process. Thus, regions virtually eliminate the need to flush the TLB when switching process, thereby improving overall system performance.
Regions are typically supported in the TLB by region registers that map virtual region number bits (which are part of the virtual address) to region identifiers. The region registers require an additional look-up step to be performed before determining whether the translation for a virtual address is in the TLB. This additional look-up step sometimes becomes a critical path in the virtual-to-physical translation process. Accordingly, performance would be enhanced if this additional look-up step could be eliminated.
SUMMARY OF THE INVENTION
The present invention is a method and apparatus for pre-validating regions in a virtual addressing scheme. In accordance with the present invention, regions are pre-validated by storing both the virtual region identifier bits and region identifiers in translation lookaside buffer (TLB) entries. By storing both the virtual region identifier bits and region identifiers in TLB entries, the region registers can be bypassed when performing most TLB accesses. Accordingly, the region registers are removed from the critical path of the TLB look-up process and system performance is enhanced.
A TLB in accordance with the present invention includes entries having a valid field, a region pre-validation valid (rpV) field, a virtual region number (VRN) field, a virtual page number (VPN) field, a region identifier (RID) field, a protection and access attributes field, and a physical page number (PPN) field. In addition, a set of region registers contains the RIDs that are active at any given time. However, the region registers are not in the path of the TLB look-up process.
When a virtual-to-physical entry is established for a page in a region having an RID stored in a region register, the RID and VRN are stored in the appropriate fields of the TLB entry. In addition, the valid field is set and the rpV field is set to indicate that the TLB entry contains an active VRN-to-RID mapping, thereby pre-validating the region.
When a CPU in accordance with the present invention translates a virtual address to a physical address, a VRN and a VPN are extracted from the virtual address and provided to the TLB. The TLB is searched to find an entry having a set valid field, a set rpV field, and VRN and VPN fields containing entries matching the VRN and VPN extracted from the virtual address. If such an entry is found, the protection and access attributes field is used to determine whether the requested access should be allowed. If the requested access is allowed, the PPN from the PPN field of the TLB entry is combined with an offset from the virtual address to produce a physical address that is used to complete the memory access. Since the path through the region registers has been eliminated because the contents of the region registers have been “pre-validated” in the entries of the TLB, the speed of the virtual-to-physical look-up process is increased.
REFERENCES:
patent: 5923864 (1999-07-01), Inoue
patent: 5940872 (1999-08-01), Hammond et al.
patent: 6044447 (2000-03-01), Averill et al.
patent: 6047362 (2000-04-01), Zucker
patent: 6065091 (2000-05-01), Green
Bryg William R.
Burger Stephen G.
Gupta Rajiv
Hammond Gary N.
Hays James O.
Chace Christian P.
Institute for the Development of Emerging Architectures LLC
Kim Matthew
Plettner David A.
LandOfFree
Method and apparatus for pre-validating regions in a virtual... 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 pre-validating regions in a virtual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for pre-validating regions in a virtual... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2919564