DETAILED ACTION
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 .
This Office Action is responsive to the reply filed 13 November 2025.
Claims 1-19 and 21 are pending and have been presented for examination.
Claim 20 has been cancelled.
Response to Arguments
Applicant’s arguments, see pages 7-9, filed 13 November 2025, with respect to claim 1 have been fully considered and are persuasive. The rejection of claim 1 under 35 U.S.C. § 103 has been withdrawn.
Applicant’s arguments with respect to claim(s) 10 and 16 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument. PRASAD is being relied upon to disclose the newly added limitation regarding updating the bloom filter.
The limitation added to claims 10 and 16 “… sending tag values from all the cache ways in a set index accessed during the lookup…” is ambiguous. This limitation could be construed two different ways:
1. accessing “set A” of a cache, and based on accessing “set A” of the cache all the cache ways in “set A” are sent to the bloom filter.
2. accessing “way1” and “way2” in “set A”, based on accessing “way1” and “way2” sending “way1” and “way2” to the bloom filter because those are all the ways that were accessed in “set A”.
Based on applicant’s arguments, it seems applicant is relying on interpretation 1 above. The art applied to the claims would anticipate the claim relying on interpretation 2. Sending just the ways that are accessed could include just sending one way, if only one way was accessed in the set.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 10-19 and 21 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
The limitation added to claims 10 and 16 “… sending tag values from all the cache ways in a set index accessed during the lookup…” is ambiguous. This limitation could be construed two different ways:
1. accessing “set A” of a cache, and based on accessing “set A” of the cache all the cache ways in “set A” are sent to the bloom filter.
2. accessing “way1” and “way2” in “set A”, based on accessing “way1” and “way2” sending “way1” and “way2” to the bloom filter because those are all the ways that were accessed in “set A”.
Based on this ambiguity, claims 10 and 16 are indefinite.
Claims 11-15 are also rejected based on their dependency to claim 10.
Claims 17-19 and 21 are also rejected based on their dependency to claim 16.
Claim Rejections - 35 USC § 103
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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 10-13 and 16-19 is/are rejected under 35 U.S.C. 103 as being unpatentable over GHOSH (U.S. Patent Application Publication #2009/0222625) in view of HORNUNG (U.S. Patent #11,907,130), DUAN (U.S. Patent Application Publication #2024/0061780) and PRASAD (U.S. Patent Application Publication #2018/0349280).
10. GHOSH discloses An apparatus for operating a cache memory (see [0060]-[0061]: level 1 and level 2 cache memories in a computing system), the apparatus comprising: a cache controller in the cache memory, the cache memory comprising a set associative structure with a plurality of cache ways and a plurality of sets, each set comprises a cache block from each way (see HORNUNG below); a hit prediction table in the cache memory (see [0076]: cache miss indication logic), the hit prediction table comprising a Bloom filter (see [0090]: bloom filter), the hit prediction table being configured to: perform a lookup in the Bloom filter for a tag (see DUAN below) value associated with a first data item requested from the cache memory (see [0090]-[0091]: bloom filter is queried using the address from the processor; [0070]; miss prediction logic uses the address from the processor; see DUAN below regarding tag value); and update the Bloom filter with results of a lookup in the cache memory for the requested first data item (see [0094]: whenever there is a line fill, counters are updated, when there is a replacement, counters are decremented), wherein updating the Bloom filter comprises sending tag values from all the cache ways in a set index accessed during the lookup to the bloom filter (see PRASAD below).
HORNUNG discloses the following limitations that are not disclosed by GHOSH: a cache controller in the cache memory (see column 2, lines 47-54: cache access circuitry), the cache memory comprising a set associative structure with a plurality of cache ways and a plurality of sets, each set comprises a cache block from each way (see column 10, lines 43-60: set-associative cache); the first data item having an associated tag value (see column 11, lines 23-55: each cache entry specifies a tag value and a data value). A set-associative cache allows more flexibility for placement of data in the cache, which results in improved performance (see column 11, lines 10-15). Cache access circuitry allows for performing a lookup in a cache memory (see column 2, lines 50-55). GHOSH fails to explicitly disclose the use of a tag value. However, GHOSH does disclose the use of an address to locate data in a cache. HORNUNG discloses that a tag value is used to locate data in a cache. The use of a tag array is well-known in the art and is ubiquitous in the use of cache memory systems to locate data. While GHOSH doesn’t explicitly disclose a tag, the use of a tag would have been obvious to one of ordinary skill in the art to allow a cache lookup to take place.
It would have been obvious, before the effective filing date of the claimed invention, to a person having ordinary skill in the art to which said subject matter pertains to modify GHOSH to use a set-associative cache, as disclosed by HORNUNG. One of ordinary skill in the art would have been motivated to make such a modification to improve performance, as taught by HORNUNG. GHOSH and HORNUNG are analogous/in the same field of endeavor as both references are directed to locating data in a cache memory.
It would have been obvious, before the effective filing date of the claimed invention, to a person having ordinary skill in the art to which said subject matter pertains to modify GHOSH to have a tag value associated with a data item, as disclosed by HORNUNG. One of ordinary skill in the art would have been motivated to make such a modification to locate a data item in the cache, as taught by HORNUNG. GHOSH and HORNUNG are analogous/in the same field of endeavor as both references are directed to locating data in a cache memory.
DUAN discloses the following limitations that are not disclosed by GHOSH: performing a lookup in a Bloom filter for the tag value associated with the first data item (see [0043]-[0044]: the tag part of an address is used as part of the partial address that is fed into a hash function to perform miss detection). GHOSH discloses an address is fed to a hash function to perform miss detection. DUAN discloses that the address can be the tag address that would be used to locate data in a cache. The combination of GHOSH and HORNUNG established that a tag address is used to locate data in a cache. Mapping a tag address to a bloom filter allows for hit/miss prediction based on the tag address, as disclosed by DUAN. Furthermore, the address in GHOSH would be considered a tag address based on the combination of GHOSH and HORNUNG. The use of the cache tag address in a bloom filter for miss predication is one of a limited number of known solutions to implement miss prediction using a bloom filter. This is disclosed by DUAN. “When there is a design need for market pressure to solve a problem and there are a finite number if identified, predictable solutions, a person of ordinary skill has good reason to pursue the known options within his or her technical grasp." KSR, 82 USPQ2d at 1397.
It would have been obvious, before the effective filing date of the claimed invention, to a person having ordinary skill in the art to which said subject matter pertains to modify GHOSH to perform a lookup in a bloom filter using the tag value, as disclosed by DUAN. One of ordinary skill in the art would have been motivated to make such a modification, as this would be obvious to try, as taught by DUAN. GHOSH and DUAN are analogous/in the same field of endeavor as both references are directed to cache miss prediction using bloom filters.
PRASAD disclose the following limitations that are not disclosed by GHOSH: wherein updating the Bloom filter comprises sending tag values from all the cache ways in a set index accessed during the lookup to the bloom filter (see [0057]-[0058]). PRASAD discloses fetching the missing data to a cache memory, along with additional data for addresses that are sequential to the requested address that missed in the cache. This results in multiple data values being added to the cache. As GHOSH discloses, each time there is a line fill, the bloom filter is updated. If there are multiple line fills, multiple updates would occur in the bloom filter. The advantage of fetching multiple lines is quicker access to data that is likely to be accessed in the near future (see [0058]).
It would have been obvious, before the effective filing date of the claimed invention, to a person having ordinary skill in the art to which said subject matter pertains to modify GHOSH to fetch multiple cache lines, and perform updates for multiple tag values in the bloom filter, as disclosed by PRASAD. One of ordinary skill in the art would have been motivated to make such a modification to ensure quick access to data likely to be accessed in the near future, as taught by PRASAD. GHOSH and PRASAD are analogous/in the same field of endeavor as both references are directed to predicting access to data in a cache memory.
11. The apparatus of claim 10, wherein to perform the lookup in the Bloom filter for the tag value associated with the first data item, the hit prediction table is further configured to: compute indices for the Bloom filter based on the tag value associated with the first data item (see GHOSH [0095]: entry to the bloom filter computed using the address; DUAN [0043]-[0044]: tag address used to compute an entry in the bloom filter).
12. The apparatus of claim 10, wherein the cache controller is configured to: perform a lookup in the cache memory for the requested first data item based on the lookup in the hit prediction table (see GHOSH [0105]: if the bloom filter indicates the data may be in the cache, the cache is accessed to locate the data).
13. The apparatus of claim 12, wherein the cache controller is configured to: cancel the lookup in the cache memory for the requested first data item when the lookup in the hit prediction table for the tag value associated with the first data item results in a miss (see GHOSH [0072]: abort cache access if a miss is predicted).
16. GHOSH discloses A non-transitory computer-readable storage device storing instructions that, when executed by a computing system, cause the computing system to perform a method for operating a cache memory (see [0060]-[0061]: level 1 and level 2 cache memories in a computing system), the method comprising: receiving a request for a first data item from the cache memory of the computing system (see [0060]-[0061]: fetch and instruction from the instruction cache, load/store instruction for data from the cache), the first data item having an associated tag value (see HORNUNG below); performing a lookup in a Bloom filter for the tag (see DUAN below) value associated with the first data item (see [0090]-[0091]: bloom filter is queried using the address from the processor; [0070]; miss prediction logic uses the address from the processor; see HORNUNG below regarding tag value); performing a lookup in the cache memory for the requested first data item based on the lookup in the Bloom filter (see [0105]-[0110]: if a miss is predicted, no access is made to the cache, conversely, if a miss is not predicted an access would be made to the cache; [0096]: when the vector entry is set, the data value may be in the cache); and updating the Bloom filter based on results of the lookup in the cache memory for the requested first data item (see [0094]: whenever there is a line fill, counters are updated, when there is a replacement, counters are decremented), wherein updating the Bloom filter comprises sending tag values from all the cache ways in a set index accessed during the lookup to the bloom filter (see PRASAD below).
HORNUNG discloses the following limitations that are not disclosed by GHOSH: the first data item having an associated tag value (see column 11, lines 23-55: each cache entry specifies a tag value and a data value). GHOSH discloses the use of cache memories, and accessing data in a cache memory. GHOSH fails to explicitly disclose the use of a tag value. However, GHOSH does disclose the use of an address to locate data in a cache. HORNUNG discloses that a tag value is used to locate data in a cache. The use of a tag array is well-known in the art and is ubiquitous in the use of cache memory systems to locate data. While GHOSH doesn’t explicitly disclose a tag, the use of a tag would have been obvious to one of ordinary skill in the art to allow a cache lookup to take place.
It would have been obvious, before the effective filing date of the claimed invention, to a person having ordinary skill in the art to which said subject matter pertains to modify GHOSH to have a tag value associated with a data item, as disclosed by HORNUNG. One of ordinary skill in the art would have been motivated to make such a modification to locate a data item in the cache, as taught by HORNUNG. GHOSH and HORNUNG are analogous/in the same field of endeavor as both references are directed to locating data in a cache memory.
DUAN discloses the following limitations that are not disclosed by GHOSH: performing a lookup in a Bloom filter for the tag value associated with the first data item (see [0043]-[0044]: the tag part of an address is used as part of the partial address that is fed into a hash function to perform miss detection). GHOSH discloses an address is fed to a hash function to perform miss detection. DUAN discloses that the address can be the tag address that would be used to locate data in a cache. The combination of GHOSH and HORNUNG established that a tag address is used to locate data in a cache. Mapping a tag address to a bloom filter allows for hit/miss prediction based on the tag address, as disclosed by DUAN. Furthermore, the address in GHOSH would be considered a tag address based on the combination of GHOSH and HORNUNG. The use of the cache tag address in a bloom filter for miss predication is one of a limited number of known solutions to implement miss prediction using a bloom filter. This is disclosed by DUAN. “When there is a design need for market pressure to solve a problem and there are a finite number if identified, predictable solutions, a person of ordinary skill has good reason to pursue the known options within his or her technical grasp." KSR, 82 USPQ2d at 1397.
It would have been obvious, before the effective filing date of the claimed invention, to a person having ordinary skill in the art to which said subject matter pertains to modify GHOSH to perform a lookup in a bloom filter using the tag value, as disclosed by DUAN. One of ordinary skill in the art would have been motivated to make such a modification, as this would be obvious to try, as taught by DUAN. GHOSH and DUAN are analogous/in the same field of endeavor as both references are directed to cache miss prediction using bloom filters.
17. The non-transitory computer-readable storage device of claim 16, further comprising instructions that cause the computing system to perform the method for operating the cache memory, the method further comprising: computing indices for the Bloom filter based on the tag value associated with the first data item (see GHOSH [0095]: entry to the bloom filter computed using the address; DUAN [0043]-[0044]: tag address used to compute an entry in the bloom filter).
18. The non-transitory computer-readable storage device of claim 16, wherein the cache memory comprises a set associative structure with a plurality of cache ways and a plurality of sets, each set comprises a cache block from each way (see HORNUNG below).
HORNUNG discloses the following limitations that are not disclosed by GHOSH: the cache memory comprises a set associative structure with the plurality of cache ways and a plurality of sets, each set comprises a cache block from each way (see column 10, lines 43-60: set-associative cache). A set-associative cache allows more flexibility for placement of data in the cache, which results in improved performance (see column 11, lines 10-15).
It would have been obvious, before the effective filing date of the claimed invention, to a person having ordinary skill in the art to which said subject matter pertains to modify GHOSH to use a set-associative cache, as disclosed by HORNUNG. One of ordinary skill in the art would have been motivated to make such a modification to improve performance, as taught by HORNUNG. GHOSH and HORNUNG are analogous/in the same field of endeavor as both references are directed to locating data in a cache memory.
19. The non-transitory computer-readable storage device of claim 18, further comprising instructions that cause the computing system to perform the method for operating the cache memory, the method further comprising: retrieving tag values associated with cache blocks in a set index of the plurality of sets for the requested first data item; and comparing the retrieved tag values with the tag value associated with the first data item (see HORNUNG column 11, lines 40-55: compare tag values to locate data).
Allowable Subject Matter
Claims 1-9 are allowed.
Claims 14 and 21 would be allowable if rewritten to overcome the rejection(s) under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), 2nd paragraph, set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
The state of the art discloses miss detection logic used with a cache memory. The miss detection logic can include a bloom filter. Updates made to the cache memory through line fills and eviction are reflected in the bloom filter for future miss predictions. GHOSH discloses incrementing a counter and decrementing a counter in response to line fills and line replacements. GHOSH also discloses updating the vector entry based on updates to the cache. Clearly, when a line is removed, the corresponding entry is updated in the bloom filter.
However, the prior art fails to anticipate, or render obvious, sending the tag values remaining to the bloom filter and computing indices for the remaining cache blocks. Since the bloom filter is updated when data items are added, the remaining data items in GHOSH are already reflected in the bloom filter and there is no need to send them to the bloom filter when an entry is removed.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to EDWARD J DUDEK JR whose telephone number is (571)270-1030. The examiner can normally be reached Monday - Friday, 8:00A-4:00P.
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, Hosain T Alam can be reached at 571-272-3978. 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.
/EDWARD J DUDEK JR/Primary Examiner, Art Unit 2132