DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Status of the Claims
Claims 1-20 are pending for examinations.
Claims 1, 9 and 16 are independent Claims.
Claims 1-20 are rejected under 35 U.S.C. § 103.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-3, 5, 8-11, 13, 16-18 and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Plush et al. (U.S. 2023/0229652 hereinafter Plush) in view of Larson et al. (U.S. 10,180,821 in hereafter Larson) in further view of Nurvitadhi et al. (U.S. 20220121593 hereinafter Nurvitadhi).
As Claim 1, Plush teaches a computer-implemented (Plush (¶0104 line 11-13), processor and memory) method for training a graph neural network for database driven place and route, comprising:
training a graph neural network (GNN) to predict a nearest matching subgraph identifier and a nearest matching score (Plush (¶0061 last 6 lines), machine learning identifies threshold similarity scores (a nearest matching score) to indicate when resolver trees (nearest matching subgraph identifier) associated with the same entity) using a plurality of features for each previously placed reference unit graph from a database of previously placed reference unit graphs (Plush (¶0061 last 6 lines), training dataset includes resolver trees known (previous placed reference unit graph) to represent the same entities (plurality of features)), and to produce a trained GNN (Plush (¶0061 last 6 lines), machine learning is trained);
determining, using the trained GNN (Plush (¶0061 last 6 lines), machine learning identifies threshold similarity scores (a nearest matching score) to indicate when resolver trees (nearest matching subgraph identifier) associated with the same entity), a nearest matching subgraph identifier (Plush (¶0083 line 1-4, fig. 4 item 402, ¶0084 line 1-5), system determines potential matching entity based on information stored in resolver tree 110 associated with the potential matching entities 104) and a nearest matching score for the unplaced unit graph (Plush (¶0086 line 1-7, fig. 4 item 404), system generate similarity score associated with potential matching entities.)
Plush may not explicitly disclose:
receiving an unplaced unit graph representing a portion of a computational dataflow
wherein the nearest matching subgraph identifier identifies a previously placed reference unit graph in the database having placement position attributes for configurable units;
according to the placement position attributes corresponding to the previously placed reference unit graph identified by the nearest matching subgraph identifier to produce placed configurable units; and
Larson teaches:
receiving an unplaced unit graph representing a portion of a computational dataflow (Larson (col. 8 line 1-9), system identifies unlinked sub-graph interfaces)
wherein the nearest matching subgraph identifier identifies a previously placed reference unit graph in the database having placement position attributes for configurable units (Larson (col. 8 line 10-15), “the module 106 links (154) the appropriate sub-graph. During this potentially recursive process of linking (called "link-time"), there may be various parameters associated with dataflow graphs that need to be evaluated, including parameters (placement position attributes) indicating which particular implementation (nearest matching subgraph identifier) sub-graph (previous placed reference unit graph) should be linked to a given sub-graph interface”, system establishes a link between “a given sub-graph interface” with an existing subgraph);
according to the placement position attributes corresponding to the previously placed reference unit graph identified by the nearest matching subgraph identifier to produce placed configurable units (Larson (col. 8 line 14-20), “subgraph should be linked to a given sub-graph interface. After dynamic linking is complete, the module 106 compiles (156) the fully assembled dataflow graph into an executable form (at "compile-time"), and the execution module 104 executes (158) the compiled dataflow graph (at "run-time").”); and
Plush teaches a system to combine similar sub-graphs using a machine learning system. Larson teaches a system/method to detected unlinked graph and connect an unliked graph to an existing workflow graph based on the similarity between the graphs. The workflow graph is implemented using a processing system. Plush and Larson are analogous arts because they are related to graph and combining graphs. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify graph system of Plush instead be a graph linking module taught by Larson, with a reasonable expectation of success. The motivation would be to “provide the ability to make a data flow graph generic across multiple implementations of the interface. Sub-graph interfaces provide the ability to develop graphs against the interface in advance of any implementation of the sub-graph interface. Sub-graph interfaces provide the ability to validate an implementation against the inter-face without a specific instance of use. Sub-graph interfaces provide the ability to differentiate the shipping location, permissions, encryption, or other attributes of the implementation of a sub-graph” (Larson (col. 5 line 5-15)).
Plush in view of Larson may not explicitly disclose:
for execution on a coarse-grained reconfigurable processor;
placing configurable units of the unplaced unit graph onto positions in a configurable units array of the coarse-grained reconfigurable processor
generating configuration data corresponding to the placed configurable units that enables the configurable units array to implement at least a portion of the unplaced unit graph on the coarse-grained reconfigurable processor.
Nurvitadhi teaches:
for execution on a coarse-grained reconfigurable processor (Nurvitadhi (¶0024), “A coarse-grained CISC processor can process coarse-grained data in fewer steps (e.g., matrix data can be read in one step, and processed in one instruction by a matrix compute functional unit in a processing element.” Nurvitadhi (¶0027), “CG-CISC processor that provides multi-threading and/or multi-programming may be built as a processor on a programmable logic integrated circuit (e.g., combination of soft and hard features in an FPGA) or manufactured as a hard processor in silicon.”);
placing configurable units of the unplaced unit graph onto positions in a configurable units array of the coarse-grained reconfigurable processor (Nurvitadhi (¶0097 last 6 lines), “Processor generator 502 combines the three modules 1105-1107 from library 607 by matching the graph for instruction set 1104 (with instruction Instl) with the merged operations graphs of modules 1105-1107 to generate a hardware block 1108, shown in FIG. 11, containing PEs 1111-1113 for a CG-CISC processor circuit.”)
generating configuration data corresponding to the placed configurable units that enables the configurable units array to implement at least a portion of the unplaced unit graph on the coarse-grained reconfigurable processor (Nurvitadhi (¶0097 last 6 lines), “Processor generator 502 combines the three modules 1105-1107 from library 607 by matching the graph for instruction set 1104 (with instruction Instl) with the merged operations graphs of modules 1105-1107 to generate a hardware block 1108, shown in FIG. 11, containing PEs 1111-1113 for a CG-CISC processor circuit.”).
Plush in view of Larson teaches a system/method to detected unlinked graph and connect an unliked graph to an existing workflow graph based on the similarity between the graphs. The workflow graph is implemented using a processing system. Nurvitadhi teaches a configurable hardware for for coarse-grained processing. Larson and Nurvitadhi are analogous arts because they are related to configuring processor using workflow graph. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify processing system of Plush in view of Larson instead be a coarse-grained configurable system taught by Nurvitadhi, with a reasonable expectation of success. The motivation would be to allow “the unique
reconfigurability of an FPGA allows re-configuring a single FPGA device over time to deploy multiple instances of CG-CISC processors implemented at least in part in soft logic and specialized for different application domains or to update a CG-CISC processor with a new specialized instance as an application domain evolves” (Nurvitadhi (¶0026 last 7 lines)).
As Claim 2, besides Claim 1, Plush in view of Larson in further view of Nurvitadhi teaches wherein training the GNN further comprises using each corresponding nearest matching subgraph identifier and nearest matching score as training targets to produce the trained GNN (Plush (¶0061 last 6 lines), machine learning identifies threshold similarity scores (a nearest matching score) to indicate when resolver trees (nearest matching subgraph identifier) associated with the same entity).
As Claim 3, besides Claim 2, Plush in view of Larson in further view of Nurvitadhi teaches wherein nodes in a unit graph used for training or placing correspond to a set of configurable units (Larson (col. 8 line 14-19, col. 5 line 24-30), container graph is configurable with respect to the type of data(s) emerging from or entering the implementation sub-graph).
As Claim 5, besides Claim 2, Plush in view of Larson in further view of Nurvitadhi teaches wherein the GNN and the trained GNN comprise a graph aggregation stage,
wherein the graph aggregation stage determines an aggregated feature vector for each node in a unit graph to produce aggregated feature vectors (Larson (col. 10 line 33-38), a descriptor data or computational characteristic is transferred),
wherein the graph aggregation stage determines the aggregated feature vectors by exchanging messages between each pair of connected nodes in the unit graph (Larson (col. 10 line 33-38), a descriptor data or computational characteristic is transferred from that flow to a component or a port on a component),
wherein the graph aggregation stage conducts two or more passes of exchanging messages (Larson (col. 10 line 33-38), a descriptor data or computational characteristic is transferred from that flow to a component or a port on a component in the second dataflow graph), and
wherein the graph aggregation stage averages the aggregated feature vectors to produce an average feature vector for the unit graph (Larson (col. 11 line 4-8, metadata is propagated from portions of the graph for which metadata has been explicitly defined to portions of the graph for which the metadata has not been explicitly defined).
As Claim 8, besides Claim 1, Plush in view of Larson in further view of Nurvitadhi teaches wherein construction of the database of previously placed reference unit graphs comprises:
placing and routing, using an ab-initio architecture agnostic place and route algorithm (Larson (col. 8 line 1-5, fig. 2A, assignee for Larson is ab-initio), data flow graph 200 is configured to process data from a first input dataset and second input dataset using a number of components and to store the result processed data in an input dataset),
configurable units of an unplaced reference unit graph onto positions in a configurable units array (Larson (col. 8 line 14-19, col. 5 line 24-30), sub-graphs are linked to produce dataflow graph),
wherein placing and routing associates the unplaced reference unit graph to a placed and routed reference unit graph (Larson (col. 8 line 14-19, col. 5 line 24-30), sub-graphs are linked to produce dataflow graph);
generating configuration data for placement positions and routed data and dataflow control information for the placed and routed reference unit graph (Larson (col. 8 line 14-19, col. 5 line 24-30), the data flow graph is converted to executable form. Container graph is configurable with respect to the type of data(s) emerging from or entering the implementation sub-graph);
loading the configuration data onto an instance of the configurable units array (Larson (col. 8 line 14-21, fig. 23 line 58, processors), execute module 140 executes the compiled dataflow graph) of a coarse-grained reconfigurable processor (Nurvitadhi (¶0024), “A coarse-grained CISC processor can process coarse-grained data in fewer steps (e.g., matrix data can be read in one step, and processed in one instruction by a matrix compute functional unit in a processing element.” Nurvitadhi (¶0027), “CG-CISC processor that provides multi-threading and/or multi-programming may be built as a processor on a programmable logic integrated circuit (e.g., combination of soft and hard features in an FPGA) or manufactured as a hard processor in silicon.”);
executing the placed and routed reference unit graph on the instance of the configurable units array of the course-grained reconfigurable processor (Larson (col. 8 line 14-21, fig. 23 line 58, processors), execute module 140 executes the compiled dataflow graph);
retrieving post-run attributes associated with executing the placed and routed reference unit graph on the instance of the configurable units array (Plush (¶0098 last 5 lines), system stores log about merge identifier after the merge operation); and
adding the placed and routed reference unit graph to a new entry in the database of previously placed reference unit graphs including placement position attributes of corresponding configurable units in the placed and routed reference unit graph and the post-run attributes (Plush (¶0098 last 5 lines), system stores log about merge identifier after the merge operation), wherein entries in the database of previously placed reference unit graphs form training data for training the GNN (Plush (¶0061 last 6 lines), training dataset includes resolver trees known (previous placed reference unit graph)).
As Claims 9-11 and 13, the Claims are rejected for the same reasons as Claims 1-3 and 5, respectively.
As Claims 16-18 and 20, the Claims are rejected for the same reasons as Claims 1-3 and 5, respectively.
Claim(s) 4, 6-7, 12, 14-15 and 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Plush and Larson in view of Nurvitadhi in further view of Lecue (U.S. 11,442,963 herein after Lecue).
As Claim 4, besides Claim 1, Plush in view of Larson in further view of Nurvitadhi teaches wherein an embedding stage of the GNN and the trained GNN comprises a branch for each configurable unit of a set of configurable units,
wherein inputs to each branch of the embedding stage comprise a set of configuration unit attributes for a configuration unit of the set of configurable units (Larson (col. 8 line 14-19, col. 5 line 24-30), container graph is configurable with respect to the type of data(s) emerging from or entering the implementation sub-graph),
wherein the set of configuration unit attributes comprises one or more of configurable unit type, a dataflow task, an end-to-end (e2e) attribute, and a routing length (Larson (col. 8 line 14-19, col. 5 line 24-30), sub-graphs are linked to produce dataflow graph),
wherein each branch of the embedding stage uses a set of embedding tables comprising an embedding table for each configuration unit attribute of the set of configuration unit attributes (Larson (col. 15 line 4-7, fig. 2E), tab 230 includes embedding tables for configure the flow junctions),
wherein the set of embedding tables comprises one or more of a configurable unit type table, a dataflow task table, an e2e attribute table, and a routing length table (Larson (col. 15 line 4-7, fig. 2E), tab 230 includes embedding tables for configure the flow junctions).
Plush in view of Larson in further view of Nurvitadhi may not explicitly disclose:
wherein each branch of the embedding stage generates a composite feature vector from a set of embedding vectors provided by the set of embedding tables used by the branch,
wherein the composite feature vector is generated using a multi-layer perceptron branch, and
Lecue teaches:
wherein each branch of the embedding stage generates a composite feature vector from a set of embedding vectors provided by the set of embedding tables used by the branch (Lecue (col. 5 line 34-42, col. 6 line 51-53 and 65-67), graphs are combined based on similarity scores. Neural networks are used as machine learning),
wherein the composite feature vector is generated using a multi-layer perceptron branch (Lecue (col. 5 line 34-42, col. 6 line 51-53 and 65-67), graphs are combined based on similarity scores. Neural networks with multiple perceptrons are used as machine learning), and
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify machine model of Plush in view of Larson in further view of Nurvitadhi instead be a neural network taught by Lecue, with a reasonable expectation of success. The motivation would be to “enable tuning a deep neural network to be less prone to error and enable saving computational resources” (Lecue (¶0026 line 13-15))
As Claim 6, besides Claim 1, Plush in view of Larson in further view of Nurvitadhi may not explicitly disclose:
wherein a classification stage predicts a nearest matching subgraph identifier for a unit graph from an average feature vector using a multi-layer perceptron, and wherein a regressor stage predicts a nearest matching score for the unit graph from the average feature vector using a multi-layer perceptron.
Lecue teaches:
wherein a classification stage predicts a nearest matching subgraph identifier for a unit graph from an average feature vector using a multi-layer perceptron, and wherein a regressor stage predicts a nearest matching score for the unit graph from the average feature vector using a multi-layer perceptron (Lecue (col. 5 line 34-42, col. 6 line 51-53 and 65-67), graphs are combined based on similarity scores. Neural networks with multiple perceptrons are used as machine learning).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify machine model of Plush in view of Larson in further view of Nurvitadhi instead be a neural network taught by Lecue, with a reasonable expectation of success. The motivation would be to “enable tuning a deep neural network to be less prone to error and enable saving computational resources” (Lecue (¶0026 line 13-15))
As Claim 7, besides Claim 1, Plush in view of Larson in further view of Nurvitadhi may not explicitly disclose:
wherein weights within a classification stage, a regressor stage, and an embedding stage of the GNN are updated using backpropagation.
Lecue teaches:
wherein weights within a classification stage, a regressor stage, and an embedding stage of the GNN are updated using backpropagation (Lecue (col. 5 line 34-42, col. 6 line 51-53 and 65-67), graphs are combined based on similarity scores. Neural networks implement back-propagation).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify machine model of Plush in view of Larson in further view of Nurvitadhi instead be a neural network taught by Lecue, with a reasonable expectation of success. The motivation would be to “enable tuning a deep neural network to be less prone to error and enable saving computational resources” (Lecue (¶0026 line 13-15))
As Claim 12 and 14-15, the Claims are rejected for the same reasons as Claims 4 and 6-7 respectively.
As Claim 19, the Claim is rejected for the same reasons as Claim 4.
Response to Arguments
Rejections of Claims 1-7 and 9-20 under 35 U.S.C. §101:
Applicant’s arguments regarding a specific technological improvement is persuasive; therefore, 35 U.S.C. §101 rejections on Claims 1-7 and 9-20 are respectfully withdrawn.
Rejections of Claims 1-20 under 35 U.S.C. §112(b):
Applicant amended the Claims; therefore, 35 U.S.C. §112(b) are respectfully withdrawn.
Rejections of Claims 1-3, 5, 8-11, 13, 16-10 and 20 under 35 U.S.C. §103:
Plush is not an analogous art:
As per Plush, applicant argues that is fundamentally different from the present invention (bottom of page 13 in the remarks).
Applicant’s arguments are not persuasive. Plush teaches a system to combine similar sub-graphs using a machine learning system. Larson teaches a system/method to detected unlinked graph and connect an unliked graph to an existing workflow graph based on the similarity between the graphs. The workflow graph is implemented using a processing system. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify graph system of Plush instead be a graph linking module taught by Larson, with a reasonable expectation of success. The motivation would be to “provide the ability to make a data flow graph generic across multiple implementations of the interface. Sub-graph interfaces provide the ability to develop graphs against the interface in advance of any implementation of the sub-graph interface. Sub-graph interfaces provide the ability to validate an implementation against the inter-face without a specific instance of use. Sub-graph interfaces provide the ability to differentiate the shipping location, permissions, encryption, or other attributes of the implementation of a sub-graph” (Larson (col. 5 line 5-15)). Plush and Larson are analogous arts because they are related to graph and combining graphs.
The combination lacks motivation:
As per Larson, Applicant argue that the motivation “provide the ability to make a data flow graph generic across multiple implementations” has nothing to do with the present invention (fourth paragraph of page 14 in the remarks).
Applicant’s argument are not persuasive because the motivation supports the reason to combine Plush and Larson. Plush teaches a system to combine similar sub-graphs using a machine learning system. Larson teaches a system/method to detected unlinked graph and connect an unliked graph to an existing workflow graph based on the similarity between the graphs. The workflow graph is implemented using a processing system. It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify graph system of Plush instead be a graph linking module taught by Larson, with a reasonable expectation of success. The motivation would be to “provide the ability to make a data flow graph generic across multiple implementations of the interface. Sub-graph interfaces provide the ability to develop graphs against the interface in advance of any implementation of the sub-graph interface. Sub-graph interfaces provide the ability to validate an implementation against the inter-face without a specific instance of use. Sub-graph interfaces provide the ability to differentiate the shipping location, permissions, encryption, or other attributes of the implementation of a sub-graph” (Larson (col. 5 line 5-15)).
Larson does not teach the Claimed placement and configuration:
Applicant argues that Plush does not disclose placement and configuration (top half of page 15 in the remarks).
Applicant’s arguments are not persuasive because Plush teaches the limitation about placement and configuration. See the current rejection(s) for details.
The amendments further distinguish over the prior art:
Applicant argues that current amendments overcome both Plush and Larson (bottom half of page 15 in the remarks).
Applicant’s arguments are moot because new reference Nurvitadhi teaches the new amended limitation(s).
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NHAT HUY T NGUYEN whose telephone number is (571)270-7333. The examiner can normally be reached M-F: 12:00-8:00 EST.
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, Viker Lamardo can be reached at 571-270-5871. 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.
/NHAT HUY T NGUYEN/Primary Examiner, Art Unit 2147
Prosecution Insights