%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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}}}}
-\chapter{Energy Optimization of homogeneous platforms}
+%% 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 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. 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 a very small overhead. The proposed algorithm
+takes into account both the computation and communication times of the Message Passing
+Interface (MPI) programs 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 have applied this algorithm to the NAS parallel
+benchmarks (NPB v3.3) developed by the NASA~\cite{ref65}. Our experiments are executed using the simulator
+SimGrid/SMPI v3.10~\cite{ref66} over an homogeneous
+distributed memory architecture.
+
+This chapter is composed of two parts. The first part, the proposed frequency scaling selection algorithm uses the energy model of the Rauber and Rünger \cite{ref47} and is compared to Rauber and Rünger's method. The comparison results show that our algorithm gives better energy-time trade-off. In the second part, a new energy model that takes into account both the communication and computation times of the MPI programs running over a homogeneous cluster is developed.
+It also shows the new results obtained using the new energy model. The results are compared to the ones given by Rauber and Rünger's 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 researchers. 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 algorithm that returns the scaling factor that gives the best energy-performance
+trade-off for a parallel application with iterations
+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 methods.
+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 are 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 factors, can be repeated as
+much as needed if the iterations are not regular. Kimura, Peraza, Yu-Liang et
+al.~\cite{ref61,ref55,ref62} used many 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 energy model 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 time and energy consumption of parallel tasks running on a homogeneous platform}
+\label{ch2:2}
+
+\subsection{Parallel tasks execution on a 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 the execution of synchronous tasks on distributed homogeneous
+platform. These tasks can synchronously exchange data via 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 a homogeneous platform (a) imbalanced communications and (b) imbalanced
+computations}
+\label{fig:homo}
+\end{figure}
+
+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 a 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 continue their computations. 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 consumption model for a homogeneous platform}
+\label{ch2:2:2}
+
+The total energy 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},~{i=1,2,\dots,N}
+\end{equation}
+
+Rauber and Rünger's scaling factor selection
+method 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 computes the frequency scaling factor which minimizes the energy consumption of the parallel program.
+
+\section{Performance evaluation of MPI programs}
+\label{ch2:3}
+
+The execution time of a parallel synchronous application with iteration is equal
+to the execution time of its slowest task as in figure~(\ref{fig:homo}).
+If there is no communication in the application and it is not data bounded, the execution time of this
+parallel application is linearly proportional to the operational frequency. 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 of the application. However, in most MPI applications the processes exchange
+data. During these communications the processors involved remain idle during a synchronous communication. 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 until 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 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}. 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 which gives the normalized performance and is computed 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 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}
+
+
+\begin{algorithm}[!t]
+ \caption{Scaling factor selection algorithm for a 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}
+
+
+Algorithm~\ref{EPSA} computes the optimal scaling factor according to the
+objective function described above.
+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. The experiments conducted over a homogeneous cluster and described in
+Section~\ref{ch2:6}, showed that this algorithm has a small execution time. It takes on average \np[$\mu$s]{1.52} for 4 nodes and \np[$\mu$s]{6.65} 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 \ref{EPSA} 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 execution time, $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. Seven MPI programs of the NAS
+parallel benchmarks were used: CG, MG, EP, FT, BT, LU and SP. Table \ref{table:NAS-dec} shows
+the description of these seven benchmarks. Some of these benchmarks are considered MPI parallel applications with synchronous iterations or iterative applications that repeat the same block of instructions until convergence.
+However, the proposed method can be applied to any application that executes the same block
+of instructions many times and it is not limited to iterative methods.
+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 depending on the executed benchmark. The smallest prediction error
+was for CG and the worst one was for LU.
+
+\begin{table}[!t]
+\centering
+\caption{NAS Benchmarks description}
+\label{table:NAS-dec}
+\begin{tabular}{|l|l|l|}
+\hline
+Benchmark & Full Name & Description \\ \hline
+CG & Conjugate Gradiant & \begin{tabular}[c]{@{}l@{}}
+It solves a system of linear equations by estimating\\ the smallest eigenvalue of a large sparse matrix \end{tabular}\\ \hline
+
+MG & MultiGrid & \begin{tabular}[c]{@{}l@{}}It uses the multigrid method to approximate the solution \\of a three-dimensional discrete Poisson equation\end{tabular}
+ \\ \hline
+EP & Embarrassingly Parallel & \begin{tabular}[c]{@{}l@{}} It applies the Marsaglia polar method to randomly \\generates independent Gaussian variates
+\end{tabular} \\ \hline
+FT & Fast Fourier Transform & \begin{tabular}[c]{@{}l@{}}It uses the fast Fourier transform to solve a \\ three-dimensional partial differential equation
+
+\end{tabular} \\ \hline
+BT & Block Tridiagonal & \multirow{3}{*}{\begin{tabular}[c]{@{}l@{}} \\They solve nonlinear partial differential equations \end{tabular}} \\ \cline{1-2}
+LU & \begin{tabular}[c]{@{}l@{}}Lower-Upper symmetric \\ Gauss-Seidel\end{tabular} & \\ \cline{1-2}
+SP & \begin{tabular}[c]{@{}l@{}}Scalar Pentadiagonal\end{tabular} & \\ \hline
+\end{tabular}
+\end{table}
+
+\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 in
+ascending order from class A to C. The classes A, B and C were executed on 4, 8 or 9 and 16 nodes respectively. The energy consumption for all the NAS MPI programs was measured while assuming that the dynamic power with
+the highest frequency is equal to 20 W and the static power is equal to
+4 W for all the 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 the discovered frequency scaling factors
+optimize both the energy and the performance simultaneously for all the NAS
+benchmarks. In table~(\ref{table:factors results}), the optimal
+scaling factors results for each benchmark running class C are presented. 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. In EP there are no communication inside the iterations, which leads our algorithm to select smaller scaling factors (inducing smaller energy savings).
+
+
+\subsection{Results comparison}
+\label{ch2:6:3}
+In this section, we compare our scaling factor selection method with the Rauber and
+Rünger's method~\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
+(the scale $S=1$) to keep the performance from degradation as mush as
+possible. We refer to this scenario as $R_{E-P}$ and 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
+the Rauber and Rünger's 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) has been degraded more than the
+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 the Rauber and Rünger's method, ($R_{E-P}$), gives sometimes negative
+trade-offs such as for BT and EP.
+
+
+\section{The new energy model for a 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 metric 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 a 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 Rauber and Rünger's 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 only consumes the dynamic power during computation time. Moreover, the CPU involved remains idle during the communication times and only consumes the static power, see \cite{ref53}. We have also conducted some experiments over a real homogeneous cluster where some MPI programs of the NAS benchmarks were executed while varying the CPUs frequencies at each execution. The results prove that changing the frequency does not effect on the communication times of these programs. Therefore, the frequency scaling factor $S$ can increase the computation times proportionally to its value, and does not effect the communication times. This assumption consort with 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 a homogeneous cluster all the computing nodes have the same specification and thus their CPUs 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 application.
+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 all the tasks are synchronised and have the same execution time.
+Therefore, the energy consumption model of $N$ parallel task executed synchronously over a homogeneous platforms can be represented as 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$ reduces 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 applications with synchronous iterations after gathering the computation and communication times of the first iteration.
+Furthermore, it can be used to measure the energy consumption of the parallel application with iterations by multiplying the energy consumed of all tasks in one iteration by the number of the iterations.
+
+This model is used by the algorithm \ref{EPSA} to predict the energy consumption and to select the optimal frequency scaling factor. The new frequency $F_i$ can be computed as in \ref{eq:fi} while using the new selected frequency scaling factor.
+In the next section, algorithm \ref{EPSA} is re-evaluated while using this new energy model and the new results are presented.
+
+\section{The experimental results using the new energy model}
+\label{ch2:8}
+
+This section presents the results of applying the frequency selection algorithm \ref{EPSA} using the new proposed energy model \ref{eq:e-new} to NAS parallel benchmarks.
+The class C of the benchmarks was executed on a homogeneous architecture composed of 16 nodes and simulated by SimGrid. The same static and dynamic power values were used as in section \ref{ch2:6:2}. Figure \ref{fig:energy_con} presents the energy consumption of the NAS benchmarks class C using the new energy model and the Rauber and Rünger's model. 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 consumes less energy using the new model than when using the Rauber and Rünger's model.
+Two reasons explain 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 only consumed during the computation time, while the other model assumes that the dynamic power is consumed during both computation and communication times and thus increasing the dynamic energy consumption.
+The second reason is related to the execution time. In the new model only the computation times are increased when the frequency of a processor is scaled down, while
+Rauber and Rünger's model indicates that both the computation and communication times
+are increased according to the scaling factor and hence more static energy is consumed. Therefore, the MPI programs that have big communication times, have bigger energy consumption values using Rauber and Rünger's model when compared to the new model as for the CG, SP, LU and FT benchmarks. Whereas, if the MPI programs have very small communication times, their computed energy values have very small differences using both models such as for the MG and BT benchmarks, or they are identical such as for the 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 estimated using Rauber energy model and our own}
+ \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 the energy saving and performance degradation percentages when applying the frequency selecting algorithm using the new proposed energy model. It also presents the new selected frequency scaling factors and compares them to the ones used by the Rauber and Rünger's model. It shows that the new selected frequency scaling factors are smaller than those selected using the other model because the predicted energies by the new energy model are smaller.
+Consequently, less energy savings and performance degradation percentages are produced according to
+these smaller frequency scaling factors such as for the CG, MG, LU, SP and FT benchmarks. While in the BT and EP benchmarks where there are very small or no communication times, similar scaling factors are selected because the predicted energies by the two models are approximately equivalent.
+
+Therefore, 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 message passing programs running over homogeneous clusters.
+The scaling factor selection algorithm can work with any energy model and it selects the scaling factor values according to the predicted energy values.
+
+\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 the Rauber and Rünger's
+method while being executed on the SimGrid simulator. The results showed that
+our method, outperforms the Rauber and Rünger's method in terms of energy-performance
+ratio. Finally, this chapter presents a new energy consumption model for parallel
+ applications with synchronous iterations running on homogeneous clusters. This model takes into consideration
+both the computation and communication times and their relation with the frequency scaling
+factor. The results obtained using the new energy model have shown that different frequency scaling factors
+were selected which gave new experimental results that are more accurate and realistic.
\ No newline at end of file
