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 § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-8 are rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. The claims recite at least one machine readable medium comprising a plurality of instructions which, when executed on a computing device to perform the functions as recited in the claims. However, the specification did not define what type of medium/signal are included in a machine readable medium. According to MPEP 2111, examiner obliged to give the terms or phrases their broadest interpretation definition awarded by one of an ordinary skill in the art unless applicant has provided some indication of the definition of the claimed terms or phrases. Therefore, examiner interprets the machine readable medium to include any type of medium which includes a carrier medium such as signals. Signals are directed to a non-statutory subject matter. Thus, claims 1-8 are rejected under 35 U.S.C. 101 for being directing to a non-statutory subject matter.
To overcome this rejection, it is suggested that the applicant explicitly state the machine readable medium as “non-transitory” in the claims.
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.
Claim(s) 1-3, 9-10, and 15-16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Cypher (US 7,325,102) in view of Abhishek (US 2021/0294607).
In regards to claim 1, Cypher teaches
detect a memory access with a [physical] address to a shared memory; (figs. 1 and 2, C4:49-53, a remote request is received (detected) from external processor 150 to the (shared) cache memory 120 of processor 100. The request includes an address.)
create a hash value [of a subset of the physical] address; (C4:55-62 teaches the incoming address is hashed)
identify a state bit corresponding to the hash value in a snoop filter cache tag array; (fig. 2 C5:36-53 teaches that the storage 220 (snoop filter cache tag array) includes a snoop filter indicator (i.e. state bit) that indicates if the cache line is either not stored in the cache 120 (i.e. the indicator is not set) or may potentially be stored in the cache 120 (i.e. the indicator is set)
snoop a cache with the physical address if the state bit is set. (fig. 2 C5:36-53 teaches that if the snoop filter indicator indicates that the cache line is potentially stored in the cache 120 (i.e. the indicator is set) then cache controller 110 snoops the cache 120)
Cypher may not explicitly teach
At least one machine readable medium comprising a plurality of instructions which, when executed on a computing device, cause the computing device to; and
That the address is a physical address, and that the hash value is only created from a subset of the physical address, and
However, Abhishek teaches in ¶102 that a portion of a physical address can be hashed and used to identify if the cache potentially stores a cache line associated with the full address. ¶158 that a processing device can be programmed to perform the function (i.e. via executing instructions stored on a machine readable medium)
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to have incorporated the teachings of Abhishek to improve the system of Cypher by using hashes of a portion of physical addresses for the hashing function. This allows the hashes to be simpler/faster to compute and have a smaller number of possible hashed outputs (i.e. indexes into the snoop array, or number of tags to store in the snoop array that require to be matched). The motivation for such is there is a tradeoff between speed, size, circuity complexity and accuracy where in situations like this it’s beneficial to give up accuracy (i.e. many addresses could result in the same hash, only resulting in a potential indication of a hit, while a miss is still guaranteed) at the benefit of gaining speed and reducing the size and complexity of the circuit.
In regards to claims 2, 10 and 16 Cypher further teaches
wherein the state bit indicates there is a chance the physical address is owned by the cache if set and indicates the physical address is not owned by the cache if not set. ( C5:45-63 teaches that the filter indication (state bit) indicates either the cache line is not stored in the cache (not set) or that the cache line may be in the cache (i.e. the state bit is set and indicates only a chance that the address is owned by the cache, i.e. it’s not guaranteed)
In regards to claim 3, Cypher further teaches
refresh a first portion of the snoop filter cache tag array, the refresh comprising: initiating requests for ownership of a set of physical addresses of data stored in the cache; creating a new hash value for an approved address of the set of physical addresses, recording the new hash value in a second portion of the snoop filter cache tag array and setting a corresponding new state bit in the second portion of the snoop filter cache tag array; repeating the creating, the recording, and the setting for each approved address of the set of physical addresses; and
clearing the first portion of the snoop filter cache tag array after all of the requests for ownership have been processed. (Fig. 3 C6:42-C7:40 teaches the processes of “repopulating” (i.e. refreshing) the snoop filter tag array by dividing the snoop filter array into two portions, of which one of the two portions is being actively used and the other is being repopulated (i.e. refreshed) by determining the hash index/values of the addresses in the cache 120 and storing the appropriate indicator associated with each of the hash indexes/values (i.e. the processes is repeated, until all the addresses of data in the cache have been performed). Once the processes of repopulating (refreshing) on of the portions of the snoop filter array, that array is made the active array, and the other array is then initialized (i.e. the indications are cleared) and the repopulation (refreshing) for this portion is then performed.
In regards to claims 9 and 15, taking claim 15 as exemplary Cypher teaches
a snoop filter to maintain coherency of a cache, the snoop filter comprising: (fig. 2, snoop filter 205)
an encoded value generator to create an encoded value from [a subset of a physical] address of data stored in the cache, (C6:10-26 teaches tags (addresses of data) of the cache are hashed by the hash function generator 215 (encoded value generator)
the encoded value generator to create another encoded value from another subset of another [physical] address of a memory transaction; (figs. 1 and 2, C4:49-53, a remote request is received (detected) from external processor 150 to the (shared) cache memory 120 of processor 100. The request includes an address. C4:55-62 teaches the incoming address is hashed)
a snoop filter cache tag array to store the encoded value and set a corresponding state bit; (C6:10-26 teaches tags (addresses of data) of the cache are hashed by the hash function generator 215 (encoded value generator) and uses these hashes (encoding) to identify a location in the storage 220 (snoop filter tag array) and set the corresponding indicator in the storage 220 (snoop filter tag array)
the snoop filter to identify the another encoded value in the snoop filter cache tag array and another corresponding state bit; the snoop filter to initiate a snoop of the cache if the another corresponding state bit is set. (fig. 2 C5:36-53 teaches that the storage 220 (snoop filter cache tag array) includes a snoop filter indicator (i.e. state bit) that indicates if the cache line is either not stored in the cache 120 (i.e. the indicator is not set) or may potentially be stored in the cache 120 (i.e. the indicator is set) and that if the snoop filter indicator indicates that the cache line is potentially stored in the cache 120 (i.e. the indicator is set) then cache controller 110 snoops the cache 120)
Cypher may not explicitly teach that the address is a physical address, and that the hash value is only created from a subset of the physical address or
wherein the snoop tag array is 1/Nth a size of the cache tag array, and N is at least 2.
However, Abhishek teaches in ¶102 that a portion of a physical address can be hashed and used to identify if the cache potentially stores a cache line associated with the full address.
It would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to have incorporated the teachings of Abhishek to improve the system of Cypher by using hashes of a portion of physical addresses for the hashing function. This allows the hashes to be simpler/faster to compute and have a smaller number of possible hashed outputs (i.e. indexes into the snoop array, or number of tags to store in the snoop array that require to be matched) such that the snoop tag array can be a fraction of the size of the cache tag array. The motivation for such is there is a tradeoff between speed, size, circuity complexity and accuracy where in situations like this it’s beneficial to give up accuracy (i.e. many addresses could result in the same hash, only resulting in a potential indication of a hit, while a miss is still guaranteed) at the benefit of gaining speed and reducing the size and complexity of the circuit.
Allowable Subject Matter
Claims 4-8, 11-14, and 17-20 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims (with the assumption that the 101 rejection is corrected for claims 4-8).
The following is a statement of reasons for the indication of allowable subject matter: The prior art of Cypher describes changing between two different snoop filters, with only one being active at a time while the other is being updated. The claims 4, 11, and 17 require checking both the portions for indications if data is potentially located in the cache. The prior art of Cypher does not provide any teaching/suggestions/motivation for checking both the active and the inactive (currently being updated) portions of the snoop filter array in response to receiving a new memory transaction while the updating (refreshing) is occurring. While fig. 4 of Cypher and its associated teachings in C7:41-C9:27 does describe using multiple different snoop array that are indexed by different hashes, the separate snoop arrays are also divided into active and inactive (currently being repopulated/refreshed) portions, and Cypher is silent on accessing both the active and inactive portions for checking the indicators, and using a combination of the indicators to determine whether or not to snoop the cache.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Prasad (US 2018/0349280) teaches other methods of using hashing in coordination with a snoop filter.
Tune (US 2016/0062893) teaches the use of hashing with snoop filtering.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JASON W BLUST whose telephone number is (571)272-6302. The examiner can normally be reached 12-8:30 EST.
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 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.
/JASON W BLUST/Primary Examiner, Art Unit 2132