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 .
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 1/22/2026 has been entered.
Response to Arguments
The objection to the abstract is withdrawn in view of Applicant’s amendment.
The Examiner appreciates Applicant’s statement that Applicant agrees with the Examiner’s Interpretation of Claim 12 under 35 U.S.C. § 112(f) (Remarks p. 9).
Applicant’s arguments with respect to the 35 U.S.C. 101 rejections (Remarks pp. 9-11) have been fully considered. The 35 U.S.C. 101 rejections have been withdrawn in view of the arguments and amendments.
Applicant’s following arguments with respect to the 35 U.S.C. 103 rejections (Remarks pp. 11-18) have been fully considered but are unpersuasive.
(1) Applicant states that Enrici does not disclose “dependency graphs” being generated based on a “plurality of workloads” (Remarks pp. 12-13), stating that “paragraph 0048 of Enrici describes a first ‘dependency graph G’ being generated ‘based on a union of the plurality of dependency graphs for individual users in any suitable manner.’ Enrici, 0048. While Enrici further notes in paragraph 0030 that the ‘dependency graphs for individual users’ may be ‘automatically extract[ed] ... from user specifications,’ Applicant respectfully submits that there is no disclosure or suggestion in Enrici that such ‘dependency graphs’ (either ‘dependency graph G’ or the ‘dependency graphs for individual users’) are constructed ‘based on [a] plurality of workloads,’ as amended claim 1 recites (emphasis added).”
The Examiner respectfully disagrees. Paragraph 30 of Enrici states that a dependency graph can be annotated with characteristics of workloads, meaning that they can be initialized/generated based on the characteristics of the 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.).
(2) Applicant also states that the Final Office Action's statement regarding what Xie "probably" teaches is an implicit acknowledgement that the "value '8"' referenced by Xie does not necessarily disclose the "edge weight derived from a distance between two vertices" recited by claim 1. Applicant also states that that the machine translation of Xie (attached hereto as Appendix A) indicates in paragraph 0039 that the "weight of edges [such as the "value '8"' relied upon by the Final Office Action] represents the cost of communication between the nodes," not a "distance between two nodes" (Remarks p. 13).
The Examiner respectfully disagrees.
PNG
media_image1.png
362
382
media_image1.png
Greyscale
Here, Xie’s Fig. 5 showcases “8” as a value assigned to an edge between T1 and T3. Such a value assigned to an edge can be considered an edge weight, and said value can also be considered a distance between T1 and T3. Thus, “probably” means, more likely than not, Xie teaches/suggests the “edge weight derived from a distance between two vertices” recited by claim 1. Furthermore, the “distance between two nodes” is not required to be a physical distance between two nodes. A “cost of communication between the nodes” can be considered to be a distance between nodes, as a higher cost of communication could be represented as a higher distance, meaning that the greater the distance, the more costly communication between two nodes will be. Further, the Examiner’s secondary reference Shuman also address the feature.
(3) Applicant states that Enrici does not disclose or suggest “perform[ing] the topological sort based on the edge weight,” because it is not equivalent to “sort[ing] the edge weight” (Remarks pp. 13-14), stating that “the recited ‘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.’ This ‘linear ordering’ is determined using the recited ‘edge weights’ as described in, e.g., paragraphs 0040-0043 of the Application as filed, but does not necessarily result in a sorting by the ‘edge weights.’”
The Examiner respectfully disagrees.
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.
The Examiner introduced a new reference Wolfe to address features related to “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.”
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_image1.png
362
382
media_image1.png
Greyscale
PNG
media_image2.png
366
592
media_image2.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_image3.png
582
823
media_image3.png
Greyscale
PNG
media_image4.png
582
828
media_image4.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_image5.png
597
852
media_image5.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
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