Method and apparatus for selecting preemption technique

Provided is a method and apparatus of selecting a preemption technique for a computation unit included in a processor to execute a second task before the at least one computation unit finishes executing a first task. The method includes receiving a preemption request, predicting a cost of preemption techniques based on a progress of the first task until receipt of the preemption request, and selecting one of the preemption techniques based on the predicted cost.

CROSS-REFERENCE TO RELATED APPLICATION(S)

This application claims the benefit under 35 USC § 119(a) of Korean Patent Application No. 10-2014-0187503, filed on Dec. 23, 2014, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein by reference for all purposes.

BACKGROUND

The following description relates to a method and apparatus for selecting a preemption technique.

2. Description of Related Art

Computer systems of today such as, for example, desktops, servers, cellular phones, and tablet PCs adopt Graphics Processing Units (GPUs) to support traditional Central Processing Units (CPUs). In such heterogeneous systems, tasks may be transmitted from a CPU to a GPU in the form of kernels. The GPU may effectively speed up data-parallel kernels with the help of new programming models such as OpenCL.

Meanwhile, heterogeneous systems may include a plurality of CPUs sharing one GPU. When the plurality of CPUs simultaneously transmit data-parallel kernels to the GPU, multi-tasking needs to be supported. In general, multi-tasking on a CPU is performed through context switching. However, a task executed on the GPU has a huge size of a context, such that various problems may occur if preemptive multi-tasking is performed through context switching on the GPU.

SUMMARY

Provided are a method and apparatus for selecting a preemption technique.

In one general aspect, there is provided a method of selecting a preemption technique for a computation unit included in a processor to execute a second task before the computation unit finishes executing a first task, the method including receiving a preemption request, predicting a cost of preemption techniques based on a progress of the first task until receipt of the preemption request, and selecting one of the preemption techniques based on the predicted cost.

The preemption techniques may include a first technique where information associated with the first task is stored and the first task is replaced with the second task, a second technique where the second task is executed after execution of the first task is finished, and a third technique where the first task is immediately replaced with the second task without storing the information associated with the first task.

The cost may include a throughput overhead and a preemption latency, and the predicting of the cost may include predicting the throughput overhead and the preemption latency for each preemption technique of the preemption techniques.

The selecting of the preemption technique may include selecting the preemption technique having a smallest throughput overhead among the preemption techniques.

The selecting of the preemption technique may include selecting a preemption technique having a smallest preemption latency among the preemption techniques.

The method may include receiving a user input for selecting one of throughput overhead and preemption latency, wherein the selecting of one of the preemption techniques comprises selecting the preemption technique having a lowest cost corresponding to the user input among the predetermined preemption techniques.

The predicting of the cost may include predicting the cost based on a number of Single Instruction Multiple Data (SIMD) instructions that have been executed in the first task and an average Instructions-Per-Clock (IPC) of the first task.

The method may include assigning the second task to at least one computation unit according to the selected preemption technique.

The receiving of the preemption request may include receiving information regarding which kernel is to be preempted, how many computation units are to be preempted, and at least one of a preemption latency limiting condition or a throughput overhead limiting condition.

According to another there is provided an apparatus for selecting a preemption technique for a computation unit included in a processor to execute a second task before the computation unit finishes executing a first task, the apparatus including a selector configured to receive a preemption request, and a predictor configured to predict a cost of preemption techniques based on a progress of the first task until receipt of the preemption request, wherein the selector is further configured to select one of the preemption techniques based on the predicted cost.

The preemption techniques may include a first technique where information associated with the first task is stored and the first task is replaced with the second task, a second technique where the second task is executed after execution of the first task is finished, and a third technique where the first task is immediately replaced with the second task without storing the information associated with the first task.

The cost may include a throughput overhead and a preemption latency, and the predictor is further configured to predict the throughput overhead and the preemption latency for each preemption technique of the preemption techniques.

The selector may be further configured to select a preemption technique having a smallest throughput overhead among the preemption techniques.

The selector may be further configured to select a preemption technique having a smallest preemption latency among the preemption techniques.

The selector may be further configured to receive a user input for selecting one of throughput overhead and preemption latency and to select one of the preemption techniques having a lowest cost corresponding to the user input among the preemption techniques.

The predictor may be further configured to predict the cost based on a number of Single Instruction Multiple Data (SIMD) instructions that have been executed in the first task and an average Instructions-Per-Clock (IPC) of the first task.

The predictor may be further configured to receive information comprising at least one of processing-finished task, SIMD instruction progress statistics for each task, a start point of a non-idempotent region from the computation unit and to predict the cost based on the received information.

The apparatus may include a scheduler configured to assign the second task to at least one computation unit according to the selected preemption technique.

DETAILED DESCRIPTION

FIG. 1is a diagram illustrating an example of an apparatus100for selecting a preemption technique. Referring toFIG. 1, the apparatus100for selecting a preemption technique (or a preemption technique selecting apparatus100) may include a selector110and a predictor120. While components related to the present example are illustrated in the preemption technique selecting apparatus100, it is understood that those skilled in the art may include other general components. In another example, the selector110and the predictor120of the preemptive technique selecting apparatus100illustrated inFIG. 1may be provided as independent devices.

The selector110and the predictor120may correspond to one processor or a plurality of processors. Each of the processors may be implemented with an array of multiple logic gates, or a combination of a general-purpose microprocessor and a memory having stored therein a program to be executed by the microprocessor. Also, it would be understood by those of ordinary skill in the art that the processor may be implemented with other types of hardware.

The selector110receives a preemption request. The selector110selects one preemption techniques. Herein, preemption means an event in which a first task being currently executed in a computation unit is replaced with a second task. In other words, preemption means an event in which as the second task is input prior to completion of the first task in the computation unit, execution of the first task is stopped and the second task is executed.

The preemption request may be received from the outside of the preemption technique selecting apparatus100. For example, the preemption request may be transmitted from an operating system. Assuming that the preemption technique selecting apparatus100is included in a Graphics Processing Unit (GPU), the preemption request may be transmitted from a Central Processing Unit (CPU) located outside the GPU.

The preemption request may include which kernel is to be preempted, how many computation units are to be preempted, and a preemption latency limiting condition or a throughput overhead limiting condition. Herein, the preemption latency limiting condition means a limit condition of a latency time occurring when preemption is carried out. For example, if the preemption latency limiting condition is 1 ms and a latency time occurring due to carrying out preemption is 1.5 ms, then the preemption falls beyond the preemption latency limiting condition.

The throughput overhead limiting condition means a limit condition of a throughput overhead generated due to carrying out preemption. For example, if the throughput overhead limiting condition is 3 and the throughput overhead generated by carrying out preemption is 4, then the preemption may fall beyond the throughput overhead limiting condition.

The selector110selects one of the predetermined preemption techniques based on a cost of each of the predetermined preemption techniques. The cost of each predetermined preemption technique is predicted by the predictor120. The predetermined preemption techniques may include context switching in which a first task is replaced with a second task after information associated with the first task is stored, draining in which the second task is executed after execution of the first task is finished, and flushing in which the first task is immediately replaced with the second task without storing the information associated with the first task. The selector110selects one of context switching, draining, and flushing.

The predictor120predicts the cost of each preemption technique based on a degree to which the first task has been executed until a preemption request is received. The predictor120predicts the cost of each of context switching, draining, and flushing according to a degree to which the first task has been executed until the preemption request is received. The cost means a throughput overhead or a preemption latency generated when preemption is carried out according to a preemption technique. The predictor120predicts each of a throughput overhead and a preemption latency generated when preemption is carried out by context switching. The predictor120predicts each of a throughput overhead and a preemption latency generated when preemption is carried out by draining. The predictor120predicts each of a throughput overhead and a preemption latency generated when preemption is carried out by flushing. The predictor120transmits information about the predicted cost to the selector110, which then selects a preemption technique based on the predicted cost.

Referring toFIG. 2, operations of the selector110and the predictor120will be described in further detail.FIG. 2is a diagram illustrating an example of a method of selecting a preemption technique. The operations inFIG. 2may be performed in the sequence and manner as shown, although the order of some operations may be changed or some of the operations omitted without departing from the spirit and scope of the illustrative examples described. Many of the operations shown inFIG. 2may be performed in parallel or concurrently.

Referring toFIG. 2, the preemption technique selecting method may include operations that are processed in time series by the preemption technique selecting apparatus100illustrated inFIG. 1. The above descriptions of preemption technique selecting apparatus100illustrated inFIG. 1is also applicable toFIG. 2, and is incorporated herein by reference. Thus, the above description may not be repeated here.

In operation210, the selector110receives a preemption request. The preemption request may include information regarding which kernel is to be preempted, how many computation units are to be preempted, and a preemption latency limiting condition or a throughput overhead limiting condition. Preemption will be described in detail with reference toFIGS. 3 and 4.

FIG. 3is a diagram illustrating an example of a task.FIG. 3illustrates an example of the operation of a data-parallel kernel according to OpenCL.

A computing device (for example, a CPU or GPU)310processes a plurality of processes or a plurality of threads in parallel. For example, if the computing device310is a GPU, a plurality of computation units311,312,313, and314included in the GPU may process a plurality of threads321included in input data320in parallel.

For example, the input data320may include Single Instruction Multiple Data (SIMD) instructions. Some of the plurality of threads321included in the input data320may form one task group322. The task group322means a virtual unit including threads corresponding to the same instruction, i.e., the threads included in the task group322correspond to the same instruction, but data included in each thread differs from thread to thread.

The computation unit311included in the computing device310processes one task group322. For example, the computation unit311may include a plurality of processing elements3111,3112,3113, and3114, each of which processes one of the threads included in the task group322.

When the computation unit311is processing one task group322, i.e., executes the first task, the computation unit311may be requested to process another task group, task group323, i.e., to execute the second task, which is called preemption of the computation unit311. Preemption will be described below in detail with reference toFIG. 4.

FIG. 4is a diagram illustrating an example of preemption.

FIG. 4illustrates a process of processing a task by the computation unit311illustrated inFIG. 3. A first task410and a second task420illustrated inFIG. 4may correspond to the task groups322and323illustrated inFIG. 3.

During processing of the first task410by the computation unit311, a request for processing the second task420is received. For example, the computation unit311may start processing the first task410and receive the request for processing the second task420at t1. This is referred to as preemption of the computation unit311for processing of the second task420. At t1, the computation unit311stops processing the first task410and starts processing the second task420. Once the computation unit311finishes processing the second task420at t2, the computation unit311resumes processing the first task410.

The process of replacing the first task410with the second task420may be performed by context switching, draining, or flushing. For example, the computation unit311may process the second task420after storing all information (for example, registers) required for execution of the first task410in a memory at t1. In another example, the computation unit311may process the second task420after processing the first task410is completed. In further another example, at t1, the computation unit311may immediately replace the first task410with the second task420, without storing information required for execution of the first task410, and start processing the second task420. Further description of context switching, draining, and flushing is made with reference toFIGS. 5 to 7.

FIG. 5is a diagram illustrating examples of a preemption technique. In general, a GPU510may include a plurality of computation units511and512, each of which processes a task. The computation unit511cannot process two tasks at the same time. Thus, if the computation unit511receives a request for processing a second task (that is, a preemption request) while processing a first task, the computation unit511needs to replace the first task with the second task. In this case, various preemption techniques may be used.

The selector110selects a proper preemption technique based on a cost of each preemption techniques. The cost may be predicted based on a degree to which the first task has been executed until the request for processing the second task is received.

In performing preemption using flushing, a first task521is immediately replaced with a second task without storing information associated with the first task521upon receipt of a preemption request531. Thus, if the preemption request531is received at a point in time at which the computation unit511does not process the first task521much, i.e., most of the first task521remains to be processed, it may be desirable to select flushing.

In performing preemption using draining, a second task is executed after execution of a first task522is finished, in spite of receipt of a preemption request532. Thus, if the preemption request532is received at a point in time at which the computation unit511has processed most part of the first task522, i.e., little of the first task522remains to be processed, it may be desirable to select draining.

In performing preemption using context switching, upon receipt of a preemption request533, information associated with a first task523is stored and then the first task523is replaced with a second task. Context switching separately stores the information associated with the first task523, whereas flushing immediately replaces the first task521with the second task without separately storing the information associated with the first task521. Thus, if the point in time at which the preemption request533is received is not a desirable point in time to select either flushing or draining, it may be desirable to select context switching.

FIG. 6is a diagram illustrating an example of a point in time in which preemption techniques are selected.FIG. 6illustrates a cost of a preemption technique with respect to a degree to which a first task has been executed by a computation unit.

In flushing610, a cost increases as a degree to which a first task has been executed increases. According to the flushing610, if a preemption request is received, the first task is immediately replaced with a second task without storing information associated with the first task. The computation unit resumes executing the first task from the beginning after execution of the second task is finished. Thus, the flushing610is desirable to use if a preemption request is received at a point in time at which a degree to which the first task has been executed is low.

In draining630, a cost decreases as a degree to which the first task has been executed increases. According to the draining630, the second task is executed after execution of the first task is finished. Thus, the draining630is desirable to use if a preemption request is received at a point in time at which a degree to which the first task has been executed is high.

Context switching620has a constant cost regardless of a degree to which the first task has been executed. According to the context switching620, the second task is executed after information associated with the first task is stored, such that after execution of the second task is finished, the computation unit may resume executing the first task from the stopped part of the first task. Thus, the context switching620has a constant cost regardless of a degree to which the first task has been executed until receipt of the preemption request.

The selector110selects a preemption technique having the lowest cost at the time of receipt of the preemption request, based on the cost of each of the above-described three preemption techniques. Thus, the preemption technique selecting apparatus100may select the most proper preemption technique at the current point in time, and thus the computation unit may be preempted with low overhead.

Meanwhile, the preemption request may include a preemption latency limiting condition. Herein, the preemption latency limiting condition means a limiting condition for a latency time generated due to carrying out preemption. With reference toFIG. 7, the preemption latency limiting condition will be described.

FIG. 7is a diagram illustrating an example of a preemption latency limiting condition. In the description ofFIG. 7, it is assumed that a preemption request is received at t1and a preemption latency limiting condition indicates t2.

Draining710finishes processing a first task711in spite of receipt of the preemption request. Thus, a second task712is processed after processing of the first task711is finished. Assuming that both processing of the first task711and processing of the second task712are finished at t3, and t3is greater than t2, then the draining710fails to satisfy a preemption latency limiting condition. Hence, the selector110does not select the draining710as a preemption technique.

Context switching720stores information associated with a first task721upon receipt of the preemption request, and then executes a second task722. Assuming that at t4, the information associated with the first task721is stored and processing of the second task722is finished, and t4is greater than t2, then the context switching720fails to satisfy the preemption latency limiting condition. Hence, the selector110does not select the context switching720as a preemption technique.

Flushing730replaces a first task731with a second task732immediately upon receipt of the preemption request, without storing information associated with the first task731. If execution of the second task732is finished, execution of the first task731is resumed from the beginning. Assuming that processing of the second task732is finished at t5and t5is lesser than t2, then the flushing730satisfies the preemption latency limiting condition. Hence, the selector110may select the flushing730as a preemption technique.

Meanwhile, in flushing730, since execution of the first task731resumes from the beginning when execution of the second task732is finished, it is important to identify an idempotent region of the first task731. With reference toFIGS. 8 to 10, the meaning of idempotence and an idempotent region will be described.

FIGS. 8 and 9are diagrams illustrating examples of idempotence.FIG. 8shows processing results810,821,822,823, and824with respect to a task by a kernel. It can be seen fromFIG. 8that the task processing result810when the kernel operates once is identical to each of the task processing results821,822,823, and824when the kernel operates n times. In other words, the task processing result810when the kernel operates once is identical to the task processing result821when the kernel operates first among the n times. In addition, the task processing result821when the kernel operates first among the n times is identical to the task processing result822when the kernel operates second among the n times.

As such, regardless of whether the kernel operates once or n times, the identical result may be output whenever the kernel operates, which is called idempotence.

FIG. 9illustrates a result910of processing a first task by a computation unit and a result922of stopping a first task921processed previously upon receipt of a preemption request930and resuming processing of the first task.

If processing of a first task is stopped in an idempotent region of a first task upon receipt of the preemption request930, the result910of processing the first task without stopping processing the first task is identical to the result922of resuming processing the first task. However, if processing of the first task is stopped in a non-idempotent region of the first task upon receipt of the preemption request930, the result910of processing the first task without stopping processing the first task is different from the result922of resuming processing the first task. Thus, if preemption is carried out using flushing, processing of the first task needs to be stopped in the idempotent region of the first task.

FIG. 10is a diagram illustrating an example of an idempotent region included in a first task.

On the left side ofFIG. 10, an example of a first task made using CUDA is illustrated, and on the right side ofFIG. 10, an example of a first task made using OpenCL is illustrated.

An idempotent region and a non-idempotent region of a first task may be identified using an instruction included in the first task. For example, it is assumed that the first task involves, after reading data A stored in a memory, adding data B to the data A to generate data C, and updating the data A to the data C. If a computation unit stops processing the first task after updating the data A with the data C, and then resumes the first task from the beginning, then data read for the first time from the memory is not the data A, but the data C. Thus, a part of the first task, following an instruction for updating the data A with the data C, is a non-idempotent region.

‘atomicAdd( . . . )’ of a first task made using CUDA and ‘atomic_add( . . . )’ of the first task made using OpenCL are examples of an atomic operation910. A part of the first task preceding processing of the atomic operation910is an idempotent region930. Thus, in the idempotent region930, even if processing of the first task is stopped and then resumed, the processing result is identical to the result of finishing processing the first task without stopping processing the first task.

Meanwhile, a part of the first task, following processing of the atomic operation910, corresponds to non-idempotent regions940and950. Thus, if processing of the first task is stopped and then resumed in the non-idempotent regions940and950, the processing result is different from the result of finishing processing the first task without stopping processing the first task.

Referring back toFIG. 2, in operation220, the predictor120predicts a cost of each predetermined preemption technique based on a degree to which a first task has been executed until receipt of a preemption request. Herein, the cost may be predicted in terms of a throughput overhead and a preemption latency.

In other words, the predictor120predicts a throughput overhead cost and a preemption latency cost for context switching. The predictor120predicts a throughput overhead cost and a preemption latency cost for draining. The predictor120predicts a throughput overhead cost and a preemption latency cost for flushing.

The predictor120predicts the above-described cost by using the number of Single Instruction Multiple Data (SIMD) instructions that have already been executed among SIMD instructions included in the first task and an average Instructions-Per-Clock (IPC) of the first task.

The predictor120predicts a preemption latency of context switching by dividing a size of a context of the first task by a memory bandwidth of a computation unit. The context of the first task refers to information associated with the first task and may include registers of the first task. The predictor120may determine an average IPC of the first task as a throughput overhead of context switching, and may determine the average IPC of the first task to be twice a preemption latency of context switching. According to context switching, not only a process of storing the information associated with the first task, but also a process of reading the information associated with the first task is required. Thus, the throughput overhead of the context switching is twice the preemption latency of context switching.

The predictor120determines remaining cycles of the first task, i.e., cycles that have not yet been processed, as a preemption latency of draining. The predictor120computes a throughput overhead of draining by summing up a difference in the number of already-executed SIMD instructions of each task and a minimum value among the SIMD instructions, i.e., the already-executed SIMD instructions of each task. For example, it is assumed that the number of already-executed SIMD instructions of a third task is 10 and the number of already-executed SIMD instructions of a fourth task is 13. Then, the predictor120sums up a difference between 10 and 13 and 10, thus computing a throughput overhead of draining.

The predictor120determines a preemption latency of flushing as 0. Flushing immediately replaces a first task with a second task upon receipt of a preemption request. Thus, unlike context switching, flushing does not store information associated with the first task, such that the preemption latency of flushing may be determined as 0. The predictor120may determine the number of already-executed SIMD instructions as a throughput overhead of flushing. For example, it is assumed that the number of already-executed SIMD instructions of the third task is 10 and the number of already-executed SIMD instructions of the fourth task is 13. In this case, the predictor120may compute the throughput overhead of flushing by summing up 10 and 13.

The predictor120receives information needed for cost computation from each of the computation units. For example, each computation unit may transmit information such as a processing-finished task, SIMD instruction progress statistics for each task, a start point of a non-idempotent region, and the like, to the predictor120. The predictor120may predict a cost of each preemption technique by using information transmitted from the computation units.

In operation230, the selector110selects one of the predetermined preemption techniques based on the predicted cost.

For example, the selector110selects a preemption technique corresponding to the smallest throughput overhead, by taking into account costs predicted for the preemption techniques. In another example, the selector110may select a preemption technique corresponding to the smallest preemption latency, by taking into account the cost of each preemption technique. In further another example, the selector110receives a user input of selecting one of a throughput overhead and a preemption latency and selects a preemption technique having the lowest cost corresponding to the user input. In other words, if the user selects the throughput overhead, the selector110selects a preemption technique having the smallest throughput overhead among the preemption techniques.

The selector110may further take into account whether a preemption latency limiting condition or a throughput overhead limiting condition is satisfied, when selecting one of the preemption techniques.

FIG. 11is a diagram illustrating another example of a preemption technique selecting apparatus101.

A selector111, a predictor121, and a scheduler130illustrated inFIG. 11may correspond to a single processor or a plurality of processors. Each of the processors may be implemented with an array of multiple logic gates, or a combination of a general-purpose microprocessor and a memory having stored therein a program to be executed by the microprocessor. Also, it would be understood by those of ordinary skill in the art that the processor may be implemented with other types of hardware.

The selector111and the predictor121may correspond to the selector110and the predictor120described with reference toFIGS. 1 through 10. The above descriptions of selector110and the predictor120is also applicable to the selector111and the predictor121ofFIG. 11, and is incorporated herein by reference. Thus, the above description may not be repeated here.

The scheduler130assigns a task to each computation unit according to a preemption technique selected by the selector111. For example, assuming that the selector111selects flushing, the scheduler130requests each of the computation units to stop processing the current task and assigns a new task to each computation unit.

FIGS. 12 and 13are diagrams illustrating examples of a preemption technique selecting method. The operations inFIGS. 12 and 13may be performed in the sequence and manner as shown, although the order of some operations may be changed or some of the operations omitted without departing from the spirit and scope of the illustrative examples described. Many of the operations shown inFIGS. 12 and 13may be performed in parallel or concurrently. The above descriptions ofFIGS. 1-11, is also applicable toFIGS. 12 and 13, and is incorporated herein by reference. Thus, the above description may not be repeated here.

Referring toFIGS. 12 and 13, the preemption technique selecting method includes operations processed in time series by the preemption technique selecting apparatuses100or101. Thus, the foregoing description of the preemption technique selecting apparatuses100and101illustrated inFIGS. 1 and 11may also be applied to the preemption technique selecting method ofFIGS. 12 and 13, and is incorporated herein by reference.

FIG. 12illustrates an example in which the selectors110or111select a preemption technique based on a throughput overhead.FIG. 13illustrates an example in which the selectors110or111select a preemption technique based on a preemption latency.

First, referring toFIG. 12, in operation1210, the selectors110or111sort a cost of each preemption technique based on a throughput overhead. In other words, the selectors110or111compare throughput overheads generated in computation units according to context switching, draining, and flushing. The selectors110or111sort context switching, draining, and flushing in the order of throughput overheads generated by the computation units.

In operation1220, the selectors110or111determine whether all computation units have been searched for preemption. In other words, the selectors110or111determine whether carrying out preemption is possible for all computation units. If carrying out preemption is possible for all computation units, the method is terminated and preemption is carried out.

In operation1230, the selectors110or111select a computation unit having the smallest throughput overhead as a preemption candidate computation unit.

In operation1240, the selectors110or111determine whether the computation unit selected as the preemption candidate satisfies a preemption latency limiting condition. For example, it is assumed that a preemption technique having the largest throughput overhead is context switching, a preemption technique having the next largest throughput overhead is draining, and a preemption technique having the smallest throughput overhead is flushing. The selectors110or111determine whether the preemption latency limiting condition is satisfied, when preemption is carried out for the computation unit selected as the preemption candidate according to context switching. If preemption latency limiting condition is not satisfied, then the selectors110or111determine whether the preemption latency limiting condition is satisfied when preemption is carried out according to draining. If the preemption latency limiting condition is not satisfied again, the selectors110or111determine whether the preemption latency limiting condition is satisfied when preemption is carried out according to flushing.

If all the preemption techniques fail to satisfy the preemption latency limiting condition for the computation unit selected as the preemption candidate, then operation1220is performed. Otherwise, operation1250is performed.

In operation1250, the selectors110or111determine whether the computation unit selected as the preemption candidate has already been selected as a computation unit to be preempted. If the computation unit selected as the preemption candidate has already been selected as the computation unit to be preempted, then operation1220is performed. Otherwise, operation1260is performed.

In operation1260, the selectors110or111select the computation unit selected as the preemption candidate as the computation unit to be preempted. The selectors110or111notify the scheduler130of the selected computation unit.

Referring toFIG. 13, in operation1310, the selectors110or111sort costs of respective preemption techniques based on their preemption latencies. In other words, the selectors110or111compare the preemption latencies to be generated by the computation units with each other according to context switching, draining, and flushing. The selectors110or111sort context switching, draining, and flushing in the order of the preemption latencies to be generated in the computation units.

In operation1320, the selectors110or111determine whether all computation units have been searched for preemption. In other words, the selectors110or111determine whether carrying out preemption is possible for all the computation units. If carrying out preemption is possible for all the computation units, the method is terminated and preemption is carried out.

In operation1330, the selectors110or111select a computation unit having the smallest preemption latency as a preemption candidate computation unit.

In operation1340, the selectors110or111determine whether the computation unit selected as the preemption candidate satisfies a throughput overhead limiting condition. For example, it is assumed that a preemption technique having the largest preemption latency is context switching, a preemption technique having the next largest preemption latency is draining, and a preemption technique having the smallest preemption latency is flushing. The selectors110or111determine whether the throughput overhead limiting condition is satisfied, when preemption is carried out for the computation unit selected as the preemption candidate according to context switching. If the throughput overhead limiting condition is not satisfied, the selectors110or111determine whether the throughput overhead limiting condition is satisfied, when preemption is carried out for the computation unit selected as the preemption candidate according to draining. If the throughput overhead limiting condition is not satisfied, the selectors110or111determine whether the throughput overhead limiting condition is satisfied, when preemption is carried out for the computation unit selected as the preemption candidate according to flushing.

If all the preemption techniques fail to satisfy the throughput overhead limiting condition for the computation unit selected as the preemption candidate, operation1320is performed. Otherwise, operation1350is performed.

In operation1350, the selectors110or111determine whether the computation unit selected as the preemption candidate has already been selected as a computation unit to be preempted. If the computation unit selected as the preemption candidate has already been selected as a computation unit to be preempted, operation1320is performed. Otherwise, operation1360is performed.

In operation1360, the selectors110or111select the computation unit selected as the preemption candidate as the computation unit to be preempted. The selectors110or111notify the scheduler130of the selected computation unit.

FIG. 14is a diagram illustrating an apparatus including an apparatus for selecting a preemption technique.

Referring toFIG. 14, the system may include a preemption technique selecting apparatus102and a computation device1400. Herein, the computation device1400may include a plurality of computation units1410,1420, and1430.

Operations of the selector112, the predictor122, and the scheduler131included in the preemption technique selecting apparatus102illustrated inFIG. 14have already been described with reference toFIGS. 1 through 13. The above descriptions ofFIGS. 1 through 13, is also applicable toFIG. 14, and is incorporated herein by reference. Thus, the above description may not be repeated here.

The scheduler131assigns a second task to computation units to be preempted according to a preemption technique selected by the selector112. The computation units to be preempted may be all or some of the computation units1410,1420, and1430included in the computation device1400.

As described above, the preemption technique selecting apparatuses100,101, and102may select a proper preemption technique according to the first task currently being processed in the computation unit. Thus, the cost required for preemptive multitasking may be minimized.

Moreover, the preemption technique selecting apparatuses100,101, and102may select a preemption technique, preferentially taking account of a throughput overhead or a preemption latency according to the characteristics of a task. Hence, the preemption technique optimized for a type of the task may be selected.

The methods illustrated inFIGS. 12-13that perform the operations described herein with respect toFIGS. 12-13are performed by a processor or a computer as described above executing instructions or software to perform the operations described herein.