# MASA: Multi-Application Scheduling Algorithm for Heterogeneous Resource Platform
## 2 Related Work  
The complexity of DAG scheduling has been demonstrated to be NP-complete [11], and its complexity is greatly increased when PE resources are heterogeneous. Scheduling strategies can broadly be classified into two types: dynamic and static DAG scheduling. In static DAG scheduling, the DAG information is known in advance (at the beginning of the scheduling process). Conversely, the DAG topology in dynamic scheduling is unknown in advance, and all configuration information is obtained at runtime. Scheduling decisions are then made in real time. Most current static scheduling algorithms on heterogeneous resources aim to optimize the time required to execute a single DAG. For example, the Mixed Integer Programming approach uses objective functions and constraints to formulate the task scheduling problem, exchanging computational and time complexity for an optimal solution [12]. Genetic algorithms and particle swarm algorithms based on heuristic stochastic search algorithms can find the optimal value of the parameter set through a large number of iterative experiments, and such algorithms can be applied to multi-objective optimization problems [13; 14; 15; 16]. Heuristic-based list task scheduling algorithms demonstrate their high execution capabilities in a heterogeneous processor resource. HEFT (Heterogeneous Earliest Finish Time) is the dominant algorithm for heterogeneous static list scheduling [17]. HEFT assigns priority to each task based on the critical path length, and later assigns PEs to tasks with the highest priority on the list based on the earliest finish time (EFT),mapping the task to the active PE with the minimum EFT value; in addition, HEFT uses a scheme that tries to insert tasks into the PE's idle time slots, and CPATH is a critical path aware dynamic scheduler for heterogeneous systems that prioritizes tasks in the DAG based on the lowest-cost longest-path approach, submitting high priority tasks to high frequency PEs and low frequency PEs when work is enabled. This scheduling approach does not consider communication costs for tasks [18]. These algorithms have been further expanded and extended in recent years and applied to the scheduling of real hardware platforms, such as FPGA [19]. Dynamic scheduling algorithms for multiple DAGs are also investigated, and many machine learning based scheduling algorithms for dynamic scheduling scenarios are described below. [PERSON] et al. proposed an adaptive scheduler (ADS) based on RL with the aim of improving reliability and minimizing completion time. However, ADS dynamically schedules DAGs with higher-level DAGs from the priority level of DAGs alone, and the large computational granularity is not suitable for radio application streaming analysis [3; 20]. [PERSON] et al. investigated how to dynamically schedule dynamic applications on heterogeneous embedded systems and proposed energy-efficient scheduling algorithms for the optimization of the system energy consumption problem. However, this paper uses an objective function and a constraint formulation to design the scheduling problem, which has a relatively high time complexity [21]. [PERSON] et al. proposed SoCRATE, a task scheduling scheme for the domain of System-on-a-Chip based on the DRL algorithm. SoCRATE employs an integrated network structure to generate scheduling decisions. This results in a higher level of complexity in the neural network's decision space, which prevents the neural network from converging to a steady state more quickly [22]. [PERSON] et al. designed a heterogeneous-aware multilevel scheduler, HetSched, which utilizes information about the runtime state of the underlying heterogeneous SoCs as well as the real-time nature of the application to meet the growing throughput requirements of self-driving cars. However, it takes into account the task security level and the granularity of task division is large, which is not adapted to the RF application environment [4]. [PERSON] et al.