Multi-processor apparatus and method of detection and acceleration of lagging tasks

A method and processing apparatus for accelerating program processing is provided that includes a plurality of processors configured to process a plurality of tasks of a program and a controller. The controller is configured to determine, from the plurality of tasks being processed by the plurality of processors, a task being processed on a first processor to be a lagging task causing a delay in execution of one or more other tasks of the plurality of tasks. The controller is further configured to provide the determined lagging task to a second processor to be executed by the second processor to accelerate execution of the lagging task.

BACKGROUND

Conventional computer architectures include processing devices with multiple processors configured to process sequences of programmed instructions such as threads of a program. The processors can be used to process tasks in parallel with other tasks of the program. During processing of the programs, amounts of parallel work (e.g., number of parallel tasks, amount of time to process parallel tasks, number of cycles to process parallel tasks) can vary over different portions or phases of the program. Processing delays, (e.g., delays in execution of a program) of one or more of these tasks can delay the execution of the program, negatively impacting performance.

DETAILED DESCRIPTION

As used herein, a portion of program includes any sequence of instructions executed by a processing apparatus comprising one or more processors (e.g., CPU, GPU) to perform operations, computations, functions, processes, jobs and the like. A sequence of program instructions can include one or more tasks, threads, work-items, task-groups, thread-groups and work-groups (e.g., wavefronts) and kernels. These terms are, however, merely exemplary and not exhaustive. For simplified explanation purposes the term task is used herein to denote any sequence of program instructions, such as threads, work-items, work-groups (e.g., wavefronts) and kernels.

As used herein, processing of tasks comprises one or more of a plurality of processing stages (e.g., stages of an instruction pipeline), such as but not limited to fetching, decoding, and executing tasks of a program.

During processing of a program, when a task lags behind (e.g., takes longer to complete execution) other tasks due to various factors (e.g., complex branching behavior, an irregular memory access pattern, and/or an unpredictable amount of work), one or more of the other tasks can be caused to wait for the lagging task to complete execution, such as tasks which have completed other processing stages (e.g., fetch and decode stages) but cannot execute because they are dependent on data resulting from the execution of the lagging task. One or more of these lagging tasks can bottleneck the execution of a program and, therefore, delay the execution of the program.

Some programs include lagging tasks which cause different amounts of delays to the execution of other tasks. Further, a lagging task can cause delays to execution of other tasks in one program portion or phase, but not in another program portion or phase. Examples of such programs include neural network programs, clustering programs and graph search/traversal programs having dimensional changes.

A processing apparatus is provided that comprises a plurality of processors comprising a plurality of processor types, each of the plurality of processors configured to process a plurality of tasks of a program. The apparatus also comprises a controller configured to determine, from the plurality of tasks being processed by the plurality of processors, a task being processed on a first processor of a first processor type to be a lagging task causing a delay in execution of one or more other tasks of the plurality of tasks. The controller is also configured to provide, to a second processor of a second processor type, the determined lagging task to be executed by the second processor.

The second processor can be configured to complete execution of the determined lagging task faster than the first processor.

The controller can be further configured to dynamically determine, at runtime, the task being processed on the first processor as the lagging task.

The controller can be further configured to determine the task being processed on the first processor as the lagging task by comparing an execution time of the task being processed on the first processor to execution times of each or a portion of the plurality of tasks and identifying the task being processed on the first processor as the lagging task when the execution time of the task is greater than the execution times of each or the portion of the plurality of tasks when a sampling period has elapsed.

The controller can be further configured to determine the task being processed on the first processor as the lagging task by comparing an execution time of the task being processed on the first processor to an average execution time of each or a portion of the plurality of tasks' execution times and identifying the task being processed on the first processor as the lagging task when the execution time of the task is greater than an average execution time of each or the portion of the plurality of tasks' execution times when a sampling period has elapsed.

The controller can be further configured to determine the task being processed on the first processor as the lagging task by comparing an execution time of the task being processed on the first processor to a threshold execution time and identify the task being processed on the first processor as the lagging task when the execution time of the task is equal to or greater than the threshold execution time when a sampling period has elapsed.

The processing apparatus can further comprise a counter configured to indicate a number of stalls for each of the plurality of tasks, each stall occurring when a corresponding task does not complete execution when a time interval has elapsed. The controller can be further configured to determine the task being processed on the first processor as the lagging task by comparing a stall count of the task being processed on the first processor to stall counts for each or a portion of a plurality of tasks and identifying the stall count of the task being processed on the first processor as the lagging task when the stall count of the task is beyond the stall counts for each or the portion of the plurality of tasks when a sampling period has elapsed.

The controller can be further configured to determine the task being processed on the first processor as the lagging task by comparing a stall count of the task being processed on the first processor to an average stall count of each or a portion of the plurality of tasks' stall counts and identifying the stall count of the task being processed on the first processor as the lagging task when the stall count of the task is beyond an average stall count each or the portion of the plurality of tasks' stall counts when a sampling period has elapsed.

The controller can be further configured to determine the task being processed on the first processor as the lagging task by comparing a stall count of the task being processed on the first processor to a threshold stall count and identifying the task being processed on the first processor as the lagging task when the stall count of the task is beyond the threshold stall count when a sampling period has elapsed.

The controller can be further configured to determine a delay level of a plurality of delay levels for the lagging task. Each of the plurality of delay levels corresponds to a range of amounts of delay caused to execution of other tasks of the plurality of tasks. The controller is further configured to determine the task being processed on the first processor as the lagging task to be executed by the second processor based on a delay level of the lagging task.

The processing apparatus can further comprise a dedicated bus connected between the first processor and the second processor and configured to transfer lagging tasks between the first processor and the second processor.

One or more of the plurality of processors can comprise non-uniform GPU cores each having a plurality of lanes, in which one or more first lanes of a first type are configured to execute the determined lagging task faster than one or more second lanes of a second type are configured to execute the determined lagging task.

The first processor of the first type can be a GPU and the second processor of the second type can be a CPU and the controller is configured to provide the determined lagging task from the GPU to the CPU to be executed.

A method of accelerating program processing is provided that comprises allocating, to a plurality of processors comprising a plurality of processor types, a plurality of tasks of a program for processing. The method also comprises determining, from the plurality of tasks being processed by the plurality of processors, a task being processed on a first processor of a first processor type to be a lagging task causing a delay in execution of one or more other tasks of the plurality of tasks. The method further comprises providing the determined lagging task to a second processor of a second processor type to be executed by the second processor.

The method can further comprise dynamically determining, at runtime, the task processing on the first processor as the lagging task.

The method can further comprise determining the task processing on the first processor as the lagging task by comparing an execution time of the task processing on the first processor to execution times of each or a portion of the plurality of tasks and identifying the task being processed on the first processor as the lagging task when the execution time of the task is greater than the execution times of each or the portion of the plurality of tasks when a sampling period has elapsed.

The method can further comprise determining the task processing on the first processor as the lagging task by comparing an execution time of the task processing on the first processor to an average execution time of each or a portion of the plurality of tasks' execution times and identifying the task being processed on the first processor as the lagging task when the execution time of the task is greater than an average execution time of each or the portion of the plurality of tasks' execution times when a sampling period has elapsed.

The method can further comprise receiving an indication of a number of stalls for each of the plurality of tasks. Each stall occurs when a corresponding task does not complete execution when a time interval has elapsed. The task processing on the first processor can be determined as the lagging task by comparing a stall count of the task processing on the first processor to stall counts for each or a portion of a plurality of tasks and identifying the stall count of the task as the lagging task when the stall count of the task is beyond the stall counts for each or the portion of the plurality of tasks when a sampling period has elapsed.

The task processing on the first processor can be determined as the lagging task by comparing a stall count of the task processing on the first processor to a threshold stall count and identifying the task being processed on the first processor as the lagging task when the stall count of the task is beyond the threshold stall count when a sampling period has elapsed

A tangible, non-transitory computer readable medium is provided that comprises instructions for causing a computer to execute instructions of a method of accelerating program processing. The instructions comprise allocating, to a plurality of processors comprising a plurality of processor types, a plurality of tasks of a program for processing. The instructions also comprise determining, from the plurality of tasks being processed by the plurality of processors, a task being processed on a first processor of a first processor type to be a lagging task causing a delay in execution of one or more other tasks of the plurality of tasks. The instructions further comprise providing the determined lagging task to a second processor of a second processor type to be executed by the second processor.

FIG. 1is a block diagram of an exemplary device100. The device100can include, for example, a computer, a gaming device, a handheld device, a set-top box, a television, a mobile phone, or a tablet computer. The device100includes a processor102, memory104, a storage106, one or more input devices108, and one or more output devices110. The device100can also include an input driver112and an output driver114. It is understood that the device100can include additional components not shown inFIG. 1.

The processor102can include a CPU, a GPU, a CPU and GPU located on the same die, or one or more processor cores, wherein each processor core can be a CPU or a GPU. Memory104can be located on the same die as the processor102, or can be located separately from the processor102. Memory104can include a volatile or non-volatile memory, for example, random access memory (RAM), dynamic RAM, or a cache.

The storage106can include a fixed or removable storage, for example, a hard disk drive, a solid state drive, an optical disk, or a flash drive. The input devices108can include a keyboard, a keypad, a touch screen, a touch pad, a detector, a microphone, an accelerometer, a gyroscope, a biometric scanner, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE 802 signals). The output devices110can include a display, a speaker, a printer, a haptic feedback device, one or more lights, an antenna, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE 802 signals).

The input driver112communicates with the processor102and the input devices108, and permits the processor102to receive input from the input devices108. The output driver114communicates with the processor102and the output devices110, and permits the processor102to send output to the output devices110. It is noted that the input driver112and the output driver114are optional components, and that the device100will operate in the same manner if the input driver112and the output driver114are not present.

FIG. 2is a block diagram illustrating exemplary components of a processing apparatus200used to determine lagging tasks and accelerate execution of the lagging tasks. Each of the components shown inFIG. 2can be part of the exemplary processor102shown inFIG. 1. As shown inFIG. 2, processing apparatus200comprises a first processor202of a first processor type (e.g., GPU) and a second processor204of a second processor type (e.g., CPU). First processor202includes processor cores208, a counter216and memory portion212, which is shared by any number of the processor cores208. Second processor202includes processor cores210, counter206and memory portion214, which is shared by any number of the processor cores210. Processing apparatus200also comprises shared memory portion218, which is shared by first processor202and second processor204. The shared memory218can include a unified address array to transfer lagging tasks between any number of processors (e.g., via a pointer to the shared memory). The number of processors, processor cores, counters and memory portions shown inFIG. 2is merely exemplary.

Processing apparatus200also includes controller220, which is in communication with first processor202(and any of its components), second processor204(and any of its components) and memory portion218. Controller220can also be in communication with other memory portions (not shown). Controller220is configured to determine lagging tasks and accelerate execution of lagging tasks by causing the determined lagging tasks to move between processors. As used herein, a processor can be first processor202, second processor204, processor cores208and processor cores210. Accordingly, lagging tasks can be caused to move between first processor202and second processor204, between processor cores208of first processor202and between processor cores210of second processor204. Controller220is configured to receive and compare data (e.g., task execution times, task stall counts) to determine lagging tasks. Controller220is configured to cause the determined lagging tasks to move between processors by scheduling (or causing a scheduler (not shown) in communication with the controller220) the lagging tasks for processing by any number of processors.

FIG. 3is a diagram illustrating exemplary task allocation to different processors. The tasks302comprise a portion (e.g., sequence of programmed tasks) of a program304and can be allocated (e.g., scheduled) to the first processor202and the second processor204(shown inFIG. 2) for processing. As shown inFIG. 3, tasks302a,302b,302eand302fare allocated to first processor202while tasks302c,302d,302gand302hare allocated to second processor204. The number of tasks302and the order in which the tasks302are allocated to first processor202and second processor204inFIG. 3is merely exemplary.

One or more tasks (e.g., one or more of tasks302athrough302h) are determined to be lagging tasks when they cause a delay in execution of one or more other tasks (e.g., other of tasks302athrough302h), which can occur due to, for example, a longer latency time (e.g., time to complete execution) for the lagging tasks than the one or more other tasks which delays completion of a program.

FIG. 4is a flow diagram illustrating an exemplary method400of accelerating program processing using lagging task detection. As shown at block402of the method400inFIG. 4, the program executes (e.g., executes at the beginning of a program, resumes execution at a portion after the beginning of the program).

As shown at decision block404inFIG. 4, the method400includes determining, whether a task is a lagging task causing a delay in execution of one or more other tasks.

For example, a decision is made as to whether one of the tasks302ato302hinFIG. 3being processed by processor202and204is a lagging task causing a delay in execution of one or more of the other tasks302ato302h.

Lagging task determination includes dynamically determining a lagging task at runtime using one or more metrics recorded as performance counters visible to hardware components. The performance counters can also be utilized by software programs (e.g., programs that support self-modifying or software-controlled task migration and hardware configuration, such as frequency changes). Dynamic determination of lagging tasks includes using one or more dynamic components such as: determination using scoring techniques (e.g., comparing task stall counts, comparing task execution times); determination based on types of actions being requested or processed (e.g., accessing data using a slower process, such as accessing data from a slower memory); determination based on task descheduling (e.g., when descheduling occurs due to a latency operation (e.g., greater than a latency threshold), tasks determined to cause the descheduling are determined to be a lagging tasks); and determination based on monitoring lagging tasks at a synchronization point (e.g., point at which a number of tasks completes before moving to a next portion of a program), such as determining tasks of one or more groups as lagging tasks when it is determined that the one or more groups are waiting for one or more other groups to complete execution at the synchronization point.

Scoring techniques include comparing an execution time of a task to a plurality of task execution times or a threshold execution time. For example, a task can be determined to be lagging when at least one of: a task's execution time (e.g., time to complete execution) is greater than execution times for each or a portion (e.g., percentage, fraction, ratio) of a plurality of tasks (e.g., other tasks of a portion of a program); a task's execution time is greater than an average execution time of each or a portion of the plurality of tasks' execution times; and a task's execution time is equal to or greater than a threshold execution time (e.g., a time over the average execution time of each or a portion of the plurality of tasks). For example, a clock (not shown) indicates whether each of a plurality of tasks has completed execution for each interval (e.g., one or more clock cycles) of a plurality of intervals that make up a sampling period. When the sampling period has completed, the execution times for each of the plurality of tasks is determined. One or more tasks having longer execution times are compared to each or a portion of the other tasks execution times, the average execution time of each or the portion of the plurality of tasks' execution times, or the threshold execution time to determine whether the one or more tasks having longer execution times are lagging tasks.

Scoring techniques also include monitoring stall counts for each stall (e.g., task does not execute at each clock cycle) of a plurality of tasks to indicate whether one or more tasks are waiting for a particular task to complete execution when a time interval (e.g., clock cycle) has elapsed. The particular task can be determined as a lagging task when its stall count (e.g., count for each cycle or a plurality of cycles) for a sampling period is beyond (e.g., less than when incrementing stall counts or greater than when decrementing stall counts) stall counts for each or a portion of a plurality of tasks. The particular task can also be determined as a lagging task when its stall count is beyond an average stall count of a plurality of tasks or a threshold stall count (e.g., a predetermined amount beyond the average stall count). One or more counter are used to indicate a number of stalls for each of the plurality of tasks. Stall counts can also be used to identify delay levels of lagging tasks corresponding to amounts of delay caused by the lagging tasks to the execution of other tasks.

Lagging task determination also includes determining the task being processed on the first processor202as the lagging task to be executed by the second processor204based on a delay level of the lagging task.

FIG. 5is a flow diagram illustrating an exemplary method500of determining lagging tasks using a stall count scoring technique. Tasks302ato302hshown inFIG. 3are used to illustrate the method. Any number of tasks, however, can be used to determine whether a task is a lagging tasks causing delay in the execution of other tasks.

As shown inFIG. 5, a sampling period (e.g., a plurality of clock cycles) is started at502of method500. As shown at decision block504of method500, the method includes determining whether a task is stalled for each cycle. A clock (not shown) can be used to identify each cycle. In the exemplary method shown inFIG. 3, a stall is determined when the task302cdoes not execute (e.g., due to a data dependence) at each clock cycle. For example, task302ccan be monitored at each clock cycle to determine when task302cis stalled at each clock cycle.

As shown at block506, a stall count is incremented when the task302cis determined to be stalled for each cycle. For example, counter206of second processor204(shown inFIG. 2) is used to monitor the delays of task302cby incrementing the count for a stall by task302cat each cycle. The method then proceeds to decision block508to determine whether the sampling period is complete. When the task302cis determined to not be stalled, the stall count for task302cis not incremented and the method proceeds to decision block508to determine whether the sampling period is complete.

Although the exemplary method illustrated atFIG. 5determines stalls of tasks at each clock cycle, stalls can be determined and stall counts can be incremented at other intervals, such as any number of clock cycles.

When it is determined, at block508, that the sampling period for task302cis not completed, the method returns to decision block504. When it is determined, at block508, that the sampling period for task302cis completed, the stall count for the monitored task302ctask is identified.

As shown at block510ofFIG. 5, an average stall count is determined from the stall counts of a plurality of tasks compared to the identified stall count of task. For example, the average stall count can be determined from stall counts of the tasks, such as the other tasks (e.g.,302a,302band302dto302h) or any portion of the tasks. The average stall count is then compared to the identified stall count of task302c.

When tasks are processed in parallel, the stall count for each task can be identified by monitoring the stall count for a single task. For example, one or more counters (e.g., counter206and216) can identify the stall count for each of the tasks302ato302hby monitoring the stall count for a single task (e.g.,302c). A plurality of tasks can also be determined to be lagging tasks at the end of a sampling period.

At decision block512, the method includes determining whether the identified stall count of task302cis less than the average stall count or less than or equal to a predetermined threshold stall count. The predetermined threshold stall count can be a count that is a predetermined amount less than the average stall count. When the identified stall count of task302cis less than the average stall count (or predetermined stall count threshold), indicating that the other tasks are waiting (e.g., due to data dependence) for task302cto execute, task302cis determined to be a lagging task at block514.

Alternatively, counters can be decremented each time a task is determined to be stalled. A task is then determined to be lagging when its stall count is greater than an average stall count or greater than or equal to a predetermined threshold stall count.

Task stall counts are reset, as shown at block516(e.g., reset upon the occurrence of an event, such as when a lagging task is determined; reset periodically, at equal or unequal intervals; reset upon demand, such as upon user request).

Additionally or alternatively, determination of one or more lagging tasks includes static determination via one or more static components which utilize user-assisted and/or offline techniques. Static components include pragmas that identify portions of code likely to cause lagging tasks and lagging paths which include a plurality of lagging tasks; conditions that facilitate identification of lagging task behavior; profiling mechanisms that compute statistics about one or more lagging tasks and changes to the lagging tasks over time; or any other component that utilizes user-assisted and/or offline techniques. Static components indicate to the hardware about locality of lagging tasks in the program. For example, indications are passed to the hardware via an architected register or context of the application.

Referring back toFIG. 4, when a lagging task is not detected, it is determined, at decision block406whether the program is still executing. When the program is determined to be no longer executing, the method400ends at410. When the program is determined to be executing, the method400proceeds back to decision block404to determine whether one or more lagging tasks are detected.

When one or more tasks, executing on a processor of a first type (e.g., GPU), is determined to be a lagging task, the execution of the lagging tasks is accelerated at block408by moving the lagging task from the processor of the first type) to a processor of a second type (e.g., CPU). The lagging task can be moved between processors using a dedicated high bandwidth bus connected between processors. The lagging task can be moved to a processor predetermined (e.g., a processor dedicated to processing lagging tasks) or predicted (e.g., based on past performance) to complete execution of the task faster than the first processor or moved to another processor without such determination or prediction. The lagging task can also be moved to a particular processor based on a task's level of delay.

Exemplary processing apparatuses can be configured to facilitate efficient acceleration of lagging tasks using one or more non-uniform processors, such as processors with non-uniform processing portions (e.g., SIMD cores). For example, one or more of a plurality of lanes (e.g., in each SIMD vector unit (VU) can be configured to process a task faster (e.g., process tasks at a higher frequency) than other lanes of the VU. Lagging tasks can then be moved to a lane (of the same VU or another VU) configured to process a task faster than other lanes.

Exemplary processing apparatuses can be configured to facilitate efficient acceleration of lagging tasks using heterogeneous cores (i.e., heterogeneous GPU cores) in a processor, such as a GPU configured to uniformly distribute CPU cores among vector units in the GPU (e.g., a CPU core paired with a SIMD GPU core) and access (e.g., directly or via local high-bandwidth links) vector general purpose registers (GPRs) of a GPU. A portion of memory associated with the GPU (e.g., GPU cache) can be allocated to scalar type data.

Exemplary processing apparatuses can include heterogeneous memories, in which a portion of memory configured to facilitate accelerated execution of tasks (e.g., SRAM, RLDRAM, 3D-stacked or DDR4 DRAM) is allocated to store data for determined lagging tasks causing delay in execution of one or more other tasks (e.g., when a number of memory stall counts of a lagging task is greater than or equal to a memory stall count threshold).

Exemplary processing apparatuses can be configured to facilitate efficient acceleration of lagging tasks using a memory controller scheduler configured to allocate higher priority to lagging tasks; hardware configured to remap a table that temporarily re-maps blocks of data for lagging tasks into a memory (e.g., low-latency SRAM or a scratchpad memory); one or more per-task hardware caches allocated for lagging tasks (e.g., at the runtime through dynamic partitioning of the cache space by allowing larger fraction of cache space for lagging tasks); a memory management controller configured to perform address translation on behalf of the IO device; dedicated translation lookaside buffers (TLBs) configured to receive and retain lagging tasks incurring longer latencies than one or more other tasks. Address translation entries associated with the lagging tasks can be retained in a TLB for longer periods of time than other tasks, postponing or preventing eviction of the lagging tasks which would otherwise cause performance loss due to longer search times (e.g., page table walks).