Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1, 4-5, 7-10, 13-14 and 18-20 are rejected under 35 U.S.C. 103 as being unpatentable over Schuttenberg (11086777) in view of Kailas et al. (2008/0010414).
As per claims 1 and 19, Schuttenberg teaches an integrated circuit comprising:
a cache (Fig. 4, elements 8, 30, 32, 38; Col. 6, lines 33-38) comprising:
a databank with multiple entries configured to store respective cache lines (Fig. 2, Col. 6, lines 50-57 - Describes the cache sets having multiple entries);
an array of cache tags associated with respective entries in the databank (Figs. 2 and 5, Col. 7, lines 13-22);
wherein each cache tag includes an indication of which one of two or more subsets the respective entry is a member of (Col. 7, lines 13-46; Col. 9, line 55 – Col. 10, line 3); and
a cache control circuitry (Fig. 4, element 70; Col. 8, lines 59-62) configured to:
receive a message that will cause a cache block replacement (Fig. 6, element 100; Col. 9: lines 54-58 – The initial cache access request will either cause a hit or a miss, which would then possibly cause a cache block replacement);
responsive to the message, select a way of the cache by: (Col. 7, lines 47-51, Col. 8, lines 12-22, Col. 10, lines 4-22 - Describes wherein the local replacement policy applies to the entries of the first subset, in this case would be set X)
performing an aging operation of a replacement policy exclusively on entries of a selected first subset, wherein entries of a second subset of the two or more subsets are not aged by the aging operation (Fig. 4; Col. 3, lines 27-47; Col. 5, lines 40-46; Col. 9, lines 10-15 – Describes that there are two different subsets (a “proper subset” and a “remaining subset”). Each subset can have their own replacement policy – the “proper subset” has a local replacement policy, and the “remaining subset” has a shared replacement policy. On a cache miss, in a given set, the cache control circuitry will determine whether the set is one of the “proper subset” or the “remaining subset,” and implement the respective replacement policy that is associated with the subset. Col. 4: lines 18-25, Col. 5: lines 26-29, Col. 8: lines 53-58 – Describes that the local and shared replacement policies could be one of a random replacement policy, a round-robin replacement policy, a least recently used (LRU) replacement policy and a not-recently-used (NRU) replacement policy. It is noted that in an LRU policy an aging operation is performed by incrementing counters for the ways not accessed – see Col. 4: lines 37-47. Based on the above teachings, as well as Col. 8, lines 41-58 and Col. 11: lines 53-63, it is abundantly clear that only the replacement policy that is associated with the selected subset where a miss has occurred will be implemented. For example, if the miss occurs in a “proper subset” that has a local replacement policy that consists of an LRU policy, only those entries of that “proper subset” will be aged, while the entries of the “remaining subset” that have a share replacement policy will not); and
selecting the way from the selected first subset based on results of the aging operation (Fig. 4; Col. 2, lines 22-27, Col. 3, lines 27-36; Col. 4, lines 22-25 and 37-47 – Here, the first subset is the “proper subset” that includes a local replacement policy that consists of an LRU policy, which performs an aging operation); and
responsive to the message, evict an entry of the cache in the first subset and in the selected way (Fig. 6, elements 112, 116; Col. 3, lines 27-47, Col. 10, lines 18-23, 44-46).
Although Schuttenberg does teach that the selection of the victim local replacement policy entry (which could be set X) can be based on a random or pseudorandom number generator (Col. 4, lines 18-25, Col. 5, lines19-24, Col. 10, lines 16-22), Schuttenberg does not teach selecting a first subset from among the two or more subsets based on a prioritization of the two or more subsets.
Kailas teaches a system for dynamic priority-based cache replacement which replaces lower priority data (a subset of data items) in a cache which are assigned relative priority values (Fig. 1, Abstract, Pars. 18, 20-24).
It would have been obvious to a person skilled in the art at the time the invention was filed to include the teachings of Kailas into the system taught by Schuttenberg above. This would have been obvious because Kailas, like Schuttenberg, teaches that to effectively manage cache, older data must be purged, and there are conventional schemes (static priority) for assigning priority to the data in the cache. However, there is a need in the art to provide a better dynamic priority-based cache replacement, which is presented by Kailas (Pars. 4-5, 26).
As per claims 4 and 20, Schuttenberg teaches wherein the cache control circuitry is configured to: update counters for entries of the cache from only the first subset (See detailed rationale provided in claims 1 and 19 above. Also, as illustrated in Fig. 6, when the path is taken such that the set X is in the proper subset, only the sets in the proper set are updated. As stated in Col. 4, lines 37-47, when LRU is used as a replacement policy, the accessed way is set to 0 and all others are incremented).
As per claim 5, Schuttenberg teaches wherein the counters for entries of the cache are age counters that are incremented to perform an aging operation of the replacement policy (Col. 4, lines 37-47 - wherein all others that are not accessed are incremented, and therefore the counter represents the age of the way since being accessed).
As per claim 7, Schuttenberg teaches wherein the cache control circuitry is configured to: responsive to the message, insert a new cache line in the entry of the cache in the first subset and in the selected way (Col. 10, lines 4-25 - Describes when there are no invalid ways, a replacement algorithm is used to select the way to replace with the requested data);
select one of two or more subsets for the entry storing the new cache line (Col. 10, lines 9-22 - wherein the selection is based on the tag portion for the data); and
store an indication that the entry storing the new cache line is a member of the selected subset (Col. 10, lines 4-8 - wherein in order to determine whether an entry is invalid/valid an indication must be stored).
As per claim 8, Kailas makes it abundantly clear that the cache can be an L2 cache that is shared by multiple processor cores (Par. 28).
As per claim 9, Kailas makes it abundantly clear that the cache can be an L3 cache that is shared by multiple processor cores (Par. 28).
As per claim 10, see claim 1 above. Further, Schuttenberg teaches where the sets of the cache have subsets (Abstract, Col. 2, lines 22-27; Col. 3, lines 27-47).
As per claim 13, Schuttenberg teaches applying the replacement policy to entries of the cache from only the first subset comprises: updating counters for entries of the cache from only the first subset (See detailed rationale provided in claims 1 and 19 above. Also, as illustrated in Fig. 6, when the path is taken such that the set X is in the proper subset, only the sets in the proper set are updated. As stated in Col. 4, lines 37-47, when LRU is used as a replacement policy, the accessed way is set to 0 and all others are incremented).
As per claim 14, Schuttenberg teaches wherein the counters for entries of the cache are age counters that are incremented to perform an aging operation of the replacement policy (Col. 4, lines 37-47 - wherein all others that are not accessed are increment and therefore the counter represents the age of the way since being accessed).
As per claim 18, Schuttenberg teaches:
responsive to the message, inserting a new cache line in the entry of the cache in the first subset and in the selected way (Col. 10, lines 4-25 – Describes when there are no invalid ways, a replacement algorithm is used to select the way to replace with the requested data);
selecting one of two or more subsets for the entry storing the new cache line (Col. 10, lines 9-22 - wherein the selection is based on the tag portion for the data); and
storing an indication that the entry storing the new cache line is a member of the selected subset (Col. 10, lines 4-8 - wherein in order to determine whether an entry is invalid/valid an indication must be stored).
Claims 2 and 11 are rejected under 35 U.S.C. 103 as being unpatentable over Schuttenberg and Kailas et al., as applied to claim 1 above, and further in view of Auld et al. (2005/0091457).
As per claim 2, Schuttenberg and Kailas teach all the limitations of claim 1. Schuttenberg and Kailas do not explicitly teach wherein the cache control circuitry is configured to:
set a flag in a cache tag associated with a respective entry in the cache to indicate whether data stored in the respective entry is also stored by an inner cache.
However, Auld teaches of a system when a cache line is replaced with a new cache line in an outer cache, and a victim flag is made true, the cache control logic may send a back-invalidate signal to any inner caches in order to ensure cache coherency and to improve performance and costs (Pars. 2, 4, 20-25).
It would have been obvious to a person skilled in the art at the time the invention was filed to include the teachings of Auld into the system taught by Schuttenberg and Kailas above. This would have been obvious because Auld, like Schuttenberg and Kailas, teaches a system for replacing cache lines with new cache lines, and further, teaches that cache coherency between outer and inner caches is important since what may be important to the outer cache may be unused by the inner caches, and subsequently be overwritten via an LRU method (Par. 3). Auld further teaches that the process of sending a back-invalidate signal to the inner cache provides a corrective procedure to the original method (LRU method) of selecting a victim cache line (Par. 25).
As per claim 11, see the rationale provided in claim 2 above.
Claims 6 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Schuttenberg and Kailas et al., as applied to claim 1 above, and further in view of Moyer (2023/0096814).
As per claim 6, although Schuttenberg teaches of managing a replacement policy in order to predict which entry in the set is least likely to be used again in the near future (Col. 2: lines 43-53), Schuttenberg and Kailas do not specifically teach wherein the replacement policy is a Re-reference Interval Prediction policy and the counters for entries are respective re-reference prediction values for the entries.
However, Moyer teaches a system for performing cache operations where the replacement policy is a Re-reference Interval Prediction policy and the counters for entries are respective re-reference prediction values for the entries (Pars. 19-21).
It would have been obvious to a person skilled in the art at the time the invention was filed to include the replacement policy taught by Moyer into the system taught by Schuttenberg and Kailas. This would have been obvious because Moyer makes it clear that the re-reference interval prediction (RRIP) replacement policy is a known policy (Par. 19), and Schuttenberg also teaches predicting which entry is to be less likely used is desired (Col. 2: lines 49-53), and further teaches that the cache taught therein is associated with cache replacement policy storage circuitry which stores a number of local replacement policy entries, each for storing local replacement policy information specific to a corresponding set of the set-associative cache (Col. 3: lines 1-6). A person skilled in the art would have understood that the RRIP policy taught by Moyer would be a desirable replacement policy in the system taught by Schuttenberg so as to be able to perform the prediction process of which entry is the less likely to be used, as was taught by Schuttenberg above.
As per claim 15, see the rationale provided in claim 6 above.
Claims 16 and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Schuttenberg and Kailas et al., as applied to claim 13 above, and further in view of Scott et al. (2008/0151909).
As per claim 16, Schuttenberg and Kailas teach all the limitations of claims 13. Schuttenberg further teaches that an LRU replacement policy can be used, which uses counters to determine which sets have been used less (aged) (Col. 4: lines 37-47). Schuttenberg also teaches that other replacement policies can be used, such as a random, round robin, etc. policies (Col. 4: lines 18-21).
However, neither Schuttenberg or Kailas teach comparing values of the counters for entries of the cache from the first subset; and breaking a tie between two entries from the first subset with a same counter value by selecting among ways with the tied entries using a round robin selection.
Scott teaches of a system that can determine which packet to use based on age, wherein the age of the packet is determined based on how long it has been sitting in a staging buffer (Pars. 61-62). Scott further teaches that in order to determine the time the packet has been sitting in the buffer, it uses a set of counters to keep track of the number of outstanding packets in each epoch (Par. 67). Finally, an arbiter compares the age values (counter values) to determine which packet is selected, and if there is a tie, it is broken using a separate round robin priority scheme (Par. 71).
It would have been obvious to a person skilled in the art at the time the invention was filed to include the teachings of Scott, specifically the tie-breaking process, into the system taught by Schuttenberg and Kailas above. This would have been obvious because Schuttenberg teaches that an LRU method can be used to determine which cache line to replace, where the LRU method uses counters to determine the “age” (least recently used) of the data in the cache line (See above). Since Scott also teaches using counters to determine the age of a packet within a buffer, and subsequently uses a round-robin method when two counters tie, a person skilled in the art would have seen the advantage of the process taught by Scott since you can’t have a situation where two cache lines end in a tie when using the LRU replacement policy in the system taught by Schuttenberg.
As per claim 17, see the rationale explained in claim 16 above. Further, Schuttenberg teaches that multiple replacement policies can be used, such as a random, round robin, etc. policies (Col. 4: lines 18-21). Based on the rationale described in claim 16 above, specifically the tie-breaking process taught by Scott, and being that you can’t have a situation where two cache lines end in a tie in the system taught by Schuttenberg above, a person skilled in the art would have seen the advantage of using another type of replacement policy to break the tie, in which Schuttenberg teaches that one of those policies could be a random replacement policy (Col. 8, lines 18-21).
Response to Arguments
Applicant’s arguments with respect to claims 1, 10 and 19 have been fully considered but are not persuasive.
On p. 10 of the applicant’s remarks, the applicant states that “Shuttenberg does not teach or suggest a dynamic, intra-set partition where, upon a miss, an aging operation is performed exclusively on a first subset of entries while entries in a second subset within that same set are not aged. Shuttenberg’s system is silent on this concept, as it simply selects a policy (local or shared) and applies it to the entire set.” It is noted that claims 1, 10 and 19 refer to “a databank with multiple entries, and an array of cache tags associated with respective entries, wherein each cache tag includes an indication of which one of two subsets the respective entry is a member of,” however, nowhere in the claims does it state that there are two subsets within a same set of the entries. Figs. 4 and 5 and col. 3, lines 27-47 of Shuttenberg clearly teach of multiple entries within a databank (Fig. 4) and an array of cache tags associated with respective entries (Fig. 5), wherein each cache tag indicates whether the entry is one of a proper subset (local replacement policy) or a remaining subset (shared replacement policy). As is further described in the rejection of claim 1 above, only one of these replacement policies needs to applied to a given entry/set that contains a miss, while the others would not apply their replacement policy. The applicant’s argument that Shuttenberg’s system simply selects a policy and applies it to the entire set might be true, but the claim never describes subsets within a single set. The claims simply refer to multiple entries and whether the multiple entries are a member of a subset.
The applicant’s argument with regard to Kailas et al. are moot since Kailas et al. was not used to teach this element of the claims.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Se PTO-892.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SCOTT T BADERMAN whose telephone number is (571) 272-3644. The examiner can normally be reached 8-5 M-F, every other Friday off.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, John Cottingham, can be reached at 571- 272-1400. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/SCOTT T BADERMAN/Supervisory Patent Examiner, Art Unit 2118