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 .
Remarks
This Office Action is in response to applicant’s amendment filed on March 30, 2026, under which claims 1-23 and 32-38 are pending and under consideration.
Response to Arguments
Applicant’s amendments have overcome part of the previous § 101 rejections, and have overcome the § 103 rejections. However, upon further consideration, new grounds of rejection have been made under § 103.
Applicant’s arguments directed to the § 103 rejections are moot under the new grounds of rejection, because they rely on new claim limitations that are addressed by newly applied references.
Applicant’s arguments directed to the § 101 rejections are addressed below. Applicant first argues:
The Office Action rejected claims 1-23 and 32-38 under 35 U.S.C. § 101 as allegedly directed to a judicial exception. Applicant respectfully traverses this rejection. While disagreeing with this rejection, Applicant has amended the claims to further clarify eligibility. The independent claims have been amended to more explicitly recite the practical application in computing and neural networks of to identify control flow loops in neural network data flow graphs to apply optimizations as part of compiling program code defining one or more neural networks to improve reduce time to generate inferences, reduce memory overhead, and improve processor utilization. Thus, in addition to a practical application, the amended claims also reflect an improvement to computer technology and are further eligible for that reason.
(Applicant’s response, pages 10-11).
These arguments are partially persuasive in that the amendment to claim 1 which added the new limitations of “wherein the one or more data flow graphs generated from program code defining one or more neural networks,” “reconstruct the control flow loop…” and “to compile the program code defining the one or more neural networks,” among other limitations added to the claim, has resulted in the withdrawal of the § 101 rejection of this claim.
However, the other independent claims (i.e., claims 9, 17, and 32) were not amended in the same manner and do not tie the abstract idea pertaining to graph analysis to the technical process of compiling program code defining a neural network where the data flow graph is generated from the program code. Instead, the other independent claims recite a mental process disembodied from such an application. Therefore, the above arguments, which refers to “compiling program code,” does not support the patent eligibility of the other independent claims.
Applicant also argues:
Moreover, the amended claims recite a specific "ordered combination" to identify control flow loops in neural network data flow graphs. The claim approach is not something that can be practically performed in the human mind and is thus not an abstract idea. Regardless, Applicant has further amended the independent claims to recite a specific "ordered combination" to detect one or more control flow loops within one or more data flow graphs which is an inventive concept "significantly more" than an abstract idea. As described in the specification, the claimed approach addresses technical challenges of identifying control flow loops in representations of neural networks that are centralized to data flow. The amended claims recited a specific "ordered combination" of features and a practical application to improve code defining neural networks. Accordingly, the amended pending claims are patent eligible for numerous reasons. Applicant also draws the Examiner's attention to the recent precedential PTAB Decision Ex Parte Desjardins et al., Appeal 2024-000567 (ARP Sept. 26, 2025) (precedential).
(Applicant’s response, pages 10-11).
These arguments are not persuasive in regards to claims 9, 17, and 32 because the analysis of a data flow graph that includes a control flow loop can be performed by a human as a mental process when these concepts are recited at a high degree of generality, as they are in the current claims. Furthermore, while applicant refers to an “ordered combination” of features and a practical application to improve code defining neural networks, applicant’s arguments do not specifically delineate between the elements that are mental processes and elements that are in addition to the abstract idea. Here, the Examiner notes that claims 9, 17, and 32 lack technical features such as the limitations of claim 1 noted above. In light of this, and for the reasons explained in the rejections below, the ordered combination of features in these claims are not significantly more than the mental process pertaining to the analysis of a data flow graph that includes a control flow loop.
Therefore, claims 9, 17, and 32 and their dependent claims remain rejected under § 101.
Claim Objections
Claim 1 is objected to because of the following informalities:
In claim 1, in the “identify” step, the claim language should be corrected to read “…wherein the one or more data flow graphs are generated from program code defining one or more neural networks and comprises nodes representing operations…” (i.e., the word “are” should be added in the position shown). The word “and” should be added because there should be a verb (such as “are”) to link “one or more data flow graphs” with “generated,” similar to how there is a verb (comprises) preceding “nodes.”
Appropriate correction is required.
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 9-23 and 32-38 are rejected under 35 U.S.C. § 101 because the claimed invention is directed to an abstract idea without significantly more.
Independent Claims 9, 17, and 32
Step 2A Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes. A mental process is a process that “can be performed in the human mind, or by a human using a pen and paper…examples of mental processes include observations, evaluations, judgments, and opinions” (MPEP § 2106.04(a)(2)(III), paragraphs 1-2).
Here, independent claims 1, 9, 17, and 32 recite the following limitations that are abstract ideas in the form of mental processes:
Independent Claim 9:
“detection of one or more control flow loops within one or more data flow graphs corresponding to the one or more neural networks, the detection based, at least in part, on performing a depth-first search to detect a control flow loop of the one or more control flow loops within the one or more data flow graphs, the depth-first search starting from an exit node identified in the one or more data flow graphs and proceeding in a reverse direction of data flow to identify loop boundaries encompassing nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search” [These limitations that mental processes that can be performed by observation, evaluation, judgment, and opinion, because they refer to analysis of graphs without any limitation as to the complexity of such graphs. Thus, since the graphs have no specific degree of complexity, and are presented merely as graphs comprising nodes, a human is capable of performing these operations, especially with pen and paper. The limitations of “corresponding to one or more neural networks” and “represent data flow of the one or more neural networks” are part of the mental process because this limitation merely defines the subject matter to which the graph pertains, and does not require any actual neural network computations beyond a mental process. Here, correspondence to a neural network only requires the graph to be related to a neural network. Graphs that are merely related to a neural network can still be analyzed as a mental process in order to find loops in the graph.]
Independent Claim 17:
“perform a depth-first search to detect one or more control flow loops within one or more data flow graphs corresponding to one or more neural networks, the depth-first search starting from an identified exit node and proceeding in a direction opposite data flow to collect nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search” [These limitations are similar to those of claim 9 discussed above and are mental processes for the same reasons, i.e., they refer to analysis and optimization of graphs without any limitation as to the complexity of the graphs or any search algorithm that precludes the limitations from being mental processes.] and
“apply one or more loop or control flow optimizations to the one or more control flow loops detected within the one or more data flow graphs” [These limitations that mental processes that can be performed by observation, evaluation, judgment, and opinion, because they refer to analysis and optimization of graphs without any limitation as to the complexity of the graphs or any search algorithm that precludes the limitations from being mental processes. The general rationale discussed above also apply to these limitations.]
Independent Claim 32:
“performing a depth-first search to detect one or more control flow loops in one or more data flow graphs corresponding to one or more neural networks, the depth-first search starting from an identified exit node and proceeding in a direction opposite data flow to collect nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search” [These limitations are similar to those of claim 9 discussed above and are mental processes for the same reasons, i.e., they refer to analysis and optimization of graphs without any limitation as to the complexity of the graphs or any search algorithm that precludes the limitations from being mental processes.]
“modifying evaluation of operations associated with the detected one or more control flow loops” [This step is recited at a high degree of generality, without specifying any technical implementational details of what the “operations” are and what “modifying evaluation” entails. Therefore, given this limitation reads on a process of manipulating a graph structure in a way that modifies some of its operations, which, as a concept specified at a high level of generality as in the instant claim language, is regarded as a mental process of evaluation.]
Therefore, the independent claims recite a judicial exception.
Step 2A Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No. The judicial exception recited in the above discussed claims is not integrated into a practical application. The independent claims recite the following additional elements, but these additional elements are not sufficient to integrate the judicial exception into a practical application.
“A processor comprising: one or more circuits” (claim 9) and “A system, comprising: one or more processors” (claim 17) [These elements constitute no more than mere instructions to apply the judicial exception using generic computer components (MPEP § 2106.04(d)(I)). These additional elements merely invoke the use of computers or other machinery merely as a tool to perform a mental process, without specifying technical details other than the use of generic computer components. Therefore, these additional elements do not meaningfully limit the claim.]
“modify performance of one or more neural networks based, at least in part, on” (claim 9) and “modifying performance of evaluating output of the one or more neural networks based, at least in part, on” (claim 32). [The additional elements of “modify/modifying performance of…based, at least in part, on” in claims 9, 24, and 32 does no more than generally link the use of a judicial exception to a particular technological environment or field of use (MPEP § 2106.05(h)). These elements merely indicate a field of use or technological environment in which a judicial exception is applied, namely the technological environment of neural networks. The elements recite “based, at least in part, on” which does not specify a specific methodology of using the detected loops. In other “based, at least in part, on” only generally links the detection of the loops (or, in the case of claim 32, also the “modifying evaluation” step) to the execution of a neural network, and does not recite any specific use of those loops and how use of those loops results in modification of the performance. Furthermore, the aspect that is being modified, i.e., “performance of one or more neural networks” or “performance of evaluating output of the one or more neural networks” is recited at a high degree of generality, such that it amounts to no more than invoking the technological environment of neural networks generically. Therefore, the additional elements of “modify/modifying performance of…based, at least in part, on” constitute no more than an attempt to generally link the use of the judicial exception to the technological environment of neural networks. Finally, the claim does not recite how the loops of the graph are tied to the performance of the neural network, since the claim as a whole, only requires the graph to be “corresponding to” one or more neural networks, which does not require a precise relationship between the graph and the neural network.]
Therefore, under MPEP 2106.04(d), the additional elements of the claims do not integrate the judicial exception into a practical application.
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No. The claims do not include additional elements that are sufficient for the claims to amount to significantly more than the judicial exception.
Additional elements that are mere instructions to apply an exception or merely generally linking or generally linking the use of a judicial exception to a particular technological environment or field of use do not constitute significantly more than a judicial exception under MPEP § 2106.05(I)(A). Since the additional elements in the independent claims are all are mere instructions to apply an exception or are merely generally linking or generally linking the use of a judicial exception to a particular technological environment or field of use, they do not constitute significantly more than a judicial exception.
Dependent claims
The remaining dependent claims do not recite additional elements, whether considered individually or in combination, that are sufficient to integrate the judicial exception into a practical application or amount to significantly more than the judicial exception.
Claim 10:
“to identify a region of the one or more data flow graphs that comprises the one or more control flow loops based, at least in part, on nodes traversed during the search of the one or more graphs in the reverse direction of data flow” [These limitations are mental processes practically performed in the human mind by observation, evaluation, judgment, and opinion. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 11:
“the one or more circuits to reconstruct a control flow of the one or more control flow loops detected within the one or more data flow graphs of the one or more neural networks” [These limitations are mental processes practically performed in the human mind by judgment and opinion. The Examiner notes that this claim merely recites the generation of a graph at a high degree of generality, without reciting a specific technical methodology, and without requiring the graph to have a specific technical level of complexity. As such, given that a human is capable of generating a graph, and given that the process of generating a graph is recited at a high degree of generality, the further limitations of this claim are considered to be a mental process. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 12:
“wherein the one or more control flow loops are encoded, in the one or more data flow graphs, as a plurality of nodes comprising an enter node, a loop condition node, and an exit node” [These limitations merely further define the mental process recited in the parent claim and therefore considered to be part of the mental process of the parent claim. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 13:
“to search for operations included in the one or more control flow loops based, at least in part, on a depth-first search, in a reverse direction of data flow, of operations connected to an exit node in the one or more data flow graphs” [These limitations are mental processes practically performed in the human mind by observation, evaluation, and judgment. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 14:
“the one or more circuits to combine two or more of the one or more control flow loops, in response to a determination that the two or more loops share a loop condition node” [These limitations are mental processes practically performed in the human mind by observation, evaluation, judgment, and opinion. The Examiner notes that the instant claim does not recite a particular methodology for combining loops, but instead merely recites the process of doing so at a high degree of generality. As such, a human is considered to be capable of performing the instant process, since a human is capable of analyzing loops in a graph. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 15:
“the one or more circuits to detect a sub-loop inside of a loop of the one or more control flow loops and add the sub- loop to a list of operations determined to be inside of the loop” [These limitations are mental processes practically performed in the human mind by observation, evaluation, judgment, and opinion. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 16:
“to identify nodes associated with a loop condition of the one or more control flow loops based, at least in part, on the search, in the reverse direction of data flow, of the one or more data flow graphs from a starting point corresponding to a loop condition operation” [These limitations are mental processes practically performed in the human mind by observation, evaluation, and judgment. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 18:
“identify a portion of the one or more data flow graphs that comprises the one or more control flow loops based, at least in part, on nodes traversed during a search of the one or more data flow graphs in a reverse direction of data flow; and modify performance of the portion of the one or more data flow graphs” [These limitations are mental processes practically performed in the human mind by observation, evaluation, judgment, and opinion. The Examiner notes that the “modify performance” does not specifically define performance in a technical way. Thus, it is considered to be a mental process. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 19:
“wherein the one or more control flow loops are encoded in the one or more data flow graphs as a plurality of nodes comprising an enter node, a loop condition node, and an exit node.” [These limitations merely further define the mental process recited in the parent claim and therefore considered to be part of the mental process of the parent claim. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 20:
“wherein nodes included in the one or more control flow loops comprise nodes reachable in a search of the one or more data flow graphs in a reverse direction of data flow” [These limitations merely further define the mental process recited in the parent claim and therefore considered to be part of the mental process of the parent claim. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 21:
“the one or more processors to combine two or more loops detected within the one or more data flow graphs and that share a loop condition node.” [These limitations are mental processes practically performed in the human mind by observation, evaluation, judgment, and opinion. The Examiner notes that the instant claim does not recite a particular methodology for combining loops, but instead merely recites the process of doing so at a high degree of generality. As such, a human is considered to be capable of performing the instant process, since a human is capable of analyzing loops in a graph. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 22:
“to identify nodes associated with a loop condition by a search of a graph of the one or more data flow graphs for nodes reachable from a loop condition node” [These limitations are mental processes practically performed in the human mind by observation, evaluation, and judgment. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 23:
“detecting the one or more control flow loops by at least searching the one or more data flow graphs in a reverse direction of data flow” [These limitations are mental processes practically performed in the human mind by observation, evaluation, judgment, and opinion. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 33:
“detecting the one or more control flow loops by at least searching the one or more data flow graphs in a reverse direction of data flow.” [These limitations are mental processes practically performed in the human mind by observation, evaluation, judgment, and opinion. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 34:
“wherein the searching begins at the exit node” [These further limitations merely further define the mental process recited in the parent claim and therefore considered to be part of the mental process of the parent claim. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 35:
“wherein the one or more control flow loops are encoded in the one or more data flow graphs as a plurality of nodes comprising an enter node, a loop condition node, and an exit node” [These further limitations merely further define the mental process recited in the parent claim and therefore considered to be part of the mental process of the parent claim. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 36:
“combining two or more loops detected in the one or more data flow graphs, in response to determining that the two or more loops share a loop condition node” [These limitations are mental processes practically performed in the human mind by observation, evaluation, and judgment. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 37:
“detecting a sub-loop inside of a loop of the one or more control flow loops and adding the sub-loop to a list of operations determined to be inside of the loop” [These limitations are mental processes practically performed in the human mind by observation, evaluation, and judgment. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim 38:
“searching the one or more data flow graphs, in a reverse direction of data flow, from a starting point indicated by a loop condition operation; and associating nodes identified by the searching with a loop condition” [These limitations are mental processes practically performed in the human mind by observation, evaluation, and judgment. This claim does not recite any non-abstract additional elements for purposes of Step 2A Prong Two and Step 2B analysis.]
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-23 and 32-38 are rejected under 35 U.S.C. 103 as being unpatentable over Zheng et al. (US 11,144,291 B1) (“Zheng”) in view of ChoFleming et al. (US 2019/0227777 A1) (“ChoFleming”) and Perron (US 2017/0060552 A1) (“Perron”).
As to claim 1, Zheng teaches a processor comprising:
one or more circuits to: [Col. 13, lines 18-19: “The processor 902 is an integrated circuit device that can execute program code, in the form of instructions.” Col. 21, line 64 to col. 22, line 2: “Any of the methods described herein can be implemented as…instructions which, when the program is executed by one or more computers, cause the one or more computers to carry out the steps of the method.”]
[…] one or more dataflow graphs […] wherein the one or more data flow graphs generated from program code defining one or more neural networks and comprise nodes representing operations and edges representing a data flow of the one or more neural networks; [A “data flow graph” associated with a neural network is disclosed in col. 6, lines 19-23: “FIG. 2 illustrates an example graph 200 of a neural network having multiple operators 202 and multiple constants 204. The operators 202 and the constants 204 are interconnected by arrows which indicate the flow of data within the graph 200.” The graph is a “data flow graph” because it defines the “flow of data,” as stated, specifically the flow of tensor data (e.g., tensors 210 and 212) between operations (e.g., operators 202-2, 202-3, and 202-4), as shown in FIG. 1. Furthermore, col. 6, lines 50-54 teaches: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4.” That is, operators 202-3 and 202-4 are nodes of the data flow graph of FIG. 2. In order to find the loops within these operators, these operators identified. Furthermore, the graph is generated from program code, as described in col. 14, lines 43-49: “In the example of FIG. 9, the compiler 930 includes a first stage 932, a second stage 936, and a third stage 940, which each perform different operations to produce compiled code 944…The first stage 932 can receive and process input code 942. The input code 942 can describe a program in a high-level programming language, such as Java, C++, or Tensorflow, among many other examples.” In other parts of the document, the input code is also described as a “description of the neural network.” This code is used to generate the neural network data flow graph, as disclosed in col. 15, lines 23-30: “the output 938 of the second stage 936 includes the various steps to be performed by components of the acceleration engine 912, in the order that the steps are to be performed. The output 938 can be represented, for example, as a data flow graph, where the nodes in the graph represent memory operations, computations, and other operations…”; ] […]
[…] to identify a control flow loop […] detect one or more control flow loops within the one or more data flow graphs based on the identified nodes […] associated with same loop condition [Detection of a “control flow loop” in the graph is disclosed in col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4. In the illustrated example, the compiler may identify a nested loop 302-1 associated with the operator 202-3 and a nested loop 302-2 associated with the operator 202-4.” That is, as shown in FIGS. 2-3, loops are identified in textual representations of the parts of the graph. Therefore, identifying a nested loop 302-1 identifies a loop in operation 202-3 of the graph 200. The loop is a for loop, which is a type of “control flow loop.”]; and
reconstruct the control flow loops within the one or more data flow graphs […] [Col. 7, lines 43-58: “…When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is the loops 302-1 and 302-2 are combined into a single loop, and this is an optimization of control flow because it reduces the number of data elements. See col. 4, lines 19-22: “The combined nested loop may include a reduced number of defined data elements and/or dependent data elements from the constituent sets of data dependencies.” Here, combining loops constitutes reconstruction.]
apply, to compile the program code defining the one or more neural networks, one or more loop or control flow optimizations to control flow loops reconstructed within the one or more data flow graphs. [Col. 15, lines 42-45: “The output of the third stage 940 is compiled code 944, which may include machine instructions in binary format. In some examples, the compiled code 944 can be stored in the processor memory 904.” This step refers to the compilation of the combined nested loop, as disclosed in claim 1: “generating machine instructions for the neural network based on the combined nested loop.” That is, the compilation of the neural network based on the combined loop constitutes “to apply” the combined (reconstructed) loops.]
Zheng does not teach:
(1) “identify a node of the one or more flow graphs as an exit node of a control flow”;
(2) the limitation that identification of the control flow loop is the result of “perform a depth-first search of the one or more data flow graphs” to identify the loop;
(3) “the depth-first search comprising, starting from the identified exit node and proceeding in a direction opposite the data flow: identify a first set of nodes of the one or more data flow graphs associated with the identified exit node; identify a node of the one or more data flow graphs as a loop condition node; and identify a second set of nodes of the one or more data flow graphs associated with the identified loop condition node”; and
(4) the reconstruction being “based on the identified exit node, the identified first set of nodes, the identified loop condition node, and the identified second set of nodes.”
ChoFleming teaches “identify a node of the one or more flow graphs as an exit node of a control flow” [[0032]: “In the example of FIG. 1, the backedge detector 102 obtains an example input DFG 126. The example input DFG 126 is generated by the compiler 100 based on source code in at least one of a high-level programming language…The example input DFG 126 includes a noncritical path (e.g., an example noncritical path 202 of FIG. 2) formed by operations o1, o6, and o5. The example input DFG 126 also includes a critical path (e.g., an example critical path 204 of FIG. 2) formed by operations o1-o5.” Note that “DFG” refers to data flow graph, and that o5 is an exit node and is part of a loop. See [0038]: “FIG. 2C shows the example backedge 128 that represents a loop or transfer of execution control from the ending node o5 to the second node o2.” [0060]: “For example, in the intermediate DFG 130 shown in FIG. 1, the buffer inserter 104 labels node o5 as a loop end node by storing a loop end identifier in the memory 124 in association with the instruction(s) corresponding to the node o5.”] “perform a depth-first search of the one or more data flow graphs” [[0062]: “FIG. 6 is an example DFG 600 showing backedges annotated by the example backedge detector 102 of FIG. 1 using a Depth-First Search (DFS) technique.”] “the depth-first search comprising, […]: identify a first set of nodes of the one or more data flow graphs associated with the identified exit node; [See [0038] and [0060], and [0033]: “The example buffer inserter 104 also labels the source node of the removed backedge as a loop end node (e.g., the fifth node o5) and labels the sink node of the removed backedge as a loop start node (e.g., the second node o2) in the intermediate DFG 130.” Nodes that are part of the operation of the loop that includes the loop end are regarded as “associated with” the exit node o5. See also [0037]: “identifying the connection arc between the second node o2 and the fifth node o5 as being a backedge 128.”] identify a node of the one or more data flow graphs as a loop condition node; and identify a second set of nodes of the one or more data flow graphs associated with the identified loop condition node” [In the illustration in FIG. 1, the exit node can also be regarded as a “condition node,” since it determines whether the backedge 128 is performed. Therefore, the nodes o2-o5 can also be regarded as a second set of nodes “associated” with the condition of o5. Condition nodes are disclosed in [0054]: “FIG. 4 illustrates example source code 402 in the C programming language for a cyclic computer program containing a while loop…cmp_0 (in the assembly code 404) which starts with an initial value of 0 and gets a new value based on a loop termination condition comparison (e.g., i<10 or cmplts64 cmp, i_next_1, 10 in the assembly code 404). The add operation in the DFG 406 computes the potential next value of i, and the copy operation in the DFG 406 takes a value and produces multiple copies of its input to feed other operations. The cmp operation of the DFG 406 compares the i_next with the loop boundary 10 (e.g., cmplts64 cmp, I next 1, 10 in the assembly code 404). The result of the cmp operation is copied to two different destinations as values cmp_0 and cmp_1. The cmp_0 value is used to switch the i_next value to i_loopback or to i_result based on the cmplts output which triggers the output signal.” That is, the “CMP” node as shown in FIG. 4 can be regarded as a comparison node, and nodes that used with such a node, such as COPY and SWITCH are “associated” with the CMP node.], and reconstruction “based on the identified exit node, the identified first set of nodes, the identified loop condition node, and the identified second set of nodes.” [[0033]: “The buffer inserter 104 then uses the intermediate DFG 130 to perform buffer insertion analyses in accordance with examples disclosed herein, and inserts two example buffers 136, 138 in the example input DFG 126 based on the buffer insertion analyses to generate an example output DFG 132.” That is, generation of a new DFG is considered to be analogous to the context of reconstruction/optimization. Since the new DFG includes the nodes o1-o6 in FIG. 1, for example, it is based on the nodes of the input DFG.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Zheng with the teachings of ChoFleming by implementing the technique of performing a depth-first search of the data flow graph to identify nodes of the graph, so as to arrive at the above limitations of the claimed invention. The motivation would have been to improve the performance of an input data flow graph through the detection of backedges (see ChoFleming, [0034]: “to improve performance of the input DFG 126 which is targeted to be executed by the CGRA device 142, the backedge detector 102 analyzes the input DFG 126 to detect backedges.”).
The combination of references thus far does not explicitly teach the remaining limitation of “starting from the identified exit node and proceeding in a direction opposite the data flow.”
Perron teaches “starting from the identified exit node and proceeding in a direction opposite the data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of references combined thus far with the teachings of Perron by implementing the depth-first search as a post-order search that starts at the exit node, so as to arrive at the claimed invention. The motivation for doing so would have been to implement a particular methodology for performing a depth-first search that enables analysis of a program on a node-by-node-basis (see Perron, [0023]: “The entire program may be systematically analyzed on a node-by-node basis by performing a depth-first search.”).
As to claim 2, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 1, the one or more circuits to identify a portion of the one or more data flow graphs that comprise the one or more control flow loops, [Zheng, Col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4. In the illustrated example, the compiler may identify a nested loop 302-1 associated with the operator 202-3 and a nested loop 302-2 associated with the operator 202-4.” That is, as shown in FIGS. 2-3, loops are identified in textual representations of the parts of the graph. Therefore, identifying a nested loop 302-1 identifies a loop in operation 202-3 of the graph 200, where operation 202-3 is a portion of the graph.]
Perron further teaches “the identified portion including nodes traversed by a search of the one or more data flow graphs in a reverse direction of data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 3, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 1, the one or more circuits to reconstruct a control flow of the one or more control flow loops detected within the one or more data flow graphs of the one or more neural networks. [Zheng, col. 7, lines 43-58: “FIG. 4 illustrates an example of a textual representation for a combined operator 402 formed by combining the operators 202-3 and 202-4 (or similarly, by combining the nested loops 302-1 and 302-2). The compiler may analyze a symbolic model associated with the operator 202-3 and a symbolic model associated with the operator 202-4 to determine that the nested loops 302-1 and 302-2 associated with the operators 202-3 and 202-4 are combinable. When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404…” That is, the separate loops and their associated control flows are reconstructed into a single fused set of nested loops.]
As to claim 4, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 1, as set forth above.
ChoFleming further teaches “wherein the one or more control flow loops are encoded, in the one or more data flow graphs, as a plurality of nodes comprising an enter node, a loop condition node, and an exit node.” [As noted in the rejection of the independent claim, ChoFlemon teaches loops with an enter node (e.g., o2 of FIG. 1), a loop condition node (e.g., o5 of FIG. 1 and CMP of FIG. 4), and an exit node (e.g., o5 of FIG. 1).]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of ChoFleming, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 5, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 1, as set forth above.
Perron further teaches “the one or more circuits to search for nodes included in the one or more control flow loops based, at least in part, on a search for nodes reachable in a depth-first search, in a reverse direction of data flow, starting from an exit node in the one or more data flow graphs.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 6, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 1, the one or more circuits to combine two or more loops detected within the one or more data flow graphs, [Zheng, col. 7, lines 43-58: “…When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is the loops 302-1 and 302-2 are combined into a single loop.], in response to a determination that the two or more loops share a loop condition node. [Zheng, col. 7, lines 43-58: “The compiler may analyze a symbolic model associated with the operator 202-3 and a symbolic model associated with the operator 202-4 to determine that the nested loops 302-1 and 302-2 associated with the operators 202-3 and 202-4 are combinable.” Col. 9, lines 47-51: “In some embodiments, the compiler may determine that the loop order 504-1 is combinable with the loop order 504-2 if the indices are identical, the orders associated with the indices are identical, and the ranges of the indices are identical.” That is, referring to the code in Zheng, FIG. 3, the indices and their orders, and the ranges of those indices define the condition of the “for” loops. In the case of loop 302-1 and 302-2, the expression “for (W=1:16)” has an identical index and an identical range. This expression “for (W=1:16)” also constitutes a “conditional node,” noting that it is considered to be a “node” because it is an operation that is related to another operation, and that “node” in this context does not require a specific format in relation to other nodes.]
As to claim 7, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 1, the one or more circuits to detect a sub-loop inside of a loop of the one or more control flow loops and add the sub- loop to a list of operations determined to be inside of the loop. [Zheng, col. 2, lines 33-35: “In a simple example, a nested loop includes a single outer loop and a single inner loop within the body of the outer loop.” Furthermore, in the example of combining the loops shown in FIGS. 3-4, the nested loops were determined to have the same indices and order. See Zheng, col. 9, lines 47-51: “In some embodiments, the compiler may determine that the loop order 504-1 is combinable with the loop order 504-2 if the indices are identical, the orders associated with the indices are identical, and the ranges of the indices are identical.” As such, as shown in FIG. 4, all sub-loops are identified and added to a list of operations determined to be included in the fused loop.]
As to claim 8, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 1, the one or more circuits to identify nodes associated with a loop condition [Zheng, col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4.” That is, operators 202-3 and 202-4 are nodes of the data flow graph of FIG. 2. In order to find the loops within these operators, these operators (nodes) identified. Furthermore, these nodes are associated with a loop condition because they include for-loops, which have loop conditions.]
Perron further teaches “based, at least in part, on a search for nodes reachable in a search, in a reverse direction of data flow, of the one or more data flow graphs from a starting point corresponding to a loop condition operation.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2. The limitation of “corresponding to a loop condition operation” is met in the combined teachings of the references because the graph in FIG. 2 of Zheng has nodes (e.g., nodes 202-2 and 202-3) that each have a loop condition. Thus, in the combined teachings of the references, a search from node 202-3 to 202-2 would result in a starting point of node 202-3, which includes a set of loops and is thus a node that is corresponding to a loop condition operation.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 9, Zheng teaches a processor, comprising:
one or more circuits [Col. 13, lines 18-19: “The processor 902 is an integrated circuit device that can execute program code, in the form of instructions.” Col. 21, line 64 to col. 22, line 2: “Any of the methods described herein can be implemented as…instructions which, when the program is executed by one or more computers, cause the one or more computers to carry out the steps of the method.”] to modify performance of one or more neural networks based, [Col. 7, lines 50-58: “When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is, reducing the number of operations constitutes modifying the performance of the neural network. See also col. 8, lines 3-12, which teaches reduction of memory references: “By combining the nested loops 302-1 and 302-2, the operations to store and read Data 6 are eliminated, causing the number of memory references to be significantly reduced.” Furthermore, the combining of the loops is based on detecting the loops.] at least in part, on detection of one or more control flow loops within one or more data flow graphs corresponding to the one or more neural networks, [A “data flow graph” associated with a neural network is disclosed in col. 6, lines 19-23: “FIG. 2 illustrates an example graph 200 of a neural network having multiple operators 202 and multiple constants 204. The operators 202 and the constants 204 are interconnected by arrows which indicate the flow of data within the graph 200.” The graph is a “data flow graph” because it defines the “flow of data,” as stated, specifically the flow of tensor data (e.g., tensors 210 and 212) between operations (e.g., operators 202-2, 202-3, and 202-4), as shown in FIG. 1. Furthermore, detection of a “control flow loop” in the graph is disclosed in col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4. In the illustrated example, the compiler may identify a nested loop 302-1 associated with the operator 202-3 and a nested loop 302-2 associated with the operator 202-4.” That is, as shown in FIGS. 2-3, loops are identified in textual representations of the parts of the graph. Therefore, identifying a nested loop 302-1 identifies a loop in operation 202-3 of the graph 200. The loop is a for loop, which is a type of “control flow loop.”] […]
Zheng does not teach the limitation of “the detection based, at least in part, on performing a depth-first search to detect a control flow loop of the one or more control flow loops within the one or more data flow graphs, the depth-first search starting from an exit node identified in the one or more data flow graphs and proceeding in a reverse direction of data flow to identify loop boundaries encompassing nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search.”
ChoFleming teaches “the detection based, at least in part, on performing a depth-first search to detect a control flow loop of the one or more control flow loops within the one or more data flow graphs” [[0062]: “FIG. 6 is an example DFG 600 showing backedges annotated by the example backedge detector 102 of FIG. 1 using a Depth-First Search (DFS) technique.” The process is performed on a data flow graph to detect control flow loops. See [0032]: “In the example of FIG. 1, the backedge detector 102 obtains an example input DFG 126. The example input DFG 126 is generated by the compiler 100 based on source code in at least one of a high-level programming language…The example input DFG 126 includes a noncritical path (e.g., an example noncritical path 202 of FIG. 2) formed by operations o1, o6, and o5. The example input DFG 126 also includes a critical path (e.g., an example critical path 204 of FIG. 2) formed by operations o1-o5.” Note that “DFG” refers to data flow graph, and that o5 is an exit node and is part of a loop. See [0038]: “FIG. 2C shows the example backedge 128 that represents a loop or transfer of execution control from the ending node o5 to the second node o2.” [0060]: “For example, in the intermediate DFG 130 shown in FIG. 1, the buffer inserter 104 labels node o5 as a loop end node by storing a loop end identifier in the memory 124 in association with the instruction(s) corresponding to the node o5.”] “to identify loop boundaries encompassing nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search [See [0038], [0060], and [0033]: “The example buffer inserter 104 also labels the source node of the removed backedge as a loop end node (e.g., the fifth node o5) and labels the sink node of the removed backedge as a loop start node (e.g., the second node o2) in the intermediate DFG 130.” Nodes that are part of the operation of the loop that includes the loop end are regarded as “associated with” the exit node o5. See also [0037]: “identifying the connection arc between the second node o2 and the fifth node o5 as being a backedge 128.” Furthermore, o2 and o5 constitute “loop boundaries,” since they are on the boundary between the loop and the other parts of the graph (o1 and o6). Furthermore, in the illustration in FIG. 1, the exit node can also be regarded as a “condition node,” since it determines whether the backedge 128 is performed. Therefore, the nodes o2-o5 can also be regarded as a set of nodes “associated” with the condition of o5. Condition nodes are disclosed in [0054]: “FIG. 4 illustrates example source code 402 in the C programming language for a cyclic computer program containing a while loop…cmp_0 (in the assembly code 404) which starts with an initial value of 0 and gets a new value based on a loop termination condition comparison (e.g., i<10 or cmplts64 cmp, i_next_1, 10 in the assembly code 404). The add operation in the DFG 406 computes the potential next value of i, and the copy operation in the DFG 406 takes a value and produces multiple copies of its input to feed other operations. The cmp operation of the DFG 406 compares the i_next with the loop boundary 10 (e.g., cmplts64 cmp, I next 1, 10 in the assembly code 404). The result of the cmp operation is copied to two different destinations as values cmp_0 and cmp_1. The cmp_0 value is used to switch the i_next value to i_loopback or to i_result based on the cmplts output which triggers the output signal.” That is, the “CMP” node as shown in FIG. 4 can be regarded as a comparison node, and nodes that used with such a node, such as COPY and SWITCH are “associated” with the CMP node.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Zheng with the teachings of ChoFleming by implementing the technique of performing a depth-first search of the data flow graph to identify nodes of the graph, so as to arrive at the above limitations of the claimed invention. The motivation would have been to improve the performance of an input data flow graph through the detection of backedges (see ChoFleming, [0034]: “to improve performance of the input DFG 126 which is targeted to be executed by the CGRA device 142, the backedge detector 102 analyzes the input DFG 126 to detect backedges.”).
The combination of references thus far does not explicitly teach the remaining limitation of “the depth-first search starting from an exit node identified in the one or more data flow graphs and proceeding in a reverse direction of data flow.”
Perron teaches “the depth-first search starting from an exit node identified in the one or more data flow graphs and proceeding in a reverse direction of data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of references combined thus far with the teachings of Perron by implementing the depth-first search as a post-order search that starts at the exit node, so as to arrive at the claimed invention. The motivation for doing so would have been to implement a particular methodology for performing a depth-first search that enables analysis of a program on a node-by-node-basis (see Perron, [0023]: “The entire program may be systematically analyzed on a node-by-node basis by performing a depth-first search.”).
As to claim 10, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 9, the one or more circuits to identify a region of the one or more data flow graphs that comprises the one or more control flow loops [Zheng, Col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4. In the illustrated example, the compiler may identify a nested loop 302-1 associated with the operator 202-3 and a nested loop 302-2 associated with the operator 202-4.” That is, as shown in FIGS. 2-3, loops are identified in textual representations of the parts of the graph. Therefore, identifying a nested loop 302-1 identifies a loop in operation 202-3 of the graph 200, where operation 202-3 is a portion of the graph.]
Perron further teaches “based, at least in part, on nodes traversed during the search of the one or more graphs in the reverse direction of data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The rationale for obviousness is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 11, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 9, the one or more circuits to reconstruct a control flow of the one or more control flow loops detected within the one or more data flow graphs of the one or more neural networks. [Zheng, col. 7, lines 43-58: “FIG. 4 illustrates an example of a textual representation for a combined operator 402 formed by combining the operators 202-3 and 202-4 (or similarly, by combining the nested loops 302-1 and 302-2). The compiler may analyze a symbolic model associated with the operator 202-3 and a symbolic model associated with the operator 202-4 to determine that the nested loops 302-1 and 302-2 associated with the operators 202-3 and 202-4 are combinable. When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404…” That is, the separate loops and their associated control flows are reconstructed into a single fused set of nested loops.]
As to claim 12, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 9, as set forth above.
ChoFleming further teaches “wherein the one or more control flow loops are encoded, in the one or more data flow graphs, as a plurality of nodes comprising an enter node, a loop condition node, and an exit node.” [As noted in the rejection of the independent claim, ChoFlemon teaches loops with an enter node (e.g., o2 of FIG. 1), a loop condition node (e.g., o5 of FIG. 1 and CMP of FIG. 4), and an exit node (e.g., o5 of FIG. 1).]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of ChoFleming, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 13, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 9, as set forth above.
Perron further teaches “the one or more circuits to search for operations included in the one or more control flow loops based, at least in part, on a depth-first search, in a reverse direction of data flow, of operations connected to an exit node in the one or more data flow graphs.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 14, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 9, the one or more circuits to combine two or more of the one or more control flow loops, [Zheng, col. 7, lines 43-58: “…When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is the loops 302-1 and 302-2 are combined into a single loop.] in response to a determination that the two or more loops share a loop condition node. [Zheng, col. 7, lines 43-58: “The compiler may analyze a symbolic model associated with the operator 202-3 and a symbolic model associated with the operator 202-4 to determine that the nested loops 302-1 and 302-2 associated with the operators 202-3 and 202-4 are combinable.” Col. 9, lines 47-51: “In some embodiments, the compiler may determine that the loop order 504-1 is combinable with the loop order 504-2 if the indices are identical, the orders associated with the indices are identical, and the ranges of the indices are identical.” That is, referring to the code in Zheng, FIG. 3, the indices and their orders, and the ranges of those indices define the condition of the “for” loops. In the case of loop 302-1 and 302-2, the expression “for (W=1:16)” has an identical index and an identical range. This expression “for (W=1:16)” also constitutes a “conditional node,” noting that it is considered to be a “node” because it is an operation that is related to another operation, and that “node” in this context does not require a specific format in relation to other nodes.]
As to claim 15, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 9, the one or more circuits to detect a sub-loop inside of a loop of the one or more control flow loops and add the sub- loop to a list of operations determined to be inside of the loop. [These limitations have the same wording as the limitations recited in claim 7, and are therefore taught by Zheng for the reasons given for the limitations of claim 7.]
As to claim 16, the combination of Zheng, ChoFleming, and Perron teaches the processor of claim 9, the one or more circuits to identify nodes associated with a loop condition of the one or more control flow loops [Zheng, col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4.” That is, operators 202-3 and 202-4 are nodes of the data flow graph of FIG. 2. In order to find the loops within these operators, these operators (nodes) identified. Furthermore, these nodes are associated with a loop condition because they include for-loops, which have loop conditions.]
Perron further teaches “based, at least in part, on the search, in the reverse direction of data flow, of the one or more data flow graphs from a starting point corresponding to a loop condition operation.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2. The limitation of “corresponding to a loop condition operation” is met in the combined teachings of the references because the graph in FIG. 2 of Zheng has nodes (e.g., nodes 202-2 and 202-3) that each have a loop condition. Thus, in the combined teachings of the references, a search from node 202-3 to 202-2 would result in a starting point of node 202-3, which includes a set of loops and is thus a node that is corresponding to a loop condition operation.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The rationale for obviousness is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 17, Zheng teaches a system, comprising:
one or more processors to: [Col. 13, lines 18-19: “The processor 902 is an integrated circuit device that can execute program code, in the form of instructions.” Col. 21, line 64 to col. 22, line 2: “Any of the methods described herein can be implemented as…instructions which, when the program is executed by one or more computers, cause the one or more computers to carry out the steps of the method.”]
[…] to detect one or more control flow loops within one or more data flow graphs corresponding to one or more neural networks, [A “data flow graph” associated with a neural network is disclosed in col. 6, lines 19-23: “FIG. 2 illustrates an example graph 200 of a neural network having multiple operators 202 and multiple constants 204. The operators 202 and the constants 204 are interconnected by arrows which indicate the flow of data within the graph 200.” The graph is a “data flow graph” because it defines the “flow of data,” as stated, specifically the flow of tensor data (e.g., tensors 210 and 212) between operations (e.g., operators 202-2, 202-3, and 202-4), as shown in FIG. 1. Furthermore, detection of a “control flow loop” in the graph is disclosed in col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4. In the illustrated example, the compiler may identify a nested loop 302-1 associated with the operator 202-3 and a nested loop 302-2 associated with the operator 202-4.” That is, as shown in FIGS. 2-3, loops are identified in textual representations of the parts of the graph. Therefore, identifying a nested loop 302-1 identifies a loop in operation 202-3 of the graph 200. The loop is a for loop, which is a type of “control flow loop.”] […]; and
apply one or more loop or control flow optimizations to the one or more control flow loops detected within the one or more data flow graphs. [Col. 7, lines 50-58: “When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is, reducing the number of operations constitutes modifying the performance of the neural network. See also col. 8, lines 3-12, which teaches reduction of memory references: “By combining the nested loops 302-1 and 302-2, the operations to store and read Data 6 are eliminated, causing the number of memory references to be significantly reduced.” Furthermore, the combining of the loops is based on detecting the loops.]
Zheng does not teach the limitations of:
(1) “perform a depth-first search” to detect the one or more control flow loops; and
(2) “the depth-first search starting from an identified exit node and proceeding in a direction opposite data flow to collect nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search.”
ChoFleming teaches “perform a depth-first search” to detect the one or more control flow loops [[0062]: “FIG. 6 is an example DFG 600 showing backedges annotated by the example backedge detector 102 of FIG. 1 using a Depth-First Search (DFS) technique.” The process is performed on a data flow graph to detect control flow loops. See [0032]: “In the example of FIG. 1, the backedge detector 102 obtains an example input DFG 126. The example input DFG 126 is generated by the compiler 100 based on source code in at least one of a high-level programming language…The example input DFG 126 includes a noncritical path (e.g., an example noncritical path 202 of FIG. 2) formed by operations o1, o6, and o5. The example input DFG 126 also includes a critical path (e.g., an example critical path 204 of FIG. 2) formed by operations o1-o5.” Note that “DFG” refers to data flow graph, and that o5 is an exit node and is part of a loop. See [0038]: “FIG. 2C shows the example backedge 128 that represents a loop or transfer of execution control from the ending node o5 to the second node o2.” [0060]: “For example, in the intermediate DFG 130 shown in FIG. 1, the buffer inserter 104 labels node o5 as a loop end node by storing a loop end identifier in the memory 124 in association with the instruction(s) corresponding to the node o5.”] “the depth-first search […] to collect nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search” [See [0038], [0060], and [0033]: “The example buffer inserter 104 also labels the source node of the removed backedge as a loop end node (e.g., the fifth node o5) and labels the sink node of the removed backedge as a loop start node (e.g., the second node o2) in the intermediate DFG 130.” Nodes that are part of the operation of the loop that includes the loop end are regarded as “associated with” the exit node o5. See also [0037]: “identifying the connection arc between the second node o2 and the fifth node o5 as being a backedge 128.” Furthermore, o2 and o5 constitute “loop boundaries,” since they are on the boundary between the loop and the other parts of the graph (o1 and o6). Furthermore, in the illustration in FIG. 1, the exit node can also be regarded as a “condition node,” since it determines whether the backedge 128 is performed. Therefore, the nodes o2-o5 can also be regarded as a set of nodes “associated” with the condition of o5. Condition nodes are disclosed in [0054]: “FIG. 4 illustrates example source code 402 in the C programming language for a cyclic computer program containing a while loop…cmp_0 (in the assembly code 404) which starts with an initial value of 0 and gets a new value based on a loop termination condition comparison (e.g., i<10 or cmplts64 cmp, i_next_1, 10 in the assembly code 404). The add operation in the DFG 406 computes the potential next value of i, and the copy operation in the DFG 406 takes a value and produces multiple copies of its input to feed other operations. The cmp operation of the DFG 406 compares the i_next with the loop boundary 10 (e.g., cmplts64 cmp, I next 1, 10 in the assembly code 404). The result of the cmp operation is copied to two different destinations as values cmp_0 and cmp_1. The cmp_0 value is used to switch the i_next value to i_loopback or to i_result based on the cmplts output which triggers the output signal.” That is, the “CMP” node as shown in FIG. 4 can be regarded as a comparison node, and nodes that used with such a node, such as COPY and SWITCH are “associated” with the CMP node.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Zheng with the teachings of ChoFleming by implementing the technique of performing a depth-first search of the data flow graph to identify nodes of the graph, so as to arrive at the above limitations of the claimed invention. The motivation would have been to improve the performance of an input data flow graph through the detection of backedges (see ChoFleming, [0034]: “to improve performance of the input DFG 126 which is targeted to be executed by the CGRA device 142, the backedge detector 102 analyzes the input DFG 126 to detect backedges.”).
The combination of references thus far does not explicitly teach the remaining limitation of the depth-first search “starting from an identified exit node and proceeding in a direction opposite data flow.”
Perron teaches “starting from an identified exit node and proceeding in a direction opposite data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of references combined thus far with the teachings of Perron by implementing the depth-first search as a post-order search that starts at the exit node, so as to arrive at the claimed invention. The motivation for doing so would have been to implement a particular methodology for performing a depth-first search that enables analysis of a program on a node-by-node-basis (see Perron, [0023]: “The entire program may be systematically analyzed on a node-by-node basis by performing a depth-first search.”).
As to claim 18, the combination of Zheng, ChoFleming, and Perron teaches the system of claim 17, the one or more processors to: identify a portion of the one or more data flow graphs that comprises the one or more control flow loops […] [Zheng, Col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4. In the illustrated example, the compiler may identify a nested loop 302-1 associated with the operator 202-3 and a nested loop 302-2 associated with the operator 202-4.” That is, as shown in FIGS. 2-3, loops are identified in textual representations of the parts of the graph. Therefore, identifying a nested loop 302-1 identifies a loop in operation 202-3 of the graph 200, where operation 202-3 is a portion of the graph.]; and modify performance of the portion of the one or more data flow graphs. [Zheng, col. 7, lines 50-58: “When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is, reducing the number of operations constitutes modifying the performance of the neural network. See also Zheng, col. 8, lines 3-12, which teaches reduction of memory references: “By combining the nested loops 302-1 and 302-2, the operations to store and read Data 6 are eliminated, causing the number of memory references to be significantly reduced.” Furthermore, the combining of the loops is based on detecting the loops.]
Perron further teaches “based, at least in part, on nodes traversed during a search of the one or more data flow graphs in a reverse direction of data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 19, the combination of Zheng, ChoFleming, and Perron teaches the system of claim 17, as set forth above.
ChoFleming further teaches “wherein the one or more control flow loops are encoded in the one or more data flow graphs as a plurality of nodes comprising an enter node, a loop condition node, and an exit node.” [As noted in the rejection of the independent claim, ChoFlemon teaches loops with an enter node (e.g., o2 of FIG. 1), a loop condition node (e.g., o5 of FIG. 1 and CMP of FIG. 4), and an exit node (e.g., o5 of FIG. 1).]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of ChoFleming, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 20, the combination of Zheng, ChoFleming, and Perron teaches the system of claim 17, wherein nodes included in the one or more control flow loops comprise nodes reachable in a search of the one or more data flow graphs in a reverse direction of data flow. [This limitation of “reachable” as used in the instant claim language only requires the property of being capable of being reached. Here, referring to the graph in Zheng, FIG. 2, the node 202-3 is a loop condition node since it includes a loop with a loop condition, and it is possible to reach the nodes 202-2 and 2-201 using the upward traversal taught in Enrici.]
As to claim 21, the combination of Zheng, ChoFleming, and Perron teaches the system of claim 17, the one or more processors to combine two or more loops detected within the one or more data flow graphs [Zheng, col. 7, lines 43-58: “…When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is the loops 302-1 and 302-2 are combined into a single loop.], and that share a loop condition node. [Zheng, col. 7, lines 43-58: “The compiler may analyze a symbolic model associated with the operator 202-3 and a symbolic model associated with the operator 202-4 to determine that the nested loops 302-1 and 302-2 associated with the operators 202-3 and 202-4 are combinable.” Col. 9, lines 47-51: “In some embodiments, the compiler may determine that the loop order 504-1 is combinable with the loop order 504-2 if the indices are identical, the orders associated with the indices are identical, and the ranges of the indices are identical.” That is, referring to the code in Zheng, FIG. 3, the indices and their orders, and the ranges of those indices define the condition of the “for” loops. In the case of loop 302-1 and 302-2, the expression “for (W=1:16)” has an identical index and an identical range. This expression “for (W=1:16)” also constitutes a “conditional node,” noting that it is considered to be a “node” because it is an operation that is related to another operation, and that “node” in this context does not require a specific format in relation to other nodes.]
As the claim 22, the combination of Zheng, ChoFleming, and Perron teaches the system of claim 17, the one or more processors to identify nodes associated with a loop condition [Zheng, col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4.” That is, operators 202-3 and 202-4 are nodes of the data flow graph of FIG. 2. In order to find the loops within these operators, these operators identified.]
Perron further teaches “by a search of a graph of the one or more data flow graphs for nodes reachable from a loop condition node.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2. This limitation of “reachable” as used in the instant claim language only requires the property of being capable of being reached. Here, referring to the graph in Zheng, FIG. 2, the node 202-3 is a loop condition node since it includes a loop with a loop condition, and it is possible to reach the nodes 202-2 and 2-201.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The rationale for obviousness is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 23, the combination of Zheng, ChoFleming, and Perron teaches the system of claim 17, the one or more processors to detect a sub-loop inside of a loop of the one or more control flow loops and add the sub- loop to a list of operations determined to be inside of the loop. [Zheng, col. 2, lines 33-35: “In a simple example, a nested loop includes a single outer loop and a single inner loop within the body of the outer loop.” Furthermore, in the example of combining the loops shown in FIGS. 3-4, the nested loops were determined to have the same indices and order. See Zheng, col. 9, lines 47-51: “In some embodiments, the compiler may determine that the loop order 504-1 is combinable with the loop order 504-2 if the indices are identical, the orders associated with the indices are identical, and the ranges of the indices are identical.” As such, as shown in FIG. 4, all sub-loops are identified and added to a list of operations determined to be included in the fused loop.]
As to claim 32, Zheng teaches a method, comprising:
[…] to detect one or more control flow loops in one or more data flow graphs corresponding to one or more neural networks, the detecting comprising identify notes of the one or more data flow graphs associated with [A “data flow graph” associated with a neural network is disclosed in col. 6, lines 19-23: “FIG. 2 illustrates an example graph 200 of a neural network having multiple operators 202 and multiple constants 204. The operators 202 and the constants 204 are interconnected by arrows which indicate the flow of data within the graph 200.” The graph is a “data flow graph” because it defines the “flow of data,” as stated, specifically the flow of tensor data (e.g., tensors 210 and 212) between operations (e.g., operators 202-2, 202-3, and 202-4), as shown in FIG. 1. Furthermore, detection of a “control flow loop” in the graph is disclosed in col. 6, lines 50-54: “FIG. 3 illustrates an example of a textual representation of the graph 200 for the operators 202-3 and 202-4. In the illustrated example, the compiler may identify a nested loop 302-1 associated with the operator 202-3 and a nested loop 302-2 associated with the operator 202-4.” That is, as shown in FIGS. 2-3, loops are identified in textual representations of the parts of the graph. Therefore, identifying a nested loop 302-1 identifies a loop in operation 202-3 of the graph 200. The loop is a for loop, which is a type of “control flow loop.”] […]; and
modifying performance of evaluating output of the one or more neural networks based, at least in part, on modifying evaluation of operations associated with the detected one or more control flow loops. [Col. 7, lines 50-58: “When the nested loops 302-1 and 302-2 are combined, the set of operations performed by each of the nested loops 302-1 and 302-2 are combined within a single fused nested loop 404. In some instances, the set of operations performed by the fused nested loop 404 may optionally be reduced such that the number of operations performed by the fused nested loop 404 is fewer than the sum of the number of operations performed by the nested loops 302-1 and 302-2.” That is, reducing the number of operations constitutes modifying the performance of the neural network. See also col. 8, lines 3-12, which teaches reduction of memory references: “By combining the nested loops 302-1 and 302-2, the operations to store and read Data 6 are eliminated, causing the number of memory references to be significantly reduced.” Furthermore, the combining of the loops is based on detecting the loops.]
Zheng does not teach the limitations of:
(1) “perform a depth-first search” to detect the one or more control flow loops; and
(2) “the depth-first search starting from an identified exit node and proceeding in a direction opposite data flow to collect nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search.”
ChoFleming teaches “perform a depth-first search” to detect the one or more control flow loops [[0062]: “FIG. 6 is an example DFG 600 showing backedges annotated by the example backedge detector 102 of FIG. 1 using a Depth-First Search (DFS) technique.” The process is performed on a data flow graph to detect control flow loops. See [0032]: “In the example of FIG. 1, the backedge detector 102 obtains an example input DFG 126. The example input DFG 126 is generated by the compiler 100 based on source code in at least one of a high-level programming language…The example input DFG 126 includes a noncritical path (e.g., an example noncritical path 202 of FIG. 2) formed by operations o1, o6, and o5. The example input DFG 126 also includes a critical path (e.g., an example critical path 204 of FIG. 2) formed by operations o1-o5.” Note that “DFG” refers to data flow graph, and that o5 is an exit node and is part of a loop. See [0038]: “FIG. 2C shows the example backedge 128 that represents a loop or transfer of execution control from the ending node o5 to the second node o2.” [0060]: “For example, in the intermediate DFG 130 shown in FIG. 1, the buffer inserter 104 labels node o5 as a loop end node by storing a loop end identifier in the memory 124 in association with the instruction(s) corresponding to the node o5.”] “the depth-first search […] to collect nodes of the one or more data flow graphs associated with the identified exit node and nodes of the one or more data flow graphs associated with a loop condition node identified along the depth-first search” [See [0038], [0060], and [0033]: “The example buffer inserter 104 also labels the source node of the removed backedge as a loop end node (e.g., the fifth node o5) and labels the sink node of the removed backedge as a loop start node (e.g., the second node o2) in the intermediate DFG 130.” Nodes that are part of the operation of the loop that includes the loop end are regarded as “associated with” the exit node o5. See also [0037]: “identifying the connection arc between the second node o2 and the fifth node o5 as being a backedge 128.” Furthermore, o2 and o5 constitute “loop boundaries,” since they are on the boundary between the loop and the other parts of the graph (o1 and o6). Furthermore, in the illustration in FIG. 1, the exit node can also be regarded as a “condition node,” since it determines whether the backedge 128 is performed. Therefore, the nodes o2-o5 can also be regarded as a set of nodes “associated” with the condition of o5. Condition nodes are disclosed in [0054]: “FIG. 4 illustrates example source code 402 in the C programming language for a cyclic computer program containing a while loop…cmp_0 (in the assembly code 404) which starts with an initial value of 0 and gets a new value based on a loop termination condition comparison (e.g., i<10 or cmplts64 cmp, i_next_1, 10 in the assembly code 404). The add operation in the DFG 406 computes the potential next value of i, and the copy operation in the DFG 406 takes a value and produces multiple copies of its input to feed other operations. The cmp operation of the DFG 406 compares the i_next with the loop boundary 10 (e.g., cmplts64 cmp, I next 1, 10 in the assembly code 404). The result of the cmp operation is copied to two different destinations as values cmp_0 and cmp_1. The cmp_0 value is used to switch the i_next value to i_loopback or to i_result based on the cmplts output which triggers the output signal.” That is, the “CMP” node as shown in FIG. 4 can be regarded as a comparison node, and nodes that used with such a node, such as COPY and SWITCH are “associated” with the CMP node.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of Zheng with the teachings of ChoFleming by implementing the technique of performing a depth-first search of the data flow graph to identify nodes of the graph, so as to arrive at the above limitations of the claimed invention. The motivation would have been to improve the performance of an input data flow graph through the detection of backedges (see ChoFleming, [0034]: “to improve performance of the input DFG 126 which is targeted to be executed by the CGRA device 142, the backedge detector 102 analyzes the input DFG 126 to detect backedges.”).
The combination of references thus far does not explicitly teach the remaining limitation of the depth-first search “starting from an identified exit node and proceeding in a direction opposite data flow.”
Perron teaches “starting from an identified exit node and proceeding in a direction opposite data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have combined the teachings of references combined thus far with the teachings of Perron by implementing the depth-first search as a post-order search that starts at the exit node, so as to arrive at the claimed invention. The motivation for doing so would have been to implement a particular methodology for performing a depth-first search that enables analysis of a program on a node-by-node-basis (see Perron, [0023]: “The entire program may be systematically analyzed on a node-by-node basis by performing a depth-first search.”).
As to claim 33, the combination of Zheng, ChoFleming, and Perron teaches the method of claim 32, as set forth above.
Perron further teaches “further comprising: detecting the one or more control flow loops by at least searching the one or more data flow graphs in a reverse direction of data flow.” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 34, the combination of Zheng, ChoFleming, and Perron teaches the method of claim 33, wherein the searching begins at the exit node. [Perron, [0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.”]
As to claim 35, the combination of Zheng, ChoFleming, and Perron teaches the method of claim 32, as set forth above.
ChoFleming further teaches “wherein the one or more control flow loops are encoded in the one or more data flow graphs as a plurality of nodes comprising an enter node, a loop condition node, and an exit node.” [As noted in the rejection of the independent claim, ChoFlemon teaches loops with an enter node (e.g., o2 of FIG. 1), a loop condition node (e.g., o5 of FIG. 1 and CMP of FIG. 4), and an exit node (e.g., o5 of FIG. 1).]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of ChoFleming, so as to have also arrived at the limitations of the instant dependent claim. The motivation for doing so is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
As to claim 36, the combination of Zheng, ChoFleming, and Perron teaches the method of claim 32, further comprising: combining two or more loops detected in the one or more data flow graphs, in response to determining that the two or more loops share a loop condition node. [These limitations have the same or substantially the same claim language as those of claim 6, and are therefore taught by Zheng for the reason given for the limitations of claim 6.]
As to claim 37, the combination of Zheng, ChoFleming, and Perron teaches the method of claim 32, further comprising: detecting a sub-loop inside of a loop of the one or more control flow loops and adding the sub-loop to a list of operations determined to be inside of the loop. [These limitations have the same or substantially the same claim language as those of claim 7, and are therefore taught by Zheng for the reason given for the limitations of claim 7.]
As to claim 38, the combination of Zheng, ChoFleming, and Perron teaches the method of claim 32, as set forth above, further comprising: […] associating nodes […] with a loop condition. [Zheng, col. 9, lines 47-51: “In some embodiments, the compiler may determine that the loop order 504-1 is combinable with the loop order 504-2 if the indices are identical, the orders associated with the indices are identical, and the ranges of the indices are identical.” That is, the loop indices define a loop condition, and identifying loops with the same indices constitutes identifying the nodes containing those loops (e.g., nodes 202-3 and 202-4) in
Perron further teaches “searching the one or more data flow graphs, in a reverse direction of data flow, from a starting point indicated by a loop condition operation” and nodes identified “by the searching” [[0026]: “the depth-first search runs as a post-order search that starts at the exit node. The order in which the nodes may be processed in a post-order depth-first search is F-D-A-B-G-H-E-C, or, with the other handedness preference, H-G-E-C-B-F-D-A.” See also [0023]: “The arrows between each node may be referred to as edges and represent the flow of execution of the program represented by example 200”; [0019]: “To identify an H pathway, first a backwards data flow may be performed on the control-flow graph.” That is, the depth-first search starts from the exit and proceeds in a reverse direction of data flow, as illustrated in connection with FIG. 2. The limitation of “corresponding to a loop condition operation” is met in the combined teachings of the references because the graph in FIG. 2 of Zheng has nodes (e.g., nodes 202-2 and 202-3) that each have a loop condition. Thus, in the combined teachings of the references, a search from node 202-3 to 202-2 would result in a starting point of node 202-3, which includes a set of loops and is thus a node that is corresponding to a loop condition operation.]
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have further combined the teachings of the references combined thus far, including the teachings of Perron, so as to have also arrived at the limitations of the instant dependent claim. The rationale for obviousness is covered by the one given for the teachings of Perron in the rejection of the parent independent claim.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. The following documents depict the state of the art.
Avadhanula et al. (US 8826255 B1) teaches restructuring loops with various types of nodes, including condition nodes.
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to YAO DAVID HUANG whose telephone number is (571)270-1764. The examiner can normally be reached Monday - Friday 9:00 am - 5:30 pm.
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, Miranda Huang can be reached at (571) 270-7092. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Y.D.H./Examiner, Art Unit 2124
/Kevin W Figueroa/Primary Examiner, Art Unit 2124
Prosecution Insights