Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-02-03
2002-12-03
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S137000
Reexamination Certificate
active
06490652
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of information storage and retrieval, and, more specifically, to a technique for improving cache memory performance.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever. ArtX, and all ArtX-based trademarks and logos are trademarks or registered trademarks of ArtX, Inc. in the United States and other countries.
2. Background Art
In a computer system there may be two types of memories, a large memory that is relatively slow, and a smaller memory called a “cache” memory that is relatively fast. Some portion of the larger memory is stored in the cache memory. When the computer system needs data, it first checks the cache to see if the data is already there (a cache “hit”). If the data is there, the computer gets it quickly (because the cache is fast) and can move on to some other step. If the data is not already in the cache, (a cache “miss”), the computer retrieves the data from the large memory. This slows computer operation down. Prior art cache memory environments have a disadvantage of very slow operation when data is not in the cache memory. The disadvantages of prior art cache environments can be understood by reviewing computer operation, particularly with respect to the storage and display of graphical information.
Storing and Displaying Graphical Data
Computers are often used to display graphical information. In some instances, graphical data is “rendered” by executing instructions from an application that is drawing data to a display. A displayed image may be made up of a plurality of graphical objects. Examples of graphical objects include points, lines, polygons, and three dimensional solid objects.
If you looked closely at a television screen, computer display, magazine page, etc., you would see that an image is made up of hundreds or thousands of tiny dots, where each dot is a different color. These dots are known as picture elements, or “pixels” for short when they are on a computer display and as dots when printed on a page. The color of each pixel is represented by a number value. To store an image in a computer memory, the number value of each pixel of the picture is stored. The number value represents the color and intensity of the pixel.
The accuracy with which a document can be reproduced is dependent on the “resolution” of the pixels that make up the document. The resolution of a pixel is the size of the number value used to describe that pixel. The size of the number value is limited by the number of “bits” in the memory available to describe each pixel (a bit is a binary number having a value of 1 or 0). The greater the number of bits available per pixel, the greater the resolution of the document. For example, when only one bit per pixel is available for storage, only two values are available for the pixel. If two bits are available, four levels of color or intensity are available. While greater resolution is desirable, it can lead to greater use of data storage. For example, if each pixel is represented by a 32-bit binary number, 320,000 bits of information would be required to represent a 100 X 100 pixel image. Such information is stored in what is referred to as a “Frame Buffer” (or “G array”).
Pixel Rendering and Texture Mapping
The process of converting graphics data and instructions into a display image is known as “pixel rendering.” During pixel rendering, color and other details can be applied to areas and surfaces of these objects using “texture mapping” techniques. In texture mapping, a texture image (also referred to as a texture map, or simply as a texture) is mapped to an area or surface of a graphical object to produce a visually modified object with the added detail of the texture image. A texture image may contain, for example, an array of RGB (red, green, blue) color values, intensity values, or opacity values.
As an example of texture mapping, given a featureless graphical object in the form of a cube and a texture image defining a wood grain pattern,.the wood grain pattern of the texture image may be mapped onto one or more surfaces of the cube such that the cube appears to be made out of wood. Other examples of texture mapping include mapping of product logo texture images to computer-modeled products, or mapping of texture images containing vegetation and trees to a barren computer-modeled landscape. Textures mapped onto geometric surfaces may also be used to provide additional motion and spatial cues that surface shading alone might not be capable of providing. For example, a featureless sphere rotating about an axis appears static until an irregular texture image or pattern is mapped to its surface.
Texture mapping involves using a texture image having a function defined in texture space. Typically, the texture space is represented as a two dimensional space, with “S” and “T” indices defining orthogonal axes (e.g., horizontal and vertical). A texture image is represented in texture space as an array in S and T of discrete texture elements or values called “texels.” The texture image is warped or mapped from the texture space into an image space having an array of picture elements called “pixels.” The pixels are associated with orthogonal axis coordinates “X” and “Y” in the image space which define a viewing plane for display. Based on the particular mapping function, a correspondence is generated between pixels representing an object or primitive in the image space and texels representing a texture image in the texture space.
Typically, a two-dimensional texture or pattern image is mapped onto a two or three-dimensional surface. For a two-dimensional surface, X and Y coordinates may be sufficient for defining a mapping function between pixels forming the surface and texels forming the texture image. For a three-dimensional surface, a perspective coordinate or other depth cueing mechanism may be provided to indicate distance from the viewing plane defined by the X and Y axes. The perspective coordinate may then be applied to the mapping function. For example, as the perspective coordinate value for a surface region increases (i.e., the surface region is further from the viewing plane), the mapping of the texture image may be darkened and/or compressed (i.e., neighboring pixels in the surface region may span an increased number of texels in the texture image), or otherwise warped, relative to surface regions having a lower perspective coordinate value. Through the application of depth cueing, the viewer is provided with a sense of distance or depth when viewing the rendered pixels.
FIGS
1
A-
1
C illustrate a mapping of a brick-pattern texture image in texture space to a triangle primitive (
100
) in image space.
FIG. 1A
illustrates triangle primitive
100
in image space prior to texture mapping.
FIG. 1B
illustrates the brick-pattern texture image in texture space.
FIGS. 1C
illustrates triangle primitive
100
in image space after texture mapping has completed.
In
FIG. 1A
, triangle primitive
100
is defined by vertices at X,Y coordinate pixel locations P
A
(X
A
,Y
A
), P
B
(X
B
,Y
B
) and P
C
(X
C
,Y
C
), where X is the horizontal axis and Y is the vertical axis. Pixels defining the perimeter of triangle primitive
100
may be explicitly stored in memory, or, to reduce storage requirements for individual primitives, the perimeter pixels may be linearly interpolated from the vertices defined by pixel locations P
A
(X
A
,Y
A
), P
B
(X
B
,Y
B
) and P
C
(X
C
,Y
C
). The interior of triangle primitive
100
is formed by those pixel locations that lie within the defined perimeter. The surface of triangle primitive
100
in this example comprises the union of the perimeter pixels (including the vertices) and the interior pixels.
In
FIG. 1B
, a
DeLaurier Anthony P.
Van Hook Timothy
ATI Technologies Inc.
Coudert Brothers LLP
Harriman II, Esq. J. D.
Kim Matthew
Vital Pierre M.
LandOfFree
Method and apparatus for decoupled retrieval of cache miss data 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 decoupled retrieval of cache miss data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for decoupled retrieval of cache miss data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2954003