DETAILED ACTION
Claims 1-10 and 13-22 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.
This is a reminder to insert patent numbers for any issued patent applications listed in paragraphs 2-3.
The disclosure is objected to because of the following informalities:
In paragraph 34, line 3, replace “associate” with --associated--.
Appropriate correction is required.
Claim Recommendations
The examiner generally recommends wording method claims to comprise method steps as opposed to “wherein…” limitations.
Claim Interpretation
At least one claim is identified as including a non-limiting contingent limitation. “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).
Claim 8, under its BRI, includes no further limitation on claim 1 when the countdown tag is invalid.
Claims 9-10, under BRI, include no further limitation on claim 1 when the countdown tag is not expired.
Claims 16-18, under BRI, include no further limitation on claim 1 when the load status is not a late load status, in which case halting is not performed (e.g. paragraph 20).
For expedited/compact prosecution, the examiner recommends that applicant reword where possible to remove/reduce contingencies to require limitations in the aforementioned claims. This will help ensure that prior art rejections are not applied to only non-contingent portions of the claims if and when applicant overcomes the current rejections. The examiner notes that a contingent limitation cannot be the reason for allowability of a method claim. Taking claim 8 as an example, applicant could claim --determining the countdown tag is valid, wherein the load status allows compute element operation based on the valid countdown tag.--.
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
Such claim limitations are:
In claim 13, “the countdown tag is examined in one or more blocks of the memory system”. Per claim 15, the one or more blocks are interpreted to include a buffer, L1 cache, L2 cache, L3 cache, crossbar switch, and equivalents thereof. While “memory logic block” was originally listed in claim 15, the examiner deems this generic and no structure corresponding thereto has been disclosed. Thus, it is not imported into the claim.
In claim 14, “signaling…by at least one of the one or more blocks of the memory system”. Again, the one or more blocks are interpreted to include a buffer, L1 cache, L2 cache, L3 cache, crossbar switch, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
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-10 and 13-20 are rejected under 35 U.S.C. 103 as being unpatentable over Godard et al. (US 2015/0106597, as cited by applicant), in view of Hamzeh et al. “Branch-Aware Loop Mapping on CGRAs”.
Referring to claim 1, Godard has taught a processor-implemented method for parallel processing, the method comprising:
accessing compute elements (FIG.3, 201; FIG.4, 401, 403, etc.), wherein each compute element within the compute elements is known to a compiler (from paragraph 40, operations are statically scheduled to the units; thus, they are known by a compiler, which optimizes scheduling of code on those elements (e.g. paragraphs 72, 76));
tagging a load operation with a countdown tag (see the abstract, FIG.6 (601-605), and paragraphs 76-82. Basically, a compiler encodes a load operation (DLOAD) with a countdown tag (schedule latency). In the example shown, the countdown tag = 3, which means the load is expected to complete in 3 cycles), wherein the tagging is performed by the compiler (again, from paragraph 72, the scheduling compiler does the encoding), and wherein the load operation is targeted to a memory system associated with the compute elements (load instructions load data from memory (e.g. FIG.4, 115, 101A, 101B, which make up at least part of a memory system));
performing the load operation, wherein the load operation comprises load data and a load address (see paragraphs 76-77, where the load operation involves loading data from a load address p when the load is performed), wherein the countdown tag flows through the 2D array of compute elements in conjunction with the load data and the load address (the countdown tag flows through the array from an entrance point into the retire station to configure the timer. Load data/address also flows through the array to the appropriate compute elements);
monitoring countdown tag status by a control unit circuit, wherein the monitoring occurs as the load operation is performed (as the load is performed, a countdown timer configured based on the countdown tag value is decremented each cycle (FIG.6, 605). The retire station (control unit) (FIG.4, 405) monitors the countdown timer for expiration (i.e., timer = 0) and sets a flag indicating expiration (FIG.6, 611)); and
generating a load status, by the control unit circuit, based on the monitoring (again, the retire station generates a load status upon expiration of the timer (FIG.6, 611) (e.g. “load not finished before counter expiration”)).
Godard has not taught that the compute elements are in a two-dimensional (2D) array of compute elements, wherein each compute element is coupled to its neighboring compute elements within the array of compute elements. However, Godard has taught that the method could be implemented on many different architectures (paragraph 131). Hamzeh has taught a 2D reconfigurable array architecture with neighboring interconnections (e.g. FIG.1) to which instructions are statically scheduled by a compiler to at least accelerate execution of loops (abstract). FIGs.2-3 shows scheduling operations to different compute elements of the array with interconnections denoting dependencies. As a result, to accelerate loops, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Godard such that the compute elements are in a two-dimensional (2D) array of compute elements, wherein each compute element is coupled to its neighboring compute elements within the array of compute elements. One of ordinary skill in the art would have recognized the compatibility of this statically-scheduled array architecture with the static scheduling of Godard. For instance, in paragraph 72 of Godard, the load instruction (1st instruction) and the add instruction (3rd instruction that depends on the load instruction) would be similarly mapped to the array as shown in Hamzeh (where the compute element assigned to the load sends data to the element assigned to the add), but the element assigned to the add would only be allowed to execute when the load has finished in time (as indicated by the countdown timer); otherwise it would stall to ensure correct results (e.g. paragraphs 24, 44, 82, etc.).
Referring to claim 2, Godard, as modified, has taught the method of claim 1 wherein the countdown tag comprises a time value (from FIG.6 and paragraphs 76-82, the countdown tag represents a number of cycles (time value) that the countdown timer is to count).
Referring to claim 3, Godard, as modified, has taught the method of claim 2 further comprising decrementing the time value as the load operation is being performed (see paragraph 44 and FIG.6. The time value is decremented after the load is issued, i.e., as it is being performed).
Referring to claim 4, Godard, as modified, has taught the method of claim 3 further comprising basing the time value that is decremented on an architectural cycle (from paragraphs 76-82, the architectural cycle is interpreted as the time window between the load instruction and the dependent instruction (e.g. the add instruction in paragraph 81). The time value is decremented a number of times based on the length of this window), wherein the architectural cycle is based on an architecture associated with the 2D array of compute elements (again the cycle is based on the time between the load and dependent instruction. The compiler determines the cycle length based on the architecture that executes the instructions).
Referring to claim 5, Godard, as modified, has taught the method of claim 4 wherein the architectural cycle is established by the compiler (from paragraphs 76-82, the compiler generates the instructions of the window, thereby establishing the architectural cycle).
Referring to claim 6, Godard, as modified, has taught the method of claim 4 wherein the architectural cycle comprises one or more physical cycles (see paragraph 82. The window includes 3 machine cycles).
Referring to claim 7, Godard, as modified, has taught the method of claim 6 wherein the one or more physical cycles represent actual wall clock time (all time is wall clock time. A physical cycle is a time unit that corresponds to some number of seconds. A wall clock traverses all time, including fractions of seconds).
Referring to claim 8, Godard, as modified, has taught the method of claim 1 wherein the load status allows compute element operation, based on a valid countdown tag (again see paragraphs 76-82. If the countdown tag is valid, i.e., the load finishes executing within the time indicated by the tag, a dependent compute element will be allowed to operate).
Referring to claim 9, Godard, as modified, has taught the method of claim 1 wherein the load status halts compute element operation, based on an expired countdown tag (see paragraphs 44 and 76-82. If the tag expires (i.e., the counter reaches 0 before the load finishes), a stall occurs (because the load data is not ready)).
Referring to claim 10, Godard, as modified, has taught the method of claim 9 wherein the expired countdown tag indicates late load data arrival to the 2D array of compute elements (see paragraphs 44 and 76-82. If the load doesn’t finish within the time indicated by the tag, the load data is late and a stall must occur).
Referring to claim 13, Godard, as modified, has taught the method of claim 1 wherein the countdown tag is examined in one or more blocks of the memory system (the countdown tag is examined by the retire station, which is a buffer that buffers load data (FIG.5A, 505; FIG.5B, 513), and is, thus, a block of the memory system. The tag is monitored until it reaches 0 (FIG.6, steps 607-609)).
Referring to claim 14, Godard, as modified, has taught the method of claim 13 further comprising signaling the control unit circuit of a countdown tag expiration by at least one of the one or more blocks of the memory system (see FIG.6, steps 609-611, where a flag of the control unit is signaled by the retire station in response to expiration of the counter).
Referring to claim 15, Godard, as modified, has taught the method of claim 13 wherein the one or more blocks of the memory system comprise a load buffer (as described above, the retire station buffers load data and, thus, is a load buffer), a level 1 (L1) cache, a level 2 (L2) cache, a level 3 (L3) cache, an access buffer, or a crossbar switch.
Referring to claim 16, Godard, as modified, has taught the method of claim 1 further comprising halting the array of compute elements, based on the load status (again, see paragraphs 44 and 76-82. Basically, when the load status is “late” or “not finished before expiration of the counter”, a stall occurs (the array is halted)).
Referring to claim 17, Godard, as modified, has taught the method of claim 16 wherein the load status for halting the array includes a late load data status (if the data is not loaded within the scheduled latency (e.g. 3 cycles in paragraphs 76-82), the load data is late and a halt/stall occurs).
Referring to claim 18, Godard, as modified, has taught the method of claim 16 wherein the halting the array of compute elements is initiated by the control unit circuit (again, where the control unit detects a zero countdown timer, halting is initiated (paragraph 44)).
Referring to claim 19, Godard, as modified, has taught the method of claim 1 wherein the load status enables static scheduling integrity (static scheduling by the compiler is performed as in paragraphs 76-82 with the hope that the load will be complete by the time the loaded data is needed. If the load is not completed in the time indicated (e. g. 3 cycles), then if a dependent instruction were allowed to execute, the schedule would lack integrity (soundness), because the dependent instruction would not use the correct data. However, Godard’s load status allows for a “late” status, which indicates the load has not completed before the counter reaches 0, in which case the dependent instruction is stalled/halted so that it does not use the incorrect data. The dependent instruction will halt until the data is ready, which results in correct execution and scheduling integrity).
Referring to claim 20, Godard, as modified, has taught the method of claim 19 wherein the static scheduling integrity overcomes indeterminate memory load latency (see paragraphs 15 and 76-82. Basically, the load latency is unknown at compile time. The schedule in paragraphs 76-82 is created with the expectation that the load hits the L1 cache and can complete within 3 cycles. However, it may miss the cache and require more cycles. The scheduling based on load status as described above overcomes the unknown by only allowing a dependent instruction to execute if the load completes within the expected time; otherwise, it will have to be stalled until the load does complete).
Claims 21-22 are rejected under 35 U.S.C. 103 as being unpatentable over Godard in view of Hamzeh and the examiner’s taking of Official Notice.
Claim 21 is mostly rejected for similar reasoning as claim 1. Furthermore, Godard has taught a computer program product embodied in a non-transitory computer readable medium (program in instruction cache 113, L2 instruction cache 101A, and/or main memory 101B) for parallel processing, the computer program product comprising code which causes one or more processors to perform the accessing, monitoring, and generating operations (all code is executed by one or more processors in Godard, which causes these operations, which are specific to the Godard system, to occur).
Godard has not taught that the compiler code itself, which causes the one or more processors to perform the tagging, is stored in the medium of Godard (that is, it is technically possible for the compilation to occur in a system other than Godard). However, Official Notice is taken it was well known in the art before applicant’s invention to have a same processor execute both a compiler and a compiled program output by the compiler. This conveniently allows a developer to both write and compile the program and test/run it on the same system with the same hardware, instead of having to use a different system and delivering the compiled program to Godard. Among other things, this could realize a savings in time. 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 Godard such that the compiler code is also stored and executed within Godard to carry out the tagging.
Claim 22 is rejected for similar reasoning as claim 21, where the memory is one or more of 113, 101A, and 101B.
Response to Arguments
On page 9 of applicant’s response, applicant argues that the tag in Godard is consumed at the point of decode and does not physically accompany the load data and load address through the architecture. Applicant states that, at no point does the countdown tag travel with the load data and load address through the computer elements of any array.
It is the examiner’s understanding that Godard does not consume the tag at the point of decode. Instead, the load unit (which is a function unit in the array that performs the load operation) receives the countdown tag and loads it into the retire station (FIG.6, 601). The load unit is shown in FIG.4 as part of the execution logic 109, which comprises a number of function units (FIG.3). The load unit and other function units 109 receive data that flows through various stages as shown in FIG.1. As such, the load operation (including the load address), along with the tag, flows through the various stages together until they arrive at the load unit, at which point, the tag is stored in the retire station. The load operation with load address flows through the array’s load unit 401 on its way to the cache 115 (FIG.4). The load data flows through the array’s retire station 405 (FIG.4) as it travels from cache 115 to storage (registers) or other function unit. The tag flows through the array’s load unit on its way to the retire station 405. These flows occur in conjunction with each other, i.e., collectively/cooperatively/in combination, to carry out a load operation. It appears that, by using words such as “accompany” and “travel with”, applicant is interpreting the claim such that the tag, load data, and load address flow simultaneously along the same path through the array. However, the examiner asserts the claim is broader than this. The claim requires that the tag go through the array (though not even through multiple compute elements of the array as argued). The tag does not have to travel the same path and/or at the same time as the load data/address.
On page 11 of applicant’s response, applicant argues that Godard counts machine cycles, not architectural cycles, as claimed.
The claim does not require counting architectural cycles. The claim requires a time value based on an architectural cycle, which is broad.
Conclusion
THIS ACTION IS MADE FINAL. 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
Prosecution Insights