DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-28 are pending in this application.
Information Disclosure Statement
The IDS filed on 08/29/2023 has been considered.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. These limitations include “means for receiving a set of tasks to be performed; means for representing the tasks in a graph including multiple nodes connected by edges, each node corresponding to a task in the set of tasks; means for assigning a scheduling priority to each node in the graph; means for selecting a topological order of the tasks by repeating selection of a next node; and means for generating the topological order of the tasks by repeating the selection of the next node”, “means for selecting, via an artificial neural network (ANN), the next node based on one of a greedy search of a probability distribution of the potential next nodes, sampling from the probability distribution of the potential next nodes, or a beam search process”, “means for assigning the scheduling priorities to the multiple nodes with a single inference”, “means for assigning the scheduling priorities to the multiple nodes based on one or more topological transforms”, and “means for performing the set of tasks according to the topological order”.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof. The structure corresponding to these limitations is a processor.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-28 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
As per claims 1, 8, 15, and 22 (line numbers refer to claim 1):
Line 4 recites “each node” and it is unclear if this refers to each node of the multiple nodes in the graph.
Line 9 recites “the tasks” and it is unclear if this refers to “the set of tasks”.
Claims 2-7, 9-14, 16-21, and 23-28 are dependent claims of claims 1, 8, 15, and 22 and fail to resolve the deficiencies of claims 1, 8, 15, and 22, so they are rejected for the same reasons.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-28 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (abstract idea) without significantly more.
As per claim 1, in step 1 of the 101 analysis, the examiner has determined that the claim is directed to a method. Therefore, the claim is directed to one of the four statutory categories of invention.
In step 2A prong 1 of the 101 analysis, the examiner has determined that the claim recites
a judicial exception. Specifically, the limitations “representing the set of tasks in a graph including multiple nodes connected by edges; assigning a scheduling priority to each node in the graph; selecting a next node of potential next nodes according to a probability of each of the potential next nodes based at least in part on the assigned scheduling priorities and a topology of the graph; and generating a topological order of the tasks by repeating the selecting of the next node” are mental processes. Humans can use a pen and paper to draw a graph with nodes and edges to represent the set of tasks. Assigning a scheduling priority to each node is a mental process since humans can mentally use their judgement to rank the nodes. Humans can mentally select a next node since humans can mentally compute probabilities and use their judgement a next node based on the probabilities and the topology of the graph. Topological sorting can be performed mentally since humans can determine a order of the nodes to be selected.
In step 2A prong 2 of the 101 analysis, the examiner has determined that the additional
elements, alone or in combination do not integrate the judicial exceptions into a practical
application for the following rationale:
The limitation "processor-implemented" applies judicial exceptions on a generic computer. "Alappat 's rationale that an otherwise ineligible algorithm or software could be made patent-eligible by merely adding a generic computer to the claim was superseded by the Supreme Court's Bilski and Alice Corp. decisions" so therefore applying judicial exceptions on a processor which is a generic computer does not integrate the judicial exceptions into a practical application (MPEP 2106.05(b)).
The limitation "receiving a request to process a first job on a cluster" represents an
insignificant, extra-solution activity. The term "extra-solution activity" can be understood as
"activities incidental to the primary process or product that are merely a nominal or tangential
addition to the claim" (MPEP 2106.05(g)). The examiner has determined that the limitation
"receiving a request to process a first job on a cluster" is directed to a mere data gathering
activity which is a category of insignificant extra-solution activities (MPEP 2106.05(g)).
The limitation “each node corresponding to a task in the set of tasks” merely describes attributes of the technological environment in which the abstract idea is operating. The courts have identified that generally linking the use of a judicial exception into a technological environment does not integrate a judicial exception into a practical application (MPEP 2106.04(d)(I)).
In step 2B of the 101 analysis, the examiner has determined that the additional elements,
alone or in combination do not recite significantly more than the abstract ideas identified above
for the following rationale:
The limitation "processor-implemented" applies judicial exceptions on a generic computer and therefore does not provide significantly more.
The limitation "receiving a request to process a first job on a cluster " represents an
insignificant, extra-solution activity. The limitation "receiving a request to process a first job on a cluster" is well-understood, routine, or conventional because it is directed to "receiving or transmitting data" (MPEP 2106.05(d)). This is an additional element that the courts have
recognized as well understood, routine, or conventional (MPEP 2106.05(d)). The citation of
court cases in the MPEP meets the Berkheimer evidentiary burden since citation of a court case
in the MPEP is one of the 4 types of evidentiary support that can be used to prove that the
additional elements are well-understood, routine, or conventional (see 125 USPQ2d 1649
Berkheimer v. HP, Inc.). Thus, the limitation does not amount to significantly more than the
abstract idea.
The limitation “each node corresponding to a task in the set of tasks” merely describes attributes of the technological environment and therefore does not amount to significantly more than the exception itself (MPEP 2106.05(h)).
As per claim 8, it is an apparatus claim of claim 1, so it is rejected for similar reasons. Claim 8 recites additional generic computing components that neither integrate the judicial exceptions into a practical application nor recite significantly more.
As per claim 15, it is a non-transitory computer-readable medium claim of claim 1, so it is rejected for similar reasons. Claim 15 recites additional generic computing components that neither integrate the judicial exceptions into a practical application nor recite significantly more.
As per claim 22, it is an apparatus claim of claim 1, so it is rejected for similar reasons.
As per claim 2 (and similarly for claims 9, 16, and 23), it recites attributes of the technological environment that neither integrate the judicial exceptions into a practical application nor recite significantly more.
As per claim 3 (and similarly for claims 10, 17, and 24), it recites mental processes.
As per claim 4 (and similarly for claims 11, 18, and 25), it recites mental processes.
As per claim 5 (and similarly for claims 12, 19, and 26), it recites attributes of the technological environment that neither integrate the judicial exceptions into a practical application nor recite significantly more.
As per claim 6 (and similarly for claims 13, 20, and 27), it recites mental processes.
As per claim 7 (and similarly for claims 14, 21, and 28), it recites mental processes.
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The filing of a terminal disclaimer by itself is not a complete reply to a nonstatutory double patenting (NSDP) rejection. A complete reply requires that the terminal disclaimer be accompanied by a reply requesting reconsideration of the prior Office action. Even where the NSDP rejection is provisional the reply must be complete. See MPEP § 804, subsection I.B.1. For a reply to a non-final Office action, see 37 CFR 1.111(a). For a reply to final Office action, see 37 CFR 1.113(c). A request for reconsideration while not provided for in 37 CFR 1.113(c) may be filed after final for consideration. See MPEP §§ 706.07(e) and 714.13.
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The actual filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/apply/applying-online/eterminal-disclaimer.
Claims 1-28 are provisionally rejected on the ground of nonstatutory double patenting as being unpatentable over claim 1-4, 6-16, and 18-23 of copending Application No. 17/816,833 in view of Englert et al. (US 20200218969 A1 hereinafter Englert) and in view of Ma et al. (CN111695574A hereinafter Ma).
The cited portions of Ma are pulled from a translation of CN111695574A.
Although the claims at issue are not identical, they are not patentably distinct from each
other.
This is a provisional nonstatutory double patenting rejection because the patentably
indistinct claims have not in fact been patented.
Regarding claim 1 of the instant application, the following table compares claim 1 with
claim 1 of the copending application 17/816,833. The differences are bolded.
Instant Application
17/816,833
1. A processor-implemented method comprising:
receiving a set of tasks to be performed;
representing the set of tasks in a graph including multiple nodes connected by edges, each node corresponding to a task in the set of tasks;
assigning a scheduling priority to each node in the graph; selecting a next node of potential next nodes according to a probability of each of the potential next nodes based at least in part on the assigned scheduling priorities and a topology of the graph; and generating a topological order of the tasks by repeating the selecting of the next node.
1. A processor-based device comprising a workload execution reordering circuit configured to:
receive a plurality of workloads from a requestor; construct a weighted dependency graph based on the plurality of workloads, wherein the weighted dependency graph comprises: a plurality of vertices, each corresponding to a workload of the plurality of workloads; and one or more directed edges, each connecting two vertices of the plurality of vertices and indicating a dependency between a corresponding two workloads of the plurality of workloads; perform a topological sort of the weighted dependency graph; and generate a workload execution order based on the topological sort; wherein: a directed edge among the one or more directed edges represents a cross-thread dependency between the corresponding two workloads: the workload execution reordering circuit is configured to construct the weighted dependency graph by being configured to associate the directed edge with an edge weight derived from a distance between the two vertices corresponding to the corresponding two workloads: and the workload execution reordering circuit is configured to perform the topological sort based on the edge weight.
7. The processor-based device of claim 1, wherein: the workload execution reordering circuit is configured to construct the weighted dependency graph by being further configured to generate, for one or more workloads independent of the cross-thread dependency, a corresponding one or more vertex weights for the one or more vertices corresponding to the one or more workloads; and the workload execution reordering circuit is configured to perform the topological sort further based on the one or more vertex weights.
9. The processor-based device of claim 7, wherein the workload execution reordering circuit is configured to perform the topological sort by being further configured to: assign a vertex priority to each vertex of the plurality of vertices; and process the plurality of vertices in an order indicated by the vertex priority of each vertex.
Although the claims at issue are not identical, they are not patentably distinct from each
other. The copending application ‘833 does not explicitly claim selecting a next node of potential next nodes according to a probability of each of the potential next nodes based at least in part on the assigned scheduling priorities and a topology of the graph; and generating a topological order of the tasks by repeating the selecting of the next node.
However, Englert teaches selecting a next node of potential next nodes based at least in part on the assigned scheduling priorities and a topology of the graph; and generating a topological order of the tasks by repeating the selecting of the next node ([0034] the graph generator 262 may determine the various algorithms that implement the functionality and perform a topological sort to produce a directed acrylic graph (e.g., the graph 300) where the nodes of respective algorithms are ordered in accordance with their dependencies, and includes directed edges between respective nodes. For example, graph generator 262 determines that a first algorithm depends on input data that is provided by a second algorithm, and therefore would order the second algorithm before the first algorithm when generating the graph; [0029] In some implementations, prior to runtime, the framework 260 determines, as part of an integration stage, input parameters and an output format of each algorithm for a particular functionality (e.g., computer vision application for analyzing images and/or videos) provided in the compiled code, and temporal dependencies to determine an order of the algorithms; [0057] The framework 260 determines input parameters and an output format of algorithms for a particular functionality provided by an electronic device (e.g., the electronic device 115) (610). The framework 260 determines an order of the algorithms for performing the particular functionality based at least in part on temporal dependencies of the algorithms, and the input parameters and the output format of the algorithms (612). The graph generator 262 generates a graph based at least in part on the order of algorithms (614); [0042] For example, the heterogeneous scheduler 264 selects node 410 in the graph 400 corresponding to a first algorithm (“Inference 1”), which is executed on the GPU. Upon completion of the first algorithm, the heterogeneous scheduler 264 selects a subsequent node connected, by a directed edge, to the node 410).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the claims of copending application ‘833 with the teachings of Englert to easily run a neural network (see Englert [0016] automatically determining an order of algorithms to correctly maintain dependencies of operations and facilitate easier usage of neural networks in an application programming environment.).
The claims of copending application ‘833 and Englert fail to teach selecting a next node of potential next nodes according to a probability of each of the potential next nodes.
However, Ma teaches selecting a next node of potential next nodes according to a probability of each of the potential next nodes (pg. 4 lines 25-28 According to the conditional probability p (t/I, A (t), L (t)), the prediction of each node requires the information of its parent node and the left sibling node, ITT adds a directed edge to each node in the triple tree to its child node, and adds a directed edge to each node to its right sibling node, so that the directed graph topology is sorted as the generation order of the nodes. The topological ordering is obtained by a depth-first search (DFS); pg. 5 lines 24-25 In the greedy search, a word with the largest probability is selected from pi).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the claims of copending application ‘833 and Englert with the teachings of Ma to improve performance (see Ma pg. 2 line 42 improve the performance of the model).
Similar claim mappings of the remaining claims would have been obvious to a person
having ordinary skill in the art but have been omitted for the sake of brevity.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 22, 23, 26, and 28 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Englert et al. (US 20200218969 A1 hereinafter Englert).
As per claim 22, Englert teaches an apparatus, comprising: means for receiving a set of tasks to be performed ([0057] The framework 260 determines input parameters and an output format of algorithms for a particular functionality provided by an electronic device (e.g., the electronic device 115) (610).);
means for representing the tasks in a graph including multiple nodes connected by edges, each node corresponding to a task in the set of tasks ([0033] As discussed above, the subject technology, for example, generates a graph representing a data flow for performing a particular functionality that includes respective nodes representing various algorithms and an indication at each node of which processor executes the algorithm. Such algorithms may include one or more machine learning operations (e.g., predictions that utilize neural network models). Each node in the graph is connected to another node using a directed edge);
means for assigning a scheduling priority to each node in the graph ([0042] The graph 400 include nodes that are sorted in topological order; [0034] the graph generator 262 may determine the various algorithms that implement the functionality and perform a topological sort to produce a directed acrylic graph (e.g., the graph 300) where the nodes of respective algorithms are ordered in accordance with their dependencies, and includes directed edges between respective nodes);
means for selecting a topological order of the tasks by repeating selection of a next node; and means for generating the topological order of the tasks by repeating the selection of the next node ([0034] the graph generator 262 may determine the various algorithms that implement the functionality and perform a topological sort to produce a directed acrylic graph (e.g., the graph 300) where the nodes of respective algorithms are ordered in accordance with their dependencies, and includes directed edges between respective nodes. For example, graph generator 262 determines that a first algorithm depends on input data that is provided by a second algorithm, and therefore would order the second algorithm before the first algorithm when generating the graph; [0029] In some implementations, prior to runtime, the framework 260 determines, as part of an integration stage, input parameters and an output format of each algorithm for a particular functionality (e.g., computer vision application for analyzing images and/or videos) provided in the compiled code, and temporal dependencies to determine an order of the algorithms; [0057] The framework 260 determines input parameters and an output format of algorithms for a particular functionality provided by an electronic device (e.g., the electronic device 115) (610). The framework 260 determines an order of the algorithms for performing the particular functionality based at least in part on temporal dependencies of the algorithms, and the input parameters and the output format of the algorithms (612). The graph generator 262 generates a graph based at least in part on the order of algorithms (614); [0042] For example, the heterogeneous scheduler 264 selects node 410 in the graph 400 corresponding to a first algorithm (“Inference 1”), which is executed on the GPU. Upon completion of the first algorithm, the heterogeneous scheduler 264 selects a subsequent node connected, by a directed edge, to the node 410).
As per claim 23, Englert teaches the apparatus of claim 22, in which the tasks comprise a set of operations to be processed by a compiler ([0025] As illustrated, the computing architecture includes a compiler 215. A memory 240 includes source code 244, which after being compiled by the compiler 215, generates executables 242 that can be deployed to different target platforms for execution. In an example, the source code 244 may include code for various algorithms).
As per claim 26, Englert teaches the apparatus of claim 22, in which the graph comprises a direct acyclic graph ([0030] the graph is a directed acyclic graph (DAG)).
As per claim 28, Englert teaches the apparatus of claim 22, further comprising means for performing the set of tasks according to the topological order ([0042] The graph 400 include nodes that are sorted in topological order. The heterogeneous scheduler 264 performs a weighted traversal of the graph 400 while dispatching algorithms to various processors for execution. In an implementation, the heterogeneous scheduler 264 reevaluates the graph 400 after each algorithm is completed to select a subsequent node (e.g., algorithm) for executing. For example, the heterogeneous scheduler 264 selects node 410 in the graph 400 corresponding to a first algorithm (“Inference 1”), which is executed on the GPU. Upon completion of the first algorithm, the heterogeneous scheduler 264 selects a subsequent node connected, by a directed edge, to the node 410).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, 5, 7-12, 14-16, 19, 21, and 25 are rejected under 35 U.S.C. 103 as being unpatentable over Englert et al. (US 20200218969 A1 hereinafter Englert) and in view of Ma et al. (CN111695574A hereinafter Ma).
The cited portions of Ma are pulled from a translation of CN111695574A.
As per claim 1, Englert teaches the invention substantially as claimed including a processor-implemented method comprising: receiving a set of tasks to be performed ([0057] The framework 260 determines input parameters and an output format of algorithms for a particular functionality provided by an electronic device (e.g., the electronic device 115) (610).); [0025] As illustrated, the computing architecture includes a compiler 215. A memory 240 includes source code 244, which after being compiled by the compiler 215, generates executables 242 that can be deployed to different target platforms for execution. In an example, the source code 244 may include code for various algorithms);
representing the set of tasks in a graph including multiple nodes connected by edges, each node corresponding to a task in the set of tasks ([0033] As discussed above, the subject technology, for example, generates a graph representing a data flow for performing a particular functionality that includes respective nodes representing various algorithms and an indication at each node of which processor executes the algorithm. Such algorithms may include one or more machine learning operations (e.g., predictions that utilize neural network models). Each node in the graph is connected to another node using a directed edge);
assigning a scheduling priority to each node in the graph ([0042] The graph 400 include nodes that are sorted in topological order; [0034] the graph generator 262 may determine the various algorithms that implement the functionality and perform a topological sort to produce a directed acrylic graph (e.g., the graph 300) where the nodes of respective algorithms are ordered in accordance with their dependencies, and includes directed edges between respective nodes);
selecting a next node of potential next nodes based at least in part on the assigned scheduling priorities and a topology of the graph; and generating a topological order of the tasks by repeating the selecting of the next node ([0034] the graph generator 262 may determine the various algorithms that implement the functionality and perform a topological sort to produce a directed acrylic graph (e.g., the graph 300) where the nodes of respective algorithms are ordered in accordance with their dependencies, and includes directed edges between respective nodes. For example, graph generator 262 determines that a first algorithm depends on input data that is provided by a second algorithm, and therefore would order the second algorithm before the first algorithm when generating the graph; [0029] In some implementations, prior to runtime, the framework 260 determines, as part of an integration stage, input parameters and an output format of each algorithm for a particular functionality (e.g., computer vision application for analyzing images and/or videos) provided in the compiled code, and temporal dependencies to determine an order of the algorithms; [0057] The framework 260 determines input parameters and an output format of algorithms for a particular functionality provided by an electronic device (e.g., the electronic device 115) (610). The framework 260 determines an order of the algorithms for performing the particular functionality based at least in part on temporal dependencies of the algorithms, and the input parameters and the output format of the algorithms (612). The graph generator 262 generates a graph based at least in part on the order of algorithms (614); [0042] For example, the heterogeneous scheduler 264 selects node 410 in the graph 400 corresponding to a first algorithm (“Inference 1”), which is executed on the GPU. Upon completion of the first algorithm, the heterogeneous scheduler 264 selects a subsequent node connected, by a directed edge, to the node 410).
Englert fails to teach selecting a next node of potential next nodes according to a probability of each of the potential next nodes.
However, Ma teaches selecting a next node of potential next nodes according to a probability of each of the potential next nodes (pg. 4 lines 25-28 According to the conditional probability p (t/I, A (t), L (t)), the prediction of each node requires the information of its parent node and the left sibling node, ITT adds a directed edge to each node in the triple tree to its child node, and adds a directed edge to each node to its right sibling node, so that the directed graph topology is sorted as the generation order of the nodes. The topological ordering is obtained by a depth-first search (DFS); pg. 5 lines 24-25 In the greedy search, a word with the largest probability is selected from pi).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Englert with the teachings of Ma to improve performance (see Ma pg. 2 line 42 improve the performance of the model).
As per claim 2, Englert and Ma teach the processor-implemented method of claim 1. Engler teaches in which the set of tasks comprise a set of operations to be processed by a compiler ([0025] As illustrated, the computing architecture includes a compiler 215. A memory 240 includes source code 244, which after being compiled by the compiler 215, generates executables 242 that can be deployed to different target platforms for execution. In an example, the source code 244 may include code for various algorithms).
As per claim 3, Englert and Ma teach the processor-implemented method of claim 1. Ma teaches further comprising selecting the next node based on one of a greedy search of a probability distribution of the potential next nodes, sampling from the probability distribution of the potential next nodes, or a beam search process (pg. 4 lines 25-28 According to the conditional probability p (t/I, A (t), L (t)), the prediction of each node requires the information of its parent node and the left sibling node, ITT adds a directed edge to each node in the triple tree to its child node, and adds a directed edge to each node to its right sibling node, so that the directed graph topology is sorted as the generation order of the nodes. The topological ordering is obtained by a depth-first search (DFS); pg. 5 lines 24-25 In the greedy search, a word with the largest probability is selected from pi).
As per claim 5, Englert and Ma teach the processor-implemented method of claim 1. Englert teaches in which the graph comprises a direct acyclic graph ([0030] the graph is a directed acyclic graph (DAG)).
As per claim 7, Englert and Ma teach the processor-implemented method of claim 1.
Englert teaches further comprising performing the set of tasks according to the topological order ([0042] The graph 400 include nodes that are sorted in topological order. The heterogeneous scheduler 264 performs a weighted traversal of the graph 400 while dispatching algorithms to various processors for execution. In an implementation, the heterogeneous scheduler 264 reevaluates the graph 400 after each algorithm is completed to select a subsequent node (e.g., algorithm) for executing. For example, the heterogeneous scheduler 264 selects node 410 in the graph 400 corresponding to a first algorithm (“Inference 1”), which is executed on the GPU. Upon completion of the first algorithm, the heterogeneous scheduler 264 selects a subsequent node connected, by a directed edge, to the node 410 in a manner described by the following discussion.).
As per claim 8, it is an apparatus claim of claim 1, so it is rejected for similar reasons. Additionally, Englert teaches an apparatus, comprising: a memory; and at least one processor coupled to the memory, the at least one processor configured to ([0059] the bus 708 communicatively connects the one or more processing unit(s) 712 with the ROM 710, the system memory 704).
As per claims 9, 10, 12, and 14, they are apparatus claims of claims 2, 3, 5, and 7, so they are rejected for similar reasons.
As per claim 11, Englert and Ma teach the apparatus of claim 8. Ma teaches in which the at least one processor is further configured to assign the scheduling priorities to the multiple nodes with a single inference (pg. 2 lines 8-11 The prediction of each node uses the information of its parent node and the left sibling node, one directed edge is added between each node in the triple tree to its child node, and a directed edge is added between each node and the right sibling node thereof, so that the directed graph topology is sorted as the generation order of the nodes. The topological ordering is obtained by a depth-first search (DFS); pg. 3 lines 13-14 the executable program is executed by the processor; A depth-first search can be considered a single inference.).
As per claim 15, it is a non-transitory computer-readable medium claim of claim 1, so it is rejected for similar reasons. Additionally, Englert teaches a non-transitory computer-readable medium having program code recorded thereon, the program code executed by a processor ([0065] The computer-readable storage medium can be any storage medium that can be read, written, or otherwise accessed by a general purpose or special purpose computing device, including any processing electronics and/or processing circuitry capable of executing instructions).
As per claims 16, 19, and 21, they are non-transitory computer-readable medium claims of claims 2, 5, and 7, so they are rejected for similar reasons.
As per claim 25, Englert teaches the apparatus of claim 22.
Englert fails to teach further comprising means for assigning the scheduling priorities to the multiple nodes with a single inference.
However, Ma teaches further comprising means for assigning the scheduling priorities to the multiple nodes with a single inference (pg. 2 lines 8-11 The prediction of each node uses the information of its parent node and the left sibling node, one directed edge is added between each node in the triple tree to its child node, and a directed edge is added between each node and the right sibling node thereof, so that the directed graph topology is sorted as the generation order of the nodes. The topological ordering is obtained by a depth-first search (DFS); pg. 3 lines 13-14 the executable program is executed by the processor).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Englert with the teachings of Ma to improve performance (see Ma pg. 2 line 42 improve the performance of the model).
Claims 4 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Englert and Ma, as applied to claims 1 and 15 above, in view of Versace et al. (US 20170076194 A1 hereinafter Versace).
As per claim 4, Englert and Ma teach the processor-implemented method of claim 1. Ma teaches further comprising assigning the scheduling priorities to the multiple nodes with a single inference (pg. 2 lines 8-11 The prediction of each node uses the information of its parent node and the left sibling node, one directed edge is added between each node in the triple tree to its child node, and a directed edge is added between each node and the right sibling node thereof, so that the directed graph topology is sorted as the generation order of the nodes. The topological ordering is obtained by a depth-first search (DFS); pg. 3 lines 13-14 the executable program is executed by the processor).
Englert and Ma fail to teach further comprising assigning, via an artificial neural network (ANN), the scheduling priorities to the multiple nodes.
However, Versace teaches further comprising assigning, via an artificial neural network (ANN), the scheduling priorities to the multiple nodes ([0137] the scheduler can use a neural-like competitive cueing network (or ANN, or DNN) to appropriately sequence actions based on their relative importance and timing; [0146] an ANN/DNN autonomously prioritizes scheduling based on learning and experience).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Englert and Ma with the teachings of Versace to better prioritize scheduling (see Versace [0146] an ANN/DNN autonomously prioritizes scheduling based on learning and experience.).
As per claim 18, it is a non-transitory computer-readable medium claim of claim 4, so it is rejected for similar reasons.
Claims 6, 13, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Englert and Ma, as applied to claims 1, 8, and 15 above, in view of Pfitzmann et al. (US 20230252309 A1 hereinafter Pfitzmann).
As per claim 6, Englert and Ma teach the processor-implemented method of claim 1.
Englert and Ma fail to teach in which the scheduling priority is assigned based on one or more topological transforms.
However, Pfitzmann teaches in which the scheduling priority is assigned based on one or more topological transforms ([0033] The transformation (step S51) preferably includes linearly ordering (step S51) the nodes of the topology, to obtain the DAG as a graph of linearly ordered nodes. A linear order can be regarded as a list, which is free of branches. Doing so allows to write the flow as a linear sequence: one node is written before the other.).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Englert and Ma with the teachings of Pfitzmann to easily determine a data flow (see Pfitzmann [0032] In cases where the valid topology 620 is not already a DAG, then it can advantageously be transformed into a DAG once all the necessary nodes and edges have been obtained, to ease the subsequent data flow construction.)
As per claims 13 and 20, they are apparatus and non-transitory computer-readable medium claims of claim 6, so they are rejected for similar reasons.
Claim 17 is rejected under 35 U.S.C. 103 as being unpatentable over Englert and Ma, as applied to claim 15 above, in view of Tran et al. (US 20190354849 A1 hereinafter Tran).
As per claim 17, Englert and Ma teach the non-transitory computer-readable medium of claim 15.
Englert and Ma fail to teach further comprising program code to select, via an artificial neural network (ANN), the next node based on one of a greedy search of a probability distribution of the potential next nodes, sampling the probability distribution of the potential next nodes or a beam search process.
However, Tran teaches further comprising program code to select, via an artificial neural network (ANN), the next node based on one of a greedy search of a probability distribution of the potential next nodes, sampling the probability distribution of the potential next nodes or a beam search process ([0064] The artificial neural networks 426 may provide as output 432 values for the states, actions, or probability distributions of states and/or actions; [0059] the decision maker 424 may select a next action randomly with some probability, which is known as an ϵ-greedy exploration strategy; abstract For each data instance in a set of data instances, a sequence of actions may be automatically learned).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Englert and Ma with the teachings of Tran to improve performance (see Tran [0017] Thus, the present invention provides for automating the data preprocessing stage to improve the performance of machine learning projects in terms of cost effectiveness and technical quality of the outcomes).
Claim 24 is rejected under 35 U.S.C. 103 as being unpatentable over Englert as applied to claim 22 above, in view of Tran.
As per claim 24, Englert teaches the apparatus of claim 22.
Englert fails to teach further comprising means for selecting, via an artificial neural network (ANN), the next node based on one of a greedy search of a probability distribution of the potential next nodes, sampling from the probability distribution of the potential next nodes, or a beam search process.
However, Tran teaches further comprising means for selecting, via an artificial neural network (ANN), the next node based on one of a greedy search of a probability distribution of the potential next nodes, sampling from the probability distribution of the potential next nodes, or a beam search process ([0064] The artificial neural networks 426 may provide as output 432 values for the states, actions, or probability distributions of states and/or actions; [0059] the decision maker 424 may select a next action randomly with some probability, which is known as an ϵ-greedy exploration strategy; abstract For each data instance in a set of data instances, a sequence of actions may be automatically learned).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Englert with the teachings of Tran to improve performance (see Tran [0017] Thus, the present invention provides for automating the data preprocessing stage to improve the performance of machine learning projects in terms of cost effectiveness and technical quality of the outcomes).
Claim 27 is rejected under 35 U.S.C. 103 as being unpatentable over Englert, as applied to claim 22 above, in view of Pfitzmann.
As per claim 27, Englert teaches the apparatus of claim 22.
Englert fails to teach further comprising means for assigning the scheduling priorities to the multiple nodes based on one or more topological transforms.
However, Pfitzmann teaches further comprising means for assigning the scheduling priorities to the multiple nodes based on one or more topological transforms ([0033] The transformation (step S51) preferably includes linearly ordering (step S51) the nodes of the topology, to obtain the DAG as a graph of linearly ordered nodes. A linear order can be regarded as a list, which is free of branches. Doing so allows to write the flow as a linear sequence: one node is written before the other.).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined Englert with the teachings of Pfitzmann to easily determine a data flow (see Pfitzmann [0032] In cases where the valid topology 620 is not already a DAG, then it can advantageously be transformed into a DAG once all the necessary nodes and edges have been obtained, to ease the subsequent data flow construction.)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HSING CHUN LIN whose telephone number is (571)272-8522. The examiner can normally be reached Mon - Fri 9AM-5PM.
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, Aimee Li can be reached at (571) 272-4169. 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.
/H.L./Examiner, Art Unit 2195
/Aimee Li/Supervisory Patent Examiner, Art Unit 2195
Prosecution Insights