CN117632298B - Task unloading and resource allocation method based on priority list indexing mechanism - Google Patents

Abstract

The present invention discloses a method for task unloading and resource allocation based on a priority list index mechanism, including: collecting resource information of edge servers in a specified area through a monitor, building a DAG model according to task requests of local devices, and generating a priority index list; based on the priority index list, using a priority-based greedy algorithm and a resource allocation algorithm to perform target optimization, and obtaining an associated task unloading strategy and a resource allocation method; performing a user task unloading operation according to the associated task unloading strategy and resource allocation method. The present invention effectively reduces overall delay, improves resource utilization, and realizes efficient execution of associated tasks and reasonable allocation of resources by predicting and optimizing task unloading and resource allocation.

Description

A task offloading and resource allocation method based on priority list indexing mechanism

Technical Field

The present invention relates to the technical field of DAG task offloading and resource allocation in an edge computing environment, and in particular to a task offloading and resource allocation method based on a priority list index mechanism.

Background technique

Edge computing distributes computing and data processing to multiple edge servers, achieving more efficient and faster data processing and distribution, reducing dependence on cloud computing centers, and reducing data transmission delays and bandwidth consumption. In this environment, tasks need to be offloaded to multiple edge servers for processing to reduce delays and bandwidth consumption and improve service quality.

However, in a multi-user and multi-edge server environment, how to reasonably offload and allocate resources for related tasks remains a challenging problem. The related tasks generated by local devices are usually modeled as DAG tasks. A DAG task may consist of multiple subtasks, which have a sequence and dependency relationship between them. Therefore, a strategy that can reasonably allocate resources and coordinate the execution order between tasks is needed. At the same time, due to the differences in performance and resource utilization between edge servers, a solution that can dynamically adjust resource allocation and task offloading is needed.

In practical applications, resource limitation is an important issue. Since the computing power of edge servers is limited, a solution that can optimize resource utilization and task execution efficiency is needed. On the one hand, it is necessary to make full use of the computing resources of edge servers to improve the processing power and efficiency of the entire system. On the other hand, it is necessary to avoid problems such as resource waste and task blocking to ensure the stability and reliability of the system.

In order to solve these problems, we can consider introducing a priority mechanism to reasonably formulate task offloading plans and resource allocation plans.

The priority mechanism in task offloading mainly assigns different priorities to different tasks. The priority mechanism can reasonably enable tasks with higher priority to take priority in better offloading positions while ensuring the order and execution efficiency of tasks, thereby improving the overall performance of the system. At the same time, in order to allocate resources more accurately, an effective resource allocation method needs to be designed. This resource allocation method needs to be able to take into account multiple factors such as the overall computing amount of DAG tasks, the computing resources of each device, the resource utilization of edge servers, the dependencies between tasks, etc., so as to make more reasonable decisions in task offloading and resource allocation. This is a practical and challenging task.

Summary of the invention

The present invention aims at the problem of unloading DAG tasks and resource allocation in an edge computing environment, and provides a task unloading and resource allocation method based on a priority list index mechanism.

On the one hand, to achieve the above-mentioned purpose, the present invention provides a task offloading and resource allocation method based on a priority list index mechanism, comprising:

Collect resource information of edge servers in the specified area, build a DAG model based on the task requests of local devices, and generate a priority index list;

Based on the priority index list, a priority-based greedy algorithm and a resource allocation algorithm are used to perform target optimization to obtain an associated task offloading strategy and a resource allocation method;

The user task offloading operation is performed according to the associated task offloading strategy and resource allocation method.

Preferably, a DAG model is constructed according to the task request of the local device to generate a priority index list, including:

The priority of each subtask in the DAG and the priority of each DAG are set respectively, each subtask in the DAG is sorted to obtain a subtask priority list of the DAG, and then the subtask priority list of each DAG is sorted to obtain a DAG priority list, that is, the priority index list.

Preferably, the method for defining the priority of each subtask in the DAG is:

In the formula, is the subtask generated by the local device I _x , i is the subtask number, x is the local device number, Indicates/> The priority of Indicates/> The amount of calculation, /> is the combined computing power of the local device I _x and the edge server in the system,/> Indicates the need/> Send a collection of subtasks that depend on data, /> For/> A subtask in /> Indicates/> To/> Dependency data sent, /> For/> The amount of data, /> is the average transmission rate of dependent data in the system.

Preferably, the method for defining the priority of each DAG is:

Where _Gx is the DAG task generated by the local device _Ix . is the starting subtask of G _x , cost(G _x ) is the system cost of G _x , and ψ(x) is the priority of G _x .

Preferably, obtaining the associated task offloading strategy and resource allocation method includes:

According to the priority index list, a greedy algorithm is used to find an offloading decision that enables each of the subtasks to have the smallest earliest completion time, and a DAG offloading record of each edge server is obtained;

Each subtask is retrieved according to the priority index list index, and the device that makes the subtask have the earliest completion time is selected for unloading, the subtask unloading strategy and the DAG unloading record of the edge server are updated, and the computing resource proportion of the DAG on the edge server is calculated according to the DAG unloading record of the edge server to obtain the associated task unloading strategy and resource allocation method.

Preferably, the method for calculating the computing resource proportion of DAG in the edge server according to the DAG offloading record of the edge server is:

In the formula, is the resource allocation ratio, /> It is a binary variable that records whether the DAG task generated by the local device offloads subtasks to the edge server. ψ(n) is the priority of the DAG, and N is the total number of DAG tasks.

Preferably, the objective function of the associated task offloading strategy and resource allocation method is the average response time of the system to complete all DAG tasks:

Where ft is the completion time of the subtask, is the end task of G _x , G _x is the DAG task generated by the local device I _x , and N is the total number of DAG tasks.

On the other hand, in order to achieve the above-mentioned purpose, the present invention also provides a task offloading and resource allocation system based on a priority list index mechanism, comprising:

System monitoring unit: used to monitor task information from devices and system resource information;

An offloading planning unit: plans a task offloading strategy and a resource allocation method through a DAG priority list indexing mechanism according to the task information and the resource information;

Strategy implementation unit: performs user task offloading operation according to the formulated task offloading strategy and resource allocation method.

Compared with the prior art, the present invention has the following advantages and technical effects:

By comprehensively considering task priority and user priority, the present invention can better solve the problem of offloading DAG tasks in a distributed computing environment, so that each subtask can obtain the earliest end time under the current resource conditions, maximize the use of computing resources in the distributed computing environment, and thus improve the execution efficiency and performance of DAG tasks; by predicting and optimizing task offloading and resource allocation, the overall delay is effectively reduced, resource utilization is improved, and efficient execution of associated tasks and reasonable allocation of resources are achieved.

BRIEF DESCRIPTION OF THE DRAWINGS

The drawings constituting a part of the present application are used to provide a further understanding of the present application. The illustrative embodiments and descriptions of the present application are used to explain the present application and do not constitute an improper limitation on the present application. In the drawings:

FIG1 is a schematic diagram of a task offloading and resource allocation system architecture based on a priority list indexing mechanism according to an embodiment of the present invention;

FIG2 is a schematic flow chart of a method for offloading a DAG task oriented to resource allocation according to an embodiment of the present invention;

FIG3 is a schematic diagram showing the relationship between the task response time and the parameter α according to an embodiment of the present invention;

FIG4 is a schematic diagram showing the relationship between task response time and algorithm according to an embodiment of the present invention;

5 is a schematic diagram of the relationship between task response time and the number of edge servers according to an embodiment of the present invention;

6 is a schematic diagram showing the relationship between task response time and the number of local devices according to an embodiment of the present invention;

FIG. 7 is a schematic diagram showing the relationship between task response time and the maximum number of logical cores according to an embodiment of the present invention.

Detailed ways

It should be noted that, in the absence of conflict, the embodiments and features in the embodiments of the present application can be combined with each other. The present application will be described in detail below with reference to the accompanying drawings and in combination with the embodiments.

It should be noted that the steps shown in the flowcharts of the accompanying drawings can be executed in a computer system such as a set of computer executable instructions, and that, although a logical order is shown in the flowcharts, in some cases, the steps shown or described can be executed in an order different from that shown here.

The present invention proposes a task offloading and resource allocation method based on a priority list index mechanism, as shown in FIG1 , which specifically includes:

Usually, task offloading takes smaller offloading latency as the optimization goal, but the computing resources in the environment are limited. Some important or computationally intensive tasks may not be allocated more computing resources, which is particularly fatal for related tasks. The longer latency of a task often directly or indirectly affects the progress of subsequent tasks, which will increase the overall latency of the system. In order to allow tasks with large computational load or special locations to enjoy better computing resources, they should give priority to preempting better offloading locations. To this end, a task offloading and resource allocation method based on a priority list index mechanism for users is proposed.

The monitor collects resource information of edge servers in the specified area, builds a DAG model based on the task requests of local devices, and generates a priority index list;

The priority of each subtask in the DAG and the priority of each DAG are defined respectively, each subtask in the DAG is sorted to obtain a subtask priority list of the DAG, and then the subtask priority list of each DAG is sorted to obtain a DAG priority list, that is, the priority index list.

The priority of each subtask in the DAG is defined as:

The priority of each DAG is defined as:

in:

1) G _x represents the DAG task generated by the local device I _x , is the subtask with sequence number i in G _x ,/> is the starting subtask of G _x , /> Indicates the need/> Sends a collection of subtasks that depend on data.

2) For/> The amount of calculation, /> is the comprehensive computing capacity of I _x and the edge servers in the system, expressed as follows:

Among them, α represents the weight parameter, _fx is the computing power of _Ix , _Fk is the computing power of edge server _Pk , and M is the total number of edge servers.

3) Indicates/> To/> Transmitted dependent data, /> is the size of the dependent data, /> is the average transmission rate of dependent data in the system.

4) cost(G _x ) is the system cost of G _x , expressed as follows:

Among them, _Ix is the set of subtasks _{in Gx} , and _Ex is the set of dependent data in _Gx .

5) Sort each subtask in the DAG by rank from large to small to obtain the subtask priority list Q of the DAG; then sort the Q of each DAG by ψ from large to small to obtain the DAG priority list PL.

Based on the priority index list, the priority-based greedy algorithm and resource allocation algorithm are used to optimize the target, and the associated task offloading strategy and resource allocation method are obtained;

Figure 2 shows a flow chart of the offloading method for DAG tasks oriented to resource allocation. In a distributed computing environment, the monitor first collects resource information of edge servers in the region, establishes a DAG model based on the task request of the local device, and generates a priority index list for these DAGs. According to the list order, combined with the computing resources of different devices and the DAG priority, the best offloading location is selected for each subtask and appropriate computing resources are allocated.

In the process of obtaining the offloading decision, the optimization goal further constructed is the average response time of the system to complete all DAG tasks:

in,

1) ft represents the completion time of the subtask, is the end task of G _x , so/> It also represents the response time of G _x . The calculation formula of ft is as follows:

_fx is the computing power of the local device _Ix , _Fk is the computing power of the edge server _Pk , is the computing resource ratio of G _x on edge server P _k .

2) After P _k receives the execution Execution cannot begin until the required dependency data and P _k are available/> Therefore,/> The start time is expressed as follows:

in, Indicates to/> Send a set of subtasks that depend on data, ava(G _x , P _k ) represents the start availability time of P _k for the subtask of G _x , which is related to the last subtask of G _x processed by P _k , and ava(G _x , P ₀ ) represents the start availability time of the local device I _x ,/> Depends on the data transfer time.

3) Computing resource allocation ratio of _Gx on edge server _Pk Related to DAG priority, expressed as:

in, is a binary variable that records whether _Gn offloads subtasks to _Pk , and N is the total number of DAG tasks.

The present invention aims at the problem of offloading multi-user DAG tasks, and adopts a priority-based greedy algorithm and a resource allocation algorithm to perform target optimization. The associative task offloading problem is mapped to the DAG task model. After the DAG task is generated, a priority index list with an order between DAGs and an order between each subtask is obtained by calculating the subtask priority and the DAG priority. According to the list index order, the offloading decision of each subtask is obtained by the greedy algorithm. Finally, the DAG offloading record of the edge server is obtained through the offloading decision, and the computing resource proportion of each subtask is allocated. The entire priority list indexing mechanism process is as follows:

1) Initialization

Collect and process the data elements of all related tasks, model the corresponding DAG task graph, and collect the edge server resource information under the current situation.

2) Index operation

Calculate the priority of each DAG and its subtasks and build a priority list PL.

3) Greedy selection

Take out each subtask according to the PL index, select the device that makes the subtask have the earliest completion time for unloading, and update the subtask unloading strategy and edge server DAG unloading record.

4) Resource Allocation

Calculate the computing resource ratio of DAG on the edge server based on the DAG offloading record of the edge server:

Through the above-mentioned greedy algorithm and resource allocation, the present invention can efficiently solve the problem of offloading multi-user DAG tasks and realize the optimal utilization of resources, thereby improving the task execution efficiency in the edge computing environment.

Uninstall Operation

Perform user task offloading operations according to the proposed offloading strategy and resource allocation method.

The process of task offloading and resource allocation using the present invention is as follows:

1) Initialization phase: The processor receives task processing requests from various devices;

2) Task offloading decision-making stage: Construct a DAG priority list based on the DAG priority and subtask priority, and use a greedy algorithm to find the offloading decision that makes each subtask have the smallest earliest completion time, and obtain the DAG offloading record of each edge server.

3) Computing resource allocation stage: edge server computing resources are allocated according to the obtained DAG offloading records.

4) Execution phase: All DAG tasks are offloaded according to the task offloading decision and computing resource allocation strategy.

This embodiment also provides a task offloading and resource allocation system based on a priority list index mechanism, which is used to implement a task offloading and resource allocation method based on a priority list index mechanism, including:

System monitoring unit: used to monitor task information from devices and system resource information;

An offloading planning unit: plans a task offloading strategy and a resource allocation method through a DAG priority list indexing mechanism according to the task information and the resource information;

Strategy implementation unit: performs user task offloading operation according to the formulated task offloading strategy and resource allocation method.

Simulation

Compare the data results of the method of the present invention (PBGTS) with the differential evolution algorithm (MDE), the heterogeneous earliest completion time algorithm (MHEFT), the multi-application multi-task scheduling algorithm (MAMTS), the particle swarm algorithm (PSO) and the genetic algorithm (GA). As can be seen from the comparison in Figure 3, the influence of α on the average response time of the system is controlled within 2s. After comparative analysis, the α of the lightweight (Lw) DAG is set to 0.9, the α of the computationally intensive (Cpi) DAG is set to 0.875, and the α of the communication intensive (Cmi) DAG is set to 0.7. As can be seen from the comparison in Figure 4, the response time of a single DAG of the present invention and the average response time of the system are better than other algorithms. As can be seen from the comparison in Figures 5 and 6, the advantages of the present invention are not affected when the computing environment changes. Whether it is changing the number of edge servers or the number of local devices, the present invention can obtain a better result. As shown in FIG7 , the maximum number of logical cores affects the effects of the present invention and other algorithms. After comparative analysis, the present invention sets the maximum number of logical cores for processing lightweight DAG, computationally intensive DAG, and communication-intensive DAG to 10, 7, and 6, respectively, to achieve the best effect.

The present invention mainly focuses on the offloading decision and resource allocation problems of DAG tasks in edge computing environments. A priority-based task offloading decision system is designed. Under the premise of reducing the overall delay for task offloading, the goal is for each subtask to obtain the earliest start time under the current circumstances. A satisfactory task offloading scheme and resource allocation scheme are found in a distributed computing environment with limited computing resources, and a task offloading and resource allocation method based on the priority list indexing mechanism is proposed.

By comprehensively considering task priority and user priority, the present invention can better solve the problem of offloading DAG tasks in a distributed computing environment, so that each subtask can obtain the earliest end time under the current resource conditions, maximize the use of computing resources in the distributed computing environment, and thus improve the execution efficiency and performance of DAG tasks; by predicting and optimizing task offloading and resource allocation, the overall delay is effectively reduced, resource utilization is improved, and efficient execution of associated tasks and reasonable allocation of resources are achieved.

The above are only preferred specific implementations of the present application, but the protection scope of the present application is not limited thereto. Any changes or substitutions that can be easily thought of by a person skilled in the art within the technical scope disclosed in the present application should be included in the protection scope of the present application. Therefore, the protection scope of the present application should be based on the protection scope of the claims.

Claims (5)

1. The task unloading and resource allocation method based on the priority list indexing mechanism is characterized by comprising the following steps:

collecting resource information of an edge server in a designated area, constructing a DAG model according to a task request of local equipment, and generating a priority index list;

Constructing a DAG model according to the task request of the local equipment, and generating a priority index list, wherein the method comprises the following steps:

The method comprises the steps of respectively setting the priority of each subtask in a DAG and the priority of each DAG, sequencing each subtask in the DAG to obtain a subtask priority list of the DAG, and sequencing the subtask priority lists of all DAGs to obtain a DAG priority list, namely the priority index list;

the method for defining the priority of each subtask in the DAG comprises the following steps:

In the method, in the process of the invention, Subtasks generated for local device I _x, I is the serial number of the subtask, x is the serial number of the local device,/>Representation/>Priority of/>Representation/>Calculated amount size of,/>For the integrated computing power of the local device I _x and the edge servers in the system,/>Representing the need/>Sending a set of dependent data subtasks,/>For/>Is one of the sub-tasks,/>Representation/>Direction/>Transmitted dependent data,/>For/>Data size of,/>To rely on the average transmission rate of data in the system;

the method of defining the priority of each DAG is:

Where G _x is the DAG task generated by local device I _x, For the start subtask of G _x, cost (G _x) is the system cost of G _x, ψ (x) is the priority of G _x;

based on the priority index list, performing target optimization by adopting a greedy algorithm and a resource allocation algorithm based on priority to obtain an associated task unloading strategy and a resource allocation method;

And executing user task unloading operation according to the associated task unloading strategy and the resource allocation method.

2. The method for task offloading and resource allocation of claim 1, wherein obtaining the associated task offloading policy and resource allocation method comprises:

Searching an unloading decision which enables each subtask to have the minimum earliest completion time through a greedy algorithm according to the priority index list, and obtaining DAG unloading records of each edge server;

And taking out each subtask according to the index of the priority index list, selecting equipment with earliest completion time for the subtask to unload, updating a subtask unloading strategy and a DAG unloading record of an edge server, and calculating the computing resource duty ratio of the DAG in the edge server according to the DAG unloading record of the edge server to obtain the associated task unloading strategy and the resource allocation method.

3. The task offloading and resource allocation method of claim 2, wherein the method for calculating a computing resource duty ratio of the DAG at the edge server according to the DAG offloading record of the edge server is:

In the method, in the process of the invention, For resource allocation proportion,/>To record whether the local device-generated DAG tasks offload subtasks to the binary variables of the edge server, ψ (N) is the priority of the DAG and N is the total number of DAG tasks.

4. The method for task offloading and resource allocation of claim 1, wherein the objective function of the associated task offloading policy and resource allocation method is an average response time for the system to complete all DAG tasks:

Where ft is the completion time of the subtask, For the ending task of G _x, G _x is the DAG task generated by local device I _x, and N is the total number of DAG tasks.

5. A priority list indexing mechanism based task offloading and resource allocation system, comprising:

and a system monitoring unit: for monitoring task information from the device and resource information of the system;

and (3) unloading the planning unit: planning a task unloading strategy and a resource allocation method through a DAG priority list indexing mechanism according to the task information and the resource information,

The method specifically comprises the following steps:

The method comprises the steps of respectively setting the priority of each subtask in a DAG and the priority of each DAG, sequencing each subtask in the DAG to obtain a subtask priority list of the DAG, and sequencing the subtask priority lists of all DAGs to obtain a DAG priority list, namely a priority index list;

the method for defining the priority of each subtask in the DAG comprises the following steps:

In the method, in the process of the invention, Subtasks generated for local device I _x, I is the serial number of the subtask, x is the serial number of the local device,/>Representation/>Priority of/>Representation/>Calculated amount size of,/>For the integrated computing power of the local device I _x and the edge servers in the system,/>Representing the need/>Sending a set of dependent data subtasks,/>For/>Is one of the sub-tasks,/>Representation/>Direction/>Transmitted dependent data,/>For/>Data size of,/>To rely on the average transmission rate of data in the system;

the method of defining the priority of each DAG is:

Where G _x is the DAG task generated by local device I _x, For the start subtask of G _x, cost (G _x) is the system cost of G _x, ψ (x) is the priority of G _x;

Policy enforcement unit: and executing user task unloading operation according to the formulated task unloading strategy and the resource allocation method.