Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1999-10-27
2002-09-03
Nguyen, Than (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S202000, C711S207000, C711S208000, C711S209000
Reexamination Certificate
active
06446186
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to processing computer data and, more particularly, to mapping physical addresses in a virtual address system.
BACKGROUND OF THE INVENTION
One of the elements within a typical computer system is a memory management unit (MMU). The MMU includes hardware and software that work in conjunction with a processing unit (i.e. CPU) of the computer system when data is retrieved from memory. In order to allow more effective retrieval of data such as image data from memory, it is conventional for the processing unit to employ “virtual” addresses which in turn correspond to physical addresses in physical memory, as part of a virtual address system.
When accessing data, the processing unit generates virtual addresses to access physical memory. Before these virtual addresses can be used to access data in physical memory, they must be translated into physical addresses. It is the MMU that controls the allocation and use of physical memory and provides the processing unit with mapping information which enables access to the data in the physical memory.
Prior Art
FIG. 2A
illustrates one example of mapping virtual addresses
100
to segments of physical memory
102
commonly referred to as “pages”
104
. A page
104
is a block of memory typically having a predetermined size. The specific size of a page
104
varies from system to system. A common page size is 4096 bytes.
The MMU maintains tables of mapping information, or “page tables”, that keep track of where each page of virtual memory is located in physical memory. The processing unit uses this mapping information when it translates virtual addresses to physical addresses. To this end, the mapping of virtual addresses through page tables in a virtual address system provides a large virtual address space, and allows programs to run on hardware with smaller physical memory configurations.
An example of a page table is shown in Prior Art FIG.
2
B. The page table
200
of Prior Art
FIG. 2B
contains Page Table Entries (PTEs)
202
, each one of which defines a mapping between a single virtual page and a physical page of memory by providing a physical address
204
of the physical page of memory. In addition to containing the physical address, the page table
200
may also include a plurality of flags
206
as a component of each PTE
202
. Examples of such flags
206
may include a lock, read, write, and/or page present flag.
Thus a given virtual page of memory is “mapped” to a page of physical memory by a specific PTE. The PTE is thus capable of “mapping” the virtual page to a physical page of memory.
The processing unit must frequently access the contents of a PTE as a consequence of managing virtual addresses and physical memory. In particular, the processing unit must access a PTE every time a virtual address must be mapped to a specific given physical page of memory. In the case of processing graphics data, and more particularly 3-D graphics data, such constant accessing of the page table becomes especially burdensome on the processing unit, taking a significant portion of the unit's computational cycles.
There is therefore a need for a system that allows for more efficient mapping of physical memory in a virtual address system by minimizing a number of look-ups in a PTE data structure during the mapping process.
DISCLOSURE OF THE INVENTION
A method, apparatus and article of manufacture are provided for minimizing the number of look-ups in a page table entry (PTE) data structure during mapping of physical memory. First, a primary virtual address in a PTE data structure is accessed. Next, it is determined whether a primary physical address corresponding to the accessed primary virtual address in the PTE data structure is associated with a physical page having at least one contiguous physical page.
Such determination may be facilitated by using headers for each of the entries in the PTE data structure. These headers may be read upon accessing the primary physical address in the PTE data structure in order identify whether any contiguous physical pages exist and, if so, how many and where they are located.
If it is determined that at least one contiguous physical page exists, information relating to both the primary virtual address, primary physical address, and any contiguous physical pages in the PTE data structure is retrieved in a single look-up. It can thus be appreciated that a look-up process in a PTE data structure having physical pages with a significant amount of contiguity will be accelerated in a very desirable manner. Such acceleration is a direct result of fewer required look-ups in the PTE data structure and more information being retrieved during each look-up.
If it is determined that the primary physical address is not associated with any contiguous physical pages, normal operation is carried out and information is only retrieved relating to the primary physical address in the PTE data structure.
In the case where the primary physical address is not associated with any contiguous pages, the information that is retrieved may include bits representative of the primary physical address. If, however, at least two contiguous pages are identified, the retrieved information may include information for allowing the calculation of bits representative of the contiguous physical addresses and the corresponding range of the virtual addresses. For example, the retrieved information may include a minimum and maximum limit of the virtual or physical address range.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.
REFERENCES:
patent: 4875160 (1989-10-01), Brown, III
patent: 5784707 (1998-07-01), Khalidi et al.
patent: 5873127 (1999-02-01), Harvey et al.
patent: 5897664 (1999-04-01), Nesheim et al.
patent: 6212613 (2001-04-01), Belair
Bittel Don
Priem Curtis
Nguyen Than
nVidia Corporation
Silicon Valley IP Group
Zilka Kevin J.
LandOfFree
Method, apparatus and article of manufacture for mapping... 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, apparatus and article of manufacture for mapping..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, apparatus and article of manufacture for mapping... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896747