Abstract:
The invention provides a method of operating a cache memory so that operation is optimized. Instead of fetching data immediately upon a cache miss, the present invention continues with subsequent cache accesses. Decoupled from cache access, cache misses are fetched to cache. During operation, for each request in a sequence of data requests, it is determined if the requested data can be found in cache memory. If the data is not found in the cache, the next request in the sequence is processed without first retrieving the data pending from the earlier request. A miss list is generated for each of the requests in the sequence of requests whose data is not found in the cache. The data that is associated with the requests in the miss list is obtained from DRAM and used to satisfy the requests. Some cache lines may have one or more pending hits to data associated with the cache line. Those requests are kept in a pending hits list and processed in order as required. There may also be pending misses kept in a pending misses list where the list contains one or more pending misses to data associated with the cache line. A flag or indicator is set for a cache line when there are misses associated with the cache line.

Description:
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 brick pattern is stored as a texture image referenced by S and T coordinates. The brick pattern may be mapped to pixels in image space by accessing texels at integer S and T coordinates. In accordance with a particular mapping function, pixel vertices P A , P B  and P C  of the triangle primitive correspond to S and T coordinates (S A ,T A ), (S B ,T B ) and (S C ,T C ), respectively. The orientation of the mapped vertices indicates rotation and scaling of triangle primitive  100  with respect to the S and T texture space. 
     FIG. 1C shows triangle primitive  100  having pixel vertices with corresponding X,Y coordinates for the image space, as well as texture space S,T coordinates for extracting texel values. The pixel vertices are P A (X A ,Y A ; S A ,T A ), P B (X B ,Y B ; S B ,T B ) and P C (X C ,Y C ; S C ,T C ). The brick pattern of the texture image of FIG. 1B appears within triangle primitive  100  at slightly reduced scale, and at an approximately forty-five degree rotational offset from the X-axis. Other texture images may be similarly texture mapped to surfaces in render operations. 
     As the pixels defining a surface are rendered, S and T coordinate values are generated for each pixel based on the mapping function. The generated S and T coordinate values are then used to obtain a texel value for each rendered pixel in the image space. However, the generated S and T coordinate values are generally fractional values (i.e., not integer values). Consequently, the generated S and T coordinate values often correspond to a location in the texture space that falls between the texels of the texture image array. 
     Several options exist for selecting a texture value, given real S and T coordinate values. One of the simplest options is to round the S and T coordinate values to the nearest integers, and then select the texel corresponding to the rounded integer coordinate values. A more accurate representation is produced by interpolating between the four nearest samples that surround the real (S,T) location. For example, a bilinear interpolation algorithm (i.e., bilinear filtering), or higher-order interpolation algorithm, may be used to interpolate texel values for fractional S and T coordinates. Bilinear interpolation is illustrated in FIG.  2 . 
     In FIG. 2, a pixel PN is mapped to S and T coordinates (L+α,M+β). The four nearest texels in texture space are TXL(L,M), TXL(L+1,M), TXL(L,M+1) and TXL(L+1,M+1). To perform bilinear interpolation (or filtering), a linear interpolation is performed between the texel pairs [TXL(L,M), TXL(L+1,M)] and [TXL(L,M+1), TXL(L+1,M+1)] to determine intermediate pixel values P N ′(L+α,M) and P N ″(L+α,M+1), respectively. These linear interpolation functions are performed to implement equations (1) and (2) below. 
     
       
           P′   N ( L+α,M )=(1−α) TXL ( L,M )+α TXL ( L+ 1, M )  (1) 
       
     
     
       
           P″   N ( L+α,M+ 1)=(1−α) TXL ( L,M+ 1)+α TXL ( L+ 1 ,M+ 1)  (2) 
       
     
     A third linear interpolation operation is performed on intermediate pixel values P′ N (L+α,M) and P″ N (L+α,M+1) to obtain P N (L+α,M+β) in accordance with the following equation (3). The linear interpolation operations for the intermediate pixels may be performed along the opposite axis as well, or the linear interpolation operations may be combined to implement a form of equation (4) below.                        P   N          (       L   +   α     ,     M   +   β       )       =                    (     1   -   β     )            P   N   ′          (       L   +   α     ,   M     )         +                              β                     P   N   ″          (       L   +   α     ,     M   +   1       )                       (   3   )                                  =                [     1   -       (     α   +   β     )          TXL        (     L   ,   M     )         +                                  [         α        (     1   -   β     )            TXL        (       L   +   1     ,   M     )         +                                [         β        (     1   -   α     )            TXL        (     L   ,     M   +   1       )         +                                α                 β                   TXL        (       L   +   1     ,     M   +   1       )                       (   4   )                                
     The above equations (1)-(4) may be implemented in any equivalent form, or the equations may be approximated, to optimize the calculation apparatus for speed and/or complexity. 
     Using the texel selection processes described above, severe aliasing of the texture may occur if the surface being texture-mapped is far from the viewing plane. This aliasing is caused when the reduced pixel resolution provides insufficient sampling of texture images that have higher frequency components (e.g., fast transitioning color or intensity values). The interpolated (S,T) values may skip over large areas of the texture. A technique known as MIP-mapping is often performed to prevent aliasing by precomputing multiple, filtered copies of the texture at successively lower resolutions. For example, a texture image comprising a 256×256 texel array would be filtered and resampled to obtain further texel arrays (or maps) at 128×128, 64×64, 32×32, 16×16, 8×8, 4×4, and 2×2 resolutions. The cost of storing the additional texel arrays is an increase of approximately thirty percent in memory size. 
     The particular size of the texel array that is used during pixel rendering is chosen based on a computer parameter known as the “level of detail.” The level of detail represents the relative distance between the interpolated S and T values. Each texel array size represents an integer level of detail, and the computed level of detail values are real numbers. High quality texture mapping is obtained by performing bilinear interpolation in the texel array representing the integer level of detail immediately above and below the computed level of detail of each pixel. Next, a linear interpolation is performed between the integer levels of detail to obtain the texture value at the non-integer level of detail. This process is known as trilinear MIP-mapping. 
     Texture Map Storage 
     To facilitate texture mapping, a texture image may be stored in a dynamic random access memory (DRAM) device. The texel values of the texture image are accessed from the DRAM as needed to determine pixel values for a rendered image in the frame buffer. Unfortunately, DRAM devices are inefficient when performing data transfer operations (e.g., data reads) for individual data values. Peak efficiency is achieved when transferring multiple data values, especially data values that are in adjacent memory locations. For example, for a burst transfer of data in consecutive locations, a DRAM device may support a transfer rate of eight bytes per clock cycle. The same DRAM device may have a transfer rate of one byte per nine clock cycles for arbitrary single byte transfers. These performance characteristics are not well-suited to texture mapping. 
     In texture mapping operations, pixel values for a frame buffer are often determined in a particular scan order, such as by scanning in the direction of the X axis. However, texels associated with consecutive pixels are rarely in a predictable scan order with respect to texture space. For example, in the texture mapping process of FIGS  1 A- 1 C, a scan along the X axis in image space results in a scan pattern in the texture space that includes multiple passes from the left edge (T axis) of the texture image towards the upper right of the texture image. FIG. 3 illustrates the scan direction in texture space for the texture mapping of FIGS. 1A-1C. As shown, each scan arrow represents texel accesses that frequently traverse, or “skip”, rows, including large skips between the ending of one scan arrow and the beginning of the next scan arrow based on the boundaries defined by the primitive in image space. 
     For a linearly configured DRAM, for example, because the texels in a texture image are not typically scanned in a linear path along the S axis, consecutive pixels will access texels that are widely dispersed across memory. For a 1024×1024 texture image in which each texel is one byte wide, a traversal of one integer T coordinate may translate to a skip of 1024 bytes in DRAM. These memory skips are not easily predictable because the skips are dependent upon the size of the image, the width of a texel, the rotational angle between the S,T axes and the X,Y axes, etc. Texture mapping may also be nonlinear for irregular surfaces, further dispersing memory access operations. 
     FIG. 4 illustrates an example pixel scan line progressing through a portion of a texel array. The texel array shown encompasses the range [L, L+5] in the S direction and [M,M+4] in the T direction. The pixels that form the scan line comprise P N , P N+1 , P N+2 , P N+3 , P N+4 , P N+5  and P N+6 . P N  lies within the texel neighborhood formed by texels at (L,M+1), (L+1,M+1), (L,M+2) and (L+1,M+2). Pixel P N+1  has a texel neighborhood of texels at (L+1,M), (L+2,M), (L+1,M+1), and (L+2,M+1). Each of pixels P N+2 , P N+3 , P N+4 , P N+5  and P N+6  have a similar texel neighborhood. These texels may be used to determine the nearest neighbor for approximating the desired texel value. Also, as described above, interpolation may be performed on the texel neighborhood of each pixel. Assuming a linear memory in S, and memory access of a texel neighborhood in the order of (top-left, top-right, bottom-left, bottom-right), the memory transfers for the texels associated with pixels P N , P N+1 , P N+2 , P N+3 , P N+4 , P N+5  and P N+6  may occur as shown in the following table (where the texture image size is W(width)×H(height), and the base address “B” of the texel array is at (L,M)): 
     
       
         
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                   
                   
                 RAM LNR 
                 DISTANCE 
               
               
                   
                 PIXEL 
                 TEXEL 
                 ADDR 
                 (SKIP) 
               
               
                   
                   
               
             
             
               
                   
                 P N   
                 (L, M + 1) 
                 B + W 
                 — 
               
               
                   
                   
                 (L + 1, M + 1) 
                 B + W + 1 
                 1 
               
               
                   
                   
                 (L, M + 2) 
                 B + 2W 
                 W-1 
               
               
                   
                   
                 (L + 1, M + 2) 
                 B + 2W + 1 
                 1 
               
               
                   
                 P N+1   
                 (L + 1, M) 
                 B + 1 
                 −2W 
               
               
                   
                   
                 (L + 2, M) 
                 B + 2 
                 1 
               
               
                   
                   
                 (L + 1, M + 1) 
                 B + W + 1 
                 W-1 
               
               
                   
                   
                 (L + 2, M + 1) 
                 B + W + 2 
                 1 
               
               
                   
                 P N+2   
                 (L + 2, M) 
                 B + 2 
                 −W 
               
               
                   
                   
                 (L + 3, M) 
                 B + 3 
                 1 
               
               
                   
                   
                 (L + 2, M + 1) 
                 B + W + 2 
                 W-1 
               
               
                   
                   
                 (L + 3, M + 1) 
                 B + W + 3 
                 1 
               
               
                   
                 P N+3   
                 (L, M + 3) 
                 B + 3W 
                 2W-3 
               
               
                   
                   
                 (L + 1, M + 3) 
                 B + 3W + 1 
                 1 
               
               
                   
                   
                 (L, M + 4) 
                 B + 4W 
                 W-1 
               
               
                   
                   
                 (L + 1, M + 4) 
                 B + 4W + 1 
                 1 
               
               
                   
                 P N+4   
                 (L + 1, M + 2) 
                 B + 2W + 1 
                 −2W 
               
               
                   
                   
                 (L + 2, M + 2) 
                 B + 2W + 2 
                 1 
               
               
                   
                   
                 (L + 1, M + 3) 
                 B + 3W + 1 
                 W-1 
               
               
                   
                   
                 (L + 2, M + 3) 
                 B + 3W + 2 
                 1 
               
               
                   
                 P N+5   
                 (L + 2, M + 1) 
                 B + W + 2 
                 −2W 
               
               
                   
                   
                 (L + 3, M + 1) 
                 B + W + 3 
                 1 
               
               
                   
                   
                 (L + 2, M + 2) 
                 B + 2W + 2 
                 W-1 
               
               
                   
                   
                 (L + 3, M + 2) 
                 B + 2W + 3 
                 1 
               
               
                   
                 P N+6   
                 (L + 3, M + 1) 
                 B + W + 3 
                 −W 
               
               
                   
                   
                 (L + 4, M + 1) 
                 B + W + 4 
                 1 
               
               
                   
                   
                 (L + 3, M + 2) 
                 B + 2W + 3 
                 W-1 
               
               
                   
                   
                 (L + 4, M + 2) 
                 B + 2W + 4 
                 1 
               
               
                   
                   
               
             
          
         
       
     
     Associated with each of the pixels above (P N -P N+6 ) is a skip in the DRAM texel access of approximately the width of the texture image which is caused by the two-dimensional nature of the texel neighborhood. Even larger skips are introduced when the scan pattern crosses multiple integer coordinates in T for consecutive pixels. The speed of the texture mapping process may be significantly reduced by the performance of DRAM data transfers with frequent address skips of this nature. 
     Prior Art Buffer Memory 
     Prior art texture mapping schemes attempt to overcome the limitations of DRAM data transfer characteristics by using a smaller, faster buffer memory to hold data between DRAM transfers. Buffering consists of loading a block of contiguous data into buffer memory for use by the processor performing the texel processing. A new block of data is loaded from DRAM into the buffer when it is needed. 
     FIG. 5 illustrates buffering applied to a texture image. In FIG. 5, texture image  500  has dimensions W×H, and base address  502 . An N-byte buffer is used to hold N-byte buffered block  501  of texture image data having starting address M. Buffered block  501  is loaded as a linear block of texture image data from memory, or as a multidimensional tile of contiguous texture image data. 
     Buffering apparatus are illustrated in FIG.  6 . DRAM  600  is coupled to N-byte buffer  601  to receive address information  604 , and to transfer read data block  603  into the buffer memory. The data transferred from DRAM  600  comprises DRAM locations M through M+N, where M is supplied as read address  604 . The N-byte contiguous block of data in buffer  601  is available via bus  605  for texel processing component  602  to access the texture image data in buffer  601 . The texture image data is used to produce output  606 , such as rendered pixels for display. When the texture image data required by the texel processing component  602  is not located in buffer  601 , a new contiguous buffered block of texture image data is retrieved from DRAM  600  and placed in buffer  601 . 
     Rather than performing the transfer of data as a single block to the buffer, the data may be streamed through the buffer, for example, in a FIFO (first in, first out) arrangement. The streaming data has an accessibility lifetime in the buffer based on the time required to shift a data element through the buffer and out. This lifetime is directly related to the size of the buffer itself. 
     If the buffered block  501  is configured as a contiguous one-dimensional (or linear) block of data, the buffered data is strongly biased along the S axis direction. Therefore, for two-dimensional graphics applications such as texel processing, buffered block  501  in buffer  601  requires frequent transfers from DRAM  600  to track texels when scan patterns produced by a particular mapping have a strong T component that causes frequent skips. Any performance gain achieved by storing a contiguous memory block in buffer  601  is countered by the need to make frequent data transfers of different blocks from DRAM  600  to buffer  601 . Due to the contiguous nature of a buffer, a buffer needs to be very large to encompass large skips within the buffer, particularly for large images. 
     In the prior art, U.S. Pat. No. 5,548,709, issued to Hannah et al. on Aug. 20, 1996, discloses a semiconductor chip, referred to as TRAM (texture random access memory), that integrates texture memory, interpolation and resampling logic on the same substrate. Textures are input to the chip and stored in a main memory. The interpolator produces an output texel by interpolating from the textures stored in memory. 
     SUMMARY OF THE INVENTION 
     The invention provides a method of operating a cache memory so that operation is optimized. Instead of fetching data immediately upon a cache miss, the present invention continues with subsequent cache accesses. Decoupled from cache access, cache misses are fetched to cache. During operation, for each request in a sequence of data requests, it is determined if the requested data can be found in cache memory. If the data is not found in the cache, the next request in the sequence is processed without first retrieving the data pending from the earlier request. A miss list is generated for each of the requests in the sequence of requests whose data is not found in the cache. The data that is associated with the requests in the miss list is obtained from DRAM and used to satisfy the requests. Some cache lines may have one or more pending hits to data associated with the cache line. Those requests are kept in a pending hits list and processed in order as required. There may also be pending misses kept in a pending misses list where the list contains one or more pending misses to data associated with the cache line. A flag or indicator is set for a cache line when there are misses associated with the cache line. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1A illustrates a primitive in an X,Y image space. 
     FIG. 1B illustrates a texture image in an S,T texture space. 
     FIG. 1C illustrates a mapping of the texture image of FIG. 1B into the primitive of FIG.  1 A. 
     FIG. 2 is a diagram illustrating bilinear interpolation in texture space. 
     FIG. 3 illustrates the texture space scan pattern of the texture image of FIG. 1B when a scan is performed along the X axis in image space. 
     FIG. 4 is an example of a pixel scan line traversing a texel array in texture space. 
     FIG. 5 is a diagram illustrating buffering of a texture image. 
     FIG. 6 is a block diagram of a texture image buffering apparatus. 
     FIG. 7 is a diagram illustrating caching of a texture image in accordance with an embodiment of the invention. 
     FIGS. 8A-8D are diagrams of texel tiles in accordance with an embodiment of the invention. 
     FIG. 9 is a block diagram of a texture caching apparatus in accordance with an embodiment of the invention. 
     FIG. 10 is an example of a general purpose computer system in which an embodiment of the invention may be implemented. 
     FIG. 11 illustrates the tag information for a texel according to one embodiment of the invention. 
     FIG. 12A illustrates the tag information for a 16-bit texel according to one embodiment of the invention. 
     FIG. 12B illustrates the tag information for a 8-bit texel according to one embodiment of the invention. 
     FIG. 12C illustrates the tag information for a 4-bit texel according to one embodiment of the invention. 
     FIG. 13 demonstrates a method for utilizing cache according to one embodiment of the invention. 
     FIG. 14A illustrates non-interleaved cache lines with tag banks. 
     FIG. 14B illustrates tag banks with interleaved cache lines according to one embodiment of the invention. 
     FIG. 15 illustrates tiles and texel information and their relation to cache lines. 
     FIG. 16 is a two-dimensional diagram illustrating effects of cache index hashing when used with multiple tag banks. 
     FIG. 17 is a two-dimensional diagram illustrating tiles. 
     FIG. 18 is diagram illustrating a process for cache index hashing. 
     FIG. 19 is a flow diagram illustrating a process according to one embodiment of the invention. 
     FIG. 20 is a block diagram of an embodiment of the invention. 
     FIG. 21 is a flow diagram of the operation of the invention. 
     FIG. 22 is a block diagram of another embodiment of the invention. 
     FIG. 23 is a flow diagram of the operation of the embodiment of the invention of FIG.  22 . 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In the following description, numerous specific details are set forth in order to provide a more thorough understanding of the present invention. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well-known features have not been described in detail in order not to unnecessarily obscure the present invention. 
     The present invention is used in one embodiment in a caching scheme for accessing image data. A caching scheme used in conjunction with image data is described in connection with FIGS. 7-19. Embodiments of the invention for deferring the retrieval of data associated with cache misses are described in FIGS. 20-23 
     FIG. 7 illustrates the use of a tiled caching scheme within the framework of a two-dimensional texture image  500 . Texture image  500  has a size in tiles of W×H. Base address  502  of texture image  500  is the address location where the image data (i.e., texels) begins in DRAM. In the example of FIG. 7, seven tiles ( 0 - 6 ) of image data are stored in a texture cache. Tile  0  comprises a tile location at S and T coordinates (S 0 ,T 0 ) with respect to base address  502 . Tile  1 , tile  2 , tile  3 , tile  4 , tile  5  and tile  6  comprise tile locations (S 1 ,T 1 ), (S 2 ,T 2 ), (S 3 ,T 3 ), (S 4 ,T 4 ), (S 5 ,T 5 ) and (S 6 ,T 6 ), respectively. Each tile comprises a two-dimensional array of texels extending a first number of texels in the S direction and a second number of texels in the T direction. 
     The organization of cached tiles  0 - 6  in texture image  500  may be contiguous in an arbitrary two-dimensional arrangement, or the tiles may be dispersed throughout the texture image as needed for a particular scanning pattern. Tile regions of texture image  500  are not stored in the cache unless utilized in a particular texture mapping operation. More efficient use of fast data storage resources (i.e., cache memory) is thus provided than in buffering systems where, due to the large, contiguous nature of the buffer, portions of buffered data may never be utilized. 
     FIG. 8A illustrates a generalized tile for use in accordance with an embodiment of the invention. The tile comprises an array of texels of width A and height B. A more square arrangement, where A≈B, is preferred in order to optimize the two-dimensional aspect of the tile along each axis. Texture image  500  may be apportioned into a framework of tiles, any number and configuration of which may be stored in the texture cache, up to the cache limit. 
     Assuming a fixed cache line size, the sizes of A and/or B may vary based on the number of bits or bytes per texel. This is illustrated in FIGS. 8B,  8 C and  8 D, which show a tile for use with a cache having a fixed cache line, and thus fixed tile size, of thirty-two bytes. The width value A is modified to accommodate the various texel sizes in the illustrated embodiment. FIG. 8B assumes a texel size of two bytes per texel; FIG. 8C assumes one byte per texel; and FIG. 8D assumes 0.5 bytes, or four bits, per texel. 
     In FIG. 8B, the tile dimensions are optimally four by four texels, for a total of sixteen texels of two bytes each. Other arrays of sixteen texels may also be implemented in other embodiments, such as two by eight or eight by two. One by sixteen or sixteen by one are possible tile arrangements, as well, but do not provide the advantages of a two dimensional tile. 
     In FIG. 8C, the tile dimensions are eight by four texels, for a total of thirty-two texels of one byte each. Similar to FIG. 8B, other arrays of thirty-two texels may also be implemented in other embodiments. 
     In FIG. 8D, the tile dimensions are sixteen by four texels, for a total of sixty-four texels of four bits each. Other embodiments may implement a different array organization totaling sixty-four texels. However, because data is often accessed in byte-wise fashion, the width A of the tile array will typically have a minimum of two texels to form a complete byte. 
     An embodiment of texture caching apparatus is illustrated in FIG.  9 . The apparatus comprise a DRAM memory  900 , cache memory  901 , tag table  902 , cache manager  903 , and texel processing component  904 . Texture image data is transferred between DRAM  900  and cache  901  in the form of tiles the size of a single cache line (i.e., addressable cache location). Individual texels (or complete tiles in other embodiments) are read from cache  901  by texel processing component  904 . Cache manager  903  receives texel requests (e.g., texel addresses in S and T coordinates) from texel processing component  904 , and triggers the transfer of the appropriate texel (or tile) from cache  901 . Cache manager  903  also coordinates data transfers between DRAM  900  and cache  901  in accordance with a given cache replacement policy. Tag table  902  is used by cache manager  903  to track which tiles are located in which cache lines of cache  901 . 
     Texel processing component  904  is part of a graphics processing subsystem responsible for texture mapping. Texel processing component  904  is coupled to cache manager  903  via bus  909  to exchange requests for image data in the form of texels. For example, each request may include texel address information in S and T coordinates. Output  910 , in the form of rendered pixels, for example, is generated from texel processing component  904  to be placed in a frame buffer for display, or to be further processed by the graphics subsystem. 
     DRAM  900  is illustrated as a memory device containing a sequence of data words. For example, DRAM  900  may be configured to store and transmit texture image data in complete tiles, or portions thereof, as a single addressable DRAM word or a sequence of consecutive words. In other embodiments, DRAM  900  may be structured in multiple banks, with addressability in more than one dimension. Embodiments of the invention have application to any DRAM configuration. Further, embodiments of the invention are applicable to any type of memory. DRAM  900  may be, for example, the main memory of a computer system, a mass storage device, special purpose graphics memory, or any other type and configuration of memory in which texture data may be stored. 
     The arrangement of texture data in DRAM  900  may vary among different embodiments. Typically, the texture caching apparatus transforms S and T texture coordinates specified by texel processing component  904  into one or more appropriate DRAM addresses for the tile containing the specified texel. For S and T values in terms of tiles, the S and T values of a constituent texel may be individually processed in an integer division function (DIV) based on the row and column dimensions of a tile. For a tile configuration of A×B texels, the tile-based S and T coordinates in texture space for a given tile are: 
     S TILE =S TEXEL  DIV A; and 
     T TILE =T TEXEL  DIV B 
     For many cases, A and B are powers of two (e.g., 1, 2, 4, 8, 16, etc.), and the DIV function may be performed in hardware with binary shifts or hardwired selection of appropriate upper bits in S and T. From the tile-based S and T coordinates, the DRAM address (or addresses) of the tile is determined from the mapping of the tiles into DRAM  900 . 
     For example, in FIG. 9, texture image  500  is stored in DRAM  900  as a sequence of tiles in S, with traversals of one unit in the T direction comprising a skip of W (the width of the texture image) address locations, scaled by the number of DRAM words per tile. For FIG. 9, W and H represent the dimensions of the stored texture image in terms of tiles. For tile  0  having a tile location (S 0 ,T 0 ) in texture space (tile-based), the memory location in DRAM for the first texel is: 
     
       
           M   0 =BASE+k[S 0 +( T   0   * W )] 
       
     
     where BASE is the base address of the given texture image in DRAM  900 , and “k” is the number of DRAM words forming a single tile. To load a given cache line with tile  0 , DRAM addresses M 0  through M 0 +(k−1) are accessed and transmitted together as a tile to cache  901  to be stored as a cache line, such as shown by arrow  905  pointing to tile  0  at cache location  0 . For the case where k=1 (i.e., a single DRAM word stores a complete tile), the address of tile  0  is simply M 0 . Other mappings of tiles into DRAM (e.g., other than as a sequence in S) may be used in other embodiments. 
     Cache  901  is a fast memory having C addressable cache words (e.g.,  0  through C- 1 ), referred to as cache lines. Each cache line supports a tile of image data. The footprint of the cache (i.e., the total amount of data from the DRAM that may be stored in the cache) is therefore C×“tile size” in expanse, though the footprint may be dispersed across a texture image in “tile size” pieces. The ability to freely configure the tiles in the cache provides for much greater storage and re-use efficiency than that provided by a buffer that has the same sized footprint. 
     In a general caching scheme, any tile may be stored at any cache location, and the same tile may be stored in different cache locations at different points in time. As shown, locations  0 - 4  contain tiles  0 ,  1 ,  6 ,  4  and  2 , respectively, and location C- 1  contains tile  5 . Cache manager  903  determines how cache lines are written into and read from cache  901 , in accordance with a given caching scheme. A cache address is specified over bus  907  and a transfer is made between the specified cache line and either DRAM  900  or texel processing component  904  as appropriate. 
     For transfers of data from cache  901  to texel processing component  904  via data bus  908 , a complete tile may be transferred and the desired texel extracted by texel processing component  904 , or S and T address bits may be provided to cache manager  903  to resolve the correct texel from the selected tile via multiplexing performed on the cache port shared by texel processing component  904 . Cache  901  may be implemented in banks (e.g., each bank used to store a corresponding texel of each cache line) to simplify this multiplexing operation by extracting the addressed texel directly from its cache line at the port of the corresponding bank. 
     For a tile of dimensions A×B texels, given an embodiment in which tiles are internally organized as a sequence of texels in S, a tile in a cache line can be resolved into respective texels as follows. After locating the respective tile (e.g., tile  0  of location M 0 ) in cache  901 , the relative texel S and T coordinates of the desired texel are determined by performing an integer modulo (MOD) operation on the S and T texel coordinates: 
     S REL =S TEXEL  MOD A; and 
     T REL =T TEXEL  MOD B 
     For powers of two, those modulo operations may be performed by simply taking the lower bits of the original S and T texel coordinates. I.e., for A=4 and B=8, the relative coordinates comprise the lower two significant bits of the S coordinate and the lower three bits of the T coordinate. For the cache line arranged as a linear sequence of texels in S, the address of the desired texel within the cache line is: 
     
       
           M   TEXEL   =S   REL +( A*T   REL ) 
       
     
     For embodiments in which the cache is constructed of banks, those banks may be configured in a multi-dimensional manner to facilitate individual texel addressing directly from the relative texel coordinates. 
     To track which tiles are located in cache  901 , and at which locations, tag table  902  is utilized to store a tag for each tile in the cache. Each tag is associated with a particular location in the cache, and may be used to identify the tile currently stored therein. In some embodiments, the tag comprises the address of the stored tile (or one or more of its texels) in DRAM or in texture space (i.e., in S and T), or some portion thereof. When a cache request is received from texel processing component  904  in the form of an address transmitted via bus  909 , cache manager  903  determines the appropriate tag from the specified address and compares the determined tag with the tags stored in the tag table. 
     If there is no matching tag in tag table  902 , the request is termed a cache “miss,” meaning that the tile containing the requested texel must be loaded into cache  901  from DRAM  900 . Which existing cache line is to be overwritten by the desired tile is determined by cache manager  903  in accordance with a given replacement policy. Once the tile is loaded, tag table  902  is updated, and the texel or tile is transferred from cache  901  to texel processing component  904 . If there is a matching tag in tag table  902 , it is termed a cache “hit,” and the texel may be transferred from the tile associated with the matching tag. Tags are discussed in detail below. 
     Cache manager  903  may be used to perform addressing transformations, such as those described with respect to tile addressing in DRAM  900  and texel addressing in cache  901 , based on S and T coordinates. Any memory configuration details, such as banking, may be handled by such transformations within the cache manager. This allows texel processing component  904  to perform all texel operations with reference to texture space. 
     Cache Tags 
     The cache of the invention is not as large as the texture document. Additionally, the cache size limits the number of address bits that may be stored in the cache that determine which DRAM information is stored within the cache. Referring to FIG. 15, each box of FIG. 15 may be viewed as a tile or texel (e.g., tiles  1502 - 1514 ) contained within DRAM  1500 . The address of each tile differs by the most significant bits of the address. For example, DRAM  1500  may be divided into four sections (a quad) and each quad may be further divided. Each section may contain one or more tiles or texels. As the DRAM  1500  is divided into smaller sections, the divisions may be differentiated by the address bits. For example, the tiles or texels within section  00 xx differ from the tiles or texels in section  01 xx by the most significant bits ( 00  v.  01 ). An address identifies each texel with the most significant bits identifying the particular tile that the texel is located within. 
     Due to the above constraints, the tiles and texels stored in the cache may need to be removed and replaced with new tiles or texels. The manner in which the cache tiles are replaced is determined according to a cache replacement policy. 
     One prior art cache replacement policy consists of replacing the least recently used item in cache with the new item. Another prior art replacement policy determines which elements in the cache are the least frequently used and replaces the least frequently used cached items with the new item. 
     One embodiment of the present invention provides for direct mapped cache. With direct mapped cache, every S-T DRAM coordinate is mapped to a specific location in cache referred to as a cache line using some portion of the DRAM coordinates. Only one location in cache exists for a given texel or tile. But, since the cache is smaller than the DRAM, more than one texel or tile may map to the same location in cache. Accordingly, at one given time, one of several tiles or texels may be present in a specific cache line. Referring to FIG. 15, cache lines  1516 - 1522  each contain a tile from DRAM  1510 . Depending on which bits are utilized to determine the specific cache line, many tiles may fall within each cache line. For example, if the LSB bits are utilized as an index for each cache line, tiles  1502 ,  1506 ,  1512 , and  1514  may all map to cache line  1516  based on the LSB bits xxOO. Due to size constraints, the cache may not contain complete address information for each tile. Consequently, the address information for cache line  1516  may only contain the index bits  00 . To differentiate the tiles and determine which tile is in the cache, the upper bits may then be utilized. For example, tiles  1502 ,  1506 ,  1512 , and  1514  all have differing upper bits, namely,  00 ,  10 ,  01 , and  11 , respectively which may be stored separately from the cache to indicate which tile is currently in the cache. 
     A cache tag identifies the DRAM location that a tile or texel currently in cache originated from. Cache tags may be stored in a table of cache tags, an array, or other format, and are referred to as tagrams. Such a table of tagrams may be referred to as tag memory (the memory containing the tags). Specific portions of the tag identify specific aspects of the texel or tile in cache. The tag index portion of the tag is obtained from the tile/texel information and identifies the specific cache line that the tile/texel is mapped to. For example, in one embodiment of the invention, as described above, the tag index is comprised of the middle bits of the texel. In one embodiment, another portion of the tag identifies the tile that the texel is located in (e.g., the upper bits as described above). 
     Referring to FIG. 11, tag  1100  is comprised of the tag index  1104  and tag or tile information  1102 . Bits  0 - 5  of tag  1100  are the index of a texel and identify the cache line where tile  1102  is stored in the cache. Thus, tag tile  1102  identifies the tile currently stored in the cache. Index  1104  and tag tile  1102  may constitute the entire tag for a given texel. In such an embodiment, the lower bits of texel information may identify the specific texel in the cache line. However, in an embodiment where the tile consists of one texel only, then tile  1102  identifies the specific texel currently in cache. In the above embodiment, since the index is based on the middle bits of a texel, those texels with similar middle bits will map to the same cache location. 
     FIG. 13 demonstrates the utilization of cache according to one embodiment of the invention. The method begins at step  1300 . At step  1302 , the middle bits of the texel are utilized to calculate and obtain the index. At step  1304 , the tagram is examined and the index is located in the tagram (to identify whether the texel is currently in cache). At step  1306 , the upper bits of the texel are compared to the tag tile. At step  1308 , a determination is made regarding whether the upper texel bits match the tag tile. If the upper bits match, then the tile containing the texel is currently in cache, referred to as a cache hit. If the upper bits do not match, the tile containing the texel is not in cache, referred to as a cache miss. If a cache miss occurs, the tile is read from DRAM at step  1318 . At step  1320 , the tile is written in the cache. At step  1322 , the tag is updated to reflect the tile information currently in cache. 
     In an alternate embodiment in which cache write backs occur, if a cache miss occurs, the tile that is currently in the cache is examined to determine if any changes made to the tile have been updated in the DRAM (i.e., the cached tile is dirty) at step  1314 . If the changes have not been updated, the cache line containing the tile is written to DRAM (thereby updating the DRAM) at step  1316 . 
     If a cache hit is determined at step  1308 , the low bits of the texel are examined to locate the specific texel in the cache line at step  1310  (a cache line may contain a tile which contains one or more texels). At step  1312 , the texel in the cache line is read. The process is complete at step  1324 . 
     In the above example, the tag identifies whether a tile containing the texel is currently in cache at steps  1300 - 1308 . If the texel is not in the cache, it is read from DRAM, written to the cache, and the tag is updated at steps  1314 - 1322 . If the texel is in the cache, the relevant information is read directly from cache at steps  1310 - 1312 . 
     To exploit the 2D nature of graphics and texels, one embodiment of the invention utilizes the S-T coordinates as tag information. For example, referring to FIGS. 12A-12C, index  1104  is made up of a portion of the middle S bits and a portion of the middle T bits. FIG. 12A demonstrates a tagram when 16 bits are utilized to contain the relevant texel information. FIG. 12B demonstrates a tagram when 8 bits are utilized to contain the relevant texel information. FIG. 12C demonstrates a tagram when 4 bits are utilized to contain the relevant texel information. 
     In FIGS. 12A,  12 B, and  12 C, bits  3 - 5  of T and varying bits of S are utilized as the tag index  1104 . Further, the tile that contains the desired texel is identified in the tagram based on a portion of S bits and a portion of T bits. FIG. 12A demonstrates a tagram with bits  6 - 10  of S  1200  and bits  6 - 10  of T  1202  as the tag tile  1102 . Similarly, FIG. 12B demonstrates a tagram with bits  7 - 10  of S  1200  and bits  6 - 10  of T  1202  as the tag tile  1102 . FIG. 12C demonstrates a tagram with bits  8 - 10  of S  1200  and bits  6 - 10  of T  1202  as the tag tile  1102 . Thus, FIGS. 12A-12C illustrate the use of the S-T coordinates to access and locate items in the cache. 
     In one embodiment, multiple cache sets are utilized. With multiple cache sets, texels with the same index may be present in the cache simultaneously (in different cache sets). For example, texel A with an index of 011011 may be in cache set X and texel B with the same index of 011011 may be in cache set Y. When two cache sets are utilized, the cache is commonly referred to as two-way associative cache. Any number of sets may be utilized for the cache information. In one embodiment, the texels are interleaved across sets and banks (discussed below) or memory ports (e.g., a multiport RAM) within the cache lines. For example, every 2×2 texel may be interleaved across four sets and then interleaved across four banks within each set. 
     Additionally, a set associative cache may be utilized in which multiple tiles or texels are stored in the same cache line. In such a situation, the tag tile information will contain the relevant information for each tile stored in the cache line. 
     Tag Banks 
     It is desirable to access texel information and tag information more than one texel and tag at a time (per clock cycle). For example, when bilinear filtering, one pixel can access up to 4 (2×2) surrounding texels and therefore can touch up to 4 (2×2) cache lines (one cache line per texel) (and multiple tags (with one tag per cache line)) per clock cycle. Trilinear mipmapping of 4 (2×2) pixels is done by bilinear filtering 4 (2×2) pixels per clock cycle over two clock cycles. When trilinear filtering, the maximum distance between pixels in texture space is less than two which guarantees that a quad of pixels can still only touch up to 2×2 cache lines per clock cycle. It is desirable to check each of the 4 tags and 4 cache lines in one clock cycle. 
     To access multiple tags and cache lines in one clock cycle, one embodiment of the invention provides for the organization of the tagram into multiple sections (referred to as banks or ports) with the cache lines interleaved in two dimensions across the tagram banks to guarantee than any 4 (2×2) cache lines will not access the same tagram twice. Further, the cache lines may be organized in multiple banks that correspond to the tag banks. Alternatively, one bank can be utilized and the memory accesses can be superclocked (i.e., when multiple clock cycles are performed serially and appear as if the accesses are performed serially). 
     Referring to FIG. 14A, each box represents a cache line. Each cache line (which may be accessed using the tag index for each cache line) is linearly interleaved across tag banks identified by the numbers  0 - 3 . For example, as described above, when accessing one pixel, four (4) texels may be accessed for the purposes of bilinear and trilinear interpolation. Consequently, the  0 - 3  banks represent the four texels with the texel image coordinates interleaved across the cache banks to enable parallel cache line access. The texel image coordinates may be two dimensional, or three or more dimensional. 
     Neighboring texels may be utilized to render a pixel, and when mipmapping, texels must be located within a close proximity to optimize the resolution. The texels being accessed may be located within one tile. However, the texels may also be distributed across multiple tiles (with each tile stored in a separate cache line and related cache bank). For example, the relevant texels may lie in tiles  1400 - 1406 . Without interleaving the cache lines through tag banks in two dimensional space, the same tag banks (tag banks  1  and  2  for example) may store the relevant cache lines  1400 - 1406 . Consequently, the relevant information cannot be retrieved in one clock cycle. Similarly, if the cache banks contain closely related cache lines (e.g., cache lines for similar texture image coordinates), the cache lines containing related texels cannot be retrieved in one clock cycle. 
     As described, for each pixel, there is a multi-dimensional address pattern of texels in a neighborhood that may be used for filtering the pixel. Filtering may consist of a weighted sum of a multidimensional neighborhood of samples (i.e., texels) that are applied to the texel that corresponds to a specific pixel. The neighborhood may be multidimensional by utilizing texel coordinates and a level of detail in mipmapping, for example. To determine the neighborhood, a neighborhood operation (also referred to as a filter extent or file width) may be utilized which identifies texels that are located in close proximity (or within a predefined neighborhood of texels) of a pixel. The neighborhood operation may consist of an arithmetic or logical operation on the image sample values such as comparisons, minimums, and maximums. Further, because the neighborhood of texels are adjacent, contiguous or located in close proximity, the texels in the neighborhood can be accessed in parallel across cache memory banks and tag banks by interleaving. For example, when bilinear filtering is utilized, the four (4) texels at the odd and even texel address will be accessed which can be performed in parallel across cache memory banks (e.g., the neighboring pixels can fall in different cache lines with the location of the cache lines interleaved across cache memory banks) and tag memory banks. Thus, since a filter operates on a contiguous multidimensional region/neighborhood, for a neighborhood of a known size, the cache tags may be organized such that all texels of the multidimensional neighborhood can reference the tag memory simultaneously and all texels in cache memory and all texels from the neighborhood can be accessed simultaneously in cache memory (using different cache lines with different tags). 
     Referring to FIG. 14B, the cache lines are distributed in two dimensions over the tag banks. In FIG. 14B, if the relevant texels lie in tiles  1410 - 1416 , four different tag banks contain the relevant information. Consequently, the relevant texel information may be retrieved in one clock cycle. Similarly, the cache lines in the cache memory are interleaved across the cache banks and may be accessed in parallel in one clock cycle. Further, the cache line texture image coordinates may be two, or three or more dimensional. 
     If tag banks or tag sets and cache banks or cache sets are utilized, a portion of S bits and a portion of T bits specify the bank and/or set in cache that the texel information is stored in. Referring again to FIGS. 12A-12C, tagram information  1250  may be utilized to specify the tag bank that the texel is located in. In FIG. 12A, bit  2  of S and bit  2  of T is utilized to specify the bank. In FIG. 12B, bit  3  of S and bit  2  of T is utilized to specify the bank. Referring to FIG. 13, when banks are utilized, the cache lookup operation is substantially similar but for minor differences in steps  1302  and  1304 . At step  1302 , the middle bits are utilized to obtain the index line address and appropriate tag bank. At step  1304 , the index within that bank is located in the tagram. 
     In addition to specifying the bank where a texel is stored, when mipmapping, the level of detail (as discussed above) for the desired tile may be specified as part of the tag information. For example, level  1252  in FIGS. 12A-12C specifies the mipmap level of detail that contains the tile specified in the tag tile information  1102 . 
     Referring to FIG. 12A, when texel information is requested, bit  2  of S and bit  2  of T are examined to determine the appropriate tag bank to look in. After locating the appropriate tag bank, bits  3 - 5  of S and bits  3 - 5  of T are examined to determine the index in the appropriate tag bank. After locating the index in the tag table, bits  6 - 10  of S and  6 - 10  of T are utilized to determine if the tile containing the desired texel is currently in cache for the desired mipmap level. If the desired tile is in cache, the index provides the cache line and cache bank and bits  0 - 1  of S and  0 - 1  of T specify the location within the cache line where the desired texel information is located. Once located, the texel information may then be accessed. Such information may also be retrieved for multiple tiles in parallel as a result of the cache bank interleaving. If the tile containing the desired texel is not currently in cache, the information is read from DRAM. Bits  3 - 5  of S and bits  3 - 5  of T are then utilized to locate the appropriate cache line. 
     The bits specified in connection with FIG. 12A are utilized when the texel information is 16 bits long. FIGS. 12B and 12C specify the bits that are utilized when the texel information is 8 bits and 4 bits respectively. 
     In addition to performing cache memory accesses and tag memory accesses in parallel, one or more embodiments provide for multiple accesses to be performed sequentially. The different neighborhoods, different image levels, different images, and different image dimensions may be accessed sequentially with the results accumulated. For example, with mipmapping, trilinear interpolation, and multi-texturing, the neighborhood operation is performed in parallel to the texels, the results are stored, and the operation is performed again to something else (i.e., another level of detail), and then the results from the two processes are accumulated. Thus, the multi-dimensional aspect of the cache memory and tag memory may be accessed sequentially and accumulated while the individual accesses at each dimension (e.g., level of detail when mipmapping) are still performed in parallel. Thus, while some parallelism in the accesses is maintained, to perform all of the accesses for a given neighborhood, accesses may also be performed sequentially. 
     Pending Cache Access Requests 
     Multiple cache accesses may be requested faster than they can be processed. Thus, each cache access request may be monitored such that each request may be processed. Information regarding each pending cache access request is also useful to determine which pending request is for the same or different cache line (or bank, or set, etc.) as the cache access being currently performed. Consequently, a list of requested cache accesses (referred to as pending cache access requests) may be utilized. Due to the multidimensional aspect of the cache and the multidimensional aspect of the cache tags, the pending cache access requests may be sorted based on their relation to the various cache banks and tags. As a result, in one or more embodiments, the pending cache access request list may be in multiple banks that are interleaved by the two or more dimensional coordinates of the cache line that the pending request is waiting for. Once a cache bank is free (i.e., not being accessed by another cache request), any pending request for a cache line in that bank may be processed in the next clock cycle (in parallel with other cache requests). Further, comparisons between the pending requests and active requests may be performed in parallel and limited to the corresponding cache bank due to the interleaving of the pending request list. 
     Embodiment of General-Purpose Computer Environment 
     An embodiment of the invention can be implemented as computer hardware or a combination of computer software (or firmware) and hardware in a general purpose computer such as the embodiments of computer  1000  illustrated in FIGS. 10A and 10B. The embodiment of FIG. 10A includes a combined memory controller and graphics subsystem accessing a main memory, whereas the embodiment of FIG. 10B includes a graphics subsystem with graphics memory separate from the memory controller and main memory. 
     In FIG. 10A, keyboard  1010 , mouse  1011 , I/O unit  1019  and mass storage  1012  are coupled to a bidirectional I/O bus  1018 . The keyboard and mouse are for introducing user input to the computer system and communicating that user input to processor  1013 . Other suitable input devices may be used in addition to, or in place of, the mouse  1011  and keyboard  1010 . I/O (input/output) unit  1019  represents such I/O elements as a printer, A/V (audio/video) I/O, etc. Mass storage  1012  may include both fixed and removable media, such as magnetic, optical or magnetic optical storage systems or any other available mass storage technology. 
     Memory controller and graphics subsystem  1030  is coupled to I/O bus  1018 , video amplifier  1016 , processor  1013  (via processor bus  1027 ) and main memory  1015  (via main memory bus  1028 ). Memory controller and graphics subsystem  1030  provides an interface between processor  1013 , main memory  1015 , video amplifier  1016  and the components of I/O bus  1018 . An embodiment of the invention may be implemented as part of memory controller and graphics subsystem  1030 . The memory controller and graphics subsystem may provide 2-D (two-dimensional) and/or 3-D (three-dimensional) graphics processing capability for the computer system in the form of hardware and software. Memory controller and graphics subsystem  1030  can load graphical data, such as texture images and graphical object models, from main memory  1015  or mass storage  1012  to perform pixel rendering operations for display. The graphical output of memory controller and graphics subsystem  1030  is typically forwarded to a frame buffer for display via video amp  1016  and CRT  1017 . 
     Busses  1018 ,  1027  and  1028  may contain, for example, thirty-two address lines for addressing coupled components, and a 32-bit data bus for transferring data between and among the components. Alternatively, multiplexed data/address lines may be used instead of separate data and address lines. Bus widths other than 32-bits may also be used. 
     In one embodiment of the invention, processor  1013  is a microprocessor manufactured by Motorola, such as the 680X0 processor or a microprocessor manufactured by Intel, such as the 80X86, or Pentium processor, or a SPARC microprocessor from Sun Microsystems, Inc. However, any other suitable microprocessor or microcomputer may be utilized. Main memory  1015  comprises dynamic random access memory (DRAM), and may further comprise graphics memory for use in graphical processing, though standard DRAM may be used to perform graphical processing as well. Video amplifier  1016  is used to drive the cathode ray tube (CRT) raster monitor  1017 . Video amplifier  1016  is well known in the art and may be implemented by any suitable apparatus. This circuitry converts pixel data stored in a frame buffer in memory controller and graphics subsystem  1030  to a raster signal suitable for use by monitor  1017 . Monitor  1017  is a type of monitor suitable for displaying graphic images. Alternatively, memory controller and graphics subsystem  1030  may be used to drive a flat panel or liquid crystal display (LCD), or any other suitable data presentation device. 
     Computer  1000  may also include a communication interface  1020  coupled to bus  1018 . Communication interface  1020  provides a two-way data communication coupling via a network link  1021  to a local network  1022 . For example, if communication interface  1020  is an integrated services digital network (ISDN) card or a modem, communication interface  1020  provides a data communication connection to the corresponding type of telephone line, which comprises part of network link  1021 . If communication interface  1020  is a local area network (LAN) card, communication interface  1020  provides a data communication connection via network link  1021  to a compatible LAN. Communication interface  1020  could also be a cable modem or wireless interface. In any such implementation, communication interface  1020  sends and receives electrical, electromagnetic or optical signals which carry digital data streams representing various types of information. 
     Network link  1021  typically provides data communication through one or more networks to other data devices. For example, network link  1021  may provide a connection through local network  1022  to local server computer  1023  or to data equipment operated by an Internet Service Provider (ISP)  1024 . ISP  1024  in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet”  1025 . Local network  1022  and Internet  1025  both use electrical, electromagnetic or optical signals which carry digital data streams. The signals through the various networks and the signals on network link  1021  and through communication interface  1020 , which carry the digital data to and from computer  1000 , are exemplary forms of carrier waves transporting the information. 
     Computer  1000  can send messages and receive data, including program code, through the network(s), network link  1021 , and communication interface  1020 . In the Internet example, remote server computer  1026  might transmit a request for an application program or data through Internet  1025 , ISP  1024 , local network  1022  and communication interface  1020 . 
     The received data may be stored in mass storage  1012 , or other non-volatile storage for later use. In this manner, computer  1000  may obtain data in the form of a carrier wave. In accordance with an embodiment of the invention, such data may include texture image data or graphical object data as described herein. 
     FIG. 10B illustrates a further embodiment of a general purpose computer wherein the graphics subsystem is implemented as a functional block separate from the memory controller, and wherein the graphics subsystem is configured with separate graphics memory  1014  accessible over a graphics memory bus  1029 . As with memory controller and graphics subsystem  1030  of FIG. 10A, memory controller  1030  A of FIG. 10B is coupled to processor  1013 , main memory  1015  and I/O bus  1018 . However, in FIG. 10B, memory controller  1030  A interfaces with graphics subsystem  1030  B via a graphics bus  1032  for handling of graphical output and certain graphical processing functions (e.g., pixel rendering). Graphical subsystem  1030 B is equipped with graphics memory  1014  for storing texture image data or other graphical processing data. As with FIG. 10A, graphical output of graphics subsystem  1030 B may be stored in a frame buffer (not shown) and output for display via video amplifier  1016  and monitor  1017 . 
     The computer systems described above are for purposes of example only. An embodiment of the invention may be implemented in any type of computer system or graphics processing environment. 
     Cache Index Hashing 
     The performance of a cache is directly related to the likelihood of the cache containing the desired information. If the desired information is available from the cache when requested, a “cache hit” results, and the desired information can be quickly retrieved from the cache. However, if the desired information is not available from the cache when requested, a “cache miss” results. In the event of a “cache miss,” the requested information must be loaded into the cache. Such loading is typically a relatively slow process since the information is usually first retrieved from a slower memory element. Another disadvantage of a “cache miss” is that, because of the finite size of the cache, the information loaded into cache displaces other information previously held in cache. 
     Various attempts have been made to locate information in cache that is least likely to be accessed in the future. However, such attempts generally increase the complexity of the cache structure. A direct-mapped cache avoids unnecessary complexity, but may be susceptible to sequences of cache misses based on patterns of information being accessed. With many types of cache information, such as executable program code, cache accesses are generally fairly random and unpredictable. However, for digital imaging information, cache information is often accessed according to specific patterns. For example, when rendering digital images, information may represent polygons of certain shapes. Since the patterns in which such polygons are represented in memory may bear some relationship to the patterns in which information is mapped into a direct-mapped cache, the sequences in which memory is accessed when rendering such polygons may strongly affect cache performance. 
     For example, if cache mapping is organized according to a rectilinear pattern and if storage of information representing rectilinear polygons results in patterns in memory having some rectilinear structure, the rectilinear cache mapping pattern and the rectilinear structure of the information in memory may result in interference between these rectilinear patterns. This interference may be referred to as “cache aliasing.” Cache aliasing can result in increased frequency of cache misses, especially if multiple memory locations being accessed map into the same location in cache. 
     When multiple memory locations being accessed map into the same location in cache, the effective size of the cache is reduced since cache accesses tend to be concentrated on a relatively few locations in cache, while a relatively large number of the cache locations are not accessed. Since cache memory is generally a valuable limited resource for increasing performance, inefficient use of cache memory can significantly degrade performance. 
     To minimize detrimental interaction between patterns of memory accesses and patterns of cache mapping, one embodiment of the invention organizes cache memory such that information-stored in cache is indexed and the index is hashed. Hashing involves a process that generates a relatively small amount of data based on a larger amount of data. It is possible that two different larger amounts of data will result in an identical smaller amount of data after it they have been hashed. (Note that as a result, the hashing process does not necessarily result in a one-to-one correspondence between the input data and the output data of the hashing process.) 
     The hashing process is preferably optimized to be very sensitive to small changes in the input data. Thus, even very similar sets of input data will preferably not result in the same or even similar output data. Memory accesses of the sort performed when rendering graphical images may involve numerous accesses to relatively similar memory locations Therefore, hashing of the index values that determine where the information from the memory locations will be stored while that information is in cache decreases the likelihood of similar memory locations being stored at the same cache location. Consequently, cache efficiency and performance is improved. 
     Referring again to FIGS. 12A,  12 B, and  12 C, one embodiment of the invention performs a logical operation on a certain portion of one coordinate value with respect to a certain portion of another coordinate value. For example, a logical operation may be performed between certain bits of the s coordinate value, such as s component  1204  of index  1104  or s component  1204  of index  1104  combined with the s component of tagram value  1250 , and certain bits of the t coordinate value, such as t component  1202  of tag  1102 . Likewise, a logical operation may be performed between certain bits of the t coordinate value, such as t component  1206  of index  1104  or t component  1206  of index  1104  combined with the t component of tagram value  1250 , and certain bits of the s coordinate value, such as s component  1200  of tag  1102 . An example of a logical operation that may be performed is an exclusive OR, or XOR, operation, although any suitable logical operation may be used. 
     The results of these logical operations may be combined (by concatenation, for example) to form a hashed index value. The hashed index value is used to map the memory location in main memory referred to by the s and t coordinates into a memory location in cache memory. Since the hashed index value is influenced by several different bits of varying place values in the s and t coordinates, even s and t coordinates that differ by only a few bits will be mapped to different locations in cache memory. Since rendering of images often involves regions that span contiguous ranges of s and t coordinates, cache index hashing increases cache performance for image rendering. 
     FIG. 16 is a two-dimensional diagram illustrating effects of cache index hashing when used with multiple tag banks. Four tag banks, A, B, C, and D, are illustrated in FIG. 16, although any number of tag banks may be used. Tile  1601  is located at coordinates (s,t). Tile  1601  is divided into four areas, with each of the four areas stored in a different tag bank. Area  1605  is the upper left area and is stored in tag bank A. Area  1606  is the upper right area and is stored in tag bank B. Area  1607  is the lower left area and is stored in tag bank C. Area  1608  is the lower right area and is stored in tag bank D. 
     Tile  1602  is located at coordinates (s+1,t). Tile  1602  is also divided into four areas, with each area stored in a different tag bank. Area  1609  is the upper left area and is stored in tag bank C. Area  1610  is the upper right area and is stored in tag bank D. Area  1611  is the lower left area and is stored in tag bank A. Area  1612  is the lower right area and is stored in tag bank B. Thus, as the s coordinate is increased by one, the tag banks in which the areas are stored are rotated by one in the t direction. Consequently, a line or part of a polygon that passes through the upper half of tiles  1601  and  1602  will pass through areas  1605 ,  1606 ,  1609 , and  1610 , which are stored in tag banks A, B, C, and D, respectively. Since these areas are stored in different tag banks and information can be retrieved from the different tag banks simultaneously, processing of the information from areas  1605 ,  1606 ,  1609 , and  1610  can be performed in parallel and performance is greatly increased. 
     Tile  1603  is located at coordinates (s,t+1). Tile  1603  is also divided into four areas, with each area stored in a different tag bank. Area  1613  is the upper left area and is stored in tag bank B. Area  1614  is the upper right area and is stored in tag bank A. Area  1615  is the lower left area and is stored in tag bank D. Area  1616  is the lower right area and is stored in tag bank C. Thus, as the t coordinate is increased by one, the tag banks in which the areas are stored are rotated by one in the s direction. Consequently, a line or part of a polygon that passes through the left half of tiles  1601  and  1602  will pass through areas  1605 ,  1607 ,  1613 , and  1615 , which are stored in tag banks A, B, C, and D, respectively. Since these areas are stored in different tag banks and information can be retrieved from the different tag banks simultaneously, processing of the information from areas  1605 ,  1607 ,  1613 , and  1615  can be performed in parallel and performance is greatly increased. 
     Tile  1604  is located at coordinates (s+1,t+1). Tile  1604  is also divided into four areas, with each area stored in a different tag bank. Area  1617  is the upper left area and is stored in tag bank D. Area  1618  is the upper right area and is stored in tag bank C. Area  1619  is the lower left area and is stored in tag bank B. Area  1620  is the lower right area and is stored in tag bank A. Thus, as the s coordinate is increased by one, the tag banks in which the areas are stored is rotated by one in the t direction. Likewise, as the t coordinate is increased by one, the tag banks in which the areas are stored are rotated by one in the s direction. Therefore, the tag banks in which the areas of tile  1604  are stored are rotated by one in both the s and t directions. Consequently, a line or part of a polygon that passes through the upper or lower half of tiles  1603  and  1604  or through the left or right half of tiles  1602  and  1604  will pass through areas which are stored in different tag banks. Thus, processing of the information from any of these contiguous areas can be performed in parallel and performance is greatly increased. 
     FIG. 17 is a two-dimensional diagram illustrating tiles  1701  and  1702 . Each of tiles  1701  and  1702  are divided into  16  areas arranged in a 4 by 4 pattern. Tile  1701  has coordinates (s,t). Tile  1702  has coordinates (s+1,t). Since the s coordinate of tile  1702  is increased by one relative to the s coordinate of tile  1701  while the t coordinates remain the same, the tag banks in which the areas are stored are rotated by one in the t direction. Consequently, a line or part of a polygon that passes horizontally through tiles  1701  and  1702  will pass through areas which are stored in different tag banks. Since these areas are stored in different tag banks and information can be retrieved from the different tag banks simultaneously, processing of the information from these areas can be performed in parallel and performance is greatly increased. 
     FIG. 18 is diagram illustrating a process for cache index hashing. An address  101  for the s coordinate is split into first and second portions  1803  (s 1 ) and  1804  (s 2 ) respectively. Similarly, t address  1802  is split into first portion  1805  (t 1 ) and second portion  1806  (t 2 ) respectively. The division of coordinates can be based on some number of most or least significant bits or any other suitable scheme. In the embodiment of FIG. 18, s 1  and t 2  are provided to logical operator  1807 , and t 1  and s 2  are provided to logical operator  1808 . In one embodiment, the logical operators perform XOR operations. The output of logical operators  1807  and  1808  are provided to concatenator  1809  to produce the hashed cache index  1810 . 
     FIG. 19 is a flow diagram illustrating a process according to one embodiment of the invention. At step  1901  the s address is split into s 1  and s 2  components. At step  1902  the t address is split into t 1  and t 2  components. At step  1903  the s 1  and t 2  components are XORed and at step  1904  the s 2  and to components are XORed. The results of the XOR operations are concatenated at step  1905  to yield a hashed cache index value. 
     Decoupled Retrieval of Cache Miss Data 
     The use of a caching scheme can greatly improve the efficiency and speed of operation of a memory system. However, some of that efficiency and speed may be lost when data is not found in the cache memory. When requested data is not found in cache, it must be accessed from DRAM. In a typical system. reading data from DRAM can take up to 200 nanoseconds. Compare this to reading data from cache which can be done on the order of 5 nanoseconds. 
     The present invention improves system performance by decoupling cache hits and misses. In effect, there is a pipelining of misses while hits continue to be processed. Referring to FIG. 20, for a requested texel, its tag is checked, and if it is available, it is placed in the texel queue  2002 . If it is a texel miss, then the request is placed in the miss queue  2001 . The depth of the texel queue should be enough so that cache misses can have a chance to be processed before the requested (but missed) texel is needed. While requests continue to be processed, items in the miss queue are read in from DRAM and are available by the time the texel would come out of the texel queue  2002  and be processed. 
     A flow diagram of the operation of an embodiment of the present invention is illustrated in FIG.  21 . At step  2101  a request for data is processed. At step  2102  it is determined if the requested data is in the cache or not. If the data is in the cache, the data is placed in the texel queue at step  2103 . If the data is not in the cache, a miss list is updated at step  2105 . The miss list tracks the requests that could not be satisfied with data in the cache. At step  2106  the miss data is retrieved from the DRAM and placed in the texel queue at step  2103 . After step  2103 , the next request is retrieved from the pending list at step  2104  and the system returns to step  2101  to process the request. The loop of steps  2105  and  2106  is decoupled from the path for data that is in the cache. Therefore processing continues while relatively slow DRAM access is performed. 
     It is desired to have a large number of pending misses in the miss queue so that a large number of texels could be processed at the same time. The invention effectively pipelines cache misses to improve efficiency and mask context switching costs. 
     Hazards 
     The operation of the deferred retrieval of cache miss data includes a number of situations where care must be taken in the order of operation. These situations are referred to here as “hazards”. These hazards include the following: 
     1. Duplicate Miss. 
     2. Miss on Pending Hit. 
     3. Miss on Pending Miss. 
     1. Duplicate Miss 
     A duplicate miss occurs when there is a request for a cache line for which there has already been a miss and the data has not yet been returned. When the first request for the cache line is made and the data is not available, a miss entry for that cache line is entered into the miss queue. If later there is another request for that cache line, there should not be another entry for that cache line. This is because the cache line should not be read twice from DRAM, but only once, with the single read able to satisfy the multiple requests to that cache line. So there must be some indication so that the texel should not be processed but that there should not be a DRAM read for that cache line either. 
     2. Miss on Pending Hit 
     A miss on a pending hit occurs when there is a request for the same index but for a different texel. Assume a texel is a hit and a later texel misses at the same index but is for a different texel. It would not be desired to read a cache line in from the DRAM at that index until the hit has completed. Otherwise the cache line of the miss will overwrite the cache line of the hit and lead to incorrect data when the hit is processed. 
     3. Miss on Pending Miss 
     A miss on a pending miss occurs then there is a miss for the same index that has a pending miss but for a different texel. If the DRAM reads were in order, there would not be a problem. But it is desirable for the DRAM reads to be out of order to maximize efficiency of the DRAM reads. But this creates the potential for a miss on a pending miss. 
     Solution for Hazards 
     One embodiment for providing a solution to the problems raised by hazards is illustrated in FIG. 22. A pending line queue  2003  is provided to keep track of the status of requests at indexes and lines. Each line in the queue has a number of possible states, for example hit, miss, or nothing yet. So when a request comes in for processing, an entry in the pending line queue is created and status is indicated. 
     Consider where a request is processed and there is a miss. The pending line queue is updated with an entry for that line and status of miss. Sometime later there is a request for the same line. This is a duplicate miss condition. The line is processed and is found to be a miss. The pending line queue is checked for a match and the existing miss status for that line is found. Because there is already an entry in the pending line queue for that line, the miss queue is not updated. This prevents the same line from being retrieved from DRAM twice, improving efficiency. 
     Consider the second hazard, a miss on a pending hit. A request is processed and the data is in cache. The pending line queue is updated with an entry showing a hit. Later a request comes in for the same index but for a different texel. This indicates a miss. The pending line queue is checked and the pending hit at that index is found. The second request must wait until the pending hit has been satisfied before the new data can be read in from DRAM. 
     For the third hazard, a request is processed and it is a cache miss. The pending line queue is updated with an entry for that index showing a miss. A later request comes in and is for the same index but a different texel. The pending miss at that line would not satisfy this new miss, so the second request must be processed. But the processing must wait until the first miss has been satisfied. 
     After a request has been handled, the pending line queue is updated to clear any pending operations for that line. At that time, any waiting requests can go forward as appropriate. 
     The operation of the system with the pending line queue is illustrated in FIG.  23 . At step  2301  a request for data is processed. At step  2303  the pending line queue (PLQ) is examined to see if there is already an entry for the cache line of interest. If there is no entry (step  2304 ) there is a check at step  2302  to see if the data is in cache. If so, the texel of interest is placed in the texel queue at step  2315 . If the data is not in cache, the miss list is updated at step  2313  and the PLQ is updated to show that there is now a pending miss for that cache line. The data is then retrieved from DRAM at step  2314 . After the texel is placed in the texel queue at step  2315  (either from a cache hit or from a DRAM access), the PLQ is updated (decremented) at step  2316  and the next request is obtained at step  2317 . 
     If, after checking the PLQ at step  2303 , there is a duplicate hit (step  2305 ) or a duplicate miss (step  2306 ), the same steps are taken. The PLQ is updated (incremented) at step  2309  to show another pending hit or miss and the system proceeds to step  2317 . There is no need to retrieve the data since it will be available from the prior duplicate hit or miss. 
     The remaining two cases, miss on pending hit (step  2307 ) or miss on pending miss (step  2308 ) also prompt similar action. The PLQ is updated at step  2310  to show that there are multiple requests to the cache line of interest and the system enters a wait and check state at steps  2311  and  2312 . If the pending action (hit or miss) is not cleared, the request remains on hold. If the pending hit or miss is cleared the system proceeds to step  2313  where the miss list is updated and DRAM access proceeds at step  2314 . 
     The PLQ contains status bits to indicate multiple waiters for hazard situations. It is common that a number of duplicate hits or duplicate misses attempt to access the same cache line. The duplicate status bits comprise an access counter, which is incremented for each duplicate access to the line, and decremented for each duplicate processing of the line. Since a line can be only one of a pending miss with duplicate misses, or a pending hit with duplicate hits, only one counter of. duplicate accesses is needed, in conjunction with the status bit for a pending miss. In this way, the hazard of miss data overwriting pending duplicate hit processing or pending duplicate miss processing can be avoided. Since counters are of finite size in a practical implementation, when the maximum duplicate hit or miss count is reached, further texture processing is inhibited until the counter is decremented by the completion of processing of one of the texture accesses to the line. 
     Thus, a method and apparatus for deferring retrieval of cache miss data is described in conjunction with one or more specific embodiments. The invention is defined by the claims and their full scope of equivalents.