DETAILED ACTION
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 .
Claims 1-20 are pending.
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.
Claim(s) 1-4, 11-15, 22, and 23 are rejected under 35 U.S.C. 103 as being unpatentable over Beyer et al. (US 8015564).
With respect to claim 1, Beyer discloses:
for each particular task of a plurality of tasks to be executed, identifying one or more dependent tasks for the particular task such that the particular task must be executed prior to executing the one or more dependent tasks for the particular task (Fig. 2, col. 3, lines 3-15, 30-36: where a stage corresponds to Applicant’s “task”. A stage is denoted as “g”, no tasks in stage “g+1” may begin until all tasks in stage “g” have completed);
identifying a first task, of the plurality of tasks, that is ready to be executed and does not require any other tasks of the plurality of tasks to be executed prior to execution of the first task (Fig. 2 “j=1, g=1, i=1”, stage “g=1” does not require any other stage to execute prior to it being executed);
identifying a second task, of the plurality of tasks, that is ready to be executed and does not require any other tasks of the plurality of tasks to be executed prior to execution of the second task (Fig. 2, “j=2, g=1, i=1”, stage g=1 from job = 2 does not require any other stage to be executed prior to it being executed);
determining that (a) a first set of dependent tasks that depend on execution of the first task (b) a second set of dependent tasks that depend on execution of the second task (Fig 2, Fig. 3, stages g=2 and g=3 of job =1 depends on stage g=1 of job=1 to execute before they can execute; stage g=2 of job=2 depends on stage g=1 of job=2 to execute before it executes).
Beyer does not specifically disclose determining that the first set of dependent tasks are less than the second set of dependent tasks and responsive at least to determining that the first set of dependent tasks is less than the second set of dependent tasks, executing the second task prior to executing the first task
However, the nomenclature of the first, second, third, or fourth task for that matter are merely labels and are interpreted to correspond to Beyer’s series of “stages” where stage “g+1” cannot execute prior to stage “g”. The stages have precedence constraints (col. 2, lines 59-63). The claim limitation does not elaborate how the first set of dependent tasks are less than the second set of dependent tasks. The comparative determiner “less” is missing an object. Examiner interprets the missing object to include criteria such as “priority” or “Critical Path”. Beyer discloses that the dispatcher may use any of the scheduling rules in Table 1 of Fig. 5, i.e., priority, LCPF, STCPU, etc. (col. 4, lines 66-col. 5, line 2, Beyer).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to realize that when Beyer uses a “priority” scheduling rule, a job with less priority will not be scheduled to execute prior to a job with a higher priority (col. 6, lines 45-48, Beyer). One of ordinary skill in the art before the effective filing date will recognize that each job has multiple stages with precedence constraints themselves.
With respect to claim 2, Beyer discloses: wherein the operations further comprise: identifying a third task, of the plurality of tasks, that is ready to be executed and does not require any other tasks of the plurality of tasks to be executed prior to execution of the first task; identifying a fourth task, of the plurality of tasks, that is ready to be executed and does not require any other tasks of the plurality of tasks to be executed prior to execution of the second task; determining that (a) an execution time of the fourth task is more than (b) an execution time of the third task; and responsive at least to determining that the execution time of the fourth task is more than the execution time of the third task, executing the fourth task prior to executing the third task. (Fig. 3, “j=1, g=3, i=5 or 6”. for example. As explained above, the “stages” are interpreted to correspond to Applicant’s tasks. Each job has multiple stages. Fig. 5, LCPF: where the longest critical path first may be chosen as the dispatching rule, critical path is defined as the time to process each job, see e.g. col. 3, lines 13-16, col. 4, lines 66- col. 5, line 2. Therefore, any job with the longest critical path or execution time is chosen first to execute).
With respect to claim 3, Beyer discloses: wherein the operations further comprise: identify a third task, of the plurality of tasks, that is ready to be executed and does not require any other tasks of the plurality of tasks to be executed prior to execution of the first task; identify a fourth task, of the plurality of tasks, that is ready to be executed and does not require any other tasks of the plurality of tasks to be executed prior to execution of the second task; determining that (a) an execution time of the fourth task is less than (b) an execution time of the third task; and responsive at least to determining that the execution time of the fourth task is less than the execution time of the third task, executing the fourth task prior to executing the third task. (Fig. 3, “j=1, g=3, i=5 or 6”. for example. As explained above, the “stages” are interpreted to correspond to Applicant’s tasks. Each job has multiple stages. Fig. 5, STCPU: where the job with the shortest processing time is selected. 6, col. 4, lines 66- col. 5, line 2: the dispatcher can selecte a scheduling rule from Table 1 of Fig. 5. Therefore, if STCPU is selected as the dispatching rule, any job with the shortest processing time is selected. The job with the shortest processing time will always have a lesser processing time than any other job).
With respect to claim 4, Beyer discloses: wherein the operations further comprise determining that first task is ready to be executed in response to determining that each of a third set of tasks, upon which the first task depends, have been executed (stage “g=3” of job “j=1” will not execute before stage “g=2” of job “j=1”, col. 2, lines 55-63).
With respect to claim 11, Beyer discloses: wherein the operations further comprise: generating a directed acyclic graph wherein each node in the directed acyclic graph corresponds to a task, and wherein each edge in the directed acyclic graph corresponds to a dependency between a pair of tasks, wherein determining the first set of dependent tasks for the first task comprises determining a number of outbound edges from a first node in the acyclic graph that represents the first task (col. 4, lines 9-18, directed acyclic graphs, DAGs in short, is a common representation technique in the job scheduling art that illustrate job dependencies and other properties).
With respect to claims 12-15, and 22, they each recite similar limitations as claims 1-4, and 11, respectively, and are therefore rejected under the same citations and rationale.
With respect to claim 23, it recites similar limitations as claim 1 and is therefore rejected under the same citations and rationale.
Claim(s) 5-10, and 16-21 are rejected under 35 U.S.C. 103 as being unpatentable over Beyer et al. (US 8015564) in view of Hosmani et al. (US 10713088).
With respect to claim 5, Beyer does not specifically discloses: wherein the operations further comprise recalculating dependency relationships between tasks in the plurality of tasks prior to determining the first set of dependent tasks and the second set of dependent tasks.
However, Hosmani discloses: wherein the operations further comprise recalculating dependency relationships between tasks in the plurality of tasks prior to determining the first set of dependent tasks and the second set of dependent tasks (Fig. 8, “840”).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to incorporate recalculating dependency relationships as taught by Hosmani into Beyer’s scheduling technique to dynamically adapt to changes caused by task completion and or task execution failure events. Changing dependencies based on said events prevent deadlock or resource starvation.
With respect to claim 6, Hosmani discloses: wherein the operations further comprise recalculating dependency relationships prior to each selection operation for selecting tasks, from the plurality of tasks, for execution (id.).
With respect to claim 7, Hosmani discloses: wherein the operations further comprise recalculating dependency relationships in response to (a) addition of tasks to the plurality of tasks, (b) removal of tasks from the plurality of tasks, or (c) execution of tasks in the plurality of tasks (Fig. 8).
With respect to claim 8, Hosmani discloses: wherein executing the second task prior to executing the first task comprises queuing the second task in an execution queue prior to first task (col. 6, lines 61- col. 7, line 14, Fig. 2 and Fig. 4”: where “order” corresponds to Applicant’s “queuing”).
With respect to claim 9, Hosmani discloses: wherein the operations further comprises increasing or decreasing a number of executors being used to execute tasks in the execution queue based on a number of tasks currently in the execution queue (col. 5, lines 10-45).
With respect to claim 10, Beyer discloses: inserting the first task into a queue subsequent to a third task and prior to a fourth task based on the first set of dependent tasks for the first task being less than a third set of dependent tasks for the third task and greater than a fourth set of dependent tasks for the fourth task (col. 6, lines 45-55, the priority of the job dictates which job will be scheduled for execution first).
With respect to claims 16-21, they recite similar limitations as claims 5-10, respectively, and are therefore rejected under the same citations and rationale.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to WISSAM RASHID whose telephone number is (571)270-3758. The examiner can normally be reached Monday-Friday 8: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, Aimee Li can be reached at (571)272-4169. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/WISSAM RASHID/ Primary Examiner, Art Unit 2195