# Structure-Aware Scheduling Methods for Scientific Workflows in Cloud
## 4 Algorithmic Solutions
### Hierarchy-Based Approach
#### 4.2.2 Resource Allocation
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Workflow** & **Algorithm** & **Makespan (Second)** & **Cost (Cent/Hour)** \\ \hline \multirow{4}{*}{**LIGO**} & HBA & 1578 & 1640 \\  & LBA & 1788 & 1640 \\  & PBWS & 1594 & 4659 \\  & RDAS & 1643 & 4243 \\  & HEFT & 1300 & 4974 \\ \hline \multirow{4}{*}{**CyberShake**} & HBA & 533 & 315 \\  & LBA & 675 & 380 \\  & PBWS & 550 & 294 \\  & RDAS & 750 & 541 \\  & HEFT & 712 & 516 \\ \hline \multirow{4}{*}{**Montage**} & HBA & 242 & 1500 \\  & LBA & 379 & 1500 \\  & PBWS & 956 & 497 \\  & RDAS & 720 & 410 \\  & HEFT & 815 & 446 \\ \hline \multirow{4}{*}{**Sipht**} & HBA & 4464 & 2320 \\  & LBA & 4820 & 2440 \\ \cline{1-1}  & PBWS & 8465 & 3282 \\ \cline{1-1}  & RDAS & 6991 & 2862 \\ \cline{1-1}  & HEFT & 7516 & 2974 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison of the experimental results. as compared to the HBA algorithm for cost, which was due to the grouping strategy used by both algorithms. The LBA algorithm achieved better makespan results as compared to the RDAS and HEFT algorithms, whereas the HBA approach outperformed all other algorithms. The HBA behavior was mainly due to the parallel executions of groups, which conferred a significant advantage on the HBA algorithm. **Montage**: Most montage workflow levels have a small number of tasks, and most levels in the workflow have one task each, which increases the data dependency between levels. The proposed approaches demonstrated the best behavior for makespan compared to the benchmark algorithms (Figure 6), in which the utility-based mechanism used in the LBA algorithm reduced the time required to execute tasks by >50% compared to the benchmarks. The utility-based mechanism demonstrated the highest reduction when applied under the HBA. Such performance fully utilized the resource shares while applying the proposed scheduling approaches. Nonetheless, the proposed algorithms also attained the highest cost values, which was due to the structure of the Montage workflow. Therefore, having numerous VMs waiting to execute a single task (idle mode) increases the execution cost. **SIPHT**: The SIPHT workflow structure is unorganized, where levels have different numbers of tasks with different computational requirements. The SIPHT workflow results are illustrated in Figure 7 where the two proposed algorithms significantly outperformed the benchmark algorithms in terms of both makespan and execution cost. This result was linked to the task-grouping strategies in workflow structure handling. The SIPHT workflow structure emphasized the advantages of the LBA and HBA algorithms that treat task groups as sequestered objects, which minimized the inter-dependency between those groups during execution. Furthermore, the fair share resource distribution mechanism used in the proposed algorithms increased the resource utilization efficiency. The hierarchy-based approach performed best for execution cost and makespan compared to the other algorithms due to the parallel executions of the groups. Figure 4: LIGO workflow experiment results. (a) makespan \((s)\); (b) cost \((e)\). Figure 5: CyberShake workflow experiment results. (a) makespan \((s)\); (b) cost \((e)\). ## 6 Conclusions and Future Work

The structure of the workflow impacts the scheduling efficiency. In this paper, two workflow scheduling approaches are presented to utilize the structure-related information. By employing a look ahead strategy, the HBA scheduling approach has shown its advantages compared to the LBA strategy. Such advantages are due to the fact that the HBA works to minimize the data dependency between the task groups. As illustrated in the results section, the efficiency of the HBA is influenced by the number of available VMs. Increasing the number of available VMs further increases the advantages of the VMs' fair share division strategy. In situations where the number of available VMs is relatively small, the discussion has shown that the LBA is more likely to achieve better performance compared to the HBA.