X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAhmed.git/blobdiff_plain/97d703d2fc9348e7cce48fab5da451f79ca00747..HEAD:/CHAPITRE_04.tex diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex index 43987cc..eef8a4b 100644 --- a/CHAPITRE_04.tex +++ b/CHAPITRE_04.tex @@ -22,23 +22,22 @@ In order to make the asynchronous method a good alternative to the synchronous o To reduce the energy consumption of a CPU executing the asynchronous iterative method, the Dynamic voltage and frequency scaling (DVFS) technique can be used. Modern operating systems automatically adjust the frequency of the processor according to their needs using DVFS operations. However, the user can scale down the frequency of the CPU using the on-demand governor \cite{ref96}. It lowers the frequency of a CPU to reduce its energy consumption, but it also decreases its computing power and thus it might increase the execution time of an application running on that processor. Therefore, the frequency that gives the best trade-off between energy consumption and performance must be selected. For parallel asynchronous methods running over a grid, a different frequency might be selected for each CPU in the grid depending on its characteristics. -In chapters \ref{ch2} and \ref{ch3}, three frequencies selecting algorithms were proposed -to reduce the energy consumption of synchronous message passing iterative applications running over homogeneous and heterogeneous platforms respectively. In this chapter, a new frequency selecting algorithm for asynchronous iterative message passing applications running over grids is presented. An adaptation for hybrid methods, with synchronous and asynchronous communications, is also proposed. +In chapters \ref{ch2} and \ref{ch3}, three frequency selecting algorithms were proposed +to reduce the energy consumption of synchronous message passing applications with iterations running over homogeneous or heterogeneous platforms. In this chapter, a new frequency selecting algorithm for asynchronous iterative message passing applications running over grids is presented. An adaptation for hybrid methods, with synchronous and asynchronous communications, is also proposed. The algorithm and its adaptation select the vector of frequencies which simultaneously offers a maximum energy reduction and minimum performance degradation ratio. The algorithm has a very small overhead and works online without needing any training nor any profiling. - This chapter is organized as follows: Section~\ref{ch4:2} presents some -related works from other authors. models for predicting the performance and the energy consumption - of both synchronous and asynchronous message passing programs -running over a grid are explained in Section~\ref{ch4:3}. +related works from other authors. Models for predicting the performance and the energy consumption + of both synchronous and asynchronous iterative message passing programs +executed over grids are explained in Section~\ref{ch4:3}. It also presents the objective function that maximizes the reduction of energy consumption while minimizing the degradation of the program's performance, used to select the frequencies. -Section~\ref{ch4:5} details the proposed frequencies selecting algorithm. +Section~\ref{ch4:5} details the proposed frequency selecting algorithm. Section~\ref{ch4:6} presents the iterative multi-splitting application which is a hybrid method and was used as a benchmark to evaluate the efficiency of the proposed algorithm. Section~\ref{ch4:7} presents the simulation results of applying the algorithm on the multi-splitting application and executing it on different grid scenarios. It also shows the results of running -three different power scenarios and comparing them. Moreover, in the last subsection, the proposed algorithm is compared to the energy and delay product (EDP) method. Section \ref{ch4:8} shows the real experiment results of applying the proposed algorithm over Grid'5000 platform and the results with the EDP method . Finally, the chapter ends with a summary in section -\ref{ch4:9}. +three different power scenarios and comparing them. Moreover, in the last subsection, the proposed algorithm is compared to the energy and delay product (EDP) method. Section \ref{ch4:8} presents the results of real experiments executed over the Grid'5000 platform and compared to the EDP method. Finally, the chapter ends with a summary. + @@ -96,12 +95,12 @@ In this chapter, we are interested in running asynchronous iterative message \end{figure} -An iterative application consists of a block of instructions that is repeatedly executed until convergence. A distributed iterative application with interdependent tasks requires, at each iteration, exchanging data between nodes to compute the distributed tasks. The communications between the nodes can be done synchronously or asynchronously. In the synchronous model, each node has to wait to receive data from all its neighbors to compute its iteration, see figures \ref{fig:ch1:15} and \ref{fig:ch1:16}. +An iterative application consists of a block of instructions that is repeatedly executed until convergence. A distributed iterative application with interdependent tasks requires, at each iteration, exchanging data between nodes to compute the distributed tasks. The communications between the nodes can be done synchronously or asynchronously. In the synchronous model, each node has to wait to receive data from all its neighbours to compute its iteration, see figures \ref{fig:ch1:15} and \ref{fig:ch1:16}. Since the tasks are synchronized, all the nodes execute the same number of iterations. Then, The overall execution time of an iterative synchronous message passing application with balanced tasks, running on the grid described above, is equal to the execution time of the slowest node in the slowest cluster running a task as presented in \ref{eq:perf_heter}. -Whereas, in the asynchronous model, the fast nodes do not have to wait for the slower nodes to finish their computations to exchange data, see Figure \ref{fig:ch1:17}. Therefore, there are no idle times between successive iterations, the node executes the computations with the last received data from its neighbors and the communications are overlapped by computations. Since there are no synchronizations between nodes, all nodes do not have the same number of iterations. +Whereas, in the asynchronous model, the fast nodes do not have to wait for the slower nodes to finish their computations to exchange data, see Figure \ref{fig:ch1:17}. Therefore, there are no idle times between successive iterations, the node executes the computations with the last received data from its neighbours and the communications are overlapped by computations. Since there are no synchronizations between nodes, all nodes do not have the same number of iterations. The difference in the number of executed iterations between the nodes depends on the heterogeneity of the computing powers of the nodes. The execution time of an asynchronous iterative message passing application is not equal to the execution time of the slowest node like in the synchronous mode because each node executes a different number of iterations. Moreover, the overall execution time is directly dependent on the method used to detect the global convergence of the asynchronous iterative application. The global convergence detection method might be synchronous or asynchronous and centralized or distributed. In a grid, the nodes in each cluster have different characteristics, especially different frequency gears. @@ -135,7 +134,7 @@ Therefore, the execution time of one outer iteration of such a hybrid applicat In Equation (\ref{eq:asyn_perf}), the communication times $\Ltcm[ij]$ are only the communications between the local nodes because the communications between the clusters are asynchronous and overlapped by computations. -\subsection{The energy model and tradeoff optimization} +\subsection{The energy model and trade-off optimization} \label{ch3:3:3} The energy consumption of an asynchronous application running over a heterogeneous grid is the summation of @@ -412,7 +411,6 @@ of this application is not directly related to the number of computing nodes. calling the scaling factor selection algorithm algorithm~\ref{HSA-asyn}. The communications of the DVFS algorithm can be applied synchronously or asynchronously which results in four different versions of the application: synchronous or asynchronous MS with synchronous or asynchronous DVFS communications. Figures \ref{fig:eng_time_dvfs} (a) and (b) present the energy consumption and the execution time for the four different versions of the application running on all the scenarios in Table \ref{table:comp}. - \begin{figure}[!t] \centering \centering @@ -422,11 +420,11 @@ of this application is not directly related to the number of computing nodes. \label{fig:eng_time_dvfs} \end{figure} Figure \ref{fig:eng_time_dvfs} (a) shows that the energy - consumption of all four versions of the method, running over the 8 grid scenarios described in Table \ref{table:comp}, are not affected by the increase in the number of computing nodes. MS without applying DVFS operations had the same behavior. On the other hand, Figure \ref{fig:eng_time_dvfs} (b) shows that the execution time of the MS application with DVFS operations + consumption of all four versions of the method, running over the 8 grid scenarios described in Table \ref{table:comp}, are not affected by the increase in the number of computing nodes. MS without applying DVFS operations had the same behaviour. On the other hand, Figure \ref{fig:eng_time_dvfs} (b) shows that the execution time of the MS application with DVFS operations decreases in inverse proportion to the number of nodes. Moreover, it can be noticed that the asynchronous MS with synchronous DVFS consumes less energy when compared to the other versions of the method. Two reasons explain this energy consumption reduction: \begin{enumerate} - \item The asynchronous MS with synchronous DVFS version uses synchronous DVFS communications which allow it to apply the new computed frequencies at the begining of the second iteration. Thus, reducing the consumption of dynamic energy by the application from the second iteration until the end of the application. Whereas in - asynchronous DVFS versions where the DVFS communications are asynchronous, the new frequencies cannot be computed at the end of the first iteration and consequently cannot be applied at the begining of the second iteration. + \item The asynchronous MS with synchronous DVFS version uses synchronous DVFS communications which allow it to apply the new computed frequencies at the beginning of the second iteration. Thus, reducing the consumption of dynamic energy by the application from the second iteration until the end of the application. Whereas in + asynchronous DVFS versions where the DVFS communications are asynchronous, the new frequencies cannot be computed at the end of the first iteration and consequently cannot be applied at the beginning of the second iteration. Indeed, since the performance information gathered during the first iteration is not sent synchronously at the end of the first iteration, fast nodes might execute many iterations before receiving the performance information, computing the new frequencies based on this information and applying the new computed frequencies. Therefore, many iterations might be computed by CPUs running on their highest frequency and consuming more dynamic energy than scaled down processors. \item As shown in Figure \ref{fig:eng_time_ms} (b), the execution time of the asynchronous MS version is lower than the execution time of the synchronous MS version because there is no idle time in the asynchronous version and the communications are overlapped by computations. Since the consumption of static energy is proportional to the execution time, the asynchronous MS version consumes less static energy than the synchronous version. @@ -451,14 +449,14 @@ Therefore, in this section, the synchronous MS method without DVFS serves as a As in Figure \ref{fig:eng_time_dvfs} (a) and for the same reasons presented above, the asynchronous MS with synchronous DVFS version gives the best energy saving percentage when compared to the other versions. - \begin{figure}[!t] + \begin{figure}[!h] \centering \includegraphics[scale=0.7]{fig/ch4/perf_degra.eps} \caption{The results of the performance degradation} \label{fig:perf_degr} \end{figure} - \begin{figure}[!t] + \begin{figure}[!h] \centering \includegraphics[scale=0.7]{fig/ch4/dist.eps} \caption{The results of the tradeoff distance} @@ -472,7 +470,7 @@ degradation percentages which means that the new execution time of a given versi $16.9\%$. While the worst case is the synchronous MS with synchronous DVFS where the performance is on average degraded by $2.9\%$ when compared to the reference method. - The energy consumption and performance tradeoff between these five versions is presented in Figure \ref{fig:dist}. + The energy consumption and performance trade-off between these five versions is presented in Figure \ref{fig:dist}. These distance values are computed as the differences between the energy saving and the performance degradation percentages as in the optimization function (\ref{eq:max-grid}). Thus, the best MS version is the one that has the maximum distance between the energy saving and performance degradation. The distance can be negative if the energy saving percentage is less than the performance degradation percentage. @@ -496,7 +494,7 @@ The versions applying the HSA algorithm and running over the Grid 4*8 platform Therefore, applying the HSA algorithm over asynchronous applications is very promising. In this section, the number of iterations executed by the asynchronous MS method, while solving a 3D problem of size $400^3$ with and without applying the HSA algorithm, is evaluated. In Table \ref{table:sd}, the standard deviation of the number of iterations executed by the asynchronous application over all the grid platform scenarios, is presented. -\begin{table}[h] +\begin{table}[!h] \centering \caption{The standard deviation of the numbers of iterations for different asynchronous MS versions running over different grid platforms} \label{table:sd} @@ -542,21 +540,21 @@ Finally, the asynchronous MS version that does not apply the HSA algorithm giv The energy saving, performance degradation and distance percentages for both versions over both platform scenarios and with the three power scenarios are presented in Figures \ref{fig:three_power_syn} and \ref{fig:three_power_asyn}. -\begin{figure}[!t] +\begin{figure}[!h] \centering \includegraphics[width=.7\textwidth]{fig/ch4/three_powers_syn.eps} \caption{The results of the three power scenarios: Synchronous application of the HSA algorithm} \label{fig:three_power_syn} \end{figure} -\begin{figure} +\begin{figure}[!h] \centering \includegraphics[width=.7\textwidth]{fig/ch4/three_powers_Asyn.eps} \caption{The results of the three power scenarios: Asynchronous application of the HSA algorithm} \label{fig:three_power_asyn} \end{figure} -\begin{figure}[!t] +\begin{figure}[!h] \centering \includegraphics[scale=.7]{fig/ch4/three_scenarios.pdf} \caption{Comparison of the selected frequency scaling factors by the HSA algorithm for the three power scenarios} @@ -585,27 +583,7 @@ In \cite{ref100,ref60,ref55}, the researchers used equal weights for the energy However, others added some weights to the factors in order to direct the optimization towards more energy saving or less performance degradation. For example, in ~\cite{ref71} they used the product $\mathit{EDP}=\mathit{energy}\times \mathit{delay}^2$ which favour performance over energy consumption reduction. In this work, the proposed scaling factors selection algorithm optimizes both the energy consumption and the performance at the same time and gives the same weight to both factors as in Equation \ref{eq:max-grid}. In this section, to evaluate the performance of the HSA algorithm, it is compared to the algorithm proposed by Spiliopoulos et al. \cite{ref67}. The latter is an online method that selects for each processor the frequency that minimizes the energy and delay product in order to reduce the energy consumption of a parallel application running over a homogeneous multi-cores platform. It gives the same weight to both metrics and predicts both the energy consumption and the execution time for each frequency gear as in the HSA algorithm. -To fairly compare the HSA algorithm with the algorithm of Spiliopoulos et al., the same energy models, Equation (\ref{eq:energy-grid}) or (\ref{eq:asyn_energy}), and execution time models, Equation (\ref{eq:perf-grid}) or (\ref{eq:asyn_perf}), are used to predict the energy consumptions and the execution times. - -The EDP objective function can be equal to zero when the predicted delay is equal to zero. Moreover, this product is equal to zero before applying any DVFS operation. To eliminate the zero values, the EDP function must take the following form: - - -\begin{equation} - \label{eq:EDP} - EDP = E_{Norm} \times (1+ D_{Norm}) -\end{equation} -where $E_{Norm}$ is the normalized energy consumption which is computed as in Equation (\ref{eq:enorm}) -and $D_{Norm}$ is the normalized delay of the execution time which is computed as follows: -\begin{equation} - \label{eq:Dnorm} - D_{Norm}= 1 -P_{Norm}= 1- (\frac{T_{old}}{T_{new}}) -\end{equation} -Where $P_{Norm}$ is computed as in Equation (\ref{eq:pnorm}). Furthermore, the EDP algorithm starts the search process from the initial frequencies that are computed as in Equation (\ref{eq:Fint}). It stops the search process when it reaches the minimum available frequency for each processor. The EDP algorithm was applied to the synchronous and asynchronous MS algorithm solving a 3D problem of size $400^3$. Two platform scenarios, Grid 4*4 and Grid 4*8, were chosen for this experiment. The EDP method was applied synchronously and asynchronously to the MS application as for the HSA algorithm. The comparison results of the EDP and HSA algorithms are presented in the Figures \ref{fig:compare_syndvfs_synms}, \ref{fig:compare_asyndvfs_asynms},\ref{fig:compare_asyndvfs_synms} and \ref{fig:compare_asyndvfs_asynms}. Each of these figures presents the energy saving, performance degradation and distance percentages for one version of the MS algorithm. The results shown in these figures are also the average of the results obtained from running each version of the MS method over the two platform scenarios described above. - - - - -\begin{figure}[!h] +\begin{figure}[!t] \centering \includegraphics[width=.7\textwidth]{fig/ch4/compare_syndvfs_synms.eps} \caption{Synchronous application of the frequency scaling selection method on the synchronous MS version} @@ -623,29 +601,39 @@ Where $P_{Norm}$ is computed as in Equation (\ref{eq:pnorm}). Furthermore, the E \caption{Asynchronous application of the frequency scaling selection method on the synchronous MS version} \label{fig:compare_asyndvfs_synms} \end{figure} + \begin{figure}[!h] \centering \includegraphics[width=.7\textwidth]{fig/ch4/compare_asyndvfs_asynms.eps} \caption{Asynchronous application of the frequency scaling selection method on the asynchronous MS version} \label{fig:compare_asyndvfs_asynms} \end{figure} - - - - -All the figures show that the proposed HSA algorithm outperforms the EDP algorithm -in terms of energy saving and performance degradation. EDP gave for some scenarios negative trade-off values which mean that the performance degradation percentages are higher than -the energy saving percentages, while the HSA algorithm gives positive trade-off values over all scenarios. -The frequency scaling factors selected by the EDP are most of the time higher than those selected by the HSA algorithm as shown in Figure \ref{fig:three_methods}. -The results confirm that higher frequency scaling factors do not always give more energy saving, especially when the overall execution time is drastically increased. Therefore, the HSA method that computes the maximum distance between the energy saving and the performance degradation is an effective method to optimize these two metrics at the same time. - -\begin{figure}[h] +To fairly compare the HSA algorithm with the algorithm of Spiliopoulos et al., the same energy models, Equation (\ref{eq:energy-grid}) or (\ref{eq:asyn_energy}), and execution time models, Equation (\ref{eq:perf-grid}) or (\ref{eq:asyn_perf}), are used to predict the energy consumptions and the execution times. +The EDP objective function can be equal to zero when the predicted delay is equal to zero. Moreover, this product is equal to zero before applying any DVFS operation. To eliminate the zero values, the EDP function must take the following form: +\begin{equation} + \label{eq:EDP} + EDP = E_{Norm} \times (1+ D_{Norm}) +\end{equation} +where $E_{Norm}$ is the normalized energy consumption which is computed as in Equation (\ref{eq:enorm}) +and $D_{Norm}$ is the normalized delay of the execution time which is computed as follows: +\begin{equation} + \label{eq:Dnorm} + D_{Norm}= 1 -P_{Norm}= 1- (\frac{T_{old}}{T_{new}}) +\end{equation} +Where $P_{Norm}$ is computed as in Equation (\ref{eq:pnorm}). Furthermore, the EDP algorithm starts the search process from the initial frequencies that are computed as in Equation (\ref{eq:Fint}). It stops the search process when it reaches the minimum available frequency for each processor. The EDP algorithm was applied to the synchronous and asynchronous MS algorithm solving a 3D problem of size $400^3$. Two platform scenarios, Grid 4*4 and Grid 4*8, were chosen for this experiment. The EDP method was applied synchronously and asynchronously to the MS application as for the HSA algorithm. The comparison results of the EDP and HSA algorithms are presented in the Figures \ref{fig:compare_syndvfs_synms}, \ref{fig:compare_asyndvfs_asynms},\ref{fig:compare_asyndvfs_synms} and \ref{fig:compare_asyndvfs_asynms}. Each of these figures presents the energy saving, performance degradation and distance percentages for one version of the MS algorithm. The results shown in these figures are also the average of the results obtained from running each version of the MS method over the two platform scenarios described above. +\begin{figure}[!h] \centering \includegraphics[scale=0.6]{fig/ch4/compare_scales.eps} \caption{Comparison of the selected frequency scaling factors by the two algorithms over the Grid 4*4 platform scenario} \label{fig:three_methods} \end{figure} +All the figures show that the proposed HSA algorithm outperforms the EDP algorithm +in terms of energy saving and performance degradation. EDP gave for some scenarios negative trade-off values which mean that the performance degradation percentages are higher than +the energy saving percentages, while the HSA algorithm gives positive trade-off values over all scenarios. +The frequency scaling factors selected by the EDP are most of the time higher than those selected by the HSA algorithm as shown in Figure \ref{fig:three_methods}. +The results confirm that higher frequency scaling factors do not always give more energy saving, especially when the overall execution time is drastically increased. Therefore, the HSA method that computes the maximum distance between the energy saving and the performance degradation is an effective method to optimize these two metrics at the same time. + @@ -657,7 +645,8 @@ The performance of algorithm ~(\ref{HSA-asyn}) was evaluated by This testbed is a large-scale platform that consists of ten sites distributed all over metropolitan France and Luxembourg. Moreover, some sites are equipped with power measurement tools that capture the power consumption for each node on those sites. Same method for computing the dynamic power consumption described in section \ref{ch3:4} is used. Table \ref{table:grid5000} presents the characteristics of the selected clusters which are located on four different sites. -\begin{table}[!t] + +\begin{table}[!h] \caption{CPUs characteristics of the selected clusters} % title of Table \centering @@ -691,14 +680,14 @@ The asynchronous MS consumes more energy than the synchronous one. Also, it can be noticed that both the asynchronous and synchronous MS with synchronous application of the HSA algorithm consume less energy than the other versions of the application. Synchronously applying the HSA algorithm allows them to scale down the CPUs' frequencies at the beginning of the second iteration. Thus, the consumption of dynamic energy by the application is reduced from the second iteration until the end of the application. On the contrary, with the asynchronous application of the HSA algorithm, the new frequencies cannot be computed at the end of the first iteration and consequently cannot be applied at the beginning of the second iteration. Indeed, since the performance information gathered during the first iteration is not sent synchronously at the end of the first iteration, fast nodes might execute many iterations before receiving the performance information, computing the new frequencies based on this information and applying the new computed frequencies. Therefore, many iterations might be computed by CPUs running on their highest frequency and consuming more dynamic energy than the scaled down processors. Moreover, the execution time of the asynchronous MS version is lower than the execution time of the synchronous MS version because there is no idle time in the asynchronous version and the communications are overlapped by computations. Since the consumption of static energy is proportional to the execution time, the asynchronous MS version consumes less static energy than the synchronous version. -\begin{figure}[!t] +\begin{figure}[!h] \centering \includegraphics[width=.8\textwidth]{fig/ch4/time-compare.eps} \caption{ Comparing the execution time} \label{fig:time-compare} \end{figure} -\begin{figure}[!t] +\begin{figure}[!h] \centering \includegraphics[width=.8\textwidth]{fig/ch4/energy-compare.eps} \caption{ Comparing the energy consumption} @@ -706,7 +695,7 @@ Moreover, the execution time of the asynchronous MS version is lower than the \end{figure} -\begin{table}[] +\begin{table}[!h] \centering \begin{tabular}{|l|l|l|l|l|} \hline @@ -727,31 +716,30 @@ Size & Method &\begin{tabular}[c]{@{}l@{}}E Table \ref{table:exper} shows that there are positive and negative performance degradation percentages. A negative value means that the new execution time of a given version of the application is less than the execution time of the synchronous MS without DVFS. Therefore, the version with the smallest negative performance degradation percentage has actually the best speed up when compared to the other versions. - The energy consumption and performance tradeoffs between these four versions can be computed as in the optimization Function + The energy consumption and performance trade-offs between these four versions can be computed as in the optimization Function (\ref{eq:max-grid}). The asynchronous MS applying synchronously the HSA algorithm gives the best distance which is equal to $48.41\%$. This version saves up to $26.93\%$ of energy and even reduces the execution time of the application by $21.48\%$. This overall improvement is due to combining asynchronous computing and the synchronous application of the HSA algorithm. +Finally, this section shows that the obtained results over Grid'5000 are comparable to the +simulation results of Section \ref{ch4:7:2}, the asynchronous MS applying synchronously the HSA algorithm is the best version in both of sections. Moreover, the results over Grid'5000 are better +than simulation results because the computing clusters used in the Grid'5000 experiments are more heterogeneous in term of the computing power and network characteristics than the simulated platform with SimGrid. For example, the nodes in StRemi cluster have lower computing powers compared to the other used three clusters of Grid'5000 platform. +As a result, the increase in the heterogeneity between the clusters' computing nodes increases the idle times which forces the proposed algorithm to select a big scaling factors and thus saving more energy. -Finally, this section shows that the obtained results over Grid'5000 are comparable to -simulation results of section \ref{ch4:7:2}, where the asynchronous MS applying synchronously the HSA algorithm is the best version in both of them. Moreover, results of Grid'5000 are better -than simulation ones because its computing clusters are more heterogeneous in term of the computing power and network characteristics. For example, the StRemi cluster has smaller computing power compared to others three clusters of Grid'5000 platform. -As a result, The increase in the idle times forces the proposed algorithm to select a big scaling factors and thus more energy saving. \subsection{Comparing the HSA algorithm to the energy and delay product method} \label{res-comp} - -The EDP algorithm, described in section \ref{ch4:7:5}, was applied synchronously and asynchronously to both the synchronous and asynchronous MS application of size $N=400^3$. The experiments were conducted over 4 distributed clusters, described in Table \ref{table:grid5000}, and 8 homogeneous nodes were used from each cluster. +The EDP algorithm, described in Section \ref{ch4:7:5}, was applied synchronously and asynchronously to both the synchronous and asynchronous MS application of size $N=400^3$. The experiments were conducted over 4 distributed clusters, described in Table \ref{table:grid5000}, and 8 homogeneous nodes were used from each cluster. Table \ref{table:comapre} presents the results of energy saving, performance degradation and distance percentages when applying the EDP method on four different MS versions. -Figure \ref{fig:compare} compares the distance percentages, computed as the difference between energy saving and performance degradation percentages, of the EDP and HSA -algorithms. This comparison shows that the proposed HSA algorithm gives better energy reduction and performance trade-off than the EDP method. The results of EDP method over Grid'5000 are better than those for EDP obtained by the simulation according to the increase in the heterogeneity between the computing clusters of Grid'5000 as mentioned before. +Figure \ref{fig:compare-edp} compares the distance percentages, computed as the difference between energy saving and performance degradation percentages, of the EDP and HSA +algorithms. This comparison shows that the proposed HSA algorithm gives better energy reduction and performance trade-off than the EDP method. EDP gives better results when evaluated over Grid'5000 than over the simulator because the nodes used from Grid'5000 are more heterogeneous than those simulated with SimGrid. -\begin{table} +\begin{table}[!h] \centering \caption{The EDP algorithm results over the Grid'5000} \label{table:comapre} @@ -769,14 +757,13 @@ Async MS with Async DVFS & 10.32 & -17.04 & 27.36 \\ \hlin \centering \includegraphics[scale=0.65]{fig/ch4/compare.eps} \caption{Comparing the trade-off percentages of HSA and EDP methods over the Grid'5000} - \label{fig:compare} + \label{fig:compare-edp} \end{figure} - + \section{Conclusions} \label{ch4:9} - This chapter presents a new online frequency selection algorithm for asynchronous iterative applications running over a grid. It selects the best vector of frequencies that maximizes the distance between the predicted energy consumption and the predicted execution time. @@ -785,7 +772,7 @@ energy and performance models to predict the energy consumption and the executi The proposed algorithm was evaluated twice over the SimGrid simulator and Grid'5000 testbed while running a multi-splitting (MS) application that solves 3D problems. The experiments were executed over different grid scenarios composed of different numbers of clusters and different numbers of nodes per cluster. - The HSA algorithm was applied synchronously and asynchronously on a synchronous and an asynchronous version of the MS application. Both the simulation and real experiment results show that applying synchronous HSA algorithm on an asynchronous MS application gives the best tradeoff between energy consumption reduction and performance compared to other scenarios. + The HSA algorithm was applied synchronously and asynchronously on a synchronous and an asynchronous version of the MS application. Both the simulation and real experiment results show that applying synchronous HSA algorithm on an asynchronous MS application gives the best trade-off between energy consumption reduction and performance compared to other scenarios. In the simulation results, this scenario saves on average the energy consumption by 22\% and reduces the execution time of the application by 5.72\%. This version optimizes both of the dynamic energy consumption by applying synchronously the HSA algorithm at the end of the first iteration and the static energy consumption by using asynchronous communications between nodes from different clusters which are overlapped by computations. The HSA algorithm was also evaluated over three power scenarios. As expected, the algorithm selects different vectors of frequencies for each power scenario. The highest energy consumption reduction was achieved in the power scenario with the highest dynamic power and the lowest performance degradation was obtained in the power scenario with the highest static power. The proposed algorithm was compared to another method that uses the well known energy and delay product as an objective function. @@ -793,4 +780,4 @@ The comparison results showed that the proposed algorithm outperforms the latter by selecting a vector of frequencies that gives a better trade-off between the energy consumption reduction and the performance. -The experiments conducted over Grid'5000 were showed that applying the synchronous HSA algorithm on an asynchronous MS application saves the energy consumption by 26.93\% and reduces the execution time of the application by 21.48\%. On the other hand, these results are better than simulation ones, according to the increase in the heterogeneity level between the clusters of Grid'5000 compared to the simulated grid platform. \ No newline at end of file +The experiments conducted over Grid'5000 showed that applying the synchronous HSA algorithm on an asynchronous MS application gives the best results. It saves the energy consumption by 26.93\% and reduces the execution time of the application by 21.48\%. The experiments executed over Grid'5000 give better results than those simulated with SimGrid because the nodes used in Grid'5000 were more heterogeneous than the ones simulated by SimGrid.