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 Objections
Claims 4, 11, and 18 are objected to because of the following informalities. The claims recite: “wherein value for the strides of each sequence..” Examiner suggests amending to inserting ‘a’ or ‘the’ before value.
Claims 7, 14, and 20 are objected to because of the following informalities. The claims recite: “generating, by the processor set, a number of lists for each slice in the number of slices based on uncommon values and strides in the number of sequences, and values of the determined induction variable corresponding to last terms for sequences of each slice”. It is unclear whether the values of the determined induction variable are being used in the generation of the number of lists or whether the limitation is claiming additionally generating values of the determined induction variable. For the purposes of examination, the examiner will consider the values of the determined induction variable to be additionally generating along with the number of lists.
Appropriate correction is required.
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 1-25 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.
Claims 1 recites the limitation "and at" in line 16. There is insufficient antecedent basis for this limitation in the claim. Claims 8, 15, and 21 also recite this issue. Examiner suggests amending to “the values and strides”
The terms “uncommon” and “common” in claims 7, 14, 20, and 22 are a relative term which renders the claim indefinite. The terms “uncommon” and “common” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention. It is indefinite what a "uncommon" or "common" value is.
Claims 2-7, 9-14, 16-20, and 22-25 depend on claims that are rendered indefinite. Therefore, the claims suffer the same deficiency as the parent claim.
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-25 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim(s) 1, 8, and 15 recite(s):
generating, by a processor set, a conditional tree based on the number of conditionals in the loops, wherein a value is determined by evaluating each conditional in the number of conditionals;
generating, by the processor set, a multi-dimensional table based on the values for the number of conditionals obtained from the conditional tree;
determining, by the processor set, an induction variable for the modified loops;
slicing, by the processor set, the multi-dimensional table to generate a number of slices, wherein each slice in the number of slices represents at least a portion of the multi-dimensional table;
generating, by the processor set, a number of sequences by splitting values in each slice, wherein values and strides in the number of sequences are determined for proper execution of the modified loops;
generating, by the processor set, a number of new conditionals based on the determined induction variable and at least values and strides in the number of sequences;
and generating, by the processor set, the modified loops based on the number of new conditionals.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 1 is a method
Yes. Claim 8 is a machine
Yes. Claim 15 is a manufacture
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of "generating", as drafted in #1-2, and 5-7 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
The limitation of "determining", as drafted in #3 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
The limitation of "slicing", as drafted in #4 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The claims recite the following additional elements:
“A computer implemented method..”
“A computer system..”
“A computer program product..”
A processor set
A set of one or more computer readable storage media
The elements that are recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 2, 9, and 16 recite(s):
wherein each slice from the number of slices comprises a set of values obtained by varying the determined induction variable while fixing other existing induction variables in the loops with the number of conditionals.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 2 is a method
Yes. Claim 9 is a machine
Yes. Claim 16 is a manufacture
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The limitation in #8 above. As claimed and under BRI, is an additional element that is mere instructions to apply an exception. For example, "the number of slices comprises a set of values" in the context of this claim encompasses merely separating values in a table in specific orientations and storing them. See in the MPEP §§2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 3, 10, and 17 recite(s):
wherein the generating, by the processor set, a number of sequences by splitting values in each slice comprises: generating, by the processor set, sequences with fixed stride by splitting values in each slice, wherein each sequence in the sequences with fixed stride corresponds to a number of values for a result index in each slice.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 3 is a method
Yes. Claim 10 is a machine
Yes. Claim 17 is a manufacture
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation, as drafted in #9 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
a processor set
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 4, 11, 18 recite(s):
further comprising: determining, by the processor set, whether the determined induction variable is innermost iterator for the loops with the number of conditionals based on the conditional tree;
and in response to determining that the determined induction variable is not innermost iterator for the loop with the number of conditionals based on the conditional tree, adjusting, by the processor set, sequences with nonzero stride in the sequences with fixed stride to generate the number of sequences, wherein value for the strides of each sequence in the number of sequences is zero.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 4 is a method
Yes. Claim 11 is a machine
Yes. Claim 18 is a manufacture
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of 10, as drafted in #"determining" above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
The limitation of 11, as drafted in #adjusting above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
"a processor set"
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 5, 12, and 19 recite(s):
generating, by the processor set, the number of sequences by splitting sequences with nonzero stride in the sequences with fixed stride, wherein number of sequences for each result index is same across different slices.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 5 is a method
Yes Claim 12 is a machine
Yes. Claim 19 is a manufacture
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of "generating", as drafted in #12 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
"a processor set"
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 6 and 13 recite(s):
wherein the determining, by the processor set, an induction variable for the modified loops comprises: generating, by the processor set, the induction variable to mimic traversing of the multi-dimensional table in a one-dimensional fashion.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 6 is a method
Yes Claim 13 is a machine
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of "generating", as drafted in #13 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
"a processor set"
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 7, 14, and 20 recite(s):
wherein the number of new conditionals based on the determined induction variable and at least values and strides in the number of sequences comprises: generating, by the processor set, a number of lists for each slice in the number of slices based on uncommon values and strides in the number of sequences, and values of the determined induction variable corresponding to last terms for sequences of each slice;
generating, by the processor set, a number of new induction variables for the modified loops, wherein start values and strides for the number of new induction variables are determined based on values from the number of lists;
and generating, by the processor set, the number of new conditionals using the number of new induction variables, existing variables from the loops, values from the number of lists, and common values in the number of sequences.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 7 is a method
Yes. Claim 14 is a machine
Yes. Claim 20 is a manufacture
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of "generating", as drafted in #14-16 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
"a processor set"
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 21 recite(s):
A computer implemented method for generating modified loops for loops with a number of conditionals, the computer implemented method comprising: generating, by a processor set, a conditional tree based on the number of conditionals in the loops, wherein a value is determined by evaluating each conditional in the number of conditionals;
generating, by the processor set, a multi-dimensional table based on the values for the number of conditionals obtained from the conditional tree;
slicing, by the processor set, the multi-dimensional table to generate a number of slices using a number of slicing methods, wherein each slice in the number of slices represent at least a portion of the multi-dimensional table;
generating, by the processor set, a number of sequences by splitting values in each slice for each slicing method, wherein values and strides in the number of sequences are determined for proper execution of the modified loops;
generating, by the processor set, a number of new conditionals based on at least values and strides in the number of sequences for each slicing method;
and generating, by the processor set, the modified loops based on the number of new conditionals for each slicing method.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 21 is a method
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of "generating", as drafted in #17-18 and 20-22 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
The limitation of "slicing", as drafted in #19 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
"a computer implemented method.."
“a processor set”
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 22 recite(s):
wherein the generating, by the processor set, the number of new conditionals based on at least values and strides in the number of sequences for each slicing method comprises: generating, by the processor set, a number of lists for each slicing method based on uncommon values in the number of sequences for each slicing method;
generating, by the processor set, a number of new induction variables for the modified loops of each slicing method, wherein start values and strides for the number of new induction variables are determined based on values from the number of lists for each slicing method;
and generating, by the processor set, the number of new conditionals for each slicing method using the number of new induction variables for the modified loops of each slicing method, existing variables from the loops, values from the number of lists, and common values in the number of sequences for each slicing method.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 22 is a method
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of "generating", as drafted in #23-25 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
a processor set
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 23 recite(s):
further comprising: generating, by the processor set, a conditional tree for the modified loops for each slicing method;
performing, by the processor set, a cost analysis for the modified loops for each slicing method based on the conditional tree for the modified loops for each slicing method and the number of new induction variables for the modified loops of each slicing method;
and replacing, by the processor set, the loops with the number of conditionals using modified loops of a slicing method with lowest cost.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 23 is a method
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of "generating", as drafted in #26 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
The limitation of "performing", as drafted in #27 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
The limitation of "replacing", as drafted in #28 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
a processor set
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 24 recite(s):
The computer implemented method of claim 23, wherein the performing, by the processor set, the cost analysis for the modified loops for each slicing method based on the conditional tree for the modified loops for each slicing method and the number of new variables for the modified loops of each slicing method comprises: identifying, by the processor set, a set of modified loops with lowest number of leaves in the conditional trees;
determining, by the processor set, whether the set of modified loops comprise loops for more than one slicing method; and in response to determining that the set of modified loops does not comprise loops for more than one slicing method,
identifying, by the processor set, the set of modified loops as the modified loops of the slicing method with lowest cost.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 24 is a method
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation of “identifying”, as drafted in #29 and 31 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
The limitation of "determining", as drafted in #30 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
a processor set
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim(s) 25 recite(s):
in response to determining that the set of modified loops does comprise loops for more than one slicing method, identifying, by the processor set, a subset of modified loops with lowest number of new induction variables for a slicing method from the set of modified loops as the modified loops of the slicing method with lowest cost.
Step 1: are the claims to a process, machine, manufacture, or a composition of matter?
Yes. Claim 25 is a method
Step 2A, Prong I; Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The limitation, as drafted in #32 above, under its broadest reasonable interpretation, covers performance of the mind, but for generic computer parts. That is, other than reciting "a processor set", nothing in the claim element precludes the step from being performed by a person on paper.
Step 2A Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
Additionally, the claims recite the following additional element:
a processor set
The element that is recited in the claims are stated at a high level of generality (i.e. as a generic processor performing a generic computer function) such that it amounts no more than mere instructions to apply the exception using generic computer component. See the MPEP §§ 2106.05(f). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limitation on practicing the abstract idea(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because mere instructions to apply an exception using generic computer components cannot provide the inventive step.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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, 7-10, 14-17, and 21-22 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 20090083722 A1 (hereinafter referred to as Eichenberger) and US 20250053621 A1 (hereinafter referred to as Liu).
Regarding claim 1, Eichenberger teaches:
wherein a value is determined by evaluating each conditional in the number of conditionals (Para. [128], Eichenberger shows " the polyhedral scan module 510 extracts an iteration domain 640, access functions 650, and schedule 660 of each statement in the source code 630. The iteration domain 640 of a statement is a set of integer values taken by the multidimensional iteration i. The iteration domain 640 may be defined as a set of linear inequalities, e.g., i.gtoreq.0, M-i-1.gtoreq.0, j.gtoreq.0, N-j-i.gtoreq.0 in FIG. 6B, forming a convex polyhedron. The access functions 650 correspond to the polyhedral representation of which specific memory location is accessed for a given statement. For example, in FIG. 6B, the second statement 632 is controlled by the index variables i and j for, respectively, the outermost and the innermost loop." Examiner notes the above citation shows each statement in the source code including conditionals being given an iteration domain which is a set of values.)
generating, by the processor set, a multi-dimensional table based on the values for the number of conditionals obtained from the conditional tree (Para. [161], Eichenberger shows "the schedule of loops in a program may be represented as a structured matrix having three sub-matrices: (1) the Alpha matrix, which represents the speed at which statements are fired along a given time dimension; (2) the Beta matrix, which represents the sequential interleaving of statements along the different loop depths; and (3) the Gamma matrix, which represents the constant parametric shifting along each time dimension. The values of the Beta matrix will differ for each instance of an original statement S. The values of this Beta matrix may be read from the inner data representation of the AST in either the program statement view 820 or the program loop view 850." Examiner notes the above citation shows matrices containing values regarding statements and in the case of the beta matrix reads values from the Abstract Syntax Tree.);
determining, by the processor set, an induction variable for the modified loops (Para. [79], Eichenberger shows "As shown in FIG. 5, the polyhedral loop optimization proceeds from left to right in FIG. 5 starting with a polyhedral scan by a polyhedral scan module 510 of the original program from the compiler's IR into a polyhedral representation, referred to as the program statement view 520. In this representation, each statement in the source code is associated with a polyhedron describing its domain (how many times it iterates in each of its loop dimensions) as well as its schedule (when it is executed with respect to all other statements)." Para. [92-93], Eichenberger shows " the original code 681 is scanned through a polyhedral representation and a loop interchange transformation 683 is applied. Namely, the outer loop in the original code 681, i.e. the loop iterating over index i, is mapped to the second time dimension t2 and the inner loop in the original code 681, i.e. the loop iterating over index j, is mapped to the first time dimension t1. The resulting code is shown as element 682 in FIG. 6D. Note that in the statement S of the resulting code 682, the original index i is set to same value as t2, and the original index j is set to the same value as t1. One of ordinary skill in the art will notice that the original code 681 executes the statements in which, for a given value of i, all the values of j will be visited before visiting the next value of i. However, in the resulting code 682, the code executes the statements in a different order. Namely, for a given value of j, all the values of i will be visited before visiting the next value of j. This transformation is referred to as an interchange of the loop i and j, precisely because of this change in ordering. In FIG. 6E, the original code 691 is scanned through the polyhedral representation and a loop skewing and parallelization transformation 693 is applied. In this transformation 693, the two i and j indices are projected to a single time dimension t1=i+j. Thus, at the logical time date t1=3, the original iteration (i=1,j=2) and (i-2, j=1) are logically executed. This is illustrated by the DOALL loop in the resulting code 692. A DOALL loop is a parallel execution of a loop, where logically all the iterations can be executed in parallel.);
slicing, by the processor set, the multi-dimensional table to generate a number of slices, wherein each slice in the number of slices represents at least a portion of the multi-dimensional table (Para. [79], Eichenberger shows "The schedule may be represented as a structured matrix having three sub-matrices: (1) the Alpha matrix, which represents the speed at which statements are fired along a given time dimension; (2) the Beta matrix, which represents the sequential interleaving of statements along the different loop depths; and (3) the Gamma matrix, which represents the constant parametric shifting along each time dimension. See Girbal et al. "Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory Hierarchies, IJPP 2006, which is hereby incorporated by reference. The generation of a program statement view using a polyhedral representation is generally known in the art and thus, a detailed explanation of the mechanisms for representing a program in a program statement view using a polyhedral transformation will not be provided herein." Examiner notes the above citation shows a matrix having sub-matrices, wherein a matrix can be considered a multidimensional table and the sub-matrices are slices of the table still continuing to be a table);
generating, by the processor set, a number of sequences by splitting values in each slice, wherein values and strides in the number of sequences are determined for proper execution of the modified loops (Para. [164-165], Eichenberger shows "Thus, the mechanisms of the illustrative embodiments define a new transformation, the scatter domain stretching transformation, to apply on domain constraints at scattering construction time. For each statement S the following operations are performed. First, the loop depth Ds associated with statement S is determined. Then the Hermite Normal Form (Hnf) matrix is calculated from the Alpha scheduling matrix. The Hermite Normal Form matrix is constructed using a standard matrix transformation (or linear algebra) that separates a given matrix X into a product of two matrices Y*Z, where Y is a matrix in Hermite Normal Form and Z is a unimodular matrix. The Hermite Normal Form Y matrix is a non-negative, non-singular, lower triangle matrix such that for each row i, the maximal element is Y.sub.i,i (i.e. the diagonal element is larger than any others on that row). A unimodular matrix is a rectangle matrix whose determinant is either plus or minus one. The scattering matrix Theta is computed using Alpha, Beta, Gamma matrices, and the domain of the statement S. For each time dimension Td (from 1 to Ds) the following operations are performed. The stride factor is computed as Sf=Hnf[Td, Td]. Namely the stride factor is the diagonal element at row/column number Td in the Hermite Normal Form matrix. Upon a determination that the stride factor Sf>1 then a determination is made as to whether this stride factor Sf divides every component (i.e. time domain, and parametric dimensions) in the scattering matrix for every row that contains a non-null Td entry.);
generating, by the processor set, a number of new conditionals based on the determined induction variable and at least values and strides in the number of sequences (Para. [83], Eichenberger shows "In essence, the module 540 is designed to generate valid code, possibly with overhead due to extra bound computation, if conditional, modulo calculus in bounds and/or conditional computations. It is then the responsibility of optimizations like 550, 560, and 570 to clean up some of the introduced inefficiencies as best as possible. The resulting optimized AST is provided to a code emitter 570 which generates code from the AST in the compiler's internal representation (IR) by simply converting the internal AST and stripping it of its polyhedral information and generating an equivalent structure that is familiar and recognized by the traditional compiler." Para. [122], Eichenberger shows "The extract-kernel code generation optimization computes and extracts a fully unrollable kernel from a loop with complex bounds (min, max, floor, and ceiling). This usually results in 0+ prologues, 1 kernel and 0+ prologues and may yield code bloat if not done carefully. The if-host/if-hoist-gentle code generation optimization walks the children of the given node and finds conditions on the current loop's depth and hoists them. The if-hoist-brutal code generation optimization walks the leaf nodes, finds any condition on any depth smaller than the current loop's depth and brutally hoists everything. The substitute-modulo code generation optimization simplifies modulos aggressively without taking care of compatibility within different statements. When all statements in a loop have the same modulo substitutions, this is a powerful tool to embed the modulos into the enclosing loops' bounds. The loop-unroll code generation optimization performs a full unroll of a loop with static constant bounds difference. This code generation optimization should usually be preceded by an extract-kernel and a if-hoist-gentle code generation optimization if the bounds are complex (min, max, floor, ceiling) otherwise many inner conditionals may be generated. These are only examples of currently known code generation optimizations and not intended to be limiting in any way. Other code generation optimizations may be used in addition to, or replacement of, the listed code generation optimizations without departing from the spirit and scope of the present invention." Para. [132], Eichenberger shows " When loop optimizations/transformations such as skewing or strip-mining are applied, the generated loops exhibit complex bounds which can degrade performance or prevent further desired loop unrolling. Kernel extraction is a transformation that enforces the separation of such complex bounds in different versions of the loops. This transformation has three versions: (1) the unrollable kernel extraction detects pairs of lower/upper bounds that exhibit a static constant difference; (2) the lower bounds kernel extraction creates a list of conditionals where every lower bound is minimal exactly once. If at depth d, the scattered, separated domain exhibits t.sub.d.gtoreq.(l.sub.i).sub.i.sub.[1,k], the resulting conditionals are a list of k elements such that t.sub.d.gtoreq.(l.sub.i).sub.i.sub.[1,k]-{j}>l.sub.j; and (3) the upper bounds kernel extraction creates the same list of conditionals with the upper bounds, i.e. t.sub.d.gtoreq.(u.sub.i).sub.i.sub.[1,k]=>t.sub.d.gtoreq.(u.sub.i).sub- .i.sub.[1,k]-{1}>u.sub.j." Examiner notes the above citations show generating valid code containing conditionals that have been optimized. Even further these conditionals are generated with respect to the bounds and iterations of the loops.);
and generating, by the processor set, the modified loops based on the number of new conditionals (Para. [130-132], Eichenberger shows "FIG. 12A includes several conditional statements, i.e. the three "if" clauses in FIG. 12A, that will execute at each iteration of the outermost t1 loop, even though the condition associated with the conditional statement will evaluate to true for only one or two iterations of the entire t1 loop iteration. This represents a significant overhead, which can be removed the conditional hoisting optimization. While in general the aggressive technique can get rid of more conditional statements at the cost of more replication, one can see that in this case, the gentle approach (result shown in FIG. 12B) was sufficient to remove all conditionals. The aggressive technique (results shown in FIG. 12C) also resulted in all of the conditionals being removed, but resulted in more code than the gentle approach. In most cases, the gentle mode is enough and yields potentially much smaller code. In special cases, however, the more aggressive, or "brutal," mode is needed to perform more advanced conditional hoisting, such as in the case of loop unrolling after tiling. To see that program equivalence is preserved is rather straightforward. Conditional hoisting is actually a domain splitting on the time dimensions. Suppose I and I' are ordered instances of two statements that execute respectively at time t and t' such that t.ltoreq.t'. Two cases arise: (1) both instances belong to the same new split domain after transformation and their order is enforced by the schedule; and (2) each instance belongs to a different sub-domain, in which case the relative order is enforced by the disjunction and the subsequent ordering. Lastly, since the difference is computed with the reference node's domain, no iteration is lost. Another code generation optimization/transformation that may be applied to the program loop view 850 in FIG. 8 by the code generation optimization/parallelism detection module 860 is the kernel extraction code generation optimization/transformation. When loop optimizations/transformations such as skewing or strip-mining are applied, the generated loops exhibit complex bounds which can degrade performance or prevent further desired loop unrolling. Kernel extraction is a transformation that enforces the separation of such complex bounds in different versions of the loops. This transformation has three versions: (1) the unrollable kernel extraction detects pairs of lower/upper bounds that exhibit a static constant difference; (2) the lower bounds kernel extraction creates a list of conditionals where every lower bound is minimal exactly once. If at depth d, the scattered, separated domain exhibits t.sub.d.gtoreq.(l.sub.i).sub.i.sub.[1,k], the resulting conditionals are a list of k elements such that t.sub.d.gtoreq.(l.sub.i).sub.i.sub.[1,k]-{j}>l.sub.j; and (3) the upper bounds kernel extraction creates the same list of conditionals with the upper bounds, i.e. t.sub.d.gtoreq.(u.sub.i).sub.i.sub.[1,k]=>t.sub.d.gtoreq.(u.sub.i).sub- .i.sub.[1,k]-{1}>u.sub.j." Examiner notes the above citation shows generating loops with respect to the conditionals within the loop that have been modified).
Eichenberger does not explicitly disclose but teaches:
generating, by a processor set, a conditional tree based on the number of conditionals in the loops (Para. [18], Eichenberger shows "The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on the intermediate representation (IR), e.g., an abstract syntax tree (AST), generated by the polyhedral loop transformation optimization of the source code." Para. [23], Eichenberger shows "The program loop view of the source code may be a hierarchical ordered graph of the source code where each inner node of the graph corresponds to an iteration domain at a given depth in a loop nest structure. Each leaf node of the graph may have a list of statements that are enclosed by a loop nest corresponding to the leaf node. Each node in the graph may be associated with a domain. Each domain may be a polyhedral representation of a domain associated with statements enclosed by the node and projected to reflect a depth of the node within the graph." Para. [25], Eichenberger shows "detecting, in the program loop view of the source code, nodes containing hoistable conditional statements and marking a parent node as a boundary node for a re-entrance operation. Moreover, the method may comprise identifying for each marked boundary node of a given depth in the program loop view of the source code, all instances of a given statement and generating, in the first optimized code, a single compound statement representing all of the instances of the given statement at the given depth in the program loop view of the source code. Furthermore, the method may comprise setting a new domain for the compound statement as a union of domains over all instances of the given statement." Examiner notes the above citation shows generating an Abstract Syntax Tree which is a type of graph that contains a program within showing branches and subtrees based on program control flow including conditionals.);
However, in the analogous art of tokenization protocol for open-source software, Liu teaches:
generating, by a processor set, a conditional tree based on the number of conditionals in the loops (Para. [195], Liu shows "It will be appreciated that each of abstract syntax trees t(s), t′(s′) provides a tree-like representation of the code, where structural elements such as code sequences, conditionals (e.g., “if” statements), and loops (e.g., “while” loops, “for” loops, etc.) are laid out structurally. The tree analyser 18 can inspect the trees t(s) and t′(s′) from before and after the commit c to determine what changes, if any, the commit c makes to the syntactic structure of the source code." Examiner notes within a tree, any sub-tree with a root node of a loop and conditionals within the loop would constitute a conditional tree.)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Liu into the teachings of Eichenberger to implement "generating, by a processor set, a conditional tree based on the number of conditionals in the loops. The modification would have been obvious as one of ordinary skill in the art would be motivated to lay out the .
Regarding claim 2, Eichenberger as modified teaches claim 1 as cited above and teaches:
wherein each slice from the number of slices comprises a set of values obtained by varying the determined induction variable while fixing other existing induction variables in the loops with the number of conditionals. (Para. [86-88], Eichenberger shows "FIGS. 6A-6F are diagrams illustrating the program statement view and examples of the loop optimizer 530 transformations that may be performed on the program statement view. FIG. 6A provides some general notations for explaining the program statement view and these transformations. As shown in FIG. 6A, a statement S1 in source code 610 may be represented as an array-based inequality 620 defining the iteration domain of the statement S1. That is, each statement control can be captured through parameterized affine inequalities: Ax.gtoreq.c where A is a n times m element matrix of integer numbers, x is a m element vector representing each of the iteration variables, and where c is a n element vector of integer numbers or symbolic parameters. A maximal set of such consecutive statements is referred to as a static control part (SCOP) in the polyhedral loop transformation literature. For each statement, an affine function .theta.(x)=Tx+d (where T is a n' times m element matrix of integer numbers, x is a m element vector representing each of the iteration variables, and where d is a n' element vector of integer numbers or symbolic parameters) assigns logical dates, e.g., time steps starting to zero and monotonically increasing, to iterations of Ax.gtoreq.c. As shown in FIG. 6B, the polyhedral scan module 510 extracts an iteration domain 640, access functions 650, and schedule 660 of each statement in the source code 630. The iteration domain 640 of a statement is a set of integer values taken by the multidimensional iteration i. For example, in FIG. 6B, the second statement 632 is controlled by the index variables i and j for, respectively, the outermost and the innermost loop. An access function for memory reference "Z[i]" in statement 632 will indicate, to the internal representation, which specific memory location will be written into when computing the data associated with that statement for a given instance of i and j. The access function is a matrix with one row per dimension of the array (Z[i] is a one dimensional array) and one column for each of the index variables (i and j here), parameters (M and N here) plus a constant integer. Thus the access function for Z[i] is [1 0 0 0 0] as shown in 652, as it is only a function of the index variable i." Para. [124-125], Eichenberger shows "All code generation optimizations/transformations share the same template implementation based on visitors. Visitors are instantiated at 3 different points in the algorithm. First, a visitor is used to perform an outermost scan of the nodes in the AST of the program loop view. Each code generation optimization scans the nodes that have been marked by the filtering pass. For each marked node N, the code generation optimization applies its core function which determines if the node's domain is modified and returns the list of new domains to replace the obsolete ones. This list is sorted with respect to the current time dimension under the parent polyhedral context with the same algorithm proposed by Quillere, referenced above. The core function is the second point where an inner visitor is instantiated. Each new domain in the list then generates a new node N' and its corresponding subtree, which is a copy of the subtree rooted at N and simplified in the context of N'. Once the new subtree list is attached in place of the original node N, the propagation function is called along each path to every new leaf." Examiner notes the above citations show using slices of the iteration domain to determine iteration variables. The iteration domain is a matrix with 2 dimensions as shown in Fig. 6C. Also shown is node specific integration domains being changed as previous nodes located in the AST, representing statements including conditionals, are updated with new domains. This shows varying integration variables in the domain that are fixed as loops are changed according to statement modifications done by loop optimization.)
Regarding claim 3, Eichenberger teaches claim 1 as cited above and teaches:
wherein the generating, by the processor set, a number of sequences by splitting values in each slice comprises: generating, by the processor set, sequences with fixed stride by splitting values in each slice, wherein each sequence in the sequences with fixed stride corresponds to a number of values for a result index in each slice (Para. [165], Eichenberger shows "The scattering matrix Theta is computed using Alpha, Beta, Gamma matrices, and the domain of the statement S. For each time dimension Td (from 1 to Ds) the following operations are performed. The stride factor is computed as Sf=Hnf[Td, Td]. Namely the stride factor is the diagonal element at row/column number Td in the Hermite Normal Form matrix. Upon a determination that the stride factor Sf>1 then a determination is made as to whether this stride factor Sf divides every component (i.e. time domain, and parametric dimensions) in the scattering matrix for every row that contains a non-null Td entry.").
Regarding claim 7, Eichenberger as modified teach claim 1 as cited above and teaches:
wherein the number of new conditionals based on the determined induction variable and at least values and strides in the number of sequences comprises: generating, by the processor set, a number of lists for each slice in the number of slices based on uncommon values and strides in the number of sequences, and values of the determined induction variable corresponding to last terms for sequences of each slice; (Para. [87-90], Eichenberger shows "the polyhedral scan module 510 extracts an iteration domain 640, access functions 650, and schedule 660 of each statement in the source code 630. The iteration domain 640 of a statement is a set of integer values taken by the multidimensional iteration i. The iteration domain 640 may be defined as a set of linear inequalities, e.g., i.gtoreq.0, M-i-1.gtoreq.0, j.gtoreq.0, N-j-i.gtoreq.0 in FIG. 6B, forming a convex polyhedron. The access functions 650 correspond to the polyhedral representation of which specific memory location is accessed for a given statement. For example, in FIG. 6B, the second statement 632 is controlled by the index variables i and j for, respectively, the outermost and the innermost loop. An access function for memory reference "Z[i]" in statement 632 will indicate, to the internal representation, which specific memory location will be written into when computing the data associated with that statement for a given instance of i and j. The access function is a matrix with one row per dimension of the array (Z[i] is a one dimensional array) and one column for each of the index variables (i and j here), parameters (M and N here) plus a constant integer. Thus the access function for Z[i] is [1 0 0 0 0] as shown in 652, as it is only a function of the index variable i. For the "a[i][j]" reference, the access function 654 is a two dimensional array and, as a result, the access function 654 is a 2.times.5 element matrix. The first row corresponds to the access function for the first dimension of the array A, solely a function of index variable i here. The second row corresponds to the access function for the second dimension of the array A, solely a function of index variable j here. For Y[j], the access function 656 is again a one dimensional array that is solely a function of the index variable j. The schedule is a linear function assigned to a statement that precisely determines a logical timestamp for the execution of each instance of a statement. These logical timestamps express a partial order between instances of statements. As with the domain 640 and the access functions 650, the schedule 660 is a linear function of the domain iterators, e.g., i and j, and global parameters, M and N. The extraction of iteration domain 640, access functions 650, and schedule 660 is generally known in the art and thus, a more detailed explanation is not provided herein. Having extracted the iteration domain 640, access functions 650, and schedule 660, to generate a program statement view 520 of the source code, the loop optimizer 530 may perform transformations on the schedule to achieve better parallelism/locality. FIGS. 6C-6F illustrate various types of transformations that may be performed on the program statement view 520." Examiner notes the citation above shows extracting domains, access functions and schedules from source code. Every row and column from the extracted matrices (slice) can be considered as a number of lists. The functions, domain, and schedule contain values related to stride and induction variables wherein the last value in the row as well as other rows are used in determining the induction variable value.);
generating, by the processor set, a number of new induction variables for the modified loops, wherein start values and strides for the number of new induction variables are determined based on values from the number of lists; (Fig. 6D-E; Para. [92], Eichenberger shows "In FIG. 6D, the original code 681 is scanned through a polyhedral representation and a loop interchange transformation 683 is applied. Namely, the outer loop in the original code 681, i.e. the loop iterating over index i, is mapped to the second time dimension t2 and the inner loop in the original code 681, i.e. the loop iterating over index j, is mapped to the first time dimension t1. The resulting code is shown as element 682 in FIG. 6D. Note that in the statement S of the resulting code 682, the original index i is set to same value as t2, and the original index j is set to the same value as t1. One of ordinary skill in the art will notice that the original code 681 executes the statements in which, for a given value of i, all the values of j will be visited before visiting the next value of i. However, in the resulting code 682, the code executes the statements in a different order. Namely, for a given value of j, all the values of i will be visited before visiting the next value of j. This transformation is referred to as an interchange of the loop i and j, precisely because of this change in ordering." Examiner notes in Fig. 6D it shows new induction variables are declared in element 682, t1 and t2. The values of these are seen to be calculated using the domain extracted from the original code to determine stride and the start value of the induction variables.);
and generating, by the processor set, the number of new conditionals using the number of new induction variables, existing variables from the loops, values from the number of lists, and common values in the number of sequences. (Fig. 12A-C; Para. [122], Eichenberger shows "The if-host/if-hoist-gentle code generation optimization walks the children of the given node and finds conditions on the current loop's depth and hoists them. The if-hoist-brutal code generation optimization walks the leaf nodes, finds any condition on any depth smaller than the current loop's depth and brutally hoists everything. The substitute-modulo code generation optimization simplifies modulos aggressively without taking care of compatibility within different statements. When all statements in a loop have the same modulo substitutions, this is a powerful tool to embed the modulos into the enclosing loops' bounds. The loop-unroll code generation optimization performs a full unroll of a loop with static constant bounds difference. This code generation optimization should usually be preceded by an extract-kernel and a if-hoist-gentle code generation optimization if the bounds are complex (min, max, floor, ceiling) otherwise many inner conditionals may be generated." Para. [128], Eichenberger shows "Such constraints do not concern the time iterators at depth d'>d and are thus, affine guards that can be hoisted. In the aggressive mode, the visitor traverses only the leaf nodes under node N and performs a polyhedron projection of each separate statements' domain on the vector space (t.sub.1, . . . , t.sub.d, N). A subsequent simplification in the context of the parent node yields the new conditionals." Para. [132], Eichenberger shows " Kernel extraction is a transformation that enforces the separation of such complex bounds in different versions of the loops. This transformation has three versions: (1) the unrollable kernel extraction detects pairs of lower/upper bounds that exhibit a static constant difference; (2) the lower bounds kernel extraction creates a list of conditionals where every lower bound is minimal exactly once. If at depth d, the scattered, separated domain exhibits t.sub.d.gtoreq.(l.sub.i).sub.i.sub.[1,k], the resulting conditionals are a list of k elements such that t.sub.d.gtoreq.(l.sub.i).sub.i.sub.[1,k]-{j}>l.sub.j; and (3) the upper bounds kernel extraction creates the same list of conditionals with the upper bounds, i.e. t.sub.d.gtoreq.(u.sub.i).sub.i.sub.[1,k]=>t.sub.d.gtoreq.(u.sub.i).sub- .i.sub.[1,k]-{1}>u.sub.j." Examiner notes the above citations show generation of conditionals using values from both sequences and lists. As shown in Fig. 12B-C, although the original conditions within the loop were removed for optimizations the conditionals within the loop header are determined using new induction variables and as shown are generated from existing variables (former induction variables), values from number lists (bounds of the new loops), and values in the sequences (New induction variables)).
With regards to claim 8, it is a machine claim having similar limitations as cited in claim 1 above. Thus, claim 8 is also rejected under the same rationale as cited in the rejection of claim 1 above.
With regards to claim 15, it is a computer program product claim having similar limitations as cited in claim 1 above. Thus, claim 15 is also rejected under the same rationale as cited in the rejection of claim 1 above.
With regards to claim 21, it is a method claim having similar limitations as cited in claim 1 above. Thus, claim 21 is also rejected under the same rationale as cited in the rejection of claim 1 above.
With regards to claim 9, it is a machine claim having similar limitations as cited in claim 2 above. Thus, claim 9 is also rejected under the same rationale as cited in the rejection of claim 2 above.
With regards to claim 16, it is a computer program product claim having similar limitations as cited in claim 2 above. Thus, claim 16 is also rejected under the same rationale as cited in the rejection of claim 2 above.
With regards to claim 10, it is a machine claim having similar limitations as cited in claim 3 above. Thus, claim 10 is also rejected under the same rationale as cited in the rejection of claim 3 above.
With regards to claim 17, it is a computer program product claim having similar limitations as cited in claim 3 above. Thus, claim 17 is also rejected under the same rationale as cited in the rejection of claim 3 above.
With regards to claim 14, it is a machine claim having similar limitations as cited in claim 7 above. Thus, claim 14 is also rejected under the same rationale as cited in the rejection of claim 7 above.
With regards to claim 20, it is a computer program product claim having similar limitations as cited in claim 7 above. Thus, claim 20 is also rejected under the same rationale as cited in the rejection of claim 7 above.
With regards to claim 22, it is a method claim having similar limitations as cited in claim 7 above. Thus, claim 22 is also rejected under the same rationale as cited in the rejection of claim 7 above.
Claim(s) 4, 11, and 18 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 20090083722 A1 (hereinafter referred to as Eichenberger) and US 20250053621 A1 (hereinafter referred to as Liu) in further view of US 20100199257 A1 (hereinafter referred to as Biggerstaff).
Regarding claim 4, Eichenberger as modified teaches claim 3 as cited above and teaches:
further comprising: determining, by the processor set, whether the determined induction variable is innermost iterator for the loops with the number of conditionals based on the conditional tree (Para. [87], Eichenberger shows "The iteration domain 640 may be defined as a set of linear inequalities, e.g., i.gtoreq.0, M-i-1.gtoreq.0, j.gtoreq.0, N-j-i.gtoreq.0 in FIG. 6B, forming a convex polyhedron. The access functions 650 correspond to the polyhedral representation of which specific memory location is accessed for a given statement. For example, in FIG. 6B, the second statement 632 is controlled by the index variables i and j for, respectively, the outermost and the innermost loop. An access function for memory reference "Z[i]" in statement 632 will indicate, to the internal representation, which specific memory location will be written into when computing the data associated with that statement for a given instance of i and j. The access function is a matrix with one row per dimension of the array (Z[i] is a one dimensional array) and one column for each of the index variables (i and j here), parameters (M and N here) plus a constant integer. Thus the access function for Z[i] is [1 0 0 0 0] as shown in 652, as it is only a function of the index variable i." Para. [Para. [97], Eichenberger shows "The resulting AST is hierarchical, with the top node representing an outermost loop. This node corresponds to a single interval parallel to the i-axis after projecting away the j-dimension. Since, in the depicted example, all 3 statements have the same interval i=1 . . . n in this projected one-dimensional space, all 3 statements belong to this single node. Thus, there are 4 nodes 720-750, one for each distinct area in FIG. 7B. A domain is associated with each node. Domains are shown next to each node 720-750 in FIG. 7C." Examiner notes any node that is a leaf node in this context is determined to be an inner most loop and the iteration domain containing the induction variable would reflect this.);
and in response to determining that the determined induction variable is not innermost iterator for the loop with the number of conditionals based on the conditional tree, adjusting, by the processor set, sequences with nonzero stride in the sequences with fixed stride to generate the number of sequences (Para. [165], Eichenberger shows "The scattering matrix Theta is computed using Alpha, Beta, Gamma matrices, and the domain of the statement S. For each time dimension Td (from 1 to Ds) the following operations are performed. The stride factor is computed as Sf=Hnf[Td, Td]. Namely the stride factor is the diagonal element at row/column number Td in the Hermite Normal Form matrix. Upon a determination that the stride factor Sf>1 then a determination is made as to whether this stride factor Sf divides every component (i.e. time domain, and parametric dimensions) in the scattering matrix for every row that contains a non-null Td entry." Examiner notes the above citation shows for every stride greater than 1, the sequences within the calculated matrix are divided by the stride to generate new values.),
Eichenberger does not disclose:
wherein value for the strides of each sequence in the number of sequences is zero.
However, in the analogous art of automated partitioning of a computation, Biggerstaff teaches:
wherein value for the strides of each sequence in the number of sequences is zero. ([Table 5; Pg. 62], Biggerstaff shows "ranges and strides loop control variables and (e.g., i2, j3) D, for (e.g., i2 ranging unpartitioned dimensions. and transform example. from 0 to (M-1))" Examiner notes the above citation shows stride value being 0.)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Biggerstaff into the teachings of Eichenberger as modified to implement "wherein value for the strides of each sequence in the number of sequences is zero. The modification would have been obvious as one of ordinary skill in the art would be motivated as shared stride and ranges allow for loop optimization by combining loops (Para. [505]).
With regards to claim 11, it is a machine claim having similar limitations as cited in claim 4 above. Thus, claim 11 is also rejected under the same rationale as cited in the rejection of claim 4 above.
With regards to claim 18, it is a computer program product claim having similar limitations as cited in claim 4 above. Thus, claim 18 is also rejected under the same rationale as cited in the rejection of claim 4 above.
Claim(s) 5-6, 12-13 and 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 20090083722 A1 (hereinafter referred to as Eichenberger) and US 20250053621 A1 (hereinafter referred to as Liu) in further view of US 20260186750 A1 (hereinafter referred to as Yang).
Regarding claim 5, Eichenberger as modified teaches claim 3 as cited above
generating, by the processor set, the number of sequences by splitting sequences with nonzero stride in the sequences with fixed stride, wherein number of sequences for each result index is same across different slices.
However, in the analogous art of code vectorization, Yang teaches:
generating, by the processor set, the number of sequences by splitting sequences with nonzero stride in the sequences with fixed stride, wherein number of sequences for each result index is same across different slices (Para. [76-77], Yang shows "An innermost loop is the k loop. A parent loop of the k loop is the j loop. A parent loop of the j loop is an outermost loop, namely, the i loop. Lengths of the three levels of loops are respectively p, n, and m. Based on the foregoing loop structure, an index of memory access by computing in the loop is as follows: index=k+j×p+i×n×p. It may be determined that for the memory access by the computing in the loop, a memory access stride of the innermost loop is 1, a memory access stride of the second-level loop is p, and a memory access stride of the third-level loop is n×p. [0077] S302: Determine, based on the attribute information, a hardware logic level corresponding to each level of target loop code in the multidimensional loop code. Each level of target loop code is a piece of single-level loop code to be vectorized in the plurality of pieces of single-level loop code. The plurality of hardware logic levels indicate a multi-level memory access rule of a vector computing unit. Each hardware logic level corresponds to a rule for one level of memory access in the multi-level memory access." Para. [84], Yang shows "The preset interface may be vectorhint( ). A quantity of parameters in vectorhint indicates a quantity of hardware logic levels. An order in which the parameters are arranged indicates a level relationship between a plurality of hardware logic levels. For example, in vectorhint(0, 1, 1), there are three parameters, indicating that the vector computing unit supports a three-level loop representation, that is, includes three hardware logic levels. The parameters are arranged from left to right, indicating that a level relationship between the three hardware logic levels is sequentially from inner to outer. In an optional example, that the parameters are arranged from left to right may indicate that the level relationship between the three hardware logic levels is sequentially from outer to inner. Values of the parameters represent different pieces of single-level loop code in the multidimensional loop code. For example, in vectorhint(0, 1, 1), 0 represents innermost, that is, first-level, single-level loop code. The parameter values increment toward outer levels: 1 represents second-level single-level loop code from inner to outer. 2 represents third-level single-level loop code from inner to outer." Examiner notes the above citation shows a fixed stride, the innermost loop, and nonzero strides, the middle and outer loop, vectorized together wherein they are being performed in parallel at once so the index between all three is the same.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Eichenberger as modified into the teachings of Yang to implement "generating, by the processor set, the number of sequences by splitting sequences with nonzero stride in the sequences with fixed stride, wherein number of sequences for each result index is same across different slices. The modification would have been obvious as one of ordinary skill in the art would be motivated to reduce loops with multiple dimensions in order to improve computing efficiency (Yang, Para. [6]).
Regarding claim 6, Eichenberger as modified teaches claim 1 as cited above, but does not disclose:
wherein the determining, by the processor set, an induction variable for the modified loops comprises: generating, by the processor set, the induction variable to mimic traversing of the multi-dimensional table in a one-dimensional fashion.
However, in the analogous art of code vectorization, Yang teaches:
wherein the determining, by the processor set, an induction variable for the modified loops comprises: generating, by the processor set, the induction variable to mimic traversing of the multi-dimensional table in a one-dimensional fashion (Para. [50-51], Yang shows "In service code, loop code used to implement loop logic may be one-dimensional or multidimensional. For example, one-dimensional loop code, namely, single-level loop code, may be code shown in Table 1-1.[TABLE-US-00001 TABLE 1-1 Example of one-dimensional loop code for(i = 0; i < n; ++i ) {...} ] When memory addresses accessed by computing in loop code are contiguous, that is, memory access is contiguous, the foregoing one-dimensional loop code can be directly split based on a length upper limit (for example, LIMIT) of a vector computing unit. After the splitting, each segment of loop code satisfies the length upper limit of the vector computing unit in hardware, except for the last segment, namely, a tail block, which may be shorter than the length upper limit. For example, in Table 1-1, the one-dimensional loop code with a length of n may be split as follows: n=x×LIMIT+y. x×LIMIT indicates a loop whose length is x. y is a tail block. Each iteration is to compute data with a length of LIMIT in the loop. The computing of the LIMIT-length data may be converted into a vector instruction, that is, vectorized. In this way, a loop upper bound n can be a dynamic variable. Even if the length upper limit of the vector computing unit in the hardware is exceeded, the loop code can still be processed by the vector computing unit. Based on this, for multidimensional loop code, when memory access by computing in the multidimensional loop code is contiguous, the multidimensional loop code may be collapsed into one-dimensional loop code, and then vectorization is implemented through the foregoing one-dimensional loop code processing method." Examiner notes the above citation shows creation of a single loop where an induction variable is initiated capable of traversing a multidimensional table in a linear fashion. The above citation shows collapsing multidimensional loops to traverse in a one-dimensional fashion as well.).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Yang into the teachings of Eichenberger as modified to implement ". The modification would have been obvious as one of ordinary skill in the art would be motivated to reduce loops with multiple dimensions.
With regards to claim 12, it is a machine claim having similar limitations as cited in claim 5 above. Thus, claim 12 is also rejected under the same rationale as cited in the rejection of claim 5 above.
With regards to claim 19, it is a computer program product claim having similar limitations as cited in claim 5 above. Thus, claim 19 is also rejected under the same rationale as cited in the rejection of claim 5 above.
With regards to claim 13, it is a machine claim having similar limitations as cited in claim 6 above. Thus, claim 13 is also rejected under the same rationale as cited in the rejection of claim 6 above.
Claim(s) 23-25 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 20090083722 A1 (hereinafter referred to as Eichenberger) and US 20250053621 A1 (hereinafter referred to as Liu) in further view of US 20250199809 A1 (hereinafter referred to as Ogurunti).
Regarding claim 23, Eichenberger as modified teaches claim 22 as cited above and teaches:
generating, by the processor set, a conditional tree for the modified loops for each slicing method (Para. [19], Eichenberger shows "Such code generation transformations may induce statement splitting or aggregation, may modify domain and schedule components, and the like. However, they do so in a transparent manner ensuring strict equivalence of the relative orders induced by the new schedules for all instances of all statements. This strict equivalence involves program equivalence and schedule equivalence, i.e. only relative execution order of all instances of statements is required and thus, is ensured via strict equivalence. Thus, the AST generated by the polyhedral loop transformation optimizations on the program statement view will be equivalent to the new AST generated by the code generation optimizations applied to this AST from a program and schedule equivalence standpoint." Examiner notes the above citation shows generating a new tree for every optimization of the optimization methods that are listed within the reference when applied. As many optimization methods include splitting/fission/unrolling of loops this can be seen as a slicing method.);
performing, by the processor set, a cost analysis for the modified loops for each slicing method based on the conditional tree for the modified loops for each slicing method and the number of new induction variables for the modified loops of each slicing method (Para. [115-116], Eichenberger shows "For example, code generation optimizations such as simplification and unstretching, if hoisting, substitute modulo, loop unrolling, etc. may be applied to the program loop view to obtain lower control overhead of the code. The program loop view may then be rescanned and converted back to a program statement view via the reentrance path after having undergone code generation optimizations by the. The result of the reentrance path is a program statement view of the code generation optimized program loop view that may be operated upon to provide even further optimization through an iterative process. The optimizations that may be performed on the program loop view of the program, i.e. the "code generation optimizations," may be applied by code generation optimization/parallel detection module 860 in FIG. 8 to the program loop view 850 of the program. These code generation optimizations are performed on the polyhedral abstract syntax tree (AST), or the program loop view, and generate a new polyhedral AST, i.e. a new program loop view 850 for re-entrance to the program statement view 820 and/or emission back to the compiler 805. The code generation optimizations represent a set of transformations that are performed in an iterative, modular, and flexible manner to help generate the code with the least impeding control overhead as possible." Examiner notes the above citation shows performing an analysis on the overhead of a program after optimization in order to see which method of optimization (loop modification technique) works best.);
and replacing, by the processor set, the loops with the number of conditionals using modified loops (Para. [115-116], Eichenberger shows "For example, code generation optimizations such as simplification and unstretching, if hoisting, substitute modulo, loop unrolling, etc. may be applied to the program loop view to obtain lower control overhead of the code. The program loop view may then be rescanned and converted back to a program statement view via the reentrance path after having undergone code generation optimizations by the. The result of the reentrance path is a program statement view of the code generation optimized program loop view that may be operated upon to provide even further optimization through an iterative process. The optimizations that may be performed on the program loop view of the program, i.e. the "code generation optimizations," may be applied by code generation optimization/parallel detection module 860 in FIG. 8 to the program loop view 850 of the program. These code generation optimizations are performed on the polyhedral abstract syntax tree (AST), or the program loop view, and generate a new polyhedral AST, i.e. a new program loop view 850 for re-entrance to the program statement view 820 and/or emission back to the compiler 805. The code generation optimizations represent a set of transformations that are performed in an iterative, modular, and flexible manner to help generate the code with the least impeding control overhead as possible." Examiner notes the above citation shows implementing the optimization that has the least overhead into the program.).
Eichenberger shows does not disclose:
replacing, by the processor set, the loops with the number of conditionals using a slicing method with lowest cost
However, in the analogous art of multi-thread processing recommendation, Ogurunti teaches:
replacing, by the processor set, the loops with the number of conditionals using a slicing method with lowest cost (Para. [29], Oruganti shows "If the loop is configured to execute 20,000 times based on the content in the multi-page document, the system may determine that the modification of the static source code to allow for parallel multi-thread processing may result in improved run-time performance of 50% or more, depending on the number of threads implemented and the number of threads that may be executed in parallel. The system may generate a notification for a user to confirm or reject the recommended modification." Examiner notes the above citation shows modifying code in response to a more optimal option for processing loops being show)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate the teachings of Ogurunti into the teachings of Eichenberger to implement ". The modification would have been obvious as one of ordinary skill in the art would be motivated to improve run-time performance by 50% or more depending on the method of improvement.
Regarding claim 24, Eichenberger as modified teaches claim 23 as cited above and teaches:
wherein the performing, by the processor set, the cost analysis for the modified loops for each slicing method based on the conditional tree for the modified loops for each slicing method and the number of new variables for the modified loops of each slicing method comprises: identifying, by the processor set, a set of modified loops with lowest number of leaves in the conditional trees (Para. [115-116], Eichenberger shows "For example, code generation optimizations such as simplification and unstretching, if hoisting, substitute modulo, loop unrolling, etc. may be applied to the program loop view to obtain lower control overhead of the code. The program loop view may then be rescanned and converted back to a program statement view via the reentrance path after having undergone code generation optimizations by the. The result of the reentrance path is a program statement view of the code generation optimized program loop view that may be operated upon to provide even further optimization through an iterative process. The optimizations that may be performed on the program loop view of the program, i.e. the "code generation optimizations," may be applied by code generation optimization/parallel detection module 860 in FIG. 8 to the program loop view 850 of the program. These code generation optimizations are performed on the polyhedral abstract syntax tree (AST), or the program loop view, and generate a new polyhedral AST, i.e. a new program loop view 850 for re-entrance to the program statement view 820 and/or emission back to the compiler 805. The code generation optimizations represent a set of transformations that are performed in an iterative, modular, and flexible manner to help generate the code with the least impeding control overhead as possible." Para. [118], Eichenberger shows "each code generation optimization or transformation executed by the code generation optimization/parallelism detection module 860 takes two arguments: (1) a list of nodes in the program loop view referred to by prefix vectors in the program loop view of the program; and (2) a propagation mode that can be, but is not limited to, "any" (all the nodes in the AST are visited), "prefix" (all the children of the given node are visited), or "exact" (only the specified node is visited). The list of nodes, i.e. the prefix vector list, is made up of prefix vectors for the nodes that are to be optimized by the particular code generation optimization selected. The nodes of the AST of the program loop view, e.g., the nodes 720-750 in FIG. 7C, may be characterized as a vector of numbers which indicate its path from the root (top-most) node. This vector of numbers is referred to as the prefix vector for the node." Examiner notes the above citation shows generating a new AST for each optimization and determining which nodes are eligible for optimization within the tree. A tree with less nodes would have less need for optimization and less overhead.);
determining, by the processor set, whether the set of modified loops comprise loops for more than one slicing method (Para. [115], Eichenberger shows "the program loop view of the source code includes separate representations for each statement, as well as the kernel, upon which code generation optimizations may be applied by the code generation optimizer/parallel detection module 860. For example, code generation optimizations such as simplification and unstretching, if hoisting, substitute modulo, loop unrolling, etc. may be applied to the program loop view to obtain lower control overhead of the code. The program loop view may then be rescanned and converted back to a program statement view via the reentrance path after having undergone code generation optimizations by the. The result of the reentrance path is a program statement view of the code generation optimized program loop view that may be operated upon to provide even further optimization through an iterative process." Examiner notes the above citation shows iteratively using optimization methods (Methods including unrolling simplification and other methods mentioned in the reference that require splitting of loops requiring slicing methods) to continuously optimize program overhead in loops.);
and in response to determining that the set of modified loops does not comprise loops for more than one slicing method, identifying, by the processor set, the set of modified loops as the modified loops of the slicing method with lowest cost (Para. [115], Eichenberger shows "the program loop view of the source code includes separate representations for each statement, as well as the kernel, upon which code generation optimizations may be applied by the code generation optimizer/parallel detection module 860. For example, code generation optimizations such as simplification and unstretching, if hoisting, substitute modulo, loop unrolling, etc. may be applied to the program loop view to obtain lower control overhead of the code. The program loop view may then be rescanned and converted back to a program statement view via the reentrance path after having undergone code generation optimizations by the. The result of the reentrance path is a program statement view of the code generation optimized program loop view that may be operated upon to provide even further optimization through an iterative process." Examiner notes the above citation shows iteratively using optimization methods (Methods including unrolling simplification and other methods mentioned in the reference that require splitting of loops requiring slicing methods) the option to apply multiple optimization methods may not happen resulting in only one slicing method being applied.).
Regarding claim 25, Eichenberger as modified teaches claim 24 as cited above and teaches:
further comprising: in response to determining that the set of modified loops does comprise loops for more than one slicing method, identifying, by the processor set, a subset of modified loops with lowest number of new induction variables for a slicing method from the set of modified loops as the modified loops of the slicing method with lowest cost (Para. [115], Eichenberger shows "the program loop view of the source code includes separate representations for each statement, as well as the kernel, upon which code generation optimizations may be applied by the code generation optimizer/parallel detection module 860. For example, code generation optimizations such as simplification and unstretching, if hoisting, substitute modulo, loop unrolling, etc. may be applied to the program loop view to obtain lower control overhead of the code. The program loop view may then be rescanned and converted back to a program statement view via the reentrance path after having undergone code generation optimizations by the. The result of the reentrance path is a program statement view of the code generation optimized program loop view that may be operated upon to provide even further optimization through an iterative process." Fig. 6E; Para. [93], Eichenberger shows "In FIG. 6E, the original code 691 is scanned through the polyhedral representation and a loop skewing and parallelization transformation 693 is applied. In this transformation 693, the two i and j indices are projected to a single time dimension t1=i+j. Thus, at the logical time date t1=3, the original iteration (i=1,j=2) and (i-2, j=1) are logically executed. This is illustrated by the DOALL loop in the resulting code 692. A DOALL loop is a parallel execution of a loop, where logically all the iterations can be executed in parallel." Examiner notes the above citations shows an optimization method where the nested loop is condensed down to a linear time reducing the induction variables needed. Additionally noted that the optimizations are shown to be iteratively applied so this optimization method can be applied iteratively after other optimizations have been previously implemented thereby reducing the amount of inductions variables available in the modified loops.).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
US 20210208889 A1 – This prior art teaches optimizing nested loops
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ZEERICK A MALIK whose telephone number is (571)272-8110. The examiner can normally be reached Mon-Thurs, 7-5.
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, Chat Do can be reached at (571) 272-3721. 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.
/Z.A.M./ Examiner, Art Unit 2193
/Chat C Do/ Supervisory Patent Examiner, Art Unit 2193
Prosecution Insights