DETAILED ACTION
Claims 1-20 have been examined.
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 .
Specification
The lengthy specification has not been checked to the extent necessary to determine the presence of all possible minor errors. Applicant’s cooperation is requested in correcting any errors of which applicant may become aware in the specification.
Claim Objections
Claim 1 is objected to because of the following informalities:
The first line of the last paragraph should be reworded to --based on an eviction, from the processor data cache, of the cacheline with at least one of…--, so that it is not the cache that has the at least one checkpoint bit set, but the cacheline instead.
In line 8, it appears that “from” should be replaced with --with respect to--.
Claim 10 is objected to because of the following informalities:
It appears that both instances of “order from” should be replaced with --order with respect to--.
In line 6, insert --bit-- after “checkpoint”.
Claim 11 is objected to because of the following informalities:
The first line of the last paragraph should be reworded to --based on an eviction, from the processor data cache, of the cacheline with at least one of…--, so that it is not the cache that has the at least one checkpoint bit set, but the cacheline instead.
It appears that “from” should be replaced with --with respect to--.
Claim 19 is objected to because of the following informalities:
In line 3, insert commas before and after “relative to the cacheline”. There is no basis for “the triggering event relative to the cacheline”.
Claim 20 is objected to because of the following informalities:
The first line of the last paragraph should be reworded to --based on an eviction, from the processor data cache, of the cacheline with at least one of…--, so that it is not the cache that has the at least one checkpoint bit set, but the cacheline instead.
It appears that “from” should be replaced with --with respect to--.
Appropriate correction is required.
Claim Interpretation
At least one claim is identified as including non-limiting contingent limitations. “The broadest reasonable interpretation of a method (or process) claim having contingent limitations requires only those steps that must be performed and does not include steps that are not required to be performed because the condition(s) precedent are not met.” “The broadest reasonable interpretation of a system (or apparatus or product) claim having structure that performs a function, which only needs to occur if a condition precedent is met, requires structure for performing the function should the condition occur. The system claim interpretation differs from a method claim interpretation because the claimed structure must be present in the system regardless of whether the condition is met and the function is actually performed.” See MPEP 2111.04(II).
Regarding claim 1, the “setting…” step is contingent on “a second processor operation accessing the cacheline out of order from a first processor operation”. Thus, where such an out-of-order access does not occur, the setting never occurs. And, if the setting never occurs, then the eviction of the cacheline with a set checkpoint bit never occurs, which means steps (i) and (ii) also never occur. Steps (i) and (ii) also don’t occur when the setting occurs, but the eviction does not. As such, the method, under one broad interpretation, merely includes the “identifying…” step. The examiner recommends removing the contingencies by positively reciting all steps. For instance, after the “identifying…” step, applicant could claim --accessing the cacheline by a second operation out of order with respect to a first processor operation-- and then follow with --setting one of the first checkpoint bit or the second checkpoint bit of the cacheline based on the accessing--. For the last paragraph, applicant could start with --evicting, from the processor data cache, the cacheline with at least one of the first checkpoint bit or the second checkpoint bit being set-- and then follow with --based on the evicting, (i) allocating…, and (ii), resynchronizing…--. With these amendments, all steps would be required by the method.
Regarding claim 2, when the allocating does not occur in claim 1, claim 2 also does not set forth a required step.
Regarding claim 3, line 2 is required, as are the associations between the first and second subsets and first and second wrap bit values, respectively, when the setting step of claim 1 does not occur (e.g. because there may be no first operation or second operation. For instance, maybe a given program execution only results in in-order execution of first and second processor operations). Since claim 1 covers a method without the first and second operations, their associations in claim 3 are non-limiting.
Regarding claim 4, when the setting does not occur in claim 1, claim 4 also does not set forth a required step. Even if the setting of claim 1 does occur, the re-setting of claim 4 does not occur when the “based on…” conditions are not present. The examiner recommends rewording claim 4 to positively recite all steps to remove contingencies. For instance, applicant could claim --retiring the second processor operation-- and --determining…-- the association.
Regarding claim 5, when the allocating does not occur in claim 1, claim 5 also does not set forth a required step/limitation.
Regarding claim 6, the executing step is required, but the setting step is not required when the additional processor operation from the first subset is not associated with the first checkpoint bit. Again, the examiner recommends rewording appropriately.
Regarding claim 7, the executing and setting steps are required, but the re-setting step is not required prior to retirement of (or if retirement never occurs for (e.g. due to flush)) the additional processor operation from the second subset. The examiner recommends rewording appropriately.
Regarding claim 8, when the resynchronizing does not occur in claim 1, claim 8 also does not set forth a required step.
Regarding claim 9, when the evicting does not occur in claim 1, claim 9 also does not set forth a required step/limitation.
Regarding claim 10, when the setting does not occur in claim 1, claim 10 also does not set forth a required step/limitation.
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 13 and 15-17 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 claims recite the following limitations for which there is a lack of antecedent basis:
In claim 13, line 1, “the operations”. Are these the operations of claim 11, line 7, or the first and second operations in claim 11, or a combination of all operations of claim 11. The examiner recommends inserting a descriptor between “perform” and “operations” in claim 11, line 7, and then using that same descriptor before “operations” in claim 13.
In claim 15, “the operations” for similar reasoning.
In claim 16, “the operations” for similar reasoning.
In claim 17, “the operations” for similar reasoning.
Claims 16-17 are also indefinite due to their dependence on an indefinite claim.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-10 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Blundell et al., “INVISIFENCE…” (as cited by applicant).
Referring to claim 1, Blundell has taught a computer-implemented method comprising:
identifying, in a processor data cache and during program execution, a cacheline comprising a plurality of tag field bits including at least a first checkpoint bit and a second checkpoint bit (see section 3.1, 3rd paragraph, which refers to adding two bits (speculatively-read and written bits) to each cacheline tag).
As described in the “Claim Interpretation” section above, the remaining limitations in the claim are contingent on one or more conditions and, thus, are not required by the claim when the condition(s) are not satisfied.
Claim 2 is rejected for similar reasoning as claim 1, because, as discussed in the “Claim Interpretation” section, the limitation(s) of claim 2 are contingent and not required.
Referring to claim 3, Blundell has taught the computer-implemented method of claim 1, wherein: the cacheline is accessed by additional processor operations (see the “Violation detection” section. A write can access a cacheline that has been speculatively read, and a read can access a cacheline that has been speculatively written); a first subset of the additional processor operations are associated with a first wrap bit value (a first wrap bit value is interpreted as another name for a speculatively-written bit. Thus, a read that wants to read a line with the set first wrap bit value can be said to be associated with that value); and the second processor operation and a second subset of the additional processor operations are associated with a second wrap bit value (a second wrap bit value is interpreted as another name for the speculatively-read bit. Thus, a write that wants to store to a line with the set second wrap bit value can be said to be associated with that value).
Claim 4 is rejected for similar reasoning as claim 3, because, as discussed in the “Claim Interpretation” section, the limitation(s) of claim 4 are contingent and not required.
Claim 5 is rejected for similar reasoning as claim 3, because, as discussed in the “Claim Interpretation” section, the limitation(s) of claim 5 are contingent and not required.
Referring to claim 6, Blundell has taught the computer-implemented method of claim 5, further comprising: executing an additional processor operation from the first subset of the additional processor operations out of order (see a speculative store in section 3.2). As described in the “Claim Interpretation” section above, the remaining limitations in the claim are contingent on one or more conditions and, thus, are not required by the claim when the condition(s) are not satisfied.
Referring to claim 7, Blundell, as modified, has taught the computer-implemented method of claim 6, further comprising: executing an additional processor operation from the second subset of the additional processor operations out of order (this additional operation would be any that speculatively accesses a cacheline with a checkpoint bit already set. For instance, if a speculative store already occurred and the speculative write bit is set, a speculative load to the same line would set the other checkpoint bit); and setting the second checkpoint bit of the cacheline (again, see the above reasoning). As described in the “Claim Interpretation” section above, the remaining limitations in the claim are contingent on one or more conditions and, thus, are not required by the claim when the condition(s) are not satisfied.
Claim 8 is rejected for similar reasoning as claim 1, because, as discussed in the “Claim Interpretation” section, the limitation(s) of claim 8 are contingent and not required.
Claim 9 is rejected for similar reasoning as claim 1, because, as discussed in the “Claim Interpretation” section, the limitation(s) of claim 9 are contingent and not required.
Claim 10 is rejected for similar reasoning as claim 1, because, as discussed in the “Claim Interpretation” section, the limitation(s) of claim 10 are contingent and not required.
---------------------------------------------------------------------------------------------------------------------
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-7, 9-17, and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over Blundell in view of Mehrotra et al., U.S. 6,145,054.
Referring to claim 1, Blundell has taught a computer-implemented method comprising:
identifying, in a processor data cache and during program execution, a cacheline comprising a plurality of tag field bits including at least a first checkpoint bit and a second checkpoint bit (see section 3.1, 3rd paragraph, which refers to adding two bits (speculatively-read and written bits) to each cacheline tag);
setting one of the first checkpoint bit or the second checkpoint bit of the cacheline based on a second processor operation accessing the cacheline out of order from a first processor operation (see section 3.2 and note the “Speculative loads” and “Speculative stores” sections. Further, the “Violation detection” section on p.5 discusses a store/write to a speculatively-read line, meaning that the load/read incorrectly executed out of order and before the store/write (hence the violation); and
based on an eviction of the cacheline from the processor data cache with at least one of the first checkpoint bit or the second checkpoint bit being set, (ii) resynchronizing the program execution (see section 3.2, and note the “Speculation commit”, “Violation detection”, and “Speculation abort” sections. The language “forcing a commit before evicting any speculatively-read or speculatively written block from the data cache” means that a cacheline with a set checkpoint bit is evicted at some point. Further, when an entry is evicted, it is because that entry was replaced by new data brought into the cache. Thus, data replacement/eviction causes program execution to be resynchronized to the new cache contents that replaced the evicted contents, so that when the new cache contents are needed again, the processor can access it in the cache).
Blundell has not taught that, based on the eviction, (i) allocating a load ordering queue entry for the cacheline. However, Mehrotra has taught that when a cacheline is evicted from a write-back cache, which is a type of cache advantageous when the same locations in memory is frequently written to, the cache line is sent to a victim queue (load ordering queue) where it waits until it is written back to a next level of cache (see column 13, lines 17-32). This ensures data can be evicted but not lost. The entry in the victim queue to which the cacheline is allocated is a “load ordering queue entry”. As a result, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Blundell such that the cache is a write-back cache and for the evicting to cause the allocating so that the speculative data, if committed, can be saved despite being evicted.
Referring to claim 2, Blundell, as modified, has taught the computer-implemented method of claim 1, wherein allocating the load ordering queue entry for the cacheline includes holding an address of the cacheline in the load ordering queue entry (see Mehrotra (column 13, lines 31-32)).
Referring to claim 3, Blundell, as modified, has taught the computer-implemented method of claim 1, wherein: the cacheline is accessed by additional processor operations (see the “Violation detection” section. A write can access a cacheline that has been speculatively read, and a read can access a cacheline that has been speculatively written); the first processor operation and a first subset of the additional processor operations are associated with a first wrap bit value (a first wrap bit value is interpreted as another name for a speculatively-written bit. Thus, a first store operation that speculatively stores to a location corresponding to a cacheline would set a first wrap bit value, and any subsequent read that wants to read a line with the first wrap bit value can be said to be associated with that value); and the second processor operation and a second subset of the additional processor operations are associated with a second wrap bit value (a second wrap bit value is interpreted as another name for the speculatively-read bit. Thus, a second load that speculatively loads from a location corresponding to a cacheline would set a second wrap bit value, and any subsequent write that wants to store to a line with the second wrap bit value can be said to be associated with that value).
Referring to claim 4, Blundell, as modified, has taught the computer-implemented method of claim 3, further comprising re-setting at least one of the first checkpoint bit or the second checkpoint bit based on retirement of the second processor operation and at least one of the first checkpoint bit or the second checkpoint bit being associated with the second processor operation (see p.2, first full paragraph, last sentence. When a speculative instruction is committed/retired, the associated speculatively-read/written bit is cleared. Further, note that claim 4 may alternatively be rejected for similar reasoning as claim 3 because claim 4 includes a contingent step that is not required (see “Claim Interpretation” section)).
Referring to claim 5, Blundell, as modified, has taught the computer-implemented method of claim 4, wherein the second processor operation is retired based on a wrap bit value associated with the second processor operation (see the last sentence in the first paragraph of the “Violation detection” section. A commit is forced before eviction for an operation whose speculatively-read bit is set).
Referring to claim 6, Blundell, as modified, has taught the computer-implemented method of claim 5, further comprising: executing an additional processor operation from the first subset of the additional processor operations out of order; and setting the first checkpoint bit of the cacheline based on the additional processor operation from the first subset of the additional processor operations being associated with the first checkpoint bit (see a speculative store in section 3.2).
Referring to claim 7, Blundell, as modified, has taught the computer-implemented method of claim 6, further comprising: executing an additional processor operation from the second subset of the additional processor operations out of order (this additional operation would be any that speculatively accesses a cacheline with a checkpoint bit already set. For instance, if a speculative store already occurred and the speculative write bit is set, a speculative load to the same line would set the other checkpoint bit); setting the second checkpoint bit of the cacheline (again, see the above reasoning); and re-setting the second checkpoint bit of the cacheline upon retirement of the additional processor operation from the second subset of the additional processor operations (see p.2, first full paragraph, last sentence. When a speculative instruction is committed/retired, the associated speculatively-read/written bit is cleared).
Referring to claim 9, Blundell, as modified, has taught the computer-implemented method of claim 1, wherein the eviction of the cacheline from the processor data cache is initiated in response to a triggering event, and wherein the triggering event is an invalidating probe (see the “Violation detection” section on p.5. Eviction occurs in response to a violation. For example, when a load to a cacheline that has been speculatively written occurs, this will cause the speculatively written data to be evicted/replaced, such that the cacheline’s association with that data is invalidated (so as to hold new data)).
Referring to claim 10, Blundell, as modified, has taught the computer-implemented method of claim 1, setting one of the first checkpoint bit or the second checkpoint bit of the cacheline based on the second processor operation accessing the cacheline out of order from the first processor operation comprises: selecting a checkpoint bit from a group comprising the first checkpoint bit and the second checkpoint based on a wrap bit value associated with the second processor operation (the wrap bit value may be the opcode and may distinguish between load and store. So, depending on the wrap bit value, either the speculative write bit will be set (for a store), or the speculative read bit will be set (for a load)); and setting the selected checkpoint bit based on the second processor operation accessing the cacheline out of order from the first processor operation. (again, see the rejection of claim 1).
Claims 11-12, 14-17, and 19 are rejected for similar reasoning as claims 1-4, 6-7, and 9, respectively. With respect to claim 11, note that a processor, as taught by Blundell, includes various logic circuitry (“logic layer circuit”) to perform all steps. As such, whatever circuitry is involved in performing the steps of claim 11 is reasonably mapped to “logic layer circuit”.
Referring to claim 13, Blundell, as modified, has taught the processor of claim 12, wherein the operations further include:
re-setting at least one of the first checkpoint bit or the second checkpoint bit of the cacheline based on retirement of the second processor operation (see p.2, first full paragraph, last sentence. When a speculative instruction is committed/retired, the associated speculatively-read/written bit is cleared. The first checkpoint bit would be set by any instruction subsequent to the load (second operation) executing out of order, even at a significant amount of time later); and
de-allocating the load ordering queue entry for the cacheline within the load ordering queue (the victim queue holds an entry until it is written back to the next level of memory. At some point after the write-back, the entry is deallocated so it can be assigned to another entry).
Claim 20 is mostly rejected for similar reasoning as claim 1. Further, Blundell has taught physical memory comprising computer-executable instructions that, when executed by at least one processor, cause the at least one processor to performs the claimed acts (instructions, including the loads and stores that execute in Blundell, are stored in memory in a computing system, e.g. in split instruction/data L1 cache, unified L2 cache, and main memory (Figure 6)).
Allowable Subject Matter
Claim 18 is 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.
Response to Arguments
On page 10 of applicant’s response, applicant argues that Mehrotra does not disclose allocating a load ordering queue entry for the cacheline based on an eviction of the cacheline.
The examiner asserts that Mehrotra teaches allocating an entry in response to eviction. However, it is Blundell that teaches that speculatively-read/written entries are evicted (“Violation detection” section). Thus, once they are evicted in Blundell, the examiner asserts that it is obvious to store the evicted entries into the victim queue (load ordering queue) so that they can be written to slower memory for preservation in case they are to be committed.
On page 11, 1st paragraph, applicant argues that committing a speculatively loaded cache block by clearing the but used to track speculative loads of the block is not allocating a load ordering queue entry for the cacheline.
As described above, Blundell teaches evicting both speculatively read and written lines. Once evicted, it is obvious to put them into a victim queue as taught by Mehrotra. The examiner notes that a load ordering queue need not be interpreted as only holding cachelines loaded in response to load instructions. Store instructions also write/load data into cachelines and, thus, a written cacheline by a store instruction can be put into the load ordering queue to write to slower memory.
Argument IV is moot due to the removal of Official Notice.
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 David J. Huisman whose telephone number is 571-272-4168. The examiner can normally be reached on Monday-Friday, 9:00 am-5:30 pm.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jyoti Mehta, can be reached at 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.
/David J. Huisman/Primary Examiner, Art Unit 2183