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 .
Claims 1, 11, and 20 have been amended.
Claims 1-20 have been examined.
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.
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over Non-patent literature titled, “Access Map Pattern Matching for High Performance Data Cache Prefetch” by Ishii et al. (hereinafter referred to as “Ishii”) in view of US Patent 11,204,878 by Pusderis et al. (previously cited and hereinafter referred to as “Pusderis”).
Regarding claims 1, 11, and 20, taking claim 1 as representative, Ishii discloses:
a processing system, comprising: a load-store unit (Ishii discloses, at p. 15, Table 3, and related description, a processor having a load queue and store queue, which discloses a load-store unit.); and
a prefetcher connected to the load-store unit, the prefetcher including (Ishii discloses, at p. 2, a prefetcher, which discloses being connected to the load-store unit.).:
…a plurality of subzones, and each subzone has a plurality of cache lines (Ishii discloses, at Figure 2 and related description, zones having a number of cache lines, which discloses subzones.); and
an access map for each subzone, wherein each bit position represents a cache line in the plurality of cache lines (Ishii discloses, at p. 6, a memory access map for each hot zone, with “each entry in the bitmap-like data structure” being mapped to a cache line, which discloses each bit position represents a cache line.),
wherein the prefetcher is configured to: determine whether a demand request matches…[a prefetch engine] the demand request being a memory access for a particular address, wherein determining whether the demand request matches…[the prefetch engine] includes determining whether the particular memory address lies within the zone associated with…[the prefetch engine] (Ishii discloses, at pp. 6-7, determining whether a memory access for a particular memory location in particular zone is observed, which discloses a memory access for a particular address and determining whether the particular address lies within a given zone.),
wherein …[the prefetch engine] is configured to: update, with respect to the demand request, a bit position in an access map of a subzone exclusively managed by the matching prefetch engine (Ishii discloses, at pp. 6-7, updating the memory access map in response to a memory access, which discloses with regard to a demand request and exclusively managing the subzones.),
determine a pattern from the access map when a defined number of demand requests have been matched to the subzone managed by the matching prefetch engine (Ishii discloses, at p. 9, determining a pattern based on a number of demand requests matching.), and
generate a prefetch request based on at least the determined pattern (Ishii discloses, at p. 9, generating prefetch requests based on the pattern.).
Ishii does not explicitly disclose a plurality of prefetch engines, wherein each prefetch engine is associated with a zone, each zone comprising a plurality of the aforementioned subzones.
However, in the same field of endeavor (e.g., prefetch) Pusderis discloses:
a plurality of prefetch engines, each associated with a zone (Pusderis discloses, at Figures 3 and 4 and related description, a plurality of prefetch engines, each of which is allocated to a respective sub-region.).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the claimed invention to modify Ishii to include Pusderis’s multiple prefetch engines in order to improve performance by increasing prefetching capabilities. Duplicating prefetchers and dividing work between the multiple prefetchers allows faster performance.
Regarding claims 2 and 12, taking claim 2 as representative, Ishii, as modified, discloses the elements of claim 1, as discussed above. Ishii also discloses:
the prefetcher further comprises a prefetch map for each subzone, wherein each bit position represents a cache line in the plurality of cache lines, and wherein the prefetcher is configured to update, with respect to a generated prefetch request, a bit position in a prefetch map for a subzone in a matching prefetch engine (Ishii discloses, at p. 7, a memory access map for each hot zone and updating a bit in a corresponding entry in response to a prefetch request.).
Regarding claim 3, Ishii, as modified, discloses the elements of claim 2, as discussed above. Ishii also discloses:
the prefetcher is further configured to: determine a demand confirmation when a demand request hits a prefetch map (Ishii discloses, at Table 1 and related description, updating the state in response to a good prefetch, which discloses determining a demand confirmation.).
Regarding claims 4 and 17, taking claim 4 as representative, Ishii, as modified, discloses the elements of claim 3, as discussed above. Ishii also discloses:
the prefetcher is further configured to: maintain a counter for a number of demand confirmations for each prefetch engine (Ishii discloses, at Table 1 and related description, determining the number of good prefetches, which discloses a counter for demand confirmations.); and
increase a prefetch distance for a prefetch engine when the counter meets a threshold, wherein the prefetch distance determines how far ahead a prefetch request stream is relative to an associated demand stream (Ishii discloses, at Table 1 and related description, adjusting the prefetch degree based on the metrics, which discloses increasing distance based on a threshold number of good prefetches.).
Regarding claims 5 and 18, taking claim 5 as representative, Ishii, as modified, discloses the elements of claim 2, as discussed above. Ishii also discloses:
the prefetcher is further configured to: determine a demand mis-confirmation when a demand request misses a prefetch map (Ishii discloses, at Table 1 and related description, determining a prefetch accuracy, which discloses determining demand mis-confirmations.); and
retrain a prefetch engine with another pattern when a number of demand mis-confirmations meets a threshold (Ishii discloses, at Table 1 and related description, adjusting the prefetch based on the metrics, which discloses retraining based on a threshold number of misses.).
Regarding claims 6 and 13, taking claim 6 as representative, Ishii, as modified, discloses the elements of claim 1, as discussed above. Ishii also discloses:
the prefetcher is further configured to: allocate a prefetch engine and a subzone for a first demand request, wherein the first demand request is an anchor point for an associated access map (Ishii discloses, at Figure 4 and related description, determining a first access in a first zone, which discloses allocating a prefetch engine and subzone and that the first demand request is an anchor point for the associated map.);
identify a direction of a demand request stream based on a second demand request and the anchor point (Ishii discloses, at Figure 4 and related description, determining second and third accesses are at higher addresses than the first access, which discloses determining a direction based on a second demand request and the anchor point.); and
confirm the direction of the demand request stream based on a third demand request (Ishii discloses, at Figure 4 and related description, determining second and third accesses are at higher addresses than the first access, which discloses confirming the direction.).
Regarding claims 7 and 14, taking claim 7 as representative, Ishii, as modified, discloses the elements of claim 6, as discussed above. Ishii also discloses:
the prefetcher is further configured to: determine a leading edge pointer based on a most recent demand request in the direction of the demand request stream (Ishii discloses, at p. 13, determining the edge of the memory map.);
shift subzone associated with the leading edge pointer to align the leading edge pointer in a match register (Ishii discloses, at p. 13, aligning at the edge, which discloses shifting, and, at p. 12, a three zone concatenated map, which discloses a match register.);
divide the match register evenly (Ishii discloses, at p. 13, employing a copy of pattern matching logic, which discloses dividing the match register evenly.);
compare one half to the other half to find a pattern (Ishii discloses, at p. 13, generating forward and backward versions of addresses, which discloses comparing one half to the other.); and
repeat the divide and compare for a decremented number of bits (Ishii discloses, at p. 9, pattern matching involves checking addresses between a requested address and a maximum, which discloses comparing for a decremented number of bits.).
Regarding claims 8 and 15, taking claim 8 as representative, Ishii, as modified, discloses the elements of claim 1, as discussed above. Ishii also discloses:
the bit position in the access map is updated when the demand request is a cache miss (Ishii discloses, at Table 1 and related description, updating the state in response to a cache miss.).
Regarding claims 9 and 16, taking claim 9 as representative, Ishii, as modified, discloses the elements of claim 1, as discussed above. Ishii also discloses:
the bit position in the access map is updated when the demand request is a cache hit and a matching prefetch engine is trained, where a trained prefetch engine is prefetching based on a determined pattern (Ishii discloses, at Table 1 and related description, updating the state in response to a good prefetch, which discloses a hit on a prefetched, i.e., trained, value.).
Regarding claims 10 and 19, taking claim 10 as representative, Ishii, as modified, discloses the elements of claim 1, as discussed above. Ishii also discloses:
the prefetcher is further configured to process out-of-order demand requests (Ishii discloses, at p. 3, operating in an optimized environment, which discloses processing out-of-order demand requests.).
Response to Arguments
On pages 9-10of the response filed June 10, 2026 (“response”), the Applicant argues, “The Office Action's § 103 rejection relies entirely on mapping Pusdesris's "sub-regions" onto the claimed "subzones." However, Pusdesris fails to teach or suggest an access map for a subzone managed exclusively by a matching prefetch engine. In Pusdesris, the sub-regions are merely overlapping "sampling space[s]" used by tracking machinery to assess each prefetcher's misprediction behavior to determine writeback policy (Pusdesris at col. 7). They are not exclusive operational domains that confine each engine's pattern-detection and generation work. To the contrary, Pusdesris expressly defeats an "exclusively managed" reading, as it teaches that a prefetcher "routinely" generates prefetches outside of its allocated sub-region (Id. at col. 7). Because Pusdesris explicitly teaches engines reaching outside their designated sub- regions, it cannot render obvious the claimed architecture where the subzone and its corresponding access map are managed exclusively by the matching engine.”
Though fully considered, the Examiner respectfully disagrees. As an initial matter, the Applicant’s arguments mischaracterize the rejection. The rejection does not rely upon Pusderis as teaching sub-zones. Instead, Ishii is relied upon as teaching sub-zones. The main difference between the claims and Ishii is that Ishii does not teach multiple prefetch engines, each of which is associated with a sub-zone. It is for this, the teaching of multiple prefetch engines, that Pusderis is relied upon. Therefore, the argument that Pusderis does not teach exclusive management of the sub-zones is not dispositive. Ishii discloses that each of the sub-zones is managed by a single prefetcher, which discloses that the sub-zones are exclusively managed by the prefetcher. Since Ishii only discloses one prefetcher, it would be impossible for Ishii to teach joint management by multiple prefetchers.
Once the multiple prefetchers of Pusderis are introduced, the question arises how the management would be done. The Examiner maintains that since management of a zone by a single prefetcher is what is disclosed in Ishii, that would logically follow as the model of choice for the combination. This is further supported by the fact that Pusderis discloses allocating individual sub-regions to individual sub-regions. See, e.g., col. 7, line 56 – col. 8, line 23. These lines explicitly discloses that if a given prefetcher prefetches data from a zone allocated to a different prefetcher, the data is not written back. See also, col. 9, lines 41-47. The Examiner maintains that this supports the position that Pusderis does not discloses teachings inconsistent with exclusive management.
The Examiner also submits that the meaning of being “managed exclusively,” is subject to broad interpretation. For example, the specification discloses that each sub-zone maintains an access map. This is somewhat different from the claims, which state the access map is maintained by the prefetch engine. Furthermore, the updating of the maps is performed by the BPM HWPF, which seems to be a single representation of a prefetcher, and not by the individual prefetchers themselves. That is, pattern matching and updating are separate functions. These functions are interpreted as being performed by the prefetch engines collectively as part of exclusive management.
Finally, the Applicant’s arguments say that Pusderis’s sub-regions are overlapping and that Pusderis teaches a prefetcher “routinely” generating prefetch results outside its allocated sub-region. Neither of the terms “overlapping” or “routinely” are used in Pusderis. The bases for the Applicant’s characterizations are therefore unclear. At least in the example shown in Figure 4, the regions allocated to the prefetchers do not overlap. Accordingly, the Applicant’s arguments are deemed unpersuasive.
On page 10 of the response the Applicant argues, “modifying Ishii to incorporate multiple distinct, exclusively managed subzones destroys Ishii's fundamental mechanism of operation. The access-map structure in the primary reference relies entirely on a single, centralized "prefetch generator [that] implements the pattern matching logic" (Ishii at p. 11). As described in reference to Ishii's FIG. 5, which is reproduced above, the core AMPM algorithm utilizes centralized logic that concatenates maps across zones, rather than distributed engines exclusively managing their own discrete subzone maps. Consequently, combining Ishii's centralized map-concatenation logic with Pusdesris's overlapping, non-exclusive sampling spaces cannot yield the claimed invention where each matching prefetch engine exclusively manages the access map of its matched subzone.”
Though fully considered, the Examiner respectfully disagrees. The Applicant contends that a single, centralized prefetch generator is “Ishii’s fundamental mechanism of operation.” The Examiner disagrees and notes that neither single nor central are mentioned in Ishii. It is true that Ishii discloses using one prefetcher. However, whether to use single circuit or multiple circuits is an obvious design choice based on well-known tradeoffs that is typically decided by circumstances. For example, using multiple units often introduces more complexity in requiring coordination, and generally costs more in terms of chip area and thermal power consumption, However, doing so provides increased performance in terms of speed and processing power. Whether to use one or multiple circuits, i.e., duplication of parts, is not of itself a patentable distinction. Accordingly, the Applicant’s arguments are deemed unpersuasive.
Conclusion
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 extension fee 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 date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SHAWN DOMAN whose telephone number is (571)270-5677. The examiner can normally be reached on Monday through Friday 8:30am-6pm Eastern Time.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jyoti Mehta can be reached on 571-270-3995. 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.
/SHAWN DOMAN/
Primary Examiner, Art Unit 2183
Prosecution Insights