System for low miss rate replacement of texture cache lines

Details System for low miss rate replacement of texture cache lines System for low miss rate replacement of texture cache lines

2000-09-18

2003-07-08

Tung, Kee M. (Department: 2676)

Computer graphics processing and selective visual display system

Computer graphics display memory system

Texture memory

C345S557000, C345S582000, C345S559000, C711S136000

Reexamination Certificate

active

06590579

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to texture mapping in graphics systems, and more particularly to texture cache controllers.
BACKGROUND ART
Texture mapping is a powerful technique for adding realism to a computer-generated scene. In its basic form, texture mapping places an image of an object's texture onto an object in a scene. Because texture mapping is so useful, it is provided as a standard rendering technique both in graphics software interfaces and in computer graphics hardware.
When mapping a texture image onto an object, the color of the object at each picture element, or pixel, is modified by a corresponding color from the image. In general, obtaining this color from the image conceptually requires several steps. The image is normally stored as a sample array, so a continuous image must first be reconstructed from the samples. Next, the image must be warped to match any distortion (such as caused by perspective) in the projected object being displayed. Then, this warped image is filtered to remove high-frequency components that would lead to aliasing in the final step and resampled to obtain the resulting color to apply to the pixel being textured.
In practice, the required pre-filtering is approximated by one of the several methods. One of the most popular is mipmapping (from MIP, multium in pravo, many things in a small space). See L. Williams, “Pyramidal Parametrics”, Proceedings of SIGGRAPH '83, Computer Graphics, vol. 17, no. 3, July 1983, pp. 1-11.
In basic texture mapping, a texture image is applied to a polygon, such as a triangle, which is called a “primitive”. The pixel locations of the primitive in the screen space are given with orthogonal indices X and Y for the screen space coordinates. The polygon is rendered based on the geometry of the polygon, the translation, distortion, and rotation of the polygon in the scene being rendered, lighting conditions, and information about the appearance of the polygon.
A map of values with orthogonal indices U and V for the texture space coordinates specifies information about the texture of the polygon. The texture image, or “texture tile”, is made up of texture elements, or “texels,” which are analogous to the pixels of the image of the polygon being rendered in the screen space. The texture tile is mapped to the polygon such that the polygon appears to have the texture tile attached to it, like wallpaper on a wall. This is accomplished by assigning texture coordinates (U,V) to the vertices of the polygon.
As a polygon undergoes translations, distortions and rotations relative to the scene, the size, shape and orientation of the texture information attached to the polygon may be changed or resized. Because the scale of the projection of a texture map to the screen space varies as the polygon moves in the scene, it is conventional to use maps of varying levels of detail in place of a single texture map. These maps are called “mipmaps” and they allow the mapping of texture map texels to screen space pixels to be carried out efficiently. In typical mipmaps, a hierarchy of maps is constructed, based on one full resolution map. The full resolution map constitutes the lowest mipmap level map. Each higher mipmap level contains a map in which the texels each represent a proportional texel region in the map one mipmap level lower. The highest mipmap level map typically contains only one texel.
The polygon locations and mipmaps are stored in a memory, such as the main memory of the computer, but a cache is placed operationally between the main memory and the graphics processor in such systems. The caching technique is beneficial because processors, including graphics co-processors, frequently cluster their references in time and space to blocks of all data stored. When the blocks are stored locally, the access times are drastically reduced which speeds up the overall operation of the system over a system which must always access main memory.
The basic problem with caching involves establishing an efficient technique for allocating cache spatial and temporal resources. When the block of data required is found in the cache, it is a “hit” and a copy of the requested data is sent to the processor. When the block of data is not found, it is a “miss” and the requested data is read from the larger, slower main memory and transferred both to the cache and to the processor. When the block of data from the miss is added to the cache, it replaces a block of data already in the cache.
There are a number of replacement strategies which are well known, but the most universally used is the “least recently used” (LRU) strategy where the least recently used block of data is replaced in the cache. Unfortunately, it sometimes replaces the block of data which will be needed next, and this will cause a subsequent miss which will slow down the texturing process.
With the importance of speed in order to obtain fast, real-time 3D graphics, a better system for cache replacement of texture tiles has been long sought but has eluded those skilled in the art.
DISCLOSURE OF THE INVENTION
The present invention provides a system and method of faster mipmap texturing in which texture tiles are replaced in a set-associative texture cache. When a miss occurs, a new texture tile is called from main memory to replace a texture tile which is not shared between the traversal segment (the segment being traversed) and the next segment to be traversed and which is the least recently used. This is accomplished by maintaining a record for each cache line describing the texture tile it contains. The record specifies at least if: the current traversal segment is using the texture tile; the texture tile touches the right edge of the current traversal segment; the texture tile touches the bottom edge of the current traversal segment; or the texture tile has been the least recently accessed.
The present invention provides a cache data replacement process which inventors have named a “least likely to be reused” (LLR) method.
The present invention provides a cache line replacement strategy which combines the LLR method with other methods.
The present invention has the advantage of reducing the miss rate of the texture cache over other methods by taking advantage of spatial dependency.


REFERENCES:
patent: 5828382 (1998-10-01), Wilde
patent: 6233647 (2001-05-01), Bentz et al.
patent: 6295068 (2001-09-01), Peddada et al.
patent: 6490652 (2002-12-01), Van Hook et al.
Lance Williams, “Pyramidal Parametrics,” Proceedings of SIGGRAPH '83, Computer Graphics, vol. 17, No. 3, Jul. 1983, pp. 1-11.

Affiliated with

Also associated with

Rating

System for low miss rate replacement of texture cache lines does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for low miss rate replacement of texture cache lines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for low miss rate replacement of texture cache lines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3071374