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 .
Examiner Notes
Examiner cites particular columns and line numbers in the references as applied to the claims below for convenience of the applicant. Although the specified citations are representative of the teachings in the art and are applied to the specific limitations within the individual claim, other passages and figures may apply as well. It is respectfully requested that, in preparing responses, the applicant fully consider the references cited in their entirety as potentially teaching all or part of the claimed invention, as well as the context of the passage as taught by the prior art or disclosed by the examiner.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-7 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Step 1:
The claims are reciting one or more non-transitory media, which is a tangible product and falls within one of the four categories of statutory subject matter (i.e., a machine).
Step 2A, Prong One:
Claim 1 recites the limitations determining a set of tasks to be scheduled across a set of shared resources, the set of tasks comprising a plurality of periodic tasks;
filtering out one or more high-utilization tasks from the set of tasks to be scheduled;
generating a constraint programming (CP) model based on the set of tasks, the CP model comprising a set of constrained variables, a set of constraints, and a search directive;
applying a CP solver to the CP model, to obtain a CP solution for scheduling the set of tasks across the set of shared resources;
wherein the CP solution assigns two or more periodic tasks in the plurality of periodic tasks to a same resource in the set of shared resources, based at least on the two or more periodic tasks having periods that are harmonically compatible, all of which can be performed mentally, with the aid of pen and paper, through observation, evaluation, judgment and opinion.
Accordingly, claim 1 recites a judicial exception (i.e., an abstract idea).
Step 2A, Prong Two:
The additional elements recited in claim 1 include: (i) One or more non-transitory computer-readable media storing instructions which, when executed by one or more hardware processors, cause performance of operations comprising: the limitations which are reciting a mental process.
This additional element amounts to mere instructions to apply the exception, as it is merely reciting computing components are performing the judicial exception. This additional element of mere instructions to apply the exception is not indicative of integration into a practical application. See MPEP 2106.04(d) and MPEP 2106.05(f).
For clarity of the record, the Examiner would like to note the limitation (ii) “applying a CP solver to the CP model, to”, which has been interpreted as being able to be performed mentally in the present rejection, may at best be considered an additional element of mere instructions to apply the exception if a “CP solver” is considered to be limited to some combination of software and/or hardware. As such, this additional element of mere instructions to apply the exception is not indicative of integration into a practical application. See MPEP 2106.04(d) and MPEP 2106.05(f).
The additional elements recited above, even when considered in combination, results in mere instructions to apply the exception(s), which fails to integrate the judicial exception into a practical application. See MPEP 2106.04(d).
Step 2B:
Regarding the additional element (i), the limitation is reciting generic computing components used to implement the judicial exceptions. The courts have found that adding mere instructions to apply an exception is not enough to amount to significantly more than the recited judicial exception. See MPEP 2106.05.
Regarding the additional element (ii), the limitation is reciting computing components well-known in the art are used to implement the recited judicial exception. See Kadioglu et al. (U.S. Pub. No. 2016/0306671), paragraphs [0080] and [0140], as well as portions of Naveh et al. (U.S. Pub. No. 2010/0057518) and Hamadi (U.S. Pub. No. 2008/0147573) cited in the pertinent prior art for evidence that a CP solver is well-known in the art. Further, these well-known computing components are recited with a high level of generality. The courts have found that adding mere instructions to apply an exception is not enough to amount to significantly more than the recited judicial exception. See MPEP 2106.05.
The combination of these additional elements results in generic and well-known computing components implementing the judicial exceptions, and therefore the additional elements, when considered individually and in combination, fail to add an inventive concept to the claim.
Consequently, claim 1 as a whole does not amount to significantly more than the judicial exception and the claim is not eligible.
Claim 2 is dependent on claim 1, and therefore inherits the same judicial exceptions recited in claim 1. Further, claim 2 recites the limitation prohibiting collocation of any periodic tasks that are harmonically incompatible. This limitation can be performed in the human mind, with the aid of pen and paper, and thus is reciting a judicial exception (i.e., an abstract idea).
Claim 2 does not recite any additional elements beyond those recited in claim 1. Accordingly, the additional elements of claim 1 are not indicative of integration into a practical application, nor do they provide an inventive concept. Thus, claim 2 is not eligible.
Claim 3 is dependent on claim 1, and therefore inherits the same judicial exceptions recited in claim 1. Further, claim 3 recites the limitation prohibiting any tasks in the set of tasks whose duration exceeds an upper period threshold from collocation with any periodic task in the plurality of period tasks. This limitation can be performed in the human mind, with the aid of pen and paper, and thus is reciting a judicial exception (i.e., an abstract idea).
Claim 3 does not recite any additional elements beyond those recited in claim 1. Accordingly, the additional elements of claim 1 are not indicative of integration into a practical application, nor do they provide an inventive concept. Thus, claim 3 is not eligible.
Claim 4 is dependent on claim 1, and therefore inherits the same judicial exceptions recited in claim 1. Further, claim 4 recites scheduling the set of periodic tasks as indicated by the CP solution. This limitation can be performed in the human mind, with the aid of pen and paper, and thus is reciting a judicial exception (i.e., an abstract idea).
Claim 4 recites the additional element without receiving user input that indicates approval of the CP solution, which, at best, is mere instructions to apply the exception, as it is merely reciting automatically (e.g., by a computer) performing the mental process of “scheduling the set of periodic tasks as indicated by the CP solution”.
This additional element of mere instructions to apply the exception is not indicative of integration into a practical application. Even when considered in combination with the additional elements of claim 1, the additional elements recited comprise mere instructions to implement the exceptions with generic and well-known computing components, which is not indicative of integration into a practical application. Further, when considered individually and in combination with the additional elements of claim 1, the additional elements do not provide an inventive concept and do not amount to significantly more than the recited judicial exceptions. Thus, claim 4 is not eligible.
Claim 5 is dependent on claim 1, and therefore inherits the same judicial exceptions recited in claim 1. Further, claim 5 recites the limitation wherein the set of constrained variables comprises: a first set of constrained variables corresponding to task-resource assignment; a second set of constrained variables corresponding to task execution time. This limitation can be performed in the human mind with the aid of pen and paper (i.e., a person is capable of “generating a constraint programming (CP) model based on the set of tasks, the CP model comprising” the recited set of constrained variables), and thus is reciting a judicial exception (i.e., an abstract idea).
Claim 5 does not recite any additional elements beyond those recited in claim 1. Accordingly, the additional elements of claim 1 are not indicative of integration into a practical application, nor do they provide an inventive concept. Thus, claim 5 is not eligible.
Claim 6 is dependent on claim 1, and therefore inherits the same judicial exceptions recited in claim 1. Further, claim 6 recites the limitation wherein the CP model further comprises a total cost element constrained to a peak number of resources consumed by the set of tasks. This limitation can be performed in the human mind with the aid of pen and paper (i.e., a person is capable of “generating a constraint programming (CP) model” comprising the above limitations), and thus is reciting a judicial exception (i.e., an abstract idea).
Claim 6 does not recite any additional elements beyond those recited in claim 1. Accordingly, the additional elements of claim 1 are not indicative of integration into a practical application, nor do they provide an inventive concept. Thus, claim 6 is not eligible.
Claim 7 is dependent on claim 1, and therefore inherits the same judicial exceptions recited in claim 1. Further, claim 7 recites the limitation wherein the search directive indicates a First-Fit Decreasing Utilization (FFDU) approach to scheduling the set of tasks. This limitation can be performed in the human mind with the aid of pen and paper (i.e., a person is capable of “generating a constraint programming (CP) model based on the set of tasks, the CP model comprising” the recited search directive), and thus is reciting a judicial exception (i.e., an abstract idea).
Claim 7 does not recite any additional elements beyond those recited in claim 1. Accordingly, the additional elements of claim 1 are not indicative of integration into a practical application, nor do they provide an inventive concept. Thus, claim 7 is not eligible.
Claims 8-14 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claims 8-14 recite A system comprising:
one or more hardware processors;
one or more non-transitory computer-readable media; and
program instructions stored on the one or more non-transitory computer readable media which,
when executed by the one or more hardware processors, cause the system to perform
operations comprising: the operations recited in claims 1-7, respectively. As such, in view of the abovementioned reasons presented with respect to claims 1-7, claims 8-14 are also directed to a judicial exception without significantly more and are ineligible.
For clarity of the record, the additional element of claim 8 recited above is considered to be mere instructions to apply the exception, which is not indicative of integration into a practical application nor does it amount to significantly more than the judicial exception.
Claims 15-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claims 15-20 recite A method comprising: the operations recited in claims 1-3 and 5-7, respectively, wherein the method is performed by at least one device including a hardware processor. As such, in view of the abovementioned reasons presented with respect to claims 1-3 and 5-7, claims 15-20 are also directed to a judicial exception without significantly more and are ineligible.
For clarity of the record, the additional element of claim 15 recited above is considered to be mere instructions to apply the exception, which is not indicative of integration into a practical application nor does it amount to significantly more than the judicial exception.
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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1, 3-4, 8, 10-11, 15, and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Wang et al. (NPL Document: “On Harmonic Fixed-Priority Scheduling of Periodic Real-Time Tasks with Constrained Deadlines”), hereinafter Wang, in view of Li et al. (NPL Document: “Analysis of Federated and Global Scheduling for Parallel and Real-Time Tasks”), hereinafter Li, and Colena et al. (U.S. Pub. No. 2022/0027861), hereinafter Colena.
Regarding claim 1, Wang teaches a set of tasks to be scheduled across a set of shared resources, the set of tasks comprising a plurality of periodic tasks (Page 2, 2. PRELIMINARY – “We consider a real-time system consisting of N independent periodic tasks, denoted as Γ = {τ1, τ2, . . . , τN}, ordered by their priorities based on deadline monotonic scheduling (DMS) policy. Assume Γ is to be scheduled on a homogeneous multi-core platform, denoted as P = {p1, p2, ...pM}, according to DMS. Each task τi ∈ Γ is characterized by a tuple (Ci,Di, Ti), representing the worst case execution time, the relative deadline and the inter-arrival time (period), respectively. […] Problem 1. Given (i) task set Γ = {τ1, τ2, . . . , τN} and (ii) multi-core platform P = {p1, p2, ...pM}, partition Γ on P such that all tasks can meet their deadlines and the number of cores used is minimized […] we assign tasks τ1 and τ2 together to one processor and task τ3, τ4 and τ5 to another processor. Again, since task τ6 cannot be assigned to either of the two processors, we still have to allocate one more processor to schedule task τ6.”); and obtain a […] solution for scheduling the set of tasks across the set of shared resources; wherein the […] solution assigns two or more periodic tasks in the plurality of periodic tasks to a same resource in the set of shared resources, based at least on the two or more periodic tasks having periods that are harmonically compatible (Page 2, 2. PRELIMINARY – “A key to solve problem stated above is to partition real-time tasks in a way that can best utilize the processors. Consider the task set with six tasks shown in Table 1. […] Since harmonic tasks can better utilize a processor, an intuitive approach is therefore to allocate tasks with same periods (or tasks with periods being integer multiples of each other) to the same core. Specifically, for the six tasks above, we assign tasks τ1 and τ2 together to one processor and task τ3, τ4 and τ5 to another processor. Again, since task τ6 cannot be assigned to either of the two processors, we still have to allocate one more processor to schedule task τ6.”).
Wang does not expressly teach One or more non-transitory computer-readable media storing instructions which, when executed by one or more hardware processors, cause performance of operations comprising: determining the set of tasks; filtering out one or more high-utilization tasks from the set of tasks to be scheduled; generating a constraint programming (CP) model based on the set of tasks, the CP model comprising a set of constrained variables, a set of constraints, and a search directive; applying a CP solver to the CP model, to obtain a CP solution for scheduling the set of tasks; wherein the CP solution assigns the tasks to the shared resources.
However, Li teaches filtering out one or more high-utilization tasks from the set of tasks to be scheduled (Page 85, Abstract – “The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores.”; Page 87, III. Federated Scheduling, A. Federated Scheduling Algorithm – “First, tasks are divided into two disjoint sets: ͳhigh contains all high-utilization tasks — tasks with worst-case utilization at least one (ui ≥ 1), and ͳlow contains all the remaining low-utilization tasks. Consider a high-utilization task ͳi […] We assign ni dedicated cores to ͳi […] After a valid core allocation, runtime scheduling proceeds as follows: (1) Any greedy (work-conserving) parallel scheduler can be used to schedule a high-utilization task ͳi on its assigned ni cores. Informally, a greedy scheduler is one that never keeps a core idle if some node is ready to execute. (2) Low-utilization tasks are treated and executed as though they are sequential tasks and any multiprocessor scheduling algorithm (such as partitioned EDF [37], or various rate-monotonic schedulers [3]) with a utilization bound of at most 1/2 can be used to schedule all the low-utilization tasks on the allocated nlow cores.”).
Wang and Li are considered to be analogous art to the claimed invention because they are in the same field as the invention of scheduling a plurality of periodic tasks to a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang to incorporate the teachings of Li such that one or more high utilization tasks are filtered out from the set of tasks to be scheduled as taught by Li. Doing so ensures the low-utilization tasks to be executed on shared resources can be treated a sequential tasks and parallel execution is not required to meet their deadlines (Li: Page 88, III. Federated Scheduling, A. Federated Scheduling Algorithm). Further, allocating the minimum number of dedicated cores to the high-utilization tasks ensures they are schedulable, so that there is no preempting a high-utilization task and the number of migrations is minimized, thereby reducing overhead (Li: Page 95, VII. Practical Considerations).
The combination of Wang in view of Li does not expressly teach One or more non-transitory computer-readable media storing instructions which, when executed by one or more hardware processors, cause performance of operations comprising: determining the set of tasks; generating a constraint programming (CP) model based on the set of tasks, the CP model comprising a set of constrained variables, a set of constraints, and a search directive; applying a CP solver to the CP model, to obtain a CP solution for scheduling the set of tasks; wherein the CP solution assigns the tasks to the shared resources.
However, Colena teaches One or more non-transitory computer-readable media storing instructions which, when executed by one or more hardware processors, cause performance of operations ([0338] – “a non-transitory computer readable storage medium comprises instructions which, when executed by one or more hardware processors, causes performance of any of the operations described herein”) comprising: determining the set of tasks ([0170] – “One or more embodiments include identifying a set of maintenance tasks to be performed for the set of machines (Operation 204). […] Additionally or alternatively, the data packet generator 126 may obtain instructions, which when executed by at least one device including a hardware processor, performs one or more maintenance tasks.”; [0300]-[0301] – “one or more embodiments include generating a set of instructions for performing the set of maintenance tasks based on the proposed maintenance schedule (Operation 606). […]. Additional instructions are determined, specified, and/or obtained for scheduling execution of the instructions for performing each maintenance task according to the proposed maintenance schedule. The instructions are executable by at least one device including a hardware processor.”; [0304]-[0305] – “One or more embodiments include performing the set of maintenance tasks according to the proposed maintenance schedule (Operation 608). One or more maintenance resources accept the set of instructions generated at Operation 606. Based on the set of instructions, the maintenance resources perform the set of maintenance tasks according to the proposed maintenance schedule. As an example, a proposed maintenance schedule may indicate that a first maintenance task is scheduled for 9 am and a second maintenance task is scheduled for 10 am. A master server may generate instructions for performing the first maintenance task at 9 am and the second maintenance task at 10 am. The master server may execute the instructions. According to the instructions, the master server may perform the first maintenance task at 9 am and the second maintenance task at 10 am.” The tasks may be scheduled to be executed/performed by the same set of maintenance resource(s), e.g., the master server described in [0305], thus, the maintenance resources are shared by the tasks.); generating a constraint programming (CP) model based on the set of tasks ([0031] – “Constraint programming (CP) is a form of declarative programming. CP obtains a solution to a real-world problem based on a specification of a CP data model and optionally a CP search directive.”; [0034] – “One or more embodiments include generating a CP data model, to be applied to a CP solver, for determining a proposed maintenance schedule for performing a set of machine maintenance tasks”; [0196] – “FIGS. 3A-B illustrates an example set of operations for generating a constraint programming data model, in accordance with one or more embodiments.”), the CP model comprising a set of constrained variables ([0197]-[0198] – “One or more embodiments include specifying a set of task elements, each task element representing a maintenance task (Operation 302). A data model generator 114 specifies a set of task elements.” […] One or more embodiments include specifying domains of the task elements, each domain representing candidate time windows for performing a maintenance task (Operation 304).”; [0203]-[0204] and [0211]-[0212] – other constrained variables (i.e., variables constrained to a domain) may include time elements and cost elements), a set of constraints ([0248] – “One or more embodiments include generating a data model including the task elements, the time elements, the cost elements, the total cost element, the global cardinality constraint, the element constraint, and the sum constraint (Operation 324). The data model generator 114 generates a data model including the task elements, the time elements, the cost elements, the total cost element, the global cardinality constraint, the element constraint, and the sum constraint.”) and a search directive ([0033] – “A CP search directive guides the assignment of a set of values to a set of data model elements that satisfies all constraints, as specified by a CP data model. The CP search directive prioritizes the assignment of certain preferred values over other values for one or more elements.”; [0252]-[0253] – “FIG. 4 illustrates an example set of operations for generating a constraint programming search directive, in accordance with one or more embodiments. One or more embodiments include specifying one or more instructions for identifying a target task element (Operation 402). A search directive generator 116 determines, specifies, and/or obtains instructions and/or operations for traversing each of the set of task elements specified at Operation 302.”); applying a CP solver to the CP model, to obtain a CP solution for scheduling the set of tasks; wherein the CP solution assigns the tasks to the shared resources ([0159] – “In one or more embodiments, a proposed maintenance schedule 134 is a schedule for performing one or more maintenance tasks 104a-b based on a CP solution determined by a CP solver 132. The CP solution is determined based on a data model 120 and optionally a search directive 125.”; [0268] – “FIG. 5 illustrates an example set of operations applying a constraint programming data model and search directive to a constraint programming solver, in accordance with one or more embodiments. The CP data model and search directive are iteratively applied to determine a CP solution”; [0283] – “Based on assignment of a time window to a task element, the CP solver 132 returns a proposed maintenance schedule indicating that the maintenance task represented by the task element is scheduled for performance during the assigned time window.”; [0303]-[0304] – the maintenance resources perform the tasks according to the proposed maintenance schedule returned by the CP solver.).
Colena is considered to be analogous art to the claimed invention because it is reasonably pertinent to the problem faced by the inventor of generating a schedule for a plurality of constrained tasks to be performed by a set of shared resources. It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have modified the methods for scheduling a plurality of periodic computing tasks to be executed on one or more cores of a processor as taught by Wang in view of Li to be implemented as instructions stored on a non-transitory computer-readable storage media to be executed by a hardware processor as taught by Colena. One of ordinary skill in the art would see the NPL references of Wang and Li teaching the periodic tasks being scheduled for execution on processor(s), and would know that computing components and/or logic implemented by computing components, such as a non-transitory computer-readable media storing instructions to be executed by one or more hardware processors, would be needed to cause the tasks to be scheduled to the processor(s). Therefore, it would have been obvious to one of ordinary skill in the art because it would have been applying a known technique (scheduling tasks for execution by one or more processors as a result of a hardware processor executing instructions stored on a non-transitory computer readable media as taught in Colena) to a known device (Wang which teaches scheduling a set of periodic tasks for execution on one or more processors based on their periods being harmonically compatible) ready for improvement to yield predictable results (implementing the scheduling of periodic tasks as a result of a hardware processor executing instructions stored on a non-transitory computer readable media) for the benefit of using a hardware processor to efficiently schedule tasks to be executed on one or more processors. Further, it would have been obvious to one of ordinary skill in the art to have modified the methods of scheduling of a plurality of periodic tasks as taught by Wang in view of Li to use constraint programming techniques to generate the schedule as taught by Colena. Constraint programming techniques offer an efficient means for obtaining a schedule for performing a set of tasks which satisfies multiple objectives, e.g., satisfies multiple constraints, and allows for parameters of the problem to change, e.g., the tasks can change, without having to change the constraints (see Colena: [0049]).
Regarding claim 3, the combination of Wang in view of Li and Colena teaches the one or more non-transitory computer-readable media of claim 1. Li teaches the operations further comprising: prohibiting any tasks in the set of tasks whose duration exceeds an upper period threshold from collocation with any periodic task in the plurality of period tasks (Page 85, Abstract – “The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores.”; Page 87, II. System Model – “the minimum inter-arrival time (or period) Ti represents the time between consecutive arrivals of task instances, […] In this paper, we consider implicit deadline tasks where each task ͳi’s relative deadline Di is equal to its minimum inter-arrival time Ti; that is, Ti = Di. We consider the schedulability of this task set on a uniform multicore system consisting of m identical cores. […] total execution time (or work) Ci of task ͳi: This is the summation of the worst-case execution times of all the subtasks of task ͳi. […] the utilization
C
i
T
i
=
C
i
D
i
of task ͳi is denoted by ui for implicit deadlines.” ; Page 89, V. Canonical Form of a DAG Task – “in this paper, we analyze tasks with implicit deadline, so period equals to deadline (Ti = Di). Recall that we classify each task ͳi as a low-utilization if ui = Ci/Di < 1 (and hence Ci < Dii; or high-utilization task, if ͳi’s utilization ui ≥ 1.” Utilization is the execution time divided by the period, thus utilization is greater than 1 when the execution time (“duration”) exceeds the period. Any task whose execution time exceeds its period (i.e., its “upper period threshold”) is classified as a high-utilization task and assigned its own dedicated set of cores, thereby prohibiting collocation with any other periodic tasks.).
It would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang to incorporate the teachings of Li such that one or more high utilization tasks are assigned their own dedicated resources and thus prohibited from collocating with other tasks as taught by Li. Doing so ensures the low-utilization tasks to be executed on shared resources can be treated a sequential tasks and parallel execution is not required to meet their deadlines (Li: Page 88, III. Federated Scheduling, A. Federated Scheduling Algorithm). Further, allocating the minimum number of dedicated cores to the high-utilization tasks ensures they are schedulable, so that there is no preempting a high-utilization task and the number of migrations is minimized, thereby reducing overhead (Li: Page 95, VII. Practical Considerations).
Regarding claim 4, the combination of Wang in view of Li and Colena teaches the one or more non-transitory computer-readable media of claim 1. Colena teaches the operations further comprising: without receiving user input that indicates approval of the CP solution, scheduling the set of periodic tasks as indicated by the CP solution ([0054] – “Additionally or alternatively, maintenance resources obtain the proposed maintenance schedule. The maintenance resources perform the maintenance tasks according to the proposed maintenance schedule. The maintenance tasks may be performed with or without human intervention.”; [0299] – “user input accepting the proposed maintenance schedule is not necessary. The proposed maintenance schedule output from the CP solver is adopted without human intervention.”).
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]).
Regarding claim 8, Colena teaches A system (computer system 800) comprising:
one or more hardware processors (processor 804);
one or more non-transitory computer-readable media (storage device 810); and
program instructions stored on the one or more non-transitory computer readable media which, when executed by the one or more hardware processors, cause the system to perform operations ([0324] – “FIG. 8 is a block diagram that illustrates a computer system 800 upon which an embodiment of the invention may be implemented. Computer system 800 includes […] a hardware processor 804”; [0328]-[0329] – “According to one embodiment, the techniques herein are performed by computer system 800 in response to processor 804 executing one or more sequences of one or more instructions contained in main memory 806. Such instructions may be read into main memory 806 from another storage medium, such as storage device 810. Execution of the sequences of instructions contained in main memory 806 causes processor 804 to perform the process steps described herein. […] The term "storage media" as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operate in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device 810.”) comprising: the operations of claim 1. Accordingly, claim 8 is rejected as being unpatentable over Wang in view of Li and Colena for the same reasons presented with respect to claim 1.
For clarity of the record, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to modify the methods for scheduling a plurality of periodic computing tasks to be executed on one or more cores of a processor as taught by Wang in view of Li to be implemented in a system comprising one or more hardware processors and one or more non-transitory computer-readable storage media storing instructions to be executed by the hardware processors as taught by Colena. One of ordinary skill in the art would see the NPL references of Wang and Li teaching the periodic tasks being scheduled on processor(s), and would know that computing components and/or logic implemented by computing components, such as a system comprising one or more hardware processors and one or more non-transitory computer-readable media storing instructions to be executed by the one or more hardware processors, would be needed to cause the tasks to be scheduled to the processor(s). Therefore, it would have been obvious to one of ordinary skill in the art because it would have been applying a known technique (scheduling tasks for execution by one or more processors as a result of a hardware processor executing instructions stored on a non-transitory computer readable media in a system as taught in Colena) to a known device (Wang which teaches scheduling a set of periodic tasks for execution on one or more processors based on their periods being harmonically compatible) ready for improvement to yield predictable results (implementing the scheduling of periodic tasks as a result of a hardware processor executing instructions stored on a non-transitory computer readable media in a system) for the benefit of using a hardware processor to efficiently schedule tasks to be executed on one or more processors.
Claim 10 recites substantially the same limitations as those recited in claim 3, applied to the system of claim 8. Accordingly, claim 10 is rejected as being unpatentable over Wang in view of Li and Colena for the same reasons presented with respect to claim 3.
Claim 11 recites substantially the same limitations as those recited in claim 4, applied to the system of claim 8. Accordingly, claim 11 is rejected as being unpatentable over Wang in view of Li and Colena for the same reasons presented with respect to claim 4.
Regarding claim 15, Colena teaches A method comprising: the operations of claim 1; wherein the method is performed by at least one device including a hardware processor (FIGS. 2-6; [0328] – “Execution of the sequences of instructions contained in main memory 806 causes processor 804 to perform the process steps described herein.”). Accordingly, claim 15 is rejected as being unpatentable over Wang in view of Li and Colena for the same reasons presented with respect to claim 1.
For clarity of the record, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to modify the methods for scheduling a plurality of periodic computing tasks to be executed on one or more cores of a processor as taught by Wang in view of Li to be performed by at least one device including a hardware processor as taught by Colena. One of ordinary skill in the art would see the NPL references of Wang teaching the periodic tasks being scheduled on processor(s), and would know that computing components and/or logic implemented by computing components, such as a device including a hardware processor, would be needed to cause the tasks to be scheduled to the processor(s). Therefore, it would have been obvious to one of ordinary skill in the art because it would have been applying a known technique (scheduling tasks for execution by one or more processors by a device comprising a hardware processor as taught in Colena) to a known device (Wang which teaches scheduling a set of periodic tasks for execution on one or more processors based on their periods being harmonically compatible) ready for improvement to yield predictable results (implementing the scheduling of periodic tasks using a device comprising a hardware processor) for the benefit of using a hardware processor to efficiently schedule tasks to be executed on one or more processors.
Claim 17 recites substantially the same limitations as those recited in claim 3, applied to the method of claim 15. Accordingly, claim 17 is rejected as being unpatentable over Wang in view of Li and Colena for the same reasons presented with respect to claim 3.
Claims 2, 9, and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li and Colena as applied to claims 1, 8, and 15 above, and further in view of Liu et al. (U.S. Pub. No. 2024/0045720), hereinafter Liu.
Regarding claim 2, the combination of Wang in view of Li and Colena teaches the one or more non-transitory computer-readable media of claim 1, but fails to expressly teach the operations further comprising: prohibiting collocation of any periodic tasks that are harmonically incompatible.
However, Liu teaches prohibiting collocation of any periodic tasks that are harmonically incompatible ([0002] – “The main purpose of periodic task scheduling is to address the occupation of a shared computational resource by multiple periodic tasks. A shared computational resource can allow only one or more tasks to use it at the same time.”; [0050] – “the present method requires that cycle times of first periodic tasks in the first group respectively are one or more integer divisors of a maximum cycle time.”; [0052] – “execution/waiting status indicates whether the periodic task is in an active task sub-queue or in a waiting task sub-queue or in a to-be-removed sub-queue. When a periodic task is assigned a to-be-removed status, the system is configured to remove the periodic task from the task queue, e.g., due to its conflict with other periodic tasks”; [0059] – “Upon a determination there is at least one periodic task of the first group in the task queue, the computer-implemented method in some embodiments further includes determining whether or not a conflict exists between the newly arrived periodic task of the first group and any of periodic tasks of the first group in the task queue.”; [0061] – “Upon a determination the conflict exists between the newly arrived periodic task of the first group and the periodic tasks of the first group in the task queue, the computer-implemented method in some embodiments further includes excluding a periodic task of the first group having a lowest priority from the task queue.” If two periodic tasks of the first group conflict, i.e., they are harmonically incompatible, the lower priority task is excluded from the active task queue, thus they are prohibited from being collocated in the active task queue.).
Liu is considered to be analogous art to the claimed invention because it is in the same field of scheduling a plurality of periodic tasks on a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang in view of Li and Colena to incorporate the teachings of Liu. Incorporating the teachings of Liu would ensure there is no overlap, i.e., conflict (see [0044] and Fig. 1), in the execution of multiple periodic tasks on a shared resource, while ensuring tasks of higher priority are scheduled for execution (Liu: [0062]-[0063], and [0102]).
Claim 9 recites substantially the same limitations as those recited in claim 2, applied to the system of claim 8. Accordingly, claim 9 is rejected as being unpatentable over Wang in view of Li and Colena, and further in view of Liu, for the same reasons presented with respect to claim 2.
Claim 16 recites substantially the same limitations as those recited in claim 2, applied to the method of claim 15. Accordingly, claim 16 is rejected as being unpatentable over Wang in view of Li and Colena, and further in view of Liu, for the same reasons presented with respect to claim 2.
Claims 5, 12, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li and Colena as applied to claims 1, 8, and 15 above, and further in view of Kadioglu et al. (U.S. Pub. No. 2016/0306671), hereinafter Kadioglu.
Regarding claim 5, the combination of Wang in view of Li and Colena teaches the one or more non-transitory computer-readable media of claim 1. Colena further teaches wherein the set of constrained variables comprises: […] a second set of constrained variables corresponding to task execution time ([0172]-[0173] – “One or more embodiments include identifying a set of candidate time windows for performing the set of maintenance tasks (Operation 206). […] The set of candidate time windows for performing the set of maintenance tasks may be determined based on availability of maintenance resources. The duration of each candidate time window may be the same or different. The data packet generator determines possible time windows for performing each maintenance task. […] As an example, a time window restriction may indicate that a particular maintenance task may be performed during only a subset of a set of candidate time windows.”; [0198] – “One or more embodiments include specifying domains of the task elements, each domain representing candidate time windows for performing a maintenance task (Operation 304). The data model generator 114 specifies domains of the task elements. Each domain may be represented by a vector, an array, and/or any other data structure. A domain for a particular task element represents the set of candidate time windows for performing a maintenance task represented by the particular task element.”; [0170] and [0301] – performing a task may be executing instructions by a processor.).
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]). Further, Wang suggests periodic tasks to be scheduled across a set of processors may have constrained deadlines, i.e., deadlines less than or equal to their period, that should be considered in scheduling the tasks (Wang: ABSTRACT and Section 7. CONCLUSIONS).
The combination of Wang in view of Li and Colena does not expressly teach a first set of constrained variables corresponding to task-resource assignment.
However, Kadioglu teaches a first set of constrained variables corresponding to task-resource assignment ([0050] – “requests 112 correspond to requests for performance of one or more tasks by one or more resources 114. Examples of requests 112 include requests for the delivery of services, production of products, execution of operations, and/or performance of other tasks.”; [0070]-[0071] – “data model 120 includes one or more data model elements such as request elements 122-124 and counting elements 142-144. Each request element (such as request element 122 or request element 124) is associated with a request domain (such as request domain 132 or request domain 134). A request domain, corresponding to a particular request, includes a set of possible resources 114 that may be assigned to the particular request. A request domain may include all or a subset of resources 114. In an example, each request domain includes a candidate set of resources, filtered from resources 114, that may be assigned to a particular request based on resource capabilities 116 required and/or preferred for completion of the particular request.”).
Kadioglu is considered to be analogous art to the claimed invention because it is reasonably pertinent to the problem faced by the inventor of generating a schedule for a plurality of constrained tasks to be performed by a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the teachings of Wang in view of Li and Colena such that the constrained variables include a set of constrained variables corresponding to task resource assignment. Doing so would ensure tasks are only assigned to well-suited resources which have the required and/or preferred capabilities for completing the task (Kadioglu: [0028], [0071] and [0096]).
Claim 12 recites substantially the same limitations as those recited in claim 5, applied to the system of claim 8. Accordingly, claim 12 is rejected as being unpatentable over Wang in view of Li and Colena as applied to claim 8, and further in view of Kadioglu for the same reasons presented with respect to claim 5.
Claim 18 recites substantially the same limitations as those recited in claim 5, applied to the method of claim 15. Accordingly, claim 18 is rejected as being unpatentable over Wang in view of Li and Colena as applied to claim 15, and further in view of Kadioglu for the same reasons presented with respect to claim 5.
Claims 6, 13, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li and Colena as applied to claims 1, 8, and 15 above, and further in view of MOHANA NARAYANAMURTHY et al. (U.S. Pub. No. 2024/0419506), hereinafter MOHANA NARAYANAMURTHY.
Regarding claim 6, the combination of Wang in view of Li and Colena teaches the one or more non-transitory computer-readable media of claim 1. Colena further teaches wherein the CP model further comprises a total cost element constrained to [a domain of cost values for performing] the set of tasks ([0050] – “One or more embodiments include iteratively applying a CP data model to a CP solver to obtain a proposed maintenance schedule. A total cost value associated with a prior solution obtained by the CP solver is used as an upper bound for the domain of the total cost element in a next iteration of the CP solver.”; [0077]-[0082] – “data model elements 122 in a data model include at least: […] (d) a total cost element. […] A domain of a total cost element indicates possible total cost values for performing the set of maintenance tasks.”; [0268] – “The CP data model and search directive are iteratively applied to determine a CP solution associated with a total cost element assigned with a lowest total cost value (as compared with other possible CP solutions).”.
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]).
The combination of Wang in view of Li and Colena does not expressly teach a peak number of resources consumed by the set of tasks.
However, MOHANA NARAYANAMURTHY teaches a cost element constrained to a peak number of resources consumed by the set of tasks ([0005] – “ An efficiency engine identifies container sizes for containers of a workload and allocates the containers across server clusters and nodes based on peak resource usage requirements of the containers.”; [0036]-[0038] – “optimizing or otherwise selecting or identifying the sizes of the various containers 142-144 in which the workload 136 will be deployed. It is first assumed that a request (R) and a limit (L) are parameters that are defined for each type of resource in cloud resource inventory 127. […] The request represents the amount of resources that may be required by a container once the container is scheduled. […] The limit may be the maximum amount of resources that can be used by the container. […] The resources for which a request and limit may be defined may include CPU cores 250, memory 252, network bandwidth 254, and other resources 256. The container size identifier 157 may obtain the request and limit amounts as well as any historical resource usage statistics […] The resource usage and quality of service metrics may be at peak operation times 260, and they may identify container level percentages, such as the peak usage, the maximum and minimum usage, the different percentiles of usage, such as 5%, 95%, 99%, etc. […] Based upon the historical resource usage statistics and quality of service metrics, the container size identifier 157 in decision engine 156 controls the solver engine 162 in bin packing policy system 158 to obtain container size parameters (R and L) for each of the different types of resources being considered.”; [0044] – “how server cluster identifier 159 and node identifier 161 are used to place the containers for a single workload, once they have been sized by container size identifier 157, on different server clusters and nodes, in an efficient way.”; [0047] – “Server cluster identifier 159 then calculates a time cost function for the cost of adding workload W to the server cluster C. The time cost function may find services with resource utilization peaks that match the resource utilization valleys of other workloads so that the resources in the server cluster can be shared among those workloads without sacrificing performance”; [0054]-[0056] – “Server cluster identifier 159 then calculates the temporal cost of merging the groups, as indicated by block 326. The temporal cost can be based on the peak CPU usage of each workload, as indicated by block 328, or based upon other cost criteria, as indicated by block 330. Server cluster identifier 159 then calculates the total cost of each of the proposed merged groups and ranks the proposed merged groups based upon the total cost associated with each proposed merged group, as indicated by block 332. […] if, at block 346, the stopping criteria have been met, then server cluster identifier 159 generates an output to assign the workloads to server clusters based upon the merged groups.”).
MOHANA NARAYANAMURTHY is considered to be analogous art to the claimed invention because it is reasonably pertinent to the problem faced by the inventor in assigning a plurality of tasks to a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the CP model for which the CP solver is to generate a CP solution which assigns the plurality of tasks to the set of shared resources as taught by Wang in view of Li and Colena to include a cost element constrained to a peak number of resources consumed by the set of tasks as suggested by MOHANA NARAYANMURTHY. Incorporating the methods of MOHANA NARAYANMURTHY would enable the system to perform workloads, i.e., tasks, in a highly efficient manner, with fewer resources, and enables runtime adjustment of the resources allocated to and placement of the workloads being performed based on predicted resource usage (MOHANA NARAYANMURTHY [0015]-[0016], [0025], and [0063]).
Claim 13 recites substantially the same limitations as those recited in claim 6, applied to the system of claim 8. Accordingly, claim 13 is rejected as being unpatentable over Wang in view of Li and Colena as applied to claim 8, and further in view of MOHANA NARAYANMURTHY for the same reasons presented with respect to claim 6.
Claim 19 recites substantially the same limitations as those recited in claim 6, applied to the method of claim 15. Accordingly, claim 19 is rejected as being unpatentable over Wang in view of Li and Colena as applied to claim 15, and further in view of MOHANA NARAYANMURTHY for the same reasons presented with respect to claim 6.
Claims 7, 14, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Li and Colena as applied to claims 1, 8, and 15 above, and further in view of Mayank et al. (NPL Document: “Non-preemptive multiprocessor scheduling for periodic real-time tasks”), hereinafter Mayank.
Regarding claim 7, the combination of Wang in view of Li and Colena teaches the one or more non-transitory computer-readable media of claim 1. Colena further teaches wherein the search directive indicates a […] approach to scheduling the set of tasks ([0033] – “A CP search directive guides the assignment of a set of values to a set of data model elements that satisfies all constraints, as specified by a CP data model. The CP search directive prioritizes the assignment of certain preferred values over other values for one or more elements.”; [0253] – “A search directive generator 116 determines, specifies, and/or obtains instructions and/or operations for traversing each of the set of task elements specified at Operation 302. The instructions include selecting a particular task element, representing a particular maintenance task, as an initial "target task element." In subsequent iterations, traversing the set of task elements, another task element may be selected as the "target task element."; [0272] – “the CP solver may be guided by a CP search directive. The CP search directive may determine a sequence in which time windows are attempted for assignment to one or more task elements.”).
It would have been obvious to one of ordinary skill in the art to have modified the methods for scheduling the plurality of periodic tasks to a set of shared resources as taught by Wang in view of Li to incorporate the constraint programming techniques of Colena. Doing so provides a more efficient way of generating a schedule for performing a plurality of tasks (Colena: [0049]).
The combination of Wang in view of Li and Colena fails to expressly teach using a First-Fit Decreasing Utilization (FFDU) approach to scheduling the set of tasks.
However, Mayank teaches a First-Fit Decreasing Utilization (FFDU) approach to scheduling the set of tasks (Page 2, 1. INTRODUCTION – “In this work, we propose a methodology for scheduling of a set of non-preemptive tasks in multiprocessor environment. We try to minimize the number of processor for scheduling the tasks. We use partitioning based approach where the tasks are allocated to processors in the beginning. Once a task is assigned to a processor, it cannot migrate to other processors. For partitioning, we use strategies like best-fit (BF) and first-fit (FF) that are used for solving bin-packing problem. The ordering of tasks is also important for allocation of it. We explore different orderings of tasks based on utilization, periods, etc. in combination with partitioning strategies. […] We observe that FF and BF heuristics with increasing period and decreasing utilization provide good performance with respect to other multiprocessor approaches.”; Page 6, 5. CONCLUSION – “We observed FFDU and BFDU gives better performance on a given number of processor.”).
Mayank is considered to be analogous art to the claimed invention because it is in the same field of scheduling a plurality of periodic tasks on a set of shared resources. Therefore, it would have been obvious to one of ordinary skill in the art to have modified the search directive indicating an approach for traversing the task set to be scheduled as taught by Wang in view of Li and Colena to indicate a first-fit decreasing utilization approach as taught by Mayank. Doing so uses a known heuristic for solving bin-packing problems, i.e., the first-fit heuristic, to ensure processor utilization is not exceeded, and uses the task utilization to order the tasks being assigned (Mayank: Page 3). Further, using FFDU provided better performance and a higher success ratio on a given number of processors than other approaches (Mayank: Pages 5-6).
Claim 14 recites substantially the same limitations as those recited in claim 7, applied to the system of claim 8. Accordingly, claim 14 is rejected as being unpatentable over Wang in view of Li and Colena as applied to claim 8, and further in view of Mayank for the same reasons presented with respect to claim 7.
Claim 20 recites substantially the same limitations as those recited in claim 7, applied to the method of claim 15. Accordingly, claim 20 is rejected as being unpatentable over Wang in view of Li and Colena as applied to claim 15, and further in view of Mayank for the same reasons presented with respect to claim 7.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Naveh et al. (U.S. Pub. No. 2010/0057518) teaches a solution to a constraint satisfaction problem (CSP) is an assignment of a respective value to each variable that satisfies all constraints, and that CSP solvers are known in the art to receive and solve CSP definitions that include all the variables, domains and constraints, and return a solution (see [0023]). It also teaches an exemplary CSP solver known in the art is “the Choco constraint programming system, which is available on the Sourceforge.net.RTM. Web site” (See [0027]).
Hamadi (U.S. Pub. No. 2008/0147573) teaches problem solvers which use constraint programming techniques to provide solutions to planning, scheduling, and configuration problems are known and commercially available (see [0002]).
Kuo et al. (NPL Document: “Load Adjustment in Adaptive Real-Time Systems”) teaches a set of periodic processes are more likely to be schedulable if their periods are harmonically related, and teaches dividing a set of periodic processes into subsets such that each subset only comprises processes which are harmonically related (see page 162).
Xu et al. (NPL Document: “Harmonic Scheduling and Control Co-design”) teaches harmonic scheduling of periodic tasks with release offsets gives better control performance that standard non-harmonic scheduling of the periodic tasks (see Abstract).
Wikipedia (NPL Reference: “Scheduling (computing)”) teaches scheduling is the action of assigning resources, such as processors, to perform tasks, and that a scheduler is a process, often an operation system module, which performs the scheduling activity (see pages 1-2).
Narayanamurthy et al. (U.S. Pub. No. 2018/0101405) teaches a method for scheduling recurring, or periodic, jobs on selected nodes of a computing cluster, where the nodes are selected based on its current and predicted workload, using constraints that involve application of penalties for over-allocation and under-allocation (see [0001]-[0002] and [0058]).
Wang et al. (U.S. Pub. No. 2024/0004707) teaches a method for energy-efficient scheduling of periodic tasks on a group of processing devices, using an objective function optimizing the power consumption of the devices and constraints on the utilization of the devices (see Abstract).
VALVERDE ALCALA et al. (U.S. Pub. No. 2023/0133727) teaches a method for scheduling a plurality of tasks, e.g., multi-periodic tasks, for execution by a processor system, where a scheduling solver, e.g., a constraint programming solver, determines a time-partitioned schedule (see Abstract, [0012]-[0013], [0065]-[0066], [0075], and [0086]-[0087]).
Smith et al. (U.S. Pub. No. 2002/0198925) teaches a thread scheduler requiring every thread to be scheduled has a period that is harmonic (see [0029]).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JENNIFER MARIE GUTMAN whose telephone number is (703)756-1572. The examiner can normally be reached M-F: 9:00 am - 5:00 pm.
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, Kevin Young can be reached at 571-270-3180. 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.
/JENNIFER MARIE GUTMAN/ Examiner, Art Unit 2194 /KEVIN L YOUNG/Supervisory Patent Examiner, Art Unit 2194