Performance Estimation of Task Graphs Based on Path Profiling

Abstract

Correctly estimating the speed-up of a parallel embedded application is crucial to efficiently compare different parallelization techniques, task graph transformations or mapping and scheduling solutions. Unfortunately, especially in case of control-dominated applications, task correlations may heavily affect the execution time of the solutions and usually this is not properly taken into account during performance analysis. We propose a methodology that combines a single profiling of the initial sequential specification with different decisions in terms of partitioning, mapping, and scheduling in order to better estimate the actual speed-up of these solutions. We validated our approach on a multi-processor simulation platform: experimental results show that our methodology, effectively identifying the correlations among tasks, significantly outperforms existing approaches for speed-up estimation. Indeed, we obtained an absolute error less than 5 % in average, even when compiling the code with different optimization levels.

Appendix 1: Example of Application of Task Graph Estimation Technique based on Path Profiling

This appendix shows how the proposed methodology is applied to estimate the performance of the example presented in Sect. 2 when SolB is considered: Task1 and Task3 are assigned to $CPU_\alpha , Task2a$ and Task2b are assigned to $CPU_\beta$. The resulting $\overline{HTG}$ is shown in Fig. 7: the edge $<Task1,Task3>$ is added to represent the scheduling order, as discussed in Sect. 5.2. The estimation starts with the application of the Hierarchical Path Profiling on the host machine, which results are reported in Table 11. For the sake of readability, we report also the sequence of basic blocks which compose each path, even if this information is equivalent to the one provided by the corresponding CRP. The order of the Control Dependence Regions in a Control Region Path is not relevant since the basic blocks are interleaved during the execution. The table shows how HPP is able to profile the paths and and to collect correlations about the execution of basic blocks before and after a loop, even if it is executed, with a representation that can be easily mapped onto the HTG.

Fig. 7

$\overline{HTG}$ created from HTG considering SolB. a Task Graph of $L_0$. b Task Graph of $L_5$

Table 11 Results of applying the Hierarchical Path Profiling Technique to the example of Fig. 1

Before estimating the execution time ($HTC_0$) of func_0, $HTC_5$ is estimated as follows:

• 1. the contribution $BC_{i,t}$ of each basic block is computed (line 2 of Algorithm 1): the results are reported in Table 12a (e.g. $BC_{9,6} = f(o_{13}) = 1$ since $o_{13}$ is the only statement of $BB_9$);

• 2. the contribution $\overline{BC}_{i,t}$ of each basic block including nested loops is computed (lines 4 and 6—Table 13a—e.g. $\overline{BC}_{7,6} = BC_{7,6}$ since Task6 is simple);

• 3. the contribution $CC_{c,t}$ is computed summing the contribution of the single basic blocks (line 9—Table 14a—e.g. $CC_{E,6} = \overline{BC}_{6,6} + \overline{BC}_{6,9} = 3$ since $CDR_E$ is composed of $BB_6$ and $BB_9$);

• 4. the contributions of the single Control Dependence Regions are summed to compute the contributions $TPC_{p,t}$ (line 13—Table 15a—e.g. $TPC_{ {{}}, 6} = CC_B + CC_E + CC_I = 6$ since path is composed of B, E and I);

• 5. the overhead for the task management is added to $TPC_{p,t}$ to compute $\overline{TPC}_{p,t}$; since there is not any overhead cost in this task graph, $\overline{TPC}_{p,t} = TPC_{p,t}$ (line 15—Table 16a—$\overline{TPC}_{ {{}}, 6} = TPC_{ {{}}, 6}$ since Task6 has not overhead cost);

• 6. the start and end times of each task are computed (lines 20 and 21—Table 17a—e.g. $START_{ {{}}, 6} = STOP_{{{}}, Entry5}$ since $Entry_5$ is the only predecessor of Task6; $STOP_{ {{}}, 6} = START_{ {{}}, 6} + \overline{TPC}_{ {{}}, 6}$); the execution times of the two paths are computed as the end time of task Exit (line 25—last line of Table 17a—e.g. $PC_{{}} = STOP_{ {{}}, Exit_5}$);

• 7. the estimation of the whole $HTG_5$ can be computed (line 27):

  $$\begin{aligned} HTC_5=N_5 \cdot \frac{PC_{{}}\cdot f_{{}}+PC_{{}}\cdot f_{{}}}{f_{{}}+f_{{}}}=10 \cdot \frac{105\cdot 100 + 6\cdot 0}{100+0}=1050 \end{aligned}$$

  (13)

After $HTC_5$ has been estimated, $HTC_0$ can be estimated in the same way and Fig. 8 shows how the different contributions are combined. These contributions are:

• 1. the contribution of each basic block $BC_{i,t}$ (lines 2), obtained from the clock cycles of Table 1; the results are reported in Table 12b;

• 2. the contribution of each basic block including nested loops $\overline{BC}_{i,t}$ (lines 4 and 6); the results are reported in Table 13b; note in particular that $\overline{BC}_{5,2a}=BC_{5,2a} +HTC_5=1+1050$;

• 3. the contribution of each Control Dependence Region $CC_{c,t}$ (line 9); the results are reported in Table 14b;

• 4. the contribution of each path to each task $TPC_{p,t}$ (line 13); the results are reported in Table 15b;

• 5. the contribution of each path to each task, along with the overhead cost, $\overline{TPC}_{p,t}$ (line 15); the creation cost (50) is added to Task1 and Task2a; the synchronization and destruction cost (10) is added to Task3 and Task2b; the results are reported in Table 16b;

• 6. $START_{p,t}$ and $STOP_{p,t}$ (lines 20 and 21); the results are reported in Table 17b, where the selected topological order is: $Entry_0$-Task0-Task1-Task2a-Task2b-Task3-Task4-$Exit_0$;

• 7. the contribution of each path $PC_{p}$ (line 25): the results are reported in the last line of Table 17b;

• 8. $HPC_0$ in the two cases presented in Sect. 2:

• the CRPs executed are $P_{{}}$ and $P_{{}}$, so the execution time estimated for the parallel version is:

  $$\begin{aligned} HTC_{0} = \frac{PC_{{}} \cdot f_{{}} + PC_{{}} \cdot f_{{}}}{f_{{}} + f_{{}}} = \frac{4171 \cdot 5 + 1126 \cdot 5}{5 + 5} = 2648.5 \end{aligned}$$

  (14)

• the CRPs executed are $P_{{}}$ and $P_{{}}$, so the execution time estimated for the parallel version is:

  $$\begin{aligned} HTC_{0} = \frac{PC_{{}} \cdot f_{{}} + PC_{{}} \cdot f_{{}}}{f_{{}} + f_{{}}} = \frac{2122 \cdot 5 + 2122 \cdot 5}{5 + 5} = 2122 \end{aligned}$$

  (15)

Fig. 8

Composition of contributions to produce $\textit{HTC}_0$ when c1 and c2 have always the same values; contributions (rounded rectangles) are computed from top to bottom of the graph using operations described in the proposed methodology (rhombuses); the corresponding levels are reported in the left of the figure

Table 12 Contribution $BC_{i,t}$

Table 13 Contribution $\overline{BC}_{i,t}$

Table 14 Contribution $CC_{i,t}$

Table 15 Contribution $TPC_{p,t}$

Table 16 Contribution $\overline{TPC}_{p,t}$

Table 17 Starting and ending times of tasks

Finally, the speed-up for the two situations presented in Sect. 2 can be computed. The execution time of the sequential specification is 3123 cycles in both the cases, so the estimated speed-ups are 1.18 and 1.47, respectively.