DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Objections
Claim 12 objected to because of the following informalities: the word “perform” in “perform perform the recursive procedure with arguments F and V.” appears to be written twice instead of once. 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-18 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.
Claim 1 recites the limitation "the number of memory items in the second set" and “the number of distinct variables in the first set” in “wherein the number of memory items in the second set is smaller than the number of distinct variables in the first set, and the number of memory items in the second set is limited by a memory characteristic of the processor”. There is insufficient antecedent basis for this limitation in the claim as the terms "the number of memory items in the second set" and “the number of distinct variables in the first set” are not described earlier in the claim.
Claim 1 additionally recites the limitation "having an interval of the lowest to the highest number of the nodes" in “identifying all loops represented in the graph, each loop having a set of nodes that are linked as part of a cycle by directed links of the graph, and having an interval of the lowest to the highest number of the nodes in the set of nodes in each loop.” There is insufficient antecedent basis for this limitation in the claim as the terms “the lowest” and “the highest” [number of the nodes] are not described earlier in the claim.
Claim 1 additionally recites the limitation "an interval from the lowest numbered node to the highest numbered node" in “initializing a live interval for the first variable as an interval from the lowest numbered node to the highest numbered node in the first subset of nodes” and the limitation “the lowest numbered node of the first loop to the highest numbered node of the first loop” in “determining an interval of the first loop as the interval from the lowest numbered node of the first loop to the highest numbered node of the first loop.” There is insufficient antecedent basis for this limitation in the claim as the terms “the lowest numbered node” and “the highest numbered node” are not described earlier in the claim.
Claim 1 additionally recites the limitation "the full interval of nodes of the first loop" in “expanding the live interval of the first variable to include the full interval of nodes of the first loop”. There is insufficient antecedent basis for this limitation in the claim as the term “the full interval of nodes of the first loop” is not described earlier in the claim.
With regards to Claims 17 and 18, the method of Claim 1 performs the same steps as the manufacture and machine of Claims 17 and 18 respectively, and Claims 17 and 18 are therefore rejected using the same rationale set forth above in the rejection of Claim 1.
With regards to claims 2-18, the method of claims 2-18 are dependent on claim 1 and do not remedy the deficiencies described above. Claims 2-18 are therefore rejected using the same rationale set forth above in the rejection of claim 1.
The term “at least some of the distinct storage items” in claim 6 is a relative term which renders the claim indefinite. The term “at least some of the distinct storage items” 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.
Claim 7 recites the limitation “the number of memory items in the second set" in “wherein the number of memory items in the second set exceeds 1023 memory items”. There is insufficient antecedent basis for this limitation in the claim as the term “the number of memory items in the second set” is not described earlier in the claim or in claim 1.
Claim 8 recites the limitation “the number of memory items in the second set" in “wherein the number of memory items in the second set exceeds 16383 memory items”. There is insufficient antecedent basis for this limitation in the claim as the term “the number of memory items in the second set” is not described earlier in the claim or in claims 1 or 7.
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-18 are rejected under 35 U.S.C. 101 because the claimed invention is directed to (an) abstract idea(s) without significantly more.
Claims 1, 17 and 18 recite:
A method for executing a program specification on a processor, including
allocating a first set of distinct variables in a first representation of the program specification to a second set of memory items accessible by the processor, wherein the number of memory items in the second set is smaller than the number of distinct variables in the first set, and the number of memory items in the second set is limited by a memory characteristic of the processor, and wherein the first representation of the program specification comprises a graph in which nodes of the graph specify instructions referencing the variables, and directed links coupling nodes of the graph represent allowable paths of control flow during execution of the program specification, the method comprising:
determining an enumerated ordering of the nodes of the graph representation, such that each node has a unique number;
identifying all loops represented in the graph, each loop having a set of nodes that are linked as part of a cycle by directed links of the graph, and having an interval of the lowest to the highest number of the nodes in the set of nodes in each loop;
determining a live interval for each distinct variable in the first representation of the program specification;
wherein determining a live interval for a first variable of the distinct variables comprises: determining a first subset of nodes in the graph of nodes that specify an instructions referencing the first variable,
determining a second subset of nodes in which the instruction specified by said nodes fully assign the first variable, and
determining a third subset of nodes consisting of the nodes in the first set of nodes that are not in the second set of nodes;
initializing a live interval for the first variable as an interval from the lowest numbered node to the highest numbered node in the first subset of nodes; and
expanding the live interval for the first variable according to one or more loops represented in the graph, including
expanding the live interval for the first variable according to a first loop represented in the graph including:
determining an interval of the first loop as the interval from the lowest numbered node of the first loop to the highest numbered node of the first loop, the loop having a header node being a first node of the first loop accessed during execution of the program specification;
determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the first loop that does not pass through a node in the second subset of nodes;
having determined that there is a node in the third subset of nodes, expanding the live interval of the first variable to include the full interval of nodes of the first loop;
allocating variables of the first set of distinct variables to memory items of the second set of memory items, including
allocating multiple of said variables to a same memory item according to the live intervals for said multiple variables; and
forming a second representation of the program specification using a result of allocating the variables.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 1 is a process.
Claim 17 is a manufacture.
Claim 18 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 ‘determining’ limitation in #2 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining an enumerated ordering of the nodes of the graph representation, including comparison or judgement.
The ‘identifying’ limitation in #3 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “identifying” in the context of this claim encompasses a person analyzing, evaluating, or identifying all loops represented in the graph, including comparison or judgement.
The ‘determining’ limitation in #4 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a live interval for each distinct variable in the first representation of the program specification, including comparison or judgement.
The ‘determining’ limitation in #5 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a first subset of nodes in the graph of nodes that specify an instructions referencing the first variable, including comparison or judgement.
The ‘determining’ limitation in #6 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a second subset of nodes in which the instruction specified by said nodes fully assign the first variable, including comparison or judgement.
The ‘determining’ limitation in #7 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a third subset of nodes consisting of the nodes in the first set of nodes that are not in the second set of nodes, including comparison or judgement.
The ‘determining’ limitation in #11 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining an interval of the first loop as the interval from the lowest numbered node of the first loop to the highest numbered node of the first loop, including comparison or judgement.
The ‘determining’ limitation in #12 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the first loop that does not pass through a node in the second subset of nodes, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘allocating’ limitation in #1 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “allocating” in the context of this claim encompasses merely allocating a first set of distinct variables in a first representation of the program specification to a second set of memory items. See MPEP 2106.05(f).
The ‘initializing’ limitation in #8 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “initializing” in the context of this claim encompasses merely initializing a live interval for the first variable as an interval. See MPEP 2106.05(f).
The ‘expanding’ limitation in #9 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “expanding” in the context of this claim encompasses merely expanding the live interval for the first variable according to one or more loops represented in the graph. See MPEP 2106.05(f).
The ‘expanding’ limitation in #10 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “expanding” in the context of this claim encompasses merely expanding the live interval for the first variable according to a first loop represented in the graph. See MPEP 2106.05(f).
The ‘expanding’ limitation in #13 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “expanding” in the context of this claim encompasses merely expanding the live interval of the first variable to include the full interval of nodes of the first loop. See MPEP 2106.05(f).
The ‘allocating’ limitation in #14 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “allocating” in the context of this claim encompasses merely allocating variables of the first set of distinct variables to memory items of the second set of memory items. See MPEP 2106.05(f).
The ‘allocating’ limitation in #15 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “allocating” in the context of this claim encompasses merely allocating multiple of said variables to a same memory item according to the live intervals for said multiple variables. See MPEP 2106.05(f).
The ‘forming’ limitation in #16 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “forming” in the context of this claim encompasses merely forming a second representation of the program specification using a result of allocating the variables. See MPEP 2106.05(f).
Additionally, one or more of the claims recite the following additional elements:
Processor (Claims 1, 17, and 18)
Instructions (Claims 17-18)
These additional elements are recited at a high level of generality (i.e., as generic computer components) such that they amount to no more than components comprising mere instructions to apply the exception. Accordingly, these additional elements do not integrate the abstract idea(s) into a practical application because they do not impose any meaningful limits on practicing the abstract ideas(s).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Claim 5 merely further describes the processor, memory items, and first instruction of Claim 1. The claim does not include additional elements that integrate into practical application or are sufficient to amount to significantly more than the judicial exception.
Claim 6 merely further describes the distinct storage items of Claim 5. The claim does not include additional elements that integrate into practical application or are sufficient to amount to significantly more than the judicial exception.
Claim 7 merely further describes the number of memory items of Claim 1. The claim does not include additional elements that integrate into practical application or are sufficient to amount to significantly more than the judicial exception.
Claim 8 merely further describes the number of memory items of Claim 1. The claim does not include additional elements that integrate into practical application or are sufficient to amount to significantly more than the judicial exception.
Therefore, Claims 1, 5-8 and 17-18 are directed to (an) abstract idea(s) without significantly more.
Claim 2 recites:
providing the second representation of the program specification for execution using the processor to access the memory items during execution according to the allocation of variables to the memory items.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 2 is a process.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘providing’ limitation in #17 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “providing” in the context of this claim encompasses mere data gathering. See MPEP 2106.05(g).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claim 2 is directed to (an) abstract idea(s) without significantly more.
Claim 3 recites:
wherein determining the enumerated ordering of the nodes of the graph representation includes forming a depth-first ordering based on the directed links coupling the nodes of the graph.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 3 is a process.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘forming’ limitation in #18 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “forming” in the context of this claim encompasses a person analyzing, evaluating, or forming a depth-first ordering based on the directed links coupling the nodes of the graph, including comparison or judgement.
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claim 3 is directed to (an) abstract idea(s) without significantly more.
Claim 4 recites:
forming the program specification from an initial program specification that comprises a graph-based program specification.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 4 is a process.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘forming’ limitation in #19 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “forming” in the context of this claim encompasses merely forming the program specification from an initial program specification. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
With regards to Claim 14, the method of Claims 4-5 and 8 perform the same steps as the method of Claim 14, and Claim 14 is therefore rejected using the same rationale set forth above in the rejection of Claims 4-5 and 8.
Therefore, Claims 4 and 14 are directed to (an) abstract idea(s) without significantly more.
Claim 9 recites:
wherein determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the first loop that does not pass through a node in the second subset of nodes comprises determining that there is such a node that can be reached only via the header node.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 9 is a process.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #20 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining that there is such a node that can be reached only via the header node, including comparison or judgement.
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claim 9 is directed to (an) abstract idea(s) without significantly more.
Claim 10 recites:
wherein determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the loop that does not pass through a node in the second subset of nodes comprises determining that there is no such a node that can be reached only via the header node,
forming a fourth subset of nodes that is distinct from the third subset of nodes and that can be reached in an execution path from the header node without passing through a node of the second subset and can further be reached in an execution path without passing through the header node, and
determining if there is any node in the third subset of nodes for which there is at least one path of execution from a node in the fourth subset that does not pass through a node in the second subset of nodes.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 10 is a process.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #21 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining that there is no such a node that can be reached only via the header node, including comparison or judgement.
The ‘forming’ limitation in #22 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “forming” in the context of this claim encompasses a person analyzing, evaluating, or forming a fourth subset of nodes that is distinct from the third subset of nodes and that can be reached in an execution path from the header node without passing through a node of the second subset, including comparison or judgement.
The ‘determining’ limitation in #23 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining if there is any node in the third subset of nodes for which there is at least one path of execution from a node in the fourth subset that does not pass through a node in the second subset of nodes, including comparison or judgement.
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claim 10 is directed to (an) abstract idea(s) without significantly more.
Claims 11 and 15 recite:
determining live intervals for variables referenced in blocks of the first representation including
ordering instructions the first representation in reverse post-order depth-first order,
numbering the instructions in each block such that the last instruction in a block B has a lower number than the first instructions in any of B's successors, unless the successor is reached via a backwards link, and
identifying all the loops in the first representation and their associated intervals according to the number of the instructions;
performing for each variable V of the variables references in the blocks, collecting a set of killing definitions (K) and other references (R) for the variable (V), each ordered by an instruction number,
determining an initial live interval for variable V as the interval from the first to the last member of either K or R, for each loop L in the first representation, if L is contained entirely within V's interval, or if L contains no part of V's interval, ignore the loop L, otherwise,
check whether any member of R is upwardly exposed to the first instruction of L's header,
if the member of R is upwardly exposed, expand V's interval to include all of L.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 11 is a process.
Claim 15 is a process.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #24 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining live intervals for variables referenced in blocks of the first representation, including comparison or judgement.
The ‘ordering’ limitation in #25 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “ordering” in the context of this claim encompasses a person analyzing, evaluating, or ordering instructions the first representation in reverse post-order depth-first order, including comparison or judgement.
The ‘numbering’ limitation in #26 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “numbering” in the context of this claim encompasses a person analyzing, evaluating, or numbering the instructions in each block such that the last instruction in a block B has a lower number than the first instructions in any of B's successors, including comparison or judgement.
The ‘identifying’ limitation in #27 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “identifying” in the context of this claim encompasses a person analyzing, evaluating, or identifying all the loops in the first representation and their associated intervals according to the number of the instructions, including comparison or judgement.
The ‘determining’ limitation in #29 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining an initial live interval for variable V as the interval from the first to the last member of either K or R, including comparison or judgement.
The ‘checking’ limitation in #30 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “checking” in the context of this claim encompasses a person analyzing, evaluating, or checking whether any member of R is upwardly exposed to the first instruction of L's header, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘performing’ limitation in #28 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element that is insignificant extra-solution activity. The limitation “performing” in the context of this claim encompasses mere data gathering. See MPEP 2106.05(g).
The ‘expanding’ limitation in #31 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “expanding” in the context of this claim encompasses merely expanding V's interval to include all of L. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(g)&(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claims 11 and 15 are directed to (an) abstract idea(s) without significantly more.
Claims 12 and 16 recite:
a recursive procedure to determine whether there is any other reference in R for a particular a loop L and a variable V by considering successive dominance frontiers until a reference in R is found that is upwardly exposed to the header of L, or it is certain that no such reference in R exists, in which case the interval of L does not have to be added to the live interval of V, said procedure being defined in terms of arguments V and I, such that the procedure is started with I being the loop header of L and with static sets R and K for the variable V being accessible to the procedure, the recursive procedure comprising: of killing definitions of variable V, denoted K,
determine a subset denoted KD as consisting of the members of K that are dominated by I;
expand KD to iteratively include the first instruction of any basic block B that is dominated by I, and not dominated by any member of KD, but all of whose predecessors are dominated by members of KD;
determine the members of the other references, denoted R, of variable V that are dominated by I, and not dominated by a member of KD,
if there is any member of R that is dominated by I, and not dominated by a member of KD, the interval of the loop is added to the live interval of variable V, and all further searches of R are terminated,
otherwise for each block F in the dominance frontier of I with an incoming link from a block that is dominated by I and not dominated by any member of KD, perform perform the recursive procedure with arguments F and V.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 12 is a process.
Claim 16 is a process.
Step 2A, Prong I: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes: (an) abstract idea(s).
The ‘determining’ limitation in #32 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining whether there is any other reference in R for a particular a loop L and a variable V by considering successive dominance frontiers, including comparison or judgement.
The ‘determining’ limitation in #33 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining a subset denoted KD as consisting of the members of K that are dominated by I, including comparison or judgement.
The ‘determining’ limitation in #35 above, as claimed and under broadest reasonable interpretation (BRI), is a mental process that covers performance of the limitation in the mind. The limitation “determining” in the context of this claim encompasses a person analyzing, evaluating, or determining the members of the other references, denoted R, of variable V that are dominated by I, including comparison or judgement.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘expanding’ limitation in #34 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “expanding” in the context of this claim encompasses merely expanding KD to iteratively include the first instruction of any basic block B that is dominated by I. See MPEP 2106.05(f).
The ‘adding’ limitation in #36 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “adding” in the context of this claim encompasses merely adding to the live interval of variable V. See MPEP 2106.05(f).
The ‘performing’ limitation in #37 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “performing” in the context of this claim encompasses merely performing the recursive procedure with arguments F and V. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claims 12 and 16 are directed to (an) abstract idea(s) without significantly more.
Claim 13 recites:
executing the second representation of the program specification using the processor, including accessing the memory items during execution according to the allocation of variables to the memory items.
Step 1: Is the claim to a process, machine, manufacture, or composition of matter?
Yes.
Claim 13 is a process.
Step 2A, Prong II: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No.
The ‘executing’ limitation in #38 above, as claimed and under broadest reasonable interpretation (BRI), is an additional element as “apply it” that is mere instructions to apply an exception. The limitation “executing” in the context of this claim encompasses merely executing the second representation of the program specification using the processor. See MPEP 2106.05(f).
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No.
As discussed above with respect to integration of the abstract idea(s) into a practical application, the aforementioned additional elements amount to no more than components for obtaining or gathering data and comprising mere instructions to apply the exception which is evidently seen in MPEP 2106.05(f). Mere instructions to apply an exception using generic computer components cannot provide an inventive concept.
Therefore, Claim 13 is directed to (an) abstract idea(s) without significantly more.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-18 are rejected under 35 U.S.C. 103 as being unpatentable over Duesterwald et al. (“Register Pipelining: An Integrated Approach to Register Allocation for Scalar and Subscripted Variables”), hereinafter “Duesterwald” in view of Csefalvay et al. (U.S. Publication No. US 20240231913 A1), hereinafter “Csefalvay.”
With regards to claim 1, Duesterwald teaches:
A method for executing a program specification on a processor, including allocating a first set of distinct variables in a first representation of the program specification to a second set of memory items accessible by the processor (Page 192, section 1, paragraph 1 and page 194, section 1, paragraph 7 and section 2, paragraphs 1-2, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses… We have developed an efficient data flow based algorithm to determine live ranges for array elements inside a loop… Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… The first step consists of determining the live ranges of variable values, which are the entities for register assignment. The live range of a variable value starts with an initial definition or use of the variable and ends at the last use of the same value.” The multiple variables identified from the loop structure of the program correlates to a first set of distinct variables in a first representation of the program specification. The variables being allocated to registers correlates to allocating a first set of distinct variables in a first representation of the program specification to a second set of memory items accessible by the processor), wherein the number of memory items in the second set is smaller than the number of distinct variables in the first set, (Page 193, section 1, paragraph 3, “However, in a typical loop both subscripted and scalar variables compete for the available registers. Consequently, separately handling array recurrences from scalar register allocation causes the dilemma of sacrificing the benefit of one allocation for the other.” The subscripted and scalar variables competing for the available registers would involve less available registers than the total of subscripted and scalar variables and therefore correlates to wherein the number of memory items in the second set is smaller than the number of distinct variables in the first set), and wherein the first representation of the program specification comprises a graph in which nodes of the graph specify instructions referencing the variables (Page 194, section 2, paragraphs 1-2, page 200, section 4, paragraph 1, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… The first step consists of determining the live ranges of variable values, which are the entities for register assignment. The live range of a variable value starts with an initial definition or use of the variable and ends at the last use of the same value… The nodes in the interference graph represent live ranges of variables.” The interference graph nodes representing the live ranges of variables in loops of the main program correlates to the first representation of the program specification comprises a graph in which nodes of the graph specify instructions referencing the variables), and directed links coupling nodes of the graph represent allowable paths of control flow during execution of the program specification (Fig. 3, page 197, section 3.2, paragraphs 1-2, “This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body. Since access patterns of array references are to be analyzed, the intermediate code representation (IR) preserves the original army reference as shown in the example in Fig. 3. A-ranges are constructed by inserting definition-use (da) edges and use-use (uu) edges for each detected reuse of a δ-available value in the graph. A du/uu-edge is labeled with an iteration distance indicating the number of iterations between the two access points that are connected by the edge. Thus, an A-range is represented by a path of du/uu-edges... The edge 5->1 with label 1(A), for example, expresses that the value of array A computed in node 5 is reused in node 1 one iteration later. By ignoring transitive edges we obtain the complete path representing the live ranges for elements of array A as 5->11->02->04->15. The superscripts refer to the iteration distance of the respective du/uu-edges in the graph.” The annotated directional arrows of the du and uu-edges as shown in Fig. 3, such as between nodes 5 and 1, correlates to directed links coupling nodes of the graph. The du and uu edges forming the complete path for the live ranges of elements of the array between particular nodes in the control flow iteration order correlates to directed links coupling nodes of the graph represent allowable paths of control flow during execution of the program specification), the method comprising:
determining an enumerated ordering of the nodes of the graph representation, such that each node has a unique number (Fig. 3, page 197, section 3.2, paragraph 2, “The edge 5->1 with label 1(A), for example, expresses that the value of array A computed in node 5 is reused in node 1 one iteration later. By ignoring transitive edges we obtain the complete path representing the live ranges for elements of array A as 5->11->02->04->15. The superscripts refer to the iteration distance of the respective du/uu-edges in the graph.” Each of the nodes having a number from 1 to 7 as shown in Fig. 3 correlates to determining an enumerated ordering of the nodes of the graph representation, such that each node has a unique number);
identifying all loops represented in the graph, each loop having a set of nodes that are linked as part of a cycle by directed links of the graph, and having an interval of the lowest to the highest number of the nodes in the set of nodes in each loop (Fig. 3, page 194, section 2, paragraph 1, and page 197, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body… The edge 5->1 with label 1(A), for example, expresses that the value of array A computed in node 5 is reused in node 1 one iteration later. By ignoring transitive edges we obtain the complete path representing the live ranges for elements of array A as 5->11->02->04->15. The superscripts refer to the iteration distance of the respective du/uu-edges in the graph.” Each loop in the program being processed for allocation of register pipelines correlates to identifying all loops represented in the graph. The graph being computed on the intermediate statement-level control flow for a given loop body with nodes numbered 1-7 and connected with directed du and uu-edges as seen in Fig. 3 correlates to each loop having a set of nodes that are linked as part of a cycle by directed links of the graph. The nodes being numbered from a range such as 1 through 7 as seen in Fig. 3 correlates to having an interval of the lowest to the highest number of the nodes in the set of nodes in each loop);
determining a live interval for each distinct variable in the first representation of the program specification (Page 194, section 2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… The first step consists of determining the live ranges of variable values, which are the entities for register assignment. The live range of a variable value starts with an initial definition or use of the variable and ends at the last use of the same value.” The live ranges of variable values within a loop structure of the program being determined correlates to determining a live interval for each distinct variable in the first representation of the program specification);
wherein determining a live interval for a first variable of the distinct variables comprises:
determining a first subset of nodes in the graph of nodes that specify an instructions referencing the first variable (Fig. 4, pages 197-199, section 3.2, paragraphs 2 and 4, “The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The IN array containing the canonical names of values which are i-available on entry for each node would include particular nodes which have particular variables referenced on a particular instruction and therefore correlates to determining a first subset of nodes in the graph of nodes that specify an instructions referencing the first variable), determining a second subset of nodes in which the instruction specified by said nodes fully assign the first variable (Fig. 4, page 195, section 3, paragraph 1 and pages 197-199, section 3.2, paragraphs 2 and 4, “We construct live ranges for subscripted references by computing the available array elements (available A-values) inside a loop. An available A-value v is generated by a definition or a use of a subscripted variable V. The value v is available up to a point where variable V is redefined, in which case v is said to be killed. An A-range starts at a point where an A-value v is generated (i.e., at a definition or use of an array element) and extends up to the last use of the same array element at which v is still available… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n” Based on the specification description of a “killing reference” in relation to fully assigning the first variable, the Kill array containing subscripted references of definitions for each node would include subscripted references for a particular variable occurring on a particular instruction which would kill the value v and therefore correlates to determining a second subset of nodes in which the instruction specified by said nodes fully assign the first variable), and determining a third subset of nodes consisting of the nodes in the first set of nodes that are not in the second set of nodes (Fig. 4, pages 198-199, section 3.2, paragraph 4, “The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The OUT array containing the canonical names of values from values in the IN array that pass through the particular node and are not killed correlates to determining a third subset of nodes consisting of the nodes in the first set of nodes that are not in the second set of nodes);
initializing a live interval for the first variable as an interval from the lowest numbered node to the highest numbered node in the first subset of nodes (Fig. 3 and 4, page 195, section 3, paragraph 1, and pages 197 and 199, section 3.2, paragraphs 2 and 5, “We construct live ranges for subscripted references by computing the available array elements (available A-values) inside a loop. An available A-value v is generated by a definition or a use of a subscripted variable V. The value v is available up to a point where variable V is redefined, in which case v is said to be killed. An A-range starts at a point where an A-value v is generated (i.e., at a definition or use of an array element) and extends up to the last use of the same array element at which v is still available… The edge 5->1 with label 1(A), for example, expresses that the value of array A computed in node 5 is reused in node 1 one iteration later. By ignoring transitive edges we obtain the complete path representing the live ranges for elements of array A as 5->11->02->04->15. The superscripts refer to the iteration distance of the respective du/uu-edges in the graph… Table 1 shows the computed sets at the end of the first and the second iteration of the algorithm in Fig. 4. Superscripts of table entries denote the statement number of the respective reference. Entries marked with * denote the points where a du/uu-edge is created.” The live ranges being constructed and represented by a complete path for elements of array A through connections of du and uu-edges to nodes in a numbered order and denoted by the * for the IN array in Fig. 4 correlates to initializing a live interval for the first variable as an interval from the lowest numbered node to the highest numbered node in the first subset of nodes); and
expanding the live interval for the first variable according to one or more loops represented in the graph, including expanding the live interval for the first variable according to a first loop represented in the graph (Page 195, section 3, paragraph 1, and pages 203-204, section 7, paragraphs 2-3, “We construct live ranges for subscripted references by computing the available array elements (available A-values) inside a loop. An available A-value v is generated by a definition or a use of a subscripted variable V… These transformations are applied to nested loops and shorten the dependence distance among references by moving dependencies carded by outer loops to inner loops. We consider in this section a transformation that is applied to a single-level loop. The transformation is a simplified variation of a technique used in software pipelining… To demonstrate how the use in statement 1 can be moved one iteration closer to the definition, we unroll the loop once as shown in Fig. 7 (ii). The brackets to the left denote the original iteration window and the brackets to the right show the iteration window moved forward by one statement. Fig. 7 (iii) shows the restructured and transformed loop with the new iteration window. The transformation has reduced the iteration distance by one. Thus, only two registers are necessary to preserve the values for reuse in the transformed loop.” The single-level or nested loop being unrolled increases the number of statements within the loop body, which increases the number of uses of a subscripted variable and generates additional A-values. The increased A-values generated from the unrolled loop are used to construct live ranges and therefore correlates to expanding the live interval for the first variable according to one or more loops represented in the graph, including expanding the live interval for the first variable according to a first loop represented in the graph) including:
determining an interval of the first loop as the interval from the lowest numbered node of the first loop to the highest numbered node of the first loop (Fig. 3, page 197, section 3.2, paragraph 2, “The edge 5->1 with label 1(A), for example, expresses that the value of array A computed in node 5 is reused in node 1 one iteration later. By ignoring transitive edges we obtain the complete path representing the live ranges for elements of array A as 5->11->02->04->15. The superscripts refer to the iteration distance of the respective du/uu-edges in the graph.” The statements labeled in Fig. 3 (i) are labeled in numerical order based on the order they are accessed during execution of the program specification for the particular loop. The nodes in Fig.3 (ii) similarly reflect the same ordering of the statements and include a range from 1 to 7 which correlates to determining an interval of the first loop as the interval from the lowest numbered node of the first loop to the highest numbered node of the first loop), the loop having a header node being a first node of the first loop accessed during execution of the program specification (Fig. 4, page 198, section 3.2, “Input: ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes.” The distinguished entry node of a particular loop correlates to the loop having a header node being a first node of the first loop accessed during execution of the program specification);
determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the first loop that does not pass through a node in the second subset of nodes (Fig. 4, pages 198-199, section 3.2, paragraph 4, “The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The Kill array containing subscripted references of definitions for each node which would kill the value v and result in the i-available value not passing through the node and therefore correlates to a node in the second subset of nodes. The algorithm determining the OUT array based on the input loop to only contain the canonical names of values from values in the IN array that pass through the particular node and are not killed would involve at least one value after a particular iteration of the main loop where the value is still i-available on exit from the node, or in other words, the node is not present in the Kill array, and therefore correlates to determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the first loop that does not pass through a node in the second subset of nodes);
having determined that there is a node in the third subset of nodes, expanding the live interval of the first variable to include the full interval of nodes of the first loop (Fig. 4, page 195, section 3, paragraph 1, pages 198-199, section 3.2, paragraph 4, and pages 203-204, section 7, paragraphs 2-4, “We construct live ranges for subscripted references by computing the available array elements (available A-values) inside a loop. An available A-value v is generated by a definition or a use of a subscripted variable V… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2)… These transformations are applied to nested loops and shorten the dependence distance among references by moving dependencies carded by outer loops to inner loops. We consider in this section a transformation that is applied to a single-level loop. The transformation is a simplified variation of a technique used in software pipelining… To demonstrate how the use in statement 1 can be moved one iteration closer to the definition, we unroll the loop once as shown in Fig. 7 (ii). The brackets to the left denote the original iteration window and the brackets to the right show the iteration window moved forward by one statement. Fig. 7 (iii) shows the restructured and transformed loop with the new iteration window. The transformation has reduced the iteration distance by one. Thus, only two registers are necessary to preserve the values for reuse in the transformed loop. In general, we apply the transformation in situations where a statement s1 uses a value that is available from a use (definition) d iterations earlier in a statement s2 and s1 occurs before s2 in the loop body. To apply the transformation with respect to the iteration distance d from s1 to s2, i.e., to apply Transform(s1, s2), we first unroll the loop once.” The algorithm determining a non-empty OUT array based on the input loop to only contain the canonical names of values from values in the IN array that pass through the particular node and are not killed would involve at least one value after a particular iteration of the main loop where the value is still i-available on exit from the node, and therefore correlates to having determined that there is a node in the third subset of nodes. The single-level or nested loop being unrolled increases the number of statements within the loop body, which increases the number of uses of a subscripted variable and generates additional A-values. The loop can be in a scenario where each statement in the loop references the first variable and there is a statement s1 using a value from a statement s2 earlier in the loop body. Therefore, the transformation would be applied and unrolling the loop increases the A-values for both the first variable and the first loop. The increased A-values generated from the unrolled loop are used to construct live ranges and therefore correlates to expanding the live interval of the first variable to include the full interval of nodes of the first loop);
allocating variables of the first set of distinct variables to memory items of the second set of memory items, including allocating multiple of said variables to a same memory item according to the live intervals for said multiple variables (Page 192, section 1, paragraph 1, page 194, section 1, paragraph 7 and section 2, paragraphs 1-2, and page 200, section 4, paragraph 1, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses… We have developed an efficient data flow based algorithm to determine live ranges for array elements inside a loop… Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… The first step consists of determining the live ranges of variable values, which are the entities for register assignment. The live range of a variable value starts with an initial definition or use of the variable and ends at the last use of the same value… The problem of register allocation can be formulated as the problem of k-coloring the register interference graph [1], where k is the number of available registers. The nodes in the interference graph represent live ranges of variables. Two nodes are connected, i.e., interfere, if the corresponding live ranges overlap and cannot be held in the same register. Live ranges are assigned priorities that express the benefits of keeping the corresponding variable in a register, and registers are assigned to live ranges by coloring the corresponding nodes based on their priorities. We extend the traditional structure of the register interference graph to represent live ranges for subscripted variables as well as scalar live ranges.” The multiple variables identified from the loop structure of the program correlates to variables of the first set of distinct variables. The variables being allocated to registers correlates to allocating variables of the first set of distinct variables to memory items of the second set of memory items. The live ranges associated with the different variables being assigned to registers based on having the same coloring can include at least two variables being assigned to the same register and therefore correlates to allocating multiple of said variables to a same memory item according to the live intervals for said multiple variables); and
forming a second representation of the program specification using a result of allocating the variables (Page 195, section 2, paragraph 5, and page 200, section 4, paragraph 1, “When all loops in the program have been allocated register pipelines, the final code is generated. Code generation for a register pipeline allocated to an A-range includes the code for appropriately initializing the pipeline in the loop header, the replacement of variable references by accesses to pipeline stages and the code to implement the pipeline progression at the end of each iteration… The problem of register allocation can be formulated as the problem of k-coloring the register interference graph [1], where k is the number of available registers. The nodes in the interference graph represent live ranges of variables. Two nodes are connected, i.e., interfere, if the corresponding live ranges overlap and cannot be held in the same register. Live ranges are assigned priorities that express the benefits of keeping the corresponding variable in a register, and registers are assigned to live ranges by coloring the corresponding nodes based on their priorities. We extend the traditional structure of the register interference graph to represent live ranges for subscripted variables as well as scalar live ranges. The resulting graph is called the Integrated Register Interference Graph (IRIG).” The final code being generated after the loops in the program have been allocated register pipelines and registers are assigned to live ranges correlates to forming a second representation of the program specification using a result of allocating the variables).
Duesterwald does not explicitly teach:
and the number of memory items in the second set is limited by a memory characteristic of the processor
However, Csefalvay teaches:
and the number of memory items in the second set is limited by a memory characteristic of the processor (Paragraph 66, “For example, a warp comprising a plurality of threads (e.g. 128 threads) can be processed at processing element 102 (e.g. a core of a processing unit) so as to perform an operation on an array of values (e.g. 1024 values)… The limit on the number of values that can be processed by a thread may be caused by the amount of register memory in register bank 110 accessible by (e.g. dedicated to) each thread. In order to perform the operation, the processing logic 104 may cause, for each thread of the warp, a respective group of values (e.g. 8 values) to be processed by that thread to be read from global memory 108 into the one or more registers dedicated to that thread.” The number of values that can be processed at a processing element being limited by an amount of register memory in a register bank that is accessible to each thread correlates to the number of memory items in the second set is limited by a memory characteristic of the processor).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Duesterwald with and the number of memory items in the second set is limited by a memory characteristic of the processor as taught by Csefalvay because different threads can have different amounts of register memory in a register bank accessible or dedicated to them. Each thread may be capable of completing the desired operation for a different number of values (Csefalvay: paragraphs 66 and 81).
With regards to Claims 17 and 18, the method of Claim 1 performs the same steps as the manufacture and machine of Claims 17 and 18 respectively, and Claims 17 and 18 are therefore rejected using the same rationale set forth above in the rejection of Claim 1.
With regards to claim 2, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
providing the second representation of the program specification for execution using the processor to access the memory items during execution according to the allocation of variables to the memory items (Page 192, section 1, paragraph 1 and page 195, section 2, paragraph 5, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses… When all loops in the program have been allocated register pipelines, the final code is generated. Code generation for a register pipeline allocated to an A-range includes the code for appropriately initializing the pipeline in the loop header, the replacement of variable references by accesses to pipeline stages and the code to implement the pipeline progression at the end of each iteration.” The variables being allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses would involve the execution of the final code and therefore correlates to providing the second representation of the program specification for execution using the processor to access the memory items during execution according to the allocation of variables to the memory items).
With regards to claim 3, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
wherein determining the enumerated ordering of the nodes of the graph representation includes forming a depth-first ordering based on the directed links coupling the nodes of the graph (Fig. 3, page 197, section 3.2, paragraph 1, “This section presents a data flow algorithm to construct A-ranges by computing the 8- available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body. Since access patterns of array references are to be analyzed, the intermediate code representation (IR) preserves the original army reference as shown in the example in Fig. 3.” The control flow graph ordering the nodes based on their statement-level appearance in the code as shown in Fig. 3 and linking control and du/uu-edges correlates to determining the enumerated ordering of the nodes of the graph representation includes forming a depth-first ordering based on the directed links coupling the nodes of the graph).
With regards to claim 4, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
forming the program specification from an initial program specification that comprises a graph-based program specification (Fig. 3, page 197, section 3.2, paragraph 1, “This section presents a data flow algorithm to construct A-ranges by computing the 8- available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body. Since access patterns of array references are to be analyzed, the intermediate code representation (IR) preserves the original army reference as shown in the example in Fig. 3.” The control flow graph linking nodes which represent statements and control and du/uu-edges based on their statement-level appearance in the code as shown in Fig. 3 correlates to forming the program specification from an initial program specification that comprises a graph-based program specification).
With regards to claim 5, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Csefalvay further teaches:
wherein the processor comprises a virtual processor executing on a physical processor (Paragraph 225, “Executable code may be, for example, any kind of software, firmware, script, module or library which, when suitably executed, processed, interpreted, compiled, executed at a virtual machine or other software environment, cause a processor of the computer system at which the executable code is supported to perform the tasks specified by the code.” The virtual machine causing a processor of the computer system to execute code correlates to wherein the processor comprises a virtual processor executing on a physical processor),
Duesterwald further teaches:
and wherein the second set of memory items accessible by the processor comprises a data structure accessible to the physical processor with a distinct storage area accessible by the processor for each memory item (Page 192, section 1, paragraphs 1-2, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses… The computed values can be preserved in registers for reuse, thereby avoiding memory load instructions, by allocating a register pipeline.” The registers being used to store computed values of variables correlates to wherein the second set of memory items accessible by the processor comprises a data structure accessible to the physical processor with a distinct storage area accessible by the processor for each memory item), wherein execution of a first instruction of the second representation of the program specification by the processor comprises the physical processor accessing a storage item in the data structure corresponding to a memory item in a field of the first instruction (Page 192, section 1, paragraph 1 and page 195, section 2, paragraph 5, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses… When all loops in the program have been allocated register pipelines, the final code is generated. Code generation for a register pipeline allocated to an A-range includes the code for appropriately initializing the pipeline in the loop header, the replacement of variable references by accesses to pipeline stages and the code to implement the pipeline progression at the end of each iteration.” The variables being allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses would involve the execution of the final code which starts with acquiring values for a first instruction and therefore correlates to wherein execution of a first instruction of the second representation of the program specification by the processor comprises the physical processor accessing a storage item in the data structure corresponding to a memory item in a field of the first instruction).
Duesterwald does not explicitly teach that the processor is a virtual processor. However, virtual processors are a popular type of processor as evidenced by Csefalvay above (Paragraph 225, “Executable code may be, for example, any kind of software, firmware, script, module or library which, when suitably executed, processed, interpreted, compiled, executed at a virtual machine or other software environment, cause a processor of the computer system at which the executable code is supported to perform the tasks specified by the code.” The virtual machine causing a processor of the computer system to execute code correlates to a virtual processor).
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Duesterwald with wherein the processor comprises a virtual processor executing on a physical processor as taught by Csefalvay because executable code can be executed, processed, interpreted, or compiled a virtual machine or other software environment to cause a processor of the computer system at which the executable code is supported to perform the tasks specified by the code. Computer systems may also comprise one or more processors with processing capability such that it can execute instructions (Csefalvay: paragraphs 225-226).
With regards to claim 6, Duesterwald in view of Csefalvay teaches the method of claim 5 above. Duesterwald further teaches:
wherein at least some of the distinct storage items includes references to data storage areas accessible to the physical processor outside the data structure (Fig. 1, pages 192-193, section 1, paragraph 2, and page 195, section 2, paragraph 5, “The computed values can be preserved in registers for reuse, thereby avoiding memory load instructions, by allocating a register pipeline. A register pipeline is a set of registers constituting the stages of the pipeline. A computed or loaded value enters the pipeline at the first stage and progresses through the pipeline one stage per iteration… When all loops in the program have been allocated register pipelines, the final code is generated. Code generation for a register pipeline allocated to an A-range includes the code for appropriately initializing the pipeline in the loop header, the replacement of variable references by accesses to pipeline stages and the code to implement the pipeline progression at the end of each iteration.” The computed values being preserved in registers in a register pipeline, where different pipeline stages associated with different registers can be referenced instead of the variable reference, correlates to wherein at least some of the distinct storage items includes references to data storage areas accessible to the physical processor outside the data structure).
With regards to claim 7, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
wherein the number of memory items in the second set exceeds 1023 memory items (Page 200, section 4, paragraph 1, “The problem of register allocation can be formulated as the problem of k-coloring the register interference graph [1], where k is the number of available registers. The nodes in the interference graph represent live ranges of variables. Two nodes are connected, i.e., interfere, if the corresponding live ranges overlap and cannot be held in the same register. Live ranges are assigned priorities that express the benefits of keeping the corresponding variable in a register, and registers are assigned to live ranges by coloring the corresponding nodes based on their priorities.” The number of available registers being represented by k, which is an unbounded number, under BRI correlates to wherein the number of memory items in the second set exceeds 1023 memory items).
With regards to claim 8, Duesterwald in view of Csefalvay teaches the method of claim 7 above. Duesterwald further teaches:
wherein the number of memory items in the second set exceeds 16383 memory items (Page 200, section 4, paragraph 1, “The problem of register allocation can be formulated as the problem of k-coloring the register interference graph [1], where k is the number of available registers. The nodes in the interference graph represent live ranges of variables. Two nodes are connected, i.e., interfere, if the corresponding live ranges overlap and cannot be held in the same register. Live ranges are assigned priorities that express the benefits of keeping the corresponding variable in a register, and registers are assigned to live ranges by coloring the corresponding nodes based on their priorities.” The number of available registers being represented by k, which is an unbounded number, under BRI correlates to wherein the number of memory items in the second set exceeds 16383 memory items).
With regards to claim 9, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
wherein determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the first loop that does not pass through a node in the second subset of nodes comprises determining that there is such a node that can be reached only via the header node (Fig. 4, pages 198-199, section 3.2, paragraph 4, “Input: ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The Kill array containing subscripted references of definitions for each node which would kill the value v and result in the i-available value not passing through the node and therefore correlates to a node in the second subset of nodes. The distinguished entry node of a particular loop correlates to a header node. The algorithm determining the OUT array based on the input loop which begins with the distinguished entry node to only contain the canonical names of values from values in the IN array that pass through the particular node and are not killed would involve at least one value after a particular iteration of the main loop, where the value is still i-available on exit from the node, or in other words, the node is not present in the Kill array, and therefore correlates to wherein determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the first loop that does not pass through a node in the second subset of nodes comprises determining that there is such a node that can be reached only via the header node);
With regards to claim 10, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
wherein determining if there is any node in the third subset of nodes for which there is at least one path of execution from the header node of the loop that does not pass through a node in the second subset of nodes comprises determining that there is no such a node that can be reached only via the header node (Fig. 4, pages 198-199, section 3.2, paragraph 4, “Input: ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The Kill array containing subscripted references of definitions for each node which would kill the value v and result in the i-available value not passing through the node and therefore correlates to a node in the second subset of nodes. The distinguished entry node of a particular loop correlates to a header node. The algorithm determining the OUT array based on the input loop, which passes through the distinguished entry node, to only contain the canonical names of values from values in the IN array that pass through the particular node and are not killed would involve at least one value after a particular iteration of the main loop where the value is still i-available on exit from the node, or in other words, the node is not present in the Kill array, and therefore correlates to determining that there is no such a node that can be reached only via the header node), forming a fourth subset of nodes that is distinct from the third subset of nodes and that can be reached in an execution path from the header node without passing through a node of the second subset and can further be reached in an execution path without passing through the header node (Fig. 4, pages 198-199, section 3.2, paragraph 4, “Input: ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The Kill array containing subscripted references of definitions for each node which would kill the value v and result in the i-available value not passing through the node and therefore correlates to a node in the second subset of nodes. The distinguished entry node of a particular loop correlates to a header node. The algorithm determining the OUT array based on the input loop at each iteration, which passes through the distinguished entry node, to only contain the canonical names of values from values in the IN array that pass through the particular node and are not killed would involve at least one value after a particular iteration of the main loop where the value is still i-available on exit from the node, or in other words, the node is not present in the Kill array, and therefore correlates to forming a fourth subset of nodes that is distinct from the third subset of nodes and that can be reached in an execution path from the header node without passing through a node of the second subset. In a scenario where the distinguished entry node is a conditional statement, and a particular iteration different from the previous iteration does not satisfy the conditional statement, the distinguished entry node would not be passed through and therefore the OUT array for that particular iteration correlates to forming a fourth subset of nodes that is distinct from the third subset of nodes that can further be reached in an execution path without passing through the header node), and determining if there is any node in the third subset of nodes for which there is at least one path of execution from a node in the fourth subset that does not pass through a node in the second subset of nodes (Fig. 4, pages 198-199, section 3.2, paragraph 4, page 200, section 4, paragraph 1, “Input: ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2)… The nodes in the interference graph represent live ranges of variables. Two nodes are connected, i.e., interfere, if the corresponding live ranges overlap and cannot be held in the same register.” The Kill array containing subscripted references of definitions for each node which would kill the value v and result in the i-available value not passing through the node and therefore correlates to a node in the second subset of nodes. The distinguished entry node of a particular loop correlates to a header node. The algorithm determining the OUT array for each iteration based on the input loop, which passes through the distinguished entry node, to only contain the canonical names of values from values in the IN array that pass through the particular node and are not killed would involve at least one value after a particular iteration of the main loop where the value is still i-available on exit from the node, or in other words, the node is not present in the Kill array. A particular previous iteration can have a different live range than a current iteration, where each live range is compared to determine if the live ranges overlap and therefore correlates to determining if there is any node in the third subset of nodes for which there is at least one path of execution from a node in the fourth subset that does not pass through a node in the second subset of nodes).
With regards to claim 11, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
determining live intervals for variables referenced in blocks of the first representation including ordering instructions the first representation in reverse post-order depth-first order (Fig. 3, page 194, section 2, paragraph 1 and page 197, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body.” The algorithm starting with the innermost loops and progressing towards the outermost loops and the main program correlates to a reverse post-order depth-first order. Each of the instructions being ordered by number as seen in Fig. 3 correlates to ordering instructions the first representation in reverse post-order depth-first order),
numbering the instructions in each block such that the last instruction in a block B has a lower number than the first instructions in any of B's successors, unless the successor is reached via a backwards link (Fig. 3, page 194, section 2, paragraph 1 and page 197, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body.” The algorithm starting with the innermost loops and progressing towards the outermost loops and the main program and each of the instructions being ordered by number on a per-loop basis as seen in Fig. 3 would involve the innermost loops having a lower instruction number range than an outer loop instruction number range and therefore correlates to numbering the instructions in each block such that the last instruction in a block B has a lower number than the first instructions in any of B's successors, unless the successor is reached via a backwards link), and identifying all the loops in the first representation and their associated intervals according to the number of the instructions (Fig. 3, page 194, section 2, paragraph 1 and page 197, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body… Thus, an A-range is represented by a path of du/uu-edges.” The algorithm starting with the innermost loops and progressing towards the outermost loops and the main program and determining the A-range values on a per-loop basis as seen in Fig. 3 would involve identifying each loop and therefore correlates to identifying all the loops in the first representation and their associated intervals according to the number of the instructions);
performing for each variable V of the variables references in the blocks,
collecting a set of killing definitions (K) and other references (R) for the variable (V), each ordered by an instruction number (Pages 198-199, section 3.2, paragraphs 4, “The detailed algorithm is depicted in Fig. 4. The algorithm performs multiple passes through a loop L and determines during pass i the/-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n, The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node n. An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The Kill array containing subscripted references of definitions in n which kill the value correlates to collecting a set of killing definitions (K) for the variable (V), each ordered by an instruction number. The OUT array containing values that are i-available on entry and exit for a particular node would include values that are not killed and therefore correlates to collecting a set of other references (R) for the variable (V), each ordered by an instruction number),
determining an initial live interval for variable V as the interval from the first to the last member of either K or R (Fig. 3, page 194, section 2, paragraph 1 and page 197, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body… Thus, an A-range is represented by a path of du/uu-edges.” The algorithm determining the A-range values on a per-loop basis as seen in Fig. 3 which are represented by a path of du/uu-edges going through numbered instructions correlates to determining an initial live interval for variable V as the interval from the first to the last member of either K or R), for each loop L in the first representation, if L is contained entirely within V's interval, or if L contains no part of V's interval, ignore the loop L (Fig. 3, page 194, section 2, paragraph 1 and page 197, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body… Thus, an A-range is represented by a path of du/uu-edges.” The algorithm determining the A-range values on a per-loop basis as seen in Fig. 3 which are represented by a path of du/uu-edges going through numbered instructions can involve a particular loop that does not include a particular variable. In this scenario, the A-range values for the particular variable would not be affected by the particular loop and therefore correlates to for each loop L in the first representation, if L is contained entirely within V's interval, or if L contains no part of V's interval, ignore the loop L), otherwise, check whether any member of R is upwardly exposed to the first instruction of L's header, if the member of R is upwardly exposed, expand V's interval to include all of L (Fig. 4, page 195, section 3, paragraph 1, pages 198-199, section 3.2, paragraph 4, and pages 203-204, section 7, paragraphs 2-4, “We construct live ranges for subscripted references by computing the available array elements (available A-values) inside a loop. An available A-value v is generated by a definition or a use of a subscripted variable V… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2)… These transformations are applied to nested loops and shorten the dependence distance among references by moving dependencies carded by outer loops to inner loops. We consider in this section a transformation that is applied to a single-level loop. The transformation is a simplified variation of a technique used in software pipelining… To demonstrate how the use in statement 1 can be moved one iteration closer to the definition, we unroll the loop once as shown in Fig. 7 (ii). The brackets to the left denote the original iteration window and the brackets to the right show the iteration window moved forward by one statement. Fig. 7 (iii) shows the restructured and transformed loop with the new iteration window. The transformation has reduced the iteration distance by one. Thus, only two registers are necessary to preserve the values for reuse in the transformed loop. In general, we apply the transformation in situations where a statement s1 uses a value that is available from a use (definition) d iterations earlier in a statement s2 and s1 occurs before s2 in the loop body. To apply the transformation with respect to the iteration distance d from s1 to s2, i.e., to apply Transform(s1, s2), we first unroll the loop once.” The algorithm determining a non-empty OUT array based on the input loop to only contain the canonical names of values from values in the IN array that pass through the particular node and are not killed would involve at least one value after a particular iteration of the main loop where the value is still i-available on exit from the node, and therefore correlates to checking whether any member of R is upwardly exposed to the first instruction of L's header. The single-level or nested loop being unrolled increases the number of statements within the loop body, which increases the number of uses of a subscripted variable and generates additional A-values. The loop can be in a scenario where each statement in the loop references the first variable and there is a statement s1 using a value from a statement s2 earlier in the loop body. Therefore, the transformation would be applied and unrolling the loop increases the A-values for both the first variable and the first loop. The increased A-values generated from the unrolled loop are used to construct live ranges and therefore correlates to if the member of R is upwardly exposed, expand V's interval to include all of L).
With regards to Claim 15, the method of Claim 11 performs the same steps as method of Claim 15, and Claim 15 is therefore rejected using the same rationale set forth above in the rejection of Claim 11.
With regards to claim 12, Duesterwald in view of Csefalvay teaches the method of claim 11 above. Duesterwald further teaches:
a recursive procedure to determine whether there is any other reference in R for a particular a loop L and a variable V by considering successive dominance frontiers until a reference in R is found that is upwardly exposed to the header of L, or it is certain that no such reference in R exists, in which case the interval of L does not have to be added to the live interval of V (Fig. 3, page 194, section 2, paragraph 1 and page 197, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body… Thus, an A-range is represented by a path of du/uu-edges.” The algorithm starting with the innermost loops and progressing towards the outermost loops and the main program and determining the A-range values on a per-loop basis as seen in Fig. 3 would involve considering each outer loop in a recursive manner and therefore correlates to a recursive procedure to determine whether there is any other reference in R for a particular a loop L and a variable V by considering successive dominance frontiers until a reference in R is found that is upwardly exposed to the header of L), said procedure being defined in terms of arguments V and I, such that the procedure is started with I being the loop header of L and with static sets R and K for the variable V being accessible to the procedure (Page 198, section 3.2, paragraph 4, “Algorithm: Input: Output: Begin (1) δ-Available Values. ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes δMAX: maximal iteration distance value du/uu edges in L… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The distinguished entry node correlates to I being the loop header of L. The Kill array and OUT arrays correlate to static sets R and K for the variable V being accessible to the procedure. The algorithm determining the δ-Available Values for each loop using values such as the Kill and OUT arrays, as well as the distinguished entry node, correlates to said procedure being defined in terms of arguments V and I, such that the procedure is started with I being the loop header of L and with static sets R and K for the variable V being accessible to the procedure), the recursive procedure comprising:
of killing definitions of variable V, denoted K, determine a subset denoted KD as consisting of the members of K that are dominated by I (Page 198, section 3.2, paragraph 4, “Algorithm: Input: Output: Begin (1) δ-Available Values. ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes δMAX: maximal iteration distance value du/uu edges in L… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The distinguished entry node correlates to I being the loop header of L. The Kill array includes the subscripted references of definitions in n which can include references for a particular variable which correlates to killing definitions of variable V, denoted K. The algorithm determining the δ-Available Values for each loop using values such as the Kill array for a particular node, as well as the distinguished entry node, correlates to of killing definitions of variable V, denoted K, determine a subset denoted KD as consisting of the members of K that are dominated by I)
expand KD to iteratively include the first instruction of any basic block B that is dominated by I, and not dominated by any member of KD, but all of whose predecessors are dominated by members of KD (Page 198, section 3.2, paragraph 4, “Algorithm: Input: Output: Begin (1) δ-Available Values. ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes δMAX: maximal iteration distance value du/uu edges in L… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The distinguished entry node correlates to I being the loop header of L. The Kill array correlates to killing definitions of variable V, denoted K. The algorithm determining the δ-Available Values for each loop using values such as the Kill array which is initialized for each node, as well as the distinguished entry node dictating the control flow graph for a loop, correlates to expanding KD to iteratively include the first instruction of any basic block B that is dominated by I, and not dominated by any member of KD, but all of whose predecessors are dominated by members of KD);
determine the members of the other references, denoted R, of variable V that are dominated by I, and not dominated by a member of KD (Page 198, section 3.2, paragraph 4, “Algorithm: Input: Output: Begin (1) δ-Available Values. ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes δMAX: maximal iteration distance value du/uu edges in L… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The distinguished entry node correlates to I being the loop header of L. The OUT array which is based on the values that are i-available on entry and exit of a node in a loop starting with the distinguished entry node correlates to determining the members of the other references, denoted R, of variable V that are dominated by I, and not dominated by a member of KD),
if there is any member of R that is dominated by I, and not dominated by a member of KD, the interval of the loop is added to the live interval of variable V, and all further searches of R are terminated (Page 198, section 3.2, paragraph 4, “Algorithm: Input: Output: Begin (1) δ-Available Values. ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes δMAX: maximal iteration distance value du/uu edges in L… The algorithm performs multiple passes through a loop L and determines during pass i the i-available values in L. For every node n in loop L we define the sets Gen[n ] and Kill[n ]. Gen[n ] contains the canonical names of generating references in n, Thus, Gen[n] describes the candidates for δ-available values. Kill[n] contains the subscripted references of definitions in n. The algorithm computes at every node n the data flow sets IN[n ] and OUT[n ]. At the end of the i-th iteration of the main loop (see lines 7-33), IN[n ] contains the canonical names of values that are i-available on entry to node n and OUT[n ] contains the canonical names of those values from IN[n ] that pass through n, i.e., that are i-available on exit from node An i-available value with canonical name A[f (I-i)] does not pass through node n if the value is killed in n by a definition to A[f(l-i)] or to a potential alias thereof (see lines 19-2).” The distinguished entry node correlates to I being the loop header of L. The OUT array which is based on the values that are i-available on entry and exit of a node in a loop starting with the distinguished entry node correlates to members of the other references, denoted R, of variable V. The algorithm determining the δ-Available Values for each loop using values such as the OUT array which is updated for a particular node, as well as the distinguished entry node dictating the control flow graph for a loop, correlates to if there is any member of R that is dominated by I, and not dominated by a member of KD, the interval of the loop is added to the live interval of variable V, and all further searches of R are terminated),
otherwise for each block F in the dominance frontier of I with an incoming link from a block that is dominated by I and not dominated by any member of KD, perform perform the recursive procedure with arguments F and V (Fig. 3, page 194, section 2, paragraph 1 and pages 197-198, section 3.2, paragraphs 1-2, “Our integrated register allocation algorithm is driven by the loop structure of the program starting with innermost loops and subsequently progressing towards outermost loops and the main program. Thus, a single loop is considered at any one time, and each loop is processed for allocation of register pipelines in the following steps… This section presents a data flow algorithm to construct A-ranges by computing the δ-available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body… Thus, an A-range is represented by a path of du/uu-edges… Algorithm: Input: Output: Begin (1) δ-Available Values. ( L, nentry, nexit): control flow graph for a loop with distinguished entry and exit nodes.” The algorithm starting with the innermost loops and progressing towards the outermost loops and the main program and determining the A-range values on a per-loop basis through the distinguished entry node as seen in Fig. 3 would involve considering each outer loop in a recursive manner and therefore correlates to for each block F in the dominance frontier of I with an incoming link from a block that is dominated by I and not dominated by any member of KD, perform the recursive procedure with arguments F and V).
With regards to Claim 16, the method of Claim 12 performs the same steps as method of Claim 16, and Claim 16 is therefore rejected using the same rationale set forth above in the rejection of Claim 12.
With regards to claim 13, Duesterwald in view of Csefalvay teaches the method of claim 1 above. Duesterwald further teaches:
executing the second representation of the program specification using the processor, including accessing the memory items during execution according to the allocation of variables to the memory items (Page 192, section 1, paragraph 1 and page 195, section 2, paragraph 5, and page 200, section 4, paragraph 1, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses. Current compilers employ sophisticated register allocation strategies, such as allocation via graph coloring [6, 7] for holding scalar variables in registers… Scientific programs typically spend most of their time executing loops that process large amounts of data involving references to both scalar and subscripted variables. Exploiting reuse opportunities for these variables can significantly reduce the memory traffic and thus improve the overall performance of the program... When all loops in the program have been allocated register pipelines, the final code is generated. Code generation for a register pipeline allocated to an A-range includes the code for appropriately initializing the pipeline in the loop header, the replacement of variable references by accesses to pipeline stages and the code to implement the pipeline progression at the end of each iteration… The problem of register allocation can be formulated as the problem of k-coloring the register interference graph [1], where k is the number of available registers. The nodes in the interference graph represent live ranges of variables. Two nodes are connected, i.e., interfere, if the corresponding live ranges overlap and cannot be held in the same register. Live ranges are assigned priorities that express the benefits of keeping the corresponding variable in a register, and registers are assigned to live ranges by coloring the corresponding nodes based on their priorities. We extend the traditional structure of the register interference graph to represent live ranges for subscripted variables as well as scalar live ranges. The resulting graph is called the Integrated Register Interference Graph (IRIG).” The final code being generated after the loops in the program have been allocated register pipelines and registers are assigned to live ranges correlates to a second representation of the program specification using a result of allocating the variables. The variables being allocated to registers to enable fast reuse and avoid expensive memory accesses through compilers, and improving the overall performance and reducing memory traffic of a program would involve executing the code and therefore correlates to executing the second representation of the program specification using the processor, including accessing the memory items during execution according to the allocation of variables to the memory items).
With regards to claim 14, Duesterwald in view of Csefalvay teaches the method of claim 13 above. Duesterwald further teaches:
forming the program specification from an initial program specification that comprises a graph-based program specification (Fig. 3, page 197, section 3.2, paragraph 1, “This section presents a data flow algorithm to construct A-ranges by computing the 8- available values inside a loop. Our algorithm operates on the intermediate statement-level control flow graph for a given loop body. Since access patterns of array references are to be analyzed, the intermediate code representation (IR) preserves the original army reference as shown in the example in Fig. 3.” The control flow graph linking nodes which represent statements and control and du/uu-edges based on their statement-level appearance in the code as shown in Fig. 3 correlates to forming the program specification from an initial program specification that comprises a graph-based program specification); and
wherein the number of memory items in the second set exceeds 16383 memory items (Page 200, section 4, paragraph 1, “The problem of register allocation can be formulated as the problem of k-coloring the register interference graph [1], where k is the number of available registers. The nodes in the interference graph represent live ranges of variables. Two nodes are connected, i.e., interfere, if the corresponding live ranges overlap and cannot be held in the same register. Live ranges are assigned priorities that express the benefits of keeping the corresponding variable in a register, and registers are assigned to live ranges by coloring the corresponding nodes based on their priorities.” The number of available registers being represented by k, which is an unbounded number, under BRI correlates to wherein the number of memory items in the second set exceeds 16383 memory items), and wherein the second set of memory items accessible by the processor comprises a data structure accessible to the physical processor with a distinct storage area accessible by the virtual processor for each memory item (Page 192, section 1, paragraphs 1-2, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses… The computed values can be preserved in registers for reuse, thereby avoiding memory load instructions, by allocating a register pipeline.” The registers being used to store computed values of variables correlates to wherein the second set of memory items accessible by the processor comprises a data structure accessible to the physical processor with a distinct storage area accessible by the processor for each memory item), wherein execution of a first instruction of the second representation of the program specification by the virtual processor comprises the physical processor accessing a storage item in the data structure corresponding to a memory item in a field of the first instruction (Page 192, section 1, paragraph 1 and page 195, section 2, paragraph 5, “Variables are allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses… When all loops in the program have been allocated register pipelines, the final code is generated. Code generation for a register pipeline allocated to an A-range includes the code for appropriately initializing the pipeline in the loop header, the replacement of variable references by accesses to pipeline stages and the code to implement the pipeline progression at the end of each iteration.” The variables being allocated to registers to enable fast reuse of computed values and avoid expensive memory accesses would involve the execution of the final code which starts with acquiring values for a first instruction and therefore correlates to wherein execution of a first instruction of the second representation of the program specification by the processor comprises the physical processor accessing a storage item in the data structure corresponding to a memory item in a field of the first instruction).
Duesterwald does not explicitly teach that the processor is a virtual processor. However, virtual processors are a popular type of processor as evidenced by Csefalvay above (Paragraph 225).
Csefalvay further teaches:
the processor comprises a virtual processor executing on a physical processor (Paragraph 225, “Executable code may be, for example, any kind of software, firmware, script, module or library which, when suitably executed, processed, interpreted, compiled, executed at a virtual machine or other software environment, cause a processor of the computer system at which the executable code is supported to perform the tasks specified by the code.” The virtual machine causing a processor of the computer system to execute code correlates to wherein the processor comprises a virtual processor executing on a physical processor),
Therefore, it would have been obvious to one of ordinary skill in the art to which said subject matter pertains before the effective filing date of the claimed invention to combine Duesterwald with the processor comprises a virtual processor executing on a physical processor as taught by Csefalvay because executable code can be executed, processed, interpreted, or compiled a virtual machine or other software environment to cause a processor of the computer system at which the executable code is supported to perform the tasks specified by the code. Computer systems may also comprise one or more processors with processing capability such that it can execute instructions (Csefalvay: paragraphs 225-226).
Prior Art Made of Record
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
Li et al. (U.S. Publication No. US 20220114177 A1); teaching a method of determining a live range and live interval of database objects based on the occurrences of database operations to the database object. Based on the live range of the database object, memory is optimally assigned to store the database object based on characteristics of the memory. Live intervals can be computed for each database object from a range such that there is no instruction with a number greater than the upper limit of the range for which the database object is live.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SELINA HU whose telephone number is (571)272-5428. The examiner can normally be reached Monday-Friday 8:30-5:30.
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.
The publicPAIR and privatePAIR systems are no longer available. 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.
SELINA HU
Examiner
Art Unit 2193
/Chat C Do/Supervisory Patent Examiner, Art Unit 2193
Prosecution Insights