Schedule decision device, parallel execution device, schedule decision method, and program
View Patent ↗A schedule decision method acquires dependencies of execution sequences required for a plurality of sub tasks into which a first task has been divided; generates a plurality of sub task structure candidates that satisfy said dependencies and for which a plurality of processing devices execute said plurality of sub tasks; generates a plurality of schedule candidates by further assigning at least one second task to each of said sub task structure candidates; computes an effective degree that represents effectiveness of executions of said first task and said second task for each of said plurality of schedule candidates; and decides a schedule candidate used for the executions of said first task and said second task from said plurality of schedule candidates based on said effective degrees.
1. A schedule decision device, comprising:
dependency acquisition means that acquires dependencies of execution sequences required for a plurality of sub tasks into which a first task has been divided;
candidate generation means that generates a plurality of sub task structure candidates that satisfy said dependencies acquired by said dependency acquisition means and for which a plurality of processing devices execute said plurality of sub tasks;
superimposition means that categorizes said plurality of sub task structure candidates generated by said candidate generation means as a plurality of groups, selects a first and second sub task structure candidate, compares the execution duration of the selected first and second sub task structure candidates, and adds a duration for which the executaion duration of one the first or second task structure candidate does not match the execution duration of the other task structure candidate to the other task structure candidate;
scheduling means that generates a plurality of the first schedule candidates by further assigning at least one second task to each of said sub task structure candidates generated by said superimposition means;
effective degree computation means that computes an effective degree that is realized by the effective degree of said first task and the effective degree of said second task for each of said plurality of the first schedule candidates generated by said scheduling means, wherein the computation means performs the step of:
computing the effective degree scores for the first and second task,
wherein the effective degree score for each task is computed according to the following formula:
(
k
3
*
(
average
tolerance
degree
)
)
+
(
k
4
*
(
average
interruption
time
)
)
(
execution
period
)
+
(
k
5
*
(
average
jitter
)
)
(
execution
period
)
,
where k3, k4, k5 are weighting coefficients, the average tolerance degree is an average value of tolerance degrees computed according to the following formula:
(
execution
period
)
-
(
task
completion
time
)
(
execution
period
)
,
,the average interruption time is an average value of times for which a task is interrupted in each execution period, and the average jitter is an average value of delay times after a period starts until a task starts in each execution period, and
computing the effective degree score of the plurality of sub task structure candidates, wherein the effective degree score of each sub task structure candidate is computed according to the following formula:
k1 * (effective degree score of first task)+ k 2* (effective degree score of second task),
where k1 and k2 are weighting coefficients; and
candidate decision means that decides a schedule candidate used for the executions of said first task and said second task from said plurality of the first schedule candidates based on said effective degrees computed by said effective degree computation means;
wherein said effective degree computation means further computes an effective degree of the respective first schedule candidates belonging to said respective sub task structure candidates generated by said superposition means, selects a group of sub task structure candidates from among said groups generated by the said superimposition means based on the computed effective degrees, and computes a plurality of second effective degree scores for a plurality of second schedule candidates corresponding to the sub task structure candidates that belong to the selected group;
said candidate decision means decides a second schedule candidate used for the executions of said first task and said second task from said plurality of second schedule candidates based on said second effective degrees computed by said effective degree computation means.
2. The schedule decision device according to claim 1 , wherein said superposition means categorizes said plurality of sub task structure candidates such that a difference of the numbers of said sub task structure candidates that belong to the individual groups becomes a predetermined value or less.
3. The schedule decision device according to claim 1 , wherein said superposition means computes a sum of execution times of sub tasks assigned to the predetermined processing devices for each of the sub task structure candidates and categorizes said plurality of candidates such that the sum computed for each of the sub task structure candidates that belong to each of the groups falls in a range that has been predetermined for each of the groups.
4. The schedule decision device according to claim 1 , wherein said superposition means categorizes said plurality of sub task structure candidates such that sub task structure candidates having offsets that differ from each other by a predetermined value or greater belong to different groups.