Abstract:
A system and method for distributed cache. Cache tag storage and cache data storage are maintained in separate pipeline stages. Cache tag storage is operated by a data producer. Cache data storage is operated by a data consumer. Cache hits and misses are determined by the data producer prior to any operations being performed by the processor. In the event of a cache miss, produced data is sent to the processor to be processed. In the event of a cache hit, the cache address of the corresponding previously processed data is sent to the data consumer so that the corresponding processed data unit can be retrieved from cache data storage.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates generally to caching processed data, and, more particularly, to a method and apparatus for distributing the functions of cache to different stages in an execution pipeline such that the stages can operate independently while saving processing time and preventing data hazards.  
         BACKGROUND OF THE INVENTION  
         [0002]    The function of a 3D graphics processing pipeline for a computer is to represent a 3-dimensional scene on a 2-dimensional computer display screen. In order to change view-point within the 3-dimensional scene, the graphics processing pipeline must redraw the scene according to the new view-point; this can affect perspective, lighting, reflections, the obscuring or revealing of objects and so forth. This requires a large amount of calculation.  
           [0003]    Consider the polygon shown in FIG. 1 a . The symbols a, b, c, and d represent the vertices of the polygon. The characteristics of each vertex include such information as its position in 3-dimensional space (x,y,z Cartesian co-ordinates), its color, its transparency, and its texture.  
           [0004]    When drawing a scene, the 3D graphics processor works with flat surfaces. The most complex surface that is guaranteed to be flat is a triangle. Therefore, part of the process of displaying the polygon abcd involves tessellating it into triangles. This process is shown in FIG. 1 b . The polygon abcd is now represented by the two triangles abc and adc. For more complex shapes, tessellation can lead to the introduction of new vertices, as shown in the tessellation of FIG. 1 c.    
           [0005]    The task of drawing the polygon is now replaced by the task of drawing the two triangles abc and adc. One way of representing the task to the 3D graphics pipeline is to produce a sequence of triplets representing the vertices to be drawn: abcadc. Each identifier a, b, c, and d must uniquely define a particular vertex within a scene, but a vertex can be shared with several triangles. In addition, the identifier allows the characteristics of the vertex (the position, color, transparency, etc.) to be retrieved from storage elsewhere in the system.  
           [0006]    Part of the functions performed by a 3D-graphics processor are shown in FIG. 2. The sequence of triplets is passed to data producer  20 . Producer  20  is responsible for translating a vertex identifier “a” into the vertex characteristics “A”. “a” represents a relatively small data item (for example, an 8-bit value) while “A” represents a number of relatively large data items (for example, 16, 32-bit values). The translation process is costly in terms of time and occupied system resources; for example, it might require a number of memory accesses and data conversion operations.  
           [0007]    The vertex characteristics “A” are processed by a processor and the processed vertex “A″” is passed to the consumer (the next stage in the pipeline). The processing performed by the processor is costly in terms of time.  
           [0008]    The vertices “a” and “c” are each processed twice for polygon abcd—once for triangle abc and once for triangle acd. The result of processing a given vertex is identical, irrespective of the triangle it is being processed for. It wastes resources to translate the vertex identifier and process the vertex multiple times, so performance would be improved by maintaining a cache of transformed vertices.  
           [0009]    The rate at which producer  20 , processor  21  and consumer  22  handle data is different and may vary on a triangle-by-triangle or vertex-by-vertex basis. With the system shown in FIG. 2, the slowest unit determines the rate at any time, and faster units are stalled. This is an inefficient use of resources.  
           [0010]    One way to more efficiently utilize the resources of a 3D-graphics pipeline is by using the cache as shown in FIG. 3. Producer  30  translates a vertex identifier “a” and writes the translated vertex data “A” to data FIFO  31 . Data FIFO  31  is a first in first out queue. Data is sent from producer  30  to data FIFO  31  where processor  32  can access it when ready. When producer  30  translates a vertex faster than processor  32  processes a vertex, multiple data units can be stored in data FIFO  31 . Similarly, when processor  32  begins to processes data units at a faster rate than producer  30  translates vertices, processor  32 , rather than stalling immediately, continues to read translated vertices from data FIFO  31  until it is empty.  
           [0011]    Processor  32  maintains a cache tag storage  36  with tags containing the minimum amount of information A′, B′, C′, D′ required to uniquely identify a data unit incoming to processor  32 , i.e. data A, B, C, D. The minimum amount of information required to uniquely identify a data unit that is stored in cache tag storage  36  can be the data unit itself, a shortened form of the data unit, or an identifier derived from the data unit. For each element A′, B′, C′, D′ of tag storage, there is a corresponding element of processed data A″, B″, C″, D″ stored in cache data storage  37 . Thus, cache data storage  37  contains processed data A″, B″, C″, D″ corresponding to input data A, B, C, D previously processed by processor  32 . The tags A′, B′, C′, D′ must be stored as well as the data A″, B″, C″, D″, so that the tags can be compared to the incoming data units before they are processed so the processor  32  can determine if there is cached data A″, B″, C″, D″ corresponding to incoming data A, B, C, D. When processor  32  removes a data unit from data FIFO  31 , it checks to see whether the data unit has a corresponding tag A′, B′, C′, D′ currently in cache tag storage  36 . If there is no corresponding tag in cache data storage  36 , that is, processor  32  gets a cache “miss,” processor  32  stores a tag for the incoming data unit from FIFO  31  in cache tag storage  36  by using a currently unused storage location or reallocating a location that currently holds an old tag in cache tag storage  36 . Processor  32  also processes the incoming data unit and stores the newly processed data unit as cache data in the corresponding location in cache data storage  37 . The processed data is also passed through multiplexor  33  under control of processor  32  to a FIFO  34  for processed data and from there to a data consumer  35 . If processor  32  finds a cache tag in tag storage  36 , that is, it gets a cache “hit,” then processor  32  operates multiplexor  33  and cache data storage  37  so that the cache data, corresponding to the cache tag for which there was a “hit,” is passed through FIFO  34  to consumer  35 . Consumer  35  can then take each processed data unit from data FIFO  34  in the correct order. For a 3D graphics processing pipeline, processor  32  might transform vertex data “A” according to the point of view for which the scene is to be rendered and according to the way in which the scene is lit to produce processed data A″.  
           [0012]    There are, however, still some problems with the method discussed above. While a cache “hit” saves the latency associated with processor  32  having to reprocess previously processed data, it does not save the time taken by producer  30  to generate the stream ABCD from incoming data stream abcd or the time taken by processor  32  to check for cache hits and misses. In addition, the values A′B′C′D′ are likely to be larger than abcd requiring greater storage capacity in cache tag storage  36 .  
           [0013]    Thus, there exists a desire and need for a system and method for more efficiently performing cache functions.  
         BRIEF SUMMARY OF THE INVENTION  
         [0014]    The present invention mitigates the problems associated with the prior art and provides a unique method and system of distributed cache.  
           [0015]    In accordance with an exemplary embodiment of the present invention, a cache tag storage is provided which is maintained by a producer which sends data to the processor. A cache data storage is also provided which holds data output from a processor. A producer determines cache hits and misses without performing any translations on the data, and passes cache hit information through a control path to the consumer without any involvement from the processor. A cache miss causes the producer to fetch and translate data and pass that data to the processor for processing. The producer implements a cache replacement algorithm and manages the cache tag storage in accordance with the algorithm.  
           [0016]    The consumer uses information from the control path to allow it to read data from the output of the processor and the cache storage in the correct data order. The consumer also manages the cache data storage, in accordance with a cache replacement algorithm compatible with that used by the producer, by writing certain values that it has read from the output of the processor into the cache storage. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0017]    The above and other features and advantages of the invention will be more readily understood from the following detailed description of the invention which is provided in connection with the accompanying drawings.  
         [0018]    [0018]FIGS. 1 a - 1   c  are an illustration of the tessellation of a few shapes  
         [0019]    [0019]FIG. 2 is a block diagram of a conventional graphics pipeline;  
         [0020]    [0020]FIG. 3 is a block diagram of a conventional simple cache in a graphics pipeline;  
         [0021]    [0021]FIG. 4 is a block diagram of a first exemplary embodiment of a distributed cache in accordance with the present invention;  
         [0022]    [0022]FIG. 5 is a block diagram of second exemplary embodiment of a distributed cache in accordance with the present invention; and  
         [0023]    [0023]FIG. 6 a  and FIG. 6 b  are block diagrams of the memory allocation scheme for a combined processed data FIFO and cache data storage. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0024]    In the following detailed description, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to make and use the invention, and it is to be understood that structural changes may be made and equivalent structures substituted for those shown without departing from the spirit and scope of the present invention.  
         [0025]    In accordance with a first exemplary embodiment of the present invention, a processor system can distribute the functions of a cache to increase system performance by eliminating re-fetching and re-processing of data. FIG. 4 illustrates the flow of data for a distributed cache in accordance with the first exemplary embodiment of the invention. The two cache storage elements, cache tag storage  45  and cache data storage  48 , are controlled separately. Cache tag storage  45  is controlled by producer  40  while cache data storage  48  is controlled by consumer  44 . A data path through identification FIFO  46  passes cache control information from producer  40  to consumer  44 . Data FIFO  41 , identification FIFO  46  and processed data FIFO  43  are all data storage elements that are operated as first in first out queues.  
         [0026]    Incoming data units a, b, c, a, d, are sent to producer  40 . When producer  40  receives an incoming data unit, e.g. “a”, producer  40  examines cache tag storage  45  and determines whether data “a,” or a derived data tag corresponding to data “a,” is stored in cache tag storage  45  and will produce a cache “hit” or cache “miss.” A cache hit means that the end result of processing the incoming data unit by processor  42  is already stored in cache data storage  48  and processor  42  does not have to reprocess the incoming data unit, while a cache miss means that the end result of processing the incoming data unit is not stored in cache data storage  48  and processor  42  must process the incoming data unit.  
         [0027]    If an incoming data unit, e.g. “a,” produces a cache “miss” when producer  40  examines cache tag storage  45 , producer  40  uses a cache allocation and replacement algorithm to determine whether to allocate space for “a” in cache data storage  48 . The simplest algorithm is to always allocate an entry on a cache miss, and always to replace the oldest data entry. However, any of the other algorithms for cache allocation and replacement that are well known in the art, such as, for example, replacing the least recently used data entry or the most recently used data entry may be used. If space is allocated for “a” in cache tag storage  45 , producer  40  updates cache tag storage  45  to show that “a” is now in the cache. The allocation of space for a new entry in the cache may require the deletion of some other entry in the cache, which takes place in accordance with the cache allocation and replacement algorithm.  
         [0028]    If an incoming data unit, e.g. “a,” produces a cache “miss” when producer  40  examines cache tag storage  45 , producer  40  then generates data “A” from data “a” which is then sent to data FIFO  41 . When “A” becomes the oldest data unit in data FIFO  41 , processor  42  will read “A”. Processor  42  will then process data “A” into data “A″”. Once processor  42  completes transforming “A” into “A″”, processor  42  sends “A″” to processed data FIFO  43 .  
         [0029]    For each incoming data unit, e.g. “a,” producer  40  sends a corresponding data unit “a′” to identification FIFO  46 . The value of “a′” is determined by the outcome of the examination of cache tag storage  45  and the cache allocation and replacement algorithm in use, as follows:  
         [0030]    If producer  40  determined that “a” produced a cache “hit,” the value of “a′” indicates that processed data “A″” corresponding to “a” is in cache data storage  48  and furthermore, it indicates the location within cache data storage  48  where “A″” is stored.  
         [0031]    If producer  40  determined that “a” produced a cache “miss” and no storage is to be allocated, the value of “a′” indicates that the processed data “A″” corresponding to “a” must be read from the processed data FIFO  43 .  
         [0032]    If producer  40  determined that “a” produced a cache “miss” and that storage is to be allocated, the value of “a′” indicates that the processed data “A″” corresponding to “a” must be read from the processed data FIFO  43 , and that the data read must be written into the cache data storage  48  and furthermore, it indicates the location within cache data storage  28  where “A″” is to be written.  
         [0033]    Consumer  44  reads the oldest data unit (e.g. “a′”) from id FIFO  46 . If “a′” indicates a cache “miss” where space has not been allocated in cache data storage  48 , consumer  44  sends a signal to multiplexor (“MUX”)  47  to select processed data FIFO  43 . Consumer  44  then reads the oldest data unit “A″” from processed data FIFO  43  which corresponds to “a”. If “a′” indicates a cache “miss” where space has been allocated in cache data storage  48 , consumer  44  sends a signal to MUX  47  to select processed data FIFO  43 . Consumer  44  then reads the oldest data unit “A″” from processed data FIFO  23  which corresponds to “a”, and, preferably simultaneously, writes “A″” to cache data storage  48  at the address specified in “a′”. If “a′” indicates a cache “hit,” consumer  44  sends a signal to MUX  47  to select cache data storage  48 . Consumer  44  then reads “A″” from the address in cache data storage  48  specified in “a′”.  
         [0034]    Since producer  40 , processor  42  and consumer  44  all work at different rates, it is possible for any of the three FIFOs  41 ,  43 , or  46  to become empty or full. If producer  40 , processor  42 , or consumer  44  wishes to read from a FIFO that is empty or write to a FIFO that is full, it must stall (wait) until the fill/empty condition has changed.  
         [0035]    Thus, for processed data “A″” which is present in cache data storage  48 , corresponding to data “a” arriving at producer  40 , producer  40  need not translate the vertex identifier “a” into the vertex characteristics “A”, and processor  42  need not process data “A” from producer  40  to produce the processed data “A″.” By avoiding re-processing data that is in the cache data storage  48 , more processing power is available to handle data that is not. Moreover, data read from cache data storage  48  as a result of a cache “hit” is available to consumer  44  with a lower latency than if it had to be processed by processor  42 .  
         [0036]    The present embodiment can be further improved by adding a valid bit to each entry in cache tag storage  45 . Producer  40  would determine if an entry is active by its valid bit. This would allow producer  40  to effectively clear the cache by setting all of the valid bits to null.  
         [0037]    [0037]FIG. 5 illustrates a second exemplary embodiment of a distributed cache system in accordance with the invention. In this embodiment, processed data FIFO  43  is combined with cache data storage  48  in the form of a circular buffer. The resulting processed data FIFO/cache data storage  50  performs the functions of both.  
         [0038]    While the system described in FIG. 4 allows cache data storage  48  and processed data FIFO  43  to each be implemented in an efficient way, there are other considerations that might make combining cache data storage  48  and processed data FIFO  43  desirable. There is a fixed overhead for each memory device used (i.e. power rings and address decoder logic) which is reduced by having fewer memory devices. However, this merged system can only be implemented efficiently when the cache use a FIFO replacement algorithm, so that the addition of a new entry to the cache causes the displacement of the oldest entry currently in the cache.  
         [0039]    Processed data FIFO/Cache data storage  50 , as represented in FIGS. 6 a  and  6   b , has three operating pointers—SpareStart  60 , ProcessedStart  61 , and CacheStart  62 , which delimit the Spare, Processed, and Cache regions of the data storage. This contrasts with the implementation of a normal FIFO, which has two operating pointers (a Filling pointer and an Emptying pointer which delimit the Spare and Used regions of a FIFO). When processed data FIFO/Cache data storage  50  is initialized CacheStart  62  points to the address of the first storage location in processed data FIFO/Cache data storage  50 , ProcessedStart  61  points to a storage location leaving the Cache region large enough to hold a pre-determined number of processed data units corresponding to the number of cache tags that can be stored in cache tag storage  45 , and SpareStart  60  is equal to ProcessedStart  61 .  
         [0040]    The processed data FIFO/Cache data storage  50  can have additional regions. The key feature is that it contains a Cache region, which moves, and some other regions, and that comparisons of pointers within processed data FIFO/Cache data storage  50  prevent the Cache region from being overwritten in order to avoid a read-before-write hazard.  
         [0041]    In the embodiment depicted in FIG. 5, producer  40  and processor  42  behave in the same way as described for the embodiment depicted in FIG. 4.  
         [0042]    Each time that Processor  42  generates a new processed data unit, it writes the processed data unit into the processed data FIFO/Cache data storage  50  storage locations immediately to the left of the location pointed to by SpareStart  60 , and then advances SpareStart  60 . The processed data FIFO/Cache data storage  50  is a circular buffer so incrementing a pointer beyond the final location (i.e. the location farthest to the left) in processed data FIFO/Cache data storage  50  causes it to wrap around to the start (i.e. the location farthest to the right), as can be seen in FIG. 6 b . If SpareStart  60  equals CacheStart  62 , the Spare region has shrunk to zero size, and the Processed region has grown to its maximum size. In these circumstances, processor  40  must stall to avoid overwriting the Cache region.  
         [0043]    Consumer  44  processes entries from identification FIFO  46  in the same manner as described above with reference to FIG. 4. Each time it detects a cache “hit,” it retrieves the data from the cache region of processed data FIFO/Cache data storage  50 . When consumer  44  detects a cache “miss,” the required data must be the oldest unit in the processed region (e.g. the data starting at the address designated by ProcessedStart  61 ). If ProcessedStart  61  is equal to SpareStart  60 , the Processed region has shrunk to zero size and consumer  44  must stall until processor  42  has generated the next piece of data. Otherwise, the round-robin allocation policy dictates that the oldest entry in the cache must be discarded and replaced by the entry at the start of the processed region. This is accomplished by advancing CacheStart  62  and ProcessedStart  61 . The Processed region shrinks in size, the Cache region remains the same size and the Spare region grows in size. The discarded entry from the cache region becomes part of the Spare region.  
         [0044]    Although Producer  40  must determine “hit”/“miss” information , it is not necessary for the identification FIFO to contain “hit”/“miss” information. Consumer  44  can determine whether an entry is in the Cache region (and is therefore a “hit”) by comparing the address of the entry with the values of CacheStart  62  and ProcessedStart  61  pointers.  
         [0045]    The processed data FIFO/cache data storage  50  implements a circular buffer. If the data buses and processed data FIFO/cache data storage  50  width match the data unit size, a data unit will fit in a single processed data FIFO/cache data storage  50  location. Increments to CacheStart  62 , ProcessedStart  61 , and SpareStart  60  pointers will be by  1 . If the data buses and processed data FIFO/cache data storage  50  width are smaller than the data unit size, so that a data unit will require n successive locations within processed data FIFO/cache data storage  50 , increments to the pointers will be by n. The value of n need not be constant. However, if the value of n is changed, the cache must be invalidated so that pointers  60 ,  61 ,  62  can be re-initialized correctly.  
         [0046]    Algorithms (1) and (2) show two ways to increment the pointers that control the combined processed data FIFO/cache data storage  50 . Both of these algorithms are easy to implement in hardware.  
         [0047]    Algorithm 1:  
         pointer=(pointer+ n )modulo (size of processed data FIFO/cache data storage  50 )  
         [0048]    Algorithm 2:  
         if(pointer+ n )&gt;(size of processed data FIFO/cache data storage  50 ) then pointer=0  
         [0049]    else  
         pointer=pointer+ n    
         [0050]    Algorithm (2) leaves some processed data FIFO/cache data storage  50  locations unused when the size of processed data FIFO/cache data storage  50  is not an integer multiple of the data unit size. The advantage of algorithm (2), however, is that it makes it easier to detect the stall condition on SpareStart  60 &gt;=CacheStart  62 . Using algorithm (1), this comparison has to take into account the possibility that SpareStart  60  has wrapped around the end of the buffer. Using algorithm (2), the stall condition can be simplified to SpareStart  60 =CacheStart  62 , which does not require the detection of wrap-around and can therefore be implemented more efficiently.  
         [0051]    The present invention allows a processor to cache processed data without performing the caching functions itself The apparent speed of the system is increased because the processor does not determine when there is a cache hit or miss or store or retrieve the cached data. A producer performs the functions of determining whether there is a cache hit or miss while a consumer retrieves the cached data in the event of a cache hit.  
         [0052]    Generally, each cache tag in cache tag storage  45  has an associated “valid” bit. The “valid” bit indicates that the particular location in the cache contains a valid cache tag. If it is necessary to flush the cache, all of the “valid” bits can be cleared. Once the “valid” bits are cleared, producer  40  will begin writing to cache tag storage  45  and allocating space in cache data storage  48  as though they are empty. Any data in transit at the time (for example, in id FIFO  46 , data FIFO  41 , or processed data FIFO  43 ) will still be processed correctly because the data in cache data storage  48  will not be affected until every entry in id FIFO  46  that was in transit when the cache was flushed has been processed.  
         [0053]    Another method of flushing the cache uses pointers (that are controlled by Producer  40 ) to point to the first and last cache tags that have been allocated. Since cache tags are allocated in order, the cache can be flushed by setting the first cache tag pointer to the same value as the second cache tag pointer. As with the method of flushing the cache described above, any data in transit at the time the pointers are reset will be processed correctly.  
         [0054]    Arbitrary delays can be introduced on any of the data paths without affecting the correct operation of the system. Therefore, different parts of the system can operate in independent clock domains and clock synchronization can be performed across the data paths.  
         [0055]    While the invention has been described with reference to exemplary embodiments various additions, deletions, substitutions, or other modifications may be made without departing from the spirit or scope of the invention. Accordingly, the invention is not to be considered as limited by the foregoing description, but is only limited by the scope of the appended claims.