adding the second chapter

[ThesisAhmed.git] / CHAPITRE_02.tex

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

\newcommand{\AG}[2][inline]{%
  \todo[color=green!50,#1]{\sffamily\textbf{AG:} #2}\xspace}
\newcommand{\JC}[2][inline]{%
  \todo[color=red!10,#1]{\sffamily\textbf{JC:} #2}\xspace}

\newcommand{\Xsub}[2]{{\ensuremath{#1_\mathit{#2}}}}

%% used to put some subscripts lower, and make them more legible
\newcommand{\fxheight}[1]{\ifx#1\relax\relax\else\rule{0pt}{1.52ex}#1\fi}

\newcommand{\Tcomp}[1][]{\Xsub{T}{comp}_{#1}}
\renewcommand*\npunitcommand[1]{\text{#1}}


\chapter{Energy optimization of homogeneous platform}
\label{ch2}

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

Dynamic Voltage and Frequency Scaling (DVFS) can be applied to modern CPUs. This technique is 
usually used to reduce the energy consumed by a CPU while computing. Indeed,
power consumption by a processor at a given time is exponentially related to its frequency. 
Thus, decreasing the frequency reduces the power consumed by the CPU. However, it can also 
significantly affect the performance of the executed program if it is compute bound and 
if a low CPU frequency is selected. The performance degradation ratio can even be higher 
than the saved energy ratio. Therefore, the chosen frequency scaling factor must give the best possible
trade-off between energy reduction and performance. This chapter presents an algorithm 
that predicts the energy consumed with each frequency gear and selects the one that gives 
the best ratio between energy consumption reduction and performance. Furthermore, the main
objective of HPC systems is to execute as fast as possible the application. Therefore, our 
algorithm selects the scaling factor online with very small overhead.  The proposed algorithm 
takes into account both the computation and communication times of the Message passing 
programs (MPI) to choose the frequency scaling factor. 
This algorithm has the ability to predict both energy consumption and execution time over 
all available scaling factors.  The prediction achieved depends on some computing time information,
gathered at the beginning of the runtime.  We apply this algorithm to seven MPI
benchmarks.  These MPI programs are the NAS parallel benchmarks (NPB v3.3)
developed by NASA~\cite{ref65}.  Our experiments are executed using the simulator
SimGrid/SMPI v3.10~\cite{ref66} over an homogeneous
distributed memory architecture. 

Mainly there are two tasks in this chapter, the first one is showed the results of the proposed frequency scaling selection algorithm  using the energy model of the Rauber and Rünger \cite{ref47}. Furthermore, the proposed algorithm  is compared with Rauber and Rünger's method.  The comparison results show that our algorithm gives better energy-time trade-off. In the second task,  a new energy model  that takes into account both the communication and computation times of the MPI programs running over homogeneous cluster is developed.
It  also shows the new results obtained using the new energy model and comparing them with the ones use Rauber and Rünger energy model.  


This chapter is organized as follows:  Section~\ref{ch2:2} explains the execution
of parallel tasks and the sources of slack times.  It also presents an energy
model for homogeneous platforms from other authors.  Section~\ref{ch2:3} describes how the
performance of MPI programs can be predicted.  Section~\ref{ch2:4} presents
the energy-performance objective function that maximizes the reduction of energy
consumption while minimizing the degradation of the program's performance.
Section~\ref{ch2:5} details the proposed energy-performance algorithm.
Section~\ref{ch2:6} verifies the accuracy of the performance prediction model
and presents the results of the proposed algorithm.  It also shows the
comparison results between our method and other existing method.  
Section~\ref{ch2:7} describes the new proposed energy consumption model for 
homogeneous platforms. Section~\ref{ch2:8} presents the experimental results 
of using the new energy model. Finally,  section~\ref{ch2:9} summarizes this chapter.


\section{Related works}
\label{sec.relwork}


In this section, some heuristics to compute the scaling factor are presented and
classified into two categories: offline and online methods.

\subsection{Offline scaling factor selection methods}

The offline scaling factor selection methods are executed before the runtime of
the program.  They return static scaling factor values to the processors
participating in the execution of the parallel program.  On the one hand, the
scaling factor values could be computed based on information retrieved by
analyzing the code of the program and the computing system that will execute it.
In~\cite{ref56}, Azevedo et al. detect during compilation the dependency points
between tasks in a multi-task program.  This information is then used to lower
the frequency of some processors in order to eliminate slack times.  A slack
time is the period of time during which a processor that has already finished
its computation, has to wait for a set of processors to finish their
computations and send their results to the waiting processor in order to
continue its task that is dependent on the results of computations being
executed on other processors.  Freeh et al. showed in~\cite{ref53} that the
communication times of MPI programs do not change when the frequency is scaled
down.  On the other hand, some offline scaling factor selection methods use the
information gathered from previous full or partial executions of the program. 
The whole program or, a part of it,  is usually executed over all the available frequency
gears and the execution time and the energy consumed with each frequency
gear are measured.  Then a heuristic or an exact method uses the retrieved
information to compute the values of the scaling factor for the processors.
In~\cite{ref57}, Xie et al. use an exact exponential breadth-first search algorithm
to compute the scaling factor values that give the optimal energy reduction
while respecting a deadline for a sequential program.  They also present a
linear heuristic that approximates the optimal solution.  In~\cite{ref58} , Rountree
et al. use a linear programming algorithm, while in~\cite{ref59,ref60}, Cochran et
al. use a multi-logistic regression algorithm for the same goal.  The main
drawback of these methods is that they all require executing the
whole program or, a part of it, on all frequency gears for each new instance of 
the same program.

\subsection{Online scaling factor selection methods}

The online scaling factor selection methods are executed during the runtime of
the program.  They are usually integrated into iterative programs where the same
block of instructions is executed many times.  During the first few iterations,
a lot of information is measured such as the execution time, the energy consumed
using a multimeter, the slack times, \dots{} Then a method will exploit these
measurements to compute the scaling factor values for each processor.  This
operation, measurements and computing new scaling factor, can be repeated as
much as needed if the iterations are not regular.  Kimura, Peraza, Yu-Liang et
al.~\cite{ref61,ref55,ref62} used varied heuristics to select the appropriate scaling
factor values to eliminate the slack times during runtime.  However, as seen
in~\cite{ref63,ref64}, machine learning methods can take a lot of time to converge
when the number of available gears is big.  To reduce the impact of slack times,
in~\cite{ref54}, Lim et al. developed an algorithm that detects the communication
sections and changes the frequency during these sections only.  This approach
might change the frequency of each processor many times per iteration if an
iteration contains more than one communication section.  In~\cite{ref53}, Rauber and
Rünger used an analytical model that can predict the consumed energy and the
execution time for every frequency gear after measuring the consumed energy and
the execution time with the highest frequency gear.  These predictions may be
used to choose the optimal gear for each processor executing the parallel
program to reduce energy consumption.  To maintain the performance of the
parallel program , they set the processor with the biggest load to the highest
gear and then compute the scaling factor values for the rest of the processors.
Although this model was built for parallel architectures, it can be adapted to
distributed architectures by taking into account the communication times.  The
primary contribution of this chapter is to present a new online scaling factor
selection method which has the following characteristics:
\begin{enumerate}
\item It is based on both  Rauber and Rünger and the new developed energy models to predict the energy consumption of the application with different frequency gears. 
\item It selects the frequency scaling factor for simultaneously optimizing
  energy reduction and maintaining performance.
\item It is well adapted to distributed architectures because it takes into
  account the communication time.
\item It is well adapted to distributed applications with imbalanced tasks.
\item It has a very small footprint when compared to other methods
  (e.g.,~\cite{ref64}) and does not require profiling or training as
  in~\cite{ref59,ref60}.
\end{enumerate}


\section{Execution and energy of parallel tasks on homogeneous platform}
\label{ch2:2}

\subsection{Parallel tasks execution on homogeneous platform}
\label{ch2:2:1}
A homogeneous cluster consists in identical nodes in terms of hardware and
software.  Each node has its own memory and at least one processor which can be
a multi-core.  The nodes are connected via a high bandwidth network.  Tasks
executed on this model can be either synchronous or asynchronous.  In this chapter
we consider execution of the synchronous tasks on distributed homogeneous
platform.  These tasks can exchange the data via synchronous message passing.



\begin{figure}[h!]
\centering
\centering
\includegraphics[scale=0.73]{fig/ch2/commtasks} 
\includegraphics[scale=0.73]{fig/ch2/compt}\\ ~ ~ ~ ~ ~  ~(a) ~ ~  ~ ~ ~  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~(b)
\caption{Parallel tasks execution on homogeneous platform (a) imbalanced communications and (b) imbalanced  
computations}
\label{fig:homo}
\end{figure}

Therefore, the execution time of a task consists in the computation time and the
communication time.  Moreover, the synchronous communications between tasks can
lead to slack times while tasks wait at the synchronization barrier for other
tasks to finish their tasks (see figure~\ref{fig:homo}(a)).  The imbalanced
communications happen when nodes have to send/receive different amounts of data
or they communicate with different numbers of nodes.  Other sources of slack
times are imbalanced computations.  This happens when processing different
amounts of data on each processor (see figure~\ref{fig:homo}(b)).  In this case the
fastest tasks have to wait at the synchronization barrier for the slowest ones
to begin the next task.  In both cases the overall execution time of the program
is the execution time of the slowest task as in EQ~(\ref{eq:T1}).
\begin{equation}
  \label{eq:T1}
  \textit{Program Time} = \max_{i=1,2,\dots,N} T_i
\end{equation}
where $T_i$ is the execution time of task $i$ and all the tasks are executed
concurrently on different processors.

\subsection{Energy model for homogeneous platform}
\label{ch2:2:2}

The total energy consumption model for a parallel homogeneous
platform, as presented by Rauber and Rünger~\cite{ref47}, can be written as a
function of the scaling factor $S$, as in EQ~\ref{eq:energy}.
Moreover, the scaling factor $S_1$ is the scaling factor which should be the
highest because they are proportional to the time values $T_i$.  Therefore, the scaling
factors of the others tasks $S_i$ are computed as in EQ~\ref{eq:si}.

\begin{equation}
  \label{eq:si}
  S_i = S \cdot \frac{T_1}{T_i}
      = \frac{F_{max}}{F_{new}} \cdot \frac{T_1}{T_i}
\end{equation}

We compare our algorithm with Rauber and Rünger's scaling factor selection
method which uses the same energy model.  In their method, the optimal scaling factor is
computed by minimizing the derivation of EQ~(\ref{eq:energy}) which produces
EQ~(\ref{eq:sopt}).

\begin{equation}
  \label{eq:sopt}
  S_\textit{opt} = \sqrt[3]{\frac{2}{N} \cdot \frac{P_\textit{dyn}}{P_\textit{static}} \cdot
    \left( 1 + \sum_{i=2}^{N} \frac{T_i^3}{T_1^3} \right) }
\end{equation}

This model is computed the frequency scaling factor which optimizes the energy consumption of the parallel
program into minimal level.

\section{Performance evaluation of MPI programs}
\label{ch2:3}

The execution time of a parallel synchronous iterative application is equal
to the execution time of the slowest task as in figure~(\ref{fig:homo}).  
If there is no communication and the application is not data bounded, the execution time of a
parallel program is linearly proportional to the operational frequency and any
DVFS operation for energy reduction increases the execution time of the parallel
program.  Therefore, the scaling factor $S$ is linearly proportional to the
execution time.  However, in most MPI applications the processes exchange
data.  During these communications the processors involved remain idle until the
communications are finished.  For that reason, any change in the frequency has no
impact on the time of communication~\cite{ref53}.  The communication time for a
task is the summation of periods of time that begin with an MPI call for sending
or receiving a message till the message is synchronously sent or received.  To
be able to predict the execution time of MPI program, the communication time and
the computation time for the slowest task must be measured before scaling.  These
times are used to predict the execution time for any MPI program as a function
of the new scaling factor as in EQ~(\ref{eq:tnew}).
\begin{equation}
  \label{eq:tnew}
 \textit  T_\textit{new} = T_\textit{Max Comp Old} \cdot S + T_{\textit{Min Comm Old}}
\end{equation}
In this chapter, this prediction method is used to select the best scaling factor
for each processor as presented in the next section.



\section{Performance and energy reduction trade-off}
\label{ch2:4}
This section presents our method for choosing the optimal scaling factor that
gives the best tradeoff between energy reduction and performance. This method
takes into account the execution times for both computation and communication to
compute the scaling factor.  Since the energy consumption and the performance
are not measured using the same metric, a normalized value of both measurements
can be used to compare them.  The normalized energy is the ratio between the
consumed energy with scaled frequency and the consumed energy without scaled
frequency:

\begin{equation}
  \label{eq:enorm}
  E_\textit{Norm} = \frac{ E_\textit{Reduced}}{E_\textit{Original}} 
         = \frac{P_\textit{dyn} \cdot S_1^{-2} \cdot
               \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
               P_\textit{static} \cdot T_1 \cdot S_1 \cdot N  }{
              P_\textit{dyn} \cdot \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
              P_\textit{static} \cdot T_1 \cdot N }
\end{equation}
In the same way we can normalize the performance as follows:
\begin{equation}
  \label{eq:pnorm}
  T_\textit{Norm} = \frac{T_\textit{New}}{T_\textit{Old}}
          = \frac{T_\textit{Max Comp Old} \cdot S +
           T_\textit{Min Comm Old}}{T_\textit{Max Comp Old} +
           T_\textit{Min Comm Old}}
\end{equation}

The relation between the execution time and the consumed energy of a program is nonlinear and complex. In consequences,  the relation between the consumed energy and the scaling factor is also nonlinear, for more details refer to~\cite{ref53}. Therefore, the resulting normalized energy consumption curve and execution time curve, for different scaling factors, do not have the same direction see Figure~\ref{fig:rel}(b).  To tackle this problem and optimize both terms,  we inverse the equation of the normalized execution time (normalized performance) as follows:

\begin{equation}
  \label{eq:pnorm_en}
   P_\textit{Norm} = \frac{ T_\textit{old}}{ T_\textit{new}}
               = \frac{T_\textit{max Comp Old} +
                 T_\textit{min Comm Old}}{T_\textit{max Comp Old} \cdot S +
                 T_\textit{min Comm Old}}
\end{equation}

\begin{figure}[h!]
\centering
\centering
\includegraphics[scale=1]{fig/ch2/file}\\~ ~ ~ ~ ~(a) \\

\includegraphics[scale=1]{fig/ch2/file3}\\~ ~ ~ ~ ~(b)

\caption{The energy and performance relation (a) Converted relation and (b) Real relation}
\label{fig:rel}
\end{figure}

Then, we can model our objective function as finding the maximum distance
between the energy curve EQ~\ref{eq:enorm} and the inverse of the execution time (performance)
curve EQ~\ref{eq:pnorm_en} over all available scaling factors.  This
represents the minimum energy consumption with minimum execution time (better
performance) at the same time, see Figure~\ref{fig:rel}(a).  Then
our objective function has the following form:

\begin{equation}
  \label{eq:max1}
   MaxDist = \max_{j=1,2,\dots,F}
      (\overbrace{P_\textit{norm}(S_j)}^{\text{Maximize}} -
       \overbrace{E_\textit{norm}(S_j)}^{\text{Minimize}} )
\end{equation}
where $F$ is the number of available frequencies. Then we can select the optimal
scaling factor that satisfies EQ~\ref{eq:max1}.  Our objective function can
work with any energy model or static power values stored in a data file.
Moreover, this function works in optimal way when the energy curve has a convex
form over the available frequency scaling factors as shown in~\cite{ref48,ref47,ref64}.

\section{Optimal scaling factor for performance and energy}
\label{ch2:5}

Algorithm~\ref{EPSA} computes the optimal scaling factor according to the
objective function described above.

\begin{algorithm}[!t]
  \caption{Scaling factor selection algorithm for homogeneous cluster}
  \label{EPSA}
  \begin{algorithmic}[1]
    \State  Initialize the variable $Dist=0$
    \State Set dynamic and static power values.
    \State Set $P_{states}$ to the number of available frequencies.
    \State Set the variable $F_{new}$ to max. frequency,  $F_{new} = F_{max} $
    \State Set the variable $F_{diff}$ to the difference between two successive
           frequencies.
    \For {$j:=1$   to   $P_{states} $}
      \State $F_{new}=F_{new} - F_{diff} $
      \State $S = \frac{F_\textit{max}}{F_\textit{new}}$
      \State $S_i = S \cdot \frac{T_1}{T_i}
                  = \frac{F_\textit{max}}{F_\textit{new}} \cdot \frac{T_1}{T_i}$
             for $i=1,\dots,N$
      \State $E_\textit{Norm} =
          \frac{P_\textit{dyn} \cdot S_1^{-2} \cdot
                  \left( T_1 + \sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
                  P_\textit{static} \cdot T_1 \cdot S_1 \cdot N }{
                P_\textit{dyn} \cdot
                  \left(T_1+\sum_{i=2}^{N}\frac{T_i^3}{T_1^2}\right) +
                  P_\textit{static} \cdot T_1 \cdot N }$
      \State $P_{Norm}= \frac{T_{old}}{T_{new}}$
      \If{$(P_{Norm}-E_{Norm} > Dist)$}
        \State $S_{opt} = S$
        \State $Dist = P_{Norm} - E_{Norm}$
      \EndIf
    \EndFor
    \State  Return $S_{opt}$
  \end{algorithmic}
\end{algorithm}



The proposed algorithm works online during the execution time of the MPI
program.  It selects the optimal scaling factor after gathering the computation
and communication times from the program after one iteration.  Then the program
changes the new frequencies of the CPUs according to the computed scaling
factors. In our experiments over a homogeneous cluster described in
Section~\ref{ch2:6}, this algorithm has a small execution time. It takes
\np[$\mu$s]{1.52} on average for 4 nodes and \np[$\mu$s]{6.65} on average for 32
nodes.  The algorithm complexity is $O(F\cdot N)$, where $F$ is the number of
available frequencies and $N$ is the number of computing nodes.  The algorithm
is called just once during the execution of the program.  The DVFS algorithm
~\ref{dvfs} shows where and when the algorithm is called in the MPI
program.



\begin{algorithm}[!t]
  \caption{DVFS algorithm of homogeneous cluster}
  \label{dvfs}
  \begin{algorithmic}[1]
    \For {$k:=1$ to \textit{some iterations}}
      \State Computations section.
      \State Communications section.
      \If {$(k=1)$}
        \State Gather all times of computation and  communication from each node.
        \State Call algorithm~\ref{EPSA} with these times.
        \State Compute the new frequency from the returned optimal scaling factor.
        \State Set the new frequency to the CPU.
      \EndIf
    \EndFor
  \end{algorithmic}
\end{algorithm}


After obtaining the optimal scaling factor, the program calculates the new
frequency $F_i$ for each task proportionally to its time value $T_i$.  By
substitution of EQ~(\ref{eq:s}) in EQ~(\ref{eq:si}), we can calculate the new
frequency $F_i$ as follows:
\begin{equation}
  \label{eq:fi}
  F_i = \frac{F_\textit{max} \cdot T_i}{S_\textit{opt} \cdot T_\textit{max}}
\end{equation}
According to this equation all the nodes may have the same frequency value if
they have balanced workloads, otherwise, they take different frequencies when
having imbalanced workloads.  Thus, EQ~(\ref{eq:fi}) adapts the frequency of the
CPU to the nodes' workloads to maintain the performance of the program.

\section{Experimental results}
\label{ch2:6}
Our experiments are executed on the simulator SimGrid/SMPI v3.10.  We configure
the simulator to use a homogeneous cluster with one core per node.  The detailed
characteristics of our platform file are shown in
table~(\ref{table:platform-homo}).  Each node in the cluster has 18 frequency values
from  2.5 GHz to 800 MHz with 100 MHz  difference between each
two successive frequencies.  The simulated network link is 1 GB Ethernet
(TCP/IP).  The backbone of the cluster simulates a high performance switch.

\begin{table}[!t]
  \caption{Platform file parameters}
  % title of Table
  \centering
  \begin{tabular}{|*{7}{l|}}
    \hline
    Max      & Min      & Backbone        & Backbone         & Link         & Link            & Sharing \\
    Freq.    & Freq.    & Bandwidth       & Latency          & Bandwidth    & Latency         & Policy  \\
    \hline
    2.5      & 800       & 2.25  GBps     & 0.5  $\mu$s      & 1 GBps       &  50 $\mu$s      & Full    \\
    GHz      & MHz      &                 &                  &              &                 & Duplex  \\
    \hline
  \end{tabular}
  \label{table:platform-homo}
\end{table}
\subsection{Performance prediction verification}
\label{ch2:6:1}
In this section, the precision of the proposed performance prediction method 
based on EQ~(\ref{eq:tnew}) is evaluated by applying it to the NAS benchmarks.  
The NAS programs are executed with the class B option to compare the real execution 
time with the predicted execution time.  Each program runs offline with all available
scaling factors on 8 or 9 nodes (depending on the benchmark) to produce real
execution time values.  These scaling factors are computed by dividing the
maximum frequency by the new one see EQ~(\ref{eq:s}).
\begin{figure*}[h!]
  \centering 
  \centering 
  \centering
  \includegraphics[width=.49\textwidth]{fig/ch2/cg_per}
  \includegraphics[width=.49\textwidth]{fig/ch2/mg_pre}
  \includegraphics[width=.49\textwidth]{fig/ch2/bt_pre}
  \includegraphics[width=.49\textwidth]{fig/ch2/lu_pre}
  \caption{Comparing predicted to real execution time}
  \label{fig:pred}
\end{figure*}
%see Figure~\ref{fig:pred}
In our cluster there are 18 available frequency states for each processor.  This
leads to 18 run states for each program.  We use seven MPI programs of the NAS
parallel benchmarks: CG, MG, EP, FT, BT, LU and SP.~Figure~(\ref{fig:pred})
presents plots of the real execution times compared to the simulated ones.  The maximum
normalized error between these two execution times varies between 0.0073 to
0.031 dependent on the executed benchmark.  The smallest prediction error
was for CG and the worst one was for LU.


\subsection{The experimental results for the scaling algorithm }
\label{ch2:6:2}
The proposed algorithm was applied to seven MPI programs of the NAS benchmarks
(EP, CG, MG, FT, BT, LU and SP) which were run with three classes (A, B and C).
For each instance the benchmarks were executed on a number of processors
proportional to the size of the class.  Each class represents the problem size
ascending from  class A to C.  Additionally, depending on some speed up
points for each class we run the classes A, B and C on 4, 8 or 9 and 16 nodes
respectively.  Depending on EQ~(\ref{eq:energy}), we measure the energy
consumption for all the NAS MPI programs while assuming that the dynamic power with
the highest frequency is equal to 20 W and the power static is equal to
4 W for all experiments.  These power values were also used by Rauber and
Rünger in~\cite{ref47}.  The results showed that the algorithm selected different
scaling factors for each program depending on the communication features of the
program as in the plots~(\ref{fig:nas}).  These plots illustrate that there are
different distances between the normalized energy and the normalized 
performance curves, because there are different communication features for each
benchmark.  When there are little or no communications, the 
performance curve is very close to the energy curve.  Then the distance between
the two curves is very small.  This leads to small energy savings.  The opposite
happens when there are a lot of communication, the distance between the two
curves is big.  This leads to more energy savings (e.g. CG and FT), see
table~(\ref{table:factors results}).  All discovered frequency scaling factors
optimize both the energy and the performance simultaneously for all NAS
benchmarks.  In table~(\ref{table:factors results}), we record all optimal
scaling factors results for each benchmark running class C.  These scaling
factors give the maximum energy saving percentage and the minimum performance
degradation percentage at the same time from all available scaling factors.
\begin{figure*}[h!]
  \centering
  \includegraphics[width=.49\textwidth]{fig/ch2/ep}
  \includegraphics[width=.49\textwidth]{fig/ch2/cg}
  \includegraphics[width=.49\textwidth]{fig/ch2/sp}
  \includegraphics[width=.49\textwidth]{fig/ch2/lu}
  \includegraphics[width=.49\textwidth]{fig/ch2/bt}
  \includegraphics[width=.49\textwidth]{fig/ch2/ft}
  \caption{Optimal scaling factors for the predicted energy and performance of NAS benchmarks}
  \label{fig:nas}
\end{figure*}
\begin{table}[htb]
  \caption{The scaling factors results}
  % title of Table
  \centering
  \begin{tabular}{|l|*{4}{r|}}
    \hline
    Program & Optimal        & Energy    & Performance    & Energy-Perf. \\
    Name    & Scaling Factor & Saving \% & Degradation \% & Distance     \\
    \hline
    CG      & 1.56           & 39.23     & 14.88          & 24.35 \\
    \hline
    MG      & 1.47           & 34.97     & 21.70          & 13.27 \\
    \hline
    EP      & 1.04           & 22.14     & 20.73          &  1.41 \\
    \hline
    LU      & 1.38           & 35.83     & 22.49          & 13.34 \\
    \hline
    BT      & 1.31           & 29.60     & 21.28          &  8.32 \\
    \hline
    SP      & 1.38           & 33.48     & 21.36          & 12.12 \\
    \hline
    FT      & 1.47           & 34.72     & 19.00          & 15.72 \\
    \hline
  \end{tabular}
  \label{table:factors results}
  % is used to refer this table in the text
\end{table}

As shown in table~(\ref{table:factors results}), when the optimal scaling
factor has a big value we can gain more energy savings  as in CG and
FT benchmarks.  The opposite happens when the optimal scaling factor has a  small value as in BT and EP benchmarks.  Our algorithm selects a big scaling factor value when the
communication and  other slacks times are big and smaller ones in opposite
cases.  In EP there are no communication inside the iterations.  This leads our
algorithm to select smaller scaling factor values (inducing smaller energy
savings).


\subsection{Results comparison}
\label{ch2:6:3}
In this section, we compare our scaling factor selection method with Rauber and
Rünger methods~\cite{ref47}.  They had two scenarios, the first is to reduce energy
to the optimal level without considering the performance as in
EQ~(\ref{eq:sopt}).  We refer to this scenario as $R_{E}$.  The second scenario
is similar to the first except setting the slower task to the maximum frequency
(when the scale $S=1$) to keep the performance from degradation as mush as
possible.  We refer to this scenario as $R_{E-P}$.  While we refer to our
algorithm as EPSA (Energy to Performance Scaling Algorithm).  The comparison is
made in table ~\ref{table:compareC}.  This table shows the results of our method and
Rauber and Rünger scenarios for all the NAS benchmarks programs for class C.

\begin{table}[h!]
  \caption{Comparing results for the NAS class C}
  % title of Table
  \centering
  \begin{tabular}{|l|l|*{4}{r|}}
    \hline
    Method    & Program & Factor & Energy    & Performance    & Energy-Perf. \\
    Name      & Name    & Value  & Saving \% & Degradation \% & Distance     \\
    \hline
    % \rowcolor[gray]{0.85}
    $EPSA$    & CG      & 1.56   & 39.23     & 14.88          &  24.35 \\ \hline
    $R_{E-P}$ & CG      & 2.15   & 45.36     & 25.89          &  19.47 \\ \hline
    $R_{E}$   & CG      & 2.15   & 45.36     & 26.70          &  18.66 \\ \hline

    $EPSA$    & MG      & 1.47   & 34.97     & 21.69          &  13.27 \\ \hline
    $R_{E-P}$ & MG      & 2.15   & 43.65     & 40.45          &   3.20 \\ \hline
    $R_{E}$   & MG      & 2.15   & 43.64     & 41.38          &   2.26 \\ \hline

    $EPSA$    & EP      & 1.04   & 22.14     & 20.73          &   1.41 \\ \hline
    $R_{E-P}$ & EP      & 1.92   & 39.40     & 56.33          & -16.93 \\ \hline
    $R_{E}$   & EP      & 1.92   & 38.10     & 56.35          & -18.25 \\ \hline

    $EPSA$    & LU      & 1.38   & 35.83     & 22.49          &  13.34 \\ \hline
    $R_{E-P}$ & LU      & 2.15   & 44.97     & 41.00          &   3.97 \\ \hline
    $R_{E}$   & LU      & 2.15   & 44.97     & 41.80          &   3.17 \\ \hline

    $EPSA$    & BT      & 1.31   & 29.60     & 21.28          &   8.32 \\ \hline
    $R_{E-P}$ & BT      & 2.13   & 45.60     & 49.84          &  -4.24 \\ \hline
    $R_{E}$   & BT      & 2.13   & 44.90     & 55.16          & -10.26 \\ \hline

    $EPSA$    & SP      & 1.38   & 33.48     & 21.35          &  12.12 \\ \hline
    $R_{E-P}$ & SP      & 2.10   & 45.69     & 43.60          &   2.09 \\ \hline
    $R_{E}$   & SP      & 2.10   & 45.75     & 44.10          &   1.65 \\ \hline

    $EPSA$    & FT      & 1.47   & 34.72     & 19.00          &  15.72 \\ \hline
    $R_{E-P}$ & FT      & 2.04   & 39.40     & 37.10          &   2.30 \\ \hline
    $R_{E}$   & FT      & 2.04   & 39.35     & 37.70          &   1.65 \\ \hline
  \end{tabular}
  \label{table:compareC}
  % is used to refer this table in the text
\end{table}


\begin{figure*}[h!]
  \centering
 % \includegraphics[width=.6\textwidth]{fig/ch2/classA.eps}
  % \includegraphics[width=.6\textwidth]{fig/ch2/classB.eps}
  \includegraphics[width=.7\textwidth]{fig/ch2/classC.eps}
  \caption{Comparing our method to Rauber and Rünger's methods}
  \label{fig:compare}
\end{figure*}



As shown in the table~\ref{table:compareC}, the ($R_{E-P}$) method outperforms the ($R_{E}$)
method in terms of performance and energy reduction.  The ($R_{E-P}$) method
also gives better energy savings than our method.  However, although our scaling
factor is not optimal for energy reduction, the results in these tables prove
that our algorithm returns the best scaling factor that satisfy our objective
method: the largest distance between energy reduction and performance
degradation. Figure~\ref{fig:compare}  illustrates even better the distance between the energy reduction and performance degradation. The negative values mean that one of
the two objectives (energy or performance) have been degraded more than 
other.  The positive trade-offs with the highest values lead to maximum energy
savings while keeping the performance degradation as low as possible.  Our
algorithm always gives the highest positive energy to performance trade-offs
while Rauber and Rünger's method, ($R_{E-P}$), gives sometimes negative
trade-offs such as in BT and EP.


\section{The new energy model for homogeneous cluster}
\label{ch2:7}
As mentioned in chapter \ref{ch1} section \ref{ch1:3}, the power consumed by a processor is divided 
into two power metrics: the static and the dynamic power. The  first power metrics  is
consumed as long as the computing unit is on, while the other one is consumed when the processor is 
doing the computations. Consequentially, the energy consumed by an individual processor
to execute a given program can be computed as follows:


\begin{equation}
  \label{eq:eind1}
   E_\textit{ind} =  P_\textit{dyn} \cdot T_{Comp} + P_\textit{static} \cdot T
\end{equation}

where $T$ is the execution time of the program, $T_{Comp}$ is the computation
time and $T_{Comp} \leq T$.  $T_{Comp}$ may be equal to $T$ if there is no
communication, no slack time and no synchronization.

Applying DVFS operation leads to a new frequency state, which is represented by the frequency scaling factor $S$ computed as in the equation \ref{eq:s}. According to the Rauber and Rünger energy model \ref{eq:energy}, the dynamic energy is consumed during the overall program's execution time. This assumption is not precise because the CPU is only consumed the dynamic power during computation time. Moreover, the CPU involved remain idle during the communication times and only consumed the static power, see \cite{ref53}. Also, we have conducted some experiments over a real homogeneous cluster by running some MPI programs of the NAS  benchmarks. The results prove that  there is no effect of changing the frequency on the communication times of these programs.  Therefore, the frequency scaling factor $S$ can be increased the computation times  propositionally, while not effecting the communication times. This assumption is acceptable according the used performance prediction model \ref{eq:tnew}. This model is evaluated and its prediction accuracy is showed in section \ref{ch2:6:1}. Therefore, the new dynamic energy is the dynamic power multiplied by the new time of computation and is given by the following equation:

\begin{equation}
  \label{eq:Edyn_new}
   Ed_{New} = Pd_{Old} \cdot S^{-3} \cdot (T_{comp} \cdot S)= S^{-2} \cdot Pd_{Old} \cdot  T_{comp}
\end{equation}

The static power is related to the power leakage of the CPU and is consumed
during computation and even when idle. As in~\cite{ref47,ref46},
the static power of a processor is considered as constant during idle and
computation periods, and for all its available frequencies.  The static energy
is the static power multiplied by the execution time of the program.  According
to the execution time model in (\ref{eq:tnew}), the execution time of the
program is the sum of the computation and the communication times. The
computation time is linearly related to the frequency scaling factor, while this
scaling factor does not affect the communication time.  Then, the static energy of a
processor after scaling its frequency is computed as follows:
\begin{equation}
  \label{eq:Estatic_new}
  Es = P_{static} \cdot (T_{comp} \cdot S  + T_{comm})
\end{equation}

In particular, in the homogeneous cluster all the computing nodes have the same computing power and thus they have similar frequencies gears. The execution time of the MPI application is the execution time of the slowest task as shown in section \ref{ch2:2:1}. Therefore, the frequency scaling factor $S$ of the slowest task can be used to modelize the  energy consumption of the parallel tasks execution.
The dynamic energy consumed by $N$  parallel tasks  is the summation of all the dynamic energies of  all tasks during the computation time $\Tcomp[i]$  of  each task. The static energy of each task is the static power consumed during the execution time of the slower task because they are synchronised together.
Therefore, the energy consumption model of $N$ parallel task executed  synchronously over a homogeneous platforms is represented in \ref{eq:e-new}. 

\begin{equation}
  \label{eq:e-new}
 E_{new} = \sum_{i=1}^{N} {(S^{-2} \cdot Pd \cdot  \Tcomp[i])}  + 
  ( Ps \cdot  ( T_\textit{Max Comp Old} \cdot S + T_{\textit{Min Comm Old}} ) )  \cdot N
\end{equation}
 
According to this model, the frequency scaling factor $S$ reducing the energy consumption of the homogeneous architecture by a factor of $S^{-2}$ and increases the execution time by a factor of  $S$.
This model can be used to predict the energy consumption of the message passing synchronous iterative applications depending on the gathered computation and communication times from the first iteration.
Furthermore, it can be used to measured the energy consumption of the iterative application by multiplying the energy consumed of all tasks in  one iteration  by the number of the iterations. 

Consequently, this model is used in the prediction process of the energy consumption by the 
algorithm \ref{EPSA} to selects the optimal frequency scaling factor. By the same way in the last section, the new frequency $F_i$ can be computed as in \ref{eq:fi} depending on the new selected frequency scaling factor. 
In the next section, the algorithm \ref{EPSA} is reimplemented using this new energy model \ref{eq:e-new}  to select new frequency scaling factors and thus a new results are obtained. 

\section{The experimental results using the new energy model}
\label{ch2:8}

This section presents results of applying the frequency selection algorithm \ref{EPSA} using 
the new proposed energy model \ref{eq:e-new}. The algorithm is applied to NAS parallel benchmarks class 
C running on 16  computing nodes using the SimGrid simulator. Same values are used for the static and dynamic powers values as in section \ref{ch2:6:2}. Two measured energy consumptions of the NAS benchmarks class C using the new energy model and Rauber and Rünger's model are presented in the figure \ref{fig:energy_con}. The energy consumptions of both models are computed using similar parameters:  frequency scaling factors, dynamic and static powers values. As shown in this figure,  the majority  of the benchmarks  have smaller computed energies values using the new model compare to those use  Rauber and Rünger's model.
Indeed, there are two reasons explaining these differences in the energy consumptions. The first one is related to the dynamic power consumption, where the new energy model ensures that this power metric is consumed only during the computation time, while  the other model assumes to consume the dynamic power during both computation and communication times and thus more dynamic energy consumption is given.
The second one is related to the execution time,  that is only its computation times is increased with the 
scaling factor value in the new energy model, while other energy model indicates that both  the 
computation and communication times are increased with scaling factor and hence more static energy consumption is given.  Therefore, the MPI programs that have big communication times, they  have bigger measured energy consumption values using  Rauber and Rünger's model  compare to the new model as in CG, SP, LU and FT benchmarks. Whereas, if the MPI programs have very small communication times, their computed energy values have very small differences  such as in  MG and BT benchmarks, or they are identical such as in EP benchmark where there is no communication and no idle times. 


\begin{figure*}[h!]
  \centering
  \includegraphics[width=.7\textwidth]{fig/ch2/energy_con.eps}
  \caption{Comparing the energy consumptions measured using the new and Rauber energy  models}
  \label{fig:energy_con}
\end{figure*}
\begin{table}[h!]
\centering
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\multicolumn{1}{|c|}{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Method\\ Name\end{tabular}}} & \multicolumn{3}{c|}{Rauber  Energy Model Results}                                                                                                                                            & \multicolumn{3}{c|}{New Energy Model Results}                                                                                                                                                \\ \cline{2-7} 
\multicolumn{1}{|c|}{}                                                                          & \begin{tabular}[c]{@{}l@{}}Scaling\\ Factors\end{tabular} & \begin{tabular}[c]{@{}l@{}}Energy \\ Saving\%\end{tabular} & \begin{tabular}[c]{@{}l@{}}Performance\\ Degradation\%\end{tabular} & \begin{tabular}[c]{@{}l@{}}Scaling\\ Factors\end{tabular} & \begin{tabular}[c]{@{}l@{}}Energy \\ Saving\%\end{tabular} & \begin{tabular}[c]{@{}l@{}}Performance\\ Degradation\%\end{tabular} \\ \hline

CG      & 1.56      & 39.23       & 14.88       & 1.47       & 30.20       & 13.56     \\ \hline
MG      & 1.47      & 34.97       & 21.69       & 1.38       & 30.04       & 16.48      \\ \hline
EP      & 1.04      & 22.14       & 20.73       & 1.04       & 22.14       & 20.73       \\ \hline
LU      & 1.38      & 35.83       & 22.49       & 1.31       & 29.15       & 18.03       \\ \hline
BT      & 1.31      & 29.60       & 21.53       & 1.31       & 28.75       & 21.55        \\ \hline
SP      & 1.38      & 33.48       & 21.35       & 1.31       & 28.93       & 14.83        \\ \hline
FT      & 1.47      & 34.72       & 19.00       & 1.38       & 29.94       & 17.43        \\ \hline
\end{tabular}
\caption{The Results of NAS Parallel Benchmarks running on 16 nodes}
\label{table:new-res}
\end{table}

Table \ref{table:new-res} shows  results of energy saving and performance degradation percentages of applying the frequency selecting algorithm  using the new propose energy model. It also presents the new selected frequency scaling factor values and comparing them to ones use Rauber and Rünger's model. It indicates  that the new selected frequency scaling factors are smaller compared to those selected using  other model because the predicted energies by the new energy model are smaller.
Consequentially, less energy savings and performance degradation percentages are produced according to 
these smaller frequency scaling factors selected using the new energy model, such as in  CG, MG, LU, SP and FT benchmarks. While in BT and EP benchmarks where a very small or no communication times, similar scaling factors are selected because the predicted energies by the two models are approximately equivalent. 
On the other hand, the scaling factor selection algorithm can work with any energy model and  it selects proportionally the scaling factor values depending on the predicted energies values. 

As a results,  the new proposed energy model is more accurate than Rauber and Rünger's energy
model, because  it takes into consideration both the communication and idle times in addition to
the computation times of  MPI programs running over homogeneous clusters. 

\section{Conclusion}
\label{ch2:9}
In this chapter, a new online scaling factor selection method
that optimizes simultaneously the energy and performance of a distributed 
application running on a homogeneous cluster have been presented .  It uses the computation and
communication times measured at the first iteration to predict the energy
consumption and the performance of the parallel application at every available
frequency.  Then, it selects the scaling factor that gives the best trade-off
between energy reduction and performance which is the maximum distance between
the energy and the performance curves.  To evaluate this method, we
have applied it to the NAS benchmarks and it was compared to Rauber and Rünger
methods while being executed on the SimGrid simulator.  The results showed that
our method, outperforms Rauber and Rünger's methods in terms of energy-performance
ratio. Finally, this chapter presents a new energy consumption model for the parallel
synchronous iterative methods running on homogeneous clusters. This model takes into consideration 
both  the computation and communication times and them relation with the frequency scaling 
factor. The results obtained using the new energy model have shown selecting different frequency scaling factors than using other energy model and thus different experimental results have been produced.