# MASA: Multi-Application Scheduling Algorithm for Heterogeneous Resource Platform
## 3 A Multi-Application Scheduling Formal Definition
### Optimization Objective  
The simulation environment for heterogeneous resources includes m independent jobs, referred to as \(\mathrm{J}=[\mathrm{j}_{1},\ldots,\mathrm{j}_{\mathrm{m}}]\), and K heterogeneous processing elements (PE), referred to as \(\mathrm{P}=[\mathrm{p}_{1},\mathrm{p}_{2},\ldots,\mathrm{p}_{\mathrm{K}}]\). It is necessary to investigate the impact of randomly arriving jobs (streaming mode) on the scheduling algorithm in different mission scenarios of varying scales, thus the _scale_ shown in Algorithm 1 is an adjustable parameter value. ```
1. Input: Job's profile \(\mathrm{J}=[\mathrm{j}_{1},\ldots,\mathrm{j}_{\mathrm{m}}]\), PE's profile \(\mathrm{P}=[\mathrm{p}_{1},\ldots,\mathrm{p}_{\mathrm{K}}]\), Maximum simulation length CLK, Job Queue capacity maximum C, job inject interval' expectation _Scale_
2. Output: Average execution time for multi-application (avg_jET)
3. for each episode do
4. clk=0
5.clk\({}_{\mathrm{inj}}\sim\exp\Bigl{(}\frac{1}{Scale}\Bigr{)}\)
6. repeat
7. if Job Queue capacity maximum not reached
8. inject job into the Job Queue every \(\mathrm{clk}_{\mathrm{inj}}\)
9. end if
10. for all tasks for each job in the job Queue do
11. Task coding based on feature networks
12. Task ordering based on policy network
13. for Ready Task do
14. Mapping task to PE based on heuristic algorithm
15. end for
16. end for
17. clk \(\leftarrow\) clk + 1
18. until clk\(\rightarrow\)CLK
19. Computer avg_jET using Equation (5)
20. end for
```  
**Algorithm 1**Flowchart of Heterogeneous Resource Simulation Environment  
Each job is modeled as a DAG, denoting the job DAG as \(\mathrm{G}\{\mathrm{N},\mathrm{E}\}\), in which each task \(\mathrm{n}_{\mathrm{i}}\in\mathrm{N}\) represents the software components that composed the application, and the directed edge \(\mathrm{e}_{\mathrm{i},\mathrm{j}}\in\mathrm{E}\) is the link from task \(\mathrm{n}_{\mathrm{i}}\) to \(\mathrm{n}_{\mathrm{j}}\). For any \(\mathrm{n}_{\mathrm{i}}\in\mathrm{N}\), the parent node has a higher priority than the child nodes. \(\mathrm{comp}\left(\mathrm{n}_{\mathrm{i}},\mathrm{p}_{\mathrm{m}}\right)\) represents the computational execution time of task \(\mathrm{n}_{\mathrm{i}}\) on \(\mathrm{p}_{\mathrm{m}}\), as provided by the profile of the heterogeneous resource PE. \(\mathrm{comm}\left(\mathrm{n}_{\mathrm{i}},\mathrm{n}_{\mathrm{j}}\right)\) represents the communication delay from \(\mathrm{n}_{\mathrm{i}}\) to \(\mathrm{n}_{\mathrm{j}}\) as shown in Equation (1). \(\mathrm{w}_{\mathrm{i},\mathrm{j}}\) is the transmission data volume between \(\mathrm{n}_{\mathrm{i}}\) and \(\mathrm{n}_{\mathrm{j}}\), task \(\mathrm{n}_{\mathrm{i}}\) is mapped to processor \(\mathrm{p}_{\mathrm{m}}\), denoted \(\mathrm{P}_{\mathrm{m}\left(\mathrm{n}_{\mathrm{i}}\right)}\cdot\mathrm{B} \Bigl{(}\mathrm{p}_{\mathrm{m}\left(\mathrm{n}_{\mathrm{i}}\right)}\cdot\mathrm{P }_{\mathrm{n}\left(\mathrm{n}_{\mathrm{j}}\right)}\Bigr{)}\) denotes the bandwidth between \(\mathrm{p}_{\mathrm{m}}\) and \(\mathrm{p}_{\mathrm{n}}\). For task \(\mathrm{n}_{\mathrm{i}}\) and its parent node \(\mathrm{pred}\left(\mathrm{n}_{\mathrm{i}}\right)\), assignment to different PEs incurs communication overhead, and frequent switching of PEs leads to an increase in task execution time.