# US 12,008,400 B2 · Method and device for arranging schedule for computing task to server on basis of task dependency

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,008,400 B2
- Document ID: US12008400B2
- Status: Granted
- Kind: B2
- Application number: 17/309,183
- Filed: 2019-10-24
- Published: 2021-12-02
- Granted: 2024-06-11
- Earliest claimed: 2018-11-06
- Assignees: Samsung Electronics Co., Ltd.; Korea University Research and Business Foundation
- Applicants: Samsung Electronics Co., Ltd.; Korea University Research And Business Foundation
- Inventors: Kisuk Kweon; Haneul Ko; Sangheon Pack; Jaewook Lee; Joonwoo Kim; Yujin Tae
- Web page: https://patentgrep.com/patent/US12008400B2

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/455: Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
- G06F 9/45558: {Hypervisor-specific management and integration aspects}
- G06F 9/48: Program initiating; Program switching, e.g. by interrupt
- G06F 9/4806: {Task transfer initiation or dispatching}
- G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system}
- G06F 9/50: Allocation of resources, e.g. of the central processing unit [CPU]
- G06F 9/5005: {to service a request}
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 9/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)}
- G06F 9/505: {considering the load}
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 2009/4557: {Distribution of virtual machine instances; Migration and load balancing}
- G06F 2209/501: Performance criteria
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 6)

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,
allocating 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, allocating 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.

### Claim 9 (depends on 6)

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,
allocating 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, allocating 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, and
that the second task is un-allocatable to the second computation server, allocating the second task to a third computation server having a largest computation processing capacity from among the plurality of computation servers based on the computing processing capacity information.

### Claim 10 (depends on 6)

The method of claim 6, wherein
each of the plurality of computation servers comprises a plurality of virtual machines (VMs),
wherein the determining of the time at which each of the plurality of tasks is to be performed comprises,
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, allocating the second task to a second VM of the first computation server and determining a time at which the second task is to be performed, or determining a time at which the second task is to be performed so that the second task is performed after the first task is performed.

### Claim 11 (depends on 6)

A computer program product comprising a recording medium storing a program for executing the method of claim 6.