corrections

[ThesisAhmed.git] / CHAPITRE_04.tex

diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex
index 43987cc5125f89b16016ca55d1f076a74b2d309e..eef8a4b9ae2b779f661ecef176b0597ee1217a3e 100644 (file)
--- 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.   
 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.
 
 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
 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.
 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
 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}    
 
 
 \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}. 
 
  
 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. 
 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. 
 
  
 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
 \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}. 
  
  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
  \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 
   \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}
  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.
  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.  
  
  
 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}
 
   \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}
   \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.
  
  
  $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.
  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.
  
   
  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}
 \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}.
  
   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}
 
   \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}
 
   \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}
   \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.
 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}
   \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}
    \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}
 \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}
   \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.
  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
   \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.  
 
 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} 
 
  \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}
  \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} 
  
 
  \end{figure} 
  
 

-\begin{table}[]
+\begin{table}[!h]

 \centering
 \begin{tabular}{|l|l|l|l|l|}
 \hline
 \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. 
 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.
 
 
  (\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}
 
 
 
  
 \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.
 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}
 \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}
   \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}
 \end{figure}

- 
+

 
 
 \section{Conclusions}
  \label{ch4:9}
 
 
 \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. 
 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 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.
 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.
 
 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.