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 .
Response to Amendment
The amendment filed on 7/9/2026 has been entered. Claims 1-5 and 7-21 remain pending in this application. The amendments to the claims have overcome the 35 U.S.C. § 101 rejection previously set forth in the Non-Final Office Action. Therefore, Examiner withdraws the 35 U.S.C. § 101 rejection of claims 1-5 and 7-20.
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, 11, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Jiang et al. (US Patent No. 10,459,751 B2 hereinafter Jiang) in view of Haghighat et al. (US Pub. No. 2021/0263779 A1 hereinafter Haghighat) in view of Cheng et al. (US Pub. No 2019/0004839 A1 hereinafter Cheng) in view of RAMADOSS et al. (US Pub. No. 2017/0069054 A1 hereinafter RAMADOSS).
As per claim 1, Jiang teaches a computer-implemented method for scheduling virtual functions (see Abstract), at least a portion of the method being performed by a computing device comprising at least one processor (Col. 3 & 4, lines 63-67 & 1-16, “As described above, physical functions and virtual functions are addressing parameters in PCIe, where transactions made across PCIe specify or are intended for a particular virtual function and/or physical function and the processor 102 or APD 116 responds accordingly (note, some ways of addressing over PCIe do not explicitly specify a virtual function or physical function; for example, transactions over PCIe can be routed by memory address instead of explicitly by function, where the devices implicitly understand which function is associated with a particular memory address). The processor 102 directs transactions for a particular VM to the appropriate virtual function of the APD 116 via a memory mapping mechanism.”), the method comprising: receiving a plurality of submissions from the respective virtual functions requesting at least some resources from the hardware accelerator (Col. 3, lines 4-49, “The processor 102 is configured to support a virtualizations scheme in which multiple virtual machines execute on the processor 102. Each virtual machine (“VM”) “appears” to software executing in that VM as a completely “real” hardware computer system, but in reality comprises a virtualized computing environment that may be sharing the device 100 with other virtual machines. Virtualization may be supported fully in software, partially in hardware and partially in software, or fully in hardware. The APD 116 supports virtualization, meaning that the APD 116 can be shared among multiple virtual machines executing on the processor 102, with each VM “believing” that the VM has full ownership of a real hardware APD 116. For virtualization, VMs take turns executing on the processor 102…The APD 116 supports virtualization by allowing time-based sharing of the APD 116 between the virtual machines. On the APD 116, the host VM 202 is mapped to a physical function 208 and guest VMs 204 are mapped to virtual functions 210.” See also Fig. 2.), scheduling, by a scheduler, divisions of the resources to the respective virtual functions based on an execution time of each respective virtual function (Col. 4, lines 17-46, “Sharing the APD 116 among the different virtual machines is accomplished by time-dividing the operations of the APD 116 amongst the different virtual machines. A virtualization scheduler 212 performs this task, scheduling different virtual machines for operation by switching between work for the different virtual machines as the execution time assigned to the virtual machines elapse…In other words, this disclosure may use terminology such as “the virtual function performs a task,” (or physical function) or “an operation is performed on of for a virtual function,” (or physical function) and this terminology should be read to mean that the APD 116 performs that task for the time-slice assigned to the VM associated with that particular virtual or physical function, or on behalf of the VM associated with that virtual or physical function.” Col. 6 & 7, lines 57-67 & 1-3, “The virtualization scheduler 212 manages time-sharing of the APD 116 among the different virtual machines. In each time-slice, the virtualization scheduler 212 permits work for the virtual machine associated with that time-slice to proceed in the APD 116.) and allocating the divisions of the resources to the respective virtual functions according to the schedule (Col. 7, lines 4-23, “Virtualization on the APD 116 works as follows. The virtualization scheduler 212 manages time-slices on the APD 116 for the VMs (both the host VM 202 and the guest VMS 204) that share the APD 116. The virtualization scheduler 212 tracks the time-slices, stopping work on the APD 116 when a time-slice for a particular VM has expired and starting work for the VM having the next time-slice. Thus, the virtualization scheduler 212 switches between different VMs that have work to be executed on the APD 116. To begin work for a particular time-slice associated with a particular VM, the virtualization scheduler 212 selects a virtual function associated with that VM to run and causes the command processor 213 to begin running for that VM.”).
Although Jiang teaches scheduling resources for use by virtual functions based on execution time, Jiang fails to teach measuring an execution time for each respective virtual function and scheduling based on the measured execution time.
However, Haghighat teaches measuring, for virtual functions, a total of execution time of each respective virtual function (¶ [0150], “The environment in which a Function's code is executed is referred to as a container. The container may be any isolated-execution entity such as a process, a Docker or Kubernetes container, a virtual machine, etc.” ¶ [0411], “In some embodiments, historical information such as that gathered from various telemetry sources (e.g. timers that timed previous function executions), may be used to estimate the execution time for each function, which may help to inform scheduling of future invocations of the functions.” ¶ [0668], “The orchestrator 2443 receives a function and decides how to route it to be executed. In some embodiments, when a function gets executed, information may be collected about behavior of the function (e.g., cache misses, timing to execute, etc.) by the orchestrator 2443. Some embodiments may use many counters to collect program information, and/or the function may be instrumented to collect data (e.g., and/or a timer may be used to collect information).”), wherein during the measured total of execution time, each respective virtual function uses at least some resources from a hardware accelerator (¶ [0155], “In the illustrated example, one or more central processing units (CPUs) 308a-308n (e.g., host processor) uses a FaaS executor 310 to execute a first set of functions 312, one or more accelerators 314a-314n (e.g., fixed-functionality hardware logic) executes a second set of functions 316, one or more field programmable gate arrays (FPGAs) 318a-318n executes a third set of functions 320 and one or more graphics processing units (GPUs) 318a-318n executes a fourth set of functions 326. Accordingly, the illustrated FaaS server configuration 300 is powered by specialized silicon, including GPUs 322a-322n, FPGAs 318a-318n, and specialized accelerators 314a-314n.”) and scheduling respective virtual functions based on the measured total of execution time (¶ [0472], “The orchestrator 1704 may determine the resource requirement based on available measures of dynamic utilization of resources. In some embodiments, historical information such as that gathered from various telemetry sources, e.g. from timers, function or debug logs, and performance monitors, may be used to estimate the execution time and/or resource requirements for each function, which may then be used to inform scheduling of future invocations of functions.”).
Jiang and Haghighat are considered to be analogous to the claimed invention because they are in the same field of task scheduling and resource allocation. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the scheduling method of Jiang with the well-known technique of allocating resources based on measured total execution time as taught by Haghighat to arrive at the claimed invention. This modification would have been reasonable under MPEP § 2143 as both references schedule tasks on resources taking into account task execution times.
Jiang and Haghighat fail to teach measuring execution time for each respective virtual function by sending an interrupt during an idle period of a hardware accelerator for a time slice associated with the virtual function.
However, Cheng teaches measuring, for virtual functions, a total execution time of each respective virtual function by sending a doorbell notification during an idle period of a hardware accelerator for a time slice associated with the virtual function (¶ [0034], “Notifications that new work is ready to be performed on the APD 116 are made via a doorbell mechanism. More specifically, to notify the APD 116 that new work is ready, an entity (such as the processor 102) writes a doorbell into the doorbell memory 214. The doorbell includes a pointer into a command buffer that indicates the memory address of commands to be fetched and processed.” ¶ [0052]-[0055], “Referring back to FIG. 2, in some instances, a current function finishes work before the amount of time allotted for the time-slice for that function expires and becomes “idle.” In some situations in this scenario, the virtualization scheduler 212 performs a virtualization context switch “early.” More specifically, after learning of the idleness and before the time-slice is over, the virtualization scheduler 212 causes a virtualization context switch away from the current function and to a next function. The purpose of performing the virtualization context switch early is to allow other functions to perform work when the current function has no more work to perform. Instead of idling the APD 116 for the remainder of the time-slice for the current function, by performing a virtualization context switch to a subsequent function, the resources of the APD 116 are used to perform useful work instead of being idle…The early virtualization context switch unit 402 communicates and coordinates with the command processor 213 to determine when it is appropriate to perform an “early virtualization context switch,” based on the state of the graphics processing pipeline 134, or, for compute-only work, the state of the SIMD scheduler 136 and compute units 134…As part of this workflow control, the command processor 213 receives reports of work completion from various sub-units of the graphics processing pipeline 134 and SIMD scheduler 136. More specifically, for outstanding work on the graphics processing pipeline 134 or the SIMD scheduler 136, the command processor 213 receives notifications when such work is complete. Additionally, the command processor 213 tracks what work is outstanding in the graphics processing pipeline 134 and SIMD scheduler 136. By correlating reports of completion of work with tracking of outstanding work, the command processor 213 tracks information that indicates whether the graphics processing pipeline 134 and SIMD scheduler 136 are idle or are performing work.” ¶ [0058]-[0059], “In one implementation, the early virtualization context switch determination includes waiting for a timeout period after receiving the idle indication from the command processor 213 and determining whether a doorbell is received within that timeout period (this determination is illustrated as step 504 in FIG. 5). If no doorbells for the current function have arrived at the APD 116 during that timeout period, then the virtualization scheduler initiates an early virtualization context switch (step 508)…Initiating the early virtualization context switch also includes transmitting a command to the command processor 213 to stop fetching work based on doorbells in the doorbell memory 214 received after the timeout period has ended. There is a small delay between the time that the virtualization scheduler 212 makes the determination that no doorbells have been received within the timeout period and transmits the command to the command processor 213 to stop fetching the work and the time that the command processor 213 receives the command to stop fetching work. If a doorbell is received during this delay period, the command processor 213 ignores the doorbell, or, if the command processor 213 has begun fetching work based on the doorbell, aborts such fetching.”), wherein during the measured total of execution time, each respective virtual function uses at least some resources from the hardware accelerator (¶ [0009]-[0011], “Typically, each VM is assigned a fixed length of time, after which a virtualization context switch is performed. This fixed length of time can lead to inefficiencies. For example, in some situations, a VM has no more work to perform and is idle but some time still remains in the current time-slice for that VM. Therefore, in some situations, in response to a VM having no more work to perform on the APD and the APD being idle, a virtualization context switch is performed “early.” This virtualization context switch is “early” in the sense that the virtualization context switch is performed before the fixed length of time for the time-slice expires…Instead, the APD is permitted to fetch the new work and perform that work. If no additional work is received during that timeout period, then an early virtualization context switch is performed. In some implementations, after an early virtualization context switch has been performed for a function, the APD does not re-schedule that function on the APD if no work has been received since the early virtualization context switch was performed. In some examples, a doorbell mechanism is implemented whereby when a memory mapped “doorbell” address is written to, the APD is notified that work is ready for a particular function.”).
Jiang, Haghighat, and Cheng are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling and resource allocation. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the method of Jiang and Haghighat with the virtual function idle period notification functionality as taught by Cheng to arrive at the claimed invention. The motivation to modify Jiang and Haghighat with the teachings of Cheng is that providing a notification when a virtual function is idle allows for an early context switch which avoids situations where an accelerator is not being used by the virtual function during its time slice.
Although Jiang, Haghighat, and Cheng teach sending a doorbell notification, they do not explicitly teach sending an interrupt. Therefore, it is necessary to bring in an additional reference that shows a doorbell is a type of interrupt.
Accordingly, RADAMOSS teaches a doorbell notification is sending an interrupt (¶ [0140], “It is contemplated “doorbell” or “DB” refers to a notification (also referred to as an “interrupt”) that is sent to a GPU/graphics microcontroller, where the notification is treated by the microcontroller's firmware as some work is added while the firmware proceeds to discover who added the work and processes the new work.” ¶ [0145], “In one embodiment, scheduler 1409 may then schedule the work items to be submitted to submit queues in order of the type or work or tasks a work item relates to and its priority level. For example and in one embodiment, as facilitated by scheduler 1409, when a time expired interrupt or other scheduling event occurs, the work item relating to the agent, as identified by the doorbell with corresponds to the context which, in turn, identifies the agent, is forwarded on from its submit queue the graphics hardware, such as GPU 1314, for processing.”).
Jiang, Haghighat, Cheng, and RADAMOSS are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling and resource allocation. Therefore, it would been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to substitute the time expired interrupt doorbell notification of RADAMOSS for the doorbell notification of Jiang, Haghighat, and Cheng to arrive at the claimed invention. This simple substitution would have been reasonable and yielded predictable results under MPEP § 2143.
As per claim 11, it is a machine claim comprising similar limitations to claim 1, so it is rejected for similar reasons. Furthermore, Jiang teaches a physical processor (Col. 3 & 4, lines 63-67 & 1-16, “As described above, physical functions and virtual functions are addressing parameters in PCIe, where transactions made across PCIe specify or are intended for a particular virtual function and/or physical function and the processor 102 or APD 116 responds accordingly (note, some ways of addressing over PCIe do not explicitly specify a virtual function or physical function; for example, transactions over PCIe can be routed by memory address instead of explicitly by function, where the devices implicitly understand which function is associated with a particular memory address). The processor 102 directs transactions for a particular VM to the appropriate virtual function of the APD 116 via a memory mapping mechanism.”), a non-transitory computer-readable memory storing instructions (Col. 12, lines 32-42, “The methods or flow charts provided herein can be implemented in a computer program, software, or firmware incorporated in a non-transitory computer-readable storage medium for execution by a general purpose computer or a processor.”), and resources of a hardware accelerator (Col. 1, lines 36-52, “The virtualized device includes a hardware accelerator and a microcontroller that executes firmware. The virtualized device is virtualized in that the virtualized device performs work for different virtual functions (with different virtual functions associated with different virtual machines), each function getting a “time-slice” during which work is performed for that function.).
As per claim 20, it is a product claim comprising similar limitations to claim 1, so it is rejected for similar reasons. Jiang also teaches a non-transitory computer-readable medium comprising one or more computer-executable instructions (Col. 12, lines 32-42, “The methods or flow charts provided herein can be implemented in a computer program, software, or firmware incorporated in a non-transitory computer-readable storage medium for execution by a general purpose computer or a processor.”).
Claim(s) 2, 12, and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Jiang, Haghighat, Cheng, and RADAMOSS as applied to claims 1 and 11 above, and further in view of Booman et al. (US Pub. No. 2016/0092275 A1 hereinafter Booman).
As per claim 2, Jiang, Haghighat, Cheng, and RADAMOSS teach the method of claim 1. Jiang teaches scheduling a first submission from a first virtual function (Col. 7, lines 4-12, “Virtualization on the APD 116 works as follows. The virtualization scheduler 212 manages time-slices on the APD 116 for the VMs (both the host VM 202 and the guest VMS 204) that share the APD 116. The virtualization scheduler 212 tracks the time-slices, stopping work on the APD 116 when a time-slice for a particular VM has expired and starting work for the VM having the next time-slice.”).
Jiang, Haghighat, Cheng, and RADAMOSS fail to teach scheduling a first submission based on the first submission having the lowest execution time among the plurality of submissions.
However, Booman teaches scheduling a first submission based on the first submission having a lowest total execution time slice among the respective submissions (¶ [0025], “In embodiments, the system could utilize a shortest job first (SJF) protocol where the system executes jobs based on the execution-time parameter for each job. For example, the system operating under the SJF protocol can receive a set of jobs and begin executing those jobs in order of ascending of the execution-time parameter for those jobs.”).
Jiang, Haghighat, Cheng, RADAMOSS, and Booman are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the virtual function scheduling method of Jiang, Haghighat, Cheng, and RADAMOSS with the shortest job first protocol of Booman to arrive at the claimed invention. The motivation to modify Jiang, Haghighat, Cheng, and RADAMOSS with the teachings of Booman is that employing a shortest job first protocol avoids the potential for critical jobs with a short execution time having to wait behind jobs with long execution times before being able to process.
As per claim 12, it is a machine claim comprising similar limitations to claim 2, so it is rejected for similar reasons.
As per claim 21, Jiang, Haghighat, Cheng, and RADAMOSS teach the method of claim 1. Jiang teaches scheduling the divisions of the resources to respective virtual functions (Col. 7, lines 4-12, “Virtualization on the APD 116 works as follows. The virtualization scheduler 212 manages time-slices on the APD 116 for the VMs (both the host VM 202 and the guest VMS 204) that share the APD 116. The virtualization scheduler 212 tracks the time-slices, stopping work on the APD 116 when a time-slice for a particular VM has expired and starting work for the VM having the next time-slice.”).
Jiang, Haghighat, Cheng, and RADAMOSS fail to teach scheduling based on a frequency of scheduling that is inversely proportional to the respective measured total of execution time for each virtual function.
However, Booman teaches wherein scheduling divisions of resources to the respective virtual function is further based on a frequency of scheduling that is inversely proportional to the respective measured total execution time for each virtual function (¶ [0043]-[0044], “As described, the workload-time parameter can describe the set of jobs based on the execution-time parameters for that set of jobs…A set of jobs for short term queries could have a large number of jobs in the set with a small execution-time parameters. In embodiments, this set of jobs would have a small workload-time parameter. As described herein, a SJF protocol could be preferred in that instance. A workload-time parameter which is neither large nor small could describe a mixed workload of jobs which contains a number of large execution-time jobs and small execution-time jobs. As described herein, the RL protocol could be preferred in that instance. In embodiments, to determine the schedule tuning parameter, an upper threshold could be associated with a large workload-time parameter and a lower threshold could be associated with small workload-time parameter. In embodiments, if the workload-time parameter is outside of the upper threshold, the schedule tuning parameter is set to a first value which configures the system to operate according to a FIFO protocol…In embodiments, if the workload-time parameter is outside of the lower threshold, the schedule tuning parameter is set to a second value that configures the system to operate according to the SJF protocol. For example, in a system using the equation, the schedule tuning parameter TP could be set to −1 in response to determining that the workload-time parameter is outside of the lower threshold. In certain embodiments, if the workload-time parameter is between the upper and lower threshold, the schedule tuning parameter is set to a third value that configures the system to operate according to the RL protocol.”).
Jiang, Haghighat, Cheng, RADAMOSS, and Booman are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the virtual function scheduling method of Jiang, Haghighat, Cheng, and RADAMOSS with the shortest job first protocol of Booman to arrive at the claimed invention. The motivation to modify Jiang, Haghighat, Cheng, and RADAMOSS with the teachings of Booman is that employing a scheduling algorithm where scheduling frequency is inversely proportional to job execution time avoids the potential for critical jobs with a short execution time having to wait behind jobs with long execution times before being able to process.
Claim(s) 3-4 and 13-14 are rejected under 35 U.S.C. 103 as being unpatentable over Jiang, Haghighat, Cheng, and RADAMOSS as applied to claims 1 and 11 above, in view of Booman and further in view of Lee et al. (US Pub. No. 2023/0071976 A1 hereinafter Lee).
As per claim 3, Jiang, Haghighat, Cheng, and RADAMOSS teach the method of claim 1. Jiang teaches scheduling a first submission from a first virtual function (Col. 7, lines 4-12, “Virtualization on the APD 116 works as follows. The virtualization scheduler 212 manages time-slices on the APD 116 for the VMs (both the host VM 202 and the guest VMS 204) that share the APD 116. The virtualization scheduler 212 tracks the time-slices, stopping work on the APD 116 when a time-slice for a particular VM has expired and starting work for the VM having the next time-slice.”). Haghighat teaches measured total execution time (¶ [0411], “In some embodiments, historical information such as that gathered from various telemetry sources (e.g. timers that timed previous function executions), may be used to estimate the execution time for each function, which may help to inform scheduling of future invocations of the functions.” ¶ [0668], “The orchestrator 2443 receives a function and decides how to route it to be executed. In some embodiments, when a function gets executed, information may be collected about behavior of the function (e.g., cache misses, timing to execute, etc.) by the orchestrator 2443. Some embodiments may use many counters to collect program information, and/or the function may be instrumented to collect data (e.g., and/or a timer may be used to collect information).”).
Jiang, Haghighat, Cheng, and RADAMOSS fail to teach scheduling a first virtual function based on the first virtual function having a smallest actual time slice and the remaining virtual functions having the same total actual execution time.
However, Booman teaches based on both the first submission having a smallest actual incremental time slice and a remainder of the submissions having the same total execution time (¶ [0029], “Some users could adopt an opinion that preferences are satisfied by a system that executes jobs based on the execution-time parameter, i.e. using the SJF protocol as described herein. For example, when many of the jobs are small jobs, executing jobs according to the execution-time parameter could quickly finish execution those small jobs so that they do not need to wait for longer jobs to be finished.”).
Jiang, Haghighat, Cheng, RADAMOSS, and Booman are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the virtual function scheduling method of Jiang, Haghighat, Cheng, and RADAMOSS with the shortest job first protocol of Booman to arrive at the claimed invention. The motivation to modify Jiang, Haghighat, Cheng, and RADAMOSS with the teachings of Booman is that employing a shortest job first protocol avoids the potential for critical jobs with a short execution time having to wait behind jobs with long execution times before being able to process.
Jiang, Haghighat, Cheng, RADAMOSS, and Booman do not explicitly teach taking into account incremental time slice when scheduling virtual functions.
However, Lee teaches incremental time slices (¶ [0044], “When the virtual functions 202, 204 and 206 of the virtual network function application 200 are actually executed on a virtual platform 400, the monitoring unit 10 monitors and collects actual value of each performance indicator of each of the virtual functions 202, 204 and 206. For the actual value of the execution time T_02 of the virtual function 202, the minimum is 55 µs, the mean is 103 µs, and the maximum is 205 µs. For the actual value of the execution time T_04 of the virtual function 204, the minimum is 27 µs, the mean is 49 µs, and the maximum is 130 µs. For the actual value of the execution time T_06 of the virtual function 206, the minimum is 110 µs, the mean is 135 µs, and the maximum is 270 µs.” The smallest incremental time slice could be calculated several ways. For example, it could be the difference between the minimum execution time and the maximum execution time.; see also 0057-0063).
Jiang, Haghighat, Cheng, RADAMOSS, Booman, and Lee are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the method for scheduling virtual functions of Jiang, Haghighat, Cheng, RADAMOSS, and Booman with the incremental time slice data of Lee to arrive at the claimed invention. The motivation to modify Jiang, Haghighat, Cheng, RADAMOSS, and Booman with the teachings of Lee is that scheduling virtual functions based on the smallest incremental time slice avoids pending virtual functions being stuck behind an executing virtual function that is taking abnormally long.
As per claim 4, Jiang, Haghighat, Cheng, and RADAMOSS teach the method of claim 1. Jiang teaches scheduling a first submission from a first virtual function (Col. 7, lines 4-12, “Virtualization on the APD 116 works as follows. The virtualization scheduler 212 manages time-slices on the APD 116 for the VMs (both the host VM 202 and the guest VMS 204) that share the APD 116. The virtualization scheduler 212 tracks the time-slices, stopping work on the APD 116 when a time-slice for a particular VM has expired and starting work for the VM having the next time-slice.”). Haghighat teaches measured total execution time (¶ [0411], “In some embodiments, historical information such as that gathered from various telemetry sources (e.g. timers that timed previous function executions), may be used to estimate the execution time for each function, which may help to inform scheduling of future invocations of the functions.” ¶ [0668], “The orchestrator 2443 receives a function and decides how to route it to be executed. In some embodiments, when a function gets executed, information may be collected about behavior of the function (e.g., cache misses, timing to execute, etc.) by the orchestrator 2443. Some embodiments may use many counters to collect program information, and/or the function may be instrumented to collect data (e.g., and/or a timer may be used to collect information).”). Booman teaches based on the first submission being scheduled first (¶ [0024], “In embodiments, the system could utilize a first-in-first-out (FIFO) protocol where the system executes jobs in order based on a queue-time parameter, which represents how long each job has been waiting to be executed.”) and based on a remainder of the submissions having the same total execution time and having the same detected incremental time slice (¶ [0026], “In certain embodiments, the system could utilize a relative latency (RL) protocol where the system executes jobs based on a ratio of the queue-time parameter to the execution-time parameter for each job.” ¶ [0031], “Some users could adopt an opinion that preferences are satisfied by a system that executes jobs based on the RL protocol as described herein. For example, jobs in the system have a number of large jobs and small jobs, the RL protocol can strike a balance between the FIFO protocol and SJF protocol by accounting for both queue-time and execution-time in the scheduling of jobs.”). Lee teaches incremental time slices (¶ [0044], “When the virtual functions 202, 204 and 206 of the virtual network function application 200 are actually executed on a virtual platform 400, the monitoring unit 10 monitors and collects actual value of each performance indicator of each of the virtual functions 202, 204 and 206. For the actual value of the execution time T_02 of the virtual function 202, the minimum is 55 µs, the mean is 103 µs, and the maximum is 205 µs. For the actual value of the execution time T_04 of the virtual function 204, the minimum is 27 µs, the mean is 49 µs, and the maximum is 130 µs. For the actual value of the execution time T_06 of the virtual function 206, the minimum is 110 µs, the mean is 135 µs, and the maximum is 270 µs.” The smallest incremental time slice could be calculated several ways. For example, it could be the difference between the minimum execution time and the maximum execution time.; see also 0057-0063).
See claim 3 for the motivation to combine.
As per claim 13, it is a machine claim comprising similar limitations to claim 3, so it is rejected for similar reasons.
As per claim 14, it is a machine claim comprising similar limitations to claim 4, so it is rejected for similar reasons.
Claim(s) 5 and 7, 10, and 15-17 are rejected under 35 U.S.C. 103 as being unpatentable over Jiang, Haghighat, Cheng, and RADAMOSS as applied to claims 1 and 11 above, and further in view of Lee.
As per claim 5, Jiang, Haghighat, Cheng, and RADAMOSS teach the method of claim 1.
Jiang, Haghighat, Cheng, and RADAMOSS fail to teach an incremental time slice for a virtual function being ascertained by a hardware or firmware component.
However, Lee teaches wherein an actual incremental time slice for a first virtual function is ascertained by a hardware or firmware component (¶ [0044], “When the virtual functions 202, 204 and 206 of the virtual network function application 200 are actually executed on a virtual platform 400, the monitoring unit 10 monitors and collects actual value of each performance indicator of each of the virtual functions 202, 204 and 206. For the actual value of the execution time T_02 of the virtual function 202, the minimum is 55 µs, the mean is 103 µs, and the maximum is 205 µs. For the actual value of the execution time T_04 of the virtual function 204, the minimum is 27 µs, the mean is 49 µs, and the maximum is 130 µs. For the actual value of the execution time T_06 of the virtual function 206, the minimum is 110 µs, the mean is 135 µs, and the maximum is 270 µs.”), and the hardware or firmware component reports the actual incremental time slice to the scheduler (¶ [0047]-[0048], “To summarize, the monitoring unit 104 may monitor and record actual value of each performance indicator (such as “execution time”, “queue length”, “execution frequency”, or “error rate”) of each of the virtual functions 202, 204 and 206 of the virtual network function application 200 (target virtual network function application)…the performance analysis unit 106 may compare actual value of each performance indicator of each of the virtual functions 202, 204 and 206 of the virtual network function application 200 and actual value of each performance indicator of each physical resource and/or each virtual resource on the virtual platform 400 with associated expected value and/or threshold value…Then, the resource adjusting unit 108 may adjust service of the virtual network function application 200 or the virtual functions 202, 204 and 206, adjust the virtual resources allocated to the virtual network function application 200 and/or other virtual network function applications 230 and 260, or expand the physical resources on the virtual platform 400.”; see also 0057-0063).).
Jiang, Haghighat, Cheng, RADAMOSS, and Lee are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling. Therefore, it would have been obvious to one of ordinary skill the art before the effective filing date of the claimed invention to modify the method for scheduling virtual functions of Jiang, Haghighat, Cheng, and RADAMOSS with the incremental time slice recording functionality of Lee to arrive at the claimed invention. The motivation to modify Jiang, Haghighat, Cheng, and RADAMOSS with the teachings of Lee is that recording the execution times of various virtual functions allows the system to dynamically reschedule the virtual functions based on the recorded execution times or reconfigure the resources allocated to the virtual functions based on the recorded execution times.
As per claim 7, Jiang, Haghighat, Cheng, RADAMOSS, and Lee teach the method of claim 5, Lee teaches wherein the actual incremental time slice for the first virtual function deviates from a designated incremental time slice that was previously assigned to the first virtual function (¶ [0060], “Refer to FIG. 7. In step 614 of the present embodiment 700, based on the comparison result between the actual value of each performance indicator and the expected value and/or threshold value which shows that the actual value of the performance indicator “execution time” is far greater than the expected value (referring to Table 5: the mean and maximum of the actual values of execution time T_04 of the virtual function 204 that is, 238 us and 2530 us respectively, are far greater than the mean and maximum of the expected values of the execution time T_04, that is, 50 us and 150 us, as listed in Table 1)…; see also 0057-0063).
Refer to claim 5 for reason to combine.
As per claim 10, Jiang, Haghighat, Cheng, and RADAMOSS teach the method of claim 1. Jiang teaches the scheduler (Col. 7, lines 4-23, “The virtualization scheduler 212 manages time-slices on the APD 116 for the VMs (both the host VM 202 and the guest VMS 204) that share the APD 116. The virtualization scheduler 212 tracks the time-slices, stopping work on the APD 116 when a time-slice for a particular VM has expired and starting work for the VM having the next time-slice.”). Haghighat teaches measured total execution time (¶ [0411], “In some embodiments, historical information such as that gathered from various telemetry sources (e.g. timers that timed previous function executions), may be used to estimate the execution time for each function, which may help to inform scheduling of future invocations of the functions.” ¶ [0668], “The orchestrator 2443 receives a function and decides how to route it to be executed. In some embodiments, when a function gets executed, information may be collected about behavior of the function (e.g., cache misses, timing to execute, etc.) by the orchestrator 2443. Some embodiments may use many counters to collect program information, and/or the function may be instrumented to collect data (e.g., and/or a timer may be used to collect information).”).
Jiang, Haghighat, Cheng, and RADAMOSS fail to teach updating the total actual execution time for each virtual function until a condition is met.
However, Lee teaches iteratively execute, during a cycle of the hardware accelerator, a function that updates the measured total of execution time of each respective virtual function (¶ [0044], “When the virtual functions 202, 204 and 206 of the virtual network function application 200 are actually executed on a virtual platform 400, the monitoring unit 10 monitors and collects actual value of each performance indicator of each of the virtual functions 202, 204 and 206.”) until a condition is met (¶ [0060], “Refer to FIG. 7. In step 614 of the present embodiment 700, based on the comparison result between the actual value of each performance indicator and the expected value and/or threshold value which shows that the actual value of the performance indicator “execution time” is far greater than the expected value (referring to Table 5: the mean and maximum of the actual values of execution time T_04 of the virtual function 204 that is, 238 µs and 2530 µs respectively, are far greater than the mean and maximum of the expected values of the execution time T_04, that is, 50 µs and 150 µs, as listed in Table 1), the performance analysis unit 106 determines that the virtual function 204 has abnormalities, and the virtual function 204 is located as the bottleneck which deteriorates system performance.” ; see also 0057-0063)
Jiang, Haghighat, Cheng, RADAMOSS, and Lee are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the scheduler of Jiang, Haghighat, Cheng, and RADAMOSS to perform the monitoring unit functionalities of Lee to arrive at the claimed invention. The motivation to modify Jiang, Haghighat, Cheng, and RADAMOSS with the teachings of Lee is that recording the execution times of the virtual functions allows the system to dynamically reschedule the virtual functions based on the recorded execution times or reconfigure the resources allocated to the virtual functions based on the recorded execution times.
As per claim 15, it is a machine claim comprising similar limitations to claim 5, so it is rejected for similar reasons.
As per claim 16, Jiang, Haghighat, Cheng, RADAMOSS and Lee teach the method of claim 15. Jiang teaches the scheduler (Col. 7, lines 4-23, “The virtualization scheduler 212 manages time-slices on the APD 116 for the VMs (both the host VM 202 and the guest VMS 204) that share the APD 116. The virtualization scheduler 212 tracks the time-slices, stopping work on the APD 116 when a time-slice for a particular VM has expired and starting work for the VM having the next time-slice.”). Lee teaches a resource adjusting unit receives a report of the actual incremental time slice from a hardware or firmware component (¶ [0047]-[0048], “To summarize, the monitoring unit 104 may monitor and record actual value of each performance indicator (such as “execution time”, “queue length”, “execution frequency”, or “error rate”) of each of the virtual functions 202, 204 and 206 of the virtual network function application 200 (target virtual network function application)…the performance analysis unit 106 may compare actual value of each performance indicator of each of the virtual functions 202, 204 and 206 of the virtual network function application 200 and actual value of each performance indicator of each physical resource and/or each virtual resource on the virtual platform 400 with associated expected value and/or threshold value…Then, the resource adjusting unit 108 may adjust service of the virtual network function application 200 or the virtual functions 202, 204 and 206, adjust the virtual resources allocated to the virtual network function application 200 and/or other virtual network function applications 230 and 260, or expand the physical resources on the virtual platform 400.”; see also 0057-0063).
Refer to claim 5 for reason to combine.
As per claim 17, it is a machine claim comprising similar limitations to claim 7, so it is rejected for similar reasons.
Claim(s) 8 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Jiang, Haghighat, Cheng, RADAMOSS, and Lee as applied to claims 7 and 17 above, and further in view of Fahrig et al. (US Pub. No. 2011/0099551 A1 hereinafter Fahrig).
As per claim 8, Jiang, Haghighat, Cheng, RADAMOSS, and Lee teach the method of claim 7.
Jiang, Haghighat, Cheng, RADAMOSS, and Lee fail to teach the hardware accelerator going idle if the time slice deviates.
However, Fahrig teaches wherein the actual incremental time slice deviating from the designated incremental time slice causes the hardware accelerator to idle (¶ [0063]-[0064], “While VP1 has acquired a lock on both LP1 and LP2, the scheduler may perform the back-end method for de-scheduling VP1 from LP2 after it has acquired a lock and has entered a spin wait. Initially, the back-end method calls for the scheduler to identify that VP1 has acquired a lock on LP2, and that LP2 is executing a thread issued by VP1 upon acquiring the lock. In further accordance with the back-end method, the scheduler may inspect LP2 to determine a duration of a spin wait. This spin-wait duration may be compared against a time threshold. In one instance, the time threshold represents a predefined number of the nonproductive loops (e.g., 4095 cycles) performed consecutively by the logical processor. In another instance, the time threshold is based on a predefined, static period of time. In yet another instance, the time threshold is dynamically tuned based on recorded behavior of the virtual processors, such as the pattern explained above. When the scheduler determines that the spin-wait duration does not meet the time threshold, it may allow the LP2 to continue attempting to execute the thread issued by VP1 at time slice 720. In contrast, when the scheduler determines that the spin-wait duration on LP2 exceeds the time threshold, VP1 is de-scheduled from LP2 for a predetermined time frame. In this way, the scheduler notices that no useful work is being performed on LP2 at the present time and allows other ready threads to be scheduled on the LP2 to improve overall system throughput.”).
Jiang, Haghighat, Cheng, RADAMOSS, Lee, and Fahrig are considered to be analogous to the claimed invention because they are in the same field of task scheduling. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the scheduling method of Jiang, Haghighat, Cheng, RADAMOSS, and Lee with the forced idling functionality of Fahrig to arrive at the claimed invention. The motivation to modify Jiang, Haghighat, Cheng, RADAMOSS, and Lee with the teachings of Fahrig is that causing the hardware accelerator to idle if time slice deviation occurs improves overall system throughout as hardware resources are not wasted doing unnecessary work.
As per claim 18, it is a machine claim comprising similar limitation to claim 8, so it is rejected for similar reasons.
Claim(s) 9 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Jiang, Haghighat, Cheng, and RADAMOSS as applied to claims 1 and 11 above, and further in view of Fahrig.
As per claim 9, Jiang, Haghighat, Cheng, and RADAMOSS teach the method of claim 1.
Jiang, Haghighat, Cheng, and RADAMOSS fail to teach allocating resources to virtual functions based on a size of the input of the virtual function.
However, Fahrig also teaches wherein the scheduler schedules a frequency of granting a division of the resources to a first virtual function based on a size of a respective submission from the first virtual function (¶ [0055], “When the scheduler determines that the LP3 is executing the critical section of code, the scheduler may grant VP1 a first time-slice extension 630 in order to facilitate LP3 completing the critical section before de-scheduling VP1. In an exemplary embodiment, the first time-slice extension 630 allocates LP3 to VP1 for a reduced duration of time in comparison to the predetermined duration of time associated with the initial time slice 620. By way of example, the initial time slice 620 may have a predetermined duration of 10 ms, while the time-slice extension 630 may have reduced duration of 100 mu.s. By reducing the duration of the time-slice extension 630, inequities between virtual processors attempting to access a particular logical processor are diminished. However, a length of the reduced duration of time associated with the time-slice extension 630 may be adjusted based upon a priority level attached to the thread, or based on a number of virtual processors within a virtual machine that are supported by a particular logical processor.”).
Jiang, Haghighat, Cheng, RADAMOSS, and Fahrig are all considered to be analogous to the claimed invention because they are all in the same field of task scheduling and resource allocation. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the scheduling method of Jiang, Haghighat, Cheng, and RADAMOSS with the well-known technique of allocating resources based on submission size as taught by Haghighat to arrive at the claimed invention. This modification would have been reasonable under MPEP § 2143 as all references schedule tasks on resources taking into account task characteristics (e.g., task size or task execution time).
As per claim 19, it is a machine claim comprising similar limitations to claim 9, so it is rejected for similar reasons.
Response to Arguments
Applicant’s arguments in regards to the 35 U.S.C. § 103 rejection of claim(s) 1-5 and 7-21 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument. Applicant has amended the claims with new limitations that change the scope of the claimed invention. Therefore, the amended claims necessitate new rejections, as addressed above. The amended claims are not allowable over prior art cited previously along with an additional reference, necessitated by amendment, for reason indicated above.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JOHN ROBERT DAKITA EWALD whose telephone number is (703)756-1845. The examiner can normally be reached Monday-Friday: 9:00-5:30 ET.
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, Lewis Bullock can be reached at (571)272-3759. 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.
/J.D.E./Examiner, Art Unit 2199
/LEWIS A BULLOCK JR/Supervisory Patent Examiner, Art Unit 2199
Prosecution Insights