DETAILED ACTION
Claims 1-4, 6-16, and 18-23 are pending.
Claims 5 and 17 have been canceled.
Claims 1-4, 6-16, and 18-23 have been rejected.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Applicant’s following arguments with respect to the 35 U.S.C. 103 rejections (Remarks pp. 9-15) have been fully considered but are unpersuasive.
(1) Applicant states:
PNG
media_image1.png
540
666
media_image1.png
Greyscale
The Examiner respectfully disagrees. The claim does not recite “physical” or “logical” distance. Applicant’s arguments do not appear to be based on the claim language of the independent claims. Therefore, the premise of Applicant’s arguments is not valid.
Furthermore, even if the claim required logical distance, reference Xie’s Figure 5 already teaches it.
PNG
media_image2.png
362
382
media_image2.png
Greyscale
As shown in Fig. 5, there are weight/distances associated with the edges. The distances are logical.
Therefore, the combination of references Shuman and Xie teach “logical” distance as well. Xie states, “Ti from node to node Tj have communication relation, the weight of edges represents the cost of communication between the nodes,” ¶ 0039. The cost could be the logical distance between two nodes.
(2) Applicant also states:
PNG
media_image3.png
446
791
media_image3.png
Greyscale
PNG
media_image4.png
432
791
media_image4.png
Greyscale
The Examiner respectfully disagrees. The limitation “perform the topological sort based on the edge weight” means that the edge weights have some influence over the topological sorting process in some way.
The topological sort is mapped to the sorting process that includes the “partition[ing] the ordered list of nodes.” Note the claim recites “a topological sort.” There is no the “topological sort,” and there is no requirements in the claim of steps that must be included in or excluded from the claimed “topological sort.” As long as the Examiner’s reference teaches the features in the claim, the Examiner’s burden is satisfied.
Enrici teaches “perform a topological sort of the weighted dependency graph” and “generate a workload execution order based on the topological sort.”
Enrici discloses, “A topological sort or topological ordering may be performed on a directed graph to determine an execution order in which to perform the jobs defined in the directed graph,” ¶ 0032.
Enrici discloses, “At step S306-2, the computation unit 120 computes cut-sets for the dependency graph G based on the ordered list of nodes l such that an allocation of memory bandwidth based on the cut-sets fits into the capacity of the target memory. The computation unit 120 considers each node of the ordered list of nodes l one by one and determines cut-sets based on the output edges of each node,” ¶ 0081.
The partitioning to determine the cut-sets is based on the edge weight, as cited by paragraph 10 of Enrici, which states “The processing circuitry may be further configured to generate an ordered list of nodes in the DFST, partition the ordered list of nodes into at least two disjoint sets such that (i) a weight of edges in each of the at least two disjoint sets is less than or equal to a threshold memory capacity.”
The generated workload execution order could be based on a cut-set for the dependency graph G based on the ordered list of nodes.
Furthermore, reference Xie also provides a topological sort using edge weights as input for its graph, which could be an example that is similar to Enrici’s:
PNG
media_image2.png
362
382
media_image2.png
Greyscale
PNG
media_image5.png
251
389
media_image5.png
Greyscale
Fig. 5 teaches a weighted graph; and Fig. 9 teaches the workload execution order after the topological sort.
Xie discloses, “task graph conversion module uses a replication fork node, a method diagram into the DAG task product processing tree, traversing the product processing tree according to the layer sequence. the said product processing tree into multiple sub tree from up to down, from sub tree of the bottom, sequentially searching in the sub tree and priority scheduling on the critical path node, a scheduling sequence is formed, each scheduling complete a sub tree virtual the subtree as a node and adding the upper layer sub tree; until all the node scheduling to form the initial dispatching sequence…,” ¶ 0029,
“said processor kernel scheduling method based on adaptive critical path, shown in FIG. 5 is a generalized diagram of one application program, a rectangular frame in T represents node (corresponding to the task in the application program), the weight of node represents the execution time of the task. the oriented side represents Ti from node to node Tj have communication relation, the weight of edges represents the cost of communication between the nodes,” ¶ 0039, and
“…hierarchical search and priority scheduling mode node of the critical path is the node T2, T5, T7, Tltl are distributed to the same sequence execution. eliminates the communication overhead between T5 and Tltl. at the same time, the T1, T3 is individually formed sequence to enable the parallel execution and immediately before the node sequence of the T6 node, start time of node T6 in advance, so as to reduce the total task finish time,” ¶ 0051.
Here, the directed acyclic graph is partitioned as part of the sorting process based on the graph’s edge weights. The nodes are ordered in such a way that it reduces the communication cost overhead. Therefore, the sorting/ordering of the tasks is influenced by the communication cost, which is represented by the edge weight. Xie is similar to Enrici because Xie’s communication cost is similar to Enrici’s memory cost, as both are computational constraints.
(3) Applicant states:
PNG
media_image6.png
579
791
media_image6.png
Greyscale
The Examiner respectfully disagrees. Annotating a dependency graph with characteristics of workloads is further constructing said dependency graph based on the workloads by augmenting it with the workloads’ characteristics. Enrici states, “In one example, edges of dependency graphs may be annotated with a positive integer number n that denotes the input/output memory consumed/produced by a node upon execution, and nodes of dependency graphs may be annotated with timing characteristics (e.g., processing time of tasks).” This added data, based on the workloads, helps provide crucial information to users or systems regarding the tasks or resources used for the tasks, further supporting that the annotating of the dependency graph is a further construction.
(4) Applicant states:
PNG
media_image7.png
468
697
media_image7.png
Greyscale
The Examiner respectfully disagrees. The stated motivation for combining Shuman with Enrici in view of Xie is a sufficiently reasonable explanation. Allowing a user to understand the weight more intuitively based on the graph, for example, allows for the user to determine and compare the weights by inspecting the distances of the edges between each node in the figure by a simple look. No complex computation is required for the user to make a rough determination of the weights and their distribution on a graph.
Applicant, in the remarks, seems to argue that the claimed distance requires a logical distance. The Applicant also states that Shuman teaches physical distance. The Examiner has explained that if the claim were to require logical distance, this reference would be redundant because Xie already teaches logical distance.
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.
This application includes one or more claim limitations that use the word “means,” and are thus being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are all in Claim 12:
a means for receiving a plurality of workloads from a requestor;
a means for constructing 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;
a means for performing a topological sort of the weighted dependency graph;
and a means for generating a workload execution order based on the topological sort.
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.
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, 3, 6, 11-13, 15, 18, and 23 are rejected under 35 U.S.C. 103 as being unpatentable over Enrici (US 20220253482 A1) in view of Xie (CN 103336723 A), Shuman (“THE EMERGING FIELD OF SIGNAL PROCESSING ON GRAPHS”), and Wolfe (US 20220066834 A1).
Regarding Claim 1, Enrici teaches a processor-based device comprising a workload execution reordering circuit (
Enrici discloses, “At least one example embodiment provides a network device comprising: processing circuitry configured to determine a depth first search tree (DFST) based on a dependency graph included in a request to allocate memory bandwidth to a set of tasks,” ¶ 0004, “A topological sort or topological ordering may be performed on a directed graph to determine an execution order in which to perform the jobs defined in the directed graph,” ¶ 0032, and “In this example, the computation unit 120 may retrieve a heuristic from the library of algorithms 150. For example, a heuristic may be an algorithm that computes a DFST T, where each node is added to the DFST T based on a topological metric (e.g., number of input/output edges),” ¶ 0075.
The claimed “processor-based device” is mapped to the disclosed “network device”, and
The claimed “workload execution reordering circuit” is mapped to the disclosed “processing circuitry configured to determine a depth first search tree (DFST) based on a dependency graph” and “A topological sort or topological ordering may be performed on a directed graph to determine an execution order in which to perform the jobs defined in the directed graph”, as a sorting process reorders tasks/jobs. The ordering could also be based on changed input data or a changed directed graph due to changed determined dependencies.),
configured to: receive a plurality of workloads from a requestor, each workload comprising a sequence of instructions to be executed (
Enrici discloses, “One or more example embodiments provide a field-programmable gate array (FPGA) architecture that may enable improved memory bandwidth allocation for multi-tenant workloads that execute on FPGA nodes,” ¶ 0003, and “The network orchestrator 10 may be configured to deploy requests including an annotated dependency graph G (or any other workload) to the MBA [(memory bandwidth allocator)] 100,” ¶ 0040.
The claimed “workload comprising a sequence of instructions to be executed” is mapped to the disclosed “multi-tenant workloads” being executed on FPGA nodes.
The claimed “receive a plurality of workloads” is mapped to the disclosed “deploy requests including an annotated dependency graph G (or any other workload)”.
The claimed “requestor” is mapped to the disclosed “network orchestrator”.);
construct a weighted dependency graph based on the plurality of workloads (
Enrici discloses, “Dependency graphs may be annotated. In one example, edges of dependency graphs may be annotated with a positive integer number n that denotes the input/output memory consumed/produced by a node upon execution, and nodes of dependency graphs may be annotated with timing characteristics (e.g., processing time of tasks),” ¶ 0030, “The network orchestrator 10 may obtain dependency graphs for individual users by, e.g., automatically extracting the dependency graphs from user specifications (e.g., programming languages, model-based specifications, etc.)… The MBA 100 may generate the dependency graph G based on a union of the plurality of dependency graphs for individual users in any suitable manner,” ¶ 0048, and “…dependency graph G for which the weight of cross-edges fits a memory capacity.” ¶ 0066.),
wherein the weighted dependency graph comprises: a plurality of vertices, each corresponding to a workload of the plurality of workloads (
Enrici discloses, “a depth first search tree (DFST) based on a dependency graph included in a request to allocate memory bandwidth to a set of tasks, determine a set of groups of edges and nodes in the dependency graph based on the DFST,” ¶ 0004, and “Nodes in V denote units of work (e.g., tasks, jobs, etc.),” ¶ 0028.)
The claimed “a plurality of vertices” is mapped to the disclosed “nodes”.
The claimed “each corresponding to a workload of the plurality of workloads” is mapped to the disclosed “Nodes in V denote units of work”.);
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 (
Enrici discloses, “Edges in E denote precedence constraints (dependencies); for instance, edge (x,y) means that task x must be executed before task y.” ¶ 0028.)
perform a topological sort of the weighted dependency graph (
Enrici discloses, “topological sort or topological ordering may be performed on a directed graph,” ¶ 0032.);
generate a workload execution order based on the topological sort (
Enrici discloses, “A topological sort or topological ordering may be performed on a directed graph to determine an execution order in which to perform the jobs defined in the directed graph,” ¶ 0032.);
and schedule the plurality of workloads based on the workload execution order (
Enrici discloses, “A topological sort or topological ordering may be performed on a directed graph to determine an execution order in which to perform the jobs defined in the directed graph,” ¶ 0032.);
wherein: the workload execution reordering circuit is configured to construct the weighted dependency graph (
Enrici discloses, “The processing circuitry may be further configured to generate an ordered list of nodes in the DFST, partition the ordered list of nodes into at least two disjoint sets such that (i) a weight of edges in each of the at least two disjoint sets is less than or equal to a threshold memory capacity,” ¶ 0010.
The claimed “weighted dependency graph” is mapped to the disclosed “partition the ordered list of nodes into at least two disjoint sets such that (i) a weight of edges in each of the at least two disjoint sets”.
); and the workload execution reordering circuit is configured to perform the topological sort based on the edge weight (
Enrici discloses, “topological sort or topological ordering may be performed on a directed graph” ¶ 0032, and “The processing circuitry may be further configured to generate an ordered list of nodes in the DFST, partition the ordered list of nodes into at least two disjoint sets such that (i) a weight of edges in each of the at least two disjoint sets is less than or equal to a threshold memory capacity,” ¶ 0010. In other words, the partitioning of the ordered list of nodes creates a graph of weighted edges, which is then automatically ordered by a topological sort later on.).
Enrici does not teach wherein
wherein the topological sort results in a linear ordering of the plurality of vertices such that, for every directed edge uv from a first vertex u to a second vertex v, the first vertex u is before the second vertex v in the linear ordering
a directed edge among the one or more directed edges represents a cross-thread dependency between the corresponding two workloads.
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
However, Xie teaches wherein a directed edge among the one or more directed edges represents a cross-thread dependency between the corresponding two workloads (
PNG
media_image2.png
362
382
media_image2.png
Greyscale
PNG
media_image8.png
366
592
media_image8.png
Greyscale
Xie discloses, “there is data dependency between tasks, the dependency relationship is such that a certain task node to start executing, all of its predecessor task must have been executed. and the special structure of the multi-core processor so that the communication time between kernel is far more than the communication time on the core, and copying by task processing the task graph, it can obtain more effectively control the communication time between the processor core.” ¶ 0011. This is illustrated in the above Figures 5 and 9.
For example, in Figure 5, it can be seen that task 4 depends on task 1. Figure 9 shows that task 4 executes on processor 3, while task 1 executes on processor 3, but also executes on processors 1 and 4. Therefore, Task 4 depends on Task 1 in a cross-thread dependency.)
Enrici and Xie are both considered to be analogous to the claimed invention because they are in the same field of structure ordering. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici to incorporate the teachings of Xie and provide wherein a directed edge among the one or more directed edges represents a cross-thread dependency between the corresponding two workloads. Doing so would help increase efficiency of the processing of the workloads (Xie discloses, “…it can obtain more effectively control the communication time between the processor core,” ⁋ 0011).
Enrici in view of Xie does not teach
wherein the topological sort results in a linear ordering of the plurality of vertices such that, for every directed edge uv from a first vertex u to a second vertex v, the first vertex u is before the second vertex v in the linear ordering
constructing 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.
However, Shuman teaches wherein: 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 (
Shuman discloses, “For instance, the edge weight may be inversely proportional to the physical distance between nodes in the network,” Page 83.
After the combination of Enrici in view of Xie, with Shuman, the directed edge from Enrici in view of Xie is assigned an edge weight that is inversely proportional to the distance between nodes in a graph according to Shuman, and the nodes correspond to the workloads from Enrici in view of Xie.).
Enrici in view of Xie, and Shuman are both considered to be analogous to the claimed invention because they are in the same field of structure ordering. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie to incorporate the teachings of Shuman and provide 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. Doing so would allow a user to understand the weight more intuitively based on the graph, because the user can associate the distance (which is visual information) to the weight.
Enrici in view of Xie and Shuman does not teach wherein the topological sort results in a linear ordering of the plurality of vertices such that, for every directed edge uv from a first vertex u to a second vertex v, the first vertex u is before the second vertex v in the linear ordering.
However, Wolfe teaches wherein the topological sort results in a linear ordering of the plurality of vertices such that, for every directed edge uv from a first vertex u to a second vertex v, the first vertex u is before the second vertex v in the linear ordering (
Wolfe discloses, “embodiments of the present disclosure can generate a topological ordering (e.g., a linear ordering of nodes) based on the graph,” ¶ 0030.).
Enrici in view of Xie and Shuman, and Wolfe are both considered to be analogous to the claimed invention because they are in the same field of scheduling. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie and Shuman to incorporate the teachings of Wolfe and provide wherein the topological sort results in a linear ordering of the plurality of vertices such that, for every directed edge uv from a first vertex u to a second vertex v, the first vertex u is before the second vertex v in the linear ordering. Doing so would allow for a more efficient and reliable scheduling of the workloads.
Claims 12, 13 and 23 are a processor-based device means, method, and non-transitory computer-readable medium claim, respectively, corresponding to the processor-based device of Claim 1. Therefore, Claims 12, 13 and 23 are rejected for the same reason set forth in the rejection of Claim 1.
Regarding Claim 3, Enrici in view of Xie, Shuman, and Wolfe teaches the processor-based device of claim 1, wherein the weighted dependency graph comprises a Directed Acyclic Graph (DAG). (
Enrici discloses, “Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u, v) (from vertex u to vertex v), u comes before v in the ordering. Such a strict topological ordering is possible only if the graph is acyclic.” ¶ 0032.)
Claim 15 is a method claim corresponding to the processor-based device Claim 3. Therefore, Claim 15 is rejected for the same reason set forth in the rejection of Claim 3.
Regarding Claim 6, Enrici in view of Xie, Shuman, and Wolfe teaches the method of claim 1, wherein the edge weight is inversely related to the distance between the two vertices corresponding to the two workloads (
Shuman discloses, “For instance, the edge weight may be inversely proportional to the physical distance between nodes in the network,” Page 83.
After the combination of Enrici in view of Xie, with Shuman, the directed edge from Enrici in view of Xie is assigned an edge weight that is inversely proportional to the distance between nodes in a graph according to Shuman, and the nodes correspond to the workloads from Enrici in view of Xie.).
Enrici in view of Xie, and Shuman are both considered to be analogous to the claimed invention because they are in the same field of vertex manipulation. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie to incorporate the teachings of Shuman and provide wherein the edge weight is inversely related to the distance between the two vertices. Doing so would allow a user to understand the weight more intuitively based on the graph, because the user can associate the distance (which is visual information) to the weight.
Claim 18 is a method claim corresponding to the processor-based device Claim 6. Therefore, Claim 18 is rejected for the same reason set forth in the rejection of Claim 6.
Regarding Claim 11, Enrici in view of Xie, Shuman, and Wolfe teaches integrated into a device selected from the group consisting of: a set top box; an entertainment unit; a navigation device; a communications device; a fixed location data unit; a mobile location data unit; a global positioning system (GPS) device; a mobile phone; a cellular phone; a smart phone; a session initiation protocol (SIP) phone; a tablet; a phablet; a server; a computer; a portable computer; a mobile computing device; a wearable computing device; a desktop computer; a personal digital assistant (PDA); a monitor; a computer monitor; a television; a tuner; a radio; a satellite radio; a music player; a digital music player; a portable music player; a digital video player; a video player; a digital video disc (DVD) player; a portable digital video player; an automobile; a vehicle component; avionics systems; a drone; and a multicopter (
Enrici discloses, “At least one example embodiment provides a network device…” ¶ 0004).
Claims 2 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Enrici (US 20220253482 A1) in view of Xie (CN 103336723 A), Shuman (“THE EMERGING FIELD OF SIGNAL PROCESSING ON GRAPHS”), Wolfe (US 20220066834 A1), and Addala (US 20100070973 A1).
Regarding Claim 2, Enrici in view of Xie, Shuman, and Wolfe teaches the method of claim 1. Enrici in view of Xie, Shuman, and Wolfe does not teach wherein the workload execution reordering circuit is configured to schedule the plurality of workloads based on the workload execution order by being configured to schedule an independent workload among the plurality of workloads to execute during idle time between two dependent workloads among the plurality of workloads, based on the workload execution order.
However, Addala teaches wherein the workload execution reordering circuit is configured to schedule the plurality of workloads based on the workload execution order by being configured to schedule an independent workload among the plurality of workloads to execute during idle time between two dependent workloads among the plurality of workloads, based on the workload execution order. (
Addala discloses, “Although not shown in flowchart 100, it is important to note that the calling application instance can continue to execute parallel task flows (i.e., task flows independent of the currently paused flow) while the generic wait service is waiting for status information in step 206. In other words, the generic wait service operates asynchronously of the calling instance. Once the generic wait service receives notification that the exit criterion is satisfied and sends that information to the calling instance, the calling instance can resume execution of the paused task flow.” ⁋ 0042.
The claimed “independent workload” is mapped to the disclosed “task flows independent of the currently paused flow”).
The claimed “two dependent workloads” is mapped to the disclosed split “paused flow”. The “paused flow” is split into two parts and thus considered to be a pair of “dependent workloads”.
Enrici in view of Xie, Shuman, and Wolfe, and Addala are both considered to be analogous to the claimed invention because they are in the same field of workload scheduling. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie, Shuman, and Wolfe to incorporate the teachings of Addala and provide wherein the workload execution reordering circuit is configured to schedule the plurality of workloads based on the workload execution order by being configured to schedule an independent workload among the plurality of workloads to execute during idle time between two dependent workloads among the plurality of workloads, based on the workload execution order. Doing so would help ensure greater efficiency of the workload scheduling (Addala discloses, “Third, since the logic for implementing pausing functionality is encapsulated in the generic wait service, this logic does not need to duplicated in the service-oriented applications or the event producers, thereby reducing code duplication and increasing development productivity,” ⁋ 0034).
Claim 14 is a method claim corresponding to the processor-based device Claim 2. Therefore, Claim 14 is rejected for the same reason set forth in the rejection of Claim 2.
Claims 4 and 16 are rejected under 35 U.S.C. 103 as being unpatentable Enrici (US 20220253482 A1) in view of Xie (CN 103336723 A), Shuman (“THE EMERGING FIELD OF SIGNAL PROCESSING ON GRAPHS”), Wolfe (US 20220066834 A1), and Dechu (US 20230367619 A1).
Regarding Claim 4, Enrici in view of Xie, Shuman, and Wolfe teaches the method of claim 1. Enrici in view of Xie, Shuman, and Wolfe does not teach wherein the workload execution reordering circuit is configured to perform the topological sort based on Kahn's topological sorting algorithm.
However, Dechu teaches wherein the workload execution reordering circuit is configured to perform the topological sort based on Kahn's topological sorting algorithm. (Dechu discloses, “Ordering 450 the agents may use an algorithm based on topological ordering using a directed acyclic graph (DAG) and use, for example, Kahn's topological sorting algorithm.” ⁋ 0069).
Enrici in view of Xie, Shuman, and Wolfe, and Dechu are both considered to be analogous to the claimed invention because they are in the same field of workload scheduling. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie, Shuman, and Wolfe to incorporate the teachings of Dechu and provide wherein the workload execution reordering circuit is configured to perform the topological sort based on Kahn's topological sorting algorithm. Doing so would help sort the graph more efficiently or conveniently in certain situations. For example, Kahn’s topological sorting algorithm may better enable the system to detect cycles in the graph compared to depth first search, the sorting algorithm used in Enrici in view of Xie, Shuman, and Wolfe. Further, it would also have been a simple substitution of one known element for another to obtain predictable results. Kahn's topological sorting algorithm is a known element, and so is the depth first search used in Enrici in view of Xie, Shuman, and Wolfe (Enrici discloses, “An example algorithm for computing a scheduling (or execution order) for tasks in a flow graph is the Depth First Search (DFS),” ⁋ 0033). The substitution of these similar algorithms produces predictable results.
Claim 16 is a method claim corresponding to the processor-based device Claim 4. Therefore, Claim 16 is rejected for the same reason set forth in the rejection of Claim 4.
Claims 7-8 and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over Enrici (US 20220253482 A1) in view of Xie (CN 103336723 A), Shuman (“THE EMERGING FIELD OF SIGNAL PROCESSING ON GRAPHS”), Wolfe (US 20220066834 A1), de Jong (US 20220050642 A1), and Zhang (US 20130226840 A1).
Regarding Claim 7, Enrici in view of Xie, Shuman, and Wolfe teaches the method of claim 1. Enrici in view of Xie, Shuman, and Wolfe does not teach 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.
However, de Jong teaches 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 (de Jong discloses, “The directed graph may be a weighted directed graph, wherein the weight on a vertex of the weighted directed graph represents an estimated execution time of the process step represented by the vertex, the estimated execution time being determined by the digital process controller.”, ⁋ 0016.
PNG
media_image9.png
582
823
media_image9.png
Greyscale
PNG
media_image10.png
582
828
media_image10.png
Greyscale
Figure 2 shows a potential cross-thread dependency, while Figure 3 shows a workflow of tasks that is independent from the potential cross-thread dependency in Figure 2.
);
Enrici in view of Xie, Shuman, and Wolfe, and de Jong are both considered to be analogous to the claimed invention because they are in the same field of workload scheduling. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie, Shuman, and Wolfe to incorporate the teachings of de Jong and provide 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. Doing so can help estimate remaining execution time for each workload. (De Jong discloses, “The digital process controller may comprise a track and trace mechanism for tracking and tracing the status and progress information of a validation of each process step.,” ⁋ 0018).
Enrici in view of Xie, Shuman, Wolfe, and de Jong does not teach wherein the workload execution reordering circuit is configured to perform the topological sort further based on the one or more vertex weights.
However, Zhang teaches wherein the workload execution reordering circuit is configured to perform the topological sort further based on the one or more vertex weights (
Zhang discloses, “Thereafter, the analyzer module sorts all vertices in the graph according to their post-balancing vertex weights in a decreasing order,” ⁋ 0022).
Enrici in view of Xie, Shuman, Wolfe, and de Jong, and Zhang are both considered to be analogous to the claimed invention because they are in the same field of workload scheduling. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie, Shuman, Wolfe, and de Jong to incorporate the teachings of Zhang and provide wherein the workload execution reordering circuit is configured to perform the topological sort further based on the one or more vertex weights. Doing so can help ensure that the sorted graph is more human-readable. (Zhang discloses, “The sequence of vertex values and identifications of the corresponding vertices can be produces as computational output of the analyzer module for review by a user or used as input for further computations,” ⁋ 0022).
Claim 19 is a method claim corresponding to the processor-based device Claim 7. Therefore, Claim 19 is rejected for the same reason set forth in the rejection of Claim 7.
Regarding Claim 8, Enrici in view of Xie, Shuman, Wolfe, de Jong, and Zhang teaches the method of claim 7, wherein each vertex weight of the one or more vertex weights is based on a logical distance from the vertex corresponding to the vertex weight to a vertex corresponding to the workload that caused the cross-thread dependency. (
PNG
media_image11.png
597
852
media_image11.png
Greyscale
De Jong discloses, “The directed graph may be a weighted directed graph, wherein the weight on a vertex of the weighted directed graph represents an estimated execution time of the process step represented by the vertex, the estimated execution time being determined by the digital process controller.” ⁋ 0016. The disclosure and figure 2 illustrate that the logical distance from one vertex to another is the execution time of the process steps between the two vertices.).
Enrici in view of Xie, Shuman, and Wolfe, and de Jong are both considered to be analogous to the claimed invention because they are in the same field of workload scheduling. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie, Shuman, and Wolfe to incorporate the teachings of de Jong and provide wherein each vertex weight of the one or more vertex weights is based on a logical distance from the vertex corresponding to the vertex weight to a vertex corresponding to the workload that caused the cross-thread dependency. Doing so can help estimate remaining execution time for each workload using the logical distance between vertices.
Claim 20 is a method claim corresponding to the processor-based device Claim 8. Therefore, Claim 20 is rejected for the same reason set forth in the rejection of Claim 8.
Claims 9 and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Enrici (US 20220253482 A1) in view of Xie (CN 103336723 A), Shuman (“THE EMERGING FIELD OF SIGNAL PROCESSING ON GRAPHS”), Wolfe (US 20220066834 A1), de Jong (US 20220050642 A1), Zhang (US 20130226840 A1), and Sharma (US 20180121348 A1).
Regarding Claim 9, Enrici in view of Xie, Shuman, Wolfe, de Jong, and Zhang teaches the method of claim 7, wherein the workload execution reordering circuit is configured to perform the topological sort. Enrici in view of Xie, Shuman, Wolfe, de Jong, and Zhang does not teach the workload execution reordering circuit 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.
However, Sharma teaches assign[ing] 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. (Sharma discloses, “…a user can configure a node priority and topologically sort the nodes that are fed to the algorithm in order of priority,” ⁋ 0039).
Enrici in view of Xie, Shuman, Wolfe, de Jong, and Zhang, and Sharma are both considered to be analogous to the claimed invention because they are in the same field of vertex processing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have Enrici in view of Xie, Shuman, Wolfe, de Jong, and Zhang to incorporate the teachings of Sharma and provide 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. Doing so would help improve the overall performance of the process. (Sharma discloses, “Note that the order of nodes being visited matters in the performance of the garbage collection.” ⁋ 0039).
Claim 21 is a method claim corresponding to the processor-based device Claim 9. Therefore, Claim 21 is rejected for the same reason set forth in the rejection of Claim 9.
Claims 10 and 22 are rejected under 35 U.S.C. 103 as being unpatentable over Enrici (US 20220253482 A1) in view of Xie (CN 103336723 A), Shuman (“THE EMERGING FIELD OF SIGNAL PROCESSING ON GRAPHS”), Wolfe (US 20220066834 A1), de Jong (US 20220050642 A1), Zhang (US 20130226840 A1), Sharma (US 20180121348 A1), and Niu (CN 109034578 A).
Regarding Claim 10, Enrici in view of Xie, Shuman, Wolfe, de Jong, Zhang, and Sharma teaches the method of claim 9, wherein the vertex priority is determined. Enrici in view of Xie, Shuman, Wolfe, de Jong, Zhang, and Sharma does not teach wherein the vertex priority is determined based on an identity of each vertex, a vertex weight of the vertex, and an edge weight of an edge of the vertex.
However, Niu teaches wherein the vertex priority is determined based on an identity of each vertex, a vertex weight of the vertex, and an edge weight of an edge of the vertex. (Niu discloses, “Composite network node important degree evaluation model of comprehensive traffic transportation network mainly comprises:
5.1, constructed based on the sub network topology model of L space, calculating the weight of network topology graph edge; 5.2, constructing comprehensive transportation network composite network topology, calculating the weight and distance of the composite network edge; 5.3, calculating the weighted node and weighted node index, and standardization processing; 5.4, calculating the composite network node importance degree.” ⁋⁋ 0067, 0068).
Enrici in view of Xie, Shuman, Wolfe, de Jong, Zhang, and Sharma, and Niu are both considered to be analogous to the claimed invention because they are in the same field of vertex processing. Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Enrici in view of Xie, Shuman, Wolfe, de Jong, Zhang, and Sharma to incorporate the teachings of Niu and provide wherein the vertex priority is determined based on an identity of each vertex, a vertex weight of the vertex, and an edge weight of an edge of the vertex. Doing so ensures that nodes that are of high importance can be processed with priority. (Niu discloses, “The embodiment of the invention can effectively identify the key node of comprehensive transportation network in the network system reliability improved,” ⁋ 0050).
Claim 22 is a method claim corresponding to the processor-based device Claim 10. Therefore, Claim 22 is rejected for the same reason set forth in the rejection of Claim 10.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Boss et al. (US 20230187068 A1): Methods, Apparatuses and Computer Program Products for Generating Predicted Member Query Vertices in a Healthcare Graph Data Object
Malabarba (US 20190005025 A1): Performing Semantic Graph Search
Fukuda et al. (US 20090281845 A1): Method and Apparatus of Constructing and Exploring KPI Networks
Firnkes (US 20210097081 A1): Throughput Optimization in Distributed Database Systems Using Hypergraph Partitioning
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ANDREW SUN whose telephone number is (571)272-6735. The examiner can normally be reached Monday-Friday 8:00-5:00.
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.
/ANDREW NMN SUN/Examiner, Art Unit 2195
/Aimee Li/Supervisory Patent Examiner, Art Unit 2195
Prosecution Insights