Method and system for maximum residency replacement of cache memory
IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
UP-0437501
(2006-05-17)
|
등록번호 |
US-7673102
(2010-04-21)
|
발명자
/ 주소 |
|
출원인 / 주소 |
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
0 인용 특허 :
5 |
초록
▼
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 forming a first-in, first-out (FIFO) replacement listing of victim ways for the cache memory, wher
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 forming a first-in, first-out (FIFO) replacement listing of victim ways for the cache memory, wherein the depth of the FIFO replacement listing approximately equals the number of ways in the cache set. The method and system place a victim way on the FIFO replacement 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 replacement listing after any previously selected victim way. Use of a victim way on the FIFO replacement 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.
대표청구항
▼
What is claimed is: 1. A method for replacing one of a plurality of set ways of a cache set 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 listing of cache ways for use i
What is claimed is: 1. A method for replacing one of a plurality of set ways of a cache set 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 listing of cache ways for use in the operation of a digital signal processor; placing at the end of said cache set FIFO listing subsequent cache tag misses to said cache set reusing a victim way on a next cache tag miss; preventing reuse of a victim way until initial allocation of said victim way avoids incoherency between the cache tag and said cache set; 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 cache set FIFO listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache set. 3. The method of claim 1, further comprising the step of replacing one of a plurality of set ways of a cache set in the event of a cache tag miss in association with the execution of digital signal processor data unit instructions. 4. The method of claim 1, further comprising the step of replacing one of a plurality of set ways of a cache set in the event of a cache tag miss in association with the execution of digital signal processor instruction unit instructions. 5. The method of claim 4, 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 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. 6. The method of claim 1, further comprising the step of adding the most recently used victim way to the tail of said FIFO listing. 7. The method of claim 1, further comprising the step of replacing said victim way in a multi-threaded digital signal processor. 8. 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. 9. The method for claim 1, further comprising the step of only incrementing said FIFO listing in the event of a cache way miss. 10. 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 set 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 listing of cache ways for use in the operation of the digital signal processor; FIFO listing populating circuitry for placing at the end of said cache set FIFO listing subsequent cache tag misses to said cache set 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 avoids incoherency between the cache tag and said cache set, 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. 11. The cache way replacement circuit of claim 10, 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 cache set FIFO listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache set. 12. The cache way replacement circuit of claim 10, further comprising data unit circuitry for replacing one of a plurality of set ways of a cache set in the event of a cache tag miss in association with the execution of digital signal processor data unit instructions. 13. The cache way replacement circuit of claim 10, further comprising instruction unit circuitry for replacing one of a plurality of set ways of a cache set in the event of a cache tag miss in association with the execution of digital signal processor instruction unit instructions. 14. The cache way replacement circuit of claim 10, further comprising: comparison circuitry for comparing a current/incoming primary miss victim way to other ways in said FIFO 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. 15. The cache way replacement circuit of claim 10, further comprising FIFO listing circuitry for adding the most recently used victim way to the tail of said FIFO listing. 16. The cache way replacement circuit of claim 10, further comprising multi-threaded digital signal processing circuitry replacing said victim way in a multi-threaded digital signal processor. 17. The cache way replacement circuit of claim 10, further comprising replacement circuitry permitting the performance of said replacement steps without requiring use of a storage bit for recording used victim ways. 18. The cache way replacement circuit of claim 10, further comprising incrementing circuitry for only incrementing said FIFO listing in the event of a cache way miss. 19. A digital signal processor including means for replacing one of a plurality of set ways of a cache set 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 listing of cache ways for use in the operation of the digital signal processor; means for placing at the end of said cache set FIFO listing subsequent cache tag misses to said cache set 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 avoids incoherency between the cache tag and said cache set; 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. 20. The digital signal processor of claim 19, 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 cache set FIFO listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache set. 21. The digital signal processor of claim 19, further comprising means for replacing one of a plurality of set ways of a cache set in the event of a cache tag miss in association with the execution of digital signal processor data unit instructions. 22. The digital signal processor of claim 19, further comprising means for replacing one of a plurality of set ways of a cache set in the event of a cache tag miss in association with the execution of digital signal processor instruction unit instructions. 23. The digital signal processor of claim 22, further comprising: means for comparing a current/incoming primary miss victim way to other ways in said FIFO 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. 24. The digital signal processor of claim 19, further comprising means for adding the most recently used victim way to the tail of said FIFO listing. 25. The digital signal processor of claim 19, further comprising means for replacing said victim way in a multi-threaded digital signal processor. 26. The digital signal processor of claim 19, further comprising means for performing said replacement steps without requiring use of a storage bit for recording used victim ways. 27. The digital signal processor of claim 19, further comprising means for only incrementing said FIFO listing in the event of a cache way miss. 28. A computer usable storage medium having computer readable program code means embodied therein for processing instructions on a digital signal processor for replacing one of a plurality of set ways of a cache set in the event of a cache tag miss, said computer usable storage 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 listing of cache ways for use in the operation of the digital signal processor; computer readable program code means for placing at the end of said cache set FIFO listing subsequent cache tag misses to said cache set 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 set; 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. 29. The computer usable storage medium of claim 28, 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 cache set FIFO listing following said cache miss and wherein the depth of said FIFO approximately equals the number of ways in said cache set.
이 특허에 인용된 특허 (5)
-
Steely, Jr.,Simon C., Managing a multi-way associative cache.
-
Hassler Joseph A. (West Chester PA) Deal Gregory K. (West Chester PA) Koss Timothy A. (Pottstown PA) Heil Stephen F. (West Chester PA), Method and apparatus for cache memory access with separate fetch and store queues.
-
Villagomez, Javier; Gupta, Mayank; Pak, Edward T., Scalable replacement method and system in a cache memory.
-
Gilhousen Klein S. (San Diego CA) Jacobs Irwin M. (La Jolla CA) Weaver ; Jr. Lindsay A. (San Diego CA), Spread spectrum multiple access communication system using satellite or terrestrial repeaters.
-
Gilhousen Klein S. (San Diego CA) Jacobs Irwin M. (La Jolla CA) Padovani Roberto (San Diego CA) Weaver ; Jr. Lindsay A. (San Diego CA) Wheatley ; III Charles E. (Del Mar CA) Viterbi Andrew J. (La Jol, System and method for generating signal waveforms in a CDMA cellular telephone system.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.