# Review of Task-Scheduling Methods for Heterogeneous Chips
## 4 Research Status of the Task-Scheduling Algorithm
### Static Scheduling Algorithm  
A static scheduling algorithm is an algorithm in which a heterogeneous chip determines scheduling policies according to predetermined resource allocation and task characteristics before task execution. It suits scenarios where task and resource requirements are fixed and do not change with time. In static scheduling algorithms, the task execution order, resource allocation, and scheduling are predetermined before the program runs, which usually relies on prior analysis of the task and exhaustive knowledge of the system resources. Common static scheduling algorithms include the max-min algorithm [19], the min-min algorithm [19], and the minimum completion time algorithm [8].  
[PERSON] et al. [4] proposed the heterogeneous earliest-finish-time (HEFT) algorithm. Figure 6 illustrates the process of HEFT list scheduling. The principle of HEFT is to calculate task priorities and arrange them in descending order. For each task, a processor that can achieve the earliest completion time and consider communication overhead is selected to achieve efficient task-scheduling optimization in a heterogeneous environment. [PERSON] et al. [20] proposed a variant of the HEFT algorithm, which prioritizes the task by calculating the average execution time and communication cost of the task on each heterogeneous chip processing unit when making the scheduling decision, and considers the subsequent sub-tasks of the task through the foresight mechanism to achieve the overall optimum. The static scheduling algorithm calculates the optimal or approximately optimal scheduling scheme in advance, thus reducing the time overhead of decision-making when the system runs and ensuring that tasks are performed on a strict schedule. However, in the static task-scheduling direction, most existing algorithms have disadvantages such as unbalanced task allocation and too long of a total task execution time [21].  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Description** & **Limitation** \\ \hline \multirow{2}{*}{Static} & Determines the scheduling plan takes place & \multirow{2}{*}{Limited adaptability to runtime dynamics.} \\  & before task execution begins. & \\ \hline \multirow{2}{*}{Dynamic} & Adapts to dynamic changes in tasks and & \multirow{2}{*}{\begin{tabular}{c} Incurs significant computational and \\ communication overheads from frequent \\ re-evaluations. \\ \end{tabular} } \\  & system resources. & & \\ \hline \multirow{2}{*}{Heuristic} & Uses empirical rules or heuristic rules to quickly & \multirow{2}{*}{\begin{tabular}{c} Computational intractability for large-scale \\ problems due to NP-hard complexity. \\ \end{tabular} } \\  & generate acceptable standing plans without & \\ \multicolumn{2}{c}{guaranteeing a globally optimal solution.} & \\ \hline \multirow{2}{*}{Optimization} & Relies on mathematical models and optimization & \multirow{2}{*}{\
\begin{tabular}{c} Solution quality varies unpredictably and may \\ converge to local optima. \\ \end{tabular} } \\  & algorithms to minimize or maximize a specific & \\ \multicolumn{2}{c}{objective function to obtain an optimal solution.} & \\ \hline \multirow{2}{*}{Hybrid} & Combines multiple scheduling algorithms to & \multirow{2}{*}{
\begin{tabular}{c} Increases design complexity and sensitivity to \\ parameter tuning. \\ \end{tabular} } \\  & leverage the strengths of different algorithms. & \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison of task-scheduling algorithms.