# Review of Task-Scheduling Methods for Heterogeneous Chips
## 4 Research Status of the Task-Scheduling Algorithm
### Optimized Scheduling Algorithm  
The task-scheduling algorithm based on optimization usually adopts mathematical models and complex optimization techniques, such as linear programming and integer programming, to determine the optimal scheduling scheme [29]. Optimization-based task-scheduling algorithms for heterogeneous chips represent a mathematically rigorous approach to task allocation and execution sequencing, where the scheduling problem is formulated as a constrained optimization model to systematically minimize objectives such as makespan, energy consumption, or resource contention. Implementation typically involves three stages: abstracting tasks and hardware into computational graphs and capability matrices, formulating objectives with constraints on precedence, resource limits, and PE compatibility, and deploying solvers such as branch-and-bound for exact solutions or swarm intelligence for scalability. Compared with the heuristic scheduling algorithm, the optimization-based method optimizes the scheduling effect through rigorous mathematical modeling, assuming that the computational resources allow it. Optimization of scheduling algorithms can provide a globally optimal solution.  
[PERSON] et al. proposed a classification-based scheduling algorithm with minimal hardware overhead for many instruction set architecture (ISA) scenarios [30]. It utilizes a smaller set of microarchitectural parameters obtained via online performance counters to determine the most affine ISA for upcoming program phases. [PERSON] et al. modeled the task and heterogeneous chip, represented the task diagram with the Kahn process network model [31], assigned the task to the processing unit, and considered its execution time and memory access time. The task-scheduling scheme was then encoded as chromosomes, and new populations were generated by genetic operator operation, where parental chromosomes were selected according to different rules and progeny chromosomes are generated. Finally, the chromosome was evaluated according to the defined fitness function, and the Pareto optimal solution was obtained as the final scheduling scheme. [PERSON] et al. proposed a method to model the architecture model (including processor, bus, memory, etc.) and task map (including task execution time, data dependence, traffic, etc.) [32]. They also mapped the task to a heterogeneous chip processing unit into a linear planning (integer linear programming, ILP) problem, represented the task assignment through decision variables, and solved the task-scheduling scheme according to the constraints and target function. The ILP formula was then extended to handle pipeline scheduling, considering constraints such as pipeline stage assignments and communication tasks to optimize the overall performance. However, the complexity of this approach grew exponentially with the problem size and heterogeneous chip complexity, requiring significant computational resources to solve it, making a trade-off between optimization effect and computational cost in practical applications.