💻 computer science

QoS-Efficient and Near-Optimal Imprecise Computation Task Deployment for Heterogeneous Multicore Systems

This paper proposes a decomposition-based approach with a closed-loop feedback mechanism to efficiently solve the joint mapping and scheduling problem of dependent imprecise computation tasks on heterogeneous multicore systems, achieving near-optimal quality-of-service with significantly reduced computational time compared to commercial solvers.

Original authors: Linlin Zhao, Xinmei Li, Minyu Cui, Lei Mo

Published 2026-11-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Linlin Zhao, Xinmei Li, Minyu Cui, Lei Mo

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of modern computing, devices like drones, self-driving cars, and advanced robots rely on processors that are not just fast, but smartly diverse. These systems use heterogeneous multicore platforms, which are chips containing different types of processing units, each designed to handle specific kinds of work with maximum efficiency. However, these devices often face a difficult balancing act: they must complete tasks instantly to ensure safety and responsiveness, yet they are strictly limited by how much energy their batteries can provide. Running a processor faster to meet a deadline usually drains the battery much quicker. To navigate this conflict, engineers use a concept called imprecise computation. This approach acknowledges that many tasks do not need to be perfect to be useful. Instead, a task is split into two parts: a mandatory section that guarantees a basic, acceptable result, and an optional section that refines that result to be more accurate or detailed. The system can choose to run the optional part if time and energy allow, or skip it if resources are tight, ensuring the device always delivers a minimum level of performance without crashing.

The challenge for researchers has been figuring out exactly how to assign these split tasks to the different processors and decide how much of the optional work to perform, all while respecting strict deadlines and energy limits. This is a complex puzzle because the processors are different from one another, the tasks often depend on each other (where one task cannot start until another finishes), and the decisions are deeply interconnected. A new study by Linlin Zhao and colleagues at Southeast University and Linnaeus University tackles this problem by developing a method to deploy these tasks on such platforms in a way that maximizes the overall quality of the system's output. The researchers formulated the problem as a mathematical model that seeks the best possible arrangement of tasks, but they found that solving it directly is too slow and computationally heavy for real-world use.

To overcome this hurdle, the team devised a strategy that breaks the massive problem into smaller, manageable pieces that can be solved in a loop. They created a two-part system. The first part, which they call the master problem, decides which processor should handle each task and how much optional work should be attempted. The second part, the scheduling problem, takes those decisions and checks if they can actually be executed in time, respecting the order in which tasks must happen and ensuring no two tasks try to use the same processor at the same time. Crucially, the system includes a feedback mechanism. If the second part finds that a schedule is impossible to meet because a task would finish too late or use too much energy, it sends that information back to the first part. The first part then adjusts its decisions, perhaps assigning a task to a faster processor or reducing the optional work, and the cycle repeats. This closed-loop process continues until the system finds a solution that is both feasible and highly efficient.

The researchers tested their method using realistic scenarios, including applications like image processing and flight control, and compared their results against a powerful commercial solver known for finding perfect solutions, as well as other existing techniques. Their approach proved remarkably effective. In their simulations, the new method achieved 95.25% of the optimal quality of service that the commercial solver could find, yet it required only about 19.8% of the time to compute that solution. This demonstrates a significant trade-off where the system sacrifices a tiny fraction of theoretical perfection to gain a massive advantage in speed. Furthermore, the study showed that the feedback mechanism was essential; without it, the system struggled to find valid schedules for complex tasks, leading to lower overall performance. The results indicate that this decomposition method scales well, meaning it can handle a growing number of tasks without becoming unmanageably slow, making it a practical tool for the next generation of energy-efficient, real-time computing systems.

Technical Summary: QoS-Efficient and Near-Optimal Imprecise Computation Task Deployment for Heterogeneous Multicore Systems

Problem Statement
The paper addresses the joint design problem of mapping and scheduling dependent Imprecise Computation (IC) tasks on heterogeneous multicore platforms. IC tasks are characterized by a mandatory subtask (guaranteeing baseline Quality-of-Service, QoS) and an optional subtask (enhancing QoS at the cost of additional execution time and energy). The objective is to maximize system QoS by optimizing three decision variables simultaneously: task-to-processor allocation, optional cycle adjustment, and task start times.

This optimization must satisfy four critical constraints:

Real-time constraints: All tasks must complete within a scheduling horizon $H$ , and precedence relations must be respected.
Energy supply: Total energy consumption (dynamic and static) across the scheduling horizon must not exceed a budget $E_s$ .
Task dependency: Tasks modeled as Directed Acyclic Graphs (DAGs) must follow execution order.
Non-overlapping: Tasks assigned to the same processor cannot execute simultaneously.

The problem is formulated as a Mixed-Integer Nonlinear Program (MINLP). The nonlinearity arises from the interaction between binary allocation variables and continuous optional execution variables, as well as a nonlinear concave QoS function (where QoS gains diminish as optional cycles increase). The authors note that solving this MINLP directly is NP-hard and computationally expensive for large-scale systems.

Methodology
To address the computational intractability of the MINLP, the authors propose a decomposition-based solution framework called TS-DD (Topological-sorting-assisted Dual Decomposition). The framework decomposes the original problem into two subproblems solved iteratively with a closed-loop feedback mechanism:

Master Problem (MP):
- Focus: Determines task-to-core allocation ( $s_{ik}$ ) and optional execution time adjustment ( $o_i$ ).
- Technique: The binary allocation variables are relaxed to continuous variables. The problem is transformed into a convex form using auxiliary variables to handle nonlinear terms. A Lagrangian dual decomposition approach is employed, separating the problem into task allocation and optional execution subproblems.
- Solution: The dual problem is solved using a subgradient method to iteratively update Lagrange multipliers, recovering near-optimal binary allocation decisions.
Scheduling Problem (SP):
- Focus: Determines task execution sequences ( $u_{ij}$ ) and start times ( $t^s_i$ ) based on the allocation and execution time decisions from the MP.
- Technique: A dependency-aware task sorting algorithm based on topological sorting is used. It calculates the latest completion time of predecessors and the earliest availability time of the assigned processor to determine valid start times without violating precedence or non-overlap constraints.
Closed-Loop Feedback Mechanism:
- Function: The SP acts as a feasibility check. If the schedule generated by the SP violates the global deadline ( $H$ ), the residual time is fed back to the MP.
- Mechanism: The feedback updates the Lagrange multipliers (specifically those related to timing and optional execution bounds) in the MP. This increases the "cost" of optional execution or forces the selection of faster processors in the next iteration, thereby guiding the MP toward a solution that is both high-QoS and schedulable.

Key Contributions

Joint-Design Problem Formulation: The paper formulates the QoS-aware task deployment on heterogeneous multicores as an MINLP, explicitly modeling the trade-off between optional execution, energy, and real-time constraints using a nonlinear QoS function.
Decomposition-Based Solution: A novel framework is developed that decouples the complex MINLP into a Master Problem (allocation/cycle adjustment) and a Scheduling Problem (sequence/timing), solved via dual decomposition and topological sorting.
Constraint-Aware Feedback: A closed-loop mechanism is introduced where scheduling infeasibility (deadline violations) directly influences the allocation and optional cycle decisions in the Master Problem, improving overall solution quality and schedulability.
Complexity Reduction: The proposed method reduces the computational complexity from exponential (typical of direct MINLP solvers) to approximately linear with respect to the number of tasks ( $O(N_{max}N)$ ), making it scalable for large DAGs.

Experimental Results
The authors evaluated the method using real-world application DAGs (LE, JPEG, FFT, MW) and randomly generated graphs on a 5-core heterogeneous platform.

Solution Quality: The proposed TS-DD method achieved 95.25% of the optimal QoS obtained by the commercial solver Gurobi. This outperformed a Genetic Algorithm (GA, ~90.25%) and a two-step heuristic (HEU, ~75.00%).
Computational Efficiency: TS-DD required only 19.8% of the computation time used by Gurobi. While HEU was faster, it yielded significantly lower QoS.
Scalability: The computation time grew approximately linearly with the number of tasks, confirming the theoretical complexity analysis.
Feedback Mechanism Impact: Experiments comparing TS-DD with a version lacking the feedback loop (NoFB) showed that the feedback mechanism significantly improved both QoS (especially in complex DAGs with high dependency intensity) and the task schedulability rate (96.7% vs. 80.0%).

Significance and Claims
The paper claims that the proposed method offers a favorable trade-off between solution quality and computational efficiency, making it suitable for resource-constrained heterogeneous systems where real-time response and energy efficiency are critical. The authors emphasize that their approach handles the coupling of heterogeneous platform characteristics, task dependencies, and nonlinear QoS models more comprehensively than existing energy-aware or QoS-aware methods. The closed-loop feedback is highlighted as a key innovation that ensures the theoretical allocation decisions translate into feasible, real-world schedules without sacrificing too much QoS.

Technical Summary: QoS-Efficient and Near-Optimal Imprecise Computation Task Deployment for Heterogeneous Multicore Systems

More like this