Hashed direct-mapped texture cache

Details Hashed direct-mapped texture cache Hashed direct-mapped texture cache

1998-07-07

2001-05-15

Yoo, Do (Department: 2187)

Electrical computers and digital processing systems: memory

Addressing combined with specific memory configuration or...

Addressing cache memories

C711S216000, C345S519000

Reexamination Certificate

active

06233647

ABSTRACT:

FIELD OF THE INVENTION
The present invention pertains to the field of computer controlled graphics display systems. More particularly, the present invention relates to an apparatus for and method of caching texture memory.
BACKGROUND OF THE INVENTION
Computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publishing, gaming, medical diagnosis, etc. In those applications, three-dimensional (3D) graphical objects are displayed on a computer screen by using a number of polygons to represent the three-dimensional objects. In order to portray a more realistic real-world representation, texture mapping is usually applied. Texture mapping refers to techniques for using two-dimensional (2D) texture images, or texture maps, for adding surface details to areas or surfaces of these 3D graphical objects. For example, given a featureless solid cube and a texture map defining a wood grain pattern, texture mapping techniques may be used to map the wood grain pattern onto the cube. The resulting image is that of a cube that appears to be made of wood. In another example, vegetation and trees can be added by texture mapping to an otherwise barren terra model in order to portray a landscape filled with vegetation and trees.
In computer systems having dedicated graphics hardware, images for use in texture mapping are typically stored in memory in the form of a collection of tiles. These tiles are addressed and managed as a virtually contiguous region of address space by a two-dimensional index (S,T). In other words, this memory management scheme treats a texture map as an array of small, contiguous tiles each including a number of texels. Thereby, memory management issues, such as caching, virtual-to-physical mapping, swapping, etc. are more easily executed.
In order to utilize computer resources more efficiently, computer graphics systems typically include a graphics co-processor for offloading processing burdens from the CPU of the computer system, and a texture memory for storing the texture data. Moreover, in order to further accelerate the texture mapping process, a special cache memory, also known as a texture cache, may also be implemented in the computer graphics systems for providing faster access to and temporary storage of frequently used tiles of texture data.
Texture caches, like other types of cache memories, are much smaller in capacity than the texture memory to which they are mapped. To this end, texture caches may be mapped to the local memory according to one of a plurality of mapping schemes.
FIG. 1
illustrates, as an example, a prior art direct-mapping scheme for mapping texture memory to texture cache. As shown in
FIG. 1
, texture map
50
consists of texture data tiles
0
to
3
in the first row, texture data tiles
4
-
7
in the second row, texture data tiles
8
-
11
in the third row, and texture data tiles
12
-
15
in the fourth row. On the other hand, texture cache
20
is made up of cache lines
0
-
3
in the first row and cache lines
4
-
7
in the second row. In this mapping scheme, texture data tiles within the same column are mapped to the same cache lines in the texture cache. For instance, as illustrated in
FIG. 1
, texture tiles
0
and
8
are mapped to cache line
0
, texture tiles
4
and
12
are mapped to cache line
4
, and texture tiles
7
and
15
are mapped to cache line
7
, etc.
Prior art direct-mapping schemes, such as the one illustrated in
FIG. 1
, have the advantage of simplicity. However, the prior art direct-mapping schemes have the disadvantage that only a single texture data tile from a given group can be present in the texture cache at a given time. That is, if two texture data tiles from the same group are frequently referenced, thrashing—repeated moving of the two tiles in and out of the cache—will occur. Unfortunately, in texture mapping, texture data tiles are commonly accessed one row or one column at a time for display or processing. For example, it is not uncommon for a particular column of the texture map
50
to be referenced frequently. In that situation, thrashing may occur, drastically reducing the usefulness and speed of the texture cache
20
. Therefore, prior art direct-mapping schemes are not ideal for the purposes of caching texture maps.
In order to provide for a more flexible caching method, other cache-mapping schemes, such as fully associative mapping, and set-associative mapping, may be used. However, those cache-mapping schemes are complicated, and implementations of such schemes require a large number of gates. Naturally, these extra gates unnecessarily increase manufacturing costs of the integrated circuits and consume large amounts of valuable die area. Therefore, what is needed is a caching scheme that has the advantage of simplicity, and yet, has the flexibility to accommodate portions of texture maps that have a wide aspect ratio such that thrashing is reduced.
SUMMARY OF THE PRESENT DISCLOSURE
The present invention pertains to an apparatus for and method of mapping texture memory to a texture cache such that cache contention is minimized. Significantly, in one embodiment of the present invention, addresses of the texture memory are mapped to entries of the texture cache according to a predetermined hashing scheme.
In furtherance of one embodiment of the present invention, texture memory is addressed as a virtually contiguous address space by a two-dimensional index (S, T), wherein S and T each includes n bits for forming an array of 2
n−k
×2
m−l
tiles of 2
k
×2
l
texels. According to this embodiment, each of S and T is further partitioned into a low order bit field and a high order bit field. In this embodiment, low order bits of each of S and T are directly mapped to storage locations of the texture cache. High order bits of S and T are mapped to entries of the texture cache according to a predetermined scheme. Particularly, high order bits of S and T are selectively “exclusive-or-ed” to generate corresponding addresses of the texture cache.
In another embodiment of the present invention, texture data are stored in a plurality of texture maps corresponding to different level of details. In that embodiment, each texture map includes an LOD index corresponding to a specific level of details of the texture map. In that embodiment, low order bits of S and T are directly mapped to the texture cache, while high order bits of S and T, and a plurality of bits of LOD are selectively “exclusive-or-ed” to generate corresponding addresses in the texture cache. In yet another embodiment of the present invention, texture data are addressed by a three-dimensional index (R, S, T). In that embodiment, high order bits of R, S and T are selectively “exclusive-or-ed” to generate addresses of the texture cache, while low order bits of R, S, and T are directly mapped to the texture cache. The texture cache according to one embodiment of the present invention may also include a mode selection input for selecting one of a plurality of operation modes in which different texture map addressing schemes and different mapping schemes are used.


REFERENCES:
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 5649143 (1997-07-01), Parady
patent: 5844576 (1998-12-01), Wilde et al.
patent: 5945997 (1999-08-01), Zhao et al.
patent: 5987567 (1999-11-01), Rivard et al.
patent: 6000019 (1999-12-01), Dykstal et al.
patent: 6002410 (1999-12-01), Battle

Affiliated with

Also associated with

Rating

Hashed direct-mapped texture cache does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hashed direct-mapped texture cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hashed direct-mapped texture cache will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2522720