Method and device for arranging schedule for computing task to server on basis of task dependency

Patent metadata

Field	Value
Publication number	US-12008400-B2
Application number	US-201917309183-A
Country	US
Kind code	B2
Filing date	Oct 24, 2019
Priority date	Nov 6, 2018
Publication date	Jun 11, 2024
Grant date	Jun 11, 2024

Abstract

The disclosure relates to a method and a control server for scheduling a computing task including a plurality of tasks to be performed by computation servers. The control server according to some embodiments includes: a transceiver; a memory; and at least one processor configured to receive the computing task from a terminal, generate a task dependency graph based on a dependency relationship of each of the plurality of tasks included in the computing task, obtain computation processing capacity information of each of the plurality of computation servers and information of transmission latency between the plurality of computation servers, schedule the plurality of tasks to be performed by at least two computation severs of the plurality of computation servers, based on the task dependency graph, the computation processing capacity information, and the information of transmission latency, and transmit, to the terminal, an execution result of the plurality of tasks received from at least one of the plurality of computation servers.

First claim

The invention claimed is:

1. A control server for scheduling a computing task comprising a plurality of tasks to be performed by computation servers, the control server comprising:
a transceiver;
a memory; and
at least one processor configured to:
receive the computing task from a terminal,
generate a task dependency graph based on a dependency relationship of each of the plurality of tasks included in the computing task,
obtain computation processing capacity information of each of a plurality of computation servers and information of transmission latency between the plurality of computation servers,
schedule the plurality of tasks to be performed by at least two computation servers of the plurality of computation servers, based on the task dependency graph, the computation processing capacity information, and the information of transmission latency,
transmit, to the terminal, an execution result of the plurality of tasks received from at least one of the plurality of computation servers,
schedule the plurality of tasks to be performed by the at least two computation servers of the plurality of computation servers by allocating the plurality of tasks to the at least two computation servers and determining a time at which each of the plurality of tasks is to performed,
identify a computational complexity of each of the plurality of tasks, adjust the computational complexity of each of the plurality of tasks by converting at least one of the plurality of tasks into at least one sub-task, generate a spread task dependency graph according to a dependency relationship of each of the plurality of tasks whose computational complexities are adjusted, allocate the plurality of tasks to the at least two computation servers based on the spread task dependency graph, and
determine a time at which each of the plurality of tasks is to be performed based on the task dependency graph generated based on the dependency relationship of each of the plurality of tasks whose computational complexities are not adjusted.

2. The control server of claim 1 , wherein the at least one processor is further configured to
identify a computational complexity of each of the plurality of tasks,
adjust the computational complexity of each of the plurality of tasks, by converting at least one of the plurality of tasks into at least one sub-task, and
generate the task dependency graph based on a dependency relationship of each of the plurality of tasks whose computational complexities are adjusted.

3. The control server of claim 1 , wherein the at least one processor is further configured to:
in case that a second task of the plurality of tasks has a dependency relationship with a first task,
allocate the second task to a first computation server to which the first task is allocated, and
in case that the second task is un-allocatable to the first computation server, allocate the second task to a second computation server having a shortest transmission latency from the first computation server from among computation servers to which the second task is allocatable based on the information of transmission latency.

4. The control server of claim 1 , wherein the at least one processor is further configured to:
in case that a second task of the plurality of tasks has a dependency relationship with a first task,
allocate the second task to a first computation server to which the first task is allocated,
in case that the second task is un-allocatable to the first computation server, allocate the second task to a second computation server having a shortest transmission latency from the first computation server based on the information of transmission latency information, and
in case that the second task is un-allocatable to the second computation server, allocate the second task to a third computation server having a largest computation processing capacity from among the plurality of computation servers based on the computation processing capacity information.

5. The control server of claim 1 , wherein
each of the plurality of computation servers comprises a plurality of virtual machines (VMs), and
wherein the at least one processor is further configured to:
schedule the plurality of tasks to be performed by the at least two computation servers of the plurality of computation servers by allocating the plurality of tasks to the at least two computation servers and determining a time at which each of the plurality of tasks is to be performed, and
for a first task and a second task allocated to a first VM of a first computation server, in case that a time at which the first task is to be performed and a time at which the second task is to be performed at least partially overlap each other, allocate the second task to a second VM of the first computation server and determine a time at which the second task is to be performed, or determine a time at which the second task is to be performed so that the second task is performed after the first task is performed.

6. A method, performed by a control server, of scheduling a computing task comprising a plurality of tasks to be performed by computation servers, the method comprising:
receiving the computing task from a terminal;
generating a task dependency graph based on a dependency relationship of each of the plurality of tasks included in the computing task;
obtaining computing processing capacity information of each of a plurality of computation servers and information of transmission latency between the plurality of computation servers;
scheduling the plurality of tasks to be performed by at least two computation servers of the plurality of computation servers, based on the task dependency graph, the computing processing capacity information, and the information of transmission latency; and
transmitting an execution result of the plurality of tasks received from at least one of the plurality of computation servers to the terminal,
wherein the scheduling comprises:
allocating the plurality of tasks to the at least two computation servers; and
determining a time at which each of the plurality of tasks is to be performed,
wherein the allocating of the plurality of tasks to the at least two computation servers comprises:
identifying a computational complexity of each of the plurality of tasks;
adjusting the computational complexity of each of the plurality of tasks, by converting at least one of the plurality of tasks into at least one sub-task;
generating a spread task dependency graph, according to a dependency relationship of each of the plurality of tasks whose computational complexities are adjusted; and
allocating the plurality of tasks to the at least two computation servers based on the spread task dependency graph,
wherein the determining of the time at which each of the plurality of tasks is to be performed comprises
determining a time at which each of the plurality of tasks is to be performed based on the task dependency graph generated based on the dependency relationship of each of the plurality of tasks whose computational complexities are not adjusted.

7. The method of claim 6 , wherein
the generating of the task dependency graph comprises:
identifying a computational complexity of each of the plurality of tasks;
adjusting the computational complexity of each of the plurality of tasks, by converting at least one of the plurality of tasks into at least one sub-task; and
generating the task dependency graph based on a dependency relationship of each of the plurality of tasks whose computational complexities are adjusted.

8. The method of claim 6 , wherein
the scheduling comprises, in case that a second task of the plurality of tasks has a dependency relationship with a first task,
alloc

Assignees

• Samsung Electronics Co Ltd
• Univ Korea Res & Bus Found

Inventors

• Kweon Kisuk
• Ko Haneul
• Pack Sangheon
• Lee Jaewook
• Kim Joonwoo
• Tae Yujin

Classifications

• G06F2209/501

  Performance criteria · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/505

  considering the load · CPC title

• G06F9/5038

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title