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 .
This Office Action is in response to claims filed 07/09/2026.
Claims 1-14 are amended.
Claims 16-20 are new.
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.
Claims 1-9, 11-16 and 20 are rejected under 35 U.S.C. 103(a) as being unpatentable over Ricketts et al. (US 20140337569 A1) (hereinafter Ricketts) in view of Yudanov et al. (US 20160371082 A1) (hereinafter Yudanov).
Regarding Claim 1, Ricketts teaches:
A system for task scheduling, the system comprising: a central processing unit (CPU) core configured to execute a current task;
“The hardware scheduling mechanism provides a means to implement task scheduling” … “In one embodiment, a central processing unit (CPU) is coupled to a parallel processing unit (PPU) and the PPU is configured to execute one or more task”, (Ricketts: ¶011), “In one embodiment, the PPU 200 includes an input/output (I/O) unit 205 configured to transmit and receive communications (i.e., commands, data, etc.) from a central processing unit (CPU)”, (Ricketts: ¶016).
a hardware task scheduler configured to: perform task scheduling to select a candidate task when the CPU core continues executing the current task,
“The TMU 215 selects one or more streams and is configured to organize the selected streams as a pool of pending grids. The pool of pending grids may include new grids that have not yet been selected for execution and grids that have been partially executed and have been suspended”, (Ricketts: ¶018), “A work distribution unit 220 that is coupled between the TMU 215 and the SMs 250 manages a pool of active grids, selecting and dispatching active grids for execution by the SMs 250” … “the TMU 215 also receives grids that are dynamically generated by the SMs 250 during execution of a grid. These dynamically generated grids join the other pending grids in the pending grid pool”, (Ricketts: ¶19), “tasks executing on the PPU 200 can launch child tasks locally by generating a TMD 400 in memory 204 and transmitting a pointer to the TMD 400 to the TMU 215” … “Tasks executing on the SMs 250 of the PPU 200 may transmit messages to the TMU 215 indicating that the task is ready to be scheduled”, (Ricketts: ¶38), “the TMU 215 receives an instruction that indicates a task is ready to be scheduled”, (Ricketts: ¶039), “the TMU 215 to resolve dependencies between tasks to determine whether the task is ready to be launched”, (Ricketts: ¶039). Examiner notes: executing tasks generate child tasks that get scheduled for further execution.
While Ricketts doesn’t explicitly teach a CPU used for executing scheduled tasks, it does teach a PPU connected to a CPU that handles the execution. “In one embodiment, a central processing unit (CPU) is coupled to a parallel processing unit (PPU) and the PPU is configured to execute one or more task”, (Ricketts: ¶011) is similar to a CPU executing the scheduled tasks because it uses PPU as a middleman to execute the tasks. The reference recites that tasks may be executed by the CPU however the embodiment of the invention primarily discusses the use of the PPU, “by either a device driver executing on the CPU or predecessor tasks executed on the PPU”, (Ricketts: ¶011).
actively send metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task
“the task metadata is transmitted to a scheduling unit of the processor. At step 106, the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215” … “Thus, when a TMD 400 is received by the PPU 200, the TMD 400 is stored in an available slot of the launch cache unit 520 before being copied out to memory 204. As long as the TMD 400 has not been evicted from the launch cache unit 520 when the TMU 215 receives an instruction that indicates the task is ready to be scheduled, then the data for the TMD 400 is already resident in on-chip memory accessible to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures”, (Rickett: ¶012). Examiner notes: the metadata is stored in cache before scheduling, therefore the storage happens before task switching since the candidate task hasn’t even been scheduled yet.
and actively send a context of the candidate task to a cache of the CPU core;
“The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures recently written to a memory associated with the processor”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The L1 cache is private memory that is dedicated to a particular SM 250”, (Ricketts: ¶022), “continually incrementing addresses in memory for storing the TMDs 400, this state must be stored and re-loaded whenever context switching is performed”, (Ricketts: ¶049), “FIG. 3, may include, but is not limited to, one or more processing cores, one or more load/store units (LSUs), a level-one (L1) cache, shared memory, and the like”, (Ricketts: ¶015; Fig 3).
wherein the CPU core is configured to read the metadata of the candidate task from the first storage area and read the context of the candidate task from the cache of the CPU core to execute the candidate task, and
“PPU 200 is configured to execute a plurality of threads concurrently in two or more streaming multi-processors (SMs)” … “Each SM 250, described below in more detail in conjunction with FIG. 3, may include, but is not limited to, one or more processing cores”, (Rickett: ¶015), “When the SL unit 550 receives the task state, the SL unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400 that are not resident in the scheduler cache 510” … “unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400” … “the memory read request results in a cache hit and the remaining portion of the TMD 400 is copied from the launch cache unit 520 to the SL unit 550”, (Ricketts: ¶044), “the SL unit 550 retrieves task state information for the task from the scheduler cache unit 510 and/or the launch cache unit 520 such that the task state can be transmitted to the WDU 220 so that the task can be launched” … “It will be appreciated that other information may also be examined when determining which task should be launched in addition to the input dependency information”, (Ricketts: ¶043).
wherein the first storage area is located in a storage area whose access speed is higher than that of a memory,
“The PPU 200 described above may be configured to perform highly parallel computations much faster than conventional CPUs”, (Ricketts: ¶034), “Such memory read requests are high latency operations”, (Ricketts: ¶002), “The task state for the most recently received tasks are, therefore, resident in on-chip memory and available for low-latency scheduling and launch”, (Ricketts: ¶012), “the launch cache unit 520 indicates a cache hit and the data is available for launch with low latency”, (Ricketts: ¶042), “This operation is performed with low-latency because the full TMD 400 is resident in on-chip memory”, (Ricketts: ¶043).
the first storage area comprises an internal storage space and/or a cache of the CPU core.
“the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The launch cache unit 520 provides temporary on-chip memory storage for one or more full TMDs 400”, (Ricketts: ¶042), “the TMU 215 includes a scheduler cache unit 510, a launch cache unit 520”, (Ricketts: ¶039).
Further regarding Claim 1, Ricketts fails to teach:
wherein the metadata of the candidate task comprises storage location information of the context of the candidate task, an identifier of the candidate task, and a status of the candidate task,
However, Yudanov teaches: “The scheduler 230 stores information indicating identifiers of threads that are ready to be scheduled for execution (active threads) in an active list 235” … “a first thread because the context information (Thread 1) for the first thread is stored in the registers 220”, (Yudanov: ¶026), “The scheduler 230 stores information associated with stalled threads” … “the stall list 240 include identifiers (ID 2, ID 3)” … “includes information (WAKE) indicating the wake-up time for the corresponding thread”, (Yudanov: ¶027), “a preempted list 245 includes identifiers of threads (ID 4, ID 5) that have context information stored in the context buffer 225” … “the preempted list 245 indicates that the fourth thread (ID 4) is ready (Y) for execution but the fifth thread (ID 5) is not yet ready (N) for execution”, (Yudanov: ¶028), “The context information for a thread may include information such as a location of an instruction in a program, pointers to a page table, data retrieved from memory, and the like”, (Yudanov: ¶019), “The preempted list 410 includes identifiers (ID 3, ID 5) of Thread 3 and Thread 5 indicating that the context information for these threads is stored in the context buffer 305”, (Yudanov: ¶036).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine the metadata of the candidate task comprises storage location information of a context of the candidate task, an identifier of the candidate task, and a status of the candidate task of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can assign a task metadata like an identifier, status and context location. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “Moving partial context information from the context buffer 225 to the registers 220 conserves space in the registers 220 and may allow context information for a larger number of threads to be stored in the registers 220”, (Yudanov: ¶032).
Regarding Claim 2, Ricketts teaches:
the hardware task scheduler is configured to complete the task scheduling and actively send the metadata of the candidate task to the first storage area before the CPU core detects an occasion for task switching from the current task to the candidate task.
“A hardware scheduling mechanism for a multi-threaded processor is described below. The hardware scheduling mechanism provides a means to implement task scheduling, including dependent execution of tasks, out-of-order execution of tasks, prioritization of tasks, and preemption of tasks”, (Ricketts: ¶11), “The particular fields included in the TMD 400 encapsulate the task state required to configure a processing unit (e.g., the SM 250) to execute the task”, (Ricketts: ¶35), “At step 104, the task metadata is transmitted to a scheduling unit of the processor. At step 106, the task metadata is stored in a cache unit included in the scheduling unit…”, (Ricketts: ¶13), “The TMU 215 writes the data associated with the inline task memory request to a launch cache unit 520. The launch cache unit 520 provides temporary on-chip memory storage for one or more full TMDs 400”, (Ricketts: ¶42), “the SL unit 550 retrieves task state information for the task from the scheduler cache unit 510 and/or the launch cache unit 520 such that the task state can be transmitted to the WDU 220 so that the task can be launched”, (Ricketts: ¶43), “the PPU 200 may enable context switching between different time-slice groups (TSGs)” … “The TSG, in effect, allows different tasks to be switched into and out of the state of the PPU 200 to enable different sets of tasks to be executed substantially concurrently”, (Ricketts: ¶49).
Regarding Claim 3, Ricketts fails to teach:
monitor the first storage area and, in response to determining that metadata of a to-be-executed candidate task is absent from the first storage area, perform the task scheduling and actively send the metadata of the candidate task to the first storage area.
However, Yudanov teaches: “some or all of the context information is moved from the context buffer 225 to one or more of the registers 220 prior to scheduling the corresponding thread for execution in the processor core 205”, (Yudanov: ¶24), “if there are no thread identifiers in the active list 235, indicating that all of the threads that have context information in the registers 220 have stalled, the scheduler 230 checks the preempted list 245 for any preempted threads that have become ready for execution” … “The scheduler 230 then instructs the processor core 205 to move one or more ready preempted threads from the context buffer 225 to the registers 220 so that the scheduler 230 can schedule the ready preempted threads for execution by the processor core 205”, (Yudanov: ¶29).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine monitor the first storage area and, in response to determining that metadata of a to-be-executed candidate task is absent from the first storage area, perform the task scheduling and actively send the metadata of the candidate task to the first storage area of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can move context information required for scheduling when not found. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “reduce stalling is to increase the number of thread contexts that are available for scheduling” … “Stalling may also be reduced by selectively moving context information for a thread from registers in a processor core of a processing device to a context buffer based on a latency associated with the thread”, (Yudanov: ¶13), “Coalescing the threads into a group in this manner may reduce collisions with requests to the main memory 215 from other threads”, (Yudanov: ¶33).
Regarding Claim 4, Ricketts teaches:
the hardware task scheduler is further configured to actively send the context that is of the candidate task and that is stored in the hardware task scheduler to the cache of the CPU core.
“The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures recently written to a memory associated with the processor”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The L1 cache is private memory that is dedicated to a particular SM 250”, (Ricketts: ¶022), “continually incrementing addresses in memory for storing the TMDs 400, this state must be stored and re-loaded whenever context switching is performed”, (Ricketts: ¶049), “FIG. 3, may include, but is not limited to, one or more processing cores, one or more load/store units (LSUs), a level-one (L1) cache, shared memory, and the like”, (Ricketts: ¶015; Fig 3).
Regarding Claim 5, Ricketts teaches:
A method for scheduling tasks in a hardware task scheduler, the method comprising: performing task scheduling to select a candidate task when a central processing unit (CPU) core continues executing a current task;
“The TMU 215 selects one or more streams and is configured to organize the selected streams as a pool of pending grids. The pool of pending grids may include new grids that have not yet been selected for execution and grids that have been partially executed and have been suspended”, (Ricketts: ¶018), “A work distribution unit 220 that is coupled between the TMU 215 and the SMs 250 manages a pool of active grids, selecting and dispatching active grids for execution by the SMs 250” … “the TMU 215 also receives grids that are dynamically generated by the SMs 250 during execution of a grid. These dynamically generated grids join the other pending grids in the pending grid pool”, (Ricketts: ¶19), “tasks executing on the PPU 200 can launch child tasks locally by generating a TMD 400 in memory 204 and transmitting a pointer to the TMD 400 to the TMU 215” … “Tasks executing on the SMs 250 of the PPU 200 may transmit messages to the TMU 215 indicating that the task is ready to be scheduled”, (Ricketts: ¶38), “the TMU 215 receives an instruction that indicates a task is ready to be scheduled”, (Ricketts: ¶039), “the TMU 215 to resolve dependencies between tasks to determine whether the task is ready to be launched”, (Ricketts: ¶039). Examiner notes: executing tasks generate child tasks that get scheduled for further execution.
While Ricketts doesn’t explicitly teach a CPU used for executing scheduled tasks, it does teach a PPU connected to a CPU that handles the execution. “In one embodiment, a central processing unit (CPU) is coupled to a parallel processing unit (PPU) and the PPU is configured to execute one or more task”, (Ricketts: ¶011) is similar to a CPU executing the scheduled tasks because it uses PPU as a middleman to execute the tasks. The reference recites that tasks may be executed by the CPU however the embodiment of the invention primarily discusses the use of the PPU, “by either a device driver executing on the CPU or predecessor tasks executed on the PPU”, (Ricketts: ¶011).
actively sending metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task;
“the task metadata is transmitted to a scheduling unit of the processor. At step 106, the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215” … “Thus, when a TMD 400 is received by the PPU 200, the TMD 400 is stored in an available slot of the launch cache unit 520 before being copied out to memory 204. As long as the TMD 400 has not been evicted from the launch cache unit 520 when the TMU 215 receives an instruction that indicates the task is ready to be scheduled, then the data for the TMD 400 is already resident in on-chip memory accessible to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures”, (Rickett: ¶012). Examiner notes: the metadata is stored in cache before scheduling, therefore the storage happens before task switching since the candidate task hasn’t even been scheduled yet.
and actively sending a context of the candidate task to a cache of the CPU core,
“The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures recently written to a memory associated with the processor”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The L1 cache is private memory that is dedicated to a particular SM 250”, (Ricketts: ¶022), “continually incrementing addresses in memory for storing the TMDs 400, this state must be stored and re-loaded whenever context switching is performed”, (Ricketts: ¶049), “FIG. 3, may include, but is not limited to, one or more processing cores, one or more load/store units (LSUs), a level-one (L1) cache, shared memory, and the like”, (Ricketts: ¶015; Fig 3).
and the first storage area is located in a storage area whose access speed is higher than that of a memory,
“The PPU 200 described above may be configured to perform highly parallel computations much faster than conventional CPUs”, (Ricketts: ¶034), “Such memory read requests are high latency operations”, (Ricketts: ¶002), “The task state for the most recently received tasks are, therefore, resident in on-chip memory and available for low-latency scheduling and launch”, (Ricketts: ¶012), “the launch cache unit 520 indicates a cache hit and the data is available for launch with low latency”, (Ricketts: ¶042), “This operation is performed with low-latency because the full TMD 400 is resident in on-chip memory”, (Ricketts: ¶043).
the first storage area comprises at least one of an internal storage space of a central processing unit (CPU) core or a cache of the CPU core,
“the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The launch cache unit 520 provides temporary on-chip memory storage for one or more full TMDs 400”, (Ricketts: ¶042), “the TMU 215 includes a scheduler cache unit 510, a launch cache unit 520”, (Ricketts: ¶039).
and the CPU core is configured to read the metadata of the candidate task from the first storage area and read the context of the candidate task from the cache of the CPU core to perform the candidate task.
“PPU 200 is configured to execute a plurality of threads concurrently in two or more streaming multi-processors (SMs)” … “Each SM 250, described below in more detail in conjunction with FIG. 3, may include, but is not limited to, one or more processing cores”, (Rickett: ¶015), “When the SL unit 550 receives the task state, the SL unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400 that are not resident in the scheduler cache 510” … “unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400” … “the memory read request results in a cache hit and the remaining portion of the TMD 400 is copied from the launch cache unit 520 to the SL unit 550”, (Ricketts: ¶044), “the SL unit 550 retrieves task state information for the task from the scheduler cache unit 510 and/or the launch cache unit 520 such that the task state can be transmitted to the WDU 220 so that the task can be launched” … “It will be appreciated that other information may also be examined when determining which task should be launched in addition to the input dependency information”, (Ricketts: ¶043).
Further regarding Claim 5, Ricketts fails to teach:
wherein: the metadata of the candidate task comprises storage location information of the context of the candidate task, an identifier of the candidate task, and a status of the candidate task,
However, Yudanov teaches: “The scheduler 230 stores information indicating identifiers of threads that are ready to be scheduled for execution (active threads) in an active list 235” … “a first thread because the context information (Thread 1) for the first thread is stored in the registers 220”, (Yudanov: ¶026), “The scheduler 230 stores information associated with stalled threads” … “the stall list 240 include identifiers (ID 2, ID 3)” … “includes information (WAKE) indicating the wake-up time for the corresponding thread”, (Yudanov: ¶027), “a preempted list 245 includes identifiers of threads (ID 4, ID 5) that have context information stored in the context buffer 225” … “the preempted list 245 indicates that the fourth thread (ID 4) is ready (Y) for execution but the fifth thread (ID 5) is not yet ready (N) for execution”, (Yudanov: ¶028), “The context information for a thread may include information such as a location of an instruction in a program, pointers to a page table, data retrieved from memory, and the like”, (Yudanov: ¶019), “The preempted list 410 includes identifiers (ID 3, ID 5) of Thread 3 and Thread 5 indicating that the context information for these threads is stored in the context buffer 305”, (Yudanov: ¶036).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine the metadata of the candidate task comprises storage location information of a context of the candidate task, an identifier of the candidate task, and a status of the candidate task of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can assign a task metadata like an identifier, status and context location. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “Moving partial context information from the context buffer 225 to the registers 220 conserves space in the registers 220 and may allow context information for a larger number of threads to be stored in the registers 220”, (Yudanov: ¶032).
Regarding Claim 6, Ricketts teaches:
the hardware task scheduler is configured to complete the task scheduling and actively send the metadata of the candidate task to the first storage area before the CPU core detects an occasion for task switching from the current task to the candidate task.
“A hardware scheduling mechanism for a multi-threaded processor is described below. The hardware scheduling mechanism provides a means to implement task scheduling, including dependent execution of tasks, out-of-order execution of tasks, prioritization of tasks, and preemption of tasks”, (Ricketts: ¶11), “The particular fields included in the TMD 400 encapsulate the task state required to configure a processing unit (e.g., the SM 250) to execute the task”, (Ricketts: ¶35), “At step 104, the task metadata is transmitted to a scheduling unit of the processor. At step 106, the task metadata is stored in a cache unit included in the scheduling unit…”, (Ricketts: ¶13), “The TMU 215 writes the data associated with the inline task memory request to a launch cache unit 520. The launch cache unit 520 provides temporary on-chip memory storage for one or more full TMDs 400”, (Ricketts: ¶42), “the SL unit 550 retrieves task state information for the task from the scheduler cache unit 510 and/or the launch cache unit 520 such that the task state can be transmitted to the WDU 220 so that the task can be launched”, (Ricketts: ¶43), “the PPU 200 may enable context switching between different time-slice groups (TSGs)” … “The TSG, in effect, allows different tasks to be switched into and out of the state of the PPU 200 to enable different sets of tasks to be executed substantially concurrently”, (Ricketts: ¶49).
Regarding Claim 7, Ricketts fails to teach:
monitoring the first storage area and, in response to determining that metadata of a to-be-executed candidate task is absent from the first storage area, performing the task scheduling and actively sending the metadata of the candidate task to the first storage area
However, Yudanov teaches: “some or all of the context information is moved from the context buffer 225 to one or more of the registers 220 prior to scheduling the corresponding thread for execution in the processor core 205”, (Yudanov: ¶24), “if there are no thread identifiers in the active list 235, indicating that all of the threads that have context information in the registers 220 have stalled, the scheduler 230 checks the preempted list 245 for any preempted threads that have become ready for execution” … “The scheduler 230 then instructs the processor core 205 to move one or more ready preempted threads from the context buffer 225 to the registers 220 so that the scheduler 230 can schedule the ready preempted threads for execution by the processor core 205”, (Yudanov: ¶29).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine monitor the first storage area and, in response to determining that metadata of a to-be-executed candidate task is absent from the first storage area, perform the task scheduling and actively send the metadata of the candidate task to the first storage area of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can move context information required for scheduling when not found. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “reduce stalling is to increase the number of thread contexts that are available for scheduling” … “Stalling may also be reduced by selectively moving context information for a thread from registers in a processor core of a processing device to a context buffer based on a latency associated with the thread”, (Yudanov: ¶13), “Coalescing the threads into a group in this manner may reduce collisions with requests to the main memory 215 from other threads”, (Yudanov: ¶33).
Regarding Claim 8, Ricketts teaches:
actively sending the context that is of the candidate task and that is stored in the hardware task scheduler to the cache of the CPU core.
“The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures recently written to a memory associated with the processor”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The L1 cache is private memory that is dedicated to a particular SM 250”, (Ricketts: ¶022), “continually incrementing addresses in memory for storing the TMDs 400, this state must be stored and re-loaded whenever context switching is performed”, (Ricketts: ¶049), “FIG. 3, may include, but is not limited to, one or more processing cores, one or more load/store units (LSUs), a level-one (L1) cache, shared memory, and the like”, (Ricketts: ¶015; Fig 3).
Regarding Claim 9, Ricketts teaches:
A method of task scheduling in a central processing unit (CPU) core, the method comprising: continuing to execute a current task when a hardware task scheduler performs task scheduling to select a candidate task;
“The TMU 215 selects one or more streams and is configured to organize the selected streams as a pool of pending grids. The pool of pending grids may include new grids that have not yet been selected for execution and grids that have been partially executed and have been suspended”, (Ricketts: ¶018), “A work distribution unit 220 that is coupled between the TMU 215 and the SMs 250 manages a pool of active grids, selecting and dispatching active grids for execution by the SMs 250” … “the TMU 215 also receives grids that are dynamically generated by the SMs 250 during execution of a grid. These dynamically generated grids join the other pending grids in the pending grid pool”, (Ricketts: ¶19), “tasks executing on the PPU 200 can launch child tasks locally by generating a TMD 400 in memory 204 and transmitting a pointer to the TMD 400 to the TMU 215” … “Tasks executing on the SMs 250 of the PPU 200 may transmit messages to the TMU 215 indicating that the task is ready to be scheduled”, (Ricketts: ¶38), “the TMU 215 receives an instruction that indicates a task is ready to be scheduled”, (Ricketts: ¶039), “the TMU 215 to resolve dependencies between tasks to determine whether the task is ready to be launched”, (Ricketts: ¶039). Examiner notes: executing tasks generate child tasks that get scheduled for further execution.
While Ricketts doesn’t explicitly teach a CPU used for executing scheduled tasks, it does teach a PPU connected to a CPU that handles the execution. “In one embodiment, a central processing unit (CPU) is coupled to a parallel processing unit (PPU) and the PPU is configured to execute one or more task”, (Ricketts: ¶011) is similar to a CPU executing the scheduled tasks because it uses PPU as a middleman to execute the tasks. The reference recites that tasks may be executed by the CPU however the embodiment of the invention primarily discusses the use of the PPU, “by either a device driver executing on the CPU or predecessor tasks executed on the PPU”, (Ricketts: ¶011).
reading metadata of the candidate task from a first storage area before performing task switching from the current task to the candidate task; reading a context of the candidate task from a cache of the CPU core;
“When the SL unit 550 receives the task state, the SL unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400 that are not resident in the scheduler cache 510” … “unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400” … “the memory read request results in a cache hit and the remaining portion of the TMD 400 is copied from the launch cache unit 520 to the SL unit 550”, (Ricketts: ¶044), “the SL unit 550 retrieves task state information for the task from the scheduler cache unit 510 and/or the launch cache unit 520 such that the task state can be transmitted to the WDU 220 so that the task can be launched” … “It will be appreciated that other information may also be examined when determining which task should be launched in addition to the input dependency information”, (Ricketts: ¶043).
and wherein the first storage area is located in a storage area whose access speed is higher than that of a memory,
“The PPU 200 described above may be configured to perform highly parallel computations much faster than conventional CPUs”, (Ricketts: ¶034), “Such memory read requests are high latency operations”, (Ricketts: ¶002), “The task state for the most recently received tasks are, therefore, resident in on-chip memory and available for low-latency scheduling and launch”, (Ricketts: ¶012), “the launch cache unit 520 indicates a cache hit and the data is available for launch with low latency”, (Ricketts: ¶042), “This operation is performed with low-latency because the full TMD 400 is resident in on-chip memory”, (Ricketts: ¶043).
the first storage area comprises at least one of an internal storage space of the CPU core or a cache of the CPU core.
“the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The launch cache unit 520 provides temporary on-chip memory storage for one or more full TMDs 400”, (Ricketts: ¶042), “the TMU 215 includes a scheduler cache unit 510, a launch cache unit 520”, (Ricketts: ¶039).
Further regarding Claim 9, Ricketts fails to teach:
and performing task switching from the current task to the candidate task based on the metadata and the context to perform the candidate task
However, Yudanov teaches: “
wherein the metadata of the candidate task comprises storage location information of the context of the candidate task, an identifier of the candidate task, and a status of the candidate task,
However, Yudanov teaches: “The scheduler 230 stores information indicating identifiers of threads that are ready to be scheduled for execution (active threads) in an active list 235” … “a first thread because the context information (Thread 1) for the first thread is stored in the registers 220”, (Yudanov: ¶026), “The scheduler 230 stores information associated with stalled threads” … “the stall list 240 include identifiers (ID 2, ID 3)” … “includes information (WAKE) indicating the wake-up time for the corresponding thread”, (Yudanov: ¶027), “a preempted list 245 includes identifiers of threads (ID 4, ID 5) that have context information stored in the context buffer 225” … “the preempted list 245 indicates that the fourth thread (ID 4) is ready (Y) for execution but the fifth thread (ID 5) is not yet ready (N) for execution”, (Yudanov: ¶028), “The context information for a thread may include information such as a location of an instruction in a program, pointers to a page table, data retrieved from memory, and the like”, (Yudanov: ¶019), “The preempted list 410 includes identifiers (ID 3, ID 5) of Thread 3 and Thread 5 indicating that the context information for these threads is stored in the context buffer 305”, (Yudanov: ¶036).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine performing task switching from the current task to the candidate task based on the metadata and the context to perform the candidate task wherein the metadata of the candidate task comprises storage location information of a context of the candidate task, an identifier of the candidate task, and a status of the candidate task of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can assign a task metadata like an identifier, status and context location and use that information to perform context switching. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “reduce stalling is to increase the number of thread contexts that are available for scheduling” … “Stalling may also be reduced by selectively moving context information for a thread from registers in a processor core of a processing device to a context buffer based on a latency associated with the thread”, (Yudanov: ¶13), “Moving partial context information from the context buffer 225 to the registers 220 conserves space in the registers 220 and may allow context information for a larger number of threads to be stored in the registers 220”, (Yudanov: ¶032), “Coalescing the threads into a group in this manner may reduce collisions with requests to the main memory 215 from other threads”, (Yudanov: ¶33).
Regarding Claim 11, teaches:
A hardware task scheduler, comprising: a storage, configured to store metadata of one or more candidate tasks; and a processor coupled to the storage, the processor configured to: perform task scheduling to select a candidate task when a central processing unit ( CPU) core continues executing a current task,
“The hardware scheduling mechanism provides a means to implement task scheduling” … “In one embodiment, a central processing unit (CPU) is coupled to a parallel processing unit (PPU) and the PPU is configured to execute one or more task”, (Ricketts: ¶011), “In one embodiment, the PPU 200 includes an input/output (I/O) unit 205 configured to transmit and receive communications (i.e., commands, data, etc.) from a central processing unit (CPU)”, (Ricketts: ¶016), “The TMU 215 selects one or more streams and is configured to organize the selected streams as a pool of pending grids. The pool of pending grids may include new grids that have not yet been selected for execution and grids that have been partially executed and have been suspended”, (Ricketts: ¶018), “A work distribution unit 220 that is coupled between the TMU 215 and the SMs 250 manages a pool of active grids, selecting and dispatching active grids for execution by the SMs 250” … “the TMU 215 also receives grids that are dynamically generated by the SMs 250 during execution of a grid. These dynamically generated grids join the other pending grids in the pending grid pool”, (Ricketts: ¶19), “tasks executing on the PPU 200 can launch child tasks locally by generating a TMD 400 in memory 204 and transmitting a pointer to the TMD 400 to the TMU 215” … “Tasks executing on the SMs 250 of the PPU 200 may transmit messages to the TMU 215 indicating that the task is ready to be scheduled”, (Ricketts: ¶38), “the TMU 215 receives an instruction that indicates a task is ready to be scheduled”, (Ricketts: ¶039), “the TMU 215 to resolve dependencies between tasks to determine whether the task is ready to be launched”, (Ricketts: ¶039). Examiner notes: executing tasks generate child tasks that get scheduled for further execution.
While Ricketts doesn’t explicitly teach a CPU used for executing scheduled tasks, it does teach a PPU connected to a CPU that handles the execution. “In one embodiment, a central processing unit (CPU) is coupled to a parallel processing unit (PPU) and the PPU is configured to execute one or more task”, (Ricketts: ¶011) is similar to a CPU executing the scheduled tasks because it uses PPU as a middleman to execute the tasks. The reference recites that tasks may be executed by the CPU however the embodiment of the invention primarily discusses the use of the PPU, “by either a device driver executing on the CPU or predecessor tasks executed on the PPU”, (Ricketts: ¶011).
actively send metadata that is of the selected candidate task and that is stored in the storage to a first storage area before the CPU core performs task switching from the current task to the selected candidate task,
“the task metadata is transmitted to a scheduling unit of the processor. At step 106, the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215” … “Thus, when a TMD 400 is received by the PPU 200, the TMD 400 is stored in an available slot of the launch cache unit 520 before being copied out to memory 204. As long as the TMD 400 has not been evicted from the launch cache unit 520 when the TMU 215 receives an instruction that indicates the task is ready to be scheduled, then the data for the TMD 400 is already resident in on-chip memory accessible to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures”, (Rickett: ¶012). Examiner notes: the metadata is stored in cache before scheduling, therefore the storage happens before task switching since the candidate task hasn’t even been scheduled yet.
and actively send a context of the selected candidate task to a cache of the CPU core,
“The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures recently written to a memory associated with the processor”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The L1 cache is private memory that is dedicated to a particular SM 250”, (Ricketts: ¶022), “continually incrementing addresses in memory for storing the TMDs 400, this state must be stored and re-loaded whenever context switching is performed”, (Ricketts: ¶049), “FIG. 3, may include, but is not limited to, one or more processing cores, one or more load/store units (LSUs), a level-one (L1) cache, shared memory, and the like”, (Ricketts: ¶015; Fig 3).
the first storage area is located in a storage area whose access speed is higher than that of a memory,
“The PPU 200 described above may be configured to perform highly parallel computations much faster than conventional CPUs”, (Ricketts: ¶034), “Such memory read requests are high latency operations”, (Ricketts: ¶002), “The task state for the most recently received tasks are, therefore, resident in on-chip memory and available for low-latency scheduling and launch”, (Ricketts: ¶012), “the launch cache unit 520 indicates a cache hit and the data is available for launch with low latency”, (Ricketts: ¶042), “This operation is performed with low-latency because the full TMD 400 is resident in on-chip memory”, (Ricketts: ¶043).
the first storage area comprises at least one of an internal storage space or a cache of the CPU core,
“the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The launch cache unit 520 provides temporary on-chip memory storage for one or more full TMDs 400”, (Ricketts: ¶042), “the TMU 215 includes a scheduler cache unit 510, a launch cache unit 520”, (Ricketts: ¶039).
and the CPU core is configured to read the metadata of the selected candidate task from the first storage area and read the context of the selected candidate task from the cache of the CPU core to perform the selected candidate task.
“PPU 200 is configured to execute a plurality of threads concurrently in two or more streaming multi-processors (SMs)” … “Each SM 250, described below in more detail in conjunction with FIG. 3, may include, but is not limited to, one or more processing cores”, (Rickett: ¶015), “When the SL unit 550 receives the task state, the SL unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400 that are not resident in the scheduler cache 510” … “unit 550 may transmit a memory read request to the launch cache unit 520 to read additional fields of the TMD 400” … “the memory read request results in a cache hit and the remaining portion of the TMD 400 is copied from the launch cache unit 520 to the SL unit 550”, (Ricketts: ¶044), “the SL unit 550 retrieves task state information for the task from the scheduler cache unit 510 and/or the launch cache unit 520 such that the task state can be transmitted to the WDU 220 so that the task can be launched” … “It will be appreciated that other information may also be examined when determining which task should be launched in addition to the input dependency information”, (Ricketts: ¶043).
Further regarding Claim 11, Ricketts fails to teach:
wherein: the metadata of the selected candidate task comprises storage location information of the context of the selected candidate task, an identifier of the selected candidate task, and a status of the selected candidate task,
However, Yudanov teaches: “The scheduler 230 stores information indicating identifiers of threads that are ready to be scheduled for execution (active threads) in an active list 235” … “a first thread because the context information (Thread 1) for the first thread is stored in the registers 220”, (Yudanov: ¶026), “The scheduler 230 stores information associated with stalled threads” … “the stall list 240 include identifiers (ID 2, ID 3)” … “includes information (WAKE) indicating the wake-up time for the corresponding thread”, (Yudanov: ¶027), “a preempted list 245 includes identifiers of threads (ID 4, ID 5) that have context information stored in the context buffer 225” … “the preempted list 245 indicates that the fourth thread (ID 4) is ready (Y) for execution but the fifth thread (ID 5) is not yet ready (N) for execution”, (Yudanov: ¶028), “The context information for a thread may include information such as a location of an instruction in a program, pointers to a page table, data retrieved from memory, and the like”, (Yudanov: ¶019), “The preempted list 410 includes identifiers (ID 3, ID 5) of Thread 3 and Thread 5 indicating that the context information for these threads is stored in the context buffer 305”, (Yudanov: ¶036).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine the metadata of the candidate task comprises storage location information of a context of the candidate task, an identifier of the candidate task, and a status of the candidate task of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can assign a task metadata like an identifier, status and context location. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “Moving partial context information from the context buffer 225 to the registers 220 conserves space in the registers 220 and may allow context information for a larger number of threads to be stored in the registers 220”, (Yudanov: ¶032).
Regarding Claim 12, Ricketts teaches:
the hardware task scheduler is configured to complete the task scheduling and actively send the metadata of the selected candidate task to the first storage area before the CPU core detects an occasion for task switching from the current task to the selected candidate task.
“A hardware scheduling mechanism for a multi-threaded processor is described below. The hardware scheduling mechanism provides a means to implement task scheduling, including dependent execution of tasks, out-of-order execution of tasks, prioritization of tasks, and preemption of tasks”, (Ricketts: ¶11), “The particular fields included in the TMD 400 encapsulate the task state required to configure a processing unit (e.g., the SM 250) to execute the task”, (Ricketts: ¶35), “At step 104, the task metadata is transmitted to a scheduling unit of the processor. At step 106, the task metadata is stored in a cache unit included in the scheduling unit…”, (Ricketts: ¶13), “The TMU 215 writes the data associated with the inline task memory request to a launch cache unit 520. The launch cache unit 520 provides temporary on-chip memory storage for one or more full TMDs 400”, (Ricketts: ¶42), “the SL unit 550 retrieves task state information for the task from the scheduler cache unit 510 and/or the launch cache unit 520 such that the task state can be transmitted to the WDU 220 so that the task can be launched”, (Ricketts: ¶43), “the PPU 200 may enable context switching between different time-slice groups (TSGs)” … “The TSG, in effect, allows different tasks to be switched into and out of the state of the PPU 200 to enable different sets of tasks to be executed substantially concurrently”, (Ricketts: ¶49).
Regarding Claim 13, Ricketts fails to teach:
monitor the first storage area and, in response to determining that metadata of a to-be-executed candidate task is absent from the first storage area, perform the task scheduling and actively send the metadata of the selected candidate task to the first storage area
However, Yudanov teaches: “some or all of the context information is moved from the context buffer 225 to one or more of the registers 220 prior to scheduling the corresponding thread for execution in the processor core 205”, (Yudanov: ¶24), “if there are no thread identifiers in the active list 235, indicating that all of the threads that have context information in the registers 220 have stalled, the scheduler 230 checks the preempted list 245 for any preempted threads that have become ready for execution” … “The scheduler 230 then instructs the processor core 205 to move one or more ready preempted threads from the context buffer 225 to the registers 220 so that the scheduler 230 can schedule the ready preempted threads for execution by the processor core 205”, (Yudanov: ¶29).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine monitor the first storage area and, in response to determining that metadata of a to-be-executed candidate task is absent from the first storage area, perform the task scheduling and actively send the metadata of the candidate task to the first storage area of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can move context information required for scheduling when not found. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “reduce stalling is to increase the number of thread contexts that are available for scheduling” … “Stalling may also be reduced by selectively moving context information for a thread from registers in a processor core of a processing device to a context buffer based on a latency associated with the thread”, (Yudanov: ¶13), “Coalescing the threads into a group in this manner may reduce collisions with requests to the main memory 215 from other threads”, (Yudanov: ¶33).
Regarding Claim 14, Ricketts fails to teach:
the storage is further configured to store the context of the selected candidate task.
However, Yudanov teaches: “a preempted list 245 includes identifiers of threads (ID 4, ID 5) that have context information stored in the context buffer 225”, (Yudanov: ¶028), “The preempted list 410 includes identifiers (ID 3, ID 5) of Thread 3 and Thread 5 indicating that the context information for these threads is stored in the context buffer 305”, (Yudanov: ¶036).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine the storage is further configured to store the context of the selected candidate task of Yudanov with the methods and systems of Ricketts resulting in a hardware scheduler that can store task context. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “Moving partial context information from the context buffer 225 to the registers 220 conserves space in the registers 220 and may allow context information for a larger number of threads to be stored in the registers 220”, (Yudanov: ¶032)
Regarding Claim 15, Ricketts teaches:
the processor is further configured to actively send the context that is of the selected candidate task and that is stored in the storage to the cache of the CPU core.
“The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215”, (Ricketts: ¶042), “the hardware scheduling mechanism includes a local cache for storing one or more task metadata data structures recently written to a memory associated with the processor”, (Ricketts: ¶012), “the task metadata is stored in a cache unit included in the scheduling unit”, (Ricketts: ¶013), “The L1 cache is private memory that is dedicated to a particular SM 250”, (Ricketts: ¶022), “continually incrementing addresses in memory for storing the TMDs 400, this state must be stored and re-loaded whenever context switching is performed”, (Ricketts: ¶049), “FIG. 3, may include, but is not limited to, one or more processing cores, one or more load/store units (LSUs), a level-one (L1) cache, shared memory, and the like”, (Ricketts: ¶015; Fig 3).
Regarding Claim 16, Ricketts teaches:
the CPU core is configured to send a task scheduling instruction to the hardware task scheduler while executing the current task, and to continue executing the current task after sending the task scheduling instruction
“tasks executing on the PPU 200 can launch child tasks locally by generating a TMD 400 in memory 204 and transmitting a pointer to the TMD 400 to the TMU 215” … “Tasks executing on the SMs 250 of the PPU 200 may transmit messages to the TMU 215 indicating that the task is ready to be scheduled”, (Ricketts: ¶38), “the TMDs 400 are generated by tasks executing on the SMs 250 in the PPU 200”, (Ricketts: ¶48), “When execution of a grid is completed, the grid is removed from the active grid pool by the work distribution unit 220” … “the TMU 215 also receives grids that are dynamically generated by the SMs 250 during execution of a grid. These dynamically generated grids join the other pending grids in the pending grid pool”, (Ricketts: ¶19). Examiner notes: multiple scheduling messages are transmitted during execution showing that execution continues even after sending a scheduling instruction.
Regarding Claim 20, Ricketts teaches:
the CPU core is configured to send metadata of a switched task to a second storage area, and the hardware task scheduler is configured to read the metadata of the switched task from the second storage area and store the metadata of the switched task in the hardware task scheduler.
“The scheduler cache unit 510 transmits a memory read request to the launch cache unit 520 to retrieve the first portion of the TMD 400 from the memory 204” … “the first portion of the TMD 400 is copied from the launch cache unit 520 to the scheduler cache unit 510”, (Ricketts: ¶43), “The TMD 400 includes a plurality of fields that encapsulate task state information associated with a task” … “The particular fields included in the TMD 400 encapsulate the task state required to configure a processing unit (e.g., the SM 250) to execute the task”, (Ricketts: ¶35), “the hardware-writeable fields can be updated periodically by the TMU 215 after being read from the launch cache unit 520 and stored in the scheduler cache unit 510 or in other registers internal to the TMU 215”, (Ricketts: ¶47), “the PPU 200 may enable context switching between different time-slice groups (TSGs)” … “allows different tasks to be switched into and out of the state of the PPU 200 to enable different sets of tasks to be executed substantially concurrently” … “inline task memory request relies on state within the TMU 215 in order to process continually incrementing addresses in memory for storing the TMDs 400, this state must be stored and re-loaded whenever context switching is performed…”, (Ricketts: ¶49).
Claim 10 is rejected under 35 U.S.C. 103(a) as being unpatentable over Ricketts in view of Yudanov, in further view of Cain et al. (US 20160357676 A1) (hereinafter Cain).
Regarding Claim 10, Ricketts in view of Yudanov fails to teach:
prefetching the context of the candidate task based on the storage location information included in the metadata, so that the context of the candidate task is sent to the cache of the CPU core before performing task switching from the current task to the candidate task
However, Cain teaches: “The cache restoration data indicates for each task what data need to be fetched into the cache by the prefetch logic 202 for cache restoration when the task is rescheduled.”, (Cain: ¶14), “The cache restoration data, which is stored in each entry of the OS task queue 201 of FIG. 2, may represent a pointer in memory to the location where the restoration data is stored”, (Cain: ¶15), “Then, in block 304, when the amount of time left in the current task's predicted execution time, as given by the task switch timer 108/204, is equal to the amount of time needed for cache restoration for the next task as given by the prefetch threshold, prefetching for the next task is started during the current task's time quantum” … “For example, prefetching for Task 3, based on cache restoration data 3 in OS task queue 201, is started by prefetch logic 104/202 while Task 2 finishes executing” … “when there is a task switch from Task 2 to Task 3, the data last used for Task 3 is already back in the cache 102”, (Cain: ¶17), “The amount of time per prefetch may be determined based on the location(s) of the prefetch data. For example, a prefetch of data from main memory to an L1 cache may take longer than a prefetch of data from an L4 cache to an L1 cache”, (Cain: ¶19), “The prefetch threshold allows the prefetch logic to begin cache restoration (e.g., prefetching of cache entries) for a next task before the next task is scheduled and executed”, (Cain: ¶10).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine prefetching the context of the candidate task based on the storage location information included in the metadata, so that the context of the candidate task is sent to the cache of the CPU core before performing task switching from the current task to the candidate task of Cain with the methods and systems of Ricketts in view of Yudanov resulting in a system gathering task context before performing a context switch. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “efficient cache restoration in a processor”, (Cain: ¶20), “The prefetch threshold allows the prefetch logic to begin cache restoration (e.g., prefetching of cache entries) for a next task before the next task is scheduled and executed”, (Cain: ¶10).
Claims 17-18 are rejected under 35 U.S.C. 103(a) as being unpatentable over Ricketts in view of Yudanov, in further view of Dimond et al. (US 20190114262 A1) (hereinafter Dimon).
Regarding Claim 17, Ricketts in view of Yudanov fails to teach:
the hardware task scheduler is configured to send an instruction to a bus to cause the metadata of the candidate task to be stored in the first storage area.
However, Dimond teaches: “a data processing system 150 comprises a task scheduler 164 which allocates software tasks to the CPUs 154 and 156 in the data processing system for execution” … “The task scheduling information received from the task scheduler 164 by the stashing hardware 162 enables it to determine which of the data caches 158 or 160 is the appropriate recipient for this cache stashing operation”, (Dimond: ¶63), “a scheduling table 186 showing a set of task IDs and the destination host devices on which the task scheduler has scheduled those processes to be executed”, (Dimond: ¶64), “the stashing manager initiates the cache stashing using the defined cache stashing parameters for the defined link from Agent A to Agent X, and (if also defined) for the message and/or the data buffer, to cause at least a proportion of the data specified in the message to be stashed in a cache associated with the host data processing device upon which task Z is scheduled”, (Dimond: ¶66), “a bus master in a data processing system may proactively cause a specific item of data to be stored in a specific cache in the data processing system in a technique called cache stashing…”, (Dimond: ¶2), “
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine the hardware task scheduler is configured to send an instruction to a bus to cause the metadata of the candidate task to be stored in the first storage area of Dimond with the methods and systems of Ricketts in view of Yudanov resulting in a system with store metadata via a bus. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “to avoid a cache miss and software prefetching techniques in the system may suffice to ensure that future accesses to the remainder of the data will not miss in the cache”, (Dimond: ¶42), “improve performance by reducing the access latency associated with retrieving these items from the shared memory”, (Dimond: ¶57).
Regarding Claim 18, Ricketts in view of Yudanov fails to teach:
the instruction comprises at least one of a cache level or an identifier of the CPU core.
However, Dimon teaches: “In the embodiment shown the descriptor portion 82 also comprises at least one further stashing control parameter to enable further configuration of the stashing behavior with respect to this message”, (Dimond: ¶60), “This set of stashing control parameters may be provided in a number of ways in the system, for example as part of an individual message” … “The parameters which may be controlled by the stashing control field 100 are: a target cache level at which the stashing should take place…”, (Dimond: ¶61), “at least one of these stashing control parameters specifies a cache level at which the data associated with the message is to be cached”, (Dimond: ¶ 40).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine the instruction comprises at least one of a cache level or an identifier of the CPU core of Dimond with the methods and systems of Ricketts in view of Yudanov resulting in a system with instructions to store specifying a cache level. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “to avoid a cache miss and software prefetching techniques in the system may suffice to ensure that future accesses to the remainder of the data will not miss in the cache”, (Dimond: ¶42), “improve performance by reducing the access latency associated with retrieving these items from the shared memory”, (Dimond: ¶57).
Claim 19 is rejected under 35 U.S.C. 103(a) as being unpatentable over Ricketts in view of Yudanov, in further view of Sukhomlinov et al. (US 20190104178 A1) (hereinafter Sukhomlinov).
Regarding Claim 19, Ricketts in view of Yudanov fails to teach:
the hardware task scheduler is configured to select the candidate task based on affinity between the candidate task and the CPU core.
However, Sukhomlinov teaches: “scheduling circuitry to allocate and pin a VHTR to each of the plurality of VNFs, schedule execution of a VHTR on each of a plurality of cores”, (Sukhomlinov: Abstract), “the VHTR quality control includes affinity requirements, indicating whether the VHTR is to be pinned to a specific physical core, a non-uniform memory access (NUMA) node, etc.”, (Sukhomlinov: ¶83), “a hardware scheduler is a state machine which uses information from VHTR descriptors of VHTRs in a VHTR queue, and selects those to schedule on physical/logical cores”, (Sukhomlinov: ¶80), “Example 3 includes the substance of the exemplary processor of Example 1, wherein each of the multiple VHTR descriptors further comprises an affinity, and the scheduling circuitry attempts to schedule execution of the allocated and pinned VHTRs according to the affinity”, (Sukhomlinov: ¶174).
It would have been obvious to a person having ordinary skill in the art prior to the effective filing date of the claimed invention to combine the hardware task scheduler is configured to select the candidate task based on affinity between the candidate task and the CPU core of Sukhomlinov with the methods and systems of Ricketts in view of Yudanov resulting in a system executing tasks on selected cores. A person having ordinary skill in the art would have been motivated to make this combination, with a reasonable expectation of success, for the purpose of “avoid the context switch penalty associated with using an operating system for the context switch” … “promotes efficient use of the processing core”, (Sukhomlinov: ¶32), “allow more flexible scheduling and reduce the potential for massive oversubscription of the particular core”, (Sukhomlinov: ¶35), “improve the efficient use of CPU resources by switching in another VHTR to use a processor core”, (Sukhomlinov: ¶54).
Response to Arguments
In light of applicants amendments, all Claim objections and rejections under 35 U.S.C. 101 have been with withdrawn.
Regarding rejections made under 35 U.S.C. 103:
Applicant argues:
“Applicant submits that Ricketts does not disclose or suggest all limitations in the independent claims 1, 5, 9, and 11 as amended. For example, claim 1 recites "actively send a context of the candidate task to a cache of the CPU core," "perform task scheduling to select a candidate task when the CPU core continues executing the current task," and "actively send metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task" as recited in claim 1.
According to Ricketts, the TMD fields are launch/configuration data for PPU/GPU tasks. For example, Ricketts explains that the TMD encapsulates task state necessary for configuring a processing unit to complete work, and identifies TMD fields such as program offset, grid dimensions, block dimensions, resources, cache control, memory barriers, and semaphores for launching and executing tasks on the PPU. See Ricketts " [0011], [0035]-[0037], [0039]-[0044]. Ricketts, however, does not teach a CPU execution context used to restore a running environment during task switching.
As amended, claim 1 requires a hardware task scheduler to select a candidate task when the CPU core continues executing a current task, actively send selected-task metadata to CPU- core internal storage or CPU-core cache before task switching, and actively send a context of the selected candidate task to a cache of the CPU core, so that the CPU core reads both the metadata and the context from the recited fast-storage/cache locations to execute the candidate task. Therefore, because Ricketts only caches a received TMD in a scheduling-unit cache for low- latency launch of memory-defined PPU tasks, Ricketts does not disclose or suggest "actively send a context of the candidate task to a cache of the CPU core," "perform task scheduling to select a candidate task when the CPU core continues executing the current task," and "actively send metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task" as recited in claim 1.”
Examiner respectfully disagrees, Ricketts teaches: “tasks executing on the PPU 200 can launch child tasks locally by generating a TMD 400 in memory 204 and transmitting a pointer to the TMD 400 to the TMU 215”, (Ricketts: ¶38), “The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215” … “The TMU 215 writes the data associated with the inline task memory request to a launch cache unit 520”, (Ricketts: ¶042). This citation uses the verb transmit to describe the movement of task context data of the next task. Therefore the citations in Ricketts are an explicit teaching of the limitation “actively send a context of the candidate task to a cache of the CPU core”. Further, Ricketts teaches: “tasks executing on the PPU 200 can launch child tasks locally by generating a TMD 400 in memory 204 and transmitting a pointer to the TMD 400 to the TMU 215” … “Tasks executing on the SMs 250 of the PPU 200 may transmit messages to the TMU 215 indicating that the task is ready to be scheduled”, (Ricketts: ¶38), “the task may then be sent to the SL unit 550 to be scheduled and launched”, (Ricketts: ¶39). The citations indicate that tasks which are already executing may generate child tasks that are instructed to be scheduled while execution occurs. This explicitly teaches the limitation “perform task scheduling to select a candidate task when the CPU core continues executing the current task” and therefore Ricketts still applies to this amended limitation. Lastly, Ricketts teaches: “The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215” … “Thus, when a TMD 400 is received by the PPU 200, the TMD 400 is stored in an available slot of the launch cache unit 520 before being copied out to memory 204. As long as the TMD 400 has not been evicted from the launch cache unit 520 when the TMU 215 receives an instruction that indicates the task is ready to be scheduled, then the data for the TMD 400 is already resident in on-chip memory accessible to the TMU 215”, (Ricketts: ¶042). The citations once again use the verb transmit to describe the movement of meta data which falls under “actively sending”. The process of scheduling cannot occur without the existence of metadata in the storage so the transmission of the meta data must occur before execution of the candidate task via task switching. Therefore, not only does Ricketts teach the aforementioned limitations of “actively send a context of the candidate task to a cache of the CPU core” and “perform task scheduling to select a candidate task when the CPU core continues executing the current task”, but “actively send metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task” as well, thus the Claim does not recite patent eligible subject matter and the 35 U.S.C. 103 rejection is upheld.
Applicant argues:
“In addition, Ricketts does not teach or suggest "a hardware task scheduler actively [[sending]] metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task" as recited in claim 1 because according to Ricketts, the TMD data flows in the CPU-PPU direction, and the TMU passively receives and stores it in its own launch cache (emphasis added).”
Examiner respectfully disagrees, Ricketts teaches: “The host interface unit 210 receives the inline task memory request as well as the data defining a task state (i.e., TMD 400) and transmits the inline task memory request and the data to the TMU 215” … “Thus, when a TMD 400 is received by the PPU 200, the TMD 400 is stored in an available slot of the launch cache unit 520 before being copied out to memory 204. As long as the TMD 400 has not been evicted from the launch cache unit 520 when the TMU 215 receives an instruction that indicates the task is ready to be scheduled, then the data for the TMD 400 is already resident in on-chip memory accessible to the TMU 215”, (Ricketts: ¶042). The citations clearly use the action verb “transmit” which does not indicate any passive storage contrary to applicants assertion that data simply “flows” to the storage. Data is being actively sent to the component that stores the it which is an explicit disclosure of the Claim limitation. Therefore Ricketts fully teaches the limitation “a hardware task scheduler actively [[sending]] metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task”, thus the Claims do not recite patent eligible subject matter and the 35 U.S.C. 103 rejection is upheld.
Applicant argues:
“Independent claims 5, 9, and 11 have been amended with similar limitations as in claim 1. For similar reasons, claims 5, 9, and 11, and the respective dependent claims, are also patentable over Ricketts”
Examiner Respectfully disagrees, as discussed above, Claim 1 does not recite patent eligible subject matter and the 35 U.S.C. 103 rejection is upheld, therefore the corresponding limitations of the further independent Claims 5, 9 and 11 also do not recite patent eligible subject matter and the 35 U.S.C. 103 rejection is upheld.
Applicant argues:
“Claims 2, 6, 10, 12, and 14 are rejected under 35 U.S.C. 103(a) as being unpatentable over Ricketts, in view of Yudanov et al. (US 20160371082 A1, "Yudanov"). Claim 2 depends from claim 1. Claim 6 depends from claim 5. Claim 10 depends from claim 9. Claims 12 and 14 depend from claim 11. Yudanov does not remedy the deficiency in Ricketts regarding "actively send a context of the candidate task to a cache of the CPU core," "perform task scheduling to select a candidate task when the CPU core continues executing the current task," and "actively send metadata of the candidate task to a first storage area before the CPU core performs task switching from the current task to the candidate task" as recited in claim 1. For similar reasons above, because claims 1, 5, 9, and 11 are patentable, the respective dependent claims 2, 6, 10, 12, and 14 are also patentable”
Examiner respectfully disagrees, as detailed above Ricketts teaches amended dependent Claims in view of Yudanov and therefore the dependent Claims 2, 6, 10, 12, and 14 are fully taught by Yudanov as originally cited in the previous Office Action. Therefore Yudanov does remedy the deficiencies of Ricketts with regards to the dependent Claims 2, 6, 10, 12, and 14 and thus the Claims do not recite patent eligible subject matter and the 35 U.S.C. 103 rejection is upheld.
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.
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 SHIHAB ALAM whose telephone number is (571)272-8705. The examiner can normally be reached Mon - Fri 7:30am-5pm.
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, Bradley Teets can be reached at (571) 272-3338. 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.
/S.A./Examiner, Art Unit 2197
/BRADLEY A TEETS/Supervisory Patent Examiner, Art Unit 2197
