Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2001-05-24
2002-07-09
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C345S568000
Reexamination Certificate
active
06418523
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer systems, and more particularly, to an apparatus for mapping virtual addresses to physical addresses in graphics applications.
2. Description of the Related Technology
As shown in
FIG. 1
, a conventional computer system architecture
100
includes a processor
102
, system logic
104
, main memory
106
, a system bus
108
, a graphics accelerator
110
communicating with a local frame buffer
112
and a plurality of peripherals
114
. The processor
102
communicates with main memory
106
through a memory management unit (MMU) in the system logic
104
. Peripherals
114
and the graphics accelerator
110
communicate with main memory
106
and system logic
104
through the system bus
108
. The standard system bus
108
is currently the Peripherals Connection Interface (PCI). The original personal computer bus, the Industry Standard Architecture (ISA), is capable of a peak data transfer rate of 8 megabytes/sec and is still used for low-bandwidth peripherals, such as audio. On the other hand, PCI supports multiple peripheral components and add-in cards at a peak bandwidth of 132 megabytes/sec. Thus, PCI is capable of supporting full motion video playback at 30 frames/sec, true color high-resolution graphics and 100 megabits/sec Ethernet local area networks. However, the emergence of high-bandwidth applications, such as three dimensional (3D) graphics applications, threatens to overload the PCI bus.
For example, a 3D graphics image is formed by taking a two dimensional image and applying, or mapping, it as a surface onto a 3D object. The major kinds of maps include texture maps, which deal with colors and textures, bump maps, which deal with physical surfaces, reflection maps, refraction maps and chrome maps. Moreover, to add realism to a scene, 3D graphics accelerators often employ a z-buffer for hidden line removal and for depth queuing, wherein an intensity value is used to modify the brightness of a pixel as a function of distance. A z-buffer memory can be as large or larger than the memory needed to store two dimensional images. The graphics accelerator
110
retrieves and manipulates image data from the local frame buffer
112
, which is a type of expensive high performance memory. For example, to transfer an average 3D scene (polygon overlap of three) in 16-bit color at 30 frames/sec at 75 Hz screen refresh, estimated bandwidths of 370 megabytes/sec to 840 megabytes/sec are needed for screen resolutions from 640×480 resolution (VGA) to 1024×768 resolution (XGA). Thus, rendering of 3D graphics on a display requires a large amount of bandwidth between the graphics accelerator
110
and the local frame buffer
112
, where 3D texture maps and z-buffer data typically reside.
In addition, many computer systems use virtual memory systems to permit the processor
102
to address more memory than is physically present in the main memory
106
. A virtual memory system allows addressing of very large amounts of memory as though all of that memory were a part of the main memory of the computer system. A virtual memory system allows this even though actual main memory may consist of some substantially lesser amount of storage space than is addressable. For example, main memory may include sixteen megabytes (16,777,216 bytes) of random access memory while a virtual memory addressing system permits the addressing of four gigabytes (4,294,967,296 bytes) of memory.
Virtual memory systems provide this capability using a memory management unit (MMU) to translate virtual memory addresses into their corresponding physical memory addresses, where the desired information actually resides. A particular physical address holding desired information may reside in main memory or in mass storage, such as a tape drive or hard disk. If the physical address of the information is in main memory, the information is readily accessed and utilized. Otherwise, the information referenced by the physical address is in mass storage and the system transfers this information (usually in a block referred to as a page) to main memory for subsequent use. This transfer may require the swapping of other information out of main memory into mass storage in order to make room for the new information. If so, the MMU controls the swapping of information to mass storage.
Pages are the usual mechanism used for addressing information in a virtual memory system. Pages are numbered, and both physical and virtual addresses often include a page number and an offset into the page. Moreover, the physical offset and the virtual offset are typically the same. In order to translate between the virtual and physical addresses, a basic virtual memory system creates a series of lookup tables, called page tables, stored in main memory. These page tables store the virtual address page numbers used by the computer. Stored with each virtual address page number is the corresponding physical address page number which must be accessed to obtain the information. Often, the page tables are so large that they are paged themselves. The page number of any virtual address presented to the memory management unit is compared to the values stored in these tables in order to find a matching virtual address page number for use in retrieving the corresponding physical address page number.
There are often several levels of tables, and the comparison uses a substantial amount of system clock time. For example, to retrieve a physical page address using lookup tables stored in main memory, the typical MMU first looks to a register for the address of a base table which stores pointers to other levels of tables. The MMU retrieves this pointer from the base table and places it in another register. The MMU then uses this pointer to go to the next level of table. This process continues until the physical page address of the information sought is recovered. When the physical address is recovered, it is combined with the offset furnished as a part of the virtual address and the processor uses the result to access the particular information desired. Completion of a typical lookup in the page tables may take from ten to fifteen clock cycles at each level of the search.
To overcome this delay, virtual management systems often include cache memories called translation look aside buffers (TLBs). A TLB is essentially a buffer for caching recently translated virtual page addresses along with their corresponding physical page addresses. Such an address cache works on the same principle as do caches holding data and instructions, the most recently used addresses are more likely to be used than are other addresses. Thus, if a subsequent virtual address refers to the same page as the last one, the page table lookup process is skipped to save time. A TLB entry is like a cache entry wherein a tag portion includes portions of the virtual address and the data portion includes a physical page frame number, protections fields, use bits and status bits. When provided with a virtual page address stored in the TLB (a translation hit), the TLB furnishes a physical page address for the information without having to consult any page lookup tables. When the processor requests a virtual page address not stored in the TLB (a translation miss), the MMU must then consult the page lookup tables. When this occurs, the physical page address recovered is stored along with the virtual page address in the TLB so that it is immediately available for subsequent use. This saves a substantial amount of time on the next use of the information. For example, accessing the information using a TLB may require only one or two clock cycles compared to the hundreds of clock cycles required for a page table lookup.
Virtual memory systems are common in the art. For example, in U.S. Pat. No. 5,446,854, Khalidi et al. disclose a method and apparatus for virtual to physical address translation using hashing. Similarly, Crawford et al. disclose a microprocessor architecture having segmentation mechanisms for tr
Knobbe Martens Olson & Bear LLP
Micron Electronics Inc.
Verbrugge Kevin
LandOfFree
Apparatus comprising a translation lookaside buffer for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus comprising a translation lookaside buffer for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus comprising a translation lookaside buffer for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2914401