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-6, 8-13, 15-20, and 22-27 are pending in this application.
Response to Arguments
Applicant’s arguments regarding the rejections of claims 1-28 under 35 U.S.C. 112b have been fully considered and are persuasive. The rejections have been withdrawn.
Applicant's arguments regarding the 35 U.S.C. 103 rejections of claims 1-28 have been fully considered and are unpersuasive.
Regarding the 35 U.S.C. 103 rejection, the applicant argues the following in the remarks:
Lee describes forward-path and inverse-path attention heads that operate on the same directed acyclic graph with different neighbor masks. However, Lee does not disclose multi-head attention blocks that each "...operate on a different topologically transformed graph induced by the original graph."
Examiner has thoroughly considered Applicant' s arguments, but respectfully finds them unpersuasive for at least the following reasons:
As to point (a), the examiner respectfully disagrees. Lee discloses in Section IV.A.3) Two-Way Path Aggregation “Thus, we adopt two types of Attention heads, incorporating them in the message-passing loop. This is similar with [22], [28] except we exploit different masks for each Attention head. Specifically, we define inverse neighbors as N-1(vi)={vk|eik∈E}∪{vi}.(14) Then, among H Attention heads, we set half of them to be forward-path graph Attention in Eq. (10) and the other half to be inverse-path graph Attention in Eq. (15). Attθ({h(k)j|vj∈N-1(vi)})(15) This graph path aggregation in a GCN with both forward-path and inverse-path is illustrated in Figure 3. Employing Attention from the two path types enables the model to learn features on predecessor conditions as well as successor conditions in a DAG while preserving their different relations”. The different topologically transformed graphs include N(vi) as shown in equation 10 and figure 3 and N-1(vi) as shown in equation 15 and figure 3.
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 an original graph including multiple nodes connected by edges, each node of the multiple nodes corresponding to a task in the set of tasks; means for assigning a scheduling priority to each node in the original graph with a plurality of multi-head attention blocks; 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 set of tasks by repeating the selection of the next node; and means for executing the set of tasks in the topological order”, “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 § 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-6, 8-13, 15-20, and 22-27 are rejected under 35 U.S.C. 103 as being -unpatentable over Englert et al. (US 20200218969 A1 hereinafter Englert) and in view of Lee et al. (A Global DAG Task Scheduler Using Deep Reinforcement Learning and Graph Convolution Network hereinafter Lee).
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 an original graph including multiple nodes connected by edges, each node of the multiple nodes 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 original 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 original graph; generating a topological order of the set of 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); and
executing the set of tasks in 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; [0057] The graph generator 262 generates a graph based at least in part on the order of algorithms (614). In an implementation, the graph is a directed acyclic graph including a set of nodes corresponding to the algorithms where each node indicates a particular processor provided by the electronic device for executing an algorithm. The heterogeneous scheduler 264 executes the particular functionality based on performing a traversal of the graph (616). In an implementation, the traversal is a topological traversal of the set of nodes).
Englert fails to teach assigning a scheduling priority to each node in the original graph based on an aggregate of outputs of a plurality of multi-head attention blocks, each multi-head attention block of the plurality of multi-head attention blocks operating on a different topologically transformed graph induced by the original graph; selecting a next node of potential next nodes according to a probability of each of the potential next nodes.
However, Lee teaches assigning a scheduling priority to each node in the original graph based on an aggregate of outputs of a plurality of multi-head attention blocks, each multi-head attention block of the plurality of multi-head attention blocks operating on a different topologically transformed graph induced by the original graph (Section I paragraph 7 Section IV presents our proposed encoder-decoder model structure with GCN-based DAG embeddings and Attention-based priority assignments for subtasks in a DAG; Section IV. paragraph 2 In the GCN-based encoder, the raw features of individual n nodes (or n subtasks) in a DAG task τ are first processed via a feed-forward network (FFN). The structural information of τ ’s task dependency graph is encoded via the message passing mechanism of a GCN, and then latent vectors of the nodes are generated. With the latent vectors, the Attention-based decoder generates a priority order for the nodes of τ; Section IV.A.2) Graph Level Embedding We exploit several Attention modules (heads) simultaneously and aggregate them to get the final latent representation. This is useful since different Attention heads can give weights more relevantly to different latent representations (h ). The Aggregate function is implemented using multi-head Attention, and is defined as Aggregateθ({h(k)j|vj∈N(vi)})=(Attθ,1⊕Attθ,2⊕…⊕Attθ,H) (12) where ⊕ concatenates vectors, and Attθ,1,…,Attθ,H are H -individual Attention modules. H denotes the number of distinct Attention heads per layer; Section V.A.3) Model Hyperparameters In the encoder, we set the number of graph convolution layers to K=2. For each graph convolution layer, we set the number of heads to 4 where two of them are forward-path Attention modules and the others are inverse-path Attention modules; Section IV.A.3) Two-Way Path Aggregation Thus, we adopt two types of Attention heads, incorporating them in the message-passing loop. This is similar with [22], [28] except we exploit different masks for each Attention head. Specifically, we define inverse neighbors as N-1(vi)={vk|eik∈E}∪{vi}.(14) Then, among H Attention heads, we set half of them to be forward-path graph Attention in Eq. (10) and the other half to be inverse-path graph Attention in Eq. (15). Attθ({h(k)j|vj∈N-1(vi)})(15) This graph path aggregation in a GCN with both forward-path and inverse-path is illustrated in Figure 3. Employing Attention from the two path types enables the model to learn features on predecessor conditions as well as successor conditions in a DAG while preserving their different relations; Figure 3
PNG
media_image1.png
231
588
media_image1.png
Greyscale
; Figure 3 Graph path aggregation with two path types, forward- and inverse-path: This illustrates how to produce the representation of node v7 in a DAG (in Figure 1) using the forward-path and inverse-path aggregation, where self-loops in the aggregate are omitted for simplicity; Equation 10:
PNG
media_image2.png
71
400
media_image2.png
Greyscale
); selecting a next node of potential next nodes according to a probability of each of the potential next nodes (Section IV.B.1) Sequential Node Selection As formulated in Eq. (5), we decompose the probability function of a priority order into a product of probabilities of node selection in sequence. The decoder chooses a node to have the highest priority by sampling from probability distribution pθ(π1|τ) . It then chooses another node with the next highest priority (i.e., the highest priority among nodes not chosen yet) by sampling from pθ(π2|π1,τ) . For each selection at step t , the embedding of a partial priority order (π1,…,πt−1,τ) is used to generate the respective conditioned probability. This procedure continues until no node is left, so it comprises n -iterative decoding.).
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 Lee to improve performance (see Lee Abstract With comprehensive evaluations, we verify that our model shows comparable performance to several state-of-the-art DAG task scheduling algorithms, and outperforms them by 2~3% in the slowdown of achieved makespans particularly in nontrivial system configurations where workloads are neither too small nor heavy compared to the given number of processors).
As per claim 2, Englert and Lee teach the processor-implemented method of claim 1. Englert 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 Lee teach the processor-implemented method of claim 1. Lee 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 (Section IV.B.2) Sampling Priority From the Distribution Here we describe our strategy for sampling πt from the distribution at step t in Eq. (19). We can conduct successive selection in a greedy way using πt=argmax(pθ(πt|π1,…,πt−1,τ)).(21) It is also possible to use stochastic sampling that randomly draws πt according to the distribution. Note that there are other sampling strategies than those simple approaches, e.g., A∗ [30], Beam Search; Section IV.B.1) Sequential Node Selection As formulated in Eq. (5), we decompose the probability function of a priority order into a product of probabilities of node selection in sequence. The decoder chooses a node to have the highest priority by sampling from probability distribution pθ(π1|τ) . It then chooses another node with the next highest priority (i.e., the highest priority among nodes not chosen yet) by sampling from pθ(π2|π1,τ) . For each selection at step t , the embedding of a partial priority order (π1,…,πt−1,τ) is used to generate the respective conditioned probability. This procedure continues until no node is left, so it comprises n -iterative decoding).
As per claim 4, Englert and Lee teach the processor-implemented method of claim 1. Lee teaches further comprising assigning, via an artificial neural network (ANN), the scheduling priorities to the multiple nodes with a single inference (Section IV.E.3) Baseline Reduction In model training, we employ an additional variance reduction technique with baseline [32]. Specifically, we exploit a greedy baseline method, similar to [21], in which a target model pθ and another base model pβ are used. The two models share the same neural network structure but have distinct θ and β parameters; Abstract Recently, deep reinforcement learning (DRL) was found to provide effective solutions to various combinatorial optimization problems. In this paper, inspired by recent achievements in DRL, we employ DRL techniques for scheduling a directed acyclic graph (DAG) task in which a set of non-preemptive subtasks are specified by precedence conditions among them; Section IV. paragraph 1 The modules are end-to-end trained through DRL to generate a priority order of a DAG task input; Figure 2; Section IV.B. paragraph 1 With the node embeddings (the final latent vectors h(k)i in Eq. (9)) from the encoder, for a DAG task τ of n nodes, the decoder sequentially selects nodes to generate an n -sized priority order; Section IV.D. paragraph 2 Therefore, the complexity to infer a priority order for a DAG task input is O(n2d2);).
As per claim 5, Englert and Lee teach the processor-implemented method of claim 1. Englert teaches in which the original graph comprises a directed acyclic graph ([0030] the graph is a directed acyclic graph (DAG)).
As per claim 6, Englert and Lee teach the processor-implemented method of claim 1. Lee teaches in which the scheduling priority is assigned based on one or more topological transforms (Figure 3; Section IV. paragraph 1 The modules are end-to-end trained through DRL to generate a priority order of a DAG task input, where the learning objective is to minimize the makespan of the task scheduled by the priority order. Specifically, we adapt graph learning with two-way path aggregation in the encoder to effectively extract the relational information in a DAG; Section IV.A.3) Two-Way Path Aggregation Thus, we adopt two types of Attention heads, incorporating them in the message-passing loop. This is similar with [22], [28] except we exploit different masks for each Attention head. Specifically, we define inverse neighbors as N-1(vi)={vk|eik∈E}∪{vi}.(14) Then, among H Attention heads, we set half of them to be forward-path graph Attention in Eq. (10) and the other half to be inverse-path graph Attention in Eq. (15). Attθ({h(k)j|vj∈N-1(vi)})(15) This graph path aggregation in a GCN with both forward-path and inverse-path is illustrated in Figure 3. Employing Attention from the two path types enables the model to learn features on predecessor conditions as well as successor conditions in a DAG while preserving their different relations).
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: at least one memory; and at least one processor coupled to the at least one 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 13, they are apparatus claims of claims 2, 3, 5, and 6, so they are rejected for similar reasons.
As per claim 11, Englert and Lee teach the apparatus of claim 8. Lee teaches in which the at least one processor is further configured to assign the scheduling priorities to the multiple nodes with a single inference (Figure 2; Section IV.B. paragraph 1 With the node embeddings (the final latent vectors h(k)i in Eq. (9)) from the encoder, for a DAG task τ of n nodes, the decoder sequentially selects nodes to generate an n -sized priority order; Section IV.D. paragraph 2 Therefore, the complexity to infer a priority order for a DAG task input is O(n2d2);).
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, 18, 19, and 20, they are non-transitory computer-readable medium claims of claims 2, 4, 5, and 6, so they are rejected for similar reasons.
As per claim 17, Englert and Lee teach the non-transitory computer-readable medium of claim 15. Lee 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 (Section IV.E.3) Baseline Reduction In model training, we employ an additional variance reduction technique with baseline [32]. Specifically, we exploit a greedy baseline method, similar to [21], in which a target model pθ and another base model pβ are used. The two models share the same neural network structure but have distinct θ and β parameters; Abstract Recently, deep reinforcement learning (DRL) was found to provide effective solutions to various combinatorial optimization problems. In this paper, inspired by recent achievements in DRL, we employ DRL techniques for scheduling a directed acyclic graph (DAG) task in which a set of non-preemptive subtasks are specified by precedence conditions among them; Section IV.B.2) Sampling Priority From the Distribution Here we describe our strategy for sampling πt from the distribution at step t in Eq. (19). We can conduct successive selection in a greedy way using πt=argmax(pθ(πt|π1,…,πt−1,τ)).(21) It is also possible to use stochastic sampling that randomly draws πt according to the distribution. Note that there are other sampling strategies than those simple approaches, e.g., A∗ [30], Beam Search; Section IV.B.1) Sequential Node Selection As formulated in Eq. (5), we decompose the probability function of a priority order into a product of probabilities of node selection in sequence. The decoder chooses a node to have the highest priority by sampling from probability distribution pθ(π1|τ) . It then chooses another node with the next highest priority (i.e., the highest priority among nodes not chosen yet) by sampling from pθ(π2|π1,τ) . For each selection at step t , the embedding of a partial priority order (π1,…,πt−1,τ) is used to generate the respective conditioned probability. This procedure continues until no node is left, so it comprises n -iterative decoding).
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 an original graph including multiple nodes connected by edges, each node of the multiple nodes 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 original 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 generating the topological order of the set of 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); and
means for executing the set of tasks in 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; [0057] The graph generator 262 generates a graph based at least in part on the order of algorithms (614). In an implementation, the graph is a directed acyclic graph including a set of nodes corresponding to the algorithms where each node indicates a particular processor provided by the electronic device for executing an algorithm. The heterogeneous scheduler 264 executes the particular functionality based on performing a traversal of the graph (616). In an implementation, the traversal is a topological traversal of the set of nodes).
Englert fails to teach means for assigning a scheduling priority to each node in the original graph based on an aggregate of outputs of a plurality of multi-head attention blocks, each multi-head attention block of the plurality of multi-head attention blocks operating on a different topologically transformed graph induced by the original graph; means for 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 original graph.
However, Lee teaches means for assigning a scheduling priority to each node in the original graph based on an aggregate of outputs of a plurality of multi-head attention blocks, each multi-head attention block of the plurality of multi-head attention blocks operating on a different topologically transformed graph induced by the original graph (Section I paragraph 7 Section IV presents our proposed encoder-decoder model structure with GCN-based DAG embeddings and Attention-based priority assignments for subtasks in a DAG; Section IV. paragraph 2 In the GCN-based encoder, the raw features of individual n nodes (or n subtasks) in a DAG task τ are first processed via a feed-forward network (FFN). The structural information of τ ’s task dependency graph is encoded via the message passing mechanism of a GCN, and then latent vectors of the nodes are generated. With the latent vectors, the Attention-based decoder generates a priority order for the nodes of τ; Section IV.A.2) Graph Level Embedding We exploit several Attention modules (heads) simultaneously and aggregate them to get the final latent representation. This is useful since different Attention heads can give weights more relevantly to different latent representations (h ). The Aggregate function is implemented using multi-head Attention, and is defined as Aggregateθ({h(k)j|vj∈N(vi)})=(Attθ,1⊕Attθ,2⊕…⊕Attθ,H) (12) where ⊕ concatenates vectors, and Attθ,1,…,Attθ,H are H -individual Attention modules. H denotes the number of distinct Attention heads per layer; Section V.A.3) Model Hyperparameters In the encoder, we set the number of graph convolution layers to K=2. For each graph convolution layer, we set the number of heads to 4 where two of them are forward-path Attention modules and the others are inverse-path Attention modules; Section IV.A.3) Two-Way Path Aggregation Thus, we adopt two types of Attention heads, incorporating them in the message-passing loop. This is similar with [22], [28] except we exploit different masks for each Attention head. Specifically, we define inverse neighbors as N-1(vi)={vk|eik∈E}∪{vi}.(14) Then, among H Attention heads, we set half of them to be forward-path graph Attention in Eq. (10) and the other half to be inverse-path graph Attention in Eq. (15). Attθ({h(k)j|vj∈N-1(vi)})(15) This graph path aggregation in a GCN with both forward-path and inverse-path is illustrated in Figure 3. Employing Attention from the two path types enables the model to learn features on predecessor conditions as well as successor conditions in a DAG while preserving their different relations; Figure 3
PNG
media_image1.png
231
588
media_image1.png
Greyscale
; Figure 3 Graph path aggregation with two path types, forward- and inverse-path: This illustrates how to produce the representation of node v7 in a DAG (in Figure 1) using the forward-path and inverse-path aggregation, where self-loops in the aggregate are omitted for simplicity; Equation 10:
PNG
media_image2.png
71
400
media_image2.png
Greyscale
); means for 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 original graph (Section IV.B.1) Sequential Node Selection As formulated in Eq. (5), we decompose the probability function of a priority order into a product of probabilities of node selection in sequence. The decoder chooses a node to have the highest priority by sampling from probability distribution pθ(π1|τ) . It then chooses another node with the next highest priority (i.e., the highest priority among nodes not chosen yet) by sampling from pθ(π2|π1,τ) . For each selection at step t , the embedding of a partial priority order (π1,…,πt−1,τ) is used to generate the respective conditioned probability. This procedure continues until no node is left, so it comprises n -iterative decoding; Section IV. Paragraph 2 In the GCN-based encoder, the raw features of individual n nodes (or n subtasks) in a DAG task τ are first processed via a feed-forward network (FFN). The structural information of τ ’s task dependency graph is encoded via the message passing mechanism of a GCN, and then latent vectors of the nodes are generated. With the latent vectors, the Attention-based decoder generates a priority order for the nodes of τ , establishing a probability distribution, i.e., pθ(π|τ) over priority orders π . ).
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 Lee to improve performance (see Lee Abstract With comprehensive evaluations, we verify that our model shows comparable performance to several state-of-the-art DAG task scheduling algorithms, and outperforms them by 2~3% in the slowdown of achieved makespans particularly in nontrivial system configurations where workloads are neither too small nor heavy compared to the given number of processors).
As per claim 23, Englert and Lee teach the apparatus of claim 22. Englert teaches 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 24, Englert and Lee teach the apparatus of claim 22. Lee 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 (Section IV.E.3) Baseline Reduction In model training, we employ an additional variance reduction technique with baseline [32]. Specifically, we exploit a greedy baseline method, similar to [21], in which a target model pθ and another base model pβ are used. The two models share the same neural network structure but have distinct θ and β parameters; Abstract Recently, deep reinforcement learning (DRL) was found to provide effective solutions to various combinatorial optimization problems. In this paper, inspired by recent achievements in DRL, we employ DRL techniques for scheduling a directed acyclic graph (DAG) task in which a set of non-preemptive subtasks are specified by precedence conditions among them; Section IV.B.2) Sampling Priority From the Distribution Here we describe our strategy for sampling πt from the distribution at step t in Eq. (19). We can conduct successive selection in a greedy way using πt=argmax(pθ(πt|π1,…,πt−1,τ)).(21) It is also possible to use stochastic sampling that randomly draws πt according to the distribution. Note that there are other sampling strategies than those simple approaches, e.g., A∗ [30], Beam Search; Section IV.B.1) Sequential Node Selection As formulated in Eq. (5), we decompose the probability function of a priority order into a product of probabilities of node selection in sequence. The decoder chooses a node to have the highest priority by sampling from probability distribution pθ(π1|τ) . It then chooses another node with the next highest priority (i.e., the highest priority among nodes not chosen yet) by sampling from pθ(π2|π1,τ) . For each selection at step t , the embedding of a partial priority order (π1,…,πt−1,τ) is used to generate the respective conditioned probability. This procedure continues until no node is left, so it comprises n -iterative decoding).
As per claim 25, Englert and Lee teach the apparatus of claim 22. Lee teaches further comprising means for assigning the scheduling priorities to the multiple nodes with a single inference (Figure 2; Section IV.B. paragraph 1 With the node embeddings (the final latent vectors h(k)i in Eq. (9)) from the encoder, for a DAG task τ of n nodes, the decoder sequentially selects nodes to generate an n -sized priority order; Section IV.D. paragraph 2 Therefore, the complexity to infer a priority order for a DAG task input is O(n2d2);).
As per claim 26, Englert and Lee teach the apparatus of claim 22. Englert teaches in which the original graph comprises a directed acyclic graph ([0030] the graph is a directed acyclic graph (DAG)).
As per claim 27, Englert and Lee teach the apparatus of claim 22. Lee teaches further comprising means for assigning the scheduling priorities to the multiple nodes based on one or more topological transforms (Figure 3; Section IV. paragraph 1 The modules are end-to-end trained through DRL to generate a priority order of a DAG task input, where the learning objective is to minimize the makespan of the task scheduled by the priority order. Specifically, we adapt graph learning with two-way path aggregation in the encoder to effectively extract the relational information in a DAG; Section IV.A.3) Two-Way Path Aggregation Thus, we adopt two types of Attention heads, incorporating them in the message-passing loop. This is similar with [22], [28] except we exploit different masks for each Attention head. Specifically, we define inverse neighbors as N-1(vi)={vk|eik∈E}∪{vi}.(14) Then, among H Attention heads, we set half of them to be forward-path graph Attention in Eq. (10) and the other half to be inverse-path graph Attention in Eq. (15). Attθ({h(k)j|vj∈N-1(vi)})(15) This graph path aggregation in a GCN with both forward-path and inverse-path is illustrated in Figure 3. Employing Attention from the two path types enables the model to learn features on predecessor conditions as well as successor conditions in a DAG while preserving their different relations).
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
