CN117938851A

CN117938851A - DAG real-time task unloading optimization method based on edge calculation

Info

Publication number: CN117938851A
Application number: CN202410087384.9A
Authority: CN
Inventors: 龙林波; 邓姚; 沈靖程; 刘智
Original assignee: Chongqing University of Post and Telecommunications
Current assignee: Chongqing University of Post and Telecommunications
Priority date: 2024-01-22
Filing date: 2024-01-22
Publication date: 2024-04-26

Abstract

The present invention belongs to the technical field of task offloading, and specifically relates to a DAG real-time task offloading optimization method based on edge computing; the method comprises: an SDN controller receives real-time tasks to be offloaded sent by a user, and constructs an earliest task completion time model; the execution time of tasks on different servers is calculated to obtain an initial task offloading strategy; all tasks are offloaded to a waiting queue in a server according to the initial task offloading strategy, and real-time tasks with dependencies in the waiting queue are executed; the remaining real-time tasks in the waiting queue in the server are sorted according to the remaining tolerance delay and a set of tasks to be offloaded for a second time is constructed; a secondary offloading strategy is obtained according to the remaining tolerance delay of the real-time tasks, and the secondary offloading of tasks is executed according to the secondary offloading strategy; the server executes the real-time tasks in the waiting queue to complete the offloading execution of the DAG real-time tasks; the present invention improves the system utilization rate and reduces the congestion of the server when a large number of tasks are executed.

Description

DAG real-time task unloading optimization method based on edge calculation

Technical Field

The invention belongs to the technical field of task unloading, and particularly relates to a DAG real-time task unloading optimization method based on edge calculation.

Background

With the rapid arrival of the universal interconnection age and the popularization of wireless networks, the number of devices at the network edge is rapidly increased; the Edge Computing (EC) is used as an emerging distributed computing architecture, and due to the characteristic that the EC is closer to a user side, services are provided near the user side, so that lower network delay is ensured, and the application low-delay requirement of the Internet of things can be better met. However, applying real-time processing remains a major challenge in task offloading, and real-time processing requirements from unstructured data and large volumes of real-time data are an urgent issue to be addressed. How to achieve real-time offloading in a resource-limited edge environment is a major goal of research.

In order to fully exert the edge computing advantages and further optimize the application time delay, a plurality of research works propose a new edge computing task model, and the task parallelism is increased and the processing time delay is reduced by carrying out optimization modeling around the DAG task model; the offloading of DAG real-time tasks requires simultaneous consideration of the execution delays of multiple tasks on servers and the communication delays consumed by the data transfer of tasks between servers. Some researchers propose new multi-user resource allocation schemes and application level adjustment decisions to achieve near real-time processing of tasks. However, these schemes still do not effectively meet the low latency requirements of the real-time task offloading problem.

When an application performs real-time offloading in a scenario with multiple heterogeneous edge servers, how to guarantee the minimum completion time of the DAG application subtask offloading policy with a dependency is optimal. When a large number of real-time tasks are unloaded onto the same server, how to avoid task waiting and blocking problems caused by limited server resources. How to perform cooperative service between servers to improve the utilization rate of edge computing resources. All are major problems to be solved.

Disclosure of Invention

Aiming at the defects existing in the prior art, the invention provides a DAG real-time task unloading optimization method based on edge calculation, which comprises the following steps:

S1: the SDN controller receives real-time tasks to be offloaded sent by a user, constructs a DAG real-time task flow chart, and constructs a task earliest completion time model according to the DAG real-time task flow chart;

S2: calculating the execution time of the task on different servers to obtain a primary task unloading strategy; according to the primary task unloading strategy, all tasks are unloaded to a waiting queue in a server;

S3: executing real-time tasks with dependency relations in the waiting queue according to the earliest task completion time model;

S4: calculating the residual tolerance time delay of the tasks, sequencing the residual real-time tasks in a waiting queue in the server according to the residual tolerance time delay, and constructing a task set to be secondarily offloaded;

s5: obtaining a secondary unloading strategy according to the residual tolerance time delay of the real-time task in the secondary unloading task set, and executing task secondary unloading according to the secondary unloading strategy;

S6: and the server executes the real-time tasks in the waiting queue to finish the unloading execution of the DAG real-time tasks. Preferably, the task earliest completion time model is expressed as:

F_i＝min{F_{max_i}+D_i+p_i}

Wherein, F _i represents the earliest completion time of task R _i, F _{max_i} represents the earliest completion time of the largest precursor task of task R _i, D _i represents the transmission delay of the task, and p _i represents the computation delay of the task.

Preferably, the process of obtaining the primary task offloading policy includes:

periodically acquiring the execution rate of each server and the data size of unfinished tasks by the SDN controller; and calculating the execution time of the real-time task on different servers according to the data size of the real-time task, the execution rate of the servers and the data size of the unfinished task, and selecting the server with the minimum execution time as an unloading server.

Further, the formula for calculating the execution time of the task on the server is:

wherein T _i,j represents the execution time of task R _i on server ES _j, p _i,j represents the computation delay of task R _i on server ES _j, W _j represents the size of task data outstanding on server ES _j, and q _j represents the execution rate of server ES _j.

Preferably, the process of constructing the task set to be secondarily offloaded includes: and selecting real-time tasks which cannot be completed within the limited tolerance time delay from the residual real-time tasks, and sequencing the real-time tasks which cannot be completed according to the residual tolerance time delay to obtain a task set to be subjected to secondary unloading.

Preferably, the process of obtaining the secondary offloading policy includes: judging whether each server meets the time delay condition according to the residual tolerance time delay of the real-time tasks in the secondary unloading task set, and if so, selecting the server with the minimum sum of the transmission time delay and the calculation time delay as the unloading server.

Further, the time delay condition is:

Wherein, p _i,k represents the calculation time delay of the task R _i on the server ES _k, d _i represents the data amount required to be processed by the task R _i, v _j,k represents the data transmission rate between the server ES _j and the server ES _k, W _k represents the unfinished task data size on the server ES _k, and q _k represents the execution rate of the server ES _k; t _i' represents the remaining tolerable delay for task R _i.

The beneficial effects of the invention are as follows:

(1) Under the condition of meeting the real-time processing of the task, the invention optimizes the data communication time delay of the DAG task; and processing according to the data dependence among the tasks, adopting an integer programming mode, taking real-time requirements as limiting conditions, minimizing real-time task completion time, obtaining an optimized unloading decision, and effectively mapping the server and the DAG real-time tasks.

(2) According to the invention, the multi-server cooperative processing is adopted in the unloading scene of the edge environment facing a large number of real-time tasks, so that the utilization rate of the system is improved, the congestion of the server when a large number of tasks are executed is reduced, and the real-time processing of the tasks is satisfied.

Drawings

FIG. 1 is a schematic diagram of a DAG real-time task offloading optimization method based on edge computation in the present invention.

Detailed Description

The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

The invention provides a DAG real-time task unloading optimization method based on edge calculation, which is shown in fig. 1 and comprises the following steps:

S1: the SDN controller receives real-time tasks to be offloaded sent by a user, builds a DAG real-time task flow chart, and builds a task earliest completion time model according to the DAG real-time task flow chart.

Periodically obtaining initial information of edge computing server nodes by SDN controller, and using a full graphRepresenting a communication relationship between edge servers within an edge computing environment, wherein a complete graph Gt vertex es= { ES ₁,...,ES_j,...,ES_J } is an edge server computing node,For the collection of Gt edges,Element e _x,y of ES _x、ES_y represents an edge connecting two vertices of ES _x、ES_y, v is the weight of the Gt edge, that is, the transmission rate v= { v ₁,...,v_j,…,v_J},ES_j between edge server computing nodes and the data transmission rate to ES _y is v _i,y, and meanwhile, waiting queue information of the edge computing server nodes is obtained.

The user sends real-time tasks to the SDN, and the SDN controller receives the real-time tasks to be offloaded sent by the user and constructs a DAG real-time task flow chart with I nodes. Specific: analyzing the dependency relationship of the tasks to obtain the data amount to be transmitted by the precursor task and the precursor task of each task, wherein the dependency matrix is represented by a matrix pro with a size IxI, wherein pro _i,x＝u_x represents that the task R _i needs to receive the transmission data u _x from the precursor task R _x, and when pro _i,x =0, R _i does not need to receive the transmission data of R _x, i.e. R _x is not the precursor task of R _i; one task is provided with a plurality of precursor tasks, and the current task can be started to be executed after all the precursor tasks are executed; constructing a DAG real-time task flow chart according to the dependency relationship of the tasks, introducing a virtual starting task R ₀ to be linked to each actual starting task, and simulating the actual requirements by a virtual ending task R _I+1 to which each actual ending task needs to be pointed; the processing time of the virtual start task and the virtual end task is 0, and the virtual start task and the virtual end task are placed on the same server.

Constructing a task earliest completion time model according to the DAG real-time task flow chart, and specifically:

The task earliest completion time model is expressed as:

F_i＝min{F_{max_i}+D_i+p_i}

Wherein F _i represents the earliest completion time of task R _i, D _i represents the transmission delay of the task, p _i represents the computation delay of the task, and F _{max_i} represents the earliest completion time of the largest precursor task of task R _i:

F_{max_i}＝max｛F_x|pro_i,x＞0}

Wherein F _x represents the earliest completion time of the precursor task R _x.

S2: calculating the execution time of the task on different servers to obtain a primary task unloading strategy; and unloading all tasks to a waiting queue in the server according to the primary task unloading strategy.

The DAG real-time task offload policy is x= { X ₁,...,X_i,...,X_n }, where X _i＝{x₁,...,x_j,...,x_m},x_j e {0,1},0 represents no offload, 1 represents offload. The SDN controller periodically acquires the execution rate of each server and the data size of the unfinished task, and calculates the execution time of the real-time task on different servers according to the data size of the real-time task, the execution rate of the servers and the data size of the unfinished task; task R _i is executed on server ES _j for the following time:

Wherein, p _i,j represents the calculation delay of the task R _i, W _j represents the data size of the task which is not completed on the server ES _j, d _i represents the data size of the task R _i, and q _j represents the execution rate of the server ES _j.

And selecting the server with the minimum execution time as an unloading server to obtain a primary task unloading strategy. Therefore, in the primary task offloading policy, the execution time of the task on the offload server is:

Where T _i represents the execution time of task R _i, m represents the number of servers, and X _i,j represents whether task R _i is offloaded to server ES _j.

And unloading all tasks to a waiting queue in the server according to the primary task unloading strategy. The real-time task enters a waiting queue with a queue length L in a target edge server computing node to wait for execution, wherein the queue length L=L' +1 of the updated waiting queue represents the queue length before being updated.

S3: and executing the real-time tasks with the dependency relationship in the waiting queue according to the earliest task completion time model.

And acquiring an execution sequence corresponding to the real-time tasks with the dependency relationships according to the earliest task completion time model, and executing the real-time tasks with the dependency relationships by the server.

S4: calculating the residual tolerance time delay of the tasks, sequencing the residual real-time tasks in the waiting queue in the server according to the residual tolerance time delay, and constructing a task set to be secondarily offloaded.

After the primary unloading execution, tasks from different DAG flowcharts or tasks without data dependency relationship exist in a waiting queue of the same server, and the tasks can be optimized for the execution sequence again in the actual unloading; specific:

Calculating the residual tolerance time delay of the task:

T_i′＝θ_i-D_i

Where T _i' represents the remaining tolerable delay of task R _i, θ _i represents the defined tolerable delay of task R _i, and D _i represents the transmission delay of task R _i.

And sequencing the residual real-time tasks in the waiting queue in the server according to the residual tolerance time delay, wherein the sequencing is more forward when the residual tolerance time delay is smaller. And selecting real-time tasks which cannot be completed within the limited tolerance time delay from the residual real-time tasks, and sequencing the real-time tasks which cannot be completed according to the residual tolerance time delay (the residual tolerance time delay is smaller and the sequencing is more forward), so as to obtain a task set to be subjected to secondary unloading.

S5: and obtaining a secondary unloading strategy according to the residual tolerance time delay of the real-time task in the secondary unloading task set, and executing task secondary unloading according to the secondary unloading strategy.

Acquiring real-time information of each server so as to calculate task calculation time delay, task residual tolerance time delay and transmission time delay among the servers; screening servers meeting the time delay conditions according to the residual tolerance time delay of the real-time tasks in the secondary unloading task set, and selecting a server with the minimum sum of the transmission time delay and the calculation time delay as an unloading server to obtain a secondary unloading strategy; and if the server meeting the condition does not exist, canceling the secondary unloading. Preferably, the delay conditions are:

Wherein, p _i,k represents the calculation time delay of the task R _i on the server ES _k, d _i represents the data amount required to be processed by the task R _i, v _j,k represents the data transmission rate between the server ES _j and the server ES _k, W _k represents the unfinished task data size on the server ES _k, and q _k represents the execution rate of the server ES _k; t _i' represents task R _i.

And executing task secondary unloading according to the secondary unloading strategy, and sequentially unloading real-time tasks in the secondary unloading task set to the waiting queues of the corresponding target servers.

S6: and the server executes the real-time tasks in the waiting queue to finish the unloading execution of the DAG real-time tasks.

And the server executes the real-time tasks in the waiting queue, finishes the unloading execution of the DAG real-time tasks, and obtains the minimum time delay after the DAG real-time tasks are optimized, wherein the minimum completion time of the DAG real-time tasks is the completion time of the ending tasks in the DAG real-time task flow chart.

In summary, in the large-scale DAG real-time task unloading scene of edge computing processing, the task unloading efficiency is improved, the transmission delay of the task in the unloading process is considered, the task with large computing capacity or low priority is cooperatively processed with other servers on the edge server with limited resources, congestion is avoided, and real-time processing of the task is ensured.

While the foregoing is directed to embodiments, aspects and advantages of the present invention, other and further details of the invention may be had by the foregoing description, it will be understood that the foregoing embodiments are merely exemplary of the invention, and that any changes, substitutions, alterations, etc. which may be made herein without departing from the spirit and principles of the invention.

Claims

1. A method for optimizing real-time task offloading based on edge computing using a DAG, characterized by comprising:

S1: The SDN controller receives the real-time tasks to be unloaded sent by the user and constructs a DAG real-time task flowchart. Based on the DAG real-time task flowchart, it constructs the earliest completion time model of the task.

S2: Calculate the execution time of tasks on different servers to obtain the initial task unloading strategy; unload all tasks into the waiting queue on the server according to the initial task unloading strategy;

S3: Execute real-time tasks with dependencies in the waiting queue based on the earliest completion time model of the tasks;

S4: Calculate the remaining tolerance latency of the task and sort the remaining real-time tasks in the waiting queue in the server according to the remaining tolerance latency, and construct a set of tasks to be unloaded a second time.

S5: Obtain the secondary unloading strategy based on the remaining tolerable latency of real-time tasks in the secondary unloading task set, and execute the secondary unloading of tasks according to the secondary unloading strategy.

S6: The server executes the real-time tasks in the waiting queue and completes the unloading and execution of the DAG real-time tasks.

2. The DAG real-time task offloading optimization method based on edge computing according to claim 1, characterized in that the earliest task completion time model is expressed as:

F _i =min{F _{max_i} +D _i + _pi }

Where F _i represents the earliest completion time of task R_i , F _{max_i} represents the earliest completion time of the maximum predecessor task of task R _i , D _i represents the transmission delay of the task, and p_i represents the computation delay of the task.

3. The DAG real-time task offloading optimization method based on edge computing according to claim 1, characterized in that the process of obtaining the initial task offloading strategy includes:

The SDN controller periodically obtains the execution rate and the amount of unfinished tasks for each server; based on the data size of the real-time tasks, the server's execution rate, and the amount of unfinished tasks, it calculates the execution time of the real-time tasks on different servers and selects the server with the shortest execution time as the offloading server.

4. The DAG real-time task offloading optimization method based on edge computing according to claim 3, characterized in that the formula for calculating the execution time of the computation task on the server is:

Where Ti _,j represents the execution time of task _Ri on server ES _j , p _i,j represents the computation latency of task _Ri on server ES _j , W _j represents the size of unfinished task data on server ES _j , and q _j represents the execution rate of server ES _j .

5. The DAG real-time task offloading optimization method based on edge computing according to claim 1, characterized in that the process of constructing the set of tasks to be offloaded a second time includes: selecting real-time tasks that cannot be completed within the limited tolerance delay from the remaining real-time tasks, sorting the real-time tasks that cannot be completed according to the remaining tolerance delay, and obtaining the set of tasks to be offloaded a second time.

6. The DAG real-time task offloading optimization method based on edge computing according to claim 1, characterized in that the process of obtaining the secondary offloading strategy includes: judging whether each server meets the latency condition based on the remaining tolerable latency of the real-time tasks in the secondary offloading task set; if it meets the condition, selecting the server with the smallest sum of transmission latency and computation latency as the offloading server.

7. The DAG real-time task offloading optimization method based on edge computing according to claim 6, characterized in that the latency condition is:

Where p _{i,k} represents the computation latency of task R _i _ on server ESk, d_i represents the amount of data that task R_i needs to process, v _{j,k} represents the data transfer rate between server ES _j _ and server ESk, W_k represents the size of unfinished task data on server ES _k , q _k represents the execution rate of server ES _k , and T _i ′ represents the remaining tolerable latency of task R _i .