Distributed cache

• US 20030093623A1
• Filed: 11/15/2001
• Published: 05/15/2003
• Est. Priority Date: 11/15/2001
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Crook, Neal A., Wootton, Alan
• Granted Patent: US 6,754,772 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0855 Overlapped cache accessing, e.g. pipeline G06F12/0846 takes precedence
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/005 General purpose rendering architectures

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.

Claims

1. A method of caching comprising:

receiving input data and assigning a cache tag to said input data;

storing in a first data storage area a cache tag of received input data if no entry in said first data storage area is identical to said assigned cache tag;

storing in a second data storage area data produced by a processor which is based on said input data and corresponding to said assigned cache tag if no entry in said first data storage area is identical to said assigned cache tag; and

transmitting data selectively from said second data storage area if said first data storage area contains an entry identical to said assigned cache tag or from said processor if no entry in said first data storage area is identical to said assigned cache tag.

2. A method as in claim 1, further comprising a data producer storing said assigned cache tag in said first data storage area;

said data producer, when a data consumer is to retrieve data processed by said processor from said second storage area, determining the address in said second data storage area that data corresponding to said cache tag is stored based on the address in said first data storage area where said cache tag is stored and transmitting to a data consumer said corresponding address in said second data storage area where data previously produced by said processor is stored, a hit/miss indicator to indicate to said data consumer whether said data processed by said processor should be retrieved from said second data storage area and an allocation indicator to indicate whether said corresponding address is an address in said second data storage area to write data processed by said processor to.

3. A method as in claim 2, further comprising said consumer selectively retrieving consumption data from said second data storage area or said processor based on said hit/miss indicator.

4. A method as in claim 3, further comprising said consumer selectively writing the data retrieved from said processor into said second data storage area at said corresponding address based on said allocation indicator.

5. A method as in claim 2, further comprising said data producer replacing the least recently used entry in said first data storage area with the assigned cache tag if said first data storage area is full and no identical entry to said assigned cache tag is found in said first data storage area.

6. A method as in claim 2, further comprising said data producer replacing the most recently used entry in said first data storage area with the assigned cache tag if said data storage area is fill and no identical entry to said assigned cache tag is found in said first data storage area.

7. A method as in claim 2, further comprising said data producer replacing the oldest entry in said first data storage area with the assigned cache tag if said first data storage area is full and no identical entry to said assigned cache tag is found in said first data storage area.

8. A method as in claim 2, further comprising said data producer using a deterministic algorithm to select an entry in said first data storage area and replacing said entry with the assigned cache tag if said first data storage area is full and no identical entry to said assigned cache tag is found in said first data storage area.

9. A method as in claim 1, further comprising said consumer retrieving data from said processor and storing said data in said second data storage area;

said data producer determining the address in said second data storage area where said data is stored based on the address in said first data storage area where said cache tag is stored and transmitting to said data consumer the address in said second data storage area where said data is stored when said assigned cache tag is identical to a cache tag stored in said first data storage area; and

said consumer retrieving said data produced by said processor from said second data storage area using said address.

10. A method as in claim 9, further comprising said data producer replacing the least recently used entry in said first data storage area with the assigned cache tag if said first data storage area is full and no identical entry to said assigned cache tag is found in said first data storage area.

11. A method as in claim 9, further comprising said data producer replacing the most recently used entry in said first data storage area with the assigned cache tag if said first data storage area is full and no identical entry to said assigned cache tag is found in said first data storage area.

12. A method as in claim 9, further comprising said data producer replacing the oldest entry in said first data storage area with the assigned cache tag if said first data storage area is full and no identical entry to said assigned cache tag is found in said first data storage area.

13. A method as in claim 9, further comprising said data producer using a deterministic algorithm to select an entry in said first data storage area and replacing said entry with the assigned cache tag if said first data storage area is full and no identical entry to said assigned cache tag is found in said first data storage area.

14. A method as in claim 2, further comprising said data producer producing a derived unit of data from said input data, and said processor uses said derived unit of data to produce said produced data.

15. A method as in claim 2, further comprising said data producer storing said corresponding address, said hit/miss indicator and said allocation indicator in a third data storage area;

said data producer storing in a fourth data storage area data generated by said data producer corresponding to said input data if no matching entry was found in said first data storage area;

said processor retrieving from said fourth data storage area said data generated by said data producer;

said processor storing in a fifth data storage area data produced by said processor;

said data consumer retrieving data from said third data storage area; and

said data consumer retrieving said data produced by said processor from said second data storage area if said hit/miss indicator indicates that a match was found in said first data storage area or from said fifth data storage area if a match was found in said first data storage area.

16. A method as in claim 15, wherein said third data storage area, said fourth data storage area and said firth data storage area operate as first-in-first-out queues of finite size;

and

said data producer stalling if at attempt is made to write to said third or fourth data storage area, and said third or fourth storage area are full; and

said data processor stalling if an attempt is made to write to said fifth data storage area and said fifth data storage area is full; and

said data processor stalling if an attempt is made to read from said fourth data storage area and said fourth data storage area is empty; and

said data consumer stalling if an attempt is made to read from said third or said fifth data storage area and said third or fifth data storage area is empty.

17. A method as in claim 1, wherein each of said cache tags has an associated valid bit.

18. A method as in claim 13, further comprising said data producer clearing said first data storage area by erasing all of said associated valid bits.

19. A method as in claim 17, wherein assigning a cache tag in said first data storage area additionally includes setting the valid bit associated with said cache tag and;

said data producer converts a hit indication into a miss indication if the hit indication is associated with a cache tag for which said associated valid bit is erased.

20. A method as in claim 7, further comprising said data producer maintaining a first pointer associated with the most-recently-stored entry in said first data storage device and a second pointer associated with the oldest entry in said first data storage device.

21. A method as in claim 20, further comprising said data producer clearing said first data storage area by setting said first pointer equal to said second pointer.

22. A method as in claim 20, wherein assigning a cache tag in said first data storage area additionally includes advancing said first pointer and;

said data producer converting a hit indication into a miss indication if the hit indication is associated with a cache tag which does not lie within the region between said first pointer and said second pointer.

23. A method as in claim 12, further comprising said data producer maintaining a first pointer associated with the most-recently-stored entry in said first data storage device and a second pointer associated with the oldest entry in said first data storage device.

24. A method as in claim 23, further comprising said data producer clearing said first data storage area by setting said first pointer equal to said second pointer.

25. A method as in claim 23, wherein assigning a cache tag in said first data storage area additionally includes advancing said first pointer and;

said data producer converting a hit indication into a miss indication if the hit indication is associated with a cache tag which does not lie within the region between said first pointer and said second pointer.

26. A method as in claim 1, wherein said second data storage area is divided into a cache region, processed data region and a spare region by pointers;

and

wherein cached data is stored in said cache region, data produced by said processor that has not been retrieved by said data consumer is stored in said processed data region and said spare region is empty.

27. A method as in claim 26, further comprising said data consumer advancing the pointer separating said cache region from said processed region into the processed region when said data consumer retrieves data from said processed region;

said processor advancing the pointer separating said processed region from said spare region into said spare region when said data processor stores data in said processed region; and

said data consumer advancing said pointer separating said cache region and said processed region into said processed region and said pointer separating said spare region and said cache region into said cache region when the storage space in said cache region equals a threshold and said data consumer retrieves data from said processed region.

28. A method as in claim 26, further comprising said data producer clearing said first data storage area by setting a pointer associated with the most recently stored entry in said first data storage device equal to a pointer associated with the oldest entry in said first data storage area.

29. A system for caching data comprising:

a producer, which produces a derived unit of data from an incoming unit of data;

a processor, which transforms said derived unit of data into a corresponding processed unit of data and sends said processed unit of data to a consumer;

a consumer, which uses said processed units of data;

a cache tag storage device coupled to said producer; and

a cache data storage device coupled to said processor and said consumer;

wherein said data producer assigns a cache tag to said incoming unit of data and compares said assigned cache tag to each entry in said cache tag storage;

if said assigned cache tag does not match an entry in said cache tag storage, said data producer sends a derived unit of data corresponding to said incoming unit of data to said processor, selects an entry in said cache tag storage, writes said cache tag to said selected entry in said cache tag storage, sends the corresponding address in said cache data storage device, a hit/miss indicator and an allocation indicator to said consumer; and

if said assigned cache tag does match an entry in said cache tag storage, said data producer determines what address in said cache data storage device corresponds to the address in said cache tag storage device where said matching cache tag is stored and sends said corresponding address and a hit/miss indicator to said data consumer.

30. The system as in claim 29, further comprising said processor generating a processed data unit from said derived data unit and sending said processed data unit to said consumer.

31. The system as in claim 29, further comprising said consumer reading said processed data unit from said processor and writing said processed unit of data to a received cache data storage address when said assigned cache tag does not match an entry in said cache tag storage.

32. The system as in claim 29, further comprising said consumer reading said processed data unit from a received cache data storage address when said assigned cache tag matches a unit of data in said cache tag storage.

33. A system as in claim 29, further comprising said data producer replacing the least recently used entry in said cache tag storage with the assigned cache tag if said cache tag storage is full and no entry identical to said assigned cache tag is found in said cache tag storage.

34. A system as in claim 29, further comprising said data producer replacing the most recently used entry in said cache tag storage with the assigned cache tag if said cache tag storage is full and no entry identical to said assigned cache tag is found in said cache tag storage.

35. A system as in claim 29, further comprising said data producer replacing the oldest entry in said cache tag storage with the assigned cache tag if said cache tag storage is full and no entry identical to said assigned cache tag is found in said cache tag storage.

36. A method as in claim 29, further comprising said data producer using a deterministic algorithm to select an entry in said cache tag storage and replacing said entry with the assigned cache tag if said cache tag storage is full and no entry identical to said assigned cache tag is found in said cache tag storage.

37. A system as in claim 29, further comprising a data storage area coupled to said data producer and said processor;

wherein when said data producer sends said derived unit of data, said derived unit of data is stored in said data storage area and said processor retrieves said derived unit of data from said data storage area.

38. A system as in claim 29, further comprising a data storage area coupled to said producer and said data consumer;

wherein when said data producer sends an address in said cache data storage to retrieve data from or write data to, said hit/miss indicator and said allocation indicator, said address in said cache data storage to retrieve data from or write data to, said hit/miss indicator and said allocation indicator are stored in said data storage device and said data consumer retrieves said address in said cache data storage to retrieve data from or write data to, said hit/miss indicator and said allocation indicator from said data storage device.

39. A system as in claim 29, further comprising a data storage area coupled to said processor and said data consumer;

wherein when said processor sends said processed unit of data, said processed unit of data is stored in said data storage area and said data consumer retrieves said processed unit of data from said data storage area.

40. A system as in claim 29, wherein each of said cache tags stored in said cache tag storage device has an associated valid bit.

41. A system as in claim 40, further comprising said data producer clearing said cache tag storage device by erasing all of said associated valid bits.

42. A system for caching data comprising:

a producer, which produces a derived unit of data from an incoming unit of data;

a processor, which transforms said derived unit of data into a corresponding processed unit of data;

a consumer, which uses said processed units of data;

a cache tag storage device coupled to said producer;

a first data storage device coupled to said producer and said consumer;

a second data storage device coupled to said producer and said processor; and

a cache data storage device coupled to said processor and said consumer;

wherein said data producer assigns a cache tag to said incoming unit of data and compares said assigned cache tag to each entry in said cache tag storage;

if said assigned cache tag does not match an entry in said cache tag storage, said data producer stores a unit of data corresponding to said incoming unit of data in said second data storage device, stores said assigned cache tag in said cache tag storage, determines the corresponding address in said cache data storage and stores said corresponding address in said first data storage device, and if said assigned cache tag does match an entry in said cache tag storage, said data producer stores in said first data storage device the address in said cache data storage containing processed data corresponding to said matched entry in said cache tag storage.

43. The system as in claim 42, wherein said cache data storage area is divided into a cache region, processed data region and a spare region by pointers.

44. The system as in claim 43, further comprising said processor storing said processed data in said processed data region and advancing said pointer between said processed data region and said spare region.

45. The system as in claim 44 further comprising said processor stalling on a write to said cache data storage device if the size of said spare region is zero.

46. The system as in claim 43, further comprising said data consumer retrieving said processed data from the address in said cache data storage device specified in said first data storage device;

and

said consumer advancing said pointer separating said cache region from said processed region into said processed region if said specified address is in said processed region and advancing said pointer separating said spare region from said cache region into said cache region if said cache region exceeds a predetermined maximum size.

47. The system as in claim 46, further comprising said pointers being controlled such that said cache storage device behaves as a circular buffer, said control involving:

advancing each pointer by a fixed value;

setting the value of the pointer to zero if the value of the pointer exceeds the size of said cache storage device.

48. The system as in claim 46, further comprising said consumer stalling on a read from said cache data storage device if said processed region is of zero size.

49. A system as in claim 43, further comprising said data producer replacing the oldest entry in said cache tag storage with the assigned cache tag if said cache tag storage is fill and no entry identical to said assigned cache tag is found in said cache tag storage.

50. A system as in claim 43, wherein said cache tag storage device further comprises:

a first pointer associated with the most recently stored entry in said cache tag storage device; and

a second pointer associated with the oldest entry in said cache tag storage device.

51. A system as in claim 50, further comprising said data producer clearing said cache tag storage device by setting said first pointer equal to said second pointer .

52. A method as in claim 50, wherein assigning a cache tag in said cache tag storage device additionally includes advancing said first pointer and;

said producer converting a hit indication into a miss indication if the hit indication is associated with a cache tag which does not lie within the region between said first pointer and said second pointer.