METHOD AND SYSTEM FOR MAXIMUM RESIDENCY REPLACEMENT OF CACHE MEMORY

• US 20070271417A1
• Filed: 09/12/2006
• Published: 11/22/2007
• Est. Priority Date: 05/17/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Ahmed, Muhammad
• Granted Patent: US 7,584,326 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0859 with reload from main memory
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Techniques for use in CDMA-based products and services, including replacing cache memory allocation so as to maximize residency of a plurality of set ways following a tag miss allocation. Herein, steps and instructions provide for forming a first-in, first-out (FIFO) cache way listing of victim ways for the cache memory, wherein the depth of the FIFO cache way listing approximately equals the number of ways in the cache memory. The method and system place a victim way on the FIFO cache way listing only in the event that a tag miss results in a tag miss allocation, the victim way is placed at the tail of the FIFO cache way listing after any previously selected victim way. Use of a victim way on the FIFO cache way listing is prevented in the event of an incomplete prior allocation of the victim way by, for example, stalling a reuse request until such initial allocation of the victim way completes or replaying a reuse request until such initial allocation of the victim way completes.

Claims

1. A method for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss, comprising the steps of:

selecting a victim way as the cache way that is to be replaced according to the position of said cache way on a FIFO cache way listing of cache ways for use in the operation of a digital signal processor;

placing at the end of said FIFO cache way listing subsequent cache tag misses to said cache memory reusing a victim way on a next cache tag miss;

preventing reuse of a victim way until initial allocation of said victim way completes avoiding incoherency between the cache tag and said cache memory;

preventing reuse of a victim way until initial allocation of said victim way completes by stalling response to a reuse request until such initial allocation of said victim way completes;

preventing reuse of a victim way until initial allocation of said victim way completes by replaying a reuse request until such initial allocation of said victim way completes.

2. The method of claim 1, wherein said selecting step further comprises the step of selecting a victim way as the cache way that is to be replaced by placing said victim way on the tail of a FIFO cache way listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache memory.

3. The method of claim 1, further comprising the step of skipping said victim way and selecting a different victim way in the event of detecting a reuse hazard associated with the use of said victim way.

4. The method for claim 3, further comprising the steps of:

performing a tag look up for obtaining a replacement victim way, and, in the event of no hit being detected with said replacement victim way, determining that a reuse hazard does not exist, and,

in the event of no reuse hazard existing with said replacement victim way, using said replacement victim way for replacing one of said plurality of set ways.

5. The method of claim 1, further comprising the step of replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss in association with the execution of digital signal processor data unit instructions.

6. The method of claim 5, in the event of a victim way reuse hazard, further comprising the steps of:

comparing a current/incoming primary miss victim way to other ways in said FIFO cache way listing;

comparing the set address of the incoming primary miss against other set addresses; and

in response to said comparing steps, replaying the current/incoming thread until a victim way arises that is free from a reuse hazard.

7. The method of claim 1, further comprising the step of replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss in association with the execution of digital signal processor instruction unit instructions.

8. The method of claim 7, in the event of a victim way reuse hazard, further comprising the steps of:

comparing a current/incoming primary miss victim way to other ways in said FIFO cache way listing;

comparing the set address of the incoming primary miss against other set addresses; and

in response to said comparing steps, replaying the current/incoming thread until a victim way arises that is free from a reuse hazard.

9. The method of claim 1, further comprising the step of adding the most recently used victim way to the tail of said FIFO cache way listing.

10. The method of claim 1, further comprising the step of replacing said victim way in a multi-threaded digital signal processor.

11. The method of claim 1, further comprising the step of performing said replacement steps without requiring use of a storage bit for recording used victim ways.

12. The method for claim 1, further comprising the step of only incrementing said FIFO cache way listing in the event of a cache way miss.

13. The method of claim 1, further comprising the step of performing back-to-back multi-thread accesses in said replacement FIFO cache way listing without replaying said listing.

14. A cache way replacement circuit for operation in association with a digital signal processor, said cache way replacement circuit for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss and comprising:

victim way selection circuitry for selecting a victim way as the cache way that is to be replaced according to the position of said cache way on a FIFO cache way listing of cache ways for use in the operation of a digital signal processor;

FIFO cache way listing populating circuitry for placing at the end of said FIFO cache way listing subsequent cache tag misses to said cache memory reusing a victim way on a next cache tag miss;

cache way reuse hazard detection circuitry for preventing reuse of a victim way until initial allocation of said victim way completes avoiding incoherency between the cache tag and said cache memory, said cache way reuse hazard detection circuitry further for preventing reuse of a victim way until initial allocation of said victim way completes by stalling response to a reuse request until such initial allocation of said victim way completes and preventing reuse of a victim way until initial allocation of said victim way completes by replaying a reuse request until such initial allocation of said victim way completes.

15. The cache way replacement circuit of claim 14, further comprising victim way selection circuitry for selecting a victim way as the cache way that is to be replaced by placing said victim way on the tail of a FIFO cache way listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache memory.

16. The cache way replacement circuit of claim 14, further comprising data unit circuitry for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss in association with the execution of digital signal processor data unit instructions.

17. The cache way replacement circuit of claim 14, further comprising:

comparison circuitry for comparing a current/incoming primary miss victim way to other ways in said FIFO cache way listing and comparing the set address of the incoming primary miss against other set addresses; and

cache way replaying circuitry for replaying the current/incoming thread in response to said comparing steps until a victim way arises that is free from a reuse hazard.

18. The cache way replacement circuit of claim 14, further comprising circuitry for skipping said victim way and selecting a different victim way in the event of detecting a reuse hazard associated with the use of said victim way.

19. The cache way replacement circuit of claim 18, further comprising circuitry and instructions for performing a tag look up for obtaining a replacement victim way, and, in the event of no hit being detected with said replacement victim way, determining that a reuse hazard does not exist, and, in the event of no reuse hazard existing with said replacement victim way, using said replacement victim way for replacing one of said plurality of set ways.

20. The cache way replacement circuit of claim 19, further comprising instruction unit circuitry for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss in association with the execution of digital signal processor instruction unit instructions.

21. The cache way replacement circuit of claim 20, further comprising:

comparison circuitry for comparing a current/incoming primary miss victim way to other ways in said FIFO cache way listing and comparing the set address of the incoming primary miss against other set addresses; and

cache way replaying circuitry for replaying the current/incoming thread in response to said comparing steps until a victim way arises that is free from a reuse hazard.

22. The cache way replacement circuit of claim 14, further comprising FIFO cache way listing circuitry for adding the most recently used victim way to the tail of said FIFO cache way listing.

23. The cache way replacement circuit of claim 14, further comprising multi-threaded digital signal processing circuitry replacing said victim way in a multi-threaded digital signal processor.

24. The cache way replacement circuit of claim 14, further comprising replacement circuitry permitting the performance of said replacement steps without requiring use of a storage bit for recording used victim ways.

25. The cache way replacement circuit of claim 14, further comprising incrementing circuitry for only incrementing said FIFO cache way listing in the event of a cache way miss.

26. The cache way replacement circuit of claim 14, further comprising incrementing circuitry for performing back-to-back multi-thread accesses in said replacement FIFO cache way listing without replaying said listing.

27. A digital signal processor including means for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss, the digital signal processor comprising:

means for selecting a victim way as the cache way that is to be replaced according to the position of said cache way on a FIFO cache way listing of cache ways for use in the operation of a digital signal processor;

means for placing at the end of said FIFO cache way listing subsequent cache tag misses to said cache memory reusing a victim way on a next cache tag miss;

means for preventing reuse of a victim way until initial allocation of said victim way completes avoiding incoherency between the cache tag and said cache memory;

means for preventing reuse of a victim way until initial allocation of said victim way completes by stalling response to a reuse request until such initial allocation of said victim way completes; and

means for preventing reuse of a victim way until initial allocation of said victim way completes by replaying a reuse request until such initial allocation of said victim way completes.

28. The digital signal processor of claim 27, further comprising means for selecting a victim way as the cache way that is to be replaced by placing said victim way on the tail of a FIFO cache way listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache memory.

29. The digital signal processor of claim 27, further comprising means for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss in association with the execution of digital signal processor data unit instructions.

30. The digital signal processor of claim 29, further comprising:

means for comparing a current/incoming primary miss victim way to other ways in said FIFO cache way listing;

means for comparing the set address of the incoming primary miss against other set addresses; and

means for in response to said comparing steps, replaying the current/incoming thread until a victim way arises that is free from a reuse hazard.

31. The digital signal processor of claim 27, further comprising means for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss in association with the execution of digital signal processor instruction unit instructions.

32. The digital signal processor of claim 31, further comprising:

means for comparing a current/incoming primary miss victim way to other ways in said FIFO cache way listing;

means for comparing the set address of the incoming primary miss against other set addresses; and

means for in response to said comparing steps, replaying the current/incoming thread until a victim way arises that is free from a reuse hazard.

33. The digital signal processor of claim 27, further comprising:

means for comparing a current/incoming primary miss victim way to other ways in said FIFO cache way listing;

means for comparing the set address of the incoming primary miss against other set addresses; and

means for replaying the current/incoming thread in response to said comparing steps until a victim way arises that is free from a reuse hazard.

34. The digital signal processor of claim 27, further comprising means for adding the most recently used victim way to the tail of said FIFO cache way listing.

35. The digital signal processor of claim 27, further comprising means for replacing said victim way in a multi-threaded digital signal processor.

36. The digital signal processor of claim 27, further comprising means for performing said replacement steps without requiring use of a storage bit for recording used victim ways.

37. The digital signal processor of claim 27, further comprising means for only incrementing said FIFO cache way listing in the event of a cache way miss.

38. A computer usable medium having computer readable program code means embodied therein for processing instructions on the digital signal processor for replacing one of a plurality of set ways of a cache memory in the event of a cache tag miss, said computer readable medium comprising:

computer readable program code means for selecting a victim way as the cache way that is to be replaced according to the position of said cache way on a FIFO cache way listing of cache ways for use in the operation of a digital signal processor;

computer readable program code means for placing at the end of said FIFO cache way listing subsequent cache tag misses to said cache memory reusing a victim way on a next cache tag miss;

computer readable program code means for preventing reuse of a victim way until initial allocation of said victim way avoids incoherency between the cache tag and said cache memory;

computer readable program code means for preventing reuse of a victim way until initial allocation of said victim way completes by stalling response to a reuse request until such initial allocation of said victim way completes;

computer readable program code means for preventing reuse of a victim way until initial allocation of said victim way completes by replaying a reuse request until such initial allocation of said victim way completes.

39. The computer usable medium of claim 38, further comprising computer readable program code means for selecting a victim way as the cache way that is to be replaced by placing said victim way on the tail of a FIFO cache way listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache memory.