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} presenting the results of real experiments executed over the Grid'5000 platform and compared to the EDP method. Finally, the chapter ends with a summary.
+
\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.
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
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
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}
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}
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}
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}
\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.
+
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
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}
\end{figure}
-\begin{table}[]
+\begin{table}[!h]
\centering
\begin{tabular}{|l|l|l|l|l|}
\hline
$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.
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.
+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}
\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}
\end{figure}
-
-
-
\section{Conclusions}
\label{ch4:9}
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.
