corrections

[ThesisAhmed.git] / CHAPITRE_04.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                          %%
%%       CHAPTER 04        %%
%%                          %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Tnorm}{\Xsub{T}{Norm}}
\newcommand{\Ltcm}[1][]{\Xsub{L}{tcm}_{\fxheight{#1}}}
\newcommand{\Etcm}[1][]{\Xsub{E}{tcm}_{\fxheight{#1}}}
\newcommand{\Niter}[1][]{\Xsub{N}{iter}_{\fxheight{#1}}}

\chapter{Energy Optimization of Asynchronous Applications}
\label{ch4}


\section{Introduction}
\label{ch4:1}

A grid is composed of heterogeneous clusters: CPUs from distinct clusters might have different computing power, energy consumption or frequency range. 
Running synchronous parallel applications on grids  results in long slack times where the fast nodes have to wait for the slower ones to finish their computations before synchronously exchanging data with them. Therefore, it is widely accepted that asynchronous parallel methods are more suitable than synchronous ones for such architectures because there is no slack time and the asynchronous communications are overlapped by computations. However, they usually execute more iterations than the synchronous ones and thus consume more energy.
In order to make the asynchronous method a good alternative to the synchronous one, it should not be just competitive in performance but also in energy consumption. 
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 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 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 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} 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.





\section{Related works}
\label{ch4:2}


A message passing application is in general composed of two types of sections, which are the computations and the communications sections. The communications can be done synchronously or asynchronously. In a synchronous message passing application, when a process synchronously sends a message to another node, it is blocked until the latter receives the message. During that time, there is no computation on both nodes and that period is called slack time. 
On the contrary, in an asynchronous message passing application, the asynchronous communications are overlapped by computations, thus, there is no slack time. 
Many techniques have been used to reduce the energy consumption of  message passing applications,
such as scheduling, heuristics and DVFS. For example,   different scheduling techniques, to switch off the idle nodes to save their energy consumption, were presented in \cite{ref83,ref84,ref85} and \cite{ref86}. In \cite{ref87}
and \cite{ref88}, an heuristic to manage the workloads between the computing resources of the cluster and reduce their energy, was published.
However, the  dynamic voltage and frequency scaling (DVFS) is the most popular technique to reduce the energy consumption  of computing processors.

As shown in the related works of chapter \ref{ch2}, most of the works in this field targeted the synchronous message passing applications because they are more common than the asynchronous ones and easier to work on.  Some researchers tried to reduce slack times in synchronous applications running over homogeneous clusters. These slack times can happen on such architectures if the distributed  workloads over the computing nodes are imbalanced.
Other works focused on reducing the energy consumption of synchronous applications running over heterogeneous  architectures such as heterogeneous clusters or grids. When executing synchronous message passing applications on these architectures, slack times are generated when fast nodes have to communicate with slower ones. Indeed, the fast nodes have to wait for the slower ones to finish their computations to be able to communicate with them. In this case, some  energy was saved as in the work of chapter \ref{ch3}  and its related works by reducing the frequencies of the fast nodes with DVFS operations while minimizing the slack times.

Whereas, no work has been conducted to optimize the energy consumption of  asynchronous message passing applications.   Some works use asynchronous communications when applying DVFS operations on synchronous applications. For example, Hsu et al. \cite{ref92} proposed an online adaptive algorithm that divides the synchronous  message passing application into several time periods and selects the suitable frequency for each one. The  algorithm  asynchronously applies the new computed frequencies  to overlap the multiple DVFS switching times with computation.  Similarly to this work, Zhu et al.  \cite{ref93} studied the difference between applying  synchronously  or asynchronously the  frequency changing algorithm during the execution time of the program. The results of the proposed asynchronous scheduler were more energy efficient than synchronous one. In \cite{ref94}, Vishnu et al.  presented an energy efficient asynchronous agent that  reduces the slack times in a parallel program to reduce the energy consumption. They used asynchronous communications in the proposed algorithm, which calls the DVFS algorithm many times during the execution time of the program. The three previous presented works were applied on applications running over  homogeneous platforms.
   
In \cite{ref95}, the energy consumption of an asynchronous iterative  linear solver running over a heterogeneous platform, is evaluated. The results showed that the asynchronous version of the application had less execution time than the synchronous one. Therefore, according to their energy model the asynchronous method consumes less energy. 
However, in their model they do not consider that during synchronous communications only static power which is significantly lower than dynamic power, is consumed.    

This chapter presents the following contributions:
\begin{enumerate}
\item new model to predict the energy consumption and the execution time 
 of asynchronous iterative message passing applications running over a  grid platform. 
  
\item a new online algorithm that selects a vector of frequencies which gives the best trade-off between energy consumption and performance for asynchronous iterative message passing applications running over a  grid platform. The algorithm has a very small overhead 
  and does not need any training or profiling. The new algorithm can be applied synchronously and asynchronously on an iterative message passing application.

\end{enumerate}



                                                                                            
\section{The performance and the energy consumption measurement models}
\label{ch4:3}

\subsection{The execution time of  iterative asynchronous message passing  applications}
\label{ch4:3:1}
In this chapter, we are interested in running  asynchronous iterative message 
 passing distributed applications over a grid while reducing the energy consumption of the 
 CPUs during the execution. 
  Figure \ref{fig:heter}   is an example of a grid with four different clusters. Inside each cluster, all the nodes are   homogeneous, have the same specifications, but are different  from the nodes of the other clusters. 
 To reduce the energy consumption of these applications while  running on a grid, 
 the  heterogeneity of the clusters' nodes,  such as nodes' computing powers (FLOPS), energy consumptions and
 CPU's frequency ranges, must be taken into account. To reduce the complexity of the experiments and focus on the heterogeneity of the nodes, the local networks of all the clusters are assumed to be identical, with the same  latency and bandwidth. The networks connecting the clusters are also assumed to be homogeneous but they are slower than the local networks.
   
   \begin{figure}[!t]
  \centering
  \includegraphics[scale=0.9]{fig/ch4/GRID}
  \caption{A grid platform composed of heterogeneous clusters}
  \label{fig:heter}
\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 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 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. 
Therefore, when applying  DVFS operations on these nodes, they may get different scaling factors represented
by a scaling vector: $(S_{11}, S_{12},\dots, S_{NM_i})$ where $S_{ij}$ is the 
scaling factor of processor $j$ in the cluster $i$. 
To be able to predict the execution time of asynchronous iterative message passing  applications running 
over a  grid, for different vectors of scaling factors, the communication times  and the computation times for all the tasks must be measured during the first iteration before applying any DVFS operation. Then, the execution time of one iteration of an asynchronous iterative message passing  application,
running on a grid after applying a vector of scaling factors, is equal to the execution time of the synchronous application but without its communication times. The communication times  are overlapped by computations and the execution time can be evaluated for all the application as the average of the execution time of all the parallel tasks. This  is presented  in Equation \ref{eq:asyn_time}.

\begin{equation}
  \label{eq:asyn_time}
  \Tnew =  \frac{\sum_{i=1}^{N} \sum_{j=1}^{M_i}({\TcpOld[ij]} \cdot S_{ij})} {N  \cdot M_i }
\end{equation}


In this work, a hybrid (synchronous/asynchronous) message passing application \cite{ref99} is being used. It is composed of two loops: 
\begin{enumerate}
\item In the inner loop, at each iteration, the nodes in a cluster synchronously exchange data between them. There is no communication between nodes from different clusters.
\item In the outer loop, at each iteration, the nodes from different clusters asynchronously exchange their data between them because the network interconnecting  the clusters has a high latency. 
\end{enumerate}

Therefore, the execution time  of one outer iteration of such a hybrid  application can be evaluated by computing the average of the execution time of the slowest node in each cluster. The  overall execution time of the asynchronous iterative applications can be evaluated as follows:
  
\begin{equation}
  \label{eq:asyn_perf}
  \Tnew =  \frac{\sum_{i=1}^{N} (\max_{j=1,\dots, M_i} ({\TcpOld[ij]} \cdot S_{ij}) +  
   \min_{j=1,\dots,M_i} ({\Ltcm[ij]}))}{N}
\end{equation}

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 trade-off optimization}
\label{ch3:3:3}

The energy consumption of an asynchronous application running over a heterogeneous grid is the summation of
the dynamic and static power of each node multiplied by the computation time of that node as in Equation (\ref{eq:asyn_energy1}).  The computation time of each node is equal to the overall execution time of 
the node because the asynchronous  communications are overlapped by  computations.
\begin{equation}
  \label{eq:asyn_energy1}
 E = \sum_{i=1}^{N} \sum_{j=1}^{M_i} {(S_{ij}^{-2} \cdot  \Tcp[ij] \cdot (\Pd[ij]+\Ps[ij]) )} 
\end{equation} 


It is common for distributed algorithms running over grids to have asynchronous external communications between clusters and synchronous ones between the nodes of the same cluster. In this hybrid  communication scheme, the dynamic energy consumption can be computed in the same way as for the synchronous application with Equation (\ref{eq:Edyn_new}).
However, since the nodes of different clusters are not synchronized and do not have the same execution time as in the synchronous application, the static energy consumption is different between them. The cluster execution time is equal to the execution time of the slowest task in that cluster.  The  energy 
consumption of the asynchronous iterative message passing application running on a 
heterogeneous grid platform during one iteration  can be computed as follows:

 \begin{equation}
  \label{eq:asyn_energy}
 E = \sum_{i=1}^{N} \sum_{j=1}^{M_i} {(S_{ij}^{-2} \cdot \Pd[ij] \cdot  \Tcp[ij])} +  \sum_{i=1}^{N} \sum_{j=1}^{M_i} (\Ps[ij] \cdot 
 ( \mathop{\max_{j=1,\dots,M_i}} ({\Tcp[ij]} \cdot S_{ij}) + \mathop{\min_{j=1,\dots,M_i}} ({\Ltcm[ij]}))) 
\end{equation}
Where $\Ltcm[ij]$ is the local  communication time of the cluster $i$ of node $j$.
Reducing the frequencies of the processors according to the vector of scaling
factors $(S_{11}, S_{12},\dots, S_{NM_i})$ may degrade the performance of the application
and thus, increase the static energy consumed because the execution time is
increased~\cite{ref78}. The overall 
energy consumption for the asynchronous application can be computed by multiplying the energy consumption 
from one iteration of each cluster by the number of the iterations of that cluster, $\Niter[i]$,
as in Equation (\ref{eq:asyn_energy_it}).

    
 \begin{multline}
  \label{eq:asyn_energy_it}
 E = \sum_{i=1}^{N} (\sum_{j=1}^{M_i} {(S_{ij}^{-2} \cdot \Pd[ij] \cdot  \Tcp[ij])}) \cdot \Niter[i] +  \sum_{i=1}^{N} (\sum_{j=1}^{M_i} (\Ps[ij] \cdot \\
 ( \mathop{\max_{j=1,\dots,M_i}} ({\Tcp[ij]} \cdot S_{ij}) + \mathop{\min_{j=1,\dots,M_i}} ({\Ltcm[ij]})))) \cdot \Niter[i]
\end{multline}

In order to optimize the energy consumption and the performance of the asynchronous iterative applications at the same time, the maximum distance between the two metrics can be computed as in the previous chapters. 
However, both the energy model and performance must be normalized as in the Equations \ref{eq:enorm-heter} and
\ref{eq:pnorm-heter} respectively. 
Hence, $\Tnew$ should be  computed as in Equation~\ref{eq:asyn_perf} and $\Told$  computed as follows:
\begin{equation}
  \label{eq:asyn_told}
  \Told =  \frac{\sum_{i=1}^{N} (\max_{j=1,\dots, M_i} ({\TcpOld[ij]}) +  
   \min_{j=1,\dots,M_i} ({\Ltcm[ij]}))}{N}
\end{equation}

The original energy consumption of asynchronous applications, $\Eoriginal$ is computed as in (\ref{eq:asyn_energy_original}).



\begin{equation}
  \label{eq:asyn_energy_original}
 E_{original} = \sum_{i=1}^{N} \sum_{j=1}^{M_i} {( \Pd[ij] \cdot  \TcpOld[ij])} +  \sum_{i=1}^{N} \sum_{j=1}^{M_i} (\Ps[ij] \cdot 
 ( \mathop{\max_{j=1,\dots,M_i}} ({\TcpOld[ij]} ) + \mathop{\min_{j=1,\dots,M_i}} ({\Ltcm[ij]}))) 
\end{equation}


Then, the objective function can be modeled  as the maximum
distance between the normalized energy curve  and the normalized 
performance curve  over all available sets of scaling factors and is computed as in the
objective function \ref{eq:max-grid}.


\section[The scaling algorithm of asynchronous applications]{The scaling factors selection algorithm of asynchronous applications over grid}
\label{ch4:5}
The frequency selection algorithm~(\ref{HSA-asyn}) works online during the first iteration of  asynchronous iterative message passing program running over a  grid. The algorithm selects 
 the set of frequency scaling factors $\Sopt[11],\Sopt[12],\dots,\Sopt[NM_i]$ which maximizes
 the distance, the tradeoff function (\ref{eq:max-grid}), between the predicted normalized energy consumption
 and the normalized performance of the  program. The algorithm is called just once in the iterative program and
 it uses information gathered from the first iteration to approximate the vector of frequency scaling factors that gives the best tradeoff. 
 According to the returned vector of  scaling factors, the DVFS algorithm (\ref{dvfs-heter}) computes the new frequency 
 for each node in the grid. It also shows where and when the proposed scaling algorithm is called in 
 the iterative message passing program. 

\begin{figure}[!t]
  \centering
  \includegraphics[scale=0.65]{fig/ch4/init_freq}
  \caption{Selecting the initial frequencies in a grid composed of four clusters}
  \label{fig:st_freq}
\end{figure}

In contrast to the scaling factors selection algorithm of synchronous applications running on the grid 
(algorithm \ref{HSA-grid}), this algorithm  computed the initial frequencies depending on the Equations 
\ref{eq:Scp-grid} and \ref{eq:Fint-grid}. Figure~\ref{fig:st_freq} shows the selected initial frequencies of the grid composed of four different types of clusters that are presented in the Figure \ref{fig:heter}.
The only difference between the two algorithms is the energy and performance models that are used. Furthermore,  this algorithm scales down all frequencies of nodes at each iteration, while other algorithm don't scaled down the frequency of the slowest node. However, the performance of asynchronous application does not depend on the performance of the slower nodes, while it depends on the performance of all nodes.

\begin{algorithm}
  \begin{algorithmic}[1]
    % \footnotesize
    \Require ~
    \item [{$N$}] number of clusters in the grid.
    \item [{$M$}] number of nodes in each cluster.
    \item[{$\Tcp[ij]$}] array of all computation times for all nodes during one iteration and with the highest frequency.
    \item[{$\Tcm[ij]$}] array of all communication times for all nodes during one iteration and with the highest frequency.
    \item[{$\Fmax[ij]$}] array of the maximum frequencies for all nodes.
    \item[{$\Pd[ij]$}] array of the dynamic powers for all nodes.
    \item[{$\Ps[ij]$}] array of the static powers for all nodes.
    \item[{$\Fdiff[ij]$}] array of the differences between two successive frequencies for all nodes.
  
    \Ensure $\Sopt[11],\Sopt[12] \dots, \Sopt[NM_i]$,  a vector of scaling factors that gives the optimal tradeoff between energy consumption and execution time

    \State $\Scp[ij] \gets \frac{\max_{i=1,2,\dots,N}(\max_{j=1,2,\dots,M_i}(\Tcp[ij]))}{\Tcp[ij]} $
    \State $F_{ij} \gets  \frac{\Fmax[ij]}{\Scp[i]},~{i=1,2,\cdots,N},~{j=1,2,\dots,M_i}.$
    \State Round the computed initial frequencies $F_i$ to the closest  available frequency for each node.
    \If{(not the first frequency)}
          \State $F_{ij} \gets F_{ij}+\Fdiff[ij],~i=1,\dots,N,~{j=1,\dots,M_i}.$
    \EndIf
    \State $\Told \gets \frac{\sum_{i=1}^{N} (\max\limits_{j=1,\dots, M_i} ({\TcpOld[ij]}) +  
   \min\limits_{j=1,\dots,M_i} ({\Ltcm[ij]}))}{N} $
   \vspace*{0.2 cm} 
    \State $\Eoriginal \gets \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{M_i} {( \Pd[ij] \cdot  \TcpOld[ij])} +  \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{M_i} (\Ps[ij] \cdot 
 (\mathop{\max\limits_{j=1,\dots,M_i}} ({\TcpOld[ij]} ) + \mathop{\min\limits_{j=1,\dots,M_i}} ({\Ltcm[ij]})))$ 
    \State $\Sopt[ij] \gets 1,~i=1,\dots,N,~{j=1,\dots,M_i}. $
    \State $\Dist \gets 0 $
    \While {(all nodes have not reached their  minimum frequency  \textbf{or}  $\Pnorm - \Enorm < 0 $)}
        \If{(not the last frequency)}
        \State $F_{ij} \gets F_{ij} - \Fdiff[ij],~{i=1,\dots,N},~{j=1,\dots,M_i}$.
        \State $S_{ij} \gets \frac{\Fmax[ij]}{F_{ij}},~{i=1,\dots,N},~{j=1,\dots,M_i}.$
        \EndIf
       \State $\Tnew \gets \frac{\sum\limits_{i=1}^{N} (\max\limits_{j=1,\dots, M_i} ({\TcpOld[ij]} \cdot S_{ij}) +   \min\limits_{j=1,\dots,M_i} ({\Ltcm[ij]}))}{N} $  
   \vspace*{0.2 cm} 
       \State $\Ereduced \gets \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{M_i} {(S_{ij}^{-2} \cdot \Pd[ij] \cdot  \Tcp[ij])} +  \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{M_i} (\Ps[ij] \cdot 
 ( \mathop{\max\limits_{j=1,\dots,M_i}} ({\Tcp[ij]} \cdot S_{ij}) + \mathop{\min\limits_{j=1,\dots,M_i}} ({\Ltcm[ij]}))) $ 
       \State $\Pnorm \gets \frac{\Told}{\Tnew}$
       \State $\Enorm\gets \frac{\Ereduced}{\Eoriginal}$
      \If{$(\Pnorm - \Enorm > \Dist)$}
        \State $\Sopt[ij] \gets S_{ij},~i=1,\dots,N,~j=1,\dots,M_i. $
        \State $\Dist \gets \Pnorm - \Enorm$
      \EndIf
    \EndWhile
    \State  Return $\Sopt[11],\Sopt[12],\dots,\Sopt[NM_i]$
  \end{algorithmic}
  \caption{Scaling factors selection algorithm of asynchronous applications over grid}
  \label{HSA-asyn}
\end{algorithm}




\section{The iterative multi-splitting method }
  \label{ch4:6}

  Multi-splitting algorithms have been initially studied  to
  solve linear systems of equations in parallel
  \cite{ref97}. Thereafter, they were  used to design
  non linear iterative algorithms and asynchronous iterative
  algorithms~\cite{ref98}. The principle of multi-splitting
  algorithms lies in splitting the system of equations, then solving
  each sub-system using a direct or an iterative method and then
  combining the results in order to build a global solution. Since a
  multi-splitting method is iterative, it requires executing several iterations
  in order to reach global convergence. 

  In this chapter, we have used an asynchronous iterative multisplitting method
  to solve a 3D Poisson problem as described in~\cite{ref99}. The
  problem is divided into small 3D sub-problems  and each one is solved by a
  parallel GMRES method. For more information about multi-splitting
  algorithms, interested readers are invited to
  consult the previous references.


\section{The experimental results over SimGrid}
 \label{ch4:7}
In this section, the heterogeneous scaling algorithm (HSA), Algorithm~(\ref{HSA-asyn}), is applied to the parallel iterative
multi-splitting method. The performance of this algorithm is evaluated by
 executing  the iterative  multi-splitting method on the Simgrid/SMPI simulator v3.10 
\cite{ref66}. This simulator offers flexible tools to create a  
grid architecture and run the iterative application over it. The  grid used in these 
experiments has four different types of nodes. Two types of nodes have different computing powers, frequency ranges, static and dynamic powers. Table \ref{table:platform} 
presents the characteristics of the four types of nodes.   The specifications of the simulated nodes are similar to real Intel processors. 
Many grid configurations have been used in the experiments where the number of clusters and the number of nodes per cluster are equal to 4 or 8.
For the grids composed of 8 clusters, two clusters of each type of nodes were used. The number of nodes per cluster is the same for all the clusters in a given grid.


\begin{table}[!t]
  \caption{The characteristics of the four types of nodes}
  % title of Table
  \centering
  \begin{tabular}{|*{7}{r|}}
    \hline
    node& Simulated   & Max   & Min   & Diff. & Dynamic    & Static    \\
    type   & GFLOPS      & Freq. & Freq. & Freq. & power      & power     \\
           & of one node & GHz   & GHz   & GHz   &            &           \\
    \hline
    A      & 40          & 2.50  & 1.20  & 0.100 & \np[W]{20} & \np[W]{4} \\
    \hline
    B      & 50          & 2.66  & 1.60  & 0.133 & \np[W]{25} & \np[W]{5} \\
    \hline
    C      & 60          & 2.90  & 1.20  & 0.100 & \np[W]{30} & \np[W]{6} \\
    \hline
    D      & 70          & 3.40  & 1.60  & 0.133 & \np[W]{35} & \np[W]{7} \\
    \hline
  \end{tabular}
  \label{table:platform}
\end{table}
 

  The CPUs' constructors do not specify the amount of static and dynamic powers their CPUs consume.
The maximum power consumption for each node's CPU was chosen to be proportional  to its computing power (FLOPS). The dynamic power was assumed to represent  \np[\%]{80} of the overall power consumption and the rest  (\np[\%]{20}) is the static power. Similar assumptions were made in last two chapters and \cite{ref47}. 
The clusters of the grid are connected via a long distance Ethernet network with 
\np[Gbit/s]{1} bandwidth, while inside each cluster the nodes are connected via a high-speed \np[Gbit/s]{10} bandwidth local Ethernet network. The local networks have ten times less latency than the network connecting the clusters.

\subsection{The energy consumption and the execution time of the multi-splitting application}
 \label{ch4:7:1}
 The multi-splitting (MS) method solves a three dimensional problem of size $N=N_x \cdot N_y \cdot N_z$. The problem is divided into equal sub-problems which are distributed  to the computing nodes of the grid and then solved. 
 The experiments were conducted on  problems of size  $N=400^3$
 or $N=500^3$  that  require more than $12$ and $24$ Gigabyte of memory, respectively. 
  Table \ref{table:comp} presents the different experiment scenarios with different numbers of clusters, nodes per cluster and problem sizes. A name, consisting in the values of these parameters  was given to each scenario.
  
  \begin{table}[!t]
  \caption{The different experiment scenarios}
  % title of Table
  \centering
  \begin{tabular}{|*{7}{r|}}
    \hline
    Platform       & Clusters   & Number of nodes  &Vector   & Total number of      \\
    scenario       & number     & in cluster       &size     & nodes in grid         \\
    \hline
    Grid.4*4.400      & 4           & 4                &$400^3$    &16  \\
    \hline
    Grid.4*8.400      & 4           & 8                &$400^3$    &32 \\
    \hline
    Grid.8*4.400      & 8           & 4                &$400^3$    &32 \\
    \hline
    Grid.8*8.400      & 8           & 8                &$400^3$    &64 \\
    \hline
    Grid.4*4.500      & 4           & 4                &$500^3$    &16 \\
    \hline
    Grid.4*8.500      & 4           & 8                &$500^3$    &32 \\
    \hline
    Grid.8*4.500      & 8           & 4                &$500^3$    &32 \\
    \hline
    Grid.8*8.500      & 8           & 8                &$500^3$    &64 \\
    \hline
  \end{tabular}
  \label{table:comp}
\end{table}

This section focuses on the execution time and the energy consumed by 
the MS application while running over the grid platform without using DVFS operations.
The energy consumption of the synchronous and asynchronous MS was
measured using the energy Equations \ref{eq:energy-grid} and \ref{eq:asyn_energy} respectively.
Figures \ref{fig:eng_time_ms} (a) and (b)  show the energy consumption 
and the execution time, respectively,  of the multi-splitting application running over a heterogeneous grid 
with different numbers of clusters and nodes per cluster. 
The synchronous and the asynchronous versions of the MS application were executed over  each scenario in  Table \ref{table:comp}. 
As shown in Figure  \ref{fig:eng_time_ms} (a), the asynchronous MS consumes more
energy than the synchronous one. Indeed, the asynchronous application overlaps the asynchronous communications with  computations and thus it executes more iterations than the synchronous one and has no slack times. More computations result in  more dynamic energy consumption by the CPU in the asynchronous MS and since the dynamic power is chosen to be four times higher than the static power, the asynchronous MS method consumes  more  overall energy than the synchronous one.  However, the execution times of the experiments, presented in Figure \ref{fig:eng_time_ms} (b), show that the execution times of the 
asynchronous MS are smaller than the execution times of the synchronous one. Indeed, in the 
asynchronous application the fast nodes do not have to wait for the slower ones to exchange data. So there are no slack times and more iterations are executed by fast nodes which  accelerates the convergence  to the final solution.

\begin{figure}[!t]
  \centering
 \centering
    \includegraphics[width=.80\textwidth]{fig/ch4/energy_ms.eps}\\~~~~~~(a)\\
    \includegraphics[width=.82\textwidth]{fig/ch4/time_ms.eps}\\~~~~~~~~(b)
  \caption{(a) energy consumption and (b) execution time of multi-splitting application without applying the HSA algorithm}
   \label{fig:eng_time_ms}
\end{figure}


The synchronous and asynchronous MS scale well. The execution times of both methods decrease linearly with the increase of the 
number of computing nodes in the grid, whereas the energy consumption is approximately 
the same when the number of computing nodes increases. Therefore,  the energy consumption 
of this application is not directly related to  the number of computing nodes. 

\subsection{The results of the scaling factor selection algorithm}
 \label{ch4:7:2}
 The scaling factor selection algorithm~\ref{HSA-asyn} was applied to both
 synchronous and asynchronous MS applications which  were 
 executed over the 8 possible scenarios presented in  table~\ref{table:comp}.
 The  DVFS algorithm \ref{dvfs} needs to send and receive some information before 
 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
    \includegraphics[width=.82\textwidth]{fig/ch4/energy_dvfs.eps}\\~~~~~~~(a)\\
    \includegraphics[width=.80\textwidth]{fig/ch4/time_dvfs.eps}\\~~~~~~~~(b)
  \caption{(a) energy consumption and (b) execution time of different versions of the multi-splitting application after applying the HSA algorithm}
  \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 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 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.
 
 \end{enumerate}
 
 \begin{figure}[!t]
  \centering
    \includegraphics[scale=0.7]{fig/ch4/energy_saving.eps}
    \caption{The energy saving percentages after applying the HSA algorithm to the different versions and scenarios}
  \label{fig:energy_saving}
\end{figure}


 The energy  saving percentage is the ratio between the  reduced energy consumption after applying the HSA   algorithm and the original energy consumption of synchronous MS without DVFS. 
 Whereas, the performance degradation  percentage is the ratio between the original execution time of the synchronous MS without DVFS and the new execution time after applying the HSA algorithm.
Therefore, in this section, the synchronous MS method without DVFS serves  as a reference for comparison with the other methods for the following terms: energy saving, performance degradation and the distance between the two previous terms.
 
 In Figure \ref{fig:energy_saving}, the energy saving is computed for the four versions of the  MS method which  
 are the  synchronous or asynchronous MS that apply synchronously or asynchronously  the HSA algorithm. 
 The fifth  version is the asynchronous MS without any DVFS operations. Figure \ref{fig:energy_saving} shows that some versions have positive or negative energy saving percentages which means that the corresponding version respectively consumes less or more energy than the reference method.
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}[!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}[!h]
  \centering
    \includegraphics[scale=0.7]{fig/ch4/dist.eps}
  \caption{The results of the tradeoff distance}
  \label{fig:dist}
\end{figure}

Figure \ref{fig:perf_degr} shows that some versions have negative performance 
degradation percentages which 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 version that gives the  best execution time is the 
 asynchronous MS without DVFS which on average outperforms the synchronous MS without DVFS version by 
 $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 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.
 The asynchronous MS applying synchronously the HSA algorithm gives the best distance which is on average equal to $27.72\%$. 
 This version saves on average  up to $22\%$ of energy and on average speeds up  the application by $5.72\%$.  This overall improvement is due to combining asynchronous computing and the synchronous application of the HSA algorithm.
 
 
The two platform scenarios, Grid 4*8 and Grid 8*4, use the same 
number of computing  nodes but give different trade-off results. 
The versions applying the HSA algorithm and  running over the  Grid 4*8 platform, give higher  distance percentages than those running on the Grid 8*4 platform. In the Grid 8*4 platform scenario more clusters are used than in the Grid 4*8 platform and thus the global system  is divided into 8 small subsystems instead of 4. Indeed, each subsystem is assigned to a cluster and synchronously solved by the nodes of that cluster.  Dividing the global system into smaller subsystems, increases the number of outer iterations required for the global convergence of the system because for the multi-splitting system the more the system is decomposed the higher the spectral radius is.  For example, the asynchronous MS, applying synchronously the HSA algorithm, requires on average 135 outer  iterations  when running over the Grid 4*8 platform and  148 outer iterations  when running  over the Grid 8*4 platform. The increase in the number of executed iterations over the Grid 8*4 platform justifies the increase in energy consumption by applications running over that platform.
    
            
\subsection{Comparing the number of iterations executed by the different MS versions}
 \label{ch4:7:3}
 
 The heterogeneity in the computing power of the nodes in the grid has a direct 
 effect on the number of  iterations executed by the nodes of each cluster when running an asynchronous iterative  message passing method. The fast nodes execute more iterations than the slower ones because the iterations are not synchronized. 
 On the other hand, in the synchronous versions, all the nodes in all the clusters  have  the same number of iterations and have to wait for the slowest node to finish its iteration before starting the next iteration  because the iterations are synchronized. 
 
 When the fast nodes asynchronously execute more iterations than the slower ones, they consume more energy without significantly improving the global convergence of the system.  Reducing the frequency of the fast nodes will decrease the number of iterations executed by them.  If all the nodes, the fast and the slow ones, execute close numbers of iterations, the asynchronous application will consume less energy and its performance will not be significantly affected. 
 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]
\centering
\caption{The standard deviation of the numbers of iterations for different asynchronous MS versions running over different grid platforms}
\label{table:sd}
\begin{tabular}{|l|l|l|l|}
\hline
\multirow{2}{*}{\begin{tabular}[c]{@{}l@{}}Grid\\platform \end{tabular}} 
& \multicolumn{3}{c|}{Standard deviation}    \\ \cline{2-4} 
& \begin{tabular}[c]{@{}l@{}}Asyn. MS without \\  HSA\end{tabular} 
& \begin{tabular}[c]{@{}l@{}}Asyn. MS with \\ Asyn. HSA\end{tabular} 
& \begin{tabular}[c]{@{}l@{}}Asyn. MS with \\ Syn. HSA\end{tabular} \\ \hline
Grid.4*4.400     & 60.43       & 13.86     & 1.12   \\ \hline
Grid.4*8.400     & 58.06       & 27.43     & 1.22    \\ \hline
Grid.8*4.400     & 50.97       & 20.76     & 1.15    \\ \hline
Grid.8*8.400     & 52.46       & 48.40     & 2.38    \\ \hline
\end{tabular}
\end{table}

A small   standard deviation value  means that there is a very small difference between 
 the numbers of iterations executed by the nodes which means fast nodes did not uselessly execute more iterations than the slower ones and the application does not  waste a lot of energy. As shown in Table \ref{table:sd},
 the asynchronous MS  that applies synchronously the HSA algorithm has the best standard deviation value when  compared to the  other versions.  Two reasons explain the advantage of this method:
 \begin{enumerate}
\item  The applied HSA algorithm selects new frequencies that reduce the computation power of the fast nodes while maintaining the computation power of the slower nodes. Therefore, it tries to balance as much as possible the computation powers of the heterogeneous nodes. 

\item Applying synchronously the HSA algorithm scales down the frequencies of the CPUs at the end of the first iteration of the application. Therefore the computation power of all the nodes is balanced as much as possible since the beginning of the application. On the other hand,         applying asynchronously the  HSA algorithm onto the asynchronous MS application only changes the frequencies of the nodes after executing many iterations. Therefore, before the frequencies are scaled down, the fast nodes have enough time to execute many more iterations than the slower ones and consequently increase the overall energy consumption of the application.

 \end{enumerate}
 
Finally,  the asynchronous  MS version that does not apply the HSA algorithm gives the worst standard deviation values because there is a big difference between the numbers of iterations executed by the heterogeneous nodes. Therefore, this version consumes more energy than the other versions and thus saves less energy  as shown in  Figure \ref{fig:eng_time_dvfs} (a).
 
 
\subsection{Comparing different power scenarios}
 \label{ch4:7:4}
 
 In the previous sections, all the results were obtained by assuming that the dynamic and the static powers are respectively equal to 80\% and 20\% of the total power consumed by a CPU during computation at its highest frequency. The goal   
 of this section is to evaluate the proposed frequency scaling factors selection algorithm when 
 these two power ratios are changed. Two new power scenarios are proposed in this section:
 \begin{enumerate}
\item    The dynamic and the static power are respectively equal to  90\% and 10\%  of the total power consumed by a CPU during computation at its highest frequency. 
 \item  The dynamic and the static power are respectively equal to  70\% and 30\%  of the total power consumed by a CPU during computation at its highest frequency. 
 \end{enumerate} 
 The asynchronous MS method solving a 3D problem of size $400^3$ was executed over two 
 platform scenarios, the Grid 4*4 and Grid 8*4. Two versions of the asynchronous MS method, with synchronous or asynchronous application of the HSA algorithm, were evaluated on each platform scenario. 
  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}[!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}[!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}[!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}
  \label{fig:three_scenarios}
\end{figure}
 
  
 The displayed results are  the average of the percentages obtained from multiple runs.
 Both figures show that the  \np[\%]{90}-\np[\%]{10} power scenario gives the biggest  energy saving percentages. 
 The high dynamic power ratio pushes the HSA algorithm  to select bigger scaling factors 
 which decreases  exponentially the dynamic energy consumption. Figure \ref{fig:three_scenarios} shows that the HSA algorithm selects in the \np[\%]{90}-\np[\%]{10} power scenario  higher frequency scaling factors than in the other power scenarios for the same application. Moreover,  the \np[\%]{90}-\np[\%]{10} power scenario has the smallest static power consumption per CPU which reduces the effect of the performance degradation, due to scaling down the frequencies of the CPUs, on the total energy consumption of the application.  Finally, the  \np[\%]{90}-\np[\%]{10} power scenario gives higher distance percentages than the  other two scenarios which means the difference between the energy reduction and the performance degradation percentages is the highest for this scenario. From these observations, it can be concluded that in a  platform with CPUs that consume low static power and high dynamic  power, a lot of energy consumption can be reduced by applying the HSA algorithm but the performance degradation might be significant. 
   
The energy saving percentages are the smallest with the  \np[\%]{70}-\np[\%]{30} power scenario. The high static power consumption in this scenario force the HSA algorithm to select small scaling factors in order not to significantly decrease the performance of the application. Indeed, scaling down more the frequency of the CPUs will significantly increase the total execution time and consequently increase the static energy consumption which will outweigh the reduction of dynamic energy consumption. Finally, since the dynamic power consumption ratio is relatively small in this power scenario less dynamic energy reduction can be gained in lowering the frequencies of the CPUs than in the other power scenarios. On the other hand, the \np[\%]{70}-\np[\%]{30} power scenario's main advantage is that its performance suffers the least from the application of the HSA algorithm. From these observations, it can be concluded that in a  high static power model just a  small percentage of energy can be saved by applying the HSA algorithm.

The asynchronous application of the HSA algorithm on average 
improves the performance of the application more than the synchronous
application of the HSA algorithm. This difference can be explained by the fact that applying the HSA algorithm synchronously scales down the frequencies of the CPUs  after the first iteration, while applying  the HSA algorithm asynchronously scales them down after many iterations, depending on the heterogeneity of the platform. 
However, for the same reasons as above, the synchronous application of the HSA algorithm reduces the energy consumption more than the asynchronous one even though, the method applying the first has a bigger execution time than the one applying the  latter. 

\subsection{Comparing the HSA algorithm to the energy and delay product method}
\label{ch4:7:5}

Many methods have been proposed to optimize the trade-off between the energy  consumption and the performance of message passing applications. A well known optimization model used to solve this 
 problem is the energy and delay product, $\mathit{EDP}=\mathit{energy}\times \mathit{delay}$. 
In \cite{ref100,ref60,ref55}, the  researchers used equal weights for the energy and delay factors. 
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.
\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}
  \label{fig:compare_syndvfs_synms}
\end{figure}
\begin{figure}[!h]
  \centering
   \includegraphics[width=.7\textwidth]{fig/ch4/compare_syndvfs_asynms.eps}
   \caption{Synchronous application of the frequency scaling selection method on the asynchronous  MS version}
   \label{fig:compare_syndvfs_asynms}
\end{figure}
\begin{figure}[!h]
  \centering
  \includegraphics[width=.7\textwidth]{fig/ch4/compare_asyndvfs_synms.eps}
   \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}
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.





\section{The Experimental Results over Grid'5000}
\label{ch4:8}
The performance of algorithm ~(\ref{HSA-asyn}) was evaluated by
 executing  the iterative  multi-splitting method on the Grid'5000 textbed \cite{ref21}. 
 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}[!h]
  \caption{CPUs characteristics of the selected clusters}
  % title of Table
  \centering
  \begin{tabular}{|*{7}{c|}}
    \hline
    Cluster     & CPU          & Max Freq.  & Min Freq.  & Diff. Freq. & Site        & Dynamic power  \\
    Name        & model        & GHz    & GHz    & GHz   &             & of one core   \\
    \hline
     Taurus     & Intel       & 2.3   & 1.2     & 0.1    & Lyon      & \np[W]{35}    \\   
                & E5-2630     &       &         &        &           &     \\           
    \hline   
     Graphene   & Intel       & 2.53  & 1.2   & 0.133   & Nancy     & \np[W]{23}  \\  
                & X3440       &       &       &         &           &   \\             
    \hline
     Parapide   & Inte        & 2.93  & 1.6   & 0.133   & Rennes    & \np[W]{23}  \\
                & X5570       &       &       &         &           &   \\                                                                                                                                                    
    \hline           
    StRemi      & AMD         & 1.7   & 0.8   & 0.2     & Reims     & \np[W]{6} \\
                &6164 HE      &       &       &         &           &  \\ 
    \hline
  \end{tabular}
  \label{table:grid5000}
\end{table} 
The dynamic power of each core with maximum frequency is computed as the difference between the measured power of the core, only when it is  computing at maximum frequency,  and the measured power of that core when it is idle as in \ref{eq:pdyn}.  The CPUs' constructors do not specify the amount of static power their CPUs consume. Therefore, the static power consumption is assumed to be equal to  \np[\%]{20} of the dynamic power consumption. 
The experiments were conducted on problems of size $N=400^3$ and $N=500^3$  over 4 distributed clusters  described in Table \ref{table:grid5000}. Each cluster is composed of 8 homogeneous nodes.


Algorithm~\ref{HSA-asyn} was applied  synchronously and asynchronously to both  synchronous and asynchronous MS applications.
Figures \ref{fig:time-compare} and \ref{fig:energy-compare} show the energy consumption and the execution time of the multi-splitting application with and without the application of the HSA algorithm respectively.
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}[!h]
 \centering
  \includegraphics[width=.8\textwidth]{fig/ch4/time-compare.eps}
  \caption{ Comparing the execution time}
  \label{fig:time-compare}
 \end{figure} 

\begin{figure}[!h]
 \centering
  \includegraphics[width=.8\textwidth]{fig/ch4/energy-compare.eps}
  \caption{ Comparing the energy consumption}
  \label{fig:energy-compare}
 \end{figure} 
 

\begin{table}[!h]
\centering
\begin{tabular}{|l|l|l|l|l|}
\hline
Size                 & Method                      &\begin{tabular}[c]{@{}l@{}}Energy\\ saving \%\end{tabular} & \begin{tabular}[c]{@{}l@{}}Perf.  \\ degra.\%\end{tabular} & Distance \\ \hline
\multirow{4}{*}{400} & Sync MS with Sync DVFS       & 23.16      & 4.12        & 19.04   \\ \cline{2-5} 
                     & Sync MS with Async DVFS      & 18.36      & 2.59        & 15.77   \\ \cline{2-5} 
                     & Async MS with Sync DVFS      & 26.93      & -21.48      & 48.41    \\ \cline{2-5} 
                     & Async MS with Async DVFS     & 14.9       & -26.41      & 41.31   \\ \hline                     
\multirow{4}{*}{500} & Sync MS with Sync DVFS       & 24.57      & 3.15        & 21.42     \\ \cline{2-5} 
                     & Sync MS with Async DVFS      & 19.97      & 0.60        & 19.37     \\ \cline{2-5} 
                     & Async MS with Sync DVFS      & 20.69      & -10.95      & 31.64  \\ \cline{2-5} 
                     & Async MS with Async DVFS     & 9.06       & -18.22      & 27.28    \\ \hline
\end{tabular}
\caption{The experimental  results of  HSA algorithm}
\label{table:exper}
\end{table}

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 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. 





 
\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-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}[!h]
\centering
\caption{The EDP algorithm results over the Grid'5000}
\label{table:comapre}
\begin{tabular}{|l|l|l|l|}
\hline
Method name              & Energy saving \% & Perf. degra.\% & Distance \% \\ \hline
Sync MS with Sync DVFS   & 21.83            & 12.78          & 9.05     \\ \hline
Sync MS with Async DVFS  & 18.26            & 7.68           & 10.58    \\ \hline
Async MS with Sync DVFS  & 24.95            & -12.24         & 37.19    \\ \hline
Async MS with Async DVFS & 10.32            & -17.04         & 27.36    \\ \hline
\end{tabular}
\end{table}

\begin{figure}[!h]
  \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-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. 
The algorithm uses new 
energy and performance models  to predict the energy consumption and the execution time of asynchronous or hybrid message passing iterative applications running over grids.
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 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.
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 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.