DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 21-40 are pending in this application. Claims 1-20 were cancelled.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 21-40 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Claim 21 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1, Statutory Category: Yes, the claim 21 is a method that recites a series of steps and therefore falls in the statutory category of a process.
Step 2A- Prong 1: Judicial Exception Recited: Yes, the claim recites: “evaluating execution logs for an application having a plurality of services to identify different critical paths of the application during multiple previous executions of the application; identifying a statistical critical path for the application based at least on frequency of occurrence of the different critical paths in the execution logs; and scheduling individual services of the plurality of services of the application based at least on whether the individual services occur on the statistical critical path.” As drafted, the claim as a whole recites a method including steps that could be performed in the human mind, but for the recitation of generic computing components. The human mind can easily judging/evaluating execution logs for an application having a plurality of services to identify different critical paths of the application during multiple previous executions of the application, identifying/determining a statistical critical path for the application based at least on frequency of occurrence of the different critical paths in the execution logs, and scheduling/assigning individual services of the plurality of services of the application based at least on whether the individual services occur on the statistical critical path. Therefore, but for the recitation of generic computing components, these steps may be a Mental Processes that can be performed in the human mind (including an observation, evaluation, judgment, opinion).
Therefore, yes, the claims do recite judicial exceptions.
Step 2A- Prong 2: Integrated into a practical Application: No, this judicial exception is not integrated into a practical application. In particular, the claim recites an additional limitations that “computing device” and “wherein the execution logs identify at least one other critical path of the application other than the statistical critical path and the statistical critical path determines overall latency of the application more frequently than the at least one other critical path” which is directed to Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a generic computer as a tool to perform an abstract idea (see MPEP 2106.05(f)). Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they not impose any meaningful limits on practicing the abstract idea. Therefore, the claim is directed to the abstract idea.
Step 2B: Claim provides an Inventive Concept: No. The additional element that “computing device” and “wherein the execution logs identify at least one other critical path of the application other than the statistical critical path and the statistical critical path determines overall latency of the application more frequently than the at least one other critical path” which is directed to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a generic computer as a tool to perform an abstract idea (see MPEP 2106.05(f)). These additional elements and combination of the elements does not amount to significant more than the exception itself or provide an inventive concept in Step 2B.
For these reasons, there is no inventive concept in the claim, and thus the claim is ineligible.
Independent claims 27 and 35 are rejected for the same reason as claim 1 above. Claim 27 further recites “A system comprising: a processing unit; and a computer-readable storage medium storing computer-readable instructions which, when executed by the processing unit, cause the system to”. Claim 35 further recites “A computer-readable storage media storing executable instructions which, when executed by a processing unit, cause the processing unit to perform acts comprising”. These additional elements are directed to generic computing components/functions (MPEP § 2106.05(b) merely applying the abstract idea (MPEP § 2106.05(f)).
With respect to the dependent claim 22, the claim elaborates that wherein the scheduling comprises assigning scheduling priorities to threads allocated to the individual services. (“assigning scheduling priorities” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind. Further, the claim as a whole is a Mental Processes that can be performed in the human mind (including an observation, evaluation, judgment, opinion)).
With respect to the dependent claim 23, the claim elaborates that wherein the scheduling comprises: prioritizing specific services that occur on the statistical critical path above one or more other services that do not occur on the statistical critical path (“prioritizing specific services” as being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind. Further, the claim as a whole is a Mental Processes that can be performed in the human mind (including an observation, evaluation, judgment, opinion)).
With respect to the dependent claim 24, the claim elaborates that determining respective time distances of the one or more other services from the statistical critical path; and prioritizing the one or more other services based at least on the respective time distances of the one or more other services from the statistical critical path (“determining” and “prioritizing” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind. Further, the claim as a whole is a Mental Processes that can be performed in the human mind (including an observation, evaluation, judgment, opinion)).
With respect to the dependent claim 25, the claim elaborates that wherein determining the respective time distances of the one or more other services from the statistical critical path comprises: based at least on previous execution times of the one or more other services, determining the respective time distances as respective amounts of time that the one or more other services would have had to run before appearing in the statistical critical path (“determining the respective time distances” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind. Further, the claim as a whole is a Mental Processes that can be performed in the human mind (including an observation, evaluation, judgment, opinion)).
With respect to the dependent claim 26, the claim elaborates that wherein the statistical critical path comprises a particular path through the application that, over the multiple previous executions, most frequently is the critical path of the application (“wherein the statistical critical path comprises a particular path through the application that, over the multiple previous executions, most frequently is the critical path of the application” are directed to Adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea (see MPEP 2106.05(f)).
With respect to the dependent claim 28, the claim elaborates that wherein the computer-readable instructions, when executed by the processing unit, cause the system to: access a dependency graph of the application; and assign scheduling priorities to the individual services based at least on distances of the individual services from a root node of the dependency graph (“access a dependency graph of the application” which is insignificant pre-solution data gathering (see MPEP § 2106.05(g)). And “assign scheduling priorities” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 29, the claim elaborates that wherein the computer-readable instructions, when executed by the processing unit, cause the system to: identify at least two different services in a particular layer of the dependency graph; and assign a relatively higher scheduling priority to a particular service in the particular layer that occurs on the statistical critical path and a relatively lower scheduling priority to another service in the particular layer that does not occur on the statistical critical path (“identify at least two different services”, “assign a relatively higher scheduling priority…” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 30, the claim elaborates that wherein the computer-readable instructions, when executed by the processing unit, cause the system to: assign higher priorities to first services in a first layer that is relatively closer to the root node than the particular layer; and assign lower priorities to second services in a second layer that is relatively further from the root node than the particular layer (“assign higher priorities…” and “assign lower priorities to second services” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 31, the claim elaborates that wherein the computer-readable instructions, when executed by the processing unit, cause the system to: identify at least two different services of the application for which input data is ready; and schedule a first service of the at least two different services that is on the statistical critical path before a second service of the at least two different services that is not on the statistical critical path (“identify at least two different services…” and “schedule a first service…” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 32, the claim elaborates that wherein the computer-readable instructions, when executed by the processing unit, cause the system to: schedule a third service of the at least two different services before a fourth service of the at least two different services based at least on the third service having occurred more frequently in the different critical paths of the application than the fourth service (“schedule a third service…” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 33, the claim elaborates that wherein the computer-readable instructions, when executed by the processing unit, cause the system to: schedule a third service of the at least two different services before a fourth service of the at least two different services based at least on the third service being relatively closer to the statistical critical path of the application than the fourth service (“schedule a third service…” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 34, the claim elaborates that wherein the individual services are scheduled to run on at least two different computing clusters (“scheduled to run on at least two different computing clusters” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 36, the claim elaborates that wherein the scheduling the individual services is further based at least on where the individual services occur in a dependency graph of the application. (“scheduling the individual services is further based at least on where the individual services occur in a dependency graph of the application” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 37, the claim elaborates that wherein the scheduling the individual services is further based at least on proximity of the individual services to a root node of the dependency graph (“wherein the scheduling the individual services is further based at least on proximity of the individual services to a root node of the dependency graph” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 38, the claim elaborates that wherein scheduling the individual services comprises determining distances of the individual services from the statistical critical path and scheduling the individual services based at least on the distances (“determining distances of the individual services… and scheduling” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 39, the claim elaborates that wherein scheduling the individual services is based at least on an expected resource conflict (“wherein scheduling the individual services is based at least on an expected resource conflict” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
With respect to the dependent claim 40, the claim elaborates that wherein the scheduling comprises preferentially scheduling a first service to complete before a second service based on expected usage of a particular resource by the first service and the second service (“preferentially scheduling a first service to complete before a second service…” are being treated as part of abstract idea and is analogous to Mental processes, such that concept can be performed in the human mind).
Claim Rejections - 35 USC § 112(b)
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
Claims 21-40 are rejected under 35 U.S.C. 112(b), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor, or for pre-AIA the applicant regards as the invention.
As per claims 21, 27 and 35 (line# refers to claim 21):
Lines 8-10, it is not clearly indicated what is meant by “the statistical critical path determines overall latency of the application more frequently than the at least one other critical path”. Is the statistical critical path that more frequently determines overall latency of the application or the statistical critical path that determines overall latency of the application and more frequently occurred than the at least one other critical path? (see claim 1, lines 5-6, “frequency of occurrence”). For examining purpose, examiner will interpret as the statistical critical path that determines overall latency of the application and more frequently occurred than the at least one other critical path.
As per claim 29:
The terms “relatively higher” and “relatively lower” in claim 29 is a relative term which renders the claim indefinite. The term “relatively higher” and “relatively lower” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
As per claim 30:
The terms “relatively closer” and ““relatively further” in claim 30 is a relative term which renders the claim indefinite. The term “relatively closer” and ““relatively further” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
As per claim 33:
The term “relatively closer” in claim 33 is a relative term which renders the claim indefinite. The term “relatively closer” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
As per claim 37:
The term “proximity” in claim 37 is a relative term which renders the claim indefinite. The term “proximity” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
As per claim 39
The term “expected resource conflict” in claim 39 is a relative term which renders the claim indefinite. The term “expected resource conflict” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
As per claim 40:
The term “expected usage” in claim 40 is a relative term which renders the claim indefinite. The term “expected usage” is not defined by the claim, the specification does not provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
As per claims 22-26, 28-34 and 36-40:
They are method, system and computer-readable storage media claims that depend from rejected claims and do not resolve the deficiencies thereof and are therefore rejected for the same reasons as above.
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 21, 26-28 and 35-37 are rejected under 35 U.S.C. 103 as being unpatentable over Chrysos et al. (US Patent. 6,549,930 B1) in view of Di Balsamo et al. (US Pub. 2018/0307532 A1) and further in view of Rakvic et al. (US Pub. 2007/0074217 A1).
As per claim 21, Chrysos teaches the invention substantially as claimed including A method performed on a computing device, the method comprising (Chrysos, Fig. 1, 100, Abstract, lines 1-3, A method is provided for scheduling execution of a plurality of threads executed in a multithreaded processor):
evaluating execution logs for an application having a plurality of services to identify different execution paths of the application during multiple previous executions of the application (Chrysos, Fig. 11, A to E, 1110, C to E 1111 (execution paths); Fig. 12, Path samples; Col 13, line 3, Branch history tables; Col 25, lines 1-2, recent execution history of the process can also aid in identifying the execution path; Col 24, line 41, Path samples for selected instructions are captured; Col 24, lines 55-60, the path samples (as execution logs) are used to perform a backward analysis of a control flow graph of the program. The analysis can identify execution paths that are consistent (1250) with the sampled data, and this information can be aggregated to identify frequently executed paths (as previous executions) (1260) which will benefit more from optimization); Col 15, line 13, execution of instructions; Col 16, lines 49-50, one application could profile a large number of instructions);
identifying a statistical execution path for the application based at least on frequency of occurrence of the different execution paths in the execution logs, wherein the execution logs identify at least one other execution path of the application other than the statistical execution path and the statistical execution path more frequently than the at least one other execution path (Chrysos, Fig. 12, Path samples; Col 23, lines 54-57, Many compiler optimizations, such as trace scheduling and hot-cold optimization rely on knowing which execution paths are frequently taken through a program. These are called "hot" paths (as statistical execution path); Col 24, lines 55-60, the path samples (as execution logs) are used to perform a backward analysis of a control flow graph of the program. The analysis can identify execution paths that are consistent (1250) with the sampled data, and this information can be aggregated to identify frequently executed paths (as identifying statistical execution path based on frequency of occurrence of execution paths in the recent execution history) (1260) which will benefit more from optimization; lines 63-66, identify the path segments AE 1110, and ABCE (1101-1105) as possible paths. The best possible outcome exists when the static analysis is able to identify only a single path; Col 25 lines 1-2, recent execution history of the process can also aid in identifying the execution path).
Chrysos fails to specifically teach when identify different execution paths of the application during multiple previous executions of the application, it is critical paths, and the execution path is critical path.
However, Balsamo teaches when identify different execution paths of the application during multiple previous executions of the application, it is critical paths, and the execution path is critical path (Balsamo, [0004] lines 1-7, these critical path methods identify critical paths in the workload plan as defined by the work units belonging to the longest paths to the workload plan's targets (according to expected durations of the work units estimated from their previous executions). This information pertaining to the critical paths allows determining the impacts of any problems that may be experienced in the execution of the work unit).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos with Balsamo because Balsamo’s teaching of identifying the different critical paths during the multiple previous executions would have provided Chrysos’s system with the advantage and capability to allow the system to determining the impacts of any problems that may be experienced in the execution of the work unit which improving the system performance and efficiency (see Balsamo, [0004]).
Chrysos and Balsamo fail to specifically teach statistical execution path is statistical critical path, and statistical critical path determines overall latency of the application, and scheduling individual services of the plurality of services of the application based at least on whether the individual services occur on the statistical critical path.
However, Rakvic teaches statistical execution path is statistical critical path, and statistical critical path determines overall latency of the application (Rakvic, Fig. 8, 820 (as statistical critical path); [0077] lines 1-4, FIG. 8 illustrates that at least one embodiment of the TSDG 800 may identify the system critical path of the program. The system critical path is the path in the program having the longest latency (as overall latency of the application). Any thread on that path is critical to the performance of the program and should therefore be scheduled with a higher priority, if possible);, and
scheduling individual services of the plurality of services of the application based at least on whether the individual services occur on the statistical critical path (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the plurality of services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos and Balsamo with Rakvic because Rakvic’s teaching of assigning higher priority to the thread/tasks/shreds on the critical path would have provided Chrysos and Balsamo’s system with the advantage and capability to allow the system to prioritizing the execution of the operations that having longest execution time in order to improving the system efficiency and reducing the overall application latency (see Rakvic, [0083] “reduce overall program latency”).
As per claim 26, Chrysos, Balsamo and Rakvic teach the invention according to claim 21 above. Chrysos teaches wherein the statistical critical path comprises a particular path through the application that, over the multiple previous executions, most frequently is the path of the application (Chrysos, Col 23, lines 54-57, Many compiler optimizations, such as trace scheduling and hot-cold optimization rely on knowing which execution paths are frequently taken through a program. These are called "hot" paths. Col 24, lines 57-60, The analysis can identify execution paths that are consistent (1250) with the sampled data, and this information can be aggregated to identify frequently executed paths (as frequency of occurrence) (1260) which will benefit more from optimization; lines 63-66, identify the path segments AE 1110, and ABCE (1101-1105) as possible paths. The best possible outcome exists when the static analysis is able to identify only a single path). In addition, Balsamo teaches the path/execution path is critical path (Balsamo, [0004] lines 1-7, these critical path methods identify critical paths in the workload plan as defined by the work units belonging to the longest paths (as overall latency) to the workload plan's targets (according to expected durations of the work units estimated from their previous executions). This information pertaining to the critical paths allows determining the impacts of any problems that may be experienced in the execution of the work unit).
As per claim 27, Chrysos teaches the invention substantially as claimed including A system comprising (Chrysos, Fig. 2B):
a processing unit; and a computer-readable storage medium storing computer-readable instructions which, when executed by the processing unit, cause the system to (Chrysos, Claim 6, A computer-readable medium having computer-executable instructions for performing a method of scheduling two or more of a plurality of threads for execution on a multithreaded processor):
identify different execution paths of an application during multiple previous executions of the application (Chrysos, Fig. 11, A to E, 1110, C to E 1111 (execution paths); Fig. 12, Path samples; Col 13, line 3, Branch history tables; Col 25, lines 1-2, recent execution history of the process can also aid in identifying the execution path; Col 24, line 41, Path samples for selected instructions are captured; Col 24, lines 55-60, the path samples (as execution logs) are used to perform a backward analysis of a control flow graph of the program. The analysis can identify execution paths that are consistent (1250) with the sampled data, and this information can be aggregated to identify frequently executed paths (as previous executions of the application) (1260) which will benefit more from optimization); Col 15, line 13, execution of instructions; Col 16, lines 49-50, one application could profile a large number of instructions);
identifying, from the different execution paths of the application, a statistical execution path of the application that more frequently than other execution paths of the application (Chrysos, Fig. 12, Path samples; Col 23, lines 54-57, Many compiler optimizations, such as trace scheduling and hot-cold optimization rely on knowing which execution paths are frequently taken through a program. These are called "hot" paths (as statistical execution path); Col 24, lines 55-60, the path samples (as execution logs) are used to perform a backward analysis of a control flow graph of the program. The analysis can identify execution paths that are consistent (1250) with the sampled data, and this information can be aggregated to identify frequently executed paths (as identifying statistical execution path based on frequency of occurrence of execution paths in the recent execution history) (1260) which will benefit more from optimization; lines 63-66, identify the path segments AE 1110, and ABCE (1101-1105) as possible paths. The best possible outcome exists when the static analysis is able to identify only a single path; Col 25 lines 1-2, recent execution history of the process can also aid in identifying the execution path).
Chrysos fails to specifically teach when identify different execution paths of the application during multiple previous executions of the application, it is critical paths, the execution path is critical path, and the different critical paths determining overall latency of the application during different executions of the application.
However, Balsamo teaches when identify different execution paths of the application during multiple previous executions of the application, it is critical paths, the execution path is critical path and the different critical paths determining overall latency of the application during different executions of the application. (Balsamo, [0004] lines 1-7, these critical path methods identify critical paths in the workload plan as defined by the work units belonging to the longest paths (as overall latency) to the workload plan's targets (according to expected durations of the work units estimated from their previous executions). This information pertaining to the critical paths allows determining the impacts of any problems that may be experienced in the execution of the work unit).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos with Balsamo because Balsamo’s teaching of identifying the different critical paths during the multiple previous executions would have provided Chrysos’s system with the advantage and capability to allow the system to determining the impacts of any problems that may be experienced in the execution of the work unit which improving the system performance and efficiency (see Balsamo, [0004]).
Chrysos and Balsamo fail to specifically teach statistical execution path is statistical critical path, and statistical critical path of the application that determines overall latency of the application, and scheduling individual services of the application based at least on whether the individual services occur on the statistical critical path.
However, Rakvic teaches statistical execution path is statistical critical path, and statistical critical path of the application that determines overall latency of the application (Rakvic, Fig. 8, 820 (as statistical critical path); [0077] lines 1-4, FIG. 8 illustrates that at least one embodiment of the TSDG 800 may identify the system critical path of the program. The system critical path is the path in the program having the longest latency (as overall latency of the application). Any thread on that path is critical to the performance of the program and should therefore be scheduled with a higher priority, if possible);, and
scheduling individual services of the application based at least on whether the individual services occur on the statistical critical path (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos and Balsamo with Rakvic because Rakvic’s teaching of assigning higher priority to the thread/tasks/shreds on the critical path would have provided Chrysos and Balsamo’s system with the advantage and capability to allow the system to prioritizing the execution of the operations that having longest execution time in order to improving the system efficiency and reducing the overall application latency (see Rakvic, [0083] “reduce overall program latency”).
As per claim 28, Chrysos, Balsamo and Rakvic teach the invention according to claim 27 above. Rakvic further teaches access a dependency graph of the application; and assign scheduling priorities to the individual services based at least on distances of the individual services from a root node of the dependency graph (Rakvic, Fig. 7, X; Fig. 8, 800 dependency graph of the application, 820 system critical path, node 4.0, node 8.0, node 8.1, node 8.2 with respective 1381, 1393, 1406, 1410 (as distances of the individual services from a root node of the dependency graph); [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds; [0070] lines 1-7, in addition to monitoring program behavior, may analyze, characterize and record certain aspects of the execution history. For at least one embodiment, these aspects of the execution history may be recorded in the form of either or both of a shred dependency graph 600 and/or a time-stamped shred dependency graph 604; [0073] lines 1-3, The label on each of these four edges shown in FIG. 7 represents the latency (as time distance); [0074] lines 1-7, the TSDG 604 shown therein further extends the information of a SDG 600 with chronological information about dynamic shred execution. In particular, the TSDG 604 may incorporate a variety of weight metrics relevant to shred scheduling and execution, such as the timing of the shred dependencies. In the TSDG 604, the nodes represent the dynamic instances of scheduled shreds and the edge-labels represent the time at which an event indicating a dependency occurred).
As per claim 35, Chrysos teaches the invention substantially as claimed including A computer-readable storage media storing executable instructions which, when executed by a processing unit, cause the processing unit to perform acts comprising (Chrysos, Claim 6, A computer-readable medium having computer-executable instructions for performing a method of scheduling two or more of a plurality of threads for execution on a multithreaded processor):
identifying a statistical execution path for an application, wherein the statistical execution path more frequently than at least one other execution path of the application (Chrysos, Fig. 12, Path samples; Col 23, lines 54-57, Many compiler optimizations, such as trace scheduling and hot-cold optimization rely on knowing which execution paths are frequently taken through a program. These are called "hot" paths (as statistical execution path); Col 24, lines 55-60, the path samples (as execution logs) are used to perform a backward analysis of a control flow graph of the program. The analysis can identify execution paths that are consistent (1250) with the sampled data, and this information can be aggregated to identify frequently executed paths (as identifying statistical execution path based on frequency of occurrence of execution paths in the recent execution history) (1260) which will benefit more from optimization; lines 63-66, identify the path segments AE 1110, and ABCE (1101-1105) as possible paths. The best possible outcome exists when the static analysis is able to identify only a single path; Col 25 lines 1-2, recent execution history of the process can also aid in identifying the execution path).
Although Chrysos teaches statistical execution path and other execution path of the application, Chrysos fails to specifically teach that execution paths are critical path.
However, Balsamo teaches the execution paths are critical path (Balsamo, [0004] lines 1-7, these critical path methods identify critical paths in the workload plan as defined by the work units belonging to the longest paths to the workload plan's targets (according to expected durations of the work units estimated from their previous executions). This information pertaining to the critical paths allows determining the impacts of any problems that may be experienced in the execution of the work unit).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos with Balsamo because Balsamo’s teaching of identifying the different critical paths during the multiple previous executions would have provided Chrysos’s system with the advantage and capability to allow the system to determining the impacts of any problems that may be experienced in the execution of the work unit which improving the system performance and efficiency (see Balsamo, [0004]).
Chrysos and Balsamo fail to specifically teach statistical execution path is statistical critical path, and statistical critical path determines overall latency of the application, and scheduling individual services of the application based at least on whether the individual services occur on the statistical critical path.
However, Rakvic teaches statistical execution path is statistical execution path is statistical critical path, and statistical critical path determines overall latency of the application (Rakvic, Fig. 8, 820 (as statistical critical path); [0077] lines 1-4, FIG. 8 illustrates that at least one embodiment of the TSDG 800 may identify the system critical path of the program. The system critical path is the path in the program having the longest latency (as overall latency of the application). Any thread on that path is critical to the performance of the program and should therefore be scheduled with a higher priority, if possible); and
scheduling individual services of the application based at least on whether the individual services occur on the statistical critical path (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos and Balsamo with Rakvic because Rakvic’s teaching of assigning higher priority to the thread/tasks/shreds on the critical path would have provided Chrysos and Balsamo’s system with the advantage and capability to allow the system to prioritizing the execution of the operations that having longest execution time in order to improving the system efficiency and reducing the overall application latency (see Rakvic, [0083] “reduce overall program latency”).
As per claim 36, Chrysos, Balsamo and Rakvic teach the invention according to claim 35 above. Rakvic further teaches wherein the scheduling the individual services is further based at least on where the individual services occur in a dependency graph of the application (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds (as where the individual services occur in a dependency graph of the application, i.e., in path or not in path)).
As per claim 37, Chrysos, Balsamo and Rakvic teach the invention according to claim 36 above. Rakvic further teaches wherein the scheduling the individual services is further based at least on proximity of the individual services to a root node of the dependency graph (Rakvic, Fig. 8, 820 (as statistical critical path); [0077] lines 1-4, FIG. 8 illustrates that at least one embodiment of the TSDG 800 may identify the system critical path of the program. The system critical path is the path in the program having the longest latency (as proximity of the individual services to a root node of the dependency graph, longer latency). Any thread on that path is critical to the performance of the program and should therefore be scheduled with a higher priority, if possible).
Claims 22-23 are rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo and Rakvic, as applied to claim 21 above, and further in view of Ismail et al. (US Pub. 2019/0042523 A1).
As per claim 22, Chrysos, Balsamo and Rakvic teach the invention according to claim 21 above. Chrysos, Balsamo and Rakvic fail to specifically teach wherein the scheduling comprises assigning scheduling priorities to threads allocated to the individual services.
However, Ismail teaches wherein the scheduling comprises assigning scheduling priorities to threads allocated to the individual services (Ismail, [0077] lines 16-24, the operating system (OS) may assign a priority to the thread or task, which the circuitry 120 may consider while allocating bandwidth. Merely as an example, if a first thread or task is associated with operations of the OS and a second thread or task is associated with transferring a movie from a USB flash storage to a hard drive, the OS may assign a relatively higher priority to the first thread or task).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo and Rakvic with Ismail because Ismail’s teaching of assigning a priority to the thread for execution the operations would have provided Chrysos, Balsamo and Rakvic’s system with the advantage and capability to allow the system to execute the importance operations based on the priority which improving the system efficiency.
As per claim 23, Chrysos, Balsamo, Rakvic and Ismail teach the invention according to claim 22 above. Rakvic further teaches wherein the scheduling comprises: prioritizing specific services that occur on the statistical critical path above one or more other services that do not occur on the statistical critical path (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds).
Claims 24-25 are rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo, Rakvic and Ismail, as applied to claim 23 above, and further in view of COMEAU et al. (US Pub. 2013/0055275 A1).
As per claim 24, Chrysos, Balsamo, Rakvic and Ismail teach the invention according to claim 23 above. Rakvic further teaches determining respective time distances of the one or more other services from the statistical critical path (Rakvic, Fig. 7, X; Fig. 8, 820 system critical path, node 4.0, node 8.0, node 8.1, node 8.2 with respective 1381, 1393, 1406, 1410 (as distance of the one or more other services from the statistical critical path); [0073] The labels on the return edges represent the execution latencies; [0077] lines 1-4, FIG. 8 illustrates that at least one embodiment of the TSDG 800 may identify the system critical path of the program. The system critical path is the path in the program having the longest latency; [0078] lines 1-8, identify which shreds are on the system critical path with the information provided by the TSDG 800. The system critical path 820 may be easily identified by starting at the node of the TSDG 800 that has the largest time value (representing the latest node) and traversing upwards to the root of the TSDG 800. FIG. 8 illustrates that node 8.2 is the latest node and that shreds 4 (node 4.0) and 8 (nodes 8.0, 8.1, 8.2) are on the system critical path 820 [Examiner noted: the time value for each node is determined, therefore, the total distance/time is determined, see Fig. 7; and Fig. 8]).
Chrysos, Balsamo, Rakvic and Ismail fail to specifically teach prioritizing the one or more other services based at least on the respective time distances of the one or more other services from the statistical critical path.
However, COMEAU teaches prioritizing the one or more other services based at least on the respective time distances of the one or more other services from the statistical critical path (COMEAU, Fig. 3, assign a priority to the task based on the evaluation of the parameter; claim 3, wherein a longer distance (time distance taught by Rakvic) results in a higher priority being assigned to the task).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo, Rakvic and Ismail with COMEAU because COMEAU’s teaching of assign a priority to the task based on distance would have provided Chrysos, Balsamo, Rakvic and Ismail’s system with the advantage and capability to allow the system to scheduling the tasks based on distance related to each other which improving the system efficiency and performance.
As per claim 25, Chrysos, Balsamo, Rakvic, Ismail and COMEAU teach the invention according to claim 24 above. Rakvic further teaches wherein determining the respective time distances of the one or more other services from the statistical critical path comprises: based at least on previous execution times of the one or more other services, determining the respective time distances as respective amounts of time that the one or more other services would have had to run before appearing in the statistical critical path (Rakvic, Fig. 7, X; Fig. 8, 820 system critical path, node 4.0, node 8.0, node 8.1, node 8.2 with respective 1381, 1393, 1406, 1410 (as distance of the one or more other services from the statistical critical path); [0069] lines 3-4, monitors behavior of a shredded program 602, and in particular, monitors thread execution history of the shredded program 602; [0070] lines 1-7, in addition to monitoring program behavior, may analyze, characterize and record certain aspects of the execution history. For at least one embodiment, these aspects of the execution history may be recorded in the form of either or both of a shred dependency graph 600 and/or a time-stamped shred dependency graph 604 (as previous execution times); [0074] lines 1-7, the TSDG 604 shown therein further extends the information of a SDG 600 with chronological information about dynamic shred execution. In particular, the TSDG 604 may incorporate a variety of weight metrics relevant to shred scheduling and execution, such as the timing of the shred dependencies. In the TSDG 604, the nodes represent the dynamic instances of scheduled shreds and the edge-labels represent the time at which an event indicating a dependency occurred (as respective distances as respective amounts of time); [0073] The labels on the return edges represent the execution latencies; [0077] lines 1-4, FIG. 8 illustrates that at least one embodiment of the TSDG 800 may identify the system critical path of the program. The system critical path is the path in the program having the longest latency; [0078] lines 1-8, identify which shreds are on the system critical path with the information provided by the TSDG 800. The system critical path 820 may be easily identified by starting at the node of the TSDG 800 that has the largest time value (representing the latest node) and traversing upwards to the root of the TSDG 800. FIG. 8 illustrates that node 8.2 is the latest node and that shreds 4 (node 4.0) and 8 (nodes 8.0, 8.1, 8.2) are on the system critical path 820 [Examiner noted: determining the respective time distances as respective amounts of time that the one or more other services would have had to run (i.e. the time/latency between each node/servers are determined) before appearing in the statistical critical path (i.e., before that determining that path should be statistical critical path]).
Claim 29 is rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo and Rakvic, as applied to claim 28 above, and further in view of Fan et al. (US Pub. 2012/0099587 A1).
As per claim 29, Chrysos, Balsamo and Rakvic teach the invention according to claim 28 above. Rakvic further teaches assign a relatively higher scheduling priority to a particular service that occurs on the statistical critical path and a relatively lower scheduling priority to another service that does not occur on the statistical critical path (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the plurality of services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds).
Chrysos, Balsamo and Rakvic fail to specifically teach identify at least two different services in a particular layer of the dependency graph; and assign a relatively higher scheduling priority to a particular service in the particular layer and a relatively lower scheduling priority to another service in the particular layer.
However, Fan teaches identify at least two different services in a particular layer of the dependency graph; and assign a relatively higher scheduling priority to a particular service in the particular layer and a relatively lower scheduling priority to another service in the particular layer (Fan, [0054] lines 1-13, a network of communication apparatus in accordance with the fourth embodiment, each apparatus forming a node in the network, the network being in the form of a directed acyclic graph, DAG, comprises a plurality of ranks, at least one of said ranks comprising more than one node, wherein said message forwarding means in said apparatus in a rank comprising more than one node are each operable to concurrently attempt to forward a message on the basis of channel access governed by channel access timers; [0079] lines 1-4, he source at each DAG rank forwards the received packet to its parents using a selected link quality metric (such as SINR). This metric is used to assign different channel access priorities to the nodes at the same DAG rank. (as including assign a relatively higher scheduling priority to a particular service in the particular layer and a relatively lower scheduling priority to another service in the particular layer)).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo and Rakvic with Fan because Fan’s teaching of assigning the different priorities to the nodes within the same rank/layer of DAG would have provided Chrysos, Balsamo and Rakvic’s system with the advantage and capability to allow the system to scheduling the tasks based on priority at the same layer of the DAG in order to optimizing the processing speed and improving the system performance.
Claim 30 is rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo, Rakvic and Fan, as applied to claim 29 above, and further in view of Huang et al. (US Pub. 2016/0203228 A1).
As per claim 30, Chrysos, Balsamo, Rakvic and Fan teach the invention according to claim 29 above. Chrysos, Balsamo, Rakvic and Fan fail to specifically teach assign higher priorities to first services in a first layer that is relatively closer to the root node than the particular layer; and assign lower priorities to second services in a second layer that is relatively further from the root node than the particular layer.
However, Huang teaches assign higher priorities to first services in a first layer that is relatively closer to the root node than the particular layer; and assign lower priorities to second services in a second layer that is relatively further from the root node than the particular layer (Huang, Claim 1, wherein the establishing the mapping relationship between the filtering requirements and the attribute description network to generate the path dependency graph according to the mapping relationship includes: sorting the description paths based on a sorting rule that a layer at a higher level has a higher priority and a description value appearing first in a same layer has a higher priority; mapping the description paths to the attribute description network in sequence according to a result of the sorting; and combining parts that have completely identical high-layer description values in the description paths to generate the path dependency graph (as including higher priorities to first services in a first layer that is relatively closer to the root node than the particular layer; and assign lower priorities to second services in a second layer that is relatively further from the root node than the particular layer, since a layer at a higher level has a higher priority (please note: root node with DAG was taught by Rakvic, see Fig. 8).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo, Rakvic and Fan with Huang because Huang’s teaching of assigning a layer at a higher level with a higher priority would have provided Chrysos, Balsamo, Rakvic and Fan’s system with the advantage and capability to allow the system to processing the tasks within the higher layer first in order to improving the system performance and efficiency.
Claims 31 and 33 are rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo and Rakvic, as applied to claim 27 above, and further in view of Eichenberger et al. (US Pub. 2009/0064152 A1).
As per claim 31, Chrysos, Balsamo and Rakvic teach the invention according to claim 27 above. Rakvic teaches schedule a first service of the at least two different services that is on the statistical critical path before a second service of the at least two different services that is not on the statistical critical path (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the plurality of services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds).
Chrysos, Balsamo and Rakvic fail to specifically teach identify at least two different services of the application for which input data is ready.
However, Eichenberger teaches identify at least two different services of the application for which input data is ready (Eichenberger, Fig. 2, 200; [0006] lines 4 -15, identify a plurality of operations that are ready to be scheduled in the cycle, wherein the plurality of operations includes operations whose input are ready in the cycle, operations whose consumed resource are available in the cycle, and operations whose input are nearly ready to be scheduled, identify one operation of the plurality of operations that at least one of contributes to a critical path and uses a critical resource, assign priority to operations that alternate a resource usage pattern, assign the one operation to a current scheduling time and update available resources for current scheduling time).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo and Rakvic with Eichenberger because Eichenberger’s teaching of identifying the servers/node that having the input data is ready would have provided Chrysos, Balsamo and Rakvic’s system with the advantage and capability to allow the system to processing the tasks based on the input data is ready in order to improving the processing speed and system efficiency.
As per claim 33, Chrysos, Balsamo, Rakvic and Eichenberger teach the invention according to claim 31 above. Rakvic further teaches schedule a third service of the at least two different services before a fourth service of the at least two different services based at least on the third service being relatively closer to the statistical critical path of the application than the fourth service (Rakvic, [0082] lines 1-15, System Critical Path Scheduling. This optimization approach recognizes that certain nodes of the TSDG 604 are more critical to performance of the application program 602 than are other nodes. When performing the system critical path scheduling optimization, the hints generator 506 identifies the critical path-those nodes (as individual services of the plurality of services of the application) whose performance affects overall performance for the program 602. The system critical path through the TSDG 604 has the property that no other path in the program 602 has a longer latency. If these nodes take longer to execute, then overall performance of the program 602 is slowed. The hints generator 506 identifies all shreds on the critical path as "critical shreds" and provides a hint to indicate that the scheduler 450 should schedule such shreds with a higher priority than other, non-critical, shreds; (as shreds closer to statistical critical path, since it is within the path)).
Claim 32 is rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo, Rakvic and Eichenberger, as applied to claim 31 above, and further in view of HUBER et al. (US Pub. 2012/0005657 A1).
As per claim 32, Chrysos, Balsamo, Rakvic and Eichenberger teach the invention according to claim 31 above. Chrysos teaches schedule a third service of the at least two different services based at least on the third service having occurred more frequently in the different critical paths of the application than the fourth service (Chrysos, Fig. 12, Path samples; Col 23, lines 54-57, Many compiler optimizations, such as trace scheduling and hot-cold optimization rely on knowing which execution paths are frequently taken through a program. These are called "hot" paths. Col 24, lines 55-60, the path samples are used to perform a backward analysis of a control flow graph of the program. The analysis can identify execution paths that are consistent (1250) with the sampled data, and this information can be aggregated to identify frequently executed paths (1260) which will benefit more from optimization; lines 63-66, identify the path segments AE 1110, and ABCE (1101-1105) as possible paths. The best possible outcome exists when the static analysis is able to identify only a single path; Col 23, lines 48-50, A trace scheduler might do an even better job when it has an estimate of how long it took to execute each basic block or a larger execution path; Col 23, lines 54-57, Many compiler optimizations, such as trace scheduling and hot-cold optimization rely on knowing which execution paths are frequently taken through a program).
Chrysos, Balsamo, Rakvic and Eichenberger fail to specifically teach when scheduling, schedule a third service of the at least two different services before a fourth service of the at least two different services based at least on the third service having occurred more frequently.
However, HUBER teaches schedule a third service of the at least two different services before a fourth service of the at least two different services based at least on the third service having occurred more frequently (HUBER, [0039] lines 1-6, the most frequently used SET commands may be moved to the top (or at least in a higher execution priority) to allow for the shortest execution path. Each routine may be optimized for the applicable specific time interval window. Claim 18, a third executable portion for pursuant to modifying the ACS routine, ordering a filtering executing the frequently used instruction to move the frequently used instruction to the higher execution priority and move a less frequently used instruction to a lower execution priority of the modified ACS routine).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo, Rakvic and Eichenberger with HUBER because HUBER’s teaching of assigning a higher priority to a command based on its frequently usage would have provided Chrysos, Balsamo, Rakvic and Eichenberger’s system with the advantage and capability to allow the system to processing the highly usage tasks first in order to improving the system performance and efficiency.
Claim 34 is rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo and Rakvic, as applied to claim 27 above, and further in view of BLAINEY et al. (US Pub. 2018/0103088 A1).
As per claim 34, Chrysos, Balsamo and Rakvic teach the invention according to claim 27 above. Chrysos, Balsamo and Rakvic fail to specifically teach wherein the individual services are scheduled to run on at least two different computing clusters.
However, BLAINEY teaches wherein the individual services are scheduled to run on at least two different computing clusters (BLAINEY, [0040] lines 6-16, The request to process the compute workload may include, for example, a graph representation of the compute workload and one or more criteria for processing the compute workload. The one or more criteria may include, for example, a deadline for processing the compute workload and a maximum cost for processing the compute workload. The graph representation of the compute workload may, for example, identify dependencies in the compute workload and processes that can be executed in parallel (e.g., on different server clusters).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo and Rakvic with BLAINEY because BLAINEY’s teaching of assigning the different processes to different server cluster for execution in parallel would have provided Chrysos, Balsamo and Rakvic’s system with the advantage and capability to allow the system to processing the tasks faster in order to improving the system performance and processing speed.
Claim 38 is rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo and Rakvic, as applied to claim 37 above, and further in view of COMEAU et al. (US Pub. 2013/0055275 A1).
As per claim 38, Chrysos, Balsamo and Rakvic teach the invention according to claim 37 above. Rakvic further teaches determining distances of the individual services from the statistical critical path (Rakvic, Fig. 7, X; Fig. 8, 820 system critical path, node 5.0, node 6.0, node 7.0, 1381, 1391, 1395 (as distance of the one or more other services from the critical path); [0077] lines 1-4, FIG. 8 illustrates that at least one embodiment of the TSDG 800 may identify the system critical path of the program. The system critical path is the path in the program having the longest latency; [0078] lines 1-8, identify which shreds are on the system critical path with the information provided by the TSDG 800. The system critical path 820 may be easily identified by starting at the node of the TSDG 800 that has the largest time value (representing the latest node) and traversing upwards to the root of the TSDG 800. FIG. 8 illustrates that node 8.2 is the latest node and that shreds 4 (node 4.0) and 8 (nodes 8.0, 8.1, 8.2) are on the system critical path 820 [Examiner noted: the time value for each node is determined, therefore, the distance/time from the statistical critical path is determined, see Fig. 7 and Fig. 8]).
Chrysos, Balsamo and Rakvic fail to specifically teach scheduling the individual services based at least on the distances.
However, COMEAU teaches scheduling the individual services based at least on the distances (COMEAU, Fig. 3, assign a priority to the task based on the evaluation of the parameter; claim 3, wherein a longer distance (time distance taught by Rakvic) results in a higher priority being assigned to the task).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo and Rakvic with COMEAU because COMEAU’s teaching of assign a priority to the task based on distance would have provided Chrysos, Balsamo and Rakvic’s system with the advantage and capability to allow the system to scheduling the tasks based on distance related to each other which improving the system efficiency and performance.
Claims 39-40 are rejected under 35 U.S.C. 103 as being unpatentable over Chrysos, Balsamo and Rakvic, as applied to claim 37 above, and further in view of MOITA et al. (US Pub. 2021/0004263 A1).
As per claim 39, Chrysos, Balsamo and Rakvic teach the invention according to claim 37 above. Chrysos, Balsamo and Rakvic fail to specifically teach wherein scheduling the individual services is based at least on an expected resource conflict.
However, MOITA teaches wherein scheduling the individual services is based at least on an expected resource conflict (MOITA, Claim 8, selecting a list of nodes having no incoming directed edges from a graph comprising a plurality of nodes and one or more directed edges connecting out from parent nodes of the plurality of nodes into respective child nodes of the plurality of nodes, wherein the directed edges specify a dependency by the child nodes on the respective parent nodes, and wherein each node represents a task of the plurality of tasks, determining a next node from the list of nodes that minimizes resource conflicts with a previous node, and inserting the task of the plurality of tasks represented by the next node into the execution order).
It would have been obvious to one having ordinary skill in the art before the effective filling date of the claimed invention to have combined the teaching of Chrysos, Balsamo and Rakvic with MOITA because MOITA’s teaching of scheduling the node/tasks based on its resource conflicts would have provided Chrysos, Balsamo and Rakvic’s system with the advantage and capability to allow the system to minimizes resource conflicts between the nodes of the DAG in order to improving the system processing efficiency and performance.
As per claim 40, Chrysos, Balsamo, Rakvic and MOITA teach the invention according to claim 39 above. MOITA further teaches wherein the scheduling comprises preferentially scheduling a first service to complete before a second service based on expected usage of a particular resource by the first service and the second service (MOITA, Fig. 4B, see node 2 and node 4, (the node 2 need to complete before node 4); [0021] lines 1-8, FIGS. 2A-2E also include a resource they need. This could be a memory resource, a library, or some other resource that could create a conflict during execution, by way of non-limiting example. One skilled in the art will recognize that, when there are resource conflicts, these conflicts will need to be resolved in turn; [0024] lines 1-4, node 5 depends on both nodes 2 and 3, which both depend on node 1. And, in fact, the dependency order resolves node 1 before nodes 2 and 3, and resolves both nodes 2 and 3 before resolving node 5).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ZUJIA XU whose telephone number is (571)272-0954. The examiner can normally be reached M-F 9:30-5:30 EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Aimee J 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.
/ZUJIA XU/Examiner, Art Unit 2195