JP7548003B2 - Execution scheduling determination method and execution scheduling determination program - Google Patents

Description

The present invention relates to an execution scheduling determination method and an execution scheduling determination program.

In recent years, FPGAs (Field Programmable Gate Arrays) have become known for use in computational processing, such as image processing and AI (Artificial Intelligence). FPGAs are devices that have built-in logic circuits and can be rewritten any number of times by writing firmware written in a dedicated hardware language. When a computation is interrupted, FPGAs discard the results of the computation up to that point, meaning that the computation cannot be resumed from the middle.

Moreover, it takes time to write firmware to an FPGA. A different application is connected to each FPGA, so that the firmware cannot be rewritten by other applications. Therefore, the number of FPGAs increases depending on the type of application.

Japanese Patent Application Publication No. 8-55036

However, because FPGAs are expensive devices, there is a demand to reduce the number of FPGAs. Therefore, there is a demand for FPGAs that can process multiple different applications with one FPGA. Furthermore, even when multiple different applications are processed with a single FPGA, there is a demand for a scheduling method that can process as many jobs as possible by efficiently executing the execution requests (jobs) of each application.

In one aspect, the objective is to provide an execution scheduling decision method and an execution scheduling decision program that can process as many jobs as possible.

In one aspect of the execution schedule determination method, when an active job and a queued job do not satisfy a set timeout condition, a process is executed to calculate the number of jobs that can be processed when the active job is stopped and rescheduled, and when the rescheduling is not executed. Furthermore, the method executes a process to execute the rescheduling when it is determined that the number of jobs that can be processed is greater when the rescheduling is executed.

On the one hand, it can handle as many jobs as possible.

FIG. 1 is an explanatory diagram showing an example of a computer according to the present embodiment. FIG. 2 is an explanatory diagram illustrating an example of a functional configuration within the CPU. FIG. 3 is an explanatory diagram showing definitions of terms used for jobs. FIG. 4 is an explanatory diagram illustrating an example of a job table. FIG. 5 is an explanatory diagram illustrating an example of the application information table. FIG. 6 is an explanatory diagram illustrating an example of an execution order list. FIG. 7A is an explanatory diagram showing an example of a job table and an application information table used when rescheduling is executed. FIG. 7B is an explanatory diagram showing an example of an execution order when rescheduling is executed (basic logic). FIG. 7C is an explanatory diagram showing an example of the execution order when the timeout of jobs C-1 and C-2 is determined. FIG. 7D is an explanatory diagram showing an example of the execution order when job A-1 is stopped. FIG. 8 is a flowchart showing an example of the processing operation of the CPU related to the queue management processing. FIG. 9 is a flowchart showing an example of a processing operation of the CPU related to the execution process. FIG. 10 is a flowchart showing an example of a processing operation of the CPU relating to the queuing process. FIG. 11 is a flowchart showing an example of a processing operation of the CPU related to the timeout adjustment processing. FIG. 12 is a flowchart showing an example of a processing operation of the CPU relating to the limit time processing. FIG. 13 is a flowchart showing an example of the processing operation of the CPU relating to the estimated end time processing. FIG. 14 is a flowchart showing an example of a processing operation of the CPU related to new job input processing. FIG. 15 is a block diagram illustrating an example of a computer that executes an execution scheduling determination program. FIG. 16 is an explanatory diagram showing an example of a rescheduling method according to the comparative example. FIG. 17 is an explanatory diagram illustrating an example of an execution sequence in the comparative example. FIG. 18 is an explanatory diagram showing an example of an execution order when rescheduling is executed in the comparative example. FIG. 19 is an explanatory diagram illustrating an example of a problem with the execution order when rescheduling is performed in the comparative example.

Below, examples of the execution scheduling determination method and the like disclosed in the present application will be described in detail with reference to the drawings. Note that the disclosed technology is not limited to each example. In addition, each example shown below may be appropriately combined as long as no contradiction occurs.

Comparative Example

First, before describing the execution scheduling determination method disclosed in the present application, an example of a rescheduling method of a comparative example will be described. FIG. 16 is an explanatory diagram showing an example of a rescheduling method of a comparative example. The FPGA 203 shown in FIG. 16 makes the firmware 202 rewritable by a plurality of types of applications 201, sets up the firmware 202 for each application 201, and executes the job of the application 201 after the setup. When the FPGA 203 detects an execution request (job A-1) of the application 201A, it sets up the firmware 202A corresponding to the application 201A. After setting up the firmware 202A, the FPGA 203 executes the job A-1. Also, when the FPGA 203 detects an execution request (job B-1) of the application 201B, it sets up the firmware 202B corresponding to the application 201B. After setting up the firmware 202B, the FPGA 203 executes the job B-1. Furthermore, when the FPGA 203 detects an execution request (job C-1) for application 201C, it sets up firmware 202C that corresponds to application 201C. After setting up firmware 202C, the FPGA 203 executes job C-1.

However, FPGA 203 cannot recognize the timing at which an execution request (job) for application 201 will arrive. FIG. 17 is an explanatory diagram showing an example of an execution order in a comparative example. Here, assume that, for example, job A-1, job B-1, job C-1, and job A-2 are input to FPGA 203 as execution requests for application 201 in this order.

When job B-1 is submitted from application 201B while job A-1 is being executed, FPGA 203 accumulates an execution request for job B-1 in the queue. Furthermore, when job C-1 from application 201C and job A-2 from application 201A are submitted to FPGA 203 while job A-1 is being executed, FPGA 203 accumulates execution requests for jobs C-1 and A-2 in the queue. FPGA 203 then accumulates the jobs being accumulated in the queue in the order of jobs A-1 → B-1 → C-1 → A-2, and executes the accumulated jobs sequentially.

FIG. 18 is an explanatory diagram showing an example of the execution order when rescheduling is executed in a comparative example. However, the FPGA 203 can reduce the overlapping setup time for each job by continuously executing jobs of the same type of application 201. In other words, the FPGA 203 rearranges the execution order of jobs stored in the queue so that jobs of the same type of application 201 are consecutive. For example, in order to continuously execute jobs of the same type of application 201A, the FPGA 203 rearranges the execution order of the stored jobs A-1 → B-1 → C-1 → A-2 to jobs A-1 → A-2 → B-1 → C-1. As a result, the FPGA 203 eliminates the need to set up job A-2 when setting up job A-1, thereby reducing the setup time for job A-2 and enabling the jobs to be implemented efficiently.

FIG. 19 is an explanatory diagram showing an example of an issue with the execution order when rescheduling is performed in the comparative example. However, when the FPGA 203 rearranges the job execution order so that jobs of the same type of application 201 are consecutive, the execution timing of jobs of other types of applications 201 is delayed. For example, when the FPGA 203 rearranges jobs A-1 → B-1 → C-1 → A-2 → A-3 to jobs A-1 → A-2 → A-3 → B-1 → C-1, each job has a timeout time, so there is a risk that each job will time out due to the delay in execution timing. Moreover, when the FPGA 203 interrupts a job being executed, it will discard the intermediate results of the job being executed. As a result, the execution time of the job up to that point will be wasted. Therefore, there is a trade-off between improving job throughput and ensuring the timeout time of the job.

Since FPGA 203 cannot interrupt job processing, it may be better to reschedule the execution order even if it means canceling the currently running job, if it maximizes the number of jobs that can be processed. Furthermore, since FPGA 203 requires time to set up firmware for each application, it is desirable to schedule jobs of the same application so that they are consecutively grouped into one job group. Therefore, even if consecutive jobs of the same application cause delays to other jobs, canceling the currently running job and postponing the execution order of other jobs in the job group that includes that job may increase the overall number of jobs that can be processed.

Therefore, there is a demand for the rescheduling execution method of this embodiment, which increases the number of jobs per unit time as much as possible while taking into account the timeout period of each job, and executes jobs of the same type of application continuously to improve job execution throughput.

Figure 1 is an explanatory diagram showing an example of a computer 1 of this embodiment. The computer 1 shown in Figure 1 has a container 2, an FPGA 3, a CPU 4, and a memory 5. The container 2 is a virtual machine that executes multiple types of applications. The FPGA 3 is a device that executes jobs, which are requests to execute applications in the container 2. The CPU 4 controls the entire computer 1. The memory 5 stores various information. The memory 5 has a job table 11, an application information table 12, and an execution order list 13, which will be described later.

The CPU 4 provides a virtual machine that is the execution environment of the container 2, and sets up firmware for each application corresponding to the job submitted to the container 2 in the FPGA 3. After setting up the firmware in the FPGA 3, the CPU 4 causes the FPGA 3 to execute the submitted job. The CPU 4 also has the functions of a queue management unit 4A and an execution unit 4B.

Figure 2 is an explanatory diagram showing an example of the functional configuration within the CPU 4. The queue management unit 4A within the CPU 4 shown in Figure 2 executes rescheduling of each job when it is determined that the currently running job and the queued jobs do not satisfy the set timeout condition due to a delay in the currently running job. Furthermore, the queue management unit 4A calculates the number of jobs that can be processed when the currently running job is stopped and rescheduling is executed, and the number of jobs that can be processed when rescheduling is not executed. The execution unit 4B executes the rescheduling when it is determined that the number of jobs is greater when the currently running job is stopped and rescheduling is executed.

The queue management unit 4A in the CPU 4 shown in FIG. 2 has a job reception unit 21, a queuing unit 22, and a timeout adjustment unit 23. The job reception unit 21 receives jobs issued from an application in the container 2. The queuing unit 22 accumulates the jobs received by the job reception unit 21 in the execution order list 13. Furthermore, the queuing unit 22 registers job information for each received job in the job table 11. The timeout adjustment unit 23 determines whether the job being executed and the queued jobs have satisfied the set timeout condition due to the delay of the job being executed. When it is determined that the set timeout condition is not satisfied, the timeout adjustment unit 23 calculates the number of jobs that can be processed when the job being executed is stopped and rescheduled and the number of jobs that can be processed when rescheduling is not executed. Furthermore, the timeout adjustment unit 23 compares the number of jobs when rescheduling is executed with the number of jobs when rescheduling is not executed, and determines whether the number of jobs when rescheduling is executed is greater.

The execution unit 4B in the CPU 4 has a container control unit 31, an FPGA control unit 32, a time information registration unit 33, an application information calculation unit 34, a table writing unit 35, and an abort processing unit 36. The container control unit 31 controls the container 2. The FPGA control unit 32 controls the FPGA 3 using a device plug-in. The time information registration unit 33 registers job execution time information for each application. The application information calculation unit 34 calculates job execution time information for each application. The job execution time information is, for example, the job execution average time, job execution distribution time, and setup average time to be registered in the application information table 12. The table writing unit 35 registers the job execution time information for each application in the application information table 12. The abort processing unit 36 is a processing unit that aborts a job being executed in response to a job abort request from the timeout adjustment unit 23.

Figure 3 is an explanatory diagram showing definitions of the terms used for jobs. The job for each application shown in Figure 3 has a setup command and an execution command. The setup command is a command that sets logic corresponding to the application of the job in the firmware in FPGA 3. The execution command is a command that causes FPGA 3 to execute the job after the firmware has been set up.

The submission time is the time when the job receiving unit 21 in the CPU 4 accepts a job from an application in the container 2. The timeout time is the time obtained by adding the timeout time (timeout condition) for the job to the timeout time for the job. The timeout condition is the timeout time set for each job from job submission to job completion. The setup time is the time required from the start of setup to the completion of setup for the firmware of the application corresponding to the job. The job execution time is the time obtained by adding the setup time for each job and the processing time for the job's execution command, and is the time required from the start of job setup to the completion of the execution command. The limit time is the scheduled job start time at the limit at which the job can be executed, which is the timeout time for the job minus the average job execution time.

FIG. 4 is an explanatory diagram showing an example of the job table 11. The job table 111 shown in FIG. 4 manages job information for each job identification information 11A that identifies a job. The job information has application identification information 11B, submission time 11C, timeout condition 11D, job start time 11E, timeout time 11F, and limit time 11G. Application identification information 11B is information that identifies the application that executes the job. Submission time 11C is the time when the job is submitted. Timeout condition 11D is a condition for determining that the job timeout is satisfied, for example, a timeout time. Job start time 11E is the time when the job is started. Timeout time 11F is the time obtained by adding the timeout time of the timeout condition to the submission time of the job. Limit time 11G corresponds to the time obtained by subtracting the average job execution time from the timeout time of the job, and is the scheduled job start time at the limit at which the job can be executed.

Figure 5 is an explanatory diagram showing an example of the app information table 12. The app information table 12 shown in Figure 5 is a table that manages job execution time information for each app identification information 12A. The job execution time information has a job execution average time 12B, a job execution distribution time 12C, and a setup average time 12D. The job execution average time 12B is the cumulative average time of job execution time for each app. The job execution distribution time 12C is the distribution time equivalent to one standard deviation required to process a job execution command for each app. The setup average time 12D is the cumulative average time of job setup time for each app.

Figure 6 is an explanatory diagram showing an example of the execution order list 13. The execution order list 13 shown in Figure 6 is a list that manages the execution order of jobs. The execution order list 13 shown in Figure 6 manages the execution order of jobs A-1 → A-2 → B-1 → B-2 → C-1 → C-2.

Next, the operation of the computer 1 of this embodiment will be described. The job reception unit 21 in the computer 1 receives jobs from the application in the container 2. The queuing unit 22 registers job information related to the received jobs in the job table 11. The queuing unit 22 sequentially accumulates the jobs in the execution order list 13 in the order of reception. Next, the timeout adjustment unit 23 extracts the limit time and timeout time for each job from the job information in the job table 11. The timeout adjustment unit 23 sorts the execution order of the jobs in the execution order list 13 so that the timeout condition of each job is satisfied and the number of jobs is large based on the limit time, timeout time, and current time for each extracted job. The timeout adjustment unit 23 compares the number of jobs when rescheduling is performed to cancel the job being executed with the number of jobs when rescheduling is performed. Furthermore, if the number of jobs when rescheduling is performed to cancel the job being executed is larger, the timeout adjustment unit 23 notifies the cancellation processing unit 36 of a cancellation request to cancel the job being executed. When the stop processing unit 36 detects a stop request, it sets the FPGA control unit 32 to stop the job being executed. The FPGA control unit 32 causes the FPGA 3 to execute each job based on the execution order in the execution order list 13.

Figure 7A is an explanatory diagram showing an example of the job table 11 and the application information table 12 used when performing rescheduling. It is assumed that the CPU 4 has registered the application information table 12 in advance.

The application information table 12 shown in FIG. 7A manages the job execution average time 12B, job execution distribution time 12C, and setup average time 12D for each application identification information 12A. The CPU 4 can also calculate the execution command average time of the execution command based on (job execution average time - setup average time) for each application identification information. For application A, the job execution average time 12B is 10 seconds, the job execution distribution time 12C is 2 seconds, the setup average time 12D is 8 seconds, and the execution command average time is 2 seconds. For application B, the job execution average time 12B is 2 seconds, the job execution distribution time 12C is 1 second, the setup average time 12D is 1 second, and the execution command average time is 1 second. For application C, the job execution average time 12B is 3 seconds, the job execution distribution time 12C is 1 second, the setup average time 12D is 2 seconds, and the execution command average time is 1 second.

For example, let us say that the CPU 4 accepts job submissions from the container 2 in the order of jobs A-1 → B-1 → C-1 → A-2 → B-2 → C-2. The CPU 4 registers the application identification information 11B, submission time 11C, timeout condition 11D, job start time 11E, timeout time 11F, and limit time 11G as job information for each job identification information 11A in the job table 11. Note that the timeout condition differs for each job.

For example, when looking at job A-1, job A-1 registers app A as app identification information 11B, 14:18:00 as input time 11C, and 30 seconds as timeout condition 11D in the job table 11. It also registers 14:18:01 as job start time 11E and 14:18:30 (= input time 14:18:00 + timeout condition 30 seconds) as timeout time 11F in the job table 11. It registers 14:18:20 (= timeout time 14:18:30 - average job execution time 10 seconds) as limit time 11G in the job table 11.

Furthermore, for example, when looking at job B-1, job B-1 registers in the job table 11 app B as app identification information 11B, 14:18:02 as input time 11C, and 15 seconds as timeout condition 11D. As job start time 11E, "-" is registered in the job table 11 since it is before execution, and as timeout time 11F, 14:18:17 (= input time 14:18:02 + timeout condition 15 seconds) is registered in the job table 11. As limit time 11G, 14:18:15 (= timeout time 14:18:17 - average job execution time 2 seconds) is registered in the job table 11.

Furthermore, for example, when looking at job C-2, job C-2 registers in the job table 11 app C as app identification information 11B, 14:18:11 as input time 11C, and 12 seconds as timeout condition 11D. As job start time 11E, "-" is registered in the job table 11 since it is before execution, and as timeout time 11F, 14:18:23 (= input time 14:18:11 + timeout condition 12 seconds) is registered in the job table 11. As limit time 11G, 14:18:20 (= timeout time 14:18:23 - average job execution time 3 seconds) is registered in the job table 11.

Figure 7B is an explanatory diagram showing an example of the execution order when rescheduling is performed (basic logic). The CPU 4 performs rescheduling to rearrange the execution order of jobs A-1 → B-1 → C-1 → A-2 → B-2 → C-2 to the execution order of jobs A-1 → A-2 → B-1 → B-2 → C-1 → C-2, based on the basic logic in which the input order is earlier and the same application is consecutive. The job execution time of jobs A-1 and A-2 is 12 seconds, calculated as the average setup time of job A-1 (8 seconds) + the average execution command time of job A-1 (2 seconds) + the average execution command time of job A-2 (2 seconds). The job execution time of jobs B-1 and B-2 is 3 seconds, calculated as the average setup time of job B-1 (1 second) + the average execution command time of job B-1 (1 second) + the average execution command time of job B-2 (1 second). The job execution time for jobs C-1 and C-2 is 3 seconds, calculated as the average setup time for job C-1 (2 seconds) + the average execution command time for job C-1 (1 second) + the average execution command time for job C-2 (1 second).

First, we will explain how to determine this basic logic. The scheduled job end time of job A-1 is (job start time 14:18:01 + average job execution time 10 seconds) = 14:18:11. The timeout adjustment unit 23 can determine that the timeout condition for job A-1 is met because the scheduled job end time of job A-1 is before the timeout time of job A-1 (14:18:30).

The scheduled job end time of job A-1 is the job start time of job A-2. The timeout adjustment unit 23 determines that the job start time of job A-2, 14:18:11, is earlier than the limit time of job A-2, 14:18:21. The scheduled job end time of job A-2 is (job start time 14:18:11 + average execution command time 2 seconds) = 14:18:13. The timeout adjustment unit 23 can determine that the timeout condition of job A-2 is met because the scheduled job end time of job A-2 is before the timeout time of job A-2 (14:18:31). As a result, the timeout adjustment unit 23 can determine that the execution order of jobs A-1 → A-2 meets the timeout condition.

Furthermore, the scheduled job end time of job A-2 becomes the job start time of job B-1. The timeout adjustment unit 23 determines that the job start time of job B-1, 14:18:13, is earlier than the limit time of job B-1, 14:18:15. The scheduled job end time of job B-1 is (job start time 14:18:13 + average job execution time 2 seconds) = 14:18:15. The timeout adjustment unit 23 can determine that the timeout condition of job B-1 is met because the scheduled job end time of job B-1 is before the timeout time of job B-1 (14:18:17). As a result, the timeout adjustment unit 23 can determine that the execution order of jobs A-1 → A-2 → B-1 meets the timeout condition.

Furthermore, the scheduled job end time of job B-1 is the job start time of job B-2. The timeout adjustment unit 23 determines that the job start time of job B-2, 14:18:15, is earlier than the limit time of job B-2, 14:18:17. The scheduled job end time of job B-2 is (job start time 14:18:15 + average execution command time 1 second) = 14:18:16. The timeout adjustment unit 23 determines that the timeout condition of job B-2 is met because the scheduled job end time of job B-2 is before the timeout time of job B-2 (14:18:19). As a result, the timeout adjustment unit 23 determines that the execution order of jobs A-1 → A-2 → B-1 → B-2 meets the timeout condition.

Furthermore, the scheduled job end time of job B-2 is the job start time of job C-1. The timeout adjustment unit 23 determines that the job start time of job C-1, 14:18:16, is earlier than the limit time of job C-1, 14:18:17. The scheduled job end time of job C-1 is (job start time 14:18:16 + average job execution time 3 seconds) = 14:18:19. The timeout adjustment unit 23 determines that the timeout condition of job C-1 is met because the scheduled job end time of job C-1 is before the timeout time of job C-1 (14:18:20). As a result, the timeout adjustment unit 23 determines that the execution order of jobs A-1 → A-2 → B-1 → B-2 → C-1 meets the timeout condition.

Furthermore, the scheduled job end time of job C-2 becomes the job start time of job C-2. The timeout adjustment unit 23 determines that the job start time of job C-2, 14:18:19, is earlier than the limit time of job C-2, 14:18:20. The scheduled job end time of job C-2 is (job start time 14:18:19 + average execution command time 1 second) = 14:18:20. The timeout adjustment unit 23 determines that the timeout condition of job C-2 is met because the scheduled job end time of job C-2 is before the timeout time of job C-2 (14:18:23). As a result, the timeout adjustment unit 23 updates the execution order list 13 to the execution order of jobs A-1 → A-2 → B-1 → B-2 → C-1 → C-2, which satisfies the timeout condition.

Figure 7C is an explanatory diagram showing an example of the execution order when jobs C-1 and C-2 are judged to have timed out. When job A-1 is being executed in the execution order of jobs A-1 → A-2 → B-1 → B-2 → C-1 → C-2, CPU 4 assumes that the job execution time of job A-1 will be extended by one standard deviation if it does not end within the average job execution time. Note that one standard deviation is different for each application and is, for example, the job execution distribution time. CPU 4 calculates the number of jobs that can be processed when rescheduling is performed to continue the execution of job A-1.

The contents of this calculation logic will be explained below. For example, the scheduled job end time of job A-1 is (job start time 14:18:01 + average job execution time 10 seconds + job execution distribution time 2 seconds) = 14:18:13. The timeout adjustment unit 23 can determine that the timeout condition for job A-1 is met because the scheduled job end time of job A-1 is before the timeout time of job A-1 (14:18:30).

The scheduled job end time of job A-1 is the job start time of job A-2. The timeout adjustment unit 23 determines that the job start time of job A-2, 14:18:13, is earlier than the limit time of job A-2, 14:18:23. The scheduled job end time of job A-2 is (job start time 14:18:13 + average execution command time 2 seconds) = 14:18:15. The timeout adjustment unit 23 can determine that the timeout condition of job A-2 is met because the scheduled job end time of job A-2 is before the timeout time of job A-2 (14:18:31). As a result, the timeout adjustment unit 23 can determine that the execution order of jobs A-1 → A-2 meets the timeout condition.

Furthermore, the scheduled job end time of job A-2 becomes the job start time of job B-1. The timeout adjustment unit 23 determines that the job start time of job B-1, 14:18:15, is the same as the limit time of job B-1, 14:18:15. The scheduled job end time of job B-1 is (job start time 14:18:15 + average job execution time 2 seconds) = 14:18:17. The timeout adjustment unit 23 can determine that the timeout condition of job B-1 is met because the scheduled job end time of job B-1 is before the timeout time of job B-1 (14:18:17). As a result, the timeout adjustment unit 23 can determine that the execution order of jobs A-1 → A-2 → B-1 meets the timeout condition.

Furthermore, the scheduled job end time of job B-1 becomes the job start time of job B-2. The timeout adjustment unit 23 determines that the job start time of job B-2, 14:18:17, is the same as the limit time of job B-2, 14:18:17. The scheduled job end time of job B-2 is (job start time 14:18:17 + average execution command time 1 second) = 14:18:18. The timeout adjustment unit 23 determines that the timeout condition of job B-2 is met because the scheduled job end time of job B-2 is before the timeout time of job B-2 (14:18:19). As a result, the timeout adjustment unit 23 determines that the execution order of jobs A-1 → A-2 → B-1 → B-2 meets the timeout condition.

Furthermore, the scheduled job end time of job B-2 becomes the job start time of job C-1. The timeout adjustment unit 23 determines that the job start time of job C-1, 14:18:18, is later than the limit time of job C-1, 14:18:17. The scheduled job end time of job C-1 is (job start time 14:18:18 + average job execution time 3 seconds) = 14:18:21. The timeout adjustment unit 23 determines that the scheduled job end time of job C-1 exceeds the timeout time of job C-1 (14:18:20), and therefore does not satisfy the timeout condition of job C-1. As a result, the execution order of jobs A-1 → A-2 → B-1 → B-2 → C-1 is invalid. Therefore, since jobs C-1 and C-2 do not satisfy the timeout condition, the timeout adjustment unit 23 can determine that the execution order of jobs A-1 → A-2 → B-1 → B-2 satisfies the timeout condition. Therefore, the number of jobs that can be processed in the job execution order if the currently running job is continued will be "4".

Figure 7D is an explanatory diagram showing an example of the execution order when job A-1 is stopped. When job A-1 is being executed in the execution order of jobs A-1 → A-2 → B-1 → B-2 → C-1 → C-2, CPU 4 assumes that the job execution time of job A-1 is extended by one standard deviation if it does not end within the average job execution time. CPU 4 will calculate the number of jobs that can be processed when rescheduling is performed to stop job A-1 that is currently being executed.

When CPU 4 cancels the execution of job A-1 in the execution order of jobs A-1 → B-1 → C-1 → A-2 → B-2 → C-2, it rearranges the execution order of the basic logic in which the jobs were submitted earlier and in which the same application is consecutive. CPU 4 calculates the number of jobs that can be processed when rescheduling is performed to rearrange the execution order of the basic logic to the execution order of jobs B-1 → B-2 → C-1 → C-2 → A-2.

The contents of the calculation logic will be explained. The job end time of job A-1 is determined by canceling job A-1 within the average job execution time and at the latest being (job start time 14:18:01 + average job execution time 10 seconds) = 14:18:11. The job end time of job A-1 is the job start time of job B-1. The timeout adjustment unit 23 determines that the job start time of job B-1 is 14:18:11, which is earlier than the limit time of job B-1, 14:18:15. The scheduled job end time of job B-1 is (job start time 14:18:11 + average job execution time 2 seconds) = 14:18:13. The timeout adjustment unit 23 determines that the scheduled job end time of job B-1 is before the timeout time of job B-1 (14:18:17), and therefore the timeout condition of job B-1 is satisfied.

Furthermore, the scheduled job end time of job B-1 is the job start time of job B-2. The timeout adjustment unit 23 determines that the job start time of job B-2, 14:18:13, is earlier than the limit time of job B-2, 14:18:17. The scheduled job end time of job B-2 is (job start time 14:18:13 + average execution command time 1 second) = 14:18:14. The timeout adjustment unit 23 determines that the timeout condition of job B-2 is met because the scheduled job end time of job B-2 is before the timeout time of job B-2 (14:18:19). As a result, it can be determined that the execution order of jobs B-1 → B-2 meets the timeout condition.

Furthermore, the scheduled job end time of job B-2 is the job start time of job C-1. The timeout adjustment unit 23 determines that the job start time of job C-1, 14:18:14, is earlier than the limit time of job C-1, 14:18:17. The scheduled job end time of job C-1 is (job start time 14:18:14 + average job execution time 3 seconds) = 14:18:17. The timeout adjustment unit 23 determines that the timeout condition of job C-1 is met because the scheduled job end time of job C-1 is before the timeout time of job C-1 (14:18:20). As a result, it can be determined that the execution order of jobs B-1 → B-2 → C-1 meets the timeout condition.

Furthermore, the scheduled job end time of job C-1 is the job start time of job C-2. The timeout adjustment unit 23 determines that the job start time of job C-2, 14:18:17, is earlier than the limit time of job C-2, 14:18:20. The scheduled job end time of job C-2 is (job start time 14:18:17 + average execution command time 1 second) = 14:18:18. The timeout adjustment unit 23 determines that the timeout condition of job C-2 is met because the scheduled job end time of job C-2 is before the timeout time of job C-2 (14:18:23). As a result, it can be determined that the execution order of jobs B-1 → B-2 → C-1 → C-2 meets the timeout condition.

Furthermore, the scheduled job end time of job C-2 is the job start time of job A-2. The timeout adjustment unit 23 determines that the job start time of job A-2, 14:18:18, is earlier than the limit time of job A-2, 14:18:21. The scheduled job end time of job A-2 is (job start time 14:18:18 + average job execution time 10 seconds) = 14:18:28. The timeout adjustment unit 23 determines that the timeout condition of job A-2 is met because the scheduled job end time of job A-2 is before the timeout time of job A-2 (14:18:31). As a result, the timeout adjustment unit 23 determines that the execution order of jobs B-1 → B-2 → C-1 → C-2 → A-2, which satisfies the timeout condition, satisfies the timeout condition. Therefore, the number of jobs that can be processed in the job execution order when the currently running job is canceled is "5".

CPU 4 compares the number of jobs that can be processed ("5") when rescheduling is performed to stop the currently running job A-1 with the number of jobs that can be processed ("4") when the currently running job A-1 is continued (without rescheduling). Based on the comparison result, CPU 4 finds that the number of jobs is greater when rescheduling is performed to stop the currently running job A-1, and so updates the execution order in execution order list 13 to the order when rescheduling is performed to stop the currently running job A-1.

Figure 8 is a flowchart showing an example of the processing operation of CPU 4 related to queue management processing. Queue management unit 4A in CPU 4 shown in Figure 8 executes event standby to monitor the occurrence of an event (step S11). Note that the events that occur in step S11 are, for example, job submission, reaching the job's limit time, and exceeding the scheduled end time of the job.

The queue management unit 4A determines whether the occurring event is job submission (step S12). If the occurring event is job submission (step S12: Yes), the job reception unit 21 in the queue management unit 4A accepts the submitted job (step S13). The queuing unit 22 in the queue management unit 4A executes the queuing process shown in FIG. 10 for the accepted submitted job (step S14).

After executing the queuing process, the timeout adjustment unit 23 in the queue management unit 4A executes the timeout adjustment process shown in FIG. 11 (step S15). Furthermore, the timeout adjustment unit 23 checks the shortest limit time by referring to the limit time 11G of each job in the job table 11 (step S16), and proceeds to step S11 to monitor the occurring event. Furthermore, if the occurring event is not job input (step S12: No), the timeout adjustment unit 23 determines that the limit time of the job has been reached or the scheduled end time of the job has been exceeded, and executes the timeout adjustment process shown in FIG. 11.

Figure 9 is a flowchart showing an example of the processing operation of CPU 4 related to execution processing. Execution unit 4B in CPU 4 shown in Figure 9 executes event standby to monitor the occurrence of an event (step S21). Note that an event that occurs in step S21 is, for example, a request to stop a job, completion of job execution, submission of a job, etc.

The abort processing unit 36 in the execution unit 4B determines whether an abort request has been detected during event standby (step S21). If an abort request has not been detected (step S22: No), the execution unit 4B determines that the job has ended or been submitted, and updates and registers the application information table 12 and the job table 11 (step S23).

For example, when the execution unit 4B detects an execution end as an occurring event, it deletes the job information of the corresponding job in the job table 11. The execution unit 4B calculates the job execution average time 12B, job execution distribution time 12C, and setup average time 12D of the application corresponding to the corresponding job based on the job execution time, execution command time, and setup time of the job that has finished execution. The execution unit 4B updates the calculated job execution average time 12B, job execution distribution time 12C, and setup average time 12D of the application in the job table 11. Furthermore, when the execution unit 4B detects a job submission as an occurring event, it registers the job information of the corresponding job in the job table 11 to register the submission of the corresponding job.

After updating and registering the application information table 12 and the job table 11 in step S23, the execution unit 4B determines the next job to be executed in the execution order list 13 (step S24). Furthermore, the FPGA control unit 32 in the execution unit 4B executes the determined job on the firmware in the FPGA 3 (step S25), and proceeds to step S21 to monitor the occurring event.

If the cancellation processing unit 36 in the execution unit 4B detects a cancellation request (step S22: Yes), it cancels the job (step S26). Furthermore, the execution unit 4B proceeds to step S23 to update and register the information associated with the cancellation of the job in the application information table 12 or the job table 11.

When the CPU 4 that executes the execution process detects a request to stop, it stops the job that is being executed. As a result, the job that is being executed can be stopped midway.

Figure 10 is a flowchart showing an example of the processing operation of CPU 4 related to queuing processing. In Figure 10, the queuing unit 22 in CPU 4 registers job information of a job in job table 11 (step S31). The queuing unit 22 acquires application identification information of each job in job table 11 (step S32). The queuing unit 22 sorts the execution order of accumulated jobs in execution order list 13 by basic logic so that jobs with the same application identification information 11B in job table 11 are consecutive (step S33). The basic logic is the logic shown in Figure 7B, which rearranges the execution order of jobs according to the input order while avoiding overlapping setup times of the same application. The queuing unit 22 updates the execution order list 13 with the execution order after sorting by basic logic (step S34), and ends the processing operation shown in Figure 10.

The CPU 4 that executes the queuing process rearranges the execution order of the jobs that are stored in the order they are submitted, using basic logic, so that jobs of the same application are executed consecutively. As a result, it is possible to reduce the setup time that is duplicated within the same application, thereby improving the execution efficiency of each job.

Figure 11 is a flowchart showing an example of the processing operation of CPU 4 related to the timeout adjustment process. In Figure 11, the timeout adjustment unit 23 in CPU 4 acquires job information for each job from the job table 11 (step S41). From the acquired job information, the timeout adjustment unit 23 calculates the limit time 11G for each job based on the input time 11C and timeout condition 11D for each job (step S42). The timeout adjustment unit 23 calculates the timeout time 11F for each job based on (input time 11C + timeout condition 11D) for each job. Furthermore, the timeout adjustment unit 23 calculates the limit time 11G for each job based on (timeout time 11F - average job execution time of the relevant application) for each job.

After calculating the limit time 11G for each job, the timeout adjustment unit 23 compares the limit time 11G with the job start time for each job (step S43). The job start time is calculated by rearranging the execution order of the prioritized jobs in the order of earliest submission, based on basic logic that prioritizes jobs in the same app when there are jobs for the same app among multiple apps. The timeout adjustment unit 23 determines whether there is a job whose limit time is earlier than the job start time (step S44).

If there is a job whose limit time is earlier than the job start time (step S44: Yes), the timeout adjustment unit 23 determines whether there is a job whose job start time has reached the limit time (step S45). If there is a job whose job start time has reached the limit time (step S45: Yes), the timeout adjustment unit 23 executes the limit time processing shown in FIG. 12 (step S46). Then, the timeout adjustment unit 23 updates the execution order list 13 (step S50) and ends the processing operation shown in FIG. 11.

If there is no job whose job start time has reached the limit time (step S45: No), the timeout adjustment unit 23 determines whether the current time exceeds the scheduled end time of the job being executed (step S47). If the current time exceeds the scheduled end time of the job being executed (step S47: Yes), the timeout adjustment unit 23 executes the scheduled end time process shown in FIG. 13 (step S48) and proceeds to step S50.

If the current time does not exceed the scheduled end time of the job being executed (step S47: No), the timeout adjustment unit 23 executes the new job submission process shown in FIG. 14 (step S49) and proceeds to step S50. If there is no job whose limit time is earlier than the job start time (step S44: No), the timeout adjustment unit 23 proceeds to step S50 to update the execution order list 13.

The CPU 4 executing the timeout adjustment process can execute limit time processing when there is a job whose limit time is earlier than the job start time and there is a job whose job start time has reached the limit time. The CPU 4 can execute scheduled end time processing when there is no job whose job start time has reached the limit time and the current time has exceeded the scheduled end time of the job being executed. Furthermore, the CPU 4 can execute new job submission processing when there is no job whose job start time has reached the limit time and the current time has not exceeded the scheduled end time of the job being executed.

FIG. 12 is a flowchart showing an example of the processing operation of the CPU 4 related to the limit time processing. In FIG. 12, the timeout adjustment unit 23 in the CPU 4 starts the limit time processing when there is a job whose job start time has reached the limit time in step S45 shown in FIG. 11. When the timeout adjustment unit 23 detects a job whose job start time has reached the limit time (step S51), it calculates the number of jobs when the job whose job start time has reached the limit time is executed with priority and the number of jobs when the job whose job whose limit time has been reached is stopped (step S52). Note that the case where the job whose limit time has been stopped corresponds to the case where the job whose limit time has been reached is stopped and rescheduled. The case where the job whose limit time has been reached is executed with priority corresponds to the case where rescheduling is performed to continue the job whose limit time has been reached.

The timeout adjustment unit 23 compares the number of jobs when priority execution is performed with the number of jobs when execution is canceled, and determines whether the number of jobs when priority execution is performed is greater (step S53). If the number of jobs when priority execution is greater (step S53: Yes), the timeout adjustment unit 23 sorts the job execution order so that the job that has reached the limit time is executed with priority (step S54), and ends the processing operation shown in FIG. 12. The execution order list 13 is updated with the execution order after sorting in step S50 shown in FIG. 11.

If the number of jobs in the case of priority execution is not greater (step S53: No), the timeout adjustment unit 23 executes job rejection to reject the job that has reached the limit time (step S55), and ends the processing operation shown in FIG. 12. In step S50 shown in FIG. 11, the execution order list 13 is updated with the execution order after the job rejection.

When the CPU 4 executing the limit time processing detects a job that has reached the limit time, it compares the number of jobs that will be executed with priority when the job that has reached the limit time is executed with the number of jobs that will be aborted when the job that has reached the limit time is executed. Furthermore, based on the comparison result, if the number of jobs that will be executed with priority when the job that has reached the limit time is greater, the CPU 4 reschedules the execution order to execute the job that has reached the limit time with priority. As a result, it is possible to process as many jobs as possible while executing the job that has reached the limit time with priority.

Based on the comparison result, if the number of jobs that would be executed preferentially for the job that has reached its limit time is not greater, the CPU 4 rejects the job that has reached its limit time. As a result, it is possible to process as many jobs as possible while rejecting jobs that have reached their limit time.

13 is a flowchart showing an example of the processing operation of the CPU 4 related to the scheduled end time processing. In FIG. 13, the timeout adjustment unit 23 in the CPU 4 starts the scheduled end time processing when the current time exceeds the scheduled end time of the job in progress in step S47 shown in FIG. 11. The timeout adjustment unit 23 assumes that the job in progress is extended by one standard deviation and calculates the number of jobs when the job in progress is stopped and the number of jobs when the job in progress is continued (step S61). The case where the job in progress is stopped corresponds to the case where the job in progress is stopped and rescheduled, and the case where the job in progress is continued corresponds to the case where rescheduling is performed to continue the job in progress. The timeout adjustment unit 23 compares the number of jobs when the job in progress is stopped and the number of jobs when the job in progress is continued, and determines whether the number of jobs when the job in progress is stopped is greater (step S62).

If the number of jobs would be greater if the currently running jobs were canceled (step S62: Yes), the timeout adjustment unit 23 sends a request to cancel the currently running jobs to the cancellation processing unit 36 in the execution unit 4B (step S63) and ends the processing operation shown in FIG. 13. The execution order list 13 is updated to the execution order in which the currently running jobs were canceled in step S50 shown in FIG. 11.

If the number of jobs would not be greater if the currently running jobs were stopped (step S62: No), the timeout adjustment unit 23 continues the currently running jobs (step S64) and ends the processing operation shown in FIG. 13. The execution order list 13 is updated to the execution order in which the currently running jobs were continued in step S50 shown in FIG. 11.

The CPU 4 that executes the scheduled end time processing assumes that the running job will be extended by one standard deviation, and compares the number of jobs when the running job is stopped with the number of jobs when the running job is continued. If the CPU 4 determines based on the comparison result that the number of jobs would be greater when the running job is stopped, it sends a stop request to the stop processing unit 36 to stop the running job. As a result, by stopping the running job, it is possible to process as many jobs as possible.

Based on the comparison result, if the number of jobs that would be processed if the currently running job were stopped is not greater, the CPU 4 continues the currently running job. As a result, as many jobs as possible can be processed while continuing the currently running job.

Figure 14 is a flowchart showing an example of the processing operation of CPU 4 related to new job submission processing. In Figure 14, the timeout adjustment unit 23 in CPU 4 starts new job submission processing when the scheduled end time of the job being executed has not been exceeded in step S47 shown in Figure 11. The timeout adjustment unit 23 calculates the number of jobs in the execution order including the new job and the number of jobs in the execution order not including the new job (step S71). Note that the execution order including the new job corresponds to a case where the execution order including the new job is rescheduled, and the execution order not including the new job corresponds to a case where the execution order not including the new job is rescheduled. The timeout adjustment unit 23 determines whether the number of jobs in the execution order including the new job is greater (step S72).

If the number of jobs in the execution order, including the new job, is greater (step S72: Yes), the timeout adjustment unit 23 sorts the execution order so that the new job can be executed (step S73) and ends the processing operation shown in FIG. 14. In step S50 shown in FIG. 11, the execution order list 13 is updated with the sorted execution order.

If the number of jobs in the execution order including the new job is not greater (step S72: No), the timeout adjustment unit 23 executes job rejection of the new job (step S74) and ends the processing operation shown in FIG. 14. In step S50 shown in FIG. 11, the execution order list 13 is updated with the execution order after the job rejection.

The CPU 4, which executes the new job submission process, compares the number of jobs in the execution order that includes the new job with the number of jobs in the execution order that does not include the new job. Furthermore, if the number of jobs in the execution order that includes the new job is greater based on the comparison result, the CPU 4 sorts the execution order so that the new job can be executed. As a result, it is possible to process as many jobs as possible while executing the new job.

Based on the comparison result, if the number of jobs in the execution order including the new job is not greater, the CPU 4 rejects the new job. As a result, it is possible to process as many jobs as possible while rejecting new jobs.

In this embodiment, the CPU 4 calculates the number of jobs that can be processed when rescheduling is not performed and when currently running jobs are stopped, and the number of jobs that can be processed when currently running jobs are stopped. If it is determined that the number of jobs that can be processed when currently running jobs are stopped is greater, the CPU 4 performs the rescheduling. As a result, it becomes possible to perform scheduling that can process as many jobs as possible, including stopping currently running jobs.

The CPU 4 calculates the number of jobs that can be processed when rescheduling is performed to prioritize execution of a job whose job start time has reached the limit time at which the timeout condition can be satisfied, and when rescheduling is performed to cancel the job whose limit time has been reached. Furthermore, if it is determined that the number of jobs is greater when rescheduling is performed to prioritize execution of a job whose limit time has been reached, the CPU 4 performs the rescheduling to prioritize execution of the job whose limit time has been reached. As a result, it becomes possible to perform scheduling that can process as many jobs as possible, including priority execution of a job whose limit time has been reached.

The CPU 4 calculates the number of jobs that can be processed when rescheduling the execution order including the new job and when not performing rescheduling. When it is determined that the number of jobs that can be processed when rescheduling the execution order including the new job is greater, the CPU 4 performs rescheduling of the execution order including the new job. As a result, when a new job is submitted, it becomes possible to perform scheduling that can process as many jobs as possible, including the new job.

In this embodiment, the basic approach is to run consecutive jobs of the same application, rearrange the jobs so that the timeout conditions are met, and if necessary, cancel the job in progress. In addition, the execution time of a job varies depending on the data being handled, and this can be fully handled in such cases.

In the above embodiment, an example was given of calculating the average job execution time, job execution distribution time, and average setup time, which differ for each application, but if the job execution time and setup time for each application are fixed, they may be set in advance or can be changed as appropriate.

In the above embodiment, step S45 is used to determine whether there is a job whose job start time has reached the limit time. However, instead of the process of step S45, a process may be executed to determine whether there is a job whose job end time has reached the timeout time. In this case, the number of jobs that would result from the priority execution of a job that has reached the timeout time is compared with the number of jobs that would result from the job that has reached the timeout time being aborted. If the number of jobs that would result from the priority execution of a job that has reached the timeout time is large, the jobs that have reached the timeout time are sorted into the order of execution that would result from the priority execution of a job that has reached the timeout time. Also, if the number of jobs that would result from the priority execution of a job that has reached the timeout time is not large, the job that has reached the timeout time may be rejected.

Furthermore, each component of each part shown in the figure does not necessarily have to be physically configured as shown in the figure. In other words, the specific form of distribution and integration of each part is not limited to that shown in the figure, and all or part of them can be functionally or physically distributed and integrated in any unit depending on various loads, usage conditions, etc.

Furthermore, the various processing functions performed by each device may be executed in whole or in part on a CPU (Central Processing Unit), DSP (Digital Signal Processor), FPGA (Field Programmable Gate Array), etc. Also, the various processing functions may be executed in whole or in part on a program that is analyzed and executed by a CPU, etc., or on hardware using wired logic.

The area for storing various information may be configured, for example, with ROM (Read Only Memory), RAM (Random Access Memory) such as SDRAM (Synchronous Dynamic Random Access Memory), MRAM (Magnetoresistive Random Access Memory), or NVRAM (Non-Volatile Random Access Memory).

The various processes described in this embodiment can be realized by executing a prepared program in a processor such as a CPU in a computer. Therefore, an example of a computer that executes a program having the same functions as those in the above embodiment will be described below. FIG. 15 is a block diagram showing an example of a computer 100 that executes an execution scheduling determination program.

The computer 100 that executes the execution scheduling determination program shown in FIG. 15 has an operation unit 101, a display unit 102, a communication unit 103, an FPGA 104, a ROM 105, a RAM 106, and a CPU 107. The CPU 107 causes the FPGA 104 to execute a job.

The ROM 105 is pre-stored with an execution scheduling determination program that performs the same functions as the above embodiment. The ROM 105 stores a queue management program 105A and an execution program 105B as execution scheduling determination programs. The execution scheduling determination program may be recorded on a computer-readable recording medium, not on the ROM 105, but on a drive (not shown). The recording medium may also be, for example, a portable recording medium such as a CD-ROM, a DVD disk, or a USB memory, or a semiconductor memory such as a flash memory.

Then, the CPU 107 reads the queue management program 105A from the ROM 105, and functions as the queue management process 106A on the RAM 106. Furthermore, the CPU 107 reads the execution program 105B from the ROM 105, and functions as the execution process 106B on the RAM 106.

When an active job and a queued job do not satisfy the set timeout condition, the CPU 107 reschedules each job. The CPU 107 calculates the number of jobs that can be processed when the active job is stopped and rescheduling is performed, and when the rescheduling is not performed. When it is determined that the number of jobs that can be processed when the rescheduling is performed is greater, the CPU 107 performs the rescheduling. As a result, as many jobs as possible can be processed.

1 Computer 2 Container 3 FPGA
4 CPU
4A Queue management unit 4B Execution unit 23 Timeout adjustment unit 36 Cancellation processing unit

Claims (4)

When the currently running job and the queued job do not satisfy the set timeout condition, the number of jobs that can be processed is calculated in a case where the currently running job is stopped and rescheduled, and in a case where the rescheduling is not performed;
a process for executing the rescheduling when it is determined that the number of jobs that can be processed is greater when the rescheduling is executed, the process being performed by a computer. Calculating the number of jobs that can be processed when rescheduling is performed to preferentially execute a job whose job start time has reached a limit time that satisfies a timeout condition, and when rescheduling is performed to cancel the job whose job start time has reached the limit time;
2. The execution scheduling determination method according to claim 1, further comprising the step of: executing a process for executing rescheduling for preferential execution of a job that has reached its limit time when it is determined that the number of jobs that can be processed when rescheduling is performed to cancel the job that has reached its limit time is greater than the number of jobs that can be processed when rescheduling is performed to preferentially execute the job that has reached its limit time. Calculating the number of jobs that can be processed when rescheduling the execution order including the new job and when not performing the rescheduling;
3. The execution scheduling determination method according to claim 1, further comprising the step of: executing rescheduling of the execution order including the new job when it is determined that the number of jobs that can be processed when rescheduling the execution order including the new job is greater than the number of jobs when the rescheduling is not executed. Calculate the number of jobs that can be processed when the currently running job and the queued job do not satisfy the set timeout condition, in a case where the currently running job is stopped and rescheduled, and in a case where the rescheduling is not performed;
an execution schedule determination program for causing a computer to execute a process of executing the rescheduling when it is determined that the number of jobs that can be processed is greater when the rescheduling is executed;

Images