# 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} \hline
**Group** & **Running Time** & **Weight** & **Share** \\ \hline \(G_{1}\) & \(1300\) & \(\frac{1300}{2150}=0.61\) & \([0.61\times 4]=2\) \\ \hline \(G_{2}\) & \(550\) & \(\frac{550}{2150}=0.25\) & \([0.25\times 4]=1\) \\ \hline \(G_{3}\) & \(300\) & \(\frac{300}{2150}=0.14\) & \([0.14\times 4]=0\) rounded to 1 \\ \hline \end{tabular}
\end{table} 
Table 2: Resource allocation (share calculation). \begin{table}
\begin{tabular}{c c c} \hline
**VM** & **Tasks** \\ \hline \(vm_{1}\) & \(1,4,8,12,14\) \\ \(vm_{2}\) & \(2,5,9\) \\ \(vm_{3}\) & \(3,6,10,13\) \\ \(vm_{3}\) & \(7,11\) \\ \hline \end{tabular}
\end{table} 
Table 1: Tasks assignment. Figure 3: Scheduling example. (**a**) Input DAG; (**b**) Level-based approach; (**c**) Hierarchy-based approach. to three, the LBA will obtain a better schedule, as the number of VMs is not enough to utilize the hierarchy-based scheduling strategy. In this line, a pre-processing step can be introduced to determine a lower bound on the number of required VMs by the hierarchical strategy. Such a lower bound can be calculated using the groups' weights, and whether the available VMs is enough for an envy-free distribution of the VMs among the groups. The calculation of this lower bound is outside the scope of this paper since we aim to investigate the efficiency of the proposed approach without any imposed restriction on the number of available VMs. Additionally, in the presented example, if we assume that all tasks have the same execution time, both approaches will obtain the same execution time. Such an observation highlights the importance of considering the heterogeneity of the tasks' execution times during the designing of the scheduling solution. In situations where the workflow has a balanced structure and tasks have relatively the same running time, the mechanism employed by the LBA is expected to perform efficiently. This efficiency is due to the fact that the computational and communication requirement of the workflow's levels is relatively the same. The proposed approaches do not consider the communication cost during the construction of the schedule. However, considering this cost is not expected to reduce the overall performance of the presented approaches. In the LBA, scheduling the workflow levels is performed in an isolated manner. The execution of a level's tasks starts once all tasks in the previous level have finished their execution. Accordingly, the utility function employed by the LBA can be modified to incorporate the communication cost. Tasks with data dependency constraints can be executed on the same VM if such an execution will not result in increasing the total execution time. In the HBA, the mechanism works by reducing the data dependency between the constructed groups. Such a mechanism reduces the communication cost since tasks with data dependency constraints are more likely to be executed on the same VM. With respect to the probability of hardware failure, the HBA is expected to be highly impacted by this probability compared to the LBA. In the HBA, VMs are divided between the groups based on their calculated weight. Thus, in situations where some of the VMs become unavailable due to hardware failure, the expected share of VMs will not be satisfied for all the groups. Such a situation might degrade the performance of the HBA since groups that lost some of their assigned VMs might create a performance bottleneck. In the LBA, all available VMs will be used during the execution of any level tasks. Accordingly, the probability of hardware failure might reduce the number of available VMs to execute the tasks of any given level. However, the impact of such probability will be smaller compared to the HBA since, for each level, all of the VMs will be used. ## 5 Results

This section discusses in detail the settings and the results of the experiments used to evaluate the performance of the LBA and HBA.