CN-117573300-B - Heterogeneous platform approximate calculation task optimization mapping method based on DVFS and DPM

CN117573300BCN 117573300 BCN117573300 BCN 117573300BCN-117573300-B

Abstract

The invention discloses a heterogeneous platform approximate calculation task optimization mapping method based on DVFS and DPM, which comprises the steps of firstly modeling a real-time task with correlation into an approximate calculation task model, obtaining a task Directed Acyclic Graph (DAG), a task correlation matrix and six-tuple representing task characteristics, introducing a mechanism of DVFS and DPM combination based on a heterogeneous multi-core platform, constructing a task mapping problem description based on QoS and energy combination optimization, linearizing the task mapping problem by using a variable substitution method and a Big-M reconstruction method to obtain an optimal solution through a Gurobi solver, designing a heuristic algorithm with low calculation complexity by using a task layering method and a greedy algorithm, and improving the expandability of the mapping method. The method adopts a DVFS+DPM combined optimization mechanism to improve the QoS of the system on the premise of meeting the constraints of the real-time performance, the energy efficiency and the reliability of the system.

Inventors

MO LEI
ZHU HAOTONG
LI XINMEI
CAO XIANGHUI

Assignees

东南大学

Dates

Publication Date: 20260508
Application Date: 20230927

Claims (5)

1. The heterogeneous platform approximate calculation task optimization mapping method based on DVFS and DPM is characterized by comprising the following steps of: the method comprises the steps of S1, modeling a correlation real-time task into an approximate calculation task, wherein the modeling can obtain a task Directed Acyclic Graph (DAG), a task correlation matrix and a six-tuple for representing task characteristics; s2, introducing a DVFS and DPM combined mechanism based on a heterogeneous multi-core platform, using Multi-core processor platform of heterogeneous processor Describing a platform model, all processors support DVFS and DPM, and computing tasks by combining the heterogeneity of the processors and DVFS technology In a processor At a frequency of The execution time of execution is Wherein, the method comprises the steps of, For processors In the execution of tasks Is used for the execution efficiency of the (c) in the (c), And give each task Defining processor allocation index And frequency allocation index , wherein, Indicating that tasks are assigned to processors At a frequency of Is executed; And The number of execution cycles of the forced portion and the number of execution cycles of the selectable portion of each approximate calculation task; the processor autonomously selects to enter an idle state or a dormant state according to the idle time of the processor; S3, completing description of task mapping problems based on QoS and energy joint optimization, wherein the description at least comprises task allocation, frequency selection, instantaneity, task non-preemption, task correlation, processor utilization rate and energy consumption constraint; s4, aiming at the optimization problem proposed in the S3, using a variable substitution method and a Big-M reconstruction method to process nonlinear items in the problem, linearizing the task mapping problem, and obtaining an optimal solution through a Gurobi solver; S5, designing a heuristic algorithm with low computational complexity by using a task layering method and a greedy algorithm, and improving the expandability of the mapping method; S51 task-processor assignment and frequency-task coarse assignment, the objective being to keep as much as possible On the premise of meeting the energy constraint and simultaneously reducing the task execution time as much as possible, An upper limit on the number of optional partial execution cycles, the steps specifically comprising: s511, selecting processor allocation and frequency selection which generate minimum energy consumption increment of each task through a polling mode and a greedy algorithm, and calculating the starting time and the ending time of the task; S512 by comparing processor idle times And Judging the state selection when the processor is idle, when the idle time is more than or equal to The processor enters a dormant state when the processor is in a dormant state, otherwise, the processor keeps an idle state; s513, calculating the total energy consumption; s514, if the generated task scheduling scheme does not meet the energy constraint, reducing If the scheme meets the energy constraint and has surplus energy, the surplus energy is utilized to improve the V/F level of the processor so as to reduce the task execution time; S52, task frequency & optional execution period joint adjustment, aiming at solving real-time constraint by reducing Reducing task execution time and simultaneously bringing energy surplus, increasing V/F grade by using the excess energy, and reducing task execution time again, so that the energy and real-time constraint are continuously adjusted until the energy and real-time constraint is satisfied; S53, optionally performing cycle readjustment by directly lowering To satisfy energy and real-time constraints, define parameters The parameter indicates the time it takes for a task to execute one cycle, all tasks are followed Descending order of decreasing the number of selectable partial cycles in sequence The minimum number of selectable execution cycles sacrificed is achieved so that the real-time constraints reach the standard.
2. The method for optimizing and mapping the task of the heterogeneous platform approximate calculation based on the DVFS and the DPM according to claim 1, wherein the real-time task model in the step S1 is composed of Describing a real-time system from a set of related, non-preemptive, approximate computing tasks, which are abstracted into a Directed Acyclic Graph (DAG), the relevance of the tasks using a binary matrix To describe if the task And (3) with Related and task At the position of Previously execute, then Otherwise, the device can be used to determine whether the current, Tasks in a task set Can use six-tuple The representation, wherein, Is a task Is used for the duration of the cut-off time of (c), And The start time and the end time of the task, respectively.
3. The method for optimizing and mapping a heterogeneous platform approximate calculation task based on DVFS and DPM as claimed in claim 2, wherein in said step S3, task allocation and frequency selection refer to each task Can be allocated to only one processor And a frequency of Thus, the task allocation, frequency selection constraints are: ; Wherein, the If a task Is allocated to the processor At a frequency of Execute then Otherwise ; The real-time performance refers to each task The execution time of (a) cannot exceed the deadline The task end time cannot exceed the scheduling period Thus the real-time constraints are: ; ; ; ; the task non-preemption refers to that the end time of the task executed first on each processor is earlier than the start time of the task executed later, so the task non-preemption constraint is: ; ; ; ; ; ; ; Wherein, the Is a binary variable if a task And tasks Are all in the processor Are executed on and tasks Is a task Is to follow the task Otherwise If a task Is a processor The first task is Otherwise If a task Is a processor Last task, then Otherwise ; Is a binary variable if a task In a processor Is executed on, then Otherwise ; Is a binary variable if no task is on the processor Is executed on, then Otherwise 。
4. The method for optimizing and mapping a task for heterogeneous platform approximate computation according to claim 3, wherein in step S3, task dependencies refer to tasks having dependencies whose end times are earlier than start times of subsequent tasks, so that task dependency constraints are specifically: ; ; The processor utilization refers to the scheduling period occupied by each task occupied time on the processor The processor utilization constraint is therefore in particular: ; The energy consumption limit means that the total energy consumption of the system cannot exceed the energy budget The energy consumption limit constraint is specifically: ; Wherein, the Is a binary variable if the processor is performing a task After switching from idle state to dormant state Otherwise ; For processors At a frequency of Power consumption when executing a task; For processors At a frequency of Power consumption in idle state; For processors Power consumption in sleep state; For processors Energy consumption for switching from an idle state to a dormant state; budgets the energy of the system.
5. The method for optimizing and mapping the task of the heterogeneous platform approximate calculation based on the DVFS and the DPM according to claim 4, wherein in the step S4, real-time constraint, task non-preemptive constraint, task dependency constraint, processor utilization constraint and energy consumption constraint are respectively linearized into: ; ; ; ; ; ; Wherein, the Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Binary variables of (a); Is a substitute for nonlinear terms Binary variables of (a); Is a substitute for nonlinear terms Binary variables of (a); Is a substitute for nonlinear terms Binary variables of (a); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Continuous variable of (2); Is a substitute for nonlinear terms Is a continuous variable of (a).

Description

Heterogeneous platform approximate calculation task optimization mapping method based on DVFS and DPM Technical Field The invention belongs to the technical field of task scheduling of multi-core processors, and mainly relates to a heterogeneous platform approximate calculation task optimization mapping method based on DVFS and DPM. Background Compared with the isomorphic multi-core processing platform, the heterogeneous multi-core processing platform has the advantages of low cost, small size, high customizable degree and the like because the heterogeneous multi-core processing platform can meet the diversified requirements of functions and nonfunctional, can meet more complex application background, and becomes a core component of the information physical system. In heterogeneous multi-core processing platforms, the computational power of a single node is often limited based on reduced power consumption, which makes some tasks not completed by the node in time, resulting in timing errors. Thus, under limited energy, imprecise calculations can be used to produce acceptable approximation results before the task deadline. Aiming at the situation, a task description mode with an elastic mechanism is introduced, namely, a task model is calculated (IMPRECISE COMPUTATION, IC) in an approximate mode, so that the energy consumption of the system and the accuracy of a calculation result can be balanced, and the utilization rate and the reliability of the system are improved. Therefore, the design of the mapping algorithm of the approximate calculation task on the heterogeneous multi-core platform has important practical significance. Today, task mapping research of heterogeneous multi-core processing platforms has achieved many research results, but there are also problems that 1) in a task scheduling method based on energy optimization, the execution period of tasks is fixed, the resource utilization rate of a system is low in the scheduling process, meanwhile, the QoS of the system is fixed, and the QoS of the system cannot be improved through task adjustment, 2) the research of heterogeneous multi-core processing platforms generally uses DVFS technology or DPM technology alone to optimize the system power consumption, but joint optimization of DVFS and DPM is rarely considered, and 3) the joint optimization task mapping problem based on QoS and energy has higher computational complexity for heterogeneous multi-core processing platforms. Disclosure of Invention Aiming at the problem that the QoS of a system cannot be improved by a multi-task mapping method in the prior art, the joint optimization of DVFS and DPM technologies is not considered, the invention provides a heterogeneous platform approximate calculation task optimization mapping method based on DVFS and DPM, which is characterized in that firstly, real-time tasks with relevance are modeled into approximate calculation task models, so that a task Directed Acyclic Graph (DAG), a task relevance matrix and six-tuple representing task characteristics can be obtained, then, a mechanism of combining the DVFS and the DPM is introduced based on a heterogeneous multi-core platform, the task execution efficiency can be improved, the task mapping problem description based on QoS and energy joint optimization is constructed, the description at least comprises task allocation, frequency selection, instantaneity, task non-preemption, task relevance, processor utilization rate and energy consumption constraint, the task mapping problem is linearized by using nonlinear terms in a variable substitution method and a Big-M reconstruction method processing problem, the task mapping problem is solved by a Gurobi solver optimal solution, and a low-calculation complexity algorithm is designed by using a task layering method and a greedy algorithm, and the scalability of the mapping method is improved. The method adopts a DVFS+DPM combined optimization mechanism to improve the QoS of the system on the premise of meeting the constraints of the real-time performance, the energy efficiency and the reliability of the system. In order to achieve the purpose, the technical scheme adopted by the invention is that the method for optimizing and mapping the approximate calculation tasks of the heterogeneous platform based on DVFS and DPM comprises the following steps: the method comprises the steps of S1, modeling a correlation real-time task into an approximate calculation task, wherein the modeling can obtain a task Directed Acyclic Graph (DAG), a task correlation matrix and a six-tuple for representing task characteristics; s2, introducing a DVFS and DPM combined mechanism based on a heterogeneous multi-core platform; S3, completing description of task mapping problems based on QoS and energy joint optimization, wherein the description at least comprises task allocation, frequency selection, instantaneity, task non-preemption, task correlation, processor utilization rate and energy c